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

line_int Class Template Reference

An integer version of the linear interpolation wavelet. More...

#include <line_int.h>

Inheritance diagram for line_int::

liftbase List of all members.

Public Methods

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

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

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


Protected Methods

void predict (T &vec, int N, transDirection direction)
 Predict phase of Lifting Scheme linear interpolation wavelet. More...

void update (T &vec, int N, transDirection direction)
 Update step of the linear interpolation wavelet. More...


Private Methods

int new_n_plus1 (int y1, int y2)
 Given y1 at x-coordinate 0 and y2 at x-coordinate 1, calculate y, at x-coordinate 2. More...

int new_n_minus1 (int y1, int y2)
 Given a point y1 at x-coordinate 0 and y2 at x-coordinate 1, calculate y at x-coordinate -1. More...


Detailed Description

template<class T> class line_int

An integer version of the linear interpolation wavelet.

The linear interpolation wavelet uses a predict phase that "predicts" that an odd element in the data set will line on a line between its two even neighbors.

This is an integer version of the linear interpolation wavelet. It is interesting to note that unlike the S transform (the integer version of the Haar wavelet) or the TS transform (an integer version of the CDF(3,1) transform) this algorithm does not preserve the mean. That is, when the transform is calculated, the first element of the result array will not be the mean.

Definition at line 60 of file line_int.h.


Constructor & Destructor Documentation

template<class T>
line_int<T>::line_int<T> ( ) [inline]
 

the constructor does nothing.

Definition at line 64 of file line_int.h.

00064 {}

template<class T>
line_int<T>::~line_int<T> ( ) [inline]
 

the destructor does nothing.

Definition at line 66 of file line_int.h.

00066 {}

template<class T>
line_int<T>::line_int<T> ( const line_int<T> & rhs )
 

declare, but do not define the copy constructor.


Member Function Documentation

template<class T>
int line_int<T>::new_n_minus1 ( int y1,
int y2 ) [inline, private]
 

Given a point y1 at x-coordinate 0 and y2 at x-coordinate 1, calculate y at x-coordinate -1.

Definition at line 85 of file line_int.h.

Referenced by update().

00086   {
00087     int y = 2 * y1 - y2;
00088     return y;
00089   }

template<class T>
int line_int<T>::new_n_plus1 ( int y1,
int y2 ) [inline, private]
 

Given y1 at x-coordinate 0 and y2 at x-coordinate 1, calculate y, at x-coordinate 2.

Definition at line 74 of file line_int.h.

Referenced by predict().

00075    {
00076      int y = 2 * y2 - y1;
00077      return y;
00078    }

template<class T>
void line_int<T>::predict ( T & vec,
int N,
transDirection direction ) [inline, protected, virtual]
 

Predict phase of Lifting Scheme linear interpolation wavelet.

The predict step attempts to "predict" the value of an odd element from the even elements. The difference between the prediction and the actual element is stored as a wavelet coefficient.

The "predict" step takes place after the split step. The split step will move the odd elements (bj) to the second half of the array, leaving the even elements (ai) in the first half

    a0, a1, a1, a3, b0, b1, b2, b2, 
    

The predict step of the line wavelet "predicts" that the odd element will be on a line between two even elements.

    bj+1,i = bj,i - (aj,i + aj,i+1)/2
    

Note that when we get to the end of the data series the odd element is the last element in the data series (remember, wavelet algorithms work on data series with 2n elements). Here we "predict" that the odd element will be on a line that runs through the last two even elements. This can be calculated by assuming that the last two even elements are located at x-axis coordinates 0 and 1, respectively. The odd element will be at 2. The new_n_plus1() function is called to do this simple calculation.

Note that in the case where (N == 2), the algorithm becomes the same as the Haar wavelet. We "predict" that the odd value vec[1] will be the same as the even value, vec[0].

Reimplemented from liftbase.

Definition at line 132 of file line_int.h.

