Click here to Skip to main content
15,868,236 members
Articles / Programming Languages / C#

Discrete Haar Wavelet Transformation

Rate me:
Please Sign up or sign in to vote.
4.87/5 (32 votes)
25 Apr 2014CPOL2 min read 133.7K   11.6K   42   54
Simple application for calculating 2D Haar wavelet on images.
Image 1

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 2n 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 2n-1 differences and one final sum.

Suppose you are given N values

x = (x1, x2, … xN)

where N is even.

We take pair-wise average of numbers

sk = (x2k + x2k+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 dk (called directed distances), we have:

dk = (x2k - x2k+1)/2 for k=0, …, N/2 -1

The process is invertible since:

sk + dk = (x2k + x2k+1)/2 + (x2k - x2k+1)/2 = x2k

sk - dk = (x2k + x2k+1)/2 - (x2k - x2k+1)/2 = x2k+1

So we map x = (x1, x2, … , xN) to (s | d) = (s1, … , sN/2 | d1, … , dN/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):

C#
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:

C#
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):

C#
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:

C#
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:

Image 2

Transformed Image (1 Iteration):

Image 3

Transformed Image (2 Iterations):

Image 4

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer Seven Smarts
Armenia Armenia
.Net developer

Comments and Discussions

 
QuestionDiscrete Haar Wavelet Transformation Pin
Member 1612834720-Jan-24 0:58
Member 1612834720-Jan-24 0:58 
QuestionReconstruction Pin
Member 126130408-Dec-16 21:16
Member 126130408-Dec-16 21:16 
QuestionFeature Vector Pin
Member 1276760128-Nov-16 21:04
Member 1276760128-Nov-16 21:04 
Questionhaar wavelet transform for steganography Pin
uaena7-Apr-16 4:04
uaena7-Apr-16 4:04 
AnswerRe: haar wavelet transform for steganography Pin
Alisaace 1095826716-Feb-17 5:52
Alisaace 1095826716-Feb-17 5:52 
QuestionWhy Image width and height must be power of 2 Pin
jubayerShamshed3-Apr-16 8:03
jubayerShamshed3-Apr-16 8:03 
AnswerRe: Why Image width and height must be power of 2 Pin
Jake_Muller29-Apr-16 0:30
Jake_Muller29-Apr-16 0:30 
QuestionDifference between code and page Pin
Member 1168529429-Jan-16 6:36
Member 1168529429-Jan-16 6:36 
AnswerRe: Difference between code and page Pin
Hovhannes Bantikyan7-Aug-16 21:54
Hovhannes Bantikyan7-Aug-16 21:54 
QuestionDifference execution between Source and demo file Pin
Jake_Muller24-Jan-16 16:57
Jake_Muller24-Jan-16 16:57 
AnswerRe: Difference execution between Source and demo file Pin
Jake_Muller24-Jan-16 17:03
Jake_Muller24-Jan-16 17:03 
GeneralRe: Difference execution between Source and demo file Pin
Member 116852947-Apr-16 15:40
Member 116852947-Apr-16 15:40 
GeneralRe: Difference execution between Source and demo file Pin
Member 126130401-Aug-16 9:25
Member 126130401-Aug-16 9:25 
GeneralRe: Difference execution between Source and demo file Pin
Jake_Muller2-Aug-16 21:20
Jake_Muller2-Aug-16 21:20 
GeneralMy vote of 4 Pin
Member 122523628-Jan-16 4:16
Member 122523628-Jan-16 4:16 
Questionvb.net 2010 Pin
Member 122505627-Jan-16 9:04
Member 122505627-Jan-16 9:04 
QuestionWrong IWT formula Pin
Member 1177763021-Jun-15 23:09
Member 1177763021-Jun-15 23:09 
QuestionSAFE and UNSAFE Pin
Member 1157451611-May-15 1:33
Member 1157451611-May-15 1:33 
QuestionSAFE and UNSAFE Pin
Member 1157451611-May-15 1:33
Member 1157451611-May-15 1:33 
QuestionCan you help me ? Pin
Member 1137698417-Mar-15 9:40
Member 1137698417-Mar-15 9:40 
AnswerRe: Can you help me ? Pin
Hovhannes Bantikyan28-Mar-15 16:13
Hovhannes Bantikyan28-Mar-15 16:13 
QuestionDiscrete Haar Wavelet Transform Pin
Member 1146815326-Feb-15 17:39
Member 1146815326-Feb-15 17:39 
AnswerRe: Discrete Haar Wavelet Transform Pin
Hovhannes Bantikyan4-Mar-15 13:11
Hovhannes Bantikyan4-Mar-15 13:11 
QuestionPython version Pin
Jaime Loepz31-Oct-14 11:41
Jaime Loepz31-Oct-14 11:41 
AnswerRe: Python version Pin
Hovhannes Bantikyan8-Nov-14 7:16
Hovhannes Bantikyan8-Nov-14 7:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.