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

Advantages of Lifting Scheme

  • 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.

 

That’s all. Thank you for reading this article.

Soumitra

Software Professional, I am passionate to work on web/enterprise application. For more information please go to about me. You can follow on Twitter. You can be a friend on Facebook or Google Plus or Linkedin

One thought on “Haar Wavelet Transform using Java

  1. I believe in your 2D Forward Transform, the two for loops on lines 35 and 47 should be looping while j < 2*w, rather than j < w, otherwise you're only doing the column processing on the left half of the matrix ds, since w has already been divided by 2 during this iteration.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.