Image Compression Using Discrete Wavelet Transform

IMAGE COMPRESSION USING DISCRETE WAVELET TRANSFORM

ABSTRACT

Our project entitled “Image Compression using Discrete Wavelet Transform”. Images require substantial storage and transmission resources, thus image compression is advantageous to reduce these requirements. This project describes some background of wavelet analysis, data compression and how wavelets have been and can be used for image compression.

Images contain large amounts of information that requires much storage space, large transmission bandwidths and long transmission times. Therefore it is advantageous to compress the image by storing only the essential information needed to reconstruct the image. An image can be thought of as a matrix of pixel (or intensity) values. In order to compress the image, redundancies must be exploited, for example, areas where there is little or no change between pixel values.

Compression is a process of converting an input data stream into another data stream that has a smaller size. Compression is possible only because data is normally represented in the computer in a format that is longer than necessary i.e. the input data has some amount of redundancy associated with it. The main objective of compression systems is to eliminate this redundancy.

The aim of image compression is to produce a compact representation of speech sounds such that when reconstructed it is perceived to be close to the original. The two main measures of closeness are intelligibility and naturalness.

This aim of the project is thresholding had an extremely important influence of compression results. So suggested thresholding strategies are given along with further lines of research that could be undertaken.

Wavelet analysis produces several important benefits, particularly for image compression. Wavelets are waveforms that occur in a very short duration that has a mean value of zero. Wavelet transform can represent non-stationary signals more effectively than Fourier transform since it retains both the time and frequency aspect of the signal. This thesis applies wavelet analysis to image compression. A mother or basis wavelet is first chosen for the compression. The signal is then decomposed to a set of scaled and translated versions of the mother wavelet.

Image Compression Steps:

The steps needed to compress an image are as follows:

Digitize the source image into a signal s, which is a string of numbers.
Decompose the signal into a sequence of wavelet coefficients w.
Use thresholding to modify the wavelet coefficients from w to another sequence w'.
Use quantization to convert w' to a sequence q.
Apply entropy coding to compress q into a sequence e.

The following implementation steps have been made for the devised algorithm, which is based on 2D-wavelet.
1. Reading an image of either gray scale or RGB image.
2. Converting the image into grayscale if the image is RGB.
3. Decomposition of images using wavelets for the level N.
4. Selecting and assigning a wavelet for compression.
5. Generating threshold coefficients using Birge-Massart strategy.
6. Performing the image compression using wavelets.
7. Computing and displaying the results such as compressed image, retained energy and Zero coefficients.
8. Decompression the image based on the wavelet decomposition structure.
9. Plotting the reconstructed image.
10. Computing and displaying the size of original image, compressed image and decompressed image.

1.Introduction

Often signals we wish to process are in the time-domain, but in order to process them more easily otherinformation, such as frequency, is required. Mathematical transforms translate the information of signalsinto different representations. For example, the Fourier transform converts a signal between the timeand frequency domains, such that the frequencies of a signal can be seen. However the Fouriertransform cannot provide information on which frequencies occur at specific times in the signal as timeand frequency are viewed independently. To solve this problem the Short Term Fourier Transform(STFT) introduced the idea of windows through which different parts of a signal are viewed. For agiven window in time the frequencies can be viewed. However Heisenburg.s Uncertainty Principlestates that as the resolution of the signal improves in the time domain, by zooming on different sections,the frequency resolution gets worse. Ideally, a method of multiresolution is needed, which allowscertain parts of the signal to be resolved well in time, and other parts to be resolved well in frequency.The power and magic of wavelet analysis is exactly this multiresolution.Images contain large amounts of information that requires much storage space, large transmissionbandwidths and long transmission times. Therefore it is advantageous to compress the image by storingonly the essential information needed to reconstruct the image. An image can be thought of as a matrixof pixel (or intensity) values. In order to compress the image, redundancies must be exploited, forexample, areas where there is little or no change between pixel values. Therefore images having largeareas of uniform colour will have large redundancies, and conversely images that have frequent andlarge changes in colour will be less redundant and harder to compress.

