lift::poly Class Reference

Inheritance diagram for lift::poly:

Inheritance graph
[legend]
Collaboration diagram for lift::poly:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 poly ()
void forwardTrans (double[] vec)
void inverseTrans (double[] vec)

Protected Member Functions

void update (double[] vec, int N, int direction)
void predict (double[] vec, int N, int direction)

Static Package Attributes

static final int numPts = 4

Detailed Description

Polynomial wavelets

This wavelet transform uses a polynomial interpolation wavelet (e.g., the function used to calculate the differences). A Haar scaling function (the calculation of the average for the even points) is used.

This wavelet transform uses a two stage version of the lifting scheme. In the "classic" two stage Lifting Scheme wavelet the predict stage preceeds the update stage. Also, the algorithm is absolutely symetric, with only the operators (usually addition and subtraction) interchanged.

The problem with the classic Lifting Scheme transform is that it can be difficult to determine how to calculate the smoothing (scaling) function in the update phase once the predict stage has altered the odd values. This version of the wavelet transform calculates the update stage first and then calculates the predict stage from the modified update values. In this case the predict stage uses 4-point polynomial interpolation using even values that result from the update stage.

In this version of the wavelet transform the update stage is no longer perfectly symetric, since the forward and inverse transform equations differ by more than an addition or subtraction operator. However, this version of the transform produces a better result than the Haar transform extended with a polynomial interpolation stage.

This algorithm was suggested to me from my reading of Wim Sweldens' tutorial Building Your Own Wavelets at Home.

  
  http://www.bearcave.com/misl/misl_tech/wavelets/lifting/index.html
  

Copyright and Use

You may use this source code without limitation and without fee as long as you include: <blockquote> This software was written and is copyrighted by Ian Kaplan, Bear Products International, www.bearcave.com, 2001. </blockquote>

This software is provided "as is", without any warrenty or claim as to its usefulness. Anyone who uses this source code uses it at their own risk. Nor is any support provided by Ian Kaplan and Bear Products International.

Please send any bug fixes or suggested source changes to:

     iank@bearcave.com

Author:
Ian Kaplan


Constructor & Destructor Documentation

lift::poly::poly  )  [inline]
 

poly class constructor

00087   {
00088     fourPt = new polyinterp();
00089   }


Member Function Documentation

void lift::poly::forwardTrans double[]  vec  )  [inline]
 

Polynomial wavelet lifting scheme transform.

This version of the forwardTrans function overrides the function in the liftbase base class. This function introduces an extra polynomial interpolation stage at the end of the transform.

Reimplemented from lift::liftbase.

00256   {
00257     final int N = vec.length;
00258 
00259     for (int n = N; n > 1; n = n >> 1) {
00260       split( vec, n );
00261       update( vec, n, forward );
00262       predict( vec, n, forward );
00263     } // for
00264   } // forwardTrans

void lift::poly::inverseTrans double[]  vec  )  [inline]
 

Polynomial wavelet lifting Scheme inverse transform.

This version of the inverseTrans function overrides the function in the liftbase base class. This function introduces an inverse polynomial interpolation stage at the start of the inverse transform.

Reimplemented from lift::liftbase.

00279    {
00280      final int N = vec.length;
00281 
00282      for (int n = 2; n <= N; n = n << 1) {
00283        predict( vec, n, inverse );
00284        update( vec, n, inverse );
00285        merge( vec, n );
00286      }
00287    } // inverseTrans

void lift::poly::predict double[]  vec,
int  N,
int  direction
[inline, protected, virtual]
 

Predict an odd point from the even points, using 4-point polynomial interpolation.

The four points used in the polynomial interpolation are the even points. We pretend that these four points are located at the x-coordinates 0,1,2,3. The first odd point interpolated will be located between the first and second even point, at 0.5. The next N-3 points are located at 1.5 (in the middle of the four points). The last two points are located at 2.5 and 3.5. For complete documentation see

  
  http://www.bearcave.com/misl/misl_tech/wavelets/lifting/index.html
    

The difference between the predicted (interpolated) value and the actual odd value replaces the odd value in the forward transform.

As the recursive steps proceed, N will eventually be 4 and then 2. When N = 4, linear interpolation is used. When N = 2, Haar interpolation is used (the prediction for the odd value is that it is equal to the even value).

Parameters:
vec the input data on which the forward or inverse transform is calculated.
N the area of vec over which the transform is calculated
direction forward or inverse transform

Implements lift::liftbase.

00198   {
00199     int half = N >> 1;
00200     double d[] = new double[ numPts ];
00201 
00202     int k = 42;
00203 
00204     for (int i = 0; i < half; i++) {
00205       double predictVal;
00206 
00207       if (i == 0) {
00208         if (half == 1) {
00209           // e.g., N == 2, and we use Haar interpolation
00210           predictVal = vec[0];
00211         }
00212         else {
00213           fill( vec, d, N, 0 );
00214           predictVal = fourPt.interpPoint( 0.5, half, d );
00215         }
00216       }
00217       else if (i == 1) {
00218         predictVal = fourPt.interpPoint( 1.5, half, d );
00219       }
00220       else if (i == half-2) {
00221         predictVal = fourPt.interpPoint( 2.5, half, d );
00222       }
00223       else if (i == half-1) {
00224         predictVal = fourPt.interpPoint( 3.5, half, d );
00225       }
00226       else {
00227         fill( vec, d, N, i-1);
00228         predictVal = fourPt.interpPoint( 1.5, half, d );
00229       }
00230 
00231       int j = i + half;
00232       if (direction == forward) {
00233         vec[j] = vec[j] - predictVal;
00234       }
00235       else if (direction == inverse) {
00236         vec[j] = vec[j] + predictVal;
00237       }
00238       else {
00239         System.out.println("poly::predict: bad direction value");
00240       }
00241     }
00242   } // predict

void lift::poly::update double[]  vec,
int  N,
int  direction
[inline, protected, virtual]
 

The update stage calculates the forward and inverse Haar scaling functions. The forward Haar scaling function is simply the average of the even and odd elements. The inverse function is found by simple algebraic manipulation, solving for the even element given the average and the odd element.

In this version of the wavelet transform the update stage preceeds the predict stage in the forward transform. In the inverse transform the predict stage preceeds the update stage, reversing the calculation on the odd elements.

Implements lift::liftbase.

00137   {
00138     int half = N >> 1;
00139 
00140     for (int i = 0; i < half; i++) {
00141       int j = i + half;
00142       double updateVal = vec[j] / 2.0;
00143 
00144       if (direction == forward) {
00145         vec[i] = (vec[i] + vec[j])/2;
00146       }
00147       else if (direction == inverse) {
00148         vec[i] = (2 * vec[i]) - vec[j];
00149       }
00150       else {
00151         System.out.println("update: bad direction value");
00152       }
00153     }
00154   }


The documentation for this class was generated from the following file:
Generated on Sun Dec 11 20:01:10 2005 for LiftingScheme by  doxygen 1.4.5