9
$\begingroup$

I want to perform 2D haar discrete wavelet transform and inverse DWT on an image.Will you please explain 2D haar discrete wavelet transform and inverse DWT in a simple language and an algorithm using which I can write the code for 2D haar dwt?The information given in google was too technical.I understood the basic things like dividing the image into 4 sub-bands:LL,LH,HL,HH but I can't really understand how to write a program to perform DWT and IDWT on an image.I also read that DWT is better than DCT as it is performed on the image as a whole and then there was some explanation which went over the top of my head.I might be wrong here but I think DWT and DCT compression techniques because the image size reduces when DWT or DCT is performed on them.Hoping you guys share a part of your knowledge and enhance my knowledge.

Thank You

Re: Does it have anything to do with the image format.What is "value of pixel" that is used in DWT?I have assumed it to be the rgb value of the image.

import java.awt.event.*;
import javax.swing.*;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;
import java.io.*;
import javax.swing.JFileChooser;
import javax.swing.filechooser.FileFilter;
import javax.swing.filechooser.FileNameExtensionFilter;
import javax.imageio.ImageIO;
import java.awt.*;
import java.lang.*;
import java.util.*;

class DiscreteWaveletTransform

{

    public static void main(String arg[])
    { DiscreteWaveletTransform dwt=new DiscreteWaveletTransform();
      dwt.initial();
    }


    static final int TYPE=BufferedImage.TYPE_INT_RGB;
    public void initial()
    {
    try{

        BufferedImage buf=ImageIO.read(new File("lena.bmp"));
        int w=buf.getWidth();
        int h=buf.getHeight();
        BufferedImage dwtimage=new BufferedImage(h,w,TYPE);
        int[][] pixel=new int[h][w];
        for (int x=0;x<h;x++)
        {
            for(int y=0;y<w;y++)
            {
                pixel[x][y]=buf.getRGB(x,y);


            }
        }
        int[][] mat =  new int[h][w];
        int[][] mat2 =  new int[h][w];

        for(int a=0;a<h;a++)
        {
            for(int b=0,c=0;b<w;b+=2,c++)
            {
                mat[a][c]    = (pixel[a][b]+pixel[a][b+1])/2;
                mat[a][c+(w/2)]  = Math.abs(pixel[a][b]-pixel[a][b+1]);
            }
        }
        for(int p=0;p<w;p++)
        {
            for(int q=0,r =0 ;q<h;q+=2)
            {
                mat2[r][p]   = (mat[q][p]+mat[q+1][p])/2;
                mat2[r+(h/2)][p] = Math.abs(mat[q][p]-mat[q+1][p]);
            }
        }
        for (int x=0;x<h;x++)
        {
            for(int y=0;y<w;y++)
            {
                dwtimage.setRGB(x,y,mat2[x][y]);
            }
        }
        String format="bmp";
        ImageIO.write(dwtimage,format, new File("DWTIMAGE.bmp"));
        }

        catch(Exception e)
        {
            e.printStackTrace();
        }
    }
}

The output is a black image with a thin line in between,in short nowhere near the actual output.I think I have interpreted the logic wrongly.Please point out the mistakes. Regards

$\endgroup$
  • 1
    $\begingroup$ You may find how to apply Discrete wavelet transform on image useful. $\endgroup$ – Max Apr 22 '12 at 23:45
  • $\begingroup$ The above code means a lot to me thanks .. can you please provide me the java code for the inverse of 2D haar transform $\endgroup$ – user8124 Mar 4 '14 at 16:36
15
$\begingroup$

Will you please explain 2D haar discrete wavelet transform and inverse DWT in a simple language

It is useful to think of the wavelet transform in terms of the Discrete Fourier Transform (for a number of reasons, please see below). In the Fourier Transform, you decompose a signal into a series of orthogonal trigonometric functions (cos and sin). It is essential for them to be orthogonal so that it is possible to decompose your signals in a series of coefficients (of two functions that are essentially INDEPENDENT of each other) and recompose it back again.

