In this tutorial I will show you a step by step guide on how haar wavelet transform happens. We will show this implementation with sample data on which we will perform haar wavelet transform. Haar Wavelet Transform is based on Lifting Scheme.

Haar wavelet transformation basically used in image processing. Using haar wavelet transform you can reduce the size of the image without compromising the quality of the image. So your image quality is not going to be decreased.

Using haar wavelet transform you can watermark the digital media and it will prevent the digital media from stealing. Even if someone steals your digital media, you can proof that the digital media belongs to you.

Lifting Schema

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

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

private static int getHaarMaxCycles(int hw) {
        int cycles = 0;
        while (hw > 1) {
            cycles++;
            hw /= 2;
        }
        return cycles;
    }

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

private static boolean isCycleAllowed(int maxCycle, int cycles) {
    return cycles <= maxCycle;
}

Now I will show you how you can apply forwrd and inverse transforms on Haar matrix. The below functions computes forward 1D transform on Haar matrix.

public static double[] doHaar1DFWTransform(int[] pixels, int cycles) {
        int w = pixels.length;
        int maxCycle = getHaarMaxCycles(w);
        boolean isCycleAllowed = isCycleAllowed(maxCycle, cycles);
        if (isCycleAllowed) {
            double[] tempPixels = new double[w];
            for (int i = 0; i < cycles; i++) {
                for (int j = 0; j < w; j++) {
                    tempPixels[j] = (pixels[2 * j] + pixels[2 * j + 1]) / 2;
                    tempPixels[j + w] = (pixels[2 * j] - pixels[2 * j + 1]) / 2;
                }
                w /= 2;
            }
            return tempPixels;
        }
        return null;
    }

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

public static double[][] doHaar2DFWTransform(int[][] pixels, int cycles) {
        int w = pixels[0].length;
        int h = pixels.length;
        int maxCycle = getHaarMaxCycles(w);
        boolean isCycleAllowed = isCycleAllowed(maxCycle, cycles);
        if (isCycleAllowed) {
            double[][] ds = new double[h][w];
            double[][] tempds = new double[h][w];
            for (int i = 0; i < pixels.length; i++) {
                for (int j = 0; j < pixels[0].length; j++) {
                    ds[i][j] = pixels[i][j];
                }
            }
            for (int i = 0; i < cycles; i++) {
                w /= 2;
                for (int j = 0; j < h; j++) {
                    for (int k = 0; k < w; k++) {
                        double a = ds[j][2 * k];
                        double b = ds[j][2 * k + 1];
                        double add = a + b;
                        double sub = a - b;
                        double avgAdd = add / 2;
                        double avgSub = sub / 2;
                        tempds[j][k] = avgAdd;
                        tempds[j][k + w] = avgSub;
                    }
                }
                for (int j = 0; j < h; j++) {
                    for (int k = 0; k < w; k++) {
                        ds[j][k] = tempds[j][k];
                        ds[j][k + w] = tempds[j][k + w];
                    }
                }
                h /= 2;
                for (int j = 0; j < w; j++) {
                    for (int k = 0; k < h; k++) {
                        double a = ds[2 * k][j];
                        double b = ds[2 * k + 1][j];
                        double add = a + b;
                        double sub = a - b;
                        double avgAdd = add / 2;
                        double avgSub = sub / 2;
                        tempds[k][j] = avgAdd;
                        tempds[k + h][j] = avgSub;
                    }
                }
                for (int j = 0; j < w; j++) {
                    for (int k = 0; k < h; k++) {
                        ds[k][j] = tempds[k][j];
                        ds[k + h][j] = tempds[k + h][j];
                    }
                }
            }
            return ds;
        }
        return null;
    }

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

