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 
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 4point 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
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

poly class constructor


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


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


Predict an odd point from the even points, using 4point polynomial interpolation. The four points used in the polynomial interpolation are the even points. We pretend that these four points are located at the xcoordinates 0,1,2,3. The first odd point interpolated will be located between the first and second even point, at 0.5. The next N3 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).
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 == half2) { 00221 predictVal = fourPt.interpPoint( 2.5, half, d ); 00222 } 00223 else if (i == half1) { 00224 predictVal = fourPt.interpPoint( 3.5, half, d ); 00225 } 00226 else { 00227 fill( vec, d, N, i1); 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


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 }
