Wavelets and the Abel Prize

The Abel Prize is a Norwegian mathematics prize, awarded yearly to international mathematicians with extraordinary contributions within mathematics. Each year I try to read a bit about the winner and his work, and at least get an idea of what the winner has contributed to in his field.

This year’s winner is Yves Meyer who is awarded the price for his role in developing the mathematical theory of wavelets, a theory he accidentally came across by the photocopier at the École Polytechnique in Paris [1]. He is in Oslo now, and will receive his prize in an award ceremony tomorrow, May 23.

So what are wavelets and what can they be used for?
I’m certainly not the right person to answer, with my few hours of knowledge on the topic, but I will share what I have discovered so far.
A wavelet is, as the word indicates, a wave-like function, or rather a family of functions, with some important properties that make them useful for signal processing. They are for instance better at detecting sudden changes in the signal than Fourier transforms.

Meyer has his own wavelet as shown in the image below [2].
MeyerMathematica
The Meyer wavelet looks a bit complicated, doesn’t it? So I will stick to a much simpler wavelet, actually the very first example of a wavelet, the Haar wavelet. Haar constructed this function system in 1909 [3], long before the term Wavelet was introduced, but the system appears later as a special case of the Daubechies wavelet [4].
The wavelet is defined by the wavelet function \psi(t), called the mother wavelet, and a scaling function \phi(t), sometimes referred to the father wavelet. The mother wavelet is defined as

    \[    \psi(t) = \begin{cases}     1 & 0 \leq t < \frac{1}{2} \\     -1 & \frac{1}{2} \leq t < 1 \\     0 & \text{otherwise}   \end{cases} \]

with the scaling function

    \[  \phi(t) = \begin{cases}     1 & 0 \leq t < 1 \\     0 & \text{otherwise}  \]

If we continue to split the unit interval [0, 1] in 2^n pieces, we get a system of functions \psi_i^n(t) = 2^{\frac{n}{2}}\psi(2^n t - i) and \phi_i^n(t) = 2^{\frac{n}{2}}\phi(2^n t - i), where i \in \{ 0, \ldots, 2^n - 1\}. The functions \psi_i^n forms an orthonormal basis for square integrable functions on the unit interval. That means that functions can be approximated by a linear combinations of \psi_i^n, the same holds for the set of \phi_i^n.

The YouTube video below shows what the \psi_i^n looks like and how they are scaled and translated from the mother wavelet.

We will start by looking at the following function, the four purple line fragments, which one can think of as the four one-dimensional pixels [9, 5, 2, 4].

If we look at the father wavelets \phi_0^2, \phi_1^2, \phi_2^2 and \phi_3^2, we see that f can be written as

    \[ f = 9\phi_0^2 + 5\phi_1^2 + 2\phi_2^2 + 4\phi_3^2 \]

From the mother and the father wavelets one can construct subspaces V_n = \text{span}(\phi_i^n) and W_n = \text{span}(\psi_i^n) and we have that V_n is the orthogonal complement of W_n in V_{m+1} [2]:

    \[ V_n \oplus W_n = V_{m+1} \]

Let us see how we can represent f by a point in V_n and a point in W_n. The function is in V_2 and we want to write the function decomposed over V_1 and W_1. In V_1 and W_1 we have the functions \phi_0^1 = \sqrt{2}\phi(2t), \phi_1^1 = \sqrt{2}\phi(2t-1), \psi_0^1 = \sqrt{2}\psi(2t) and \psi_1^1 = \sqrt{2}\psi(2t-1). I skip the square root of two to get simpler calculations, and it only contributes with a constant factor anyway. We then have the following functions:

    \[    \psi_0^1(t) = \begin{cases}     1 & 0 \leq t < \frac{1}{4} \\     -1 & \frac{1}{4} \leq t < \frac{1}{2} \\     0 & \text{otherwise}   \end{cases} \]

    \[    \psi_1^1(t) = \begin{cases}     1 & \frac{1}{2} \leq t < \frac{3}{4} \\     -1 & \frac{3}{4} \leq t < 1 \\     0 & \text{otherwise}   \end{cases} \]

    \[  \phi_0^1(t) = \begin{cases}     1 & 0 \leq t < \frac{1}{2} \\     0 & \text{otherwise} \end{cases}  \]

    \[  \phi_1^1(t) = \begin{cases}     1 & \frac{1}{2} \leq t < 1 \\     0 & \text{otherwise} \end{cases}  \]

