libpgf  6.11.42
PGF - Progressive Graphics File
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
WaveletTransform.cpp
Go to the documentation of this file.
1 /*
2  * The Progressive Graphics File; http://www.libpgf.org
3  *
4  * $Date: 2006-05-18 16:03:32 +0200 (Do, 18 Mai 2006) $
5  * $Revision: 194 $
6  *
7  * This file Copyright (C) 2006 xeraina GmbH, Switzerland
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE
11  * as published by the Free Software Foundation; either version 2.1
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22  */
23 
28 
29 #include "WaveletTransform.h"
30 
31 #define c1 1 // best value 1
32 #define c2 2 // best value 2
33 
35 // Constructor: Constructs a wavelet transform pyramid of given size and levels.
36 // @param width The width of the original image (at level 0) in pixels
37 // @param height The height of the original image (at level 0) in pixels
38 // @param levels The number of levels (>= 0)
39 // @param data Input data of subband LL at level 0
40 CWaveletTransform::CWaveletTransform(UINT32 width, UINT32 height, int levels, DataT* data) :
41 #ifdef __PGFROISUPPORT__
42 m_ROIs(levels + 1),
43 #endif
44 m_nLevels(levels + 1), m_subband(0) {
45  ASSERT(m_nLevels > 0 && m_nLevels <= MaxLevel + 1);
46  InitSubbands(width, height, data);
47 }
48 
50 // Initialize size subbands on all levels
51 void CWaveletTransform::InitSubbands(UINT32 width, UINT32 height, DataT* data) {
52  if (m_subband) Destroy();
53 
54  // create subbands
56 
57  // init subbands
58  UINT32 loWidth = width;
59  UINT32 hiWidth = width;
60  UINT32 loHeight = height;
61  UINT32 hiHeight = height;
62 
63  for (int level = 0; level < m_nLevels; level++) {
64  m_subband[level][LL].Initialize(loWidth, loHeight, level, LL); // LL
65  m_subband[level][HL].Initialize(hiWidth, loHeight, level, HL); // HL
66  m_subband[level][LH].Initialize(loWidth, hiHeight, level, LH); // LH
67  m_subband[level][HH].Initialize(hiWidth, hiHeight, level, HH); // HH
68  hiWidth = loWidth >> 1; hiHeight = loHeight >> 1;
69  loWidth = (loWidth + 1) >> 1; loHeight = (loHeight + 1) >> 1;
70  }
71  if (data) {
72  m_subband[0][LL].SetBuffer(data);
73  }
74 }
75 
77 // Compute fast forward wavelet transform of LL subband at given level and
78 // stores result on all 4 subbands of level + 1.
79 // Wavelet transform used in writing a PGF file
80 // Forward Transform of srcBand and split and store it into subbands on destLevel
81 // high pass filter at even positions: 1/4(-2, 4, -2)
82 // low pass filter at odd positions: 1/8(-1, 2, 6, 2, -1)
83 // @param level A wavelet transform pyramid level (>= 0 && < Levels())
84 // @param quant A quantization value (linear scalar quantization)
85 // @return error in case of a memory allocation problem
86 OSError CWaveletTransform::ForwardTransform(int level, int quant) {
87  ASSERT(level >= 0 && level < m_nLevels - 1);
88  const int destLevel = level + 1;
89  ASSERT(m_subband[destLevel]);
90  CSubband* srcBand = &m_subband[level][LL]; ASSERT(srcBand);
91  const UINT32 width = srcBand->GetWidth();
92  const UINT32 height = srcBand->GetHeight();
93  DataT* src = srcBand->GetBuffer(); ASSERT(src);
94  UINT32 row0, row1, row2, row3;
95  UINT32 i, k;
96 
97  // Allocate memory for next transform level
98  for (i=0; i < NSubbands; i++) {
99  if (!m_subband[destLevel][i].AllocMemory()) return InsufficientMemory;
100  }
101 
102  if (height >= FilterHeight) {
103  // transform LL subband
104  // top border handling
105  row0 = 0; row1 = width; row2 = row1 + width;
106  ForwardRow(&src[row0], width);
107  ForwardRow(&src[row1], width);
108  ForwardRow(&src[row2], width);
109  for (k=0; k < width; k++) {
110  src[row1] -= ((src[row0] + src[row2] + c1) >> 1);
111  src[row0] += ((src[row1] + c1) >> 1);
112  row0++; row1++; row2++;
113  }
114  LinearToMallat(destLevel, &src[0], &src[row0], width);
115 
116  // middle part
117  row3 = row2 + width;
118  for (i=3; i < height-1; i += 2) {
119  ForwardRow(&src[row2], width);
120  ForwardRow(&src[row3], width);
121  for (k=0; k < width; k++) {
122  src[row2] -= ((src[row1] + src[row3] + c1) >> 1);
123  src[row1] += ((src[row0] + src[row2] + c2) >> 2);
124  row0++; row1++; row2++; row3++;
125  }
126  LinearToMallat(destLevel, &src[row0], &src[row1], width);
127  row0 = row1; row1 = row2; row2 = row3; row3 += width;
128  }
129 
130  // bottom border handling
131  if (height & 1) {
132  for (k=0; k < width; k++) {
133  src[row1] += ((src[row0] + c1) >> 1);
134  row0++; row1++;
135  }
136  LinearToMallat(destLevel, &src[row0], NULL, width);
137  } else {
138  ForwardRow(&src[row2], width);
139  for (k=0; k < width; k++) {
140  src[row2] -= src[row1];
141  src[row1] += ((src[row0] + src[row2] + c2) >> 2);
142  row0++; row1++; row2++;
143  }
144  LinearToMallat(destLevel, &src[row0], &src[row1], width);
145  }
146  } else {
147  // if height to small
148  row0 = 0; row1 = width;
149  // first part
150  for (k=0; k < height; k += 2) {
151  ForwardRow(&src[row0], width);
152  ForwardRow(&src[row1], width);
153  LinearToMallat(destLevel, &src[row0], &src[row1], width);
154  row0 += width << 1; row1 += width << 1;
155  }
156  // bottom
157  if (height & 1) {
158  LinearToMallat(destLevel, &src[row0], NULL, width);
159  }
160  }
161 
162  if (quant > 0) {
163  // subband quantization (without LL)
164  for (i=1; i < NSubbands; i++) {
165  m_subband[destLevel][i].Quantize(quant);
166  }
167  // LL subband quantization
168  if (destLevel == m_nLevels - 1) {
169  m_subband[destLevel][LL].Quantize(quant);
170  }
171  }
172 
173  // free source band
174  srcBand->FreeMemory();
175  return NoError;
176 }
177 
179 // Forward transform one row
180 // high pass filter at even positions: 1/4(-2, 4, -2)
181 // low pass filter at odd positions: 1/8(-1, 2, 6, 2, -1)
182 void CWaveletTransform::ForwardRow(DataT* src, UINT32 width) {
183  if (width >= FilterWidth) {
184  UINT32 i = 3;
185 
186  // left border handling
187  src[1] -= ((src[0] + src[2] + c1) >> 1);
188  src[0] += ((src[1] + c1) >> 1);
189 
190  // middle part
191  for (; i < width-1; i += 2) {
192  src[i] -= ((src[i-1] + src[i+1] + c1) >> 1);
193  src[i-1] += ((src[i-2] + src[i] + c2) >> 2);
194  }
195 
196  // right border handling
197  if (width & 1) {
198  src[i-1] += ((src[i-2] + c1) >> 1);
199  } else {
200  src[i] -= src[i-1];
201  src[i-1] += ((src[i-2] + src[i] + c2) >> 2);
202  }
203  }
204 }
205 
207 // Copy transformed rows loRow and hiRow to subbands LL,HL,LH,HH
208 void CWaveletTransform::LinearToMallat(int destLevel, DataT* loRow, DataT* hiRow, UINT32 width) {
209  const UINT32 wquot = width >> 1;
210  const bool wrem = width & 1;
211  CSubband &ll = m_subband[destLevel][LL], &hl = m_subband[destLevel][HL];
212  CSubband &lh = m_subband[destLevel][LH], &hh = m_subband[destLevel][HH];
213  UINT32 i;
214 
215  if (hiRow) {
216  for (i=0; i < wquot; i++) {
217  ll.WriteBuffer(*loRow++); // first access, than increment
218  hl.WriteBuffer(*loRow++);
219  lh.WriteBuffer(*hiRow++); // first access, than increment
220  hh.WriteBuffer(*hiRow++);
221  }
222  if (wrem) {
223  ll.WriteBuffer(*loRow);
224  lh.WriteBuffer(*hiRow);
225  }
226  } else {
227  for (i=0; i < wquot; i++) {
228  ll.WriteBuffer(*loRow++); // first access, than increment
229  hl.WriteBuffer(*loRow++);
230  }
231  if (wrem) ll.WriteBuffer(*loRow);
232  }
233 }
234 
236 // Compute fast inverse wavelet transform of all 4 subbands of given level and
237 // stores result in LL subband of level - 1.
238 // Inverse wavelet transform used in reading a PGF file
239 // Inverse Transform srcLevel and combine to destBand
240 // inverse high pass filter for even positions: 1/4(-1, 4, -1)
241 // inverse low pass filter for odd positions: 1/8(-1, 4, 6, 4, -1)
242 // @param srcLevel A wavelet transform pyramid level (> 0 && <= Levels())
243 // @param w [out] A pointer to the returned width of subband LL (in pixels)
244 // @param h [out] A pointer to the returned height of subband LL (in pixels)
245 // @param data [out] A pointer to the returned array of image data
246 // @return error in case of a memory allocation problem
247 OSError CWaveletTransform::InverseTransform(int srcLevel, UINT32* w, UINT32* h, DataT** data) {
248  ASSERT(srcLevel > 0 && srcLevel < m_nLevels);
249  const int destLevel = srcLevel - 1;
250  ASSERT(m_subband[destLevel]);
251  CSubband* destBand = &m_subband[destLevel][LL];
252  const UINT32 width = destBand->GetWidth();
253  const UINT32 height = destBand->GetHeight();
254  UINT32 row0, row1, row2, row3, i, k, origin = 0;
255 
256  // allocate memory for the results of the inverse transform
257  if (!destBand->AllocMemory()) return InsufficientMemory;
258  DataT* dest = destBand->GetBuffer();
259 
260 #ifdef __PGFROISUPPORT__
261  const UINT32 srcLeft = (m_ROIs.ROIisSupported()) ? m_ROIs.Left(srcLevel) : 0;
262  const UINT32 srcTop = (m_ROIs.ROIisSupported()) ? m_ROIs.Top(srcLevel) : 0;
263  UINT32 destWidth = destBand->BufferWidth(); // destination buffer width; is valid only after AllocMemory
264  PGFRect destROI = (m_ROIs.ROIisSupported()) ? m_ROIs.GetROI(destLevel) : PGFRect(0, 0, width, height);
265  destROI.right = destROI.left + destWidth;
266  destROI.bottom = __min(destROI.bottom, height);
267  UINT32 destHeight = destROI.Height(); // destination buffer height
268 
269  // update destination ROI
270  if (destROI.left & 1) {
271  destROI.left++;
272  origin++;
273  destWidth--;
274  }
275  if (destROI.top & 1) {
276  destROI.top++;
277  origin += destWidth;
278  destHeight--;
279  }
280 
281  // init source buffer position
282  UINT32 left = destROI.left >> 1;
283  UINT32 top = destROI.top >> 1;
284 
285  left -= srcLeft;
286  top -= srcTop;
287  for (i=0; i < NSubbands; i++) {
288  m_subband[srcLevel][i].InitBuffPos(left, top);
289  }
290 #else
291  PGFRect destROI(0, 0, width, height);
292  const UINT32 destWidth = width; // destination buffer width
293  const UINT32 destHeight = height; // destination buffer height
294 
295  // init source buffer position
296  for (i=0; i < NSubbands; i++) {
297  m_subband[srcLevel][i].InitBuffPos();
298  }
299 #endif
300 
301  if (destHeight >= FilterHeight) {
302  // top border handling
303  row0 = origin; row1 = row0 + destWidth;
304  MallatToLinear(srcLevel, &dest[row0], &dest[row1], destWidth);
305  for (k=0; k < destWidth; k++) {
306  ASSERT(row0 < destBand->m_size);
307  ASSERT(row1 < destBand->m_size);
308  dest[row0] -= ((dest[row1] + c1) >> 1);
309  row0++; row1++;
310  }
311 
312  // middle part
313  row2 = row1; row1 = row0; row0 = row0 - destWidth; row3 = row2 + destWidth;
314  for (i=destROI.top + 2; i < destROI.bottom - 1; i += 2) {
315  MallatToLinear(srcLevel, &dest[row2], &dest[row3], destWidth);
316  for (k=0; k < destWidth; k++) {
317  ASSERT(row0 < destBand->m_size);
318  ASSERT(row1 < destBand->m_size);
319  ASSERT(row2 < destBand->m_size);
320  ASSERT(row3 < destBand->m_size);
321  dest[row2] -= ((dest[row1] + dest[row3] + c2) >> 2);
322  dest[row1] += ((dest[row0] + dest[row2] + c1) >> 1);
323  row0++; row1++; row2++; row3++;
324  }
325  InverseRow(&dest[row0 - destWidth], destWidth);
326  InverseRow(&dest[row1 - destWidth], destWidth);
327  row0 = row1; row1 = row2; row2 = row3; row3 += destWidth;
328  }
329 
330  // bottom border handling
331  if (destHeight & 1) {
332  MallatToLinear(srcLevel, &dest[row2], 0, destWidth);
333  for (k=0; k < destWidth; k++) {
334  ASSERT(row0 < destBand->m_size);
335  ASSERT(row1 < destBand->m_size);
336  ASSERT(row2 < destBand->m_size);
337  dest[row2] -= ((dest[row1] + c1) >> 1);
338  dest[row1] += ((dest[row0] + dest[row2] + c1) >> 1);
339  row0++; row1++; row2++;
340  }
341  InverseRow(&dest[row0 - destWidth], destWidth);
342  InverseRow(&dest[row1 - destWidth], destWidth);
343  InverseRow(&dest[row2 - destWidth], destWidth);
344  } else {
345  for (k=0; k < destWidth; k++) {
346  ASSERT(row0 < destBand->m_size);
347  ASSERT(row1 < destBand->m_size);
348  dest[row1] += dest[row0];
349  row0++; row1++;
350  }
351  InverseRow(&dest[row0 - destWidth], destWidth);
352  InverseRow(&dest[row1 - destWidth], destWidth);
353  }
354  } else {
355  // destHeight to small
356  row0 = origin; row1 = row0 + destWidth;
357  // first part
358  for (k=0; k < destHeight; k += 2) {
359  MallatToLinear(srcLevel, &dest[row0], &dest[row1], destWidth);
360  InverseRow(&dest[row0], destWidth);
361  InverseRow(&dest[row1], destWidth);
362  row0 += destWidth << 1; row1 += destWidth << 1;
363  }
364  // bottom
365  if (destHeight & 1) {
366  MallatToLinear(srcLevel, &dest[row0], 0, destWidth);
367  InverseRow(&dest[row0], destWidth);
368  }
369  }
370 
371  // free memory of the current srcLevel
372  for (i=0; i < NSubbands; i++) {
373  m_subband[srcLevel][i].FreeMemory();
374  }
375 
376  // return info
377  *w = destWidth;
378  *h = destHeight;
379  *data = dest;
380  return NoError;
381 }
382 
384 // Inverse Wavelet Transform of one row
385 // inverse high pass filter for even positions: 1/4(-1, 4, -1)
386 // inverse low pass filter for odd positions: 1/8(-1, 4, 6, 4, -1)
387 void CWaveletTransform::InverseRow(DataT* dest, UINT32 width) {
388  if (width >= FilterWidth) {
389  UINT32 i = 2;
390 
391  // left border handling
392  dest[0] -= ((dest[1] + c1) >> 1);
393 
394  // middle part
395  for (; i < width - 1; i += 2) {
396  dest[i] -= ((dest[i-1] + dest[i+1] + c2) >> 2);
397  dest[i-1] += ((dest[i-2] + dest[i] + c1) >> 1);
398  }
399 
400  // right border handling
401  if (width & 1) {
402  dest[i] -= ((dest[i-1] + c1) >> 1);
403  dest[i-1] += ((dest[i-2] + dest[i] + c1) >> 1);
404  } else {
405  dest[i-1] += dest[i-2];
406  }
407  }
408 }
409 
411 // Copy transformed coefficients from subbands LL,HL,LH,HH to interleaved format
412 void CWaveletTransform::MallatToLinear(int srcLevel, DataT* loRow, DataT* hiRow, UINT32 width) {
413  const UINT32 wquot = width >> 1;
414  const bool wrem = width & 1;
415  CSubband &ll = m_subband[srcLevel][LL], &hl = m_subband[srcLevel][HL];
416  CSubband &lh = m_subband[srcLevel][LH], &hh = m_subband[srcLevel][HH];
417  UINT32 i;
418 
419  if (hiRow) {
420  #ifdef __PGFROISUPPORT__
421  const bool storePos = wquot < ll.BufferWidth();
422  UINT32 llPos = 0, hlPos = 0, lhPos = 0, hhPos = 0;
423 
424  if (storePos) {
425  // save current src buffer positions
426  llPos = ll.GetBuffPos();
427  hlPos = hl.GetBuffPos();
428  lhPos = lh.GetBuffPos();
429  hhPos = hh.GetBuffPos();
430  }
431  #endif
432 
433  for (i=0; i < wquot; i++) {
434  *loRow++ = ll.ReadBuffer();// first access, than increment
435  *loRow++ = hl.ReadBuffer();// first access, than increment
436  *hiRow++ = lh.ReadBuffer();// first access, than increment
437  *hiRow++ = hh.ReadBuffer();// first access, than increment
438  }
439 
440  if (wrem) {
441  *loRow++ = ll.ReadBuffer();// first access, than increment
442  *hiRow++ = lh.ReadBuffer();// first access, than increment
443  }
444 
445  #ifdef __PGFROISUPPORT__
446  if (storePos) {
447  // increment src buffer positions
448  ll.IncBuffRow(llPos);
449  hl.IncBuffRow(hlPos);
450  lh.IncBuffRow(lhPos);
451  hh.IncBuffRow(hhPos);
452  }
453  #endif
454 
455  } else {
456  #ifdef __PGFROISUPPORT__
457  const bool storePos = wquot < ll.BufferWidth();
458  UINT32 llPos = 0, hlPos = 0;
459 
460  if (storePos) {
461  // save current src buffer positions
462  llPos = ll.GetBuffPos();
463  hlPos = hl.GetBuffPos();
464  }
465  #endif
466 
467  for (i=0; i < wquot; i++) {
468  *loRow++ = ll.ReadBuffer();// first access, than increment
469  *loRow++ = hl.ReadBuffer();// first access, than increment
470  }
471  if (wrem) *loRow++ = ll.ReadBuffer();
472 
473  #ifdef __PGFROISUPPORT__
474  if (storePos) {
475  // increment src buffer positions
476  ll.IncBuffRow(llPos);
477  hl.IncBuffRow(hlPos);
478  }
479  #endif
480  }
481 }
482 
483 #ifdef __PGFROISUPPORT__
484 
485 
486 
487 void CWaveletTransform::SetROI(const PGFRect& rect) {
488  // create and init ROIs
489  SetROI();
490 
491  // create tile indices
492  m_ROIs.CreateIndices();
493 
494  // compute tile indices
495  m_ROIs.ComputeIndices(m_subband[0][LL].GetWidth(), m_subband[0][LL].GetHeight(), rect);
496 
497  // compute ROIs
498  UINT32 w, h;
499  PGFRect r;
500 
501  for (int i=0; i < m_nLevels; i++) {
502  const PGFRect& indices = m_ROIs.GetIndices(i);
503  m_subband[i][LL].TilePosition(indices.left, indices.top, r.left, r.top, w, h);
504  //if (r.left & 1) r.left++; // ensures ROI starts at an even position
505  //if (r.top & 1) r.top++; // ensures ROI starts at an even position
506  m_subband[i][LL].TilePosition(indices.right - 1, indices.bottom - 1, r.right, r.bottom, w, h);
507  r.right += w;
508  r.bottom += h;
509  m_ROIs.SetROI(i, r);
510  }
511 }
512 
515 void CWaveletTransform::SetROI() {
516  // create and init ROIs
517  m_ROIs.CreateROIs();
518 
519  // set ROI references
520  for (int i=0; i < m_nLevels; i++) {
521  m_ROIs.SetROI(i, PGFRect(0, 0, m_subband[i][LL].GetWidth(), m_subband[i][LL].GetHeight()));
522  m_subband[i][LL].SetROI(&m_ROIs); // LL
523  m_subband[i][HL].SetROI(&m_ROIs); // HL
524  m_subband[i][LH].SetROI(&m_ROIs); // LH
525  m_subband[i][HH].SetROI(&m_ROIs); // HH
526  }
527 }
528 
530 
532 void CROIs::CreateROIs() {
533  if (!m_ROIs) {
534  // create ROIs
535  m_ROIs = new PGFRect[m_nLevels];
536  }
537 }
538 
540 void CROIs::CreateIndices() {
541  if (!m_indices) {
542  // create tile indices
543  m_indices = new PGFRect[m_nLevels];
544  }
545 }
546 
554 void CROIs::ComputeTileIndex(UINT32 width, UINT32 height, UINT32 pos, bool horizontal, bool isMin) {
555  ASSERT(m_indices);
556 
557  UINT32 m;
558  UINT32 tileIndex = 0;
559  UINT32 tileMin = 0, tileMax = (horizontal) ? width : height;
560  ASSERT(pos <= tileMax);
561 
562  // compute tile index with binary search
563  for (int i=m_nLevels - 1; i >= 0; i--) {
564  // store values
565  if (horizontal) {
566  if (isMin) {
567  m_indices[i].left = tileIndex;
568  } else {
569  m_indices[i].right = tileIndex + 1;
570  }
571  } else {
572  if (isMin) {
573  m_indices[i].top = tileIndex;
574  } else {
575  m_indices[i].bottom = tileIndex + 1;
576  }
577  }
578 
579  // compute values
580  tileIndex <<= 1;
581  m = (tileMin + tileMax)/2;
582  if (pos >= m) {
583  tileMin = m;
584  tileIndex++;
585  } else {
586  tileMax = m;
587  }
588  }
589 }
590 
596 void CROIs::ComputeIndices(UINT32 width, UINT32 height, const PGFRect& rect) {
597  ComputeTileIndex(width, height, rect.left, true, true);
598  ComputeTileIndex(width, height, rect.top, false, true);
599  ComputeTileIndex(width, height, rect.right, true, false);
600  ComputeTileIndex(width, height, rect.bottom, false, false);
601 }
602 
603 #endif // __PGFROISUPPORT__