Wavelets and Edge Detection CS698 Final Project

Submitted To: Professor Richard Mann Submitted By: Steve Hanov Course: CS698 Date: April 10, 2006

INTRODUCTION
Wavelets have had a relatively short and troubled history. They seem to be forever confined to footnotes in textbooks on Fourier theory. It seems that there is little that can be done with wavelets that cannot be done with traditional Fourier analysis. Stephane Mallat was not the father of wavelet theory, but he is certainly an evangelist. His textbook on the subject, A Wavelet Tour of Signal Processing [1], contains proofs about the theory of wavelets, and a summation about what is known about them with applications to signal processing. One of his many papers, Characterization of Signals from Multiscale Edges [2], is frequently cited as a link between wavelets and edge detection. Mallat’s method not only finds edges, but classifies them into different types as well. Mallat goes on to describe a method of recovering complete images using only the edges, but we will not implement it in this project. In this project, we study this paper, and implement the method of Mallat to multiscale edge detection and analysis. We will first present a short background on wavelet theory. Then we will describe the different types of edges that exist in images, and how they can be characterized using a Lipschitz constant. Next, we describe the algorithm for the wavelet transform, from the Mallat paper. Finally, we show the results of applying the algorithm to a test image, and a real image.

wave with the signal. When the results high valued, the coefficients of the Fourier transform will be high. Where the signal or the wave is close to zero, the coefficients will be low. Fourier analysis has a big problem, however. The sine and cosine functions are defined from - to . The effects of each frequency are analyzed as if they were spread over the entire signal. For most signals, this is not the case. Consider music, which is continuously varying in pitch. Fourier analysis done on the entire song tells you which frequencies exist, but not where they are. The short time Fourier transform (STFT) is often used when the frequencies of the signal vary greatly with time. [3] In the JPEG image encoding standard, for example, the image is first broken up into small windows with similar characteristics. The Fourier transform is not applied to the entire image, but only to these small blocks. The disadvantage of this technique can be seen at high compression ratios, when the outlines of the blocks are clearly visible artifacts. A second disadvantage is in resolution of analysis. When larger windows are used, lower frequencies can be detected, but their position in time is less certain. With a smaller window, the position can be determined with greater accuracy, but lower frequencies will not be detected. The wavelet transform helps solve this problem. Once applied to a function f(t), it provides a set of functions Wsf(t). Each function describes the strength of a wavelet scaled by factor s at time t. The wavelet extends for only a short period, so its effects are limited to the area immediately surrounding t. The wavelet transform will give information about the strengths of the frequencies of a signal at time t. In the first pages of his treatise [1], Mallat defines a wavelet as a function of zero average,
∞

WAVELET ANALYSIS
THEORY It is best to describe wavelets by showing how they differ from Fourier methods. A signal in the time domain is described by a function f(t), where t is usually a moment in time. When we apply the Fourier transform to the signal, we obtain a function F(ω) that takes as input a frequency, and outputs a complex number describing the strength of that frequency in the original signal. The real part is the strength of the cosine of that frequency, and the imaginary part is the strength of the sine. One way to obtain the Fourier transform of a signal is to repeatedly correlate the sine and cosine

ψ (t )dt = 0

−∞

which is dilated with scale parameter s, and translated by u:

∞

∫

∞

ψ u , s (t ) =

Unlike the sine and cosine functions, wavelets move toward quickly zero as their limits approach to +/-∞. In [2], Mallat notes that the derivative of a smoothing function is a wavelet with good properties. Such a wavelet is shown in Figure 1.
1 0.9 0.8
0.2 0.4 0.3

0.7 0.6 0.5 0.4 0.3
-0.2 0.1 0 -0.1

0.2 0.1 0
-0.3 -0.4

0

100

200

300

400

500

600

0

100

200

Figure 1: A smoothing function, and its corresponding wavelet.

By correlating the signal with this function at all possible translations and scales, we obtain the continuous wavelet transform. The transformation also increases the dimension of the function by one. Since we have both a scaling and position parameter, a 1-D signal will have a 2D wavelet transform. As an illustration, in Figure 2 we show the wavelet transform of a single scan line of an image, calculated using the algorithm in [2] (See Appendix A). The frequencies decrease from top to bottom, and pixel position increases from left to right. The edges in the signal result in funnel-shaped patterns in the wavelet transform.

  
Figure 2: The 512th scanline of the famous Lena image, and its wavelet transform. Pixel position increases from left to right, and frequency increases from bottom to top. Only nine scales were used, but they are stretched to simulate a continuous transform, which is more illustrative.
300 400 500 600