With this criterion of orthogonality in mind, is it possible to find two other functions that are orthogonal besides the cos and sin?

Yes, it is possible to come up with such functions with the additional useful characteristic that they do not extend to infinity (like the cos and the sin do). One example of such pair of functions is the Haar Wavelet.

Now, in terms of DSP, it is perhaps more practical to think about these two "orthogonal functions" as two Finite Impulse Response (FIR) filters and the Discrete Wavelet Transform as a series of Convolutions (or in other words, applying these filters successively over some time series). You can verify this by comparing and contrasting the formulas of the 1-D DWT and that of convolution.

In fact, if you notice the Haar functions closely you will see the two most elementary low pass and high pass filters. Here is a very simple low pass filter h=[0.5,0.5] (don't worry about the scaling for the moment) also known as a moving average filter because it essentially returns the average of every two adjacent samples. Here is a very simple high pass filter h=[1, -1] also known as a differentiator because it returns the difference between any two adjacent samples.

To perform DWT-IDWT on an image, it is simply a case of using the two dimensional versions of convolution (to apply your Haar filters successively).

Perhaps now you can begin to see where the LowLow,LowHigh,HighLow,HighHigh parts of an image that has undergone DWT come from. HOWEVER, please note that an image is already TWO DIMENSIONAL (maybe this is confusing some times). In other words, you must derive the Low-High Spatial frequencies for the X axis and the same ranges for the Y axis (this is why there are two Lows and two Highs per axis)

and an algorithm using which I can write the code for 2D haar dwt?

You must really give it a try to code this on your own from first principles so that you get an understanding of the whole process. It is very easy to find a ready made piece of code that will do what you are looking for but i am not sure that this would really help you in the long term.

I might be wrong here but I think DWT and DCT compression techniques because the image size reduces when DWT or DCT is performed on them

This is where it really "pays" to think of the DWT in terms of the Fourier Transform. For the following reason:

In the Fourier Transform (and of course the DCT as well), you transform MANY SAMPLES (in the time domain) to ONE (complex) coefficient (in the frequency domain). This is because, you construct different sinusoids and cosinusoids and then you multiply them with your signal and obtain the average of that product. So, you know that a single coefficient Ak represents a scaled version of a sinusoid of some frequency (k) in your signal.

Now, if you look at some of the wavelet functions you will notice that they are a bit more complex than the simple sinusoids. For example, consider the Fourier Transform of the High Pass Haar Filter...The high pass Haar filter looks like a square wave, i.e. it has sharp edges (sharp transitions)...What does it take to create SHARP EDGES?.....Many, many different sinusoids and co-sinusoids (!)

Therefore, representing your signal / image using wavelets saves you more space than representing it with the sinusoids of a DCT because ONE set of wavelet coefficients represents MORE DCT COEFFICIENTS. (A slightly more advanced but related topic that might be of help to you to understand why this works this way is Matched Filtering).

Two good online links (in my opinion at least :-) ) are: http://faculty.gvsu.edu/aboufade/web/wavelets/tutorials.htm and; http://disp.ee.ntu.edu.tw/tutorial/WaveletTutorial.pdf

Personally, i have found very helpful, the following books: http://www.amazon.com/A-Wavelet-Tour-Signal-Processing/dp/0124666051 (By Mallat) and; http://www.amazon.com/Wavelets-Filter-Banks-Gilbert-Strang/dp/0961408871/ref=pd_sim_sbs_b_3 (By Gilbert Strang)

Both of these are absolutely brilliant books on the subject.

I hope this helps

(sorry, i just noticed that this answer may be running a bit too long :-/ )

