wavelets
Class inplace_haar

java.lang.Object
  |
  +--wavelets.wavelet_base
        |
        +--wavelets.inplace_haar

public class inplace_haar
extends wavelet_base

Copyright and Use

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 in-place Haar wavelet transform. By in-place 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 in-place Haar. So here we only support data that falls into an even power of two.

The sad truth about computation is that the time-space tradeoff is an iron rule. The Haar in-place 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 in-place 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 < log2( size ); l++) {
for (j = 0; j < size; j++) {
aj = 2l * (2 * j);
cj = 2l * ((2 * j) + 1);
if (cj >= 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 aj, the Haar value and the second element is cj, 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 in-place 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 in-place 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 in-place Haar wavelet function.
 void wavelet_spectrum(double[] values)
           Calculate the Haar wavelet spectrum
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

wavefx

private double[] wavefx
result of calculating the Haar wavelet

isOrdered

boolean isOrdered
initially false: true means wavefx is ordered by frequency
Constructor Detail

inplace_haar

public inplace_haar()
Method Detail

setWavefx

public void setWavefx(double[] vector)
Set the wavefx reference variable to the data vector. Also, initialize the isOrdered flag to false. This indicates that the Haar coefficients have not been calculated and ordered by frequency.

setIsOrdered

public void setIsOrdered()

wavelet_calc

public void wavelet_calc(double[] values)

Calculate the in-place Haar wavelet function. The data values are overwritten by the coefficient result, which is pointed to by a local reference (wavefx).

The in-place 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.

ai = (vi + vi+1)/2
ci = (vi - vi+1)/2

In the in-place Haar transform the values for a and c replace the values for vi and vi+1. Subsequent passes calculate new a and c values from the previous ai and ai+1 values. The produces the butterfly pattern outlined below.


v0 v1 v2 v3 v4 v5 v6 v7

a0 c0 a0 c0 a0 c0 a0 c0

a1 c0 c1 c0 a1 c0 c1 c0

a2 c0 c1 c0 c2 c0 c1 c0

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
Overrides:
wavelet_calc in class wavelet_base
Parameters:
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.

spectrum_calc

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.

wavelet_spectrum

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} 1st 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}           2nd spectrum

{29.625, 22.25}                     3ed spectrum

{25.9375}                           4th spectrum

Note that we can calculate the Haar spectrum "in-place", 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

ai = (vj + vj+1)/2

For 2n initial elements, there will be 2n - 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 in-place algorithm, the result is returned in the values argument.


pr

public void pr()
Print the result of the Haar wavelet function.
Overrides:
pr in class wavelet_base

pr_ordered

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

order

public void order()

Order the result of the in-place Haar wavelet function, referenced by wavefx. As noted above in the documentation for wavelet_calc(), the in-place 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 ... 2n). An example of the coefficient sort performed by the order() function is shown below;

before: a2 c0 c1 c0 c2 c0 c1 c0

after:  a2 c2 c1 c1 c0 c0 c0 c0

The results in the same ordering as the ordered Haar wavelet transform.

If the number of elements is 2n, then the largest number of coefficients will be 2n-1. 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.


inverse

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

ai  = a + c;
ai+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 {a1, a2, a3, a4, a5, a6, a7, a8} from

a1
c1
c2 c3
c4 c5 c6 c7

The inverse Haar transform is applied:

a1 = a1 + c1
a2 = a1 - c1

a1 = a1 + c2
a2 = a1 - c2
a3 = a2 + c3
a4 = a2 - c3

a1 = a1 + c4
a2 = a1 - c4
a3 = a2 + c5
a4 = a2 - c5
a5 = a3 + c6
a6 = a3 - c6
a7 = a4 + c7
a8 = a4 - c7

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, 2-0, 8+(-1), 8-(-1) = {2, 2, 7, 9}

2+1, 2-1, 2+(-2), 2-(-2), 7+1, 7-1, 9+0, 9-0 = {3,1,0,4,8,6,9,9}

By using the butterfly indices the inverse transform can also be applied to an unordered in-place 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 in-order 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.

Overrides:
inverse in class wavelet_base

inverse_ordered

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 in-place algorithm is a bit more complex. As noted above, the Haar value and coefficient are replaced with the newly calculated values:

t1 = a1 + c1;
t2 = a1 - c1;
a1 = t1;
c1 = t2

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.00, 8.01, 0.0, -1.0, 1.0, -2.0, 1.0, 0.0}
sort:

start: {2.00, 8.01, 0.0, -1.0, 1.0, -2.0, 1.0, 0.0}
[0, 2], [1, 3]
L = 2
{2.00, 7.02, 2.01, 9.03, 1.0, -2.0, 1.0, 0.0}
sort:
exchange [1, 2]
{2.00, 2.01, 7.02, 9.03, 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.00, 0.02, 8.04, 9.06, 1.01, 4.03, 6.05, 9.07}
sort:
exchange [1, 4]
{3.00, 1.01, 8.04, 9.06, 0.02, 4.03, 6.05, 9.07}
exchange [2, 5]
{3.00, 1.01, 4.03, 9.06, 0.02, 8.04, 6.05, 9.07}
exchange [3, 6]
{3.00, 1.01, 4.03, 6.05, 0.02, 8.04, 9.06, 9.07}
exchange [2, 4]
{3.00, 1.01, 0.02, 6.05, 4.03, 8.04, 9.06, 9.07}
exchange [3, 5]
{3.00, 1.01, 0.02, 8.04, 4.03, 6.05, 9.06, 9.07}
exchange [3, 4]
{3.00, 1.01, 0.02, 4.03, 8.04, 6.05, 9.06, 9.07}

inverse_butterfly

private void inverse_butterfly()

Calculate the inverse Haar transform on the result of the in-place Haar transform.

The inverse butterfly exactly reverses in-place Haar transform. Instead of generating coefficient values (ci), the inverse butterfly calculates Haar values (ai) using the equations:

new_ai = ai + ci
new_ai+1 = ai - ci
a0 c0 c1 c0 c2 c0 c1 c0

a1 = a0 + c2
a1 = a0 - c2

a1 c0 c1 c0 a1 c0 c1 c0

a2 = a1 + c1
a2 = a1 - c1
a2 = a1 + c1
a2 = a1 - c1

a2 c0 a2 c0 a2 c0 a2 c0

a3 = a2 + c0
a3 = a2 - c0
a3 = a2 + c0
a3 = a2 - c0
a3 = a2 + c0
a3 = a2 - c0
a3 = a2 + c0
a3 = a2 - c0

a3 a3 a3 a3 a3 a3 a3 a3 

A numeric example is shown below.

50  10  01 -20 -32  10 -11  00

a1 = 5 + (-3) = 2
a1 = 5 - (-3) = 8

21  10  01 -20 81  10 -11  00

a2 = 2 + 0    = 2
a2 = 2 - 0    = 2
a2 = 8 + (-1) = 7
a2 = 8 - (-1) = 9

22  10  22 -20 72  10 92  00

a3 = 2 + 1    = 3
a3 = 2 - 1    = 1
a3 = 2 + (-2) = 0
a3 = 2 - (-2) = 4
a3 = 7 + 1    = 8
a3 = 7 - 1    = 6
a3 = 9 + 0    = 9
a3 = 9 - 0    = 9

33  13  03  43  83  63  93  93

Note that the inverse_butterfly function is faster than the inverse_ordered function, since data does not have to be reshuffled during the calculation.