Main Page   Namespace List   Class Hierarchy   Compound List   File List   Compound Members   File Members  

ts_trans_int Class Reference

An integer version of the TS transform (an extended S, or Haar transform). More...

#include <ts_trans_int.h>

Inheritance diagram for ts_trans_int::

haar_int liftbase List of all members.

Public Methods

 ts_trans_int ()
 the constructor does nothing. More...

 ~ts_trans_int ()
 the destructor does nothing. More...

 ts_trans_int (const ts_trans_int &rhs)
 declare, but do not define the copy constructor. More...

void forwardStep (int *&vec, const int n)
 One TS transform forward step. More...

void inverseStep (int *&vec, const int n)
 One TS transform inverse step. More...


Protected Methods

void predict2 (int *&vec, int N, transDirection direction)
 The predict interpolation step. More...


Private Methods

int new_n_plus1 (int y1, int y2)
 Calculate the element s1,i+1. More...

int new_n_minus1 (int y1, int y2)
 In the function new_n_plus1 a point beyond the end of the low pass filter array is calculated. More...


Detailed Description

An integer version of the TS transform (an extended S, or Haar transform).

The TS transform is an extension of integer version of the Haar trasform (which is sometimes referred the S-transform in the image processing literature. The TS transform is an integer version of the so called Cohen-Daubechies-Feaveau (3,1) transform. Here the (3,1) refer to 3 vanishing moments for the wavelet function and 1 vanishing moment for the scaling function.

The equations for the lifting scheme version of the forward TS transform are shown below. As with all lifting scheme algorithms, the inverse transform exchanges addition and subtraction operators.

The TS transform and the S transform are the same in the first two steps (the first predict and update steps). An average interpolation step is added to the S (Haar) transform.

  d(1)1,i = s0,2i+1 - s0,2i
  
  s1,i = s0,2i + floor( d(1)1,i/2 )

  d1,i = d(1)1,i + floor((s1,i-1 - s1,i+1)/4.0 + 0.5)
  

This notation and the algorithm implemented here is taken directly from Wavelet Transformst that Map Integers to Integers by A.R. Calderbank, Ingrid Daugbechies, Wim Sweldens, and Boon-Lock Yeo, 1996

The mathematical structure is reflected in the class structure. Here the ts_trans_int class extends the haar_int class. The haar_int class provide the predict() and update functions. An additional predict2() function is added that implements interpolation step.

Since an extra step has been added, the forwardStep and inverseStep functions in the base class (liftbase) are over-ridden by ts_trans_int.

A brief note on vanishing moments

This algorithm is commonly known as the CDF (3,1) wavelet algorithm. As noted above, these numbers refer to the vanishing moments. I have never found a definition of "vanishing moment" that made intuitive sense to me, at least when applied to wavelet basis functions.

As I understand the definition, a vanishing moment is a region over which the integral is zero. So the area of sin(x) in the region 0..2Pi has an integral of zero, since the region between 0..Pi results in a positive integral and the area between Pi..2Pi results in the same integeral value, but with a negative sign. The sum of these two regions is zero. If a wavelet were constructed from the sine function, such that

  x = {0..2Pi}      : y = sin(x)
  x = anything else : y = 0
  

This would be a wavelet with "compact support" (it is a defined for a finite region, 0..2Pi) and one vanishing moment.

Definition at line 113 of file ts_trans_int.h.


Constructor & Destructor Documentation

ts_trans_int::ts_trans_int ( ) [inline]
 

the constructor does nothing.

Definition at line 117 of file ts_trans_int.h.

00117 {}

ts_trans_int::~ts_trans_int ( ) [inline]
 

the destructor does nothing.

Definition at line 119 of file ts_trans_int.h.

00119 {}

ts_trans_int::ts_trans_int ( const ts_trans_int & rhs )
 

declare, but do not define the copy constructor.


Member Function Documentation

void ts_trans_int::forwardStep ( int *& vec,
const int n ) [inline]
 

One TS transform forward step.

This extends the S transform (Haar integer transform) with the predict2 step.

Definition at line 267 of file ts_trans_int.h.

00268   {
00269     split( vec, n );
00270     predict( vec, n, forward );
00271     update( vec, n, forward );
00272     predict2( vec, n, forward );
00273   } // forwardStep

void ts_trans_int::inverseStep ( int *& vec,
const int n ) [inline]
 

One TS transform inverse step.

This extends the S transform (Haar integer transform) with the predict2 step.

Definition at line 279 of file ts_trans_int.h.

00280   {
00281     predict2( vec, n, inverse );
00282     update( vec, n, inverse );
00283     predict( vec, n, inverse );
00284     merge( vec, n );
00285   } // inverseStep

int ts_trans_int::new_n_minus1 ( int y1,
int y2 ) [inline, private]
 

In the function new_n_plus1 a point beyond the end of the low pass filter array is calculated.

Here a point beyond the beginning of the array is calculated.

    x1 = 0
    x2 = 1
    y1 = s[0]
    y2 = s[1]
    x = -1
    

When these values are plugged into the two point equation we get

    y = 2 * y1 - y2
    

Definition at line 204 of file ts_trans_int.h.

Referenced by predict2().

00205   {
00206     int y = 2 * y1 - y2;
00207     return y;
00208   }

int ts_trans_int::new_n_plus1 ( int y1,
int y2 ) [inline, private]
 

Calculate the element s1,i+1.

The low pass half of the array is in the array index range {0..half-1}. In the equation below, when i = half-1 a non-existent element at i+1 is needed. This function calculates this element from s[half-2] and s[half-1].

    d1,i = d(1)1,i + floor((s1,i-1 - s1,i+1)/4.0 + 0.5)
    

Here the non-existent element s[half] is assumed to lie on the line from s[half-2] and s[half-1]. We pretend that s[half-2] has the x-coordinate of 0 and s[half-1] has an x-coordinate of 1. We then need to calculate the y value at the x-coordinate 2.

The "two-point equation" for a line is used for this calculation, where we are trying to find the value of y, given

     .          y2 - y1
     (y - y1) = -------- (x - x1)
     .          x2 - x1
     

Solving for y

     .    y2 - y1
     y = -------- (x - x1) + y1
     .    x2 - x1
     

where

    x1 = 0
    x2 = 1
    y1 = s[half-2]
    y2 = s[half-1]
    x = 2
    

Substituting in these values we get

     y = 2*y2 - y1
     

Definition at line 177 of file ts_trans_int.h.

Referenced by predict2().

00178   {
00179     int y = 2 * y2 - y1;
00180     return y;
00181   }

void ts_trans_int::predict2 ( int *& vec,
int N,
transDirection direction ) [inline, protected]
 

The predict interpolation step.

Note that special cases exist at the start and end of the array. A special case also exists for N = 2, where the calculation is the same as the Haar wavelet (e.g., no interpolation factor is added in).

Definition at line 221 of file ts_trans_int.h.

Referenced by forwardStep(), and inverseStep().

00222   {
00223     int half = N >> 1;
00224     int predictVal;
00225 
00226     for (int i = 0; i < half; i++) {
00227       int j = i + half;
00228       int y_n_plus1;
00229       int y_n_minus1;
00230 
00231       if (N == 2) {
00232         y_n_minus1 = vec[0];
00233         y_n_plus1 = vec[0];
00234       }
00235       else if (i == 0) {
00236         y_n_minus1 = new_n_minus1( vec[0], vec[1] );
00237         y_n_plus1 = vec[1];
00238       }
00239       else if (i < half-1) {
00240         y_n_minus1 = vec[i-1];
00241         y_n_plus1  = vec[i+1];
00242       }
00243       else { // i == half-1
00244         y_n_minus1 = vec[i-1];
00245         y_n_plus1  = new_n_plus1( vec[i-1], vec[i] );
00246       }
00247 
00248       predictVal = (int)( (((float)y_n_minus1 - (float)y_n_plus1)/4.0) + 0.5 );
00249 
00250       if (direction == forward) {
00251         vec[j] = vec[j] + predictVal;
00252       }
00253       else if (direction == inverse) {
00254         vec[j] = vec[j] - predictVal;
00255       }
00256       else {
00257         printf("haar_int::predict: bad direction value\n");
00258       }
00259     }      
00260   } // predict2


The documentation for this class was generated from the following file:
Generated at Tue May 27 21:56:17 2003 for Wavelet compression, determinism and time series forecasting by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001