public static double[][] doHaar2DInvTransform(double[][] pixels, int cycles) {
        int w = pixels[0].length;
        int h = pixels.length;
        int maxCycle = getHaarMaxCycles(w);
        boolean isCycleAllowed = isCycleAllowed(maxCycle, cycles);
        if (isCycleAllowed) {
            double[][] ds = new double[h][w];
            double[][] tempds = new double[h][w];
            for (int i = 0; i < pixels.length; i++) {
                for (int j = 0; j < pixels[0].length; j++) {
                    ds[i][j] = pixels[i][j];
                }
            }
            int hh = h / (int) Math.pow(2, cycles);
            int ww = w / (int) Math.pow(2, cycles);
            for (int i = cycles; i > 0; i--) {
                for (int j = 0; j < ww; j++) {
                    for (int k = 0; k < hh; k++) {
                        double a = ds[k][j];
                        double b = ds[k + hh][j];
                        double add = a + b;
                        double sub = a - b;
                        tempds[2 * k][j] = add;
                        tempds[2 * k + 1][j] = sub;
                    }
                }
                for (int j = 0; j < ww; j++) {
                    for (int k = 0; k < hh; k++) {
                        ds[2 * k][j] = tempds[2 * k][j];
                        ds[2 * k + 1][j] = tempds[2 * k + 1][j];
                    }
                }
                hh *= 2;
                for (int j = 0; j < hh; j++) {
                    for (int k = 0; k < ww; k++) {
                        double a = ds[j][k];
                        double b = ds[j][k + ww];
                        double add = a + b;
                        double sub = a - b;
                        tempds[j][2 * k] = add;
                        tempds[j][2 * k + 1] = sub;
                    }
                }
                for (int j = 0; j < hh; j++) {
                    for (int k = 0; k < ww; k++) {
                        ds[j][2 * k] = tempds[j][2 * k];
                        ds[j][2 * k + 1] = tempds[j][2 * k + 1];
                    }
                }
                ww *= 2;
            }
            return ds;
        }
        return null;
    }

The whole source code can be downloaded from the link given at the booom of this post.

Sample values for testing the Haar wavelet transform is given below:

public static void main(String[] args) {
		int[][] pixels = new int[4][4];
		pixels[0][0] = 10;
		pixels[0][1] = 5;
		pixels[0][2] = 3;
		pixels[0][3] = 2;
		pixels[1][0] = 8;
		pixels[1][1] = 4;
		pixels[1][2] = 7;
		pixels[1][3] = 9;
		pixels[2][0] = 1;
		pixels[2][1] = 5;
		pixels[2][2] = 7;
		pixels[2][3] = 6;
		pixels[3][0] = 7;
		pixels[3][1] = 5;
		pixels[3][2] = 3;
		pixels[3][3] = 1;

		System.out.println("::Original Matrix::");
		System.out.println("=======================================");
		for (int i = 0; i < pixels.length; i++) {
			for (int j = 0; j < pixels[0].length; j++) {
				System.out.print(pixels[i][j] + " ");
			}
			System.out.println();
		}

		System.out.println();

		double[][] haar2DFWTransform = HaarWaveletTransform.doHaar2DFWTransform(pixels, 1);

		System.out.println("::2D Forward Wavelet Transform::");
		System.out.println("=======================================");
		for (int i = 0; i < haar2DFWTransform.length; i++) {
			for (int j = 0; j < haar2DFWTransform[0].length; j++) {
				System.out.print(haar2DFWTransform[i][j] + " ");
			}
			System.out.println();
		}

		System.out.println();

		double[][] haar2DInvTransform = HaarWaveletTransform.doHaar2DInvTransform(haar2DFWTransform, 1);

		System.out.println("::2D Reverse Wavelet Transform::");
		System.out.println("=======================================");
		for (int i = 0; i < haar2DInvTransform.length; i++) {
			for (int j = 0; j < haar2DInvTransform[0].length; j++) {
				System.out.print((int)haar2DInvTransform[i][j] + " ");
			}
			System.out.println();
		}
	}

Testing

The above sample data will produce the below output in the console:

::Original Matrix::
=======================================
10 5 3 2 
8 4 7 9 
1 5 7 6 
7 5 3 1 

::2D Forward Wavelet Transform::
=======================================
6.75 5.25 2.5 0.5 
4.5 4.25 2.0 -1.0 
0.75 -2.75 -2.0 0.5 
-1.5 2.25 1.0 1.0 

::2D Reverse Wavelet Transform::
=======================================
10 5 3 2 
8 4 7 9 
1 5 7 6 
7 5 3 1 

In the above output I see that the reverse transform algorithm has produced the original matrix.

Source Code

Download

Thanks for reading.