Haar Wavelet Transform using Java

Haar Wavelet Transform is based on Lifting Scheme.

What is Lifting Scheme

• Wim Sweldens developed Lifting Scheme for constructing bi-orthogonal wavelets
• Simple and efficient algorithm to calculate wavelet transform
• It does not depend on Fourier Transforms
• It becomes a method to implement reversible integer wavelet transforms

Lifting Scheme Algorithm

• First split data into odd and even set
• Predict odd set from even set
It ensures polynomial cancellation in high pass
• Update even set using wavelet coefficient to calculate scaling function
It ensures preservation of moments in low pass

• It allows faster implementation of the wavelet transform
• It requires half computations as compared to traditional convolution based discrete wavelet transform
• Very efficient for real time low power applications
• Allows in-place calculation of wavelet transform. So no auxiliary memory needed and original signal can be replaced by its wavelet transform
• Allows reversible integer wavelet transform as compared to conventional scheme which introduces error due to floating operations
• Perfect reconstruction is possible for loss-less compression
• Can be used for irregular sampling

Haar Wavelet Transform

• Alfred Haar introduced first wavelet system in the year 1910
• Famous for its simplicity and speed of computation
• Two types of coefficients are obtained from Haar Wavelet Transform
Coarse approximation of speech (calculated by averaging two adjacent samples)
Fine details of speech (calculated by subtracting two adjacent samples)
• Haar Wavelet Transform involves forward and reverse transforms
Forward transform
Computation of scaling coefficients – add two adjacent sample values and divide by 2
Computation of wavelet coefficients – subtract two adjacent sample values and divide by 2
Inverse transform
Computation requires simply addition and subtraction

Haar Wavelet Algorithm

Let’s consider two neighboring samples x and y in a sequence of speech signal.

So forward transform can be achieved by

Average, a = (x+y)/2 and Difference, d = (x-y)/2

And inverse transform is applied to get the original sample values

x = (a – d)/2 and y = (a+d)/2

Before you look at the below source code, you can go through first how Haar wavelet transform happens step-by-step given in this video tutorial.

The below function calculates maximum number of cycles we can get from a Haar matrix. We divide height or width of the previous height or previous width of the matrix by 2 at each cycle.

The below function checks whether we can apply the desired number of cycles on Haar matrix.

Now we will see how we can apply forward and inverse transform on Haar matrix.

The below functions computes forward 1D transform on Haar matrix.

The below function computes forward 2D transform on Haar matrix.

The below function computes 2D inverse transform on Haar matrix and gives the original matrix back.

The whole source code given below.

Test class for Haar wavelet transform with sample values.