436 A Computational Introduction to Digital Image Processing, Second Edition
15.2 A Simple Wavelet: The Haar Wavelet
The Haar wavelet has been around for a long time, and has been used with images as
the Haar transform. Only recently has the Haar transf orm been viewed as a simple wavelet
transform. In fact, the Haar wavelet is the simplest possible wavelet, and for that reason is
a good starting place.
The Haar wavelet is defined by the function
ψ(x) =
1 if 0 < x < 1/2
−1 if 1/2 ≤ x < 1
0 otherwise
and is shown in Figure 15.3. As with our wavelet function w(x), we can compress and
ψ(x) φ(x)
FIGURE 15.3: The Haar wavelet and pulse function
expand this wavelet horizontally or vertically, and shift it.
Applying the Haar Wavelet
Given the Haar wavelet, what do we do with it? That is, how do we use the Haar wavelet
in a wavelet transform? We haven’t yet defined what a wavelet transform is, or what it
might look like. Without going into too many details, a wavelet transform can be defined
in much the same way as the DFT or the DCT: as a sum of function values multiplied
by wavelet values. In comparison, for the DFT we multiplied function values by complex
exponentials, and in the DCT we multiplied our function values by cosines.
The discrete wavelet transform (DWT) can be written [13] as a sum of input values
multiplied by the values from a particular class of functions. And as with the Fourier
transform, the discrete wavelet transform can be written as a matrix multiplication. We
shall show how this is done.
Notice that the Haar wavelet can be written in terms of the simpler pulse function:
φ(x) =
1 if 0 ≤ x < 1
0 otherwise
using the relation
ψ(x) = φ(2x) − φ(2x −1). (15.1)
We can see that this is true by noting that φ ( 2x) is equal to 1 for 0 ≤ x ≤ 1/2, and that
φ(2x −1) is equal to 1 for 1/2 ≤ x < 1.
Wavelets 437
The pulse function also satisfies the equation
φ
x
2
= φ(x) − φ(x − 1). (15.2)
In the theory of wavelets, the “starting wavelet,” in this case our function ψ(x), is called
the mother wavelet, and the corresponding f unction φ(x) is called the scaling function (and
sometimes calle d a father wavelet).
We can also write our scaling expression 15.2 as
φ(x) = φ(2x) + φ(2x −1). (15.3)
Equations 15.2 and 15.3 are important because they tell us how the wavelets are rescaled
at diffe rent resolutions. Equation 15.3 is a very important equation: it is called the dilation
equation, as it relates the scaling function to dilated versions of itself. Generalizations of
this equation, as we shall see below, have led to other wavelets than the Haar wavelet.
Equation 15.1 is the wavelet equation for the Haar wavelet. Note that the dilation and
wavelet equations have the same right-hand side, except for a change of sign. These can be
generalized to produce
φ(x) = ··· + h
−2
φ(2x + 2) + h
−1
φ(2x + 1) + h
0
φ(2x) + h
1
φ(2x −1)
+ h
2
φ(2x −2) + h
3
φ(2x −3) + ··· (15.4)
ψ(x) = ··· − h
−2
φ(2x −3) + h
−1
φ(2x −2) − h
0
φ(2x −1) + h
1
φ(2x)
− h
2
φ(2x + 1) + h
3
φ(2x + 2) − ··· (15.5)
where the values h
i
are called the filter coefficients or the taps of the wavelet. A wavelet is
completely specified by its taps.
We thus have, for the Haar wavelet:
φ(x) = h
0
φ(2x) + h
1
φ(2x −1) (15.6)
ψ(x) = h
1
φ(2x) − h
0
φ(2x −1) (15.7)
where h
0
= h
1
= 1. It is actually these h
i
values that we use in a calculation of the DWT.
We can put them into a DWT matrix:
H
2
n
=
1 1 0 0 0 0 ··· 0 0 0 0
0 0 1 1 0 0 ··· 0 0 0 0
0 0 0 0 1 1 ··· 0 0 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0 0 0 0 ··· 1 1 0 0
0 0 0 0 0 0 ··· 0 0 1 1
1 −1 0 0 0 0 ··· 0 0 0 0
0 0 1 −1 0 0 ··· 0 0 0 0
0 0 0 0 1 −1 ··· 0 0 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0 0 0 0 ··· 1 −1 0 0
0 0 0 0 0 0 ··· 0 0 1 −1
If v is the vector we investigated earlier, then vH
8
= d
1
. We can obtain d
2
and d
3
by
multiplying the first values of the vector by the appropriately sized H matrix.
438 A Computational Introduction to Digital Image Processing, Second Edition
If we compare the results W
2
and W
3
, the transforms at 2 and 3 scales, respectively,
with the input, we find that the matrices corresponding to these transforms are:
H
8
,2
=
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
1 1 −1 −1 0 0 0 0
0 0 0 0 1 1 −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
and
H
8,3
=
1 1 1 1 1 1 1 1
0 0 0 0 −1 −1 −1 −1
1 1 −1 −1 0 0 0 0
0 0 0 0 1 1 −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
In order to enter such matrices easily, a useful operation is the Kronecker product of
matrices, denoted A ⊗ B and which is defined as the b lock matrix for which the block at
position (i, j) is a
ij
B. For example:
2 3
−1 4
⊗
−2 5
1 2
=
2
−2 5
1 2
3
−2 5
1 2
(−1)
−2 5
1 2
4
−2 5
1 2
=
−4 10 −6 15
2 4 3 6
2 −5 −8 20
−1 2 4 8
With this new product, the matrix H can be defined as
H
2
n
=
I
2
n−1
⊗ [1 1]
I
2
n−1
⊗ [1 − 1]
In MATLAB and Octave, the Kronecker product is implemented with
kron:
MATLAB/Octave
>> v = [71 67 24 26 36 32 14 18];
>> H = [kron(eye(4),[1 1]); kron(eye(4),[1 -1])];
>> w = (H
*
v’)’
w =
138 50 68 32 4 -2 4 -4
and in Python by np.kron:
Python
In: from numpy import kron, array, eye, vstack
In : v = array([71, 67, 24, 26, 36, 32, 14, 18])
In : H = vstack([kron(eye(4),[1,1]),kron(eye(4),[1,-1])])
In : w = (H.dot(v.T)).T
In : print w
[ 138. 50. 68. 32. 4. -2. 4. -4.]
Wavelets 439
Given
H
1
=
1 1
1 −1
as the DWT matrix for 2 variables at 1 scale, a sequence of matrices can be created as:
H
n+1
=
H
n
⊗ [1 1]
I
2
n
⊗ [1 − 1]
Then H
n
is the matrix for a DWT of 2
n
variables at n scales—the maximum number of
scales possible.
Although we have spoken of the DWT formed by adding and subtracting as using the
Haar wavelet, this is not precisely true. In order to be a wavelet proper, the DWT matrices
must be orthogonal ; that is
HH
T
= I.
and the H matrices constructed so far are not quite; f or example, consider the 4 ×4 2-scale
matrix H. Then:
HH
T
=
1 1 1 1
1 1 −1 −1
1 −1 0 0
0 0 1 −1
1 1 1 0
1 1 −1 0
1 −1 0 1
1 −1 0 −1
=
4 0 0 0
0 4 0 0
0 0 2 0
0 0 0 2
.
In order to make H orthogonal, each row must be divided by the square root of the diagonal
elements in this last matrix:
H
=
1
/2
1
/2
1
/2
1
/2
1
/2
1
/2 −
1
/2 −
1
/2
1
/
√
2
−
1
/
√
2
0 0
0 0
1
/
√
2 −
1
/
√
2
As an example, here is the 3-scale DWT using the Haar wavelet applied to the original
vector. In MATLAB or Octave:
MATLAB/Octave
>> H = [1 1;1 -1];
>> for i = 1:2, H = [kron(H,[1 1]);kron(eye(size(H)),[1,-1])]; end
So far this produces the 8 ×8 matrix for a 3-scale transform. Now we must divide the rows
by the square roots of the diagonal elements of HH
T
:
MATLAB/Octave
>> D = diag(diag(H
*
H’))
>> H = sqrt(inv(D))
*
H
>> format bank
>> w = (H
*
v’)
w =
101.82 31.11 44.00 18.00 2.83 -1.41 2.83 -2.83
And in Python:
440 A Computational Introduction to Digital Image Processing, Second Edition
Python
In : H = array([[1,1],[1,-1]])
In : for i in range(2):
...: H = vstack([kron(H,[1,1]),kron(eye(H.shape[0]),[1,-1])])
...:
In : D = H.dot(H.T)
In : H = np.linalg.inv(np.sqrt(D)).dot(H)
In : w = (H.dot(v.T)).T
In : print np.around(w,2)
[ 101.82 31.11 44. 18. 2.83 -1.41 2.83 -2.83]
Any wavelet transform can be computed by matrix multiplications. But as we have seen in
our discussion of the DFT, this can be very inefficient. Happily many wavelet transforms can
be quickly computed by a fast algorithm similar in style to the average/difference method
we saw earlier. These methods are called lifting methods [24].
If we go back to our averaging and differencing example, we c an see that the averaging
part of the transform corresponds to low pass filtering, in that we are “coarsening” or
“blurring” our input. Similarly, the differencing part of the transform corresponds to a high
pass filter, of the sort we looked at in our discussion of edges in Chapter 9. Thus, a wavelet
transform contains within it both high and low pass filtering of our input, and we can
consider a wavelet transform entirely in terms of filters. This approach will be discussed in
Section 15.4.
Two-Dimensional Wavelets
The two-dimensional wavelet transform is separable, which means we can apply a one-
dimensional wavelet transform to an image in the same way as for the DFT: we apply a
one-dimensional DWT to all the columns, and then one-dimensional DWTs to all the rows
of the result. This is called the standard decomposition, and is illustrated in Figure 15.4.
f(x, y)
Original image
DWT of rows DWT of columns
FIGURE 15.4: The standard decomposition of the two-dimensional DWT
We can also apply a wavelet transform differently. Suppose we apply a wavelet transform
(say, using the Haar wavelet) to an image by columns and then rows, but using our transform
at 1 scale only. This will pro duce a result in four quarters: the top left will be a half-sized
version of the image; the other quarters will be high pass filtered images. These quarters will
contain horizontal, vertical, and diagonal edges of the image. We then apply a 1-scale DWT
to the top left quarter, creating smaller images, and so on. This is called the nonstandard
decomposition, and is illustrated in Figure 15.5.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.