Chapter 15
Wavelets
15.1 Waves and Wavelets
We have seen in Chapters 7 and 14 that the discrete Fourier transform and its cousin, the
discrete cosine transform, are of enormous use in image processing and image compression.
But as we saw with the Fourier transform, this power does not come without cost. In
particular, as the Fourier transform is based on the idea of an image being decomposed into
periodic sine or cosine functi ons, we have to assume some sort of periodicity in the image
to make the theory fit the practice. This periodicity was obtained by assuming that the
image “bent round” to meet itself at the top and bottom, and at the left and right sides.
But this means that we have introduced unnecessary discontinuities in the image, and these
may affect the transform and our use of it.
The idea of wavelets is to keep the wave idea, but drop the periodicity. So we may
consider a wavelet to be a little part of a wave: a wave which is only non-zero in a small
region. Figure 15.1 illustrates the idea. Figure 15.1(a) is just the graph of
y = sin(x)
for − 10 ≤ x ≤ 10, and Figure 15.1(b) is the graph of a scaled version of
y = (1 − x
2
)e
−x
2
/2
over the same interval. This second function, in the more general form
y =
2
√
3σπ
1/4
1 −
x
2
σ
2
e
−x
2
/(2σ
2
)
is known as the Mexican hat wavelet.
Suppose we are given a wavelet. What can we do with it? Well, if
f = w(x)
is the function that defines our wavelet, we can:
Dilate it by applying a scaling factor to x: f(2x) would “squash” the wavelet; f(x/2)
would expand it
Translate it by adding or subtracting an appropriate value from x: f(x − 2) would shift
the wavelet 2 to the right; f(x + 3) would shift the wavelet 3 to the left
Change its height by simply multiplying the function by a constant.
Of course, we can do any or all at once:
6f(x/2 − 3),
1
3
f(16x + 17), f (x/128 − 33.5), . . .
431
432 A Computational Introduction to Digital Image Processing, Second Edition
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
(a) A wave
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
(b) A wavelet
FIGURE 15.1: Comparing a wave and a wavelet
Let
w(x) = sin(x)e
−x
2
be the function shown in Figure 15.1(b). Figure 15.2 shows some dilations and shifts of this
wavelet.
Given our knowledge of the working of the Fourier transform, it should come as no
surprise that given a suitable starting wavelet w( x ) , we can express any function f(x) as a
sum of wavelets of the form
aw(bx + c)
Moving into two dimensions, we can apply wavelets to images in the same way we applied
sine and cosines with the Fourier transform.
Using wavelets has provided a new class of very powerful image processing algorithms:
wavelets can be used for noise reduction, edge detection, and compression. The use of
wavelets has superseded the use of the DCT for image compression in the JPEG2000 image
compression algorithm.
A possible problem with wavelets is that the theory, which has been very well researched,
can be approached from many different directions. There is thus no “natural” method of
presenting wavelets: it depends on your background, and on the use to which they will be
put. Also, much writing on wavelets tends to dive into the theory very quickly. In this
chapter, though, we shall just look at the very simplest examples of the use of wavelets and
their application to images.
A Simple Wavelet Transform
To obtain a feeling for how a wavelet transform works and behaves, we shall look at
a very simple example. All wavelet transforms work by taking weighted averages of input
values and providing any other necessary information to be able to recover the original
input.
For our example, we shall perform just two operations: adding two values and subtract-
ing. For example, suppose we are given two numbers 14 and 22. Their sum and difference
are
14 + 22 = 36
14 −22 = −8
Wavelets 433
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
w(x + 5)
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
w(x − 6)
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
w(x/4)
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
w(3x/2)
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
w(x/3 − 1)
-10 -8 -6 -4 -2 0 2 4 6 8 10
-0.5
-0.4
-0.3
-0.2
-0.1
0
0.1
0.2
0.3
0.4
0.5
w(1.5x + 11)
FIGURE 15.2: Shifts and dilations of the wavelet w(x)
434 A Computational Introduction to Digital Image Processing, Second Edition
To recover the original two values from the sum and difference, we take the sum and
difference again, and divide by two:
(36 −(−8))/2 = 22
(36 + (−8))/2 = 14
In general, if a and b are our two numbers, we have their sum and difference
s = a + b
d = a − b
from which the two original numbers can be recovered with
a = (s + d)/2
b = (s − d)/2
The forward operations (adding, subtracting) and the backward operations (adding and
dividing by two, subtracting and dividing by two) differ only in the extra division. This
function can be extended to any vector with an even number of elements. For example,
suppose
v = [71, 67, 24, 26, 36, 32, 14, 18].
Then define s to be the sum of the elements in pairs:
s = [71 + 67, 24 + 26, 36 + 32, 14 + 18]
= [138, 50, 68, 32]
and d to be the difference of pairs:
d = [71 − 67, 24 − 26, 36 − 32, 14 − 18]
= [4, −2, 4, −4].
The concatenation of these two vectors:
W = [138, 50, 68, 32, 4, −2, 4, −4]
is the discrete wavelet transform at 1 scale of the original vector.
Recall that in general adding values (such as when using an averaging filter) produces
a low pass, blurred output. Conversely, subtracting (such as when using an edge detection
filter) produces a high pass output. In general, a wavelet transform will produce a mixture
of low and high pass results. These can be separated or combined.
The preceding operation on the vector v could have been performed by a matrix product:
138
50
68
32
4
−2
4
−4
=
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
1 −1 0 0 0 0 0 0
0 0 1 −1 0 0 0 0
0 0 0 0 1 −1 0 0
0 0 0 0 0 0 1 −1
71
67
24
26
36
32
14
18
Wavelets 435
We can continue by performing this same adding and differencing of the first four el-
ements of the result; this will involve the concatenation of two vectors of two elements
each:
s
1
= [138 + 50, 68 + 32]
= [188, 100]
d
1
= [138 − 50, 68 −32]
= [88, 36]
Replacing the first four elements of w above with this new s
1
and d
1
produces
W
2
= [188, 100, 88, 36, 4, −2, 4, −4]
which is the discrete wavelet transform at 2 scales of the original vector. We can go one
more step, replacing the first two elements of w
2
with their sum and difference:
W
3
= [188 + 100, 188 −100, 88, 36, 4, − 2, 4, −4]
= [288, 88, 88, 36, 4, −2, 4, −4]
and this is the discrete wavelet transform at 3 scales of the original vector.
To recover the original vector, we simply add and subtract, dividing by two each time;
first using only the first two elements, then the first four, and finally the lot:
288 + 88
2
,
288 −88
2
, 88, 36, 4, −2, 4, −4
= [188, 100, 88, 36, 4, −2, 4, −4]
[188, 100] + [88, 36]
2
,
[188, 100] − [88, 36]
2
, 4, −2, 4, −4
= [138, 50, 68, 32, 4, −2, 4, −4]
[138, 50, 68, 32] + [4, −2, 4, −4]
2
,
[138, 50, 68, 32] − [4, −2, 4, −4]
2
= [71, 67, 24, 26, 36, 32, 14, 18]
At each stage, the sums produce a “lower resolution” version of the original vector.
Wavelet transforms produce a mix of lower resolutions of the input, and the extra informa-
tion required for inversion.
We notice that the differences may be small if the input values are close together. This
leads to an idea for compression: we apply a threshold by setting to zero all values in the
transform that are less than a predetermined value. Suppose we take a threshold of 0, thus
removing all negative values, so that after thresholding W
3
becomes:
W
3
= [288, 88, 88, 36, 4, 0, 4, 0]
If we now use this as the starting place for our adding and subtracting, we end up with
v
= [71, 67, 25, 25, 36, 32, 16, 16].
Notice how close this is to the original vector, in spite of the loss of some information from
the transf orm.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.