VKEDCO: Vladimir Kulyukin's Education Coop: July 2015

Problem

Given a 1D signal of length 2^n, how can we construct the 2^n x 2^n matrices for 1D direct and inverse Haar wavelet transforms?

Direct Matrix

The 2^n by 2^n matrix for 2D direct Haar wavelet transform is obtained by computing 1D Haar transforms of the 2^n basis vectors. Each such vector becomes the corresponding column of the matrix. In other words, the directly transformed 0th base vector becomes the 0th column of the direct matrix, the 1st transformed base vector becomes the 1st column in the direct matrix and so on. For example, if we want to compute the forward matrix for any signal of length 2^3, we need to convert the following 8 basis vectors:

double[] bv0 = {1, 0, 0, 0, 0, 0, 0, 0};
double[] bv1 = {0, 1, 0, 0, 0, 0, 0, 0};
double[] bv2 = {0, 0, 1, 0, 0, 0, 0, 0};
double[] bv3 = {0, 0, 0, 1, 0, 0, 0, 0};
double[] bv4 = {0, 0, 0, 0, 1, 0, 0, 0};
double[] bv5 = {0, 0, 0, 0, 0, 1, 0, 0};
double[] bv6 = {0, 0, 0, 0, 0, 0, 1, 0};
double[] bv7 = {0, 0, 0, 0, 0, 0, 0, 1};

The 1D Haar transforms of these vectors can be computed by using OneDHaar.orderedFastHaarWaveletTransform(double[] v). Let us quickly define two methods to display the results.

public static void forward_basis_vector(double[] bv) {
        OneDHaar.orderedFastHaarWaveletTransform(bv);
        OneDHaar.displaySample(bv);
}

public static void test_forward_basis_vectors() {
        double[] bv0 = {1, 0, 0, 0, 0, 0, 0, 0};
        double[] bv1 = {0, 1, 0, 0, 0, 0, 0, 0};
        double[] bv2 = {0, 0, 1, 0, 0, 0, 0, 0};
        double[] bv3 = {0, 0, 0, 1, 0, 0, 0, 0};
        double[] bv4 = {0, 0, 0, 0, 1, 0, 0, 0};
        double[] bv5 = {0, 0, 0, 0, 0, 1, 0, 0};
        double[] bv6 = {0, 0, 0, 0, 0, 0, 1, 0};
        double[] bv7 = {0, 0, 0, 0, 0, 0, 0, 1};

        forward_basis_vector(bv0);
        forward_basis_vector(bv1);
        forward_basis_vector(bv2);
        forward_basis_vector(bv3);
        forward_basis_vector(bv4);
        forward_basis_vector(bv5);
        forward_basis_vector(bv6);
        forward_basis_vector(bv7);
}

The output of test_forward_basis_vectors() is as follows:

0.125 0.125 0.25 0.0 0.5 0.0 0.0 0.0
0.125 0.125 0.25 0.0 -0.5 0.0 0.0 0.0
0.125 0.125 -0.25 0.0 0.0 0.5 0.0 0.0
0.125 0.125 -0.25 0.0 0.0 -0.5 0.0 0.0
0.125 -0.125 0.0 0.25 0.0 0.0 0.5 0.0
0.125 -0.125 0.0 0.25 0.0 0.0 -0.5 0.0
0.125 -0.125 0.0 -0.25 0.0 0.0 0.0 0.5
0.125 -0.125 0.0 -0.25 0.0 0.0 0.0 -0.5

Now we can compute the direct or forward 2D Haar matrix for any n.

public static double[][] computeForwardHaarTransformMatrix(int n) {
        int size = (int) Math.pow(2, n);
        double[] base_vector = new double[size];
        double[][] fhw = new double[size][size];
        for(int col_num = 0; col_num < size; col_num++) {
            for(int i = 0; i < size; i++) {
                if ( i == col_num )
                    base_vector[i] = 1;
                else
                    base_vector[i] = 0;
            }
            OneDHaar.orderedFastHaarWaveletTransform(base_vector);
            for(int row_num = 0; row_num < size; row_num++) {
                fhw[row_num][col_num] = base_vector[row_num];
            }
        }

        return fhw;
}

We can test our implementation with testForwardHaarTransformMatrix():

