#include <ts_trans_int.h>
Inheritance diagram for ts_trans_int::
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 s_{1,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... 
The TS transform is an extension of integer version of the Haar trasform (which is sometimes referred the Stransform in the image processing literature. The TS transform is an integer version of the so called CohenDaubechiesFeaveau (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} = s_{0,2i+1}  s_{0,2i} s_{1,i} = s_{0,2i} + floor( d(1)_{1,i}/2 ) d_{1,i} = d(1)_{1,i} + floor((s_{1,i1}  s_{1,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 BoonLock 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 overridden 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.

the constructor does nothing.
Definition at line 117 of file ts_trans_int.h. 00117 {} 

the destructor does nothing.
Definition at line 119 of file ts_trans_int.h. 00119 {} 

declare, but do not define the copy constructor.


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. 

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. 

In the function Here a point beyond the beginning of the array is calculated.
x_{1} = 0 x_{2} = 1 y_{1} = s[0] y_{2} = s[1] x = 1 When these values are plugged into the two point equation we get
y = 2 * y_{1}  y_{2} Definition at line 204 of file ts_trans_int.h. Referenced by predict2().
00205 { 00206 int y = 2 * y1  y2; 00207 return y; 00208 } 

Calculate the element s_{1,i+1}.
The low pass half of the array is in the array index range {0..half1}. In the equation below, when
d_{1,i} = d(1)_{1,i} + floor((s_{1,i1}  s_{1,i+1})/4.0 + 0.5) Here the nonexistent element s[half] is assumed to lie on the line from s[half2] and s[half1]. We pretend that s[half2] has the xcoordinate of 0 and s[half1] has an xcoordinate of 1. We then need to calculate the y value at the xcoordinate 2. The "twopoint equation" for a line is used for this calculation, where we are trying to find the value of y, given
. y_{2}  y_{1} (y  y_{1}) =  (x  x_{1}) . x_{2}  x_{1} Solving for y
. y_{2}  y_{1} y =  (x  x_{1}) + y_{1} . x_{2}  x_{1} where
x_{1} = 0 x_{2} = 1 y_{1} = s[half2] y_{2} = s[half1] x = 2 Substituting in these values we get
y = 2*y_{2}  y_{1} Definition at line 177 of file ts_trans_int.h. Referenced by predict2().
00178 { 00179 int y = 2 * y2  y1; 00180 return y; 00181 } 

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 < half1) { 00240 y_n_minus1 = vec[i1]; 00241 y_n_plus1 = vec[i+1]; 00242 } 00243 else { // i == half1 00244 y_n_minus1 = vec[i1]; 00245 y_n_plus1 = new_n_plus1( vec[i1], 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 