

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +wavelets.wavelet_base  +wavelets.inplace_haar
You may use this source code without limitation and without fee as long as you include:
This software was written and is copyrighted by Ian Kaplan, Bear Products International, www.bearcave.com, 2001.
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
To generate the documentation for the wavelets package using Sun Microsystem's javadoc use the command
javadoc private wavelets
The inplace_haar class calculates an inplace Haar wavelet transform. By inplace it's ment that the result occupies the same array as the data set on which the Haar transform is calculated.
The Haar wavelet calculation is awkward when the data values are not an even power of two. This is especially true for the inplace Haar. So here we only support data that falls into an even power of two.
The sad truth about computation is that the timespace tradeoff is an iron rule. The Haar inplace wavelet transform is more memory efficient, but it also takes more computation.
The algorithm used here is from Wavelets Made Easy by Yves Nievergelt, section 1.4. The inplace transform replaces data values when Haar values and coefficients. This algorithm uses a butterfly pattern, where the indices are calculated by the following:
for (l = 0; l < log_{2}( size ); l++) { for (j = 0; j < size; j++) { a_{j} = 2^{l} * (2 * j); c_{j} = 2^{l} * ((2 * j) + 1); if (c_{j} >= size) break; } // for j } // for l
If there are 16 data elements (indexed 0..15), these loops will generate the butterfly index pattern shown below, where the first element in a pair is a_{j}, the Haar value and the second element is c_{j}, the Haar coefficient.
{0, 1} {2, 3} {4, 5} {6, 7} {8, 9} {10, 11} {12, 13} {14, 15} {0, 2} {4, 6} {8, 10} {12, 14} {0, 4} {8, 12} {0, 8}
Each of these index sets represents a Haar wavelet frequency (here they are listed from the highest frequency to the lowest).
Field Summary  
(package private) boolean 
isOrdered
initially false: true means wavefx is ordered by frequency 
private double[] 
wavefx
result of calculating the Haar wavelet 
Constructor Summary  
inplace_haar()

Method Summary  
private void 
inverse_butterfly()
Calculate the inverse Haar transform on the result of the inplace Haar transform. 
private void 
inverse_ordered()
Calculate the inverse Haar transform on an ordered set of coefficients. 
void 
inverse()
Regenerate the data from the Haar wavelet function. 
void 
order()
Order the result of the inplace Haar wavelet function, referenced by wavefx. 
void 
pr_ordered()
Print the Haar value and coefficient showing the ordering. 
void 
pr()
Print the result of the Haar wavelet function. 
void 
setIsOrdered()

void 
setWavefx(double[] vector)
Set the wavefx reference variable to the data vector. 
private void 
spectrum_calc(double[] values,
int start,
int end)
Recursively calculate the Haar spectrum, replacing data in the original array with the calculated averages. 
void 
wavelet_calc(double[] values)
Calculate the inplace Haar wavelet function. 
void 
wavelet_spectrum(double[] values)
Calculate the Haar wavelet spectrum 
Methods inherited from class java.lang.Object 

Field Detail 
private double[] wavefx
boolean isOrdered
Constructor Detail 
public inplace_haar()
Method Detail 
public void setWavefx(double[] vector)
public void setIsOrdered()
public void wavelet_calc(double[] values)
Calculate the inplace Haar wavelet function. The data values are overwritten by the coefficient result, which is pointed to by a local reference (wavefx).
The inplace Haar transform leaves the coefficients in a butterfly pattern. The Haar transform calculates a Haar value (a) and a coefficient (c) from the forumla shown below.
a_{i} = (v_{i} + v_{i+1})/2 c_{i} = (v_{i}  v_{i+1})/2
In the inplace Haar transform the values for a and c replace the values for v_{i} and v_{i+1}. Subsequent passes calculate new a and c values from the previous a_{i} and a_{i+1} values. The produces the butterfly pattern outlined below.
v_{0} v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{7} a_{0} c_{0} a_{0} c_{0} a_{0} c_{0} a_{0} c_{0} a_{1} c_{0} c_{1} c_{0} a_{1} c_{0} c_{1} c_{0} a_{2} c_{0} c_{1} c_{0} c_{2} c_{0} c_{1} c_{0}
For example, Haar wavelet the calculation with the data set {3, 1, 0, 4, 8, 6, 9, 9} is shown below. Bold type denotes an a value which will be used in the next sweep of the calculation.
3 1 0 4 8 6 9 9 2 1 2 2 7 1 9 0 2 1 0 2 8 1 1 0 5 1 0 2 3 1 1 0
values
 An array of double data values from which the
Haar wavelet function will be calculated. The
number of values must be a power of two.private void spectrum_calc(double[] values, int start, int end)
public void wavelet_spectrum(double[] values)
Calculate the Haar wavelet spectrum
Wavelet calculations sample a signal via a window. In the case of the Haar wavelet, this window is a rectangle. The signal is sampled in passes, using a window of a wider width for each pass. Each sampling can be thought of as generating a spectrum of the original signal at a particular resolution.
In the case of the Haar wavelet, the window is initially two values wide. The first spectrum has half as many values as the original signal, where each new value is the average of two values from the original signal.
The next spectrum is generated by increasing the window width by a factor of two and averaging four elements. The third spectrum is generated by increasing the window size to eight, etc... Note that each of these averages can be formed from the previous average.
For example, if the initial data set is
{ 32.0, 10.0, 20.0, 38.0, 37.0, 28.0, 38.0, 34.0, 18.0, 24.0, 18.0, 9.0, 23.0, 24.0, 28.0, 34.0 }
The first spectrum is constructed by averaging elements {0,1}, {2,3}, {4,5} ...
{21, 29, 32.5, 36, 21, 13.5, 23.5, 31} 1^{st} spectrum
The second spectrum is constructed by averaging elements averaging elements {0,1}, {2,3} in the first spectrum:
{25, 34.25, 17.25, 27.25} 2^{nd} spectrum {29.625, 22.25} 3^{ed} spectrum {25.9375} 4^{th} spectrum
Note that we can calculate the Haar spectrum "inplace", by replacing the original data values with the spectrum values:
{0, 25.9375, 29.625, 22.25, 25, 34.25, 17.25, 27.25, 21, 29, 32.5, 36, 21, 13.5, 23.5, 31}
The spetrum is ordered by increasing frequency. This is the same ordering used for the Haar coefficients. Keeping to this ordering allows the same code to be applied to both the Haar spectrum and a set of Haar coefficients.
This function will destroy the original data. When the Haar spectrum is calculated information is lost. For example, without the Haar coefficients, which provide the difference between the two numbers that form the average, there may be several numbers which satisify the equation
a_{i} = (v_{j} + v_{j+1})/2
For 2^{n} initial elements, there will be 2^{n}  1 results. For example:
512 : initial length 256 : 1st spectrum 128 : 2nd spectrum 64 : 3ed spectrum 32 : 4th spectrum 16 : 5th spectrum 8 : 6th spectrum 4 : 7th spectrum 2 : 8th spectrum 1 : 9th spectrum (overall average)
Since this is an inplace algorithm, the result is returned in the values argument.
public void pr()
public void pr_ordered()
Print the Haar value and coefficient showing the ordering. The Haar value is printed first, followed by the coefficients in increasing frequency. An example is shown below. The Haar value is shown in bold. The coefficients are in normal type.
Data set
{ 32.0, 10.0, 20.0, 38.0, 37.0, 28.0, 38.0, 34.0, 18.0, 24.0, 18.0, 9.0, 23.0, 24.0, 28.0, 34.0 }
Ordered Haar transform:
25.9375 3.6875 4.625 5.0 4.0 1.75 3.75 3.75 11.0 9.0 4.5 2.0 3.0 4.5 0.5 3.0
public void order()
Order the result of the inplace Haar wavelet function, referenced by wavefx. As noted above in the documentation for wavelet_calc(), the inplace Haar transform leaves the coefficients in a butterfly pattern. This can be awkward for some calculations. The order function orders the coefficients by frequency, from the lowest frequency to the highest. The number of coefficients for each frequency band follow powers of two (e.g., 1, 2, 4, 8 ... 2^{n}). An example of the coefficient sort performed by the order() function is shown below;
before: a_{2} c_{0} c_{1} c_{0} c_{2} c_{0} c_{1} c_{0} after: a_{2} c_{2} c_{1} c_{1} c_{0} c_{0} c_{0} c_{0}
The results in the same ordering as the ordered Haar wavelet transform.
If the number of elements is 2^{n}, then the largest number of coefficients will be 2^{n1}. Each of the coefficients in the largest group is separated by one element (which contains other coefficients). This algorithm pushes these together so they are not separated. These coefficients now make up half of the array. The remaining coefficients take up the other half. The next frequency down is also separated by one element. These are pushed together taking up half of the half. The algorithm keeps going until only one coefficient is left.
As with wavelet_calc above, this algorithm assumes that the number of values is a power of two.
public void inverse()
Regenerate the data from the Haar wavelet function.
There is no information loss in the Haar function. The original data can be regenerated by reversing the calculation. Given a Haar value, a and a coefficient c, two Haar values can be generated
a_{i} = a + c; a_{i+1} = a  c;
The transform is calculated from the low frequency coefficients to the high frequency coefficients. An example is shown below for the result of the ordered Haar transform. Note that the values are in bold and the coefficients are in normal type.
To regenerate {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}} from
a_{1} c_{1} c_{2} c_{3} c_{4} c_{5} c_{6} c_{7}
The inverse Haar transform is applied:
a_{1} = a_{1} + c_{1} a_{2} = a_{1}  c_{1} a_{1} = a_{1} + c_{2} a_{2} = a_{1}  c_{2} a_{3} = a_{2} + c_{3} a_{4} = a_{2}  c_{3} a_{1} = a_{1} + c_{4} a_{2} = a_{1}  c_{4} a_{3} = a_{2} + c_{5} a_{4} = a_{2}  c_{5} a_{5} = a_{3} + c_{6} a_{6} = a_{3}  c_{6} a_{7} = a_{4} + c_{7} a_{8} = a_{4}  c_{7}
For example:
5.0 3.0 0.0 1.0 1.0 2.0 1.0 0.0 5.0+(3), 5.0(3) = {2 8} 2+0, 20, 8+(1), 8(1) = {2, 2, 7, 9} 2+1, 21, 2+(2), 2(2), 7+1, 71, 9+0, 90 = {3,1,0,4,8,6,9,9}
By using the butterfly indices the inverse transform can also be applied to an unordered inplace haar function.
This function checks the to see whether the wavefx array is ordered. If wavefx is ordered the inverse transform described above is applied. If the data remains in the inorder configuration an inverse butterfly is applied. Note that once the inverse Haar is calculated the Haar function data will be replaced by the original data.
private void inverse_ordered()
Calculate the inverse Haar transform on an ordered set of coefficients.
See comment above for the inverse() method for details.
The algorithm above uses an implicit temporary. The inplace algorithm is a bit more complex. As noted above, the Haar value and coefficient are replaced with the newly calculated values:
t_{1} = a_{1} + c_{1}; t_{2} = a_{1}  c_{1}; a_{1} = t_{1}; c_{1} = t_{2}
As the calculation proceeds and the coefficients are replaced by the newly calculated Haar values, the values are out of order. This is shown in the below (use javadoc private wavelets). Here each element is numbered with a subscript as it should be ordered. A sort operation reorders these values as the calculation proceeds. The variable L is the power of two.
start: {5.0, 3.0, 0.0, 1.0, 1.0, 2.0, 1.0, 0.0} [0, 1] L = 1 {2.0_{0}, 8.0_{1}, 0.0, 1.0, 1.0, 2.0, 1.0, 0.0} sort: start: {2.0_{0}, 8.0_{1}, 0.0, 1.0, 1.0, 2.0, 1.0, 0.0} [0, 2], [1, 3] L = 2 {2.0_{0}, 7.0_{2}, 2.0_{1}, 9.0_{3}, 1.0, 2.0, 1.0, 0.0} sort: exchange [1, 2] {2.0_{0}, 2.0_{1}, 7.0_{2}, 9.0_{3}, 1.0, 2.0, 1.0, 0.0} start: {2.0, 2.0, 7.0, 9.0, 1.0, 2.0, 1.0, 0.0} [0, 4], [1, 5], [2, 6], [3, 7] L = 4 {3.0_{0}, 0.0_{2}, 8.0_{4}, 9.0_{6}, 1.0_{1}, 4.0_{3}, 6.0_{5}, 9.0_{7}} sort: exchange [1, 4] {3.0_{0}, 1.0_{1}, 8.0_{4}, 9.0_{6}, 0.0_{2}, 4.0_{3}, 6.0_{5}, 9.0_{7}} exchange [2, 5] {3.0_{0}, 1.0_{1}, 4.0_{3}, 9.0_{6}, 0.0_{2}, 8.0_{4}, 6.0_{5}, 9.0_{7}} exchange [3, 6] {3.0_{0}, 1.0_{1}, 4.0_{3}, 6.0_{5}, 0.0_{2}, 8.0_{4}, 9.0_{6}, 9.0_{7}} exchange [2, 4] {3.0_{0}, 1.0_{1}, 0.0_{2}, 6.0_{5}, 4.0_{3}, 8.0_{4}, 9.0_{6}, 9.0_{7}} exchange [3, 5] {3.0_{0}, 1.0_{1}, 0.0_{2}, 8.0_{4}, 4.0_{3}, 6.0_{5}, 9.0_{6}, 9.0_{7}} exchange [3, 4] {3.0_{0}, 1.0_{1}, 0.0_{2}, 4.0_{3}, 8.0_{4}, 6.0_{5}, 9.0_{6}, 9.0_{7}}
private void inverse_butterfly()
Calculate the inverse Haar transform on the result of the inplace Haar transform.
The inverse butterfly exactly reverses inplace Haar transform. Instead of generating coefficient values (c_{i}), the inverse butterfly calculates Haar values (a_{i}) using the equations:
new_a_{i} = a_{i} + c_{i} new_a_{i+1} = a_{i}  c_{i}
a_{0} c_{0} c_{1} c_{0} c_{2} c_{0} c_{1} c_{0} a_{1} = a_{0} + c_{2} a_{1} = a_{0}  c_{2} a_{1} c_{0} c_{1} c_{0} a_{1} c_{0} c_{1} c_{0} a_{2} = a_{1} + c_{1} a_{2} = a_{1}  c_{1} a_{2} = a_{1} + c_{1} a_{2} = a_{1}  c_{1} a_{2} c_{0} a_{2} c_{0} a_{2} c_{0} a_{2} c_{0} a_{3} = a_{2} + c_{0} a_{3} = a_{2}  c_{0} a_{3} = a_{2} + c_{0} a_{3} = a_{2}  c_{0} a_{3} = a_{2} + c_{0} a_{3} = a_{2}  c_{0} a_{3} = a_{2} + c_{0} a_{3} = a_{2}  c_{0} a_{3} a_{3} a_{3} a_{3} a_{3} a_{3} a_{3} a_{3}
A numeric example is shown below.
5_{0} 1_{0} 0_{1} 2_{0} 3_{2} 1_{0} 1_{1} 0_{0} a_{1} = 5 + (3) = 2 a_{1} = 5  (3) = 8 2_{1} 1_{0} 0_{1} 2_{0} 8_{1} 1_{0} 1_{1} 0_{0} a_{2} = 2 + 0 = 2 a_{2} = 2  0 = 2 a_{2} = 8 + (1) = 7 a_{2} = 8  (1) = 9 2_{2} 1_{0} 2_{2} 2_{0} 7_{2} 1_{0} 9_{2} 0_{0} a_{3} = 2 + 1 = 3 a_{3} = 2  1 = 1 a_{3} = 2 + (2) = 0 a_{3} = 2  (2) = 4 a_{3} = 7 + 1 = 8 a_{3} = 7  1 = 6 a_{3} = 9 + 0 = 9 a_{3} = 9  0 = 9 3_{3} 1_{3} 0_{3} 4_{3} 8_{3} 6_{3} 9_{3} 9_{3}
Note that the inverse_butterfly function is faster than the inverse_ordered function, since data does not have to be reshuffled during the calculation.


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 