Main Page   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::

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 Sat Aug 10 13:23:39 2002 for Wavelet Packet Transform and Lossless Compression by 1.2.8.1 written by Dimitri van Heesch, © 1997-2001