---

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. {}

ts_trans_int::~ts_trans_int ( ) [inline]

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

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. { split( vec, n ); predict( vec, n, forward ); update( vec, n, forward ); predict2( vec, n, forward ); } // 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. { predict2( vec, n, inverse ); update( vec, n, inverse ); predict( vec, n, inverse ); merge( vec, n ); } // 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(). { int y = 2 * y1 - y2; return y; }

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(). { int y = 2 * y2 - y1; return y; }

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(). { int half = N >> 1; int predictVal; for (int i = 0; i < half; i++) { int j = i + half; int y_n_plus1; int y_n_minus1; if (N == 2) { y_n_minus1 = vec[0]; y_n_plus1 = vec[0]; } else if (i == 0) { y_n_minus1 = new_n_minus1( vec[0], vec[1] ); y_n_plus1 = vec[1]; } else if (i < half-1) { y_n_minus1 = vec[i-1]; y_n_plus1 = vec[i+1]; } else { // i == half-1 y_n_minus1 = vec[i-1]; y_n_plus1 = new_n_plus1( vec[i-1], vec[i] ); } predictVal = (int)( (((float)y_n_minus1 - (float)y_n_plus1)/4.0) + 0.5 ); if (direction == forward) { vec[j] = vec[j] + predictVal; } else if (direction == inverse) { vec[j] = vec[j] - predictVal; } else { printf("haar_int::predict: bad direction value\n"); } } } // predict2

---

The documentation for this class was generated from the following file:

• ts_trans_int.h

---