#include <poly.h>
Inheritance diagram for poly::
Public Methods | |
poly () | |
poly class constructor. More... | |
~poly () | |
poly (const poly &rhs) | |
void | forwardStep (T &vec, const int n) |
One step in the forward wavelet transform. More... | |
virtual void | inverseStep (T &vec, const int n) |
One inverse wavelet transform step. More... | |
Protected Methods | |
void | update (T &vec, int N, transDirection direction) |
The update stage calculates the forward and inverse Haar scaling functions. More... | |
void | predict (T &vec, int N, transDirection direction) |
Predict an odd point from the even points, using 4-point polynomial interpolation. More... | |
Private Types | |
enum | bogus { numPts = 4 } |
Private Methods | |
void | fill (T &vec, double d[], int N, int start) |
Copy four points or N (which ever is less) data points from vec into d These points are the "known" points used in the polynomial interpolation. More... | |
Private Attributes | |
polyinterp | fourPtInterp |
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.
See: http://www.bearcave.com/misl/misl_tech/wavelets/lifting/index.html
This code was originally implemented in Java and then ported to C++.
Definition at line 85 of file poly.h.
|
Definition at line 97 of file poly.h. 00097 { numPts = 4 } bogus; |
|
poly class constructor.
Definition at line 91 of file poly.h. 00091 {} |
|
Definition at line 92 of file poly.h. 00092 {} |
|
|
|
Copy four points or N (which ever is less) data points from vec into d These points are the "known" points used in the polynomial interpolation.
Definition at line 111 of file poly.h. Referenced by predict().
00112 { 00113 int n = numPts; 00114 if (n > N) 00115 n = N; 00116 int end = start + n; 00117 int j = 0; 00118 00119 for (int i = start; i < end; i++) { 00120 d[j] = vec[i]; 00121 j++; 00122 } 00123 } // fill |
|
One step in the forward wavelet transform.
Reimplemented from liftbase. |
|
One inverse wavelet transform step.
Reimplemented from liftbase. |
|
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).
Reimplemented from liftbase. Definition at line 200 of file poly.h. 00201 { 00202 int half = N >> 1; 00203 double d[4]; 00204 00205 for (int i = 0; i < half; i++) { 00206 double predictVal; 00207 00208 if (i == 0) { 00209 if (half == 1) { 00210 // e.g., N == 2, and we use Haar interpolation 00211 predictVal = vec[0]; 00212 } 00213 else { 00214 fill( vec, d, N, 0 ); 00215 predictVal = fourPtInterp.interpPoint( 0.5, half, d ); 00216 } 00217 } 00218 else if (i == 1) { 00219 predictVal = fourPtInterp.interpPoint( 1.5, half, d ); 00220 } 00221 else if (i == half-2) { 00222 predictVal = fourPtInterp.interpPoint( 2.5, half, d ); 00223 } 00224 else if (i == half-1) { 00225 predictVal = fourPtInterp.interpPoint( 3.5, half, d ); 00226 } 00227 else { 00228 fill( vec, d, N, i-1); 00229 predictVal = fourPtInterp.interpPoint( 1.5, half, d ); 00230 } 00231 00232 int j = i + half; 00233 if (direction == forward) { 00234 vec[j] = vec[j] - predictVal; 00235 } 00236 else if (direction == inverse) { 00237 vec[j] = vec[j] + predictVal; 00238 } 00239 else { 00240 printf("interp: bad direction value\n"); 00241 break; 00242 } 00243 } // for 00244 } // 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. Reimplemented from liftbase. Definition at line 144 of file poly.h. 00145 { 00146 int half = N >> 1; 00147 00148 for (int i = 0; i < half; i++) { 00149 int j = i + half; 00150 double updateVal = vec[j] / 2.0; 00151 00152 if (direction == forward) { 00153 vec[i] = (vec[i] + vec[j])/2; 00154 } 00155 else if (direction == inverse) { 00156 vec[i] = (2 * vec[i]) - vec[j]; 00157 } 00158 else { 00159 printf("update: bad direction value\n"); 00160 } 00161 } 00162 } // update |
|
|