image after compression and decompression is known as the .energy retained. and this is proportional tothe sum of the squares of the pixel values. If the energy retained is 100% then the compression isknown as .lossless., as the image can be reconstructed exactly. This occurs when the threshold value isset to zero, meaning that the detail has not been changed. If any values are changed then energy will belost and this is known as .lossy. compression. Ideally, during compression the number of zeros and theenergy retention will be as high as possible. However, as more zeros are obtained more energy is lost, so a balance between the two needs to be found.

The first part of the report introduces the background of wavelets and compression in more detail. Thisis followed by a review of a practical investigation into how compression can be achieved with waveletsand the results obtained. The purpose of the investigation was to find the effect of the decompositionlevel, wavelet and image on the number of zeros and energy retention that could be achieved. Forreasons of time, the set of images, wavelets and levels investigated was kept small. Therefore only onefamily of wavelets, the Daubechies wavelets, was used. The images used in the investigation can be

seen in Appendix B. The final part of the report discusses image properties and thresholding, two issueswhich have been found to be of great importance in compression.

2. Background

2.1. The Need for Wavelets

Often signals we wish to process are in the time-domain, but in order to process them more easily otherinformation, such as frequency, is required. A good analogy for this idea is given by Hubbard, p14.The analogy cites the problem of multiplying two roman numerals. In order to do this calculation wewould find it easier to first translate the numerals in to our number system, and then translate the answerback into a roman numeral. The result is the same, but taking the detour into an alternative number

system made the process easier and quicker. Similarly we can take a detour into frequency space toanalysis or process a signal.

2.1.1 Fourier Transforms (FT)

Fourier transforms can be used to translate time domain signals into the frequency domain. Takinganother analogy from Hubbard[4] it acts as a mathematical prism, breaking up the time signal intofrequencies, as a prism breaks light into different colours.

Figure 2.1 The left graph shows a signal plotted in the time domain, the right graph shows the Fouriertransform of the signal.

The following equations can be used to calculate the Fourier transform of a time-domain signal and theinverse Fourier Transform [2]:

Image Compression Using Wavelets

1. Introduction

transform cannot provide information on which frequencies occur at specific times in the signal as timeand frequency are viewed independently.

To solve this problem the Short Term Fourier Transform(STFT) introduced the idea of windows through which different parts of a signal are viewed. For agiven window in time the frequencies can be viewed. However Heisenburg.s Uncertainty Principlestates that as the resolution of the signal improves in the time domain, by zooming on different sections,the frequency resolution gets worse. Ideally, a method of multiresolution is needed, which allowscertain parts of the signal to be resolved well in time, and other parts to be resolved well in frequency.

The power and magic of wavelet analysis is exactly this multiresolution.

Images contain large amounts of information that requires much storage space, large transmissionbandwidths and long transmission times. Therefore it is advantageous to compress the image by storingonly the essential information needed to reconstruct the image. An image can be thought of as a matrixof pixel (or intensity) values. In order to compress the image, redundancies must be exploited, forexample, areas where there is little or no change between pixel values.

Therefore images having largeareas of uniform colour will have large redundancies, and conversely images that have frequent andlarge changes in colour will be less redundant and harder to compress.

Wavelet analysis can be used to divide the information of an image into approximation and detailsubsignals. The approximation subsignal shows the general trend of pixel values, and three detailsubsignals show the vertical, horizontal and diagonal details or changes in the image. If these details arevery small then they can be set to zero without significantly changing the image. The value below whichdetails are considered small enough to be set to zero is known as the threshold. The greater the numberof zeros the greater the compression that can be achieved. The amount of information retained by animage after compression and decompression is known as the .energy retained. and this is proportional tothe sum of the squares of the pixel values. If the energy retained is 100% then the compression isknown as .lossless., as the image can be reconstructed exactly. This occurs when the threshold value isset to zero, meaning that the detail has not been changed. If any values are changed then energy will be

lost and this is known as .lossy. compression. Ideally, during compression the number of zeros and theenergy retention will be as high as possible. However, as more zeros are obtained more energy is lost, soa balance between the two needs to be found.

