libpgf
6.14.12
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 : m_nLevels(levels + 1) 00042 , m_subband(0) 00043 { 00044 ASSERT(m_nLevels > 0 && m_nLevels <= MaxLevel + 1); 00045 InitSubbands(width, height, data); 00046 #ifdef __PGFROISUPPORT__ 00047 m_ROIindices.SetLevels(levels + 1); 00048 #endif 00049 } 00050 00052 // Initialize size subbands on all levels 00053 void CWaveletTransform::InitSubbands(UINT32 width, UINT32 height, DataT* data) { 00054 if (m_subband) Destroy(); 00055 00056 // create subbands 00057 m_subband = new CSubband[m_nLevels][NSubbands]; 00058 00059 // init subbands 00060 UINT32 loWidth = width; 00061 UINT32 hiWidth = width; 00062 UINT32 loHeight = height; 00063 UINT32 hiHeight = height; 00064 00065 for (int level = 0; level < m_nLevels; level++) { 00066 m_subband[level][LL].Initialize(loWidth, loHeight, level, LL); // LL 00067 m_subband[level][HL].Initialize(hiWidth, loHeight, level, HL); // HL 00068 m_subband[level][LH].Initialize(loWidth, hiHeight, level, LH); // LH 00069 m_subband[level][HH].Initialize(hiWidth, hiHeight, level, HH); // HH 00070 hiWidth = loWidth >> 1; hiHeight = loHeight >> 1; 00071 loWidth = (loWidth + 1) >> 1; loHeight = (loHeight + 1) >> 1; 00072 } 00073 if (data) { 00074 m_subband[0][LL].SetBuffer(data); 00075 } 00076 } 00077 00079 // Compute fast forward wavelet transform of LL subband at given level and 00080 // stores result on all 4 subbands of level + 1. 00081 // Wavelet transform used in writing a PGF file 00082 // Forward Transform of srcBand and split and store it into subbands on destLevel 00083 // high pass filter at even positions: 1/4(-2, 4, -2) 00084 // low pass filter at odd positions: 1/8(-1, 2, 6, 2, -1) 00085 // @param level A wavelet transform pyramid level (>= 0 && < Levels()) 00086 // @param quant A quantization value (linear scalar quantization) 00087 // @return error in case of a memory allocation problem 00088 OSError CWaveletTransform::ForwardTransform(int level, int quant) { 00089 ASSERT(level >= 0 && level < m_nLevels - 1); 00090 const int destLevel = level + 1; 00091 ASSERT(m_subband[destLevel]); 00092 CSubband* srcBand = &m_subband[level][LL]; ASSERT(srcBand); 00093 const UINT32 width = srcBand->GetWidth(); 00094 const UINT32 height = srcBand->GetHeight(); 00095 DataT* src = srcBand->GetBuffer(); ASSERT(src); 00096 DataT *row0, *row1, *row2, *row3; 00097 00098 // Allocate memory for next transform level 00099 for (int i=0; i < NSubbands; i++) { 00100 if (!m_subband[destLevel][i].AllocMemory()) return InsufficientMemory; 00101 } 00102 00103 if (height >= FilterHeight) { 00104 // transform LL subband 00105 // top border handling 00106 row0 = src; row1 = row0 + width; row2 = row1 + width; 00107 ForwardRow(row0, width); 00108 ForwardRow(row1, width); 00109 ForwardRow(row2, width); 00110 for (UINT32 k=0; k < width; k++) { 00111 row1[k] -= ((row0[k] + row2[k] + c1) >> 1); 00112 row0[k] += ((row1[k] + c1) >> 1); 00113 } 00114 LinearToMallat(destLevel, row0, row1, width); 00115 row0 = row1; row1 = row2; row2 += width; row3 = row2 + width; 00116 00117 // middle part 00118 for (UINT32 i=3; i < height-1; i += 2) { 00119 ForwardRow(row2, width); 00120 ForwardRow(row3, width); 00121 for (UINT32 k=0; k < width; k++) { 00122 row2[k] -= ((row1[k] + row3[k] + c1) >> 1); 00123 row1[k] += ((row0[k] + row2[k] + c2) >> 2); 00124 } 00125 LinearToMallat(destLevel, row1, row2, width); 00126 row0 = row2; row1 = row3; row2 = row3 + width; row3 = row2 + width; 00127 } 00128 00129 // bottom border handling 00130 if (height & 1) { 00131 for (UINT32 k=0; k < width; k++) { 00132 row1[k] += ((row0[k] + c1) >> 1); 00133 } 00134 LinearToMallat(destLevel, row1, NULL, width); 00135 row0 = row1; row1 += width; 00136 } else { 00137 ForwardRow(row2, width); 00138 for (UINT32 k=0; k < width; k++) { 00139 row2[k] -= row1[k]; 00140 row1[k] += ((row0[k] + row2[k] + c2) >> 2); 00141 } 00142 LinearToMallat(destLevel, row1, row2, width); 00143 row0 = row1; row1 = row2; row2 += width; 00144 } 00145 } else { 00146 // if height is too small 00147 row0 = src; row1 = row0 + width; 00148 // first part 00149 for (UINT32 k=0; k < height; k += 2) { 00150 ForwardRow(row0, width); 00151 ForwardRow(row1, width); 00152 LinearToMallat(destLevel, row0, row1, width); 00153 row0 += width << 1; row1 += width << 1; 00154 } 00155 // bottom 00156 if (height & 1) { 00157 LinearToMallat(destLevel, row0, NULL, width); 00158 } 00159 } 00160 00161 if (quant > 0) { 00162 // subband quantization (without LL) 00163 for (int i=1; i < NSubbands; i++) { 00164 m_subband[destLevel][i].Quantize(quant); 00165 } 00166 // LL subband quantization 00167 if (destLevel == m_nLevels - 1) { 00168 m_subband[destLevel][LL].Quantize(quant); 00169 } 00170 } 00171 00172 // free source band 00173 srcBand->FreeMemory(); 00174 return NoError; 00175 } 00176 00178 // Forward transform one row 00179 // high pass filter at even positions: 1/4(-2, 4, -2) 00180 // low pass filter at odd positions: 1/8(-1, 2, 6, 2, -1) 00181 void CWaveletTransform::ForwardRow(DataT* src, UINT32 width) { 00182 if (width >= FilterWidth) { 00183 UINT32 i = 3; 00184 00185 // left border handling 00186 src[1] -= ((src[0] + src[2] + c1) >> 1); 00187 src[0] += ((src[1] + c1) >> 1); 00188 00189 // middle part 00190 for (; i < width-1; i += 2) { 00191 src[i] -= ((src[i-1] + src[i+1] + c1) >> 1); 00192 src[i-1] += ((src[i-2] + src[i] + c2) >> 2); 00193 } 00194 00195 // right border handling 00196 if (width & 1) { 00197 src[i-1] += ((src[i-2] + c1) >> 1); 00198 } else { 00199 src[i] -= src[i-1]; 00200 src[i-1] += ((src[i-2] + src[i] + c2) >> 2); 00201 } 00202 } 00203 } 00204 00206 // Copy transformed rows loRow and hiRow to subbands LL,HL,LH,HH 00207 void CWaveletTransform::LinearToMallat(int destLevel, DataT* loRow, DataT* hiRow, UINT32 width) { 00208 const UINT32 wquot = width >> 1; 00209 const bool wrem = width & 1; 00210 CSubband &ll = m_subband[destLevel][LL], &hl = m_subband[destLevel][HL]; 00211 CSubband &lh = m_subband[destLevel][LH], &hh = m_subband[destLevel][HH]; 00212 00213 if (hiRow) { 00214 for (UINT32 i=0; i < wquot; i++) { 00215 ll.WriteBuffer(*loRow++); // first access, than increment 00216 hl.WriteBuffer(*loRow++); 00217 lh.WriteBuffer(*hiRow++); // first access, than increment 00218 hh.WriteBuffer(*hiRow++); 00219 } 00220 if (wrem) { 00221 ll.WriteBuffer(*loRow); 00222 lh.WriteBuffer(*hiRow); 00223 } 00224 } else { 00225 for (UINT32 i=0; i < wquot; i++) { 00226 ll.WriteBuffer(*loRow++); // first access, than increment 00227 hl.WriteBuffer(*loRow++); 00228 } 00229 if (wrem) ll.WriteBuffer(*loRow); 00230 } 00231 } 00232 00234 // Compute fast inverse wavelet transform of all 4 subbands of given level and 00235 // stores result in LL subband of level - 1. 00236 // Inverse wavelet transform used in reading a PGF file 00237 // Inverse Transform srcLevel and combine to destBand 00238 // inverse high pass filter for even positions: 1/4(-1, 4, -1) 00239 // inverse low pass filter for odd positions: 1/8(-1, 4, 6, 4, -1) 00240 // @param srcLevel A wavelet transform pyramid level (> 0 && <= Levels()) 00241 // @param w [out] A pointer to the returned width of subband LL (in pixels) 00242 // @param h [out] A pointer to the returned height of subband LL (in pixels) 00243 // @param data [out] A pointer to the returned array of image data 00244 // @return error in case of a memory allocation problem 00245 OSError CWaveletTransform::InverseTransform(int srcLevel, UINT32* w, UINT32* h, DataT** data) { 00246 ASSERT(srcLevel > 0 && srcLevel < m_nLevels); 00247 const int destLevel = srcLevel - 1; 00248 ASSERT(m_subband[destLevel]); 00249 CSubband* destBand = &m_subband[destLevel][LL]; 00250 UINT32 width, height; 00251 00252 // allocate memory for the results of the inverse transform 00253 if (!destBand->AllocMemory()) return InsufficientMemory; 00254 DataT *dest = destBand->GetBuffer(), *origin = dest, *row0, *row1, *row2, *row3; 00255 00256 #ifdef __PGFROISUPPORT__ 00257 PGFRect destROI = destBand->GetROI(); // is valid only after AllocMemory 00258 width = destROI.Width(); 00259 height = destROI.Height(); 00260 const UINT32 destWidth = width; // destination buffer width 00261 const UINT32 destHeight = height; // destination buffer height 00262 00263 // update destination ROI 00264 if (destROI.top & 1) { 00265 destROI.top++; 00266 origin += destWidth; 00267 height--; 00268 } 00269 if (destROI.left & 1) { 00270 destROI.left++; 00271 origin++; 00272 width--; 00273 } 00274 00275 // init source buffer position 00276 const UINT32 leftD = destROI.left >> 1; 00277 const UINT32 left0 = m_subband[srcLevel][LL].GetROI().left; 00278 const UINT32 left1 = m_subband[srcLevel][HL].GetROI().left; 00279 const UINT32 topD = destROI.top >> 1; 00280 const UINT32 top0 = m_subband[srcLevel][LL].GetROI().top; 00281 const UINT32 top1 = m_subband[srcLevel][LH].GetROI().top; 00282 ASSERT(m_subband[srcLevel][LH].GetROI().left == left0); 00283 ASSERT(m_subband[srcLevel][HH].GetROI().left == left1); 00284 ASSERT(m_subband[srcLevel][HL].GetROI().top == top0); 00285 ASSERT(m_subband[srcLevel][HH].GetROI().top == top1); 00286 00287 UINT32 srcOffsetX[2] = { 0, 0 }; 00288 UINT32 srcOffsetY[2] = { 0, 0 }; 00289 00290 if (leftD >= __max(left0, left1)) { 00291 srcOffsetX[0] = leftD - left0; 00292 srcOffsetX[1] = leftD - left1; 00293 } else { 00294 if (left0 <= left1) { 00295 const UINT32 dx = (left1 - leftD) << 1; 00296 destROI.left += dx; 00297 origin += dx; 00298 width -= dx; 00299 srcOffsetX[0] = left1 - left0; 00300 } else { 00301 const UINT32 dx = (left0 - leftD) << 1; 00302 destROI.left += dx; 00303 origin += dx; 00304 width -= dx; 00305 srcOffsetX[1] = left0 - left1; 00306 } 00307 } 00308 if (topD >= __max(top0, top1)) { 00309 srcOffsetY[0] = topD - top0; 00310 srcOffsetY[1] = topD - top1; 00311 } else { 00312 if (top0 <= top1) { 00313 const UINT32 dy = (top1 - topD) << 1; 00314 destROI.top += dy; 00315 origin += dy*destWidth; 00316 height -= dy; 00317 srcOffsetY[0] = top1 - top0; 00318 } else { 00319 const UINT32 dy = (top0 - topD) << 1; 00320 destROI.top += dy; 00321 origin += dy*destWidth; 00322 height -= dy; 00323 srcOffsetY[1] = top0 - top1; 00324 } 00325 } 00326 00327 m_subband[srcLevel][LL].InitBuffPos(srcOffsetX[0], srcOffsetY[0]); 00328 m_subband[srcLevel][HL].InitBuffPos(srcOffsetX[1], srcOffsetY[0]); 00329 m_subband[srcLevel][LH].InitBuffPos(srcOffsetX[0], srcOffsetY[1]); 00330 m_subband[srcLevel][HH].InitBuffPos(srcOffsetX[1], srcOffsetY[1]); 00331 00332 #else 00333 width = destBand->GetWidth(); 00334 height = destBand->GetHeight(); 00335 PGFRect destROI(0, 0, width, height); 00336 const UINT32 destWidth = width; // destination buffer width 00337 const UINT32 destHeight = height; // destination buffer height 00338 00339 // init source buffer position 00340 for (int i=0; i < NSubbands; i++) { 00341 m_subband[srcLevel][i].InitBuffPos(); 00342 } 00343 #endif 00344 00345 if (destHeight >= FilterHeight) { 00346 // top border handling 00347 row0 = origin; row1 = row0 + destWidth; 00348 MallatToLinear(srcLevel, row0, row1, width); 00349 for (UINT32 k=0; k < width; k++) { 00350 row0[k] -= ((row1[k] + c1) >> 1); 00351 } 00352 00353 // middle part 00354 row2 = row1 + destWidth; row3 = row2 + destWidth; 00355 for (UINT32 i=destROI.top + 2; i < destROI.bottom - 1; i += 2) { 00356 MallatToLinear(srcLevel, row2, row3, width); 00357 for (UINT32 k=0; k < width; k++) { 00358 row2[k] -= ((row1[k] + row3[k] + c2) >> 2); 00359 row1[k] += ((row0[k] + row2[k] + c1) >> 1); 00360 } 00361 InverseRow(row0, width); 00362 InverseRow(row1, width); 00363 row0 = row2; row1 = row3; row2 = row1 + destWidth; row3 = row2 + destWidth; 00364 } 00365 00366 // bottom border handling 00367 if (height & 1) { 00368 MallatToLinear(srcLevel, row2, NULL, width); 00369 for (UINT32 k=0; k < width; k++) { 00370 row2[k] -= ((row1[k] + c1) >> 1); 00371 row1[k] += ((row0[k] + row2[k] + c1) >> 1); 00372 } 00373 InverseRow(row0, width); 00374 InverseRow(row1, width); 00375 InverseRow(row2, width); 00376 row0 = row1; row1 = row2; row2 += destWidth; 00377 } else { 00378 for (UINT32 k=0; k < width; k++) { 00379 row1[k] += row0[k]; 00380 } 00381 InverseRow(row0, width); 00382 InverseRow(row1, width); 00383 row0 = row1; row1 += destWidth; 00384 } 00385 } else { 00386 // height is too small 00387 row0 = origin; row1 = row0 + destWidth; 00388 // first part 00389 for (UINT32 k=0; k < height; k += 2) { 00390 MallatToLinear(srcLevel, row0, row1, width); 00391 InverseRow(row0, width); 00392 InverseRow(row1, width); 00393 row0 += destWidth << 1; row1 += destWidth << 1; 00394 } 00395 // bottom 00396 if (height & 1) { 00397 MallatToLinear(srcLevel, row0, NULL, width); 00398 InverseRow(row0, width); 00399 } 00400 } 00401 00402 // free memory of the current srcLevel 00403 for (int i=0; i < NSubbands; i++) { 00404 m_subband[srcLevel][i].FreeMemory(); 00405 } 00406 00407 // return info 00408 *w = destWidth; 00409 *h = height; 00410 *data = dest; 00411 return NoError; 00412 } 00413 00415 // Inverse Wavelet Transform of one row 00416 // inverse high pass filter for even positions: 1/4(-1, 4, -1) 00417 // inverse low pass filter for odd positions: 1/8(-1, 4, 6, 4, -1) 00418 void CWaveletTransform::InverseRow(DataT* dest, UINT32 width) { 00419 if (width >= FilterWidth) { 00420 UINT32 i = 2; 00421 00422 // left border handling 00423 dest[0] -= ((dest[1] + c1) >> 1); 00424 00425 // middle part 00426 for (; i < width - 1; i += 2) { 00427 dest[i] -= ((dest[i-1] + dest[i+1] + c2) >> 2); 00428 dest[i-1] += ((dest[i-2] + dest[i] + c1) >> 1); 00429 } 00430 00431 // right border handling 00432 if (width & 1) { 00433 dest[i] -= ((dest[i-1] + c1) >> 1); 00434 dest[i-1] += ((dest[i-2] + dest[i] + c1) >> 1); 00435 } else { 00436 dest[i-1] += dest[i-2]; 00437 } 00438 } 00439 } 00440 00442 // Copy transformed coefficients from subbands LL,HL,LH,HH to interleaved format 00443 void CWaveletTransform::MallatToLinear(int srcLevel, DataT* loRow, DataT* hiRow, UINT32 width) { 00444 const UINT32 wquot = width >> 1; 00445 const bool wrem = width & 1; 00446 CSubband &ll = m_subband[srcLevel][LL], &hl = m_subband[srcLevel][HL]; 00447 CSubband &lh = m_subband[srcLevel][LH], &hh = m_subband[srcLevel][HH]; 00448 00449 if (hiRow) { 00450 #ifdef __PGFROISUPPORT__ 00451 const bool storePos = wquot < ll.BufferWidth(); 00452 UINT32 llPos = 0, hlPos = 0, lhPos = 0, hhPos = 0; 00453 00454 if (storePos) { 00455 // save current src buffer positions 00456 llPos = ll.GetBuffPos(); 00457 hlPos = hl.GetBuffPos(); 00458 lhPos = lh.GetBuffPos(); 00459 hhPos = hh.GetBuffPos(); 00460 } 00461 #endif 00462 00463 for (UINT32 i=0; i < wquot; i++) { 00464 *loRow++ = ll.ReadBuffer();// first access, than increment 00465 *loRow++ = hl.ReadBuffer();// first access, than increment 00466 *hiRow++ = lh.ReadBuffer();// first access, than increment 00467 *hiRow++ = hh.ReadBuffer();// first access, than increment 00468 } 00469 00470 if (wrem) { 00471 *loRow++ = ll.ReadBuffer();// first access, than increment 00472 *hiRow++ = lh.ReadBuffer();// first access, than increment 00473 } 00474 00475 #ifdef __PGFROISUPPORT__ 00476 if (storePos) { 00477 // increment src buffer positions 00478 ll.IncBuffRow(llPos); 00479 hl.IncBuffRow(hlPos); 00480 lh.IncBuffRow(lhPos); 00481 hh.IncBuffRow(hhPos); 00482 } 00483 #endif 00484 00485 } else { 00486 #ifdef __PGFROISUPPORT__ 00487 const bool storePos = wquot < ll.BufferWidth(); 00488 UINT32 llPos = 0, hlPos = 0; 00489 00490 if (storePos) { 00491 // save current src buffer positions 00492 llPos = ll.GetBuffPos(); 00493 hlPos = hl.GetBuffPos(); 00494 } 00495 #endif 00496 00497 for (UINT32 i=0; i < wquot; i++) { 00498 *loRow++ = ll.ReadBuffer();// first access, than increment 00499 *loRow++ = hl.ReadBuffer();// first access, than increment 00500 } 00501 if (wrem) *loRow++ = ll.ReadBuffer(); 00502 00503 #ifdef __PGFROISUPPORT__ 00504 if (storePos) { 00505 // increment src buffer positions 00506 ll.IncBuffRow(llPos); 00507 hl.IncBuffRow(hlPos); 00508 } 00509 #endif 00510 } 00511 } 00512 00513 #ifdef __PGFROISUPPORT__ 00514 00515 00516 00517 void CWaveletTransform::SetROI(const PGFRect& rect) { 00518 // create tile indices 00519 m_ROIindices.CreateIndices(); 00520 00521 // compute tile indices 00522 m_ROIindices.ComputeIndices(m_subband[0][LL].GetWidth(), m_subband[0][LL].GetHeight(), rect); 00523 00524 // compute ROIs 00525 UINT32 w, h; 00526 PGFRect r; 00527 00528 for (int i=0; i < m_nLevels; i++) { 00529 const PGFRect& indices = m_ROIindices.GetIndices(i); 00530 00531 for (int o=0; o < NSubbands; o++) { 00532 CSubband& subband = m_subband[i][o]; 00533 00534 subband.SetNTiles(m_ROIindices.GetNofTiles(i)); // must be called before TilePosition() 00535 subband.TilePosition(indices.left, indices.top, r.left, r.top, w, h); 00536 subband.TilePosition(indices.right - 1, indices.bottom - 1, r.right, r.bottom, w, h); 00537 r.right += w; 00538 r.bottom += h; 00539 subband.SetROI(r); 00540 } 00541 } 00542 } 00543 00545 00547 void CRoiIndices::CreateIndices() { 00548 if (!m_indices) { 00549 // create tile indices 00550 m_indices = new PGFRect[m_nLevels]; 00551 } 00552 } 00553 00561 void CRoiIndices::ComputeTileIndex(UINT32 width, UINT32 height, UINT32 pos, bool horizontal, bool isMin) { 00562 ASSERT(m_indices); 00563 00564 UINT32 m; 00565 UINT32 tileIndex = 0; 00566 UINT32 tileMin = 0, tileMax = (horizontal) ? width : height; 00567 ASSERT(pos <= tileMax); 00568 00569 // compute tile index with binary search 00570 for (int i=m_nLevels - 1; i >= 0; i--) { 00571 // store values 00572 if (horizontal) { 00573 if (isMin) { 00574 m_indices[i].left = tileIndex; 00575 } else { 00576 m_indices[i].right = tileIndex + 1; 00577 } 00578 } else { 00579 if (isMin) { 00580 m_indices[i].top = tileIndex; 00581 } else { 00582 m_indices[i].bottom = tileIndex + 1; 00583 } 00584 } 00585 00586 // compute values 00587 tileIndex <<= 1; 00588 m = tileMin + (tileMax - tileMin)/2; 00589 if (pos >= m) { 00590 tileMin = m; 00591 tileIndex++; 00592 } else { 00593 tileMax = m; 00594 } 00595 } 00596 } 00597 00603 void CRoiIndices::ComputeIndices(UINT32 width, UINT32 height, const PGFRect& rect) { 00604 ComputeTileIndex(width, height, rect.left, true, true); 00605 ComputeTileIndex(width, height, rect.top, false, true); 00606 ComputeTileIndex(width, height, rect.right, true, false); 00607 ComputeTileIndex(width, height, rect.bottom, false, false); 00608 } 00609 00610 #endif // __PGFROISUPPORT__