Numb3rs 107: Counterfeit Reality

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.

What is Wavelet Analysis?

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

Activity 1:
    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 h and g, and the main feature of these functions is that their support (i.e. the interval where they are not 0) get's larger as i gets smaller (see figures above). This adaptative feature is what differentiates wavelet analysis from other techniques like Fourier Analysis where the functions used to analyze different frequencies have fixed support. The scheme presented in this example corresponds to what is called the Haar Discrete Wavelet Transform, which is closely related to the Haar Multiresolution Analysis; and the functions h and g are called the Haar Scale and Mother Wavelet functions, respectively. We refer the reader to "An introduction to wavelets" by Amara Graps and "A wavelet tour of signal processing" by Stephane Mallat to find out more about Fourier Analysis, Multiresolution Analysis and Discrete Wavelet Transforms. We also recommend the introductory exposition of Yves Nievergelt in the book titled "Wavelets Made Easy". Now we present an example that shows how wavelet analysis is used in data compression and explain how wavelet analysis is used to image processing.

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

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.

Image Processing

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.

Activity 2:
    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.