We see that \psi_0^1 and \phi_0^1 are non-zero in [0, \frac{1}{2}) and \psi_1^1 and \phi_1^1 are non-zero in [\frac{1}{2}, 1), so we want to find a and b such that

    \[ a\phi_0^1(t) + b\psi_0^1(t) = \begin{cases} a + b & 0 \leq t < \frac{1}{4} \\ a - b & \frac{1}{4} \leq t < \frac{1}{2} \end{cases} = \begin{cases} 9 &  0 \leq t < \frac{1}{4} \\ 5 & \frac{1}{4} \leq t < \frac{1}{2} \end{cases} \]

If we solve these equations we find that a = \frac{9+5}{2} and b = \frac{9-5}{2}, we get the equivalent for the pair 2 and 4, hence f decomposes into the point (\frac{9+5}{2}, \frac{2+4}{2}) in V_1 and the point (\frac{9-5}{2}, \frac{2-4}{2}) in W_1. We see that the point in V_1 is the average of pair of coefficients of f and the point of W_1 is the difference of the pair of coefficients, and we can represent f by [7, 3, 2, -1], where the two first points are the approximation coefficients of the original function (if you decide to zoom out and only keep half of the points in the unit interval, is seems quite natural to average the pair of points), and the two last points are called the detail coefficients.
The calculations for this example holds in general for 2^k points, we can approximate the original with half as many points by averaging pair of points, and the detail coefficients will give information about the difference of the pair of points. The detail coefficients can be used to go the other way and reconstruct the original point.

The same calculations can be applied to a 2-D image by first calculate average and difference for each row, and then for each column. I have written a simple Java program which does these calculations for an image, and thus transforms the image to a compressed image, together with three images of detail coefficients. The interesting part of the program is where the averages and differences are computed, the rest is just converting Java’s BufferedImage from color to gray scale, and from an Image to a matrix, and back again. The code snippet below shows how I computed the average and difference for the rows, the rest of the code can be found in the gist here.

  
private double[][] transformRows(double[][] input){
        int size = input.length;
        double[][] result = new double[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size / 2; j++) {
                result[i][j] = (input[i][2*j] + input[i][2*j + 1])/2.0;
                result[i][size/2 + j] = (input[i][2*j] - input[i][2*j + 1])/2.0;
            }
        }
        return result;
    }


Many of the pixels in an image will be very similar to their neighbouring pixels, hence many of the differences will be close to zero. The differences are largest when there are sudden changes in the image. For instance beetween the hair and the face of Lenna. Another interesting observation is that the in upper right image the vertical details are most prominent, like the nose, whereas the lower left has horizontal details like the mouth.This is because of the way we calculate average and sums, the upper right will be averaged differences of pixels in the same row, and the lower left will be averaged differences of pixels in same column.

So what can this wavelet transform be used for? One obvious application is image compression. We have got a compressed version of the original, and the detail coefficients are often zero (or a very small number). One can repeat the process, and transform the transformed image several times, and then use the detail coefficients to reconstruct the original, with or without loss [5]. Another interesting application is to use the detail coefficients as features in image recognition. In [6] it was used with logistic regression to detect facial expression, and in [7] the Haar transform was used to classify leaves.

References
[1] If it were true, it would be known – The Abel Committee explains the
choice of Yves Meyer as this year’s Abel Prize Laureate

[2] Wavelet. (2017, April 24). In Wikipedia, The Free Encyclopedia. Retrieved 16:17, May 21, 2017, from https://en.wikipedia.org/w/index.php?title=Wavelet&oldid=776912745
[3] A. Haar Zur Theorie der orthogonalen Funktionensysteme
[4] Haar wavelet. (2017, March 4). In Wikipedia, The Free Encyclopedia. Retrieved 21:24, May 21, 2017, from https://en.wikipedia.org/w/index.php?title=Haar_wavelet&oldid=768512588
[5] Colm Mucahy, Image compression using the Haar wavelet transform, pdf
[6] Mahesh Goyani and Narendra Patel, Multi-Level Haar Wavelet based Facial Expression Recognition using Logistic Regression, pdf
[7] Haiyan Zhang and Xingke Tao, Leaf Image Recognition Based on Wavelet and Fractal Dimension,
pdf

Upresis hodejeger

Jeg har nettopp begynt å lese Hodejegerne av Jo Nesbø (ja, jeg er av de få i Norge som ikke har lest denne enda).
Som matematiker måtte jeg selvfølgelig henge meg opp i side 26. Finnes det tre påfølgende oddetall som er primtall? Ja, selvfølgelig, 3, 5 og 7.

image

Påstanden i boka stemmer selvsagt for primtall større enn 3 🙂