seen in Appendix B. The final part of the report discusses image properties andthresholding, two issueswhich have been found to be of great importance in compression.

2. Background

2.1. The Need for Wavelets

Often signals we wish to process are in the time-domain, but in order to process them more easily otherinformation, such as frequency, is required. A good analogy for this idea is given by Hubbard[4], p14.The analogy cites the problem of multiplying two roman numerals. In order to do this calculation wewould find it easier to first translate the numerals in to our number system, and then translate the answerback into a roman numeral. The result is the same, but taking the detour into an alternative numbersystem made the process easier and quicker. Similarly we can take a detour into frequency space toanalysis or process a signal.

2.1.1 Fourier Transforms (FT)

Figure 2.1 The left graph shows a signal plotted in the time domain, the right graph shows the Fouriertransform of the signal.

The following equations can be used to calculate the Fourier transform of a time-domain signal and theinverse Fourier Transform:

Fourier transforms are very useful at providing frequency information that cannot be seen easily in thetime domain. However they do not suit brief signals, signals that change suddenly, or in fact any nonstationarysignals. The reason is that they show only what frequencies occur, not when thesefrequencies occur, so they are not much help when both time and frequency information is requiredsimultaneously. In stationary signals, all frequency components occur at all times, so FourierTransforms are very useful. Hubbard[4] helps to make this idea clearer by using the analogy of amusician; if a musician were told what notes were played during a song, but not any information aboutwhen to play them, he would find it difficult to make sense of the information. Luckily he has the toolof a music score to help him, and in a parallel with this the mathematicians first tried to use the ShortTerm Fourier Transform (STFT), which was introduced by Gabor.

The STFT looks at a signal through a small window, using the idea that a sufficiently small section ofthe wave will be approximately a stationary wave and so Fourier analysis can be used. The window ismoved over the entire wave, providing some information about what frequencies appear at what time.

Figure 2.2 Example of a window used for STFT

The following equation can be used to compute a STFT. It is different to the FT as it is computed forparticular windows in time individually, rather than computing overall time (which can be alternativelythought of as an infinitely large window). x is the signal, and w is the window.

This is an improvement as a time domain signal can be mapped onto a function of time and frequency,providing some information about what frequencies occur when. However using windows introduces anew problem; according to Heisenberg’s Uncertainty principle it is impossible to know exactly whatfrequencies occur at what time, only a range of frequencies can be found. This means that trying to gainmore detailed frequency information causes the time information to become less specific and visa versa.Therefore when using the STFT, there has to be a sacrifice of either time or frequency information.Having a big window gives good frequency resolution but poor time resolution, small windows providebetter time information, but poorer frequency information.

2.1.2 Multiresolution and Wavelets

The power of Wavelets comes from the use of multiresolution. Rather than examining entire signalsthrough the same window, different parts of the wave are viewed through different size windows (orresolutions). High frequency parts of the signal use a small window to give good time resolution, lowfrequency parts use a big window to get good frequency information.

An important thing to note is that the ’windows’ have equal area even though the height and width mayvary in wavelet analysis. The area of the window is controlled by Heisenberg’s Uncertainty principle,as frequency resolution gets bigger the time resolution must get smaller.

Figure 2.3 The different transforms provided different resolutions of time and frequency.

In Fourier analysis a signal is broken up into sine and cosine waves of different frequencies, and iteffectively re-writes a signal in terms of different sine and cosine waves. Wavelet analysis does asimilar thing, it takes a .mother wavelet., then the signal is translated into shifted and scale versions ofthis mother wavelet.

2.1.3 The Continuous Wavelet Transform (CWT)

The continuous wavelet transform is the sum over all time of scaled and shifted versions of the motherwavelet ψ. Calculating the CWT results in many coefficients C, which are functions of scale andtranslation.

The translation, τ, is proportional to time information and the scale, s, is proportional to the inverse ofthe frequency information. To find the constituent wavelets of the signal, the coefficients should bemultiplied by the relevant version of the mother wavelet.

The scale of a wavelet simply means how stretched it is along the x-axis, larger scales are morestretched: