Discrete Haar Wavelet Transformation

• Download demo - 725.9 KB
• Download HaarCSharp.zip

Background

Haar wavelet - Wikipedia

Discrete wavelet transform - Wikipedia

The first DWT was invented by the Hungarian mathematician Alfréd Haar. For an input represented by a list of 2ⁿ numbers, the Haar wavelet transform may be considered to simply pair up input values, storing the difference and passing the sum. This process is repeated recursively, pairing up the sums to provide the next scale: finally resulting in 2^n-1 differences and one final sum.

Suppose you are given N values

x = (x₁, x₂, … x_N)

where N is even.

We take pair-wise average of numbers

s_k = (x_2k + x_2k+1)/2 for k=0, …, N/2 -1

For example,

x = (6, 12, 15, 15, 14, 12, 120, 116) -> s = (9, 15, 13, 118)

We need second list of data d so that the original list x can be recovered from s and d.

For d_k (called directed distances), we have:

d_k = (x_2k - x_2k+1)/2 for k=0, …, N/2 -1

The process is invertible since:

s_k + d_k = (x_2k + x_2k+1)/2 + (x_2k - x_2k+1)/2 = x_2k

s_k - d_k = (x_2k + x_2k+1)/2 - (x_2k - x_2k+1)/2 = x_2k+1

So we map x = (x₁, x₂, … , x_N) to (s | d) = (s₁, … , s_N/2 | d₁, … , d_N/2).

Using our example values, we have:

(6, 12, 15, 15, 14, 12, 120, 116) -> (9, 15, 13, 118 | -3, 0, 1, 2)

This process is repeated recursively for s:

(9, 15, 13, 118 | -3, 0, 1, 2) -> (12, 65.5 | -3, -52.5 | -3, 0, 1, 2)

(12, 65.5 | -3, -52.5 | -3, 0, 1, 2) -> (38.75 | -26.75 | -3, -52.5 | -3, 0, 1, 2)

So final result is:

(38.75, -26.75, -3, -52.5, -3, 0, 1, 2)

Why might people prefer the data in this form?

• We can identify large changes in the differences portion d of the transform.
• It is easier to quantize the data in this form.
• The transform concentrates the information (energy) in the signal in fewer values.
• And the obvious answer: fewer digits!!

In case of images, we need 2D FWT. First, we perform 1D FWT for all rows, and next, for all columns. For color Images, we deal with RGB components of color, and perform Haar Transform for each component separately. Any component (R G B) has values from 0 to 255 to before transformation we scale this values. For displaying image after transformation, we scale back transformed values.

Here, we process image with C# in safe and unsafe manners and of course the second way is much faster.

Using the Code

1D Discrete Haar Wavelet Transform (one iteration):

public void FWT(double[] data)
{
    double[] temp = new double[data.Length];

    int h = data.Length >> 1;
    for (int i = 0; i < h; i++)
    {
        int k = (i << 1);
        temp[i] = data[k] * s0 + data[k + 1] * s1;
        temp[i + h] = data[k] * w0 + data[k + 1] * w1;
    }

    for (int i = 0; i < data.Length; i++)
        data[i] = temp[i];
}

2D Discrete Haar Wavelet Transform:

public void FWT(double[,] data, int iterations)
{
    int rows = data.GetLength(0);
    int cols = data.GetLength(1);

    double[] row;
    double[] col;

    for (int k = 0; k < iterations; k++)
    {
        int lev = 1 << k;

        int levCols = cols / lev;
        int levRows = rows / lev;

        row = new double[levCols];
        for (int i = 0; i < levRows; i++)
        {
            for (int j = 0; j < row.Length; j++)
                row[j] = data[i, j];

            FWT(row);

            for (int j = 0; j < row.Length; j++)
                data[i, j] = row[j];
        }


        col = new double[levRows];
        for (int j = 0; j < levCols; j++)
        {
            for (int i = 0; i < col.Length; i++)
                col[i] = data[i, j];

            FWT(col);

            for (int i = 0; i < col.Length; i++)
                data[i, j] = col[i];
        }
    }
}

1D Inverse Discrete Haar Wavelet Transform (one iteration):

public void IWT(double[] data)
{
    double[] temp = new double[data.Length];

    int h = data.Length >> 1;
    for (int i = 0; i < h; i++)
    {
        int k = (i << 1);
        temp[k] = (data[i] * s0 + data[i + h] * w0) / w0;
        temp[k + 1] = (data[i] * s1 + data[i + h] * w1) / s0;
    }

    for (int i = 0; i < data.Length; i++)
        data[i] = temp[i];
}

2D Inverse Discrete Haar Wavelet Transform:

public void IWT(double[,] data, int iterations)
{
    int rows = data.GetLength(0);
    int cols = data.GetLength(1);

    double[] col;
    double[] row;

    for (int k = iterations - 1; k >= 0; k--)
    {
        int lev = 1 << k;

        int levCols = cols / lev;
        int levRows = rows / lev;

        col = new double[levRows];
        for (int j = 0; j < levCols; j++)
        {
            for (int i = 0; i < col.Length; i++)
                col[i] = data[i, j];

            IWT(col);

            for (int i = 0; i < col.Length; i++)
                data[i, j] = col[i];
        }

        row = new double[levCols];
        for (int i = 0; i < levRows; i++)
        {
            for (int j = 0; j < row.Length; j++)
                row[j] = data[i, j];

            IWT(row);

            for (int j = 0; j < row.Length; j++)
                data[i, j] = row[j];
        }
    }
}

Example Images

Original Image Zelda 512x512:

Transformed Image (1 Iteration):

Transformed Image (2 Iterations):