This tutorial 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 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.

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.

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.

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 we will see how we can apply forward and inverse transform 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 given below.

package com.jeejava.image.wavelet.transforms;

public class HaarWaveletTransform {

    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;
    }

    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;
    }

    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;
    }

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

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

}

Test class for Haar wavelet transform with sample values.

package com.jeejava.image.tests;

import in.webtuts.image.wavelet.transforms.HaarWaveletTransform;

public class HaarTestWithSampleValues {

    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;

        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);
        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);
        for (int i = 0; i < haar2DInvTransform.length; i++) {
            for (int j = 0; j < haar2DInvTransform[0].length; j++) {
                System.out.print(haar2DInvTransform[i][j] + " ");
            }
            System.out.println();
        }
    }
}

That’s all.  hanks for reading.

You may also like to read haar wavelet transformation video tutorial.

Tags:

I am a professional Web developer, Enterprise Application developer, Software Engineer and Blogger. Connect me on Roy Tutorials | TwitterFacebook Google PlusLinkedin | Reddit

0 thoughts 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 *