please send me full report

[attachment=8837]
Image Compression Using Wavelets
Abstract
Images require substantial storage and transmission resources, thus image compression is advantageous
to reduce these requirements. The report covers some background of wavelet analysis, data compression
and how wavelets have been and can be used for image compression. An investigation into the process
and problems involved with image compression was made and the results of this investigation are
discussed. It was discovered that thresholding was had an extremely important influence of
compression results so suggested thresholding strategies are given along with further lines of research
that could be undertaken.
1. Introduction
Often signals we wish to process are in the time-domain, but in order to process them more easily other
information, such as frequency, is required. Mathematical transforms translate the information of signals
into different representations. For example, the Fourier transform converts a signal between the time
and frequency domains, such that the frequencies of a signal can be seen. However the Fourier
transform cannot provide information on which frequencies occur at specific times in the signal as time
and 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 a
given window in time the frequencies can be viewed. However Heisenburg.s Uncertainty Principle
states 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 allows
certain 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 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. Therefore images having large
areas of uniform colour will have large redundancies, and conversely images that have frequent and
large 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 detail
subsignals. The approximation subsignal shows the general trend of pixel values, and three detail
subsignals show the vertical, horizontal and diagonal details or changes in the image. If these details are
very small then they can be set to zero without significantly changing the image. The value below which
details are considered small enough to be set to zero is known as the threshold. The greater the number
of zeros the greater the compression that can be achieved. The amount of information retained by an
image after compression and decompression is known as the .energy retained. and this is proportional to
the sum of the squares of the pixel values. If the energy retained is 100% then the compression is
known as .lossless., as the image can be reconstructed exactly. This occurs when the threshold value is
set 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 the
energy 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. This
is followed by a review of a practical investigation into how compression can be achieved with wavelets
and the results obtained. The purpose of the investigation was to find the effect of the decomposition
level, wavelet and image on the number of zeros and energy retention that could be achieved. For
reasons of time, the set of images, wavelets and levels investigated was kept small. Therefore only one
family 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 issues
which have been found to be of great importance in compression.
x is the original signal
t is time
f is frequency
X is the Fourier transform.
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 other
information, 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 we
would find it easier to first translate the numerals in to our number system, and then translate the answer
back 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 to
analysis or process a signal.
2.1.1 Fourier Transforms (FT)
Fourier transforms can be used to translate time domain signals into the frequency domain. Taking
another analogy from Hubbard[4] it acts as a mathematical prism, breaking up the time signal into
frequencies, as a prism breaks light into different colours.
Fourier transforms are very useful at providing frequency information that cannot be seen easily in the
time domain. However they do not suit brief signals, signals that change suddenly, or in fact any nonstationary
signals. The reason is that they show only what frequencies occur, not when these
frequencies occur, so they are not much help when both time and frequency information is required
simultaneously. In stationary signals, all frequency components occur at all times, so Fourier
Transforms are very useful. Hubbard[4] helps to make this idea clearer by using the analogy of a
musician; if a musician were told what notes were played during a song, but not any information about
when to play them, he would find it difficult to make sense of the information. Luckily he has the tool
of a music score to help him, and in a parallel with this the mathematicians first tried to use the Short
Term 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 of
the wave will be approximately a stationary wave and so Fourier analysis can be used. The window is
moved over the entire wave, providing some information about what frequencies appear at what time.
The following equation can be used to compute a STFT. It is different to the FT as it is computed for
particular windows in time individually, rather than computing overall time (which can be alternatively
thought of as an infinitely large window). x is the signal, and w is the window.
STFT w t f ∫x t w t −t e−j ft t
x ( , ) [ ( ). *( ’)]. 2 [2]
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 a
new problem; according to Heisenberg’s Uncertainty principle it is impossible to know exactly what
frequencies occur at what time, only a range of frequencies can be found. This means that trying to gain
more 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 provide
better 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 signals
through the same window, different parts of the wave are viewed through different size windows (or
resolutions). High frequency parts of the signal use a small window to give good time resolution, low
frequency 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 may
vary 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.