$\endgroup$
  • $\begingroup$ I am ecstatic that you replied.Thank you for replying A_A.Based on the mathematical interpretation of DWT which I found in an IEEE paper I have written a code.However all I get is a black image,please help me out. $\endgroup$ – user1320483 Apr 23 '12 at 10:30
  • $\begingroup$ Writing the code to perform DWT really means a lot to me.(Please)^∞.I will be really grateful.I have posted the code above. $\endgroup$ – user1320483 Apr 23 '12 at 10:35
  • $\begingroup$ There are two things to note in your code a) Please review the two dimensional version of convolution (it doesn't get any simpler than that in this case) and b) Please note that your "image" is a set of coefficients that might be very small or very large and in any case outside the common dynamic range of 255 colours. Therefore, you need to find the range of your coefficients and scale it to the interval 0,255. Are you only going for one level of decomposition? $\endgroup$ – A_A Apr 23 '12 at 10:57
  • $\begingroup$ a) Please review the two dimensional version of convolution (it doesn't get any simpler than that in this case) I am not sure what you mean by this. "image" is a set of coefficients that might be very small or very large and in any case outside the common dynamic range of 255 colours This means that after adding I have to check whether the value exceeds 255 and if it start from 0? Are you only going for one level of decomposition? Yes Thank You very much $\endgroup$ – user1320483 Apr 23 '12 at 11:43
  • $\begingroup$ What i mean by (a) is that if you want to apply the Haar filters (as per the answer given above) you will have to review how is this done through the operation of convolution and in the case of the Haar filters this is very simple. Yes you need to normalise your coefficients to the range 0-255 to be able to "see" them. As far as RGB is concerned, please focus on grayscale images (just one value). You need to understand first what it is that you need to do and then do it. Looking for "the code" is going to be more time consuming in the long run. $\endgroup$ – A_A Apr 23 '12 at 12:33
8
$\begingroup$

I started writing this before the answer from @A_A, but that answer is excellent. Still I hope the following might add a little to your understanding.

The discussion about wavelets and so on falls into the general discussion about basis decomposition of signals. By this, we mean that we can represent our signal $\mathbf{x}$ as the product of some basis matrix, $\text{H}$, and the vector representing our signal in the alternative basis (the basis decomposition), $\tilde{\mathbf{x}}$. That is: $$ \mathbf{x} = \text{H}\tilde{\mathbf{x}} $$ The basis matrix $\text{H}$ is typically an orthonormal matrix (e.g. the discrete Fourier matrix, Haar wavelet matrix), but need not be - there are whole fields of research looking at decomposing signals into over-complete dictionaries, meaning an $\text{H}$ wider than it is tall (e.g. through minimum L1-norm algorithms).

The idea behind basis decomposition of signal is that the signal can be represent in some better way in an alternative basis. By better, we mean that the signal is somehow more amenable to processing, or understanding, or whatever - it doesn't really matter.

A point to note is that, particularly with orthonormal transforms, your signal is still your signal whatever basis it is in. You shouldn't think of one basis as somehow being the correct domain (I use domain to mean basis in the general sense).

Now, different bases have different properties. I'm sure you're well aware of the convolution theorem describing the useful relationship between the Fourier domain and the time domain. This makes the Fourier domain useful for performing time domain convolution operations.

In general the time (or pixel) domain can be considered as having excellent time (or spatial) resolution and bad frequency resolution. Conversely, the Fourier domain can be considered as having excellent frequency resolution and bad time (or spatial) resolution.

The wavelet bases fit somewhere in the middle of the above two. They tend to have good frequency resolution and good time or spatial resolution. One property of the wavelet transform is the good sparsification of natural images. By this, I mean the energy from the image is compressed into a few large coefficients, and many small coefficients. This means most of the salient information of the signal is represented by a relatively small set of values. This is the essence of compression.

Different wavelets have different properties. In addition to the references from @A_A, I also recommend this IEEE tutorial on the DTCWT. The focus of the tutorial is not on the wavelet transform per se, but the reason I recommend it is because of the fantastic insight it presents on the problems associated the DWT and how they might be alleviated (i'd say it requires a basic understanding first though). It really ties together an understanding of wavelets with an understanding of the Fourier transform and why the latter has the nice properties it does.

If you'd like some more reference code on the Haar transform, my former supervisor has some matlab examples on his web page (the zip file under "4F8 Image Coding Course", HAAR2D.M and IHAAR2D.M). These are very much teaching examples though.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.