1 t −u ψ s s
  

Like the Fourier transform, the wavelet transform is invertible. However, it is easier to throw away information based on position. In the Fourier domain, if you were to try to eliminate noise by simply throwing away all of the information in a certain frequency band, you would get back a smoothed signal, with rounded corners, because all frequencies contribute to larger structures in all parts of the signal. With the wavelet transform, however, it is possible to selectively throw out high frequencies in areas where they do not contribute to larger structures. Indeed, this is the idea behind wavelet compression. Here is the scan line from the Lena image, with the highest frequency wavelet coefficients removed: reconstructed 250 200 150 100 50 0

0

100

200

300

400

500

600

The signal keeps the same structure as the original, but is smoother. Here is the same signal with the three highest dyadic1 frequency bands removed: rec ons truc ted 250

200

150

100

50

0

0

100

200

300

400

500

600

The signal is smoother, but the edges are rounder. So far, this frequency removal is equivalent to smoothing the signal with a Gaussian. The true power of the wavelet transform is revealed, however, when we selectively remove wavelet coefficients from the first three dyadic frequency bands only in positions where they are weak (in this case, less than +/-20): rec ons truc ted 250

In the dyadic wavelet transform, we use only scales that are powers of two. With the careful choice of an appropriate wavelet, this covers the entire frequency domain. At the scale s=1, the image is smoothed by convolving it with a smoothing function. At scale s=2, the smoothing function is stretched, and the image is convolved with it again. The process is repeated for s=4, s=8, etc., until the smoothing function is as large as the image. At each level, the wavelet transform contains information for every position t in the image. This method is used by Mallat. Most applications today, however, use an even more optimal method. Since the image is smoothed at each step by a filter, the image only contains half of the frequency information, and needs half as many samples. So the number of samples in the image is reduced at each stage as well. As a result, the wavelet transform is reduced to the same size as the original signal. Mallat avoids this optimization because he needs the redundant information to recover the image using only its modulus maxima (edges).

200

150

100

50

0

CHARACTERIZATION OF EDGES
0 100 200 300 400 500 600

Here, the signal retains much of its original character. Most edges remain sharp. This simple algorithm for noise removal could be improved further if it did not change the weak coefficients in areas where they contribute to the larger structure. To do this, one would need to consider the coefficients across all scales, and determine the positions of the edges of the signal. In his paper, Mallat presents a way to do just that.

WAVELET TRANSFORM TYPES
There are numerous types of wavelet transforms. The first is the continuous wavelet transform (CWT). Dispite its name, the wavelet transform can be calculated on discrete data. All possible scaling factors are used, starting at 1 and increasing to the number of samples in the signal. However, the CWT is computationally expensive, and for most applications, a dyadic method is used instead.

When the wavelet transform is used with a smoothing function, it is equivalent to Canny edge detection [4]. The derivative of a Gaussian is convolved with the image, so that local maxima and minima of the image correspond to edges. Note Figure 2, in which large drops are characterized by black funnels, and leaps result in white funnels. It is clear that by examining the wavelet transform, we can extract a lot of information about the edges. For example, we can see whether it is a gradual change or a leap, or whether it is a giant cliff, or a momentary spike, by looking only at the wavelet representation. Edges are characterized mathematically by their Lipschitz regularity. We say that a function is uniformly Lipschitz α, over the interval (a,b), if, and only if, for every x, x0 in the interval, there is some constant K such that:

f ( x ) − f ( x0 ) ≤ K x − y

α

1

Dyadic: based on successive powers of two

The area over the interval will never have a slope that is steeper than the constant K. [5] Mallat shows that the Lipschitz continuity is related to the wavelet transform, and that if the wavelet transform is Lipschitz α, the function is also Lipschitz α:

W2 j f ( x ) ≤ K (2 j )α
The conclusions are summarized in the following table. α constraint Meaning Impact on Wavelet transform Amplitude decreases with scale. Amplitude remains the same across scales. Amplitude decreases with scale.

0 < α