Wednesday, June 29, 2016

Interpretation of Forward Ordered 2D Haar Wavelet Transform




Problem
  
This note describes how to interpret the results of the forward ordered 2D Haar Wavelet Transform (HWT).



Forward Ordered 2D HWT
  
Let us define several 2D signals to which we will apply the forward ordered 2D HWT. 

public static double[][] signal_2x2_01 = {
        {9, 7},
        {5, 3}

};

public static double[][] signal_4x4_01 = {
        {9,    7,    6,    2},
        {5,    3,    4,    4},
        {8,    2,    4,    0},
        {6,    0,    2,    2}

};

public static double[][] signal_8x8_01 = {
        {8.0,     5.0,      4.0,      8.0,      6.0,      8.0,    10.0,   8.0},   
        {8.0,     10.0,    10.0,    4.0,      10.0,    4.0,    8.0,     2.0},   
        {6.0,     10.0,    2.0,      4.0,      2.0,      6.0,    1.0,     6.0},   
        {0.0,     8.0,      0.0,      10.0,    10.0,    6.0,    6.0,     10.0},
        {8.0,     8.0,      8.0,      0.0,      4.0,      8.0,    6.0,     2.0},   
        {10.0,   6.0,      2.0,      2.0,      6.0,      6.0,    6.0,     8.0},   
        {2.0,     4.0,     10.0,    10.0,     10.0,    4.0,    6.0,     10.0},   
        {10.0,   6.0,    10.0,     6.0,       6.0,      4.0,    4.0,     4.0}

};


Let us define several methods that will be helpful in interpreting the results. The first method, computeMean(), will be placed in Utils.java. The other three methods, i.e., computeHorChangeMagn() computeVerChangeMagn(), computeDiagChangeMagn(), are placed in TwoDWT.java.  The method computeMean() computes the mean of a 2D signal. The method computeHorChangeMagn() computes the change from the average of the left half of the signal and the average of the right half of the signal. The method computeVerChangeMagn() computes the change from the average of the top half of the signal and the average of the bottom half of the signal. The method computeDiagChangeMagn() comptues the diagonal change magnitude, i.e., the change from the average of the top left and bottom right quadrants and the average of the top right and bottom left quadrants. The second argument, ttn, stands for "two to the n."

public static double computeMean(double[][] signal) {
        double mean = 0;
        int num_rows = signal.length;
        int num_cols = signal[0].length;
        for(int r = 0; r < num_rows; r++) {
            for(int c = 0; c < num_cols; c++) {
                mean += signal[r][c];
            }
        }
        return mean/(num_rows*num_cols);

}
  
public static double computeHorChangeMagn(double[][] sig, int ttn) {
        double left_mean  = Utils.computeMean(sig, 0, ttn-1, 0, ttn/2 - 1);
        double right_mean = Utils.computeMean(sig, 0, ttn-1, ttn/2, ttn-1);
        return (left_mean - right_mean)/2;

}
    

public static double computeVerChangeMagn(double[][] sig, int ttn) {
        double upper_mean = Utils.computeMean(sig, 0, ttn/2 - 1, 0, ttn-1);
        double lower_mean = Utils.computeMean(sig, ttn/2, ttn-1, 0, ttn-1);
        return (upper_mean - lower_mean)/2.0;

}
    

public static double computeDiagChangeMagn(double[][] sig, int ttn) {
        double top_left_quad_mean = Utils.computeMean(sig, 0, ttn/2 - 1, 0, ttn/2 - 1);
        double bot_right_quad_mean = Utils.computeMean(sig, ttn/2, ttn-1, ttn/2, ttn-1);
        double top_right_quad_mean = Utils.computeMean(sig, 0, ttn/2 - 1, ttn/2, ttn-1);
        double bot_left_quad_mean = Utils.computeMean(sig, ttn/2, ttn-1, 0, ttn/2 - 1);
        return ((top_left_quad_mean+bot_right_quad_mean)/2 -
                    (top_right_quad_mean+bot_left_quad_mean)/2)/2;

}

Here is a test method that computes the statistics of the 2D signal. Then it computes the ordered forward 2D HWT, displays the results, and then inverses the transform.

static void test_ordFwdInvHWT(double[][] sig, int num_iters, boolean dbg_flag) {
        final int ttn = sig.length;
        System.out.println("AVR="+Utils.computeMean(sig));
        System.out.println("HOR="+TwoDHWT.computeHorChangeMagn(sig, ttn));
        System.out.println("VER="+TwoDHWT.computeVerChangeMagn(sig, ttn));
        System.out.println("DIG="+TwoDHWT.computeDiagChangeMagn(sig, ttn));
       
        TwoDHWT.ordFwdDWTForNumIters(sig, num_iters, dbg_flag);


        if ( dbg_flag ) {
            System.out.println();
            System.out.println("Forward Transform");
            Utils.display2DArray(sig, sig.length, sig[0].length);
            System.out.println("================");
            System.out.println("Iverse Transform");
        }
       
        TwoDHWT.ordInvDWTForNumIters(sig, num_iters, num_iters, dbg_flag);


        if ( dbg_flag ) {
            System.out.println("Inversed Matrix");
            Utils.display2DArray(sig, sig.length, sig[0].length);
        }
 }






Interpretation of Results
  
Let us define several 2D signals to which we will apply the forward ordered 2D HWT. 

test_ordFwdInvHWT(signal_2x2_01, 1, true):

The statistics computed by the above method call correspond to the resultant transform.

AVR=6.0
HOR=1.0
VER=2.0
DIG=0.0


Forward Transform
6.0 1.0
2.0 0.0


Let us call the test method on a 4x4 signal: test_ordFwdInvHWT(signal_4x4_01, 2, true):

AVR=4.0
HOR=1.0
VER=1.0
DIG=0.0


Forward Transform
4.0 1.0 1.0 1.0
1.0 0.0 3.0 1.0
2.0 0.0 0.0 1.0
1.0 0.0 0.0 1.0


The top 2x2 corner of the above forward transform contains the average (4.0), the horizontal change magnitude (1.0), the vertical change magnitude (1.0), and the diagonal change magnitude (0.0).  

Let us call the test method on an 8x8 signal: test_ordFwdInvHWT(signal_8x8_01, 2, true):

AVR=6.1875
HOR=0.03125
VER=0.0625
DIG=-0.21875


Forward Transform
6.1875 0.03125 0.8125 0.0625 0.25 0.5 1.0 2.0
0.0625 -0.21875 0.375 0.125 -3.0 -3.0 0.0 -2.25
1.0625 0.5625 -0.1875 -0.0625 1.0 2.0 -1.0 0.5
-0.875 -0.125 2.125 0.125 0.5 1.0 2.0 -1.0
-1.25 -0.5 0.0 2.0 1.25 -2.5 -2.0 -1.0
2.0 -1.0 -2.0 -2.25 1.0 2.0 -2.0 -0.25
0.0 1.0 0.0 -1.5 -1.0 2.0 -1.0 1.5
-2.5 1.0 1.0 2.0 -1.5 -1.0 1.0 -1.0 


The top 2x2 corner of the above transform contains the average (6.1875), the horizontal change magnitude (0.03125), the vertical change magnitude (0.0625), and the diagonal change (-0.21875).  Figures 1, 2, and 3 give the components of the forward transform after the 1st, 2nd, and 3rd scales, respectively.

Figure 1. Horizontal, vertical, diagonal wavelet coefficients after 1st scale