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.

In order to clarify the statement above we present an example of how Wavelet Analysis is used to analyze a discrete signal. Assume that you have a discrete signal given by a vector with 8 components,

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 and the *k*-th component
of *d(1)* is equal to (*k=0,1,2,3*).

In our case and .

The vectors *a(1)* and *d(1)* are called
the first level **approximation and detail
coefficients** of the wavelet decomposition, respectively. On the right we show the
graph of the first level approximation coefficients, which reveals that they represent the
original signal in a different scale and explains why they are called *approximation*
coefficients.

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 , respectively. Then,
and .

*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, and
.

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 obtain then,

.

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

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.)

- 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

The Haar Scale function and Wavelet function are named after Alfred Haar, who proposed them as generators of bases for function spaces in 1902.
The main disadvantage of these functions is that they are discontinuous and therefore not appropiate for the analysis of smooth signals. Only
after 85 years, in 1987, **Ingrid Daubechies** discovered the first continuous wavelet functions with compact support and with her discovery Wavelet
Analysis
revolutioned the signal processing world.
The Wavelet Transform constitutes a new method to decompose signals. This method represents a
more adequate approach to lessen the restriction given by **Heisenberg's uncertainty principle**, which states that it is impossible to know the exact
frequency and the exact time of occurrence of this frequency in a signal. This principle is explained in
Episode 104 as well.

We mentioned above that wavelet analysis analyses frequency components with a
resolution that matches their scale. In our case, the low frequencies are analyzed with the scaled versions of

We show below a graph that reveals some similarities between the original data and the compressed one. In general, data compression using wavelets consists in the storage of a restricted amount of detail coefficients of the wavelet decompostion. These coefficients, as their name suggest, contain the information about the details of the signal but are not important in order to recognize its "big picture" features.

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.

- Find the compressed data obtained after dropping the third level detail coefficient of the wavelet decomposition of the signal given in