446 A Computational Introduction to Digital Image Processing, Second Edition
FIGURE 15.8: A 3-scale standard decomposition DWT applied to an image
15.4 The Daubechies Wavelets
We have seen that the dilation and wavelet equations for the Haar wavelet are particular
examples of the general equations 15.4 and 15.5. However, it is not at all obvious that there
are any other solutions. One of the many contributions of Ingrid Daubechies to the theory
of wavelets was to define an entire class of wavelets which may be considered solutions to
these equations.
The Daubechies-4 wavelet has a scaling function φ(x) and wavelet function ψ(x) which
satisfy the equations:
φ(x) = h
0
φ(2x) + h
1
φ(2x −1) + h
2
φ(2x −2) + h
1
φ(2x −2) (15.8)
ψ(x) = h
0
φ(2x −1) − h
1
φ(2x) + h
2
φ(2x + 1) − h
3
φ(2x + 2) (15.9)
where the values of the filter coefficients are:
h
0
=
1 +
√
3
4
√
2
≈ 0.48296
h
1
=
3 +
√
3
4
√
2
≈ 0.83652
h
2
=
3 −
√
3
4
√
2
≈ 0.22414
h
3
=
1 −
√
3
4
√
2
≈ −0.12941
These can be obtained with the
daubcqf f unction of rwt:
MATLAB/Octave
>> [h,g] = daubcqf(4)
h =
0.48296 0.83652 0.22414 -0.12941
g =
0.12941 0.22414 -0.83652 0.48296
Wavelets 447
The vectors contain the same values, but in different orders and with different signs. As for
the Haar wavelet, we can apply the Daubechies-4 wavelet by a matrix multiplication; the
matrix f or a 1-scale DWT on a vector of length 8 is
h
0
h
1
h
2
h
3
0 0 0 0
0 0 h
0
h
1
h
2
h
3
0 0
0 0 0 0 h
0
h
1
h
2
h
3
h
2
h
3
0 0 0 0 h
0
h
1
h
3
−h
2
h
1
−h
0
0 0 0 0
0 0 h
3
−h
2
h
1
−h
0
0 0
0 0 0 0 h
3
−h
2
h
1
−h
0
h
1
−h
0
0 0 0 0 h
3
−h
2
Notice that the filter coefficients overlap between rows, which is not the case for the Haar
matrix H
2
n
. This means that the use of the Daubechies-4 wavelet will have smoother results
than using the Haar wavelet. The form of the matrix above is similar to circular convolution
with the one-dimensional filters
h
0
h
1
h
2
h
3
and
h
3
−h
2
h
1
−h
0
.
The discrete wavelet transform can indeed be approached in terms of filtering; the above
two filters are then known as the low pass and high pass filters, respectively. Steps for
performing a 1-scale wavelet transform are given by Umbaugh [52]:
1. Convolve the image rows with the low pass filter.
2. Convolve the columns of the result of Step 1 with the low pass filter, and rescale this
to half its size by subsampling.
3. Convolve the result of Step 1 with the high pass filter, and again subsample to obtain
an image of half the size.
4. Convolve the original image rows with the high pass filter.
5. Convolve the columns of the result of Step 4 with the low pass filter, and rescale this
to half its size by subsampling.
6. Convolve the result of Step 4 with the high pass filter, and again subsample to obtain
an image of half the size.
At the end of these steps there are four images, each half the size of the original. They are:
1. the “low pass/low pass” image (LL); result of Step 2.
2. the “low pass/high pass” image (LH); result of Step 3.
3. the “high pass/low pass” image (HL); result of Step 5.
4. the “high pass/high pass” image (HH); result of Step 6.
448 A Computational Introduction to Digital Image Processing, Second Edition
LL LH
HL HH
FIGURE 15.9: The 1-scale wavelet transform in terms of filters
These can then be placed into a single image grid as shown in Figure 15.9.
The filter coefficients of a wavelet are such that the transform may be inverted precisely
to recover the original image. Using filters, this is done by taking each subimage, zero-
interleaving to produce an image of double the size, and convolving with the inverse low
pass and high pass filters. Finally, the results of all the filterings are added. For the
Daubechies-4 wavelet, the inverse low pass and high pass filters are:
h
2
h
1
h
0
h
3
and
h
3
−h
0
h
1
−h
2
respectively.
A further approach to the discrete wavelet transform may be considered as a general-
ization to filtering; it is called lifting, and is discussed by Jensen and la Cour-Harbo [24].
Lifting starts with a sequence s
j
[n], n = 0 . . . 2
j
−1 and produces two sequences s
j−1
[n], n =
0 . . . 2
j−1
−1 and d
j−1
[n], n = 0 . . . 2
j−1
−1, each half the length of the original. The lif ting
scheme for the Haar wavelet may be described as
d
j−1
[n] = s
j
[2n + 1] − s
j
[2n]
s
j−1
[n] = s
j
[2n] + d
j−1
[n]/2,
and a lifting scheme for the Daubechies-4 wavelet is:
s
(1)
j−1
[n] = s
j
[2n] +
√
3s
j
]2n + 1]
d
(1)
j−1
[n] = s
j
[2n + 1] −
1
4
√
3s
(1)
j−1
[n] −
1
4
(
√
3 −2)s
(1)
j−1
[n −1]
s
(2)
j−1
= s
(1)
j−1
[n] −d
(1)
j−1
[n + 1]
s
j−1
[n] =
√
3 −1
√
2
s
(2)
j−1
[n]
d
j−1
[n] =
√
3 + 1
√
2
d
(1)
j−1
[n].
Both the Haar and Daubechies-4 schemes can be reversed; see [24] for details. A single
lifting, as shown above, produces a 1-scale wavelet transform. To produce transforms of
higher scales, lifting can be applied to s
j−1
to produce s
j−2
and d
j−2
, and then to s
j−2
,
and so on. In each lifting scheme, the sequence s
j−1
may be considered the subsampled
Wavelets 449
low pass version of s
j
, and the sequence d
j
−1
may be considered the subsampled high pass
version of s
j
. Thus, a single lifting scheme provides, in effect, both the low pass and high
pass filter results. Applying a lifting to an image, first to all the rows, and then to all the
columns of the result, will produce a 1-scale wavelet transform.
We might hope that since the scaling and wavelet functions φ(x) and ψ(x) have such
simple forms for the Haar wavelet, as we saw in Figure 15.3, the same would be true for
the Daubechies-4 wavelet. We can plot a wavelet by inverting a “basis vector”: a vector
consisting of all zeros except for a single one. Following [24] we shall choose a vector whose
sixth element is one. We shall experiment first with the Haar wavelet:
MATLAB/Octave
>> [h,g] = daubcqf(2);
>> t = zeros(1,512); t(6) = 1;
>> td = miwt(t,h,9);
>> plot([1:512]/512,td,"linewidth",2)
The result is shown in Figure 15.10. Other basis vectors produce similar results, but with
FIGURE 15.10: A plot of the Haar wavelet
the wavelet scaled or translated. The vector we have chosen seems to produce the best plot.
For the Daub echies-4 wavelet, we repeat the above four commands, but starting with
MATLAB/Octave
>> [h,g] = daubcqf(4);
In Python, the plot can be generated with
Python
In : t = np.array([0]
*
512); t[5]=1
In : td = rwt.idwt(t,h,9)[0]
In : plt.plot(np.arange(512),td)
The result is shown in Figure 15.11. This is a very spiky and unusual graph! It is in fact a
fractal, and unlike the Haar wavelet, the function cannot be described in simple terms.
450 A Computational Introduction to Digital Image Processing, Second Edition
FIGURE 15.11: A plot of the Daub e chies-4 wavelet
15.5 Image Compression Using Wavelets
Wavelets provide some of the most powerful tools known for image compression. As we
stated earlier, they have replaced the use of the DCT in the JPEG2000 algorithm. In this
section we shall play around with investigating what information we can remove from the
DWT of an image, and still retain most of the original information.
Thresholding and Quantization
The idea is to take the DWT of an image, and for a given value d, set all values x in
the DWT for which |x| ≤ d to zero. This is at the basis of the JPEG2000 compression [51].
We shall try this using the Daubechies-4 wavelets, and d = 10.
MATLAB/Octave
>> c = imread(’caribou.png’);
>> imshow(c);
>> cw = mdwt(double(c),h,8);
>> length(find(abs(cw)<=10))
ans =
47427
>> cw(find(abs(cw)<=10)) = 0;
>> cw = round(cw);
>> ci=midwt(cw,h,8);
>> imshow(mat2gray(ci))
We are thus removing nearly three quarters of the information from the DWT. We further
simplify the result by quantizing; in this case we just use the
round function to turn
fractions into integers. The original caribou image and the result of the above commands
are shown in Figure 15.12. The result is indistinguishable from the original image. We
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.