libpgf
6.11.42
PGF - Progressive Graphics File
|
00001 /* 00002 * The Progressive Graphics File; http://www.libpgf.org 00003 * 00004 * $Date: 2006-05-18 16:03:32 +0200 (Do, 18 Mai 2006) $ 00005 * $Revision: 194 $ 00006 * 00007 * This file Copyright (C) 2006 xeraina GmbH, Switzerland 00008 * 00009 * This program is free software; you can redistribute it and/or 00010 * modify it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE 00011 * as published by the Free Software Foundation; either version 2.1 00012 * of the License, or (at your option) any later version. 00013 * 00014 * This program is distributed in the hope that it will be useful, 00015 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 * GNU General Public License for more details. 00018 * 00019 * You should have received a copy of the GNU General Public License 00020 * along with this program; if not, write to the Free Software 00021 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00022 */ 00023 00028 00029 #include "WaveletTransform.h" 00030 00031 #define c1 1 // best value 1 00032 #define c2 2 // best value 2 00033 00035 // Constructor: Constructs a wavelet transform pyramid of given size and levels. 00036 // @param width The width of the original image (at level 0) in pixels 00037 // @param height The height of the original image (at level 0) in pixels 00038 // @param levels The number of levels (>= 0) 00039 // @param data Input data of subband LL at level 0 00040 CWaveletTransform::CWaveletTransform(UINT32 width, UINT32 height, int levels, DataT* data) : 00041 #ifdef __PGFROISUPPORT__ 00042 m_ROIs(levels + 1), 00043 #endif 00044 m_nLevels(levels + 1), m_subband(0) { 00045 ASSERT(m_nLevels > 0 && m_nLevels <= MaxLevel + 1); 00046 InitSubbands(width, height, data); 00047 } 00048 00050 // Initialize size subbands on all levels 00051 void CWaveletTransform::InitSubbands(UINT32 width, UINT32 height, DataT* data) { 00052 if (m_subband) Destroy(); 00053 00054 // create subbands 00055 m_subband = new CSubband[m_nLevels][NSubbands]; 00056 00057 // init subbands 00058 UINT32 loWidth = width; 00059 UINT32 hiWidth = width; 00060 UINT32 loHeight = height; 00061 UINT32 hiHeight = height; 00062 00063 for (int level = 0; level < m_nLevels; level++) { 00064 m_subband[level][LL].Initialize(loWidth, loHeight, level, LL); // LL 00065 m_subband[level][HL].Initialize(hiWidth, loHeight, level, HL); // HL 00066 m_subband[level][LH].Initialize(loWidth, hiHeight, level, LH); // LH 00067 m_subband[level][HH].Initialize(hiWidth, hiHeight, level, HH); // HH 00068 hiWidth = loWidth >> 1; hiHeight = loHeight >> 1; 00069 loWidth = (loWidth + 1) >> 1; loHeight = (loHeight + 1) >> 1; 00070 } 00071 if (data) { 00072 m_subband[0][LL].SetBuffer(data); 00073 } 00074 } 00075 00077 // Compute fast forward wavelet transform of LL subband at given level and 00078 // stores result on all 4 subbands of level + 1. 00079 // Wavelet transform used in writing a PGF file 00080 // Forward Transform of srcBand and split and store it into subbands on destLevel 00081 // high pass filter at even positions: 1/4(-2, 4, -2) 00082 // low pass filter at odd positions: 1/8(-1, 2, 6, 2, -1) 00083 // @param level A wavelet transform pyramid level (>= 0 && < Levels()) 00084 // @param quant A quantization value (linear scalar quantization) 00085 // @return error in case of a memory allocation problem 00086 OSError CWaveletTransform::ForwardTransform(int level, int quant) { 00087 ASSERT(level >= 0 && level < m_nLevels - 1); 00088 const int destLevel = level + 1; 00089 ASSERT(m_subband[destLevel]); 00090 CSubband* srcBand = &m_subband[level][LL]; ASSERT(srcBand); 00091 const UINT32 width = srcBand->GetWidth(); 00092 const UINT32 height = srcBand->GetHeight(); 00093 DataT* src = srcBand->GetBuffer(); ASSERT(src); 00094 UINT32 row0, row1, row2, row3; 00095 UINT32 i, k; 00096 00097 // Allocate memory for next transform level 00098 for (i=0; i < NSubbands; i++) { 00099 if (!m_subband[destLevel][i].AllocMemory()) return InsufficientMemory; 00100 } 00101 00102 if (height >= FilterHeight) { 00103 // transform LL subband 00104 // top border handling 00105 row0 = 0; row1 = width; row2 = row1 + width; 00106 ForwardRow(&src[row0], width); 00107 ForwardRow(&src[row1], width); 00108 ForwardRow(&src[row2], width); 00109 for (k=0; k < width; k++) { 00110 src[row1] -= ((src[row0] + src[row2] + c1) >> 1); 00111 src[row0] += ((src[row1] + c1) >> 1); 00112 row0++; row1++; row2++; 00113 } 00114 LinearToMallat(destLevel, &src[0], &src[row0], width); 00115 00116 // middle part 00117 row3 = row2 + width; 00118 for (i=3; i < height-1; i += 2) { 00119 ForwardRow(&src[row2], width); 00120 ForwardRow(&src[row3], width); 00121 for (k=0; k < width; k++) { 00122 src[row2] -= ((src[row1] + src[row3] + c1) >> 1); 00123 src[row1] += ((src[row0] + src[row2] + c2) >> 2); 00124 row0++; row1++; row2++; row3++; 00125 } 00126 LinearToMallat(destLevel, &src[row0], &src[row1], width); 00127 row0 = row1; row1 = row2; row2 = row3; row3 += width; 00128 } 00129 00130 // bottom border handling 00131 if (height & 1) { 00132 for (k=0; k < width; k++) { 00133 src[row1] += ((src[row0] + c1) >> 1); 00134 row0++; row1++; 00135 } 00136 LinearToMallat(destLevel, &src[row0], NULL, width); 00137 } else { 00138 ForwardRow(&src[row2], width); 00139 for (k=0; k < width; k++) { 00140 src[row2] -= src[row1]; 00141 src[row1] += ((src[row0] + src[row2] + c2) >> 2); 00142 row0++; row1++; row2++; 00143 } 00144 LinearToMallat(destLevel, &src[row0], &src[row1], width); 00145 } 00146 } else { 00147 // if height to small 00148 row0 = 0; row1 = width; 00149 // first part 00150 for (k=0; k < height; k += 2) { 00151 ForwardRow(&src[row0], width); 00152 ForwardRow(&src[row1], width); 00153 LinearToMallat(destLevel, &src[row0], &src[row1], width); 00154 row0 += width << 1; row1 += width << 1; 00155 } 00156 // bottom 00157 if (height & 1) { 00158 LinearToMallat(destLevel, &src[row0], NULL, width); 00159 } 00160 } 00161 00162 if (quant > 0) { 00163 // subband quantization (without LL) 00164 for (i=1; i < NSubbands; i++) { 00165 m_subband[destLevel][i].Quantize(quant); 00166 } 00167 // LL subband quantization 00168 if (destLevel == m_nLevels - 1) { 00169 m_subband[destLevel][LL].Quantize(quant); 00170 } 00171 } 00172 00173 // free source band 00174 srcBand->FreeMemory(); 00175 return NoError; 00176 } 00177 00179 // Forward transform one row 00180 // high pass filter at even positions: 1/4(-2, 4, -2) 00181 // low pass filter at odd positions: 1/8(-1, 2, 6, 2, -1) 00182 void CWaveletTransform::ForwardRow(DataT* src, UINT32 width) { 00183 if (width >= FilterWidth) { 00184 UINT32 i = 3; 00185 00186 // left border handling 00187 src[1] -= ((src[0] + src[2] + c1) >> 1); 00188 src[0] += ((src[1] + c1) >> 1); 00189 00190 // middle part 00191 for (; i < width-1; i += 2) { 00192 src[i] -= ((src[i-1] + src[i+1] + c1) >> 1); 00193 src[i-1] += ((src[i-2] + src[i] + c2) >> 2); 00194 } 00195 00196 // right border handling 00197 if (width & 1) { 00198 src[i-1] += ((src[i-2] + c1) >> 1); 00199 } else { 00200 src[i] -= src[i-1]; 00201 src[i-1] += ((src[i-2] + src[i] + c2) >> 2); 00202 } 00203 } 00204 } 00205 00207 // Copy transformed rows loRow and hiRow to subbands LL,HL,LH,HH 00208 void CWaveletTransform::LinearToMallat(int destLevel, DataT* loRow, DataT* hiRow, UINT32 width) { 00209 const UINT32 wquot = width >> 1; 00210 const bool wrem = width & 1; 00211 CSubband &ll = m_subband[destLevel][LL], &hl = m_subband[destLevel][HL]; 00212 CSubband &lh = m_subband[destLevel][LH], &hh = m_subband[destLevel][HH]; 00213 UINT32 i; 00214 00215 if (hiRow) { 00216 for (i=0; i < wquot; i++) { 00217 ll.WriteBuffer(*loRow++); // first access, than increment 00218 hl.WriteBuffer(*loRow++); 00219 lh.WriteBuffer(*hiRow++); // first access, than increment 00220 hh.WriteBuffer(*hiRow++); 00221 } 00222 if (wrem) { 00223 ll.WriteBuffer(*loRow); 00224 lh.WriteBuffer(*hiRow); 00225 } 00226 } else { 00227 for (i=0; i < wquot; i++) { 00228 ll.WriteBuffer(*loRow++); // first access, than increment 00229 hl.WriteBuffer(*loRow++); 00230 } 00231 if (wrem) ll.WriteBuffer(*loRow); 00232 } 00233 } 00234 00236 // Compute fast inverse wavelet transform of all 4 subbands of given level and 00237 // stores result in LL subband of level - 1. 00238 // Inverse wavelet transform used in reading a PGF file 00239 // Inverse Transform srcLevel and combine to destBand 00240 // inverse high pass filter for even positions: 1/4(-1, 4, -1) 00241 // inverse low pass filter for odd positions: 1/8(-1, 4, 6, 4, -1) 00242 // @param srcLevel A wavelet transform pyramid level (> 0 && <= Levels()) 00243 // @param w [out] A pointer to the returned width of subband LL (in pixels) 00244 // @param h [out] A pointer to the returned height of subband LL (in pixels) 00245 // @param data [out] A pointer to the returned array of image data 00246 // @return error in case of a memory allocation problem 00247 OSError CWaveletTransform::InverseTransform(int srcLevel, UINT32* w, UINT32* h, DataT** data) { 00248 ASSERT(srcLevel > 0 && srcLevel < m_nLevels); 00249 const int destLevel = srcLevel - 1; 00250 ASSERT(m_subband[destLevel]); 00251 CSubband* destBand = &m_subband[destLevel][LL]; 00252 const UINT32 width = destBand->GetWidth(); 00253 const UINT32 height = destBand->GetHeight(); 00254 UINT32 row0, row1, row2, row3, i, k, origin = 0; 00255 00256 // allocate memory for the results of the inverse transform 00257 if (!destBand->AllocMemory()) return InsufficientMemory; 00258 DataT* dest = destBand->GetBuffer(); 00259 00260 #ifdef __PGFROISUPPORT__ 00261 const UINT32 srcLeft = (m_ROIs.ROIisSupported()) ? m_ROIs.Left(srcLevel) : 0; 00262 const UINT32 srcTop = (m_ROIs.ROIisSupported()) ? m_ROIs.Top(srcLevel) : 0; 00263 UINT32 destWidth = destBand->BufferWidth(); // destination buffer width; is valid only after AllocMemory 00264 PGFRect destROI = (m_ROIs.ROIisSupported()) ? m_ROIs.GetROI(destLevel) : PGFRect(0, 0, width, height); 00265 destROI.right = destROI.left + destWidth; 00266 destROI.bottom = __min(destROI.bottom, height); 00267 UINT32 destHeight = destROI.Height(); // destination buffer height 00268 00269 // update destination ROI 00270 if (destROI.left & 1) { 00271 destROI.left++; 00272 origin++; 00273 destWidth--; 00274 } 00275 if (destROI.top & 1) { 00276 destROI.top++; 00277 origin += destWidth; 00278 destHeight--; 00279 } 00280 00281 // init source buffer position 00282 UINT32 left = destROI.left >> 1; 00283 UINT32 top = destROI.top >> 1; 00284 00285 left -= srcLeft; 00286 top -= srcTop; 00287 for (i=0; i < NSubbands; i++) { 00288 m_subband[srcLevel][i].InitBuffPos(left, top); 00289 } 00290 #else 00291 PGFRect destROI(0, 0, width, height); 00292 const UINT32 destWidth = width; // destination buffer width 00293 const UINT32 destHeight = height; // destination buffer height 00294 00295 // init source buffer position 00296 for (i=0; i < NSubbands; i++) { 00297 m_subband[srcLevel][i].InitBuffPos(); 00298 } 00299 #endif 00300 00301 if (destHeight >= FilterHeight) { 00302 // top border handling 00303 row0 = origin; row1 = row0 + destWidth; 00304 MallatToLinear(srcLevel, &dest[row0], &dest[row1], destWidth); 00305 for (k=0; k < destWidth; k++) { 00306 ASSERT(row0 < destBand->m_size); 00307 ASSERT(row1 < destBand->m_size); 00308 dest[row0] -= ((dest[row1] + c1) >> 1); 00309 row0++; row1++; 00310 } 00311 00312 // middle part 00313 row2 = row1; row1 = row0; row0 = row0 - destWidth; row3 = row2 + destWidth; 00314 for (i=destROI.top + 2; i < destROI.bottom - 1; i += 2) { 00315 MallatToLinear(srcLevel, &dest[row2], &dest[row3], destWidth); 00316 for (k=0; k < destWidth; k++) { 00317 ASSERT(row0 < destBand->m_size); 00318 ASSERT(row1 < destBand->m_size); 00319 ASSERT(row2 < destBand->m_size); 00320 ASSERT(row3 < destBand->m_size); 00321 dest[row2] -= ((dest[row1] + dest[row3] + c2) >> 2); 00322 dest[row1] += ((dest[row0] + dest[row2] + c1) >> 1); 00323 row0++; row1++; row2++; row3++; 00324 } 00325 InverseRow(&dest[row0 - destWidth], destWidth); 00326 InverseRow(&dest[row1 - destWidth], destWidth); 00327 row0 = row1; row1 = row2; row2 = row3; row3 += destWidth; 00328 } 00329 00330 // bottom border handling 00331 if (destHeight & 1) { 00332 MallatToLinear(srcLevel, &dest[row2], 0, destWidth); 00333 for (k=0; k < destWidth; k++) { 00334 ASSERT(row0 < destBand->m_size); 00335 ASSERT(row1 < destBand->m_size); 00336 ASSERT(row2 < destBand->m_size); 00337 dest[row2] -= ((dest[row1] + c1) >> 1); 00338 dest[row1] += ((dest[row0] + dest[row2] + c1) >> 1); 00339 row0++; row1++; row2++; 00340 } 00341 InverseRow(&dest[row0 - destWidth], destWidth); 00342 InverseRow(&dest[row1 - destWidth], destWidth); 00343 InverseRow(&dest[row2 - destWidth], destWidth); 00344 } else { 00345 for (k=0; k < destWidth; k++) { 00346 ASSERT(row0 < destBand->m_size); 00347 ASSERT(row1 < destBand->m_size); 00348 dest[row1] += dest[row0]; 00349 row0++; row1++; 00350 } 00351 InverseRow(&dest[row0 - destWidth], destWidth); 00352 InverseRow(&dest[row1 - destWidth], destWidth); 00353 } 00354 } else { 00355 // destHeight to small 00356 row0 = origin; row1 = row0 + destWidth; 00357 // first part 00358 for (k=0; k < destHeight; k += 2) { 00359 MallatToLinear(srcLevel, &dest[row0], &dest[row1], destWidth); 00360 InverseRow(&dest[row0], destWidth); 00361 InverseRow(&dest[row1], destWidth); 00362 row0 += destWidth << 1; row1 += destWidth << 1; 00363 } 00364 // bottom 00365 if (destHeight & 1) { 00366 MallatToLinear(srcLevel, &dest[row0], 0, destWidth); 00367 InverseRow(&dest[row0], destWidth); 00368 } 00369 } 00370 00371 // free memory of the current srcLevel 00372 for (i=0; i < NSubbands; i++) { 00373 m_subband[srcLevel][i].FreeMemory(); 00374 } 00375 00376 // return info 00377 *w = destWidth; 00378 *h = destHeight; 00379 *data = dest; 00380 return NoError; 00381 } 00382 00384 // Inverse Wavelet Transform of one row 00385 // inverse high pass filter for even positions: 1/4(-1, 4, -1) 00386 // inverse low pass filter for odd positions: 1/8(-1, 4, 6, 4, -1) 00387 void CWaveletTransform::InverseRow(DataT* dest, UINT32 width) { 00388 if (width >= FilterWidth) { 00389 UINT32 i = 2; 00390 00391 // left border handling 00392 dest[0] -= ((dest[1] + c1) >> 1); 00393 00394 // middle part 00395 for (; i < width - 1; i += 2) { 00396 dest[i] -= ((dest[i-1] + dest[i+1] + c2) >> 2); 00397 dest[i-1] += ((dest[i-2] + dest[i] + c1) >> 1); 00398 } 00399 00400 // right border handling 00401 if (width & 1) { 00402 dest[i] -= ((dest[i-1] + c1) >> 1); 00403 dest[i-1] += ((dest[i-2] + dest[i] + c1) >> 1); 00404 } else { 00405 dest[i-1] += dest[i-2]; 00406 } 00407 } 00408 } 00409 00411 // Copy transformed coefficients from subbands LL,HL,LH,HH to interleaved format 00412 void CWaveletTransform::MallatToLinear(int srcLevel, DataT* loRow, DataT* hiRow, UINT32 width) { 00413 const UINT32 wquot = width >> 1; 00414 const bool wrem = width & 1; 00415 CSubband &ll = m_subband[srcLevel][LL], &hl = m_subband[srcLevel][HL]; 00416 CSubband &lh = m_subband[srcLevel][LH], &hh = m_subband[srcLevel][HH]; 00417 UINT32 i; 00418 00419 if (hiRow) { 00420 #ifdef __PGFROISUPPORT__ 00421 const bool storePos = wquot < ll.BufferWidth(); 00422 UINT32 llPos = 0, hlPos = 0, lhPos = 0, hhPos = 0; 00423 00424 if (storePos) { 00425 // save current src buffer positions 00426 llPos = ll.GetBuffPos(); 00427 hlPos = hl.GetBuffPos(); 00428 lhPos = lh.GetBuffPos(); 00429 hhPos = hh.GetBuffPos(); 00430 } 00431 #endif 00432 00433 for (i=0; i < wquot; i++) { 00434 *loRow++ = ll.ReadBuffer();// first access, than increment 00435 *loRow++ = hl.ReadBuffer();// first access, than increment 00436 *hiRow++ = lh.ReadBuffer();// first access, than increment 00437 *hiRow++ = hh.ReadBuffer();// first access, than increment 00438 } 00439 00440 if (wrem) { 00441 *loRow++ = ll.ReadBuffer();// first access, than increment 00442 *hiRow++ = lh.ReadBuffer();// first access, than increment 00443 } 00444 00445 #ifdef __PGFROISUPPORT__ 00446 if (storePos) { 00447 // increment src buffer positions 00448 ll.IncBuffRow(llPos); 00449 hl.IncBuffRow(hlPos); 00450 lh.IncBuffRow(lhPos); 00451 hh.IncBuffRow(hhPos); 00452 } 00453 #endif 00454 00455 } else { 00456 #ifdef __PGFROISUPPORT__ 00457 const bool storePos = wquot < ll.BufferWidth(); 00458 UINT32 llPos = 0, hlPos = 0; 00459 00460 if (storePos) { 00461 // save current src buffer positions 00462 llPos = ll.GetBuffPos(); 00463 hlPos = hl.GetBuffPos(); 00464 } 00465 #endif 00466 00467 for (i=0; i < wquot; i++) { 00468 *loRow++ = ll.ReadBuffer();// first access, than increment 00469 *loRow++ = hl.ReadBuffer();// first access, than increment 00470 } 00471 if (wrem) *loRow++ = ll.ReadBuffer(); 00472 00473 #ifdef __PGFROISUPPORT__ 00474 if (storePos) { 00475 // increment src buffer positions 00476 ll.IncBuffRow(llPos); 00477 hl.IncBuffRow(hlPos); 00478 } 00479 #endif 00480 } 00481 } 00482 00483 #ifdef __PGFROISUPPORT__ 00484 00485 00486 00487 void CWaveletTransform::SetROI(const PGFRect& rect) { 00488 // create and init ROIs 00489 SetROI(); 00490 00491 // create tile indices 00492 m_ROIs.CreateIndices(); 00493 00494 // compute tile indices 00495 m_ROIs.ComputeIndices(m_subband[0][LL].GetWidth(), m_subband[0][LL].GetHeight(), rect); 00496 00497 // compute ROIs 00498 UINT32 w, h; 00499 PGFRect r; 00500 00501 for (int i=0; i < m_nLevels; i++) { 00502 const PGFRect& indices = m_ROIs.GetIndices(i); 00503 m_subband[i][LL].TilePosition(indices.left, indices.top, r.left, r.top, w, h); 00504 //if (r.left & 1) r.left++; // ensures ROI starts at an even position 00505 //if (r.top & 1) r.top++; // ensures ROI starts at an even position 00506 m_subband[i][LL].TilePosition(indices.right - 1, indices.bottom - 1, r.right, r.bottom, w, h); 00507 r.right += w; 00508 r.bottom += h; 00509 m_ROIs.SetROI(i, r); 00510 } 00511 } 00512 00515 void CWaveletTransform::SetROI() { 00516 // create and init ROIs 00517 m_ROIs.CreateROIs(); 00518 00519 // set ROI references 00520 for (int i=0; i < m_nLevels; i++) { 00521 m_ROIs.SetROI(i, PGFRect(0, 0, m_subband[i][LL].GetWidth(), m_subband[i][LL].GetHeight())); 00522 m_subband[i][LL].SetROI(&m_ROIs); // LL 00523 m_subband[i][HL].SetROI(&m_ROIs); // HL 00524 m_subband[i][LH].SetROI(&m_ROIs); // LH 00525 m_subband[i][HH].SetROI(&m_ROIs); // HH 00526 } 00527 } 00528 00530 00532 void CROIs::CreateROIs() { 00533 if (!m_ROIs) { 00534 // create ROIs 00535 m_ROIs = new PGFRect[m_nLevels]; 00536 } 00537 } 00538 00540 void CROIs::CreateIndices() { 00541 if (!m_indices) { 00542 // create tile indices 00543 m_indices = new PGFRect[m_nLevels]; 00544 } 00545 } 00546 00554 void CROIs::ComputeTileIndex(UINT32 width, UINT32 height, UINT32 pos, bool horizontal, bool isMin) { 00555 ASSERT(m_indices); 00556 00557 UINT32 m; 00558 UINT32 tileIndex = 0; 00559 UINT32 tileMin = 0, tileMax = (horizontal) ? width : height; 00560 ASSERT(pos <= tileMax); 00561 00562 // compute tile index with binary search 00563 for (int i=m_nLevels - 1; i >= 0; i--) { 00564 // store values 00565 if (horizontal) { 00566 if (isMin) { 00567 m_indices[i].left = tileIndex; 00568 } else { 00569 m_indices[i].right = tileIndex + 1; 00570 } 00571 } else { 00572 if (isMin) { 00573 m_indices[i].top = tileIndex; 00574 } else { 00575 m_indices[i].bottom = tileIndex + 1; 00576 } 00577 } 00578 00579 // compute values 00580 tileIndex <<= 1; 00581 m = (tileMin + tileMax)/2; 00582 if (pos >= m) { 00583 tileMin = m; 00584 tileIndex++; 00585 } else { 00586 tileMax = m; 00587 } 00588 } 00589 } 00590 00596 void CROIs::ComputeIndices(UINT32 width, UINT32 height, const PGFRect& rect) { 00597 ComputeTileIndex(width, height, rect.left, true, true); 00598 ComputeTileIndex(width, height, rect.top, false, true); 00599 ComputeTileIndex(width, height, rect.right, true, false); 00600 ComputeTileIndex(width, height, rect.bottom, false, false); 00601 } 00602 00603 #endif // __PGFROISUPPORT__