Counterfeiters are producing small denomination bills by using the talent of an artist who they have kidnapped. Don and Charlie are afraid that the artist will be murdered as a liability by the criminals. The only way to find out the identity of the hostage is by running a match analysis between artistic pieces of several missing artists and the work seen in the counterfeit money. In order to do this Charlie uses Wavelet Analysis over the artists' work. We will explain below what Wavelet analysis is and how it is applied to image processing.
Wavelet analysis refers to the decomposition of finite energy signals into different frequency components by superposition of functions obtained after scaling and translating an initial function known as Mother Wavelet. Wavelet Analysis is different from other techniques in that it analyses frequency components with a resolution that matches their scale.
We show in the figure on the right a graphic representation of
these data. Let's call X(i) the i-th component
of the vector X (i=0,1,2,...,7). In the first
step of the Wavelet decomposition of this signal we split our information into
two vectors of 4 components, say a(1), d(1). The k-th component
of a(1) is equal to In our case In the next step we follow the
exact same procedure over the vector a(1) splitting it
into two vectors of 2 components, a(2) and
d(2), corresponding to the sums and
differences of consecutive terms divided by a(2) and d(2) are called
the second level approximation and detail coefficients of the decomposition,
respectively. Finally for the third and last step we follow the same procedure
over the vector a(2), and we obtain two one-dimensional
vectors a(3) and d(3) (the third level approximation and detail coefficients,
respectively) where, One of the nice features of the
wavelet decomposition is that the reconstruction algorithm is very similar to
the decomposition one. Let's assume that we have the approximation coefficient
of the third level a(3) and the decomposition coefficients
corresponding to all the levels, d(3),d(2),d(1).
In order to get a(2) from this information we take sums
and differences of the components of a(3)
and d(3) divided by
We proceed analogously with a(2) and d(2) in order to obtain the first level approximation coefficients,
Finally the same calculations
over a(1) and d(1) reconstruct the original information,
In order to understand the
reasoning behind the calculations above it is convenient to see them from a
"continuous" point of view. Let's call h
the function that takes the value 1 on the interval [0,1)
and 0 otherwise, and g the function that
takes the value 1 on [0,0.5), -1 on [0.5,1), and 0 otherwise.
We can represent the signal X as a combination of translations of the function h as follows,
The key formulas behind the
wavelet decomposition and reconstruction algorithms are the ones given by the representation of h and g
as a combination of translations of
versions of h and g in a different scale. More precisely,
We adopt the following notation,
Under this notation we observe, by using the formulas above, that the first level approximation and detail coefficients of the
decomposition correspond to the coeficcientes in the
decomposition of X in terms of the scaled functions h-1,k and g-1,k as shown below,
An analogous argument shows that the second level approximation and detail coefficients correspond to the coefficients in the
decomposition of the signal generated by the first level approximation coefficients, in terms of translations of scaled versions of
h and g given by
In the signal processing terminology, we say that the functions above for i big analyze the small scales that correspond
to the high frequencies of the signal (sudden changes in a short period of time) and the scaled functions for i small analyze
the big scale features of the
signal that correspond to the low frequencies, which give the signal its overall shape. This frequency analysis is local since each approximation and
detail coefficient is calculated by using only part of the data and then it is adequate to study non-stationary signals
(signals that do not repeat into infinity with the same periodicity.)
We can think of an image as a rectangular array of numbers, where each number represents the intensity
at the corresponding
pixel.
The easiest way of generalizing the procedure explained before to the two dimensional case
is by running the wavelet decomposition first over the rows of the image and then over its columns. Image compression again corresponds
to the storage of the approximation coefficients and some of the detail coefficients.
This procedure has been found to be very useful and has numerous applications.
Perhaps the best-known application of wavelet analysis is used by the FBI, which since 1993 uses a wavelet
transform to compress digitalized fingerprint records (See figure below).
Image compression is not the only application of Wavelet Analysis. Since the analysis of the frequencies is done in a local manner
there exist many applications
of the wavelet transform to other image processing problems such as image restoration and edge detection. In edge detection edges of an image correspond to the ocurrence
of high frequencies in small portions of the signal, or equivalently to big detail coefficients in small scales.
Matlab's wavelet toolbox contains a comprehensive
collection of routines to analyze data.
All these nice features of the Wavelet transform
helped Charlie to recognize similarities, in edges and scales of grey among others, between the artist's work and the one seen in the counterfeit money.
Calculate the approximation and detail coefficients of the wavelet decomposition of the following signal,
Verify that the original signal can be recovered from your data by using the reconstruction algorithm described above
.
Data compression and Image Processing
Assume that after the wavelet decomposition described above we only keep the third level approximation coefficient and the first and second level
detail coefficients, or equivalently we drop the value of d(3). This represents a compression of data because we have to store only
seven numbers instead of the initial eight.
By assuming that d(3)=0 and following the reconstruction algorithm as described above we obtain the new
approximation coefficients and compressed signal given by
Image Processing
Find the compressed data obtained after dropping the third level detail coefficient of the wavelet decomposition of the signal given in Activity 1, and
draw a graph of your results.