public static void testForwardHaarTransformMatrix() {
        double[][] fhtm3 = OneDHaar.computeForwardHaarTransformMatrix(3);
        double[][] fhtm4 = OneDHaar.computeForwardHaarTransformMatrix(4);
        TwoDHaar.displaySample(fhtm3, 8, 0);
        double[] sample00 = {1, 1, 1, 1, 1, 1, 1, 1};
        double[] sample01 = {1, 1, 1, 1, 1, 1, 1, 1};
        System.out.print("Input:\t"); OneDHaar.displaySample(sample00);
        OneDHaar.orderedFastHaarWaveletTransform(sample00);
        System.out.print("FHWT:\t"); OneDHaar.displaySample(sample00);
        double[] fwd_sample01 = OneDHaar.applyHaarTransformMatrix(fhtm3, sample01);
        System.out.print("MHWT:\t"); OneDHaar.displaySample(fwd_sample01);
        System.out.println();

        double[] sample10 = {1, 1, 1, 1, 0, 0, 0, 0};
        double[] sample11 = {1, 1, 1, 1, 0, 0, 0, 0};
        System.out.print("Input:\t"); OneDHaar.displaySample(sample10);
        OneDHaar.orderedFastHaarWaveletTransform(sample10);
        System.out.print("FHWT:\t"); OneDHaar.displaySample(sample10);
        double[] fwd_sample11 = OneDHaar.applyHaarTransformMatrix(fhtm3, sample11);
        System.out.print("MHWT:\t"); OneDHaar.displaySample(fwd_sample11);

        double[] sample20 = {12.0, 16.0, 27.0, 32.8, 33.5, 33.5, 39.0, 39.0,
                             40.0, 41.3, 41.3, 42.0, 43.0, 45.0, 35.5, 49.0};
        double[] sample21 = {12.0, 16.0, 27.0, 32.8, 33.5, 33.5, 39.0, 39.0,
                             40.0, 41.3, 41.3, 42.0, 43.0, 45.0, 35.5, 49.0};
        System.out.print("Input:\t"); OneDHaar.displaySample(sample20);
        OneDHaar.orderedFastHaarWaveletTransform(sample20);
        System.out.print("FHWT:\t"); OneDHaar.displaySample(sample20);
        double[] fwd_sample21 = OneDHaar.applyHaarTransformMatrix(fhtm4, sample21);
        System.out.print("MHWT:\t"); OneDHaar.displaySample(fwd_sample21);
}

Inverse Matrix

The 2^n by 2^n matrix for the inverse 2D Haar wavelet transform is obtained by computing the inverse 1D Haar transforms of the 2^n basis vectors. Each such vector becomes the corresponding column of the inverse matrix. In other words, the inversely transformed 0th base vector becomes the 0th column vector, the 1st inversely transformed base vector becomes the 1st column in the direct matrix and so on. For example, if we want to compute the inverse matrix for any signal of length 2^3, we need to compute the inverse transforms the following 8 basis vectors:

double[] bv0 = {1, 0, 0, 0, 0, 0, 0, 0};
double[] bv1 = {0, 1, 0, 0, 0, 0, 0, 0};
double[] bv2 = {0, 0, 1, 0, 0, 0, 0, 0};
double[] bv3 = {0, 0, 0, 1, 0, 0, 0, 0};
double[] bv4 = {0, 0, 0, 0, 1, 0, 0, 0};
double[] bv5 = {0, 0, 0, 0, 0, 1, 0, 0};
double[] bv6 = {0, 0, 0, 0, 0, 0, 1, 0};
double[] bv7 = {0, 0, 0, 0, 0, 0, 0, 1};

The inverse 1D Haar transforms of these vectors can be computed by using OneDHaar.orderedFastInverseHaarWaveletTransform(double[] v). Let us quickly define two methods to display the results.

public static void inverse_basis_vector(double[] bv) {
        OneDHaar.orderedFastInverseHaarWaveletTransform(bv);
        OneDHaar.displaySample(bv);
}

public static void test_inverse_basis_vectors() {
        double[] bv0 = {1, 0, 0, 0, 0, 0, 0, 0};
        double[] bv1 = {0, 1, 0, 0, 0, 0, 0, 0};
        double[] bv2 = {0, 0, 1, 0, 0, 0, 0, 0};
        double[] bv3 = {0, 0, 0, 1, 0, 0, 0, 0};
        double[] bv4 = {0, 0, 0, 0, 1, 0, 0, 0};
        double[] bv5 = {0, 0, 0, 0, 0, 1, 0, 0};
        double[] bv6 = {0, 0, 0, 0, 0, 0, 1, 0};
        double[] bv7 = {0, 0, 0, 0, 0, 0, 0, 1};

        inverse_basis_vector(bv0);
        inverse_basis_vector(bv1);
        inverse_basis_vector(bv2);
        inverse_basis_vector(bv3);
        inverse_basis_vector(bv4);
        inverse_basis_vector(bv5);
        inverse_basis_vector(bv6);
        inverse_basis_vector(bv7);
}

The output of running test_inverse_basis_vectors() is given below.