00133   {
00134     int half = N >> 1;
00135     int predictVal;
00136 
00137     for (int i = 0; i < half; i++) {
00138       int j = i + half;
00139       if (i < half-1) {
00140         predictVal = (int)((((float)vec[i] + (float)vec[i+1])/2.0) + 0.5);
00141       }
00142       else if (N == 2) {
00143         predictVal = vec[0];
00144       }
00145       else {
00146         // i == half-1
00147         // Calculate the last "odd" prediction
00148         int n_plus1 = new_n_plus1( vec[i-1], vec[i] );
00149         predictVal = (int)((((float)vec[i] + (float)n_plus1)/2.0) + 0.5);
00150       }
00151 
00152       if (direction == forward) {
00153         vec[j] = vec[j] - predictVal;
00154       }
00155       else if (direction == inverse) {
00156         vec[j] = vec[j] + predictVal;
00157       }
00158       else {
00159         printf("line::predict: bad direction value\n");
00160       }
00161     }
00162   } // predict

template<class T>
void line_int<T>::update ( T & vec,
int N,
transDirection direction ) [inline, protected, virtual]
 

Update step of the linear interpolation wavelet.

The predict phase works on the odd elements in the second half of the array. The update phase works on the even elements in the first half of the array. The update phase attempts to preserve the average. After the update phase is completed the average of the even elements should be approximately the same as the average of the input data set from the previous iteration. The result of the update phase becomes the input for the next iteration.

In a Haar wavelet the average that replaces the even element is calculated as the average of the even element and its neighboring odd element (e.g., its odd neighbor before the split). In the lifting scheme version of the Haar wavelet the odd element has been overwritten by the difference between the odd element and its even neighbor. In calculating the average (to replace the even element) the value of the odd element can be recovered via a simple algebraic manipulation.

In the line wavelet the odd element has been replaced by the difference between the odd element and the mid-point of its two even neighbors. Recovering the value of the odd element to calculate the average is not as simple in this case.

The value that is added to the even element to preserve the average is calculated by the equation shown below. This equation is given in Wim Sweldens' journal articles and his tutorial (Building Your Own Wavelets at Home) and in Ripples in Mathematics. A somewhat more complete derivation of this equation is provided in Ripples in Mathematics by A. Jensen and A. la Cour-Harbo, Springer, 2001.

The equation used to calculate the average is shown below for a given iteratin i. Note that the predict phase has already completed, so the odd values belong to iteration i+1.

  eveni+1,j = eveni,j op (oddi+1,k-1 + oddi+1,k)/4
    

This version of the line wavelet code implements an integer version of linear interpolating wavelet. This versoin comes from the paper Wavelet Transforms that Map Integers to Integers by A.R. Calderbank, ingrid daubechies, wim weldens and Boon-Lock Yeo, August 1996

This is the central reference that was used to develop this code. Parts 1 and 2 of this paper are for the mathematicially sophisticated (which is to say, they are not light reading). However, for the implementer, part 3 and part 4 of this paper provide excellent coverage of perfectly invertable wavelet transforms that map integers to integers. In fact, part 3 of this paper is worth reading in general for its discussion of the wavelet Lifting Scheme.

The value added (or subtracted) from the eveni,j (depending on whether the forward or inverse transform is being calculated) is calculated from oddi+1,k-1 and oddi+1,k from the predict step. This means that there is missing value at the start of the set of odd elements (e.g., i = 0, j == half). This missing value assumed to line on a line with the first two odd elements.

Because interpolated values are used, the average is not perfectly maintained.

Reimplemented from liftbase.

Definition at line 234 of file line_int.h.

00235   {
00236     int half = N >> 1;
00237 
00238     for (int i = 0; i < half; i++) {
00239       int j = i + half;
00240       int val;
00241 
00242       if (i == 0 && N == 2) {
00243         val = (int)(((float)vec[j]/2.0) + 0.5);
00244       }
00245       else if (i == 0 && N > 2) {
00246         int v_n_minus_1 = new_n_minus1( vec[j], vec[j+1] );
00247         val = (int)((((float)v_n_minus_1 + (float)vec[j])/4.0) + 0.5);
00248       }
00249       else {
00250         val = (int)((((float)vec[j-1] + (float)vec[j])/4.0) + 0.5);
00251       }
00252       if (direction == forward) {
00253         vec[i] = vec[i] + val;
00254       }
00255       else if (direction == inverse) {
00256         vec[i] = vec[i] - val;
00257       }
00258       else {
00259         printf("update: bad direction value\n");
00260       }
00261     } // for    
00262   } // update


The documentation for this class was generated from the following file:
Generated at Sat Aug 10 13:23:37 2002 for Wavelet Packet Transform and Lossless Compression by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001