1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 -1.0 -1.0 -1.0 -1.0
1.0 1.0 -1.0 -1.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 1.0 1.0 -1.0 -1.0
1.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 1.0 -1.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 1.0 -1.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 1.0 -1.0

We can now compute the inverse 2D Haar matrix for any n:

public static double[][] computeInverseHaarTransformMatrix(int n) {
        int size = (int) Math.pow(2, n);
        double[] base_vector = new double[size];
        double[][] ihw = new double[size][size];
        for(int col_num = 0; col_num < size; col_num++) {
            for(int i = 0; i < size; i++) {
                if ( i == col_num )
                    base_vector[i] = 1;
                else
                    base_vector[i] = 0;
            }
            OneDHaar.orderedFastInverseHaarWaveletTransform(base_vector);
            for(int row_num = 0; row_num < size; row_num++) {
                ihw[row_num][col_num] = base_vector[row_num];
            }
        }

        return ihw;
}

We can test the computation of the inverse 2D matrix as follows:

public static void testInverseHaarTransformMatrix() {
        double[][] ihtm3 = OneDHaar.computeInverseHaarTransformMatrix(3);
        double[][] ihtm4 = OneDHaar.computeInverseHaarTransformMatrix(4);
        TwoDHaar.displaySample(ihtm3, 8, 0);

        double[] sample00 = {1, 1, 1, 1, 1, 1, 1, 1};
        double[] sample01 = {1, 1, 1, 1, 1, 1, 1, 1};
        OneDHaar.orderedFastHaarWaveletTransform(sample00);
        OneDHaar.orderedFastHaarWaveletTransform(sample01);

        System.out.print("Input:\t"); OneDHaar.displaySample(sample00);
        OneDHaar.orderedFastInverseHaarWaveletTransform(sample00);
        System.out.print("IFHWT:\t"); OneDHaar.displaySample(sample00);
        double[] isample01 = OneDHaar.applyHaarTransformMatrix(ihtm3, sample01);
        System.out.print("IMHWT:\t"); OneDHaar.displaySample(isample01);
        System.out.println();

        double[] sample10 = {1, 1, 1, 1, 0, 0, 0, 0};
        double[] sample11 = {1, 1, 1, 1, 0, 0, 0, 0};
        OneDHaar.orderedFastHaarWaveletTransform(sample10);
        OneDHaar.orderedFastHaarWaveletTransform(sample11);
        System.out.print("Input:\t"); OneDHaar.displaySample(sample10);
        OneDHaar.orderedFastInverseHaarWaveletTransform(sample10);
        System.out.print("IFHWT:\t"); OneDHaar.displaySample(sample10);
        double[] isample11 = OneDHaar.applyHaarTransformMatrix(ihtm3, sample11);
        System.out.print("IMHWT:\t"); OneDHaar.displaySample(isample11);

        double[] sample20 = {12.0, 16.0, 27.0, 32.8, 33.5, 33.5, 39.0, 39.0,
                             40.0, 41.3, 41.3, 42.0, 43.0, 45.0, 35.5, 49.0};
        double[] sample21 = {12.0, 16.0, 27.0, 32.8, 33.5, 33.5, 39.0, 39.0,
                             40.0, 41.3, 41.3, 42.0, 43.0, 45.0, 35.5, 49.0};
        OneDHaar.orderedFastHaarWaveletTransform(sample20);
        OneDHaar.orderedFastHaarWaveletTransform(sample21);
        System.out.print("Input:\t"); OneDHaar.displaySample(sample20);
        OneDHaar.orderedFastInverseHaarWaveletTransform(sample20);
        System.out.print("IFHWT:\t"); OneDHaar.displaySample(sample20);
        double[] isample21 = OneDHaar.applyHaarTransformMatrix(ihtm4, sample21);
        System.out.print("IMHWT:\t"); OneDHaar.displaySample(isample21);
}

Matrix Multiplication

Here is how the direct or inverse matrices can be applied to the transform or invert the 1D signals:

public static double[] applyHaarTransformMatrix(double[][] htm, double[] v) {
        int num_rows = htm.length;
        if ( num_rows < 1 ) return null;
        int num_cols = htm[0].length;
        if ( num_cols < 1 ) return null;
        if ( num_rows != num_cols ) return null;
        if ( num_rows != v.length ) return null;
        double[] inversed_v = new double[num_cols];
        double dot_product = 0;
        for(int row = 0; row < num_rows; row++) {
            dot_product = 0;
            for(int col = 0; col < num_cols; col++) {
                dot_product += htm[row][col]*v[col];
            }
            inversed_v[row] = dot_product;
        }
        return inversed_v;
    }

Friday, July 24, 2015

Programmatic Construction of Multi-Scale 2D Matrices for Direct and Inverse 1D Haar Wavelet Transform