3.3.2. Laplacian-Based Methods


    The objective of an edge detection algorithm is to locate the regions where the intensity is changing rapidly. In the case of a 1-D function f(x), searching for regions of rapidly changing intensity corresponds to searching for regions where f’(x) is large. For gradient-based methods, f’(x) is considered large when its magnitude |f’(x)| is greater than a threshold. Another possible way is to assume that f’(x) is large whenever it reaches a local extremum, that is, whenever the second derivative f”(x) has a zero crossing. This is illustrated in Figure 3.24. Declaring zero-crossing points as edges results in a large number of points being declared to be edge points. Since there is no check on the magnitude of f’(x). Declaring zero-crossing points as edges results in a large number of points being declared to be dege points. Since there is no check on the magnitude of f’(x), any small ripple in f(x) is enough to generate an edge point. Due to this sensitivity to noise the application of a noise reduction system prior to edge detection is very desirable in processing images with background noise.

    A generalization of  to a 2-D function f(x,y) for the purpose of edge detection (see Problem 3.19) is the Laplacian Ń2f(x,y) given by




For a 2-D sequence f(n1,n2), the partial second derivatives  and  can be replaced by some form of second-order differences. Second-order differences can be represented by convolution of f(n1,n2) with the impulse response of a filter h(n1,n2). Examples of h(n1,n2) that may be used are shown in Figure 3.35. To illustrate that f(n1,n2)*h(n1,n2) may be viewed as a discrete approximation of Ń2f(x, y), let us consider h(n1,n2) in Figure 3.35(a). Suppose we approximate  by




We again omitted the scaling factor, since it does not affect zero-crossing points. Since the forward difference is used in (8.12), we can use the backward difference in approximating :




From (3.12) and (3.13),

            .                          (3.14)


From (3.11) and (3.14), and approximating  in a similar manner, we obtain




The resulting  is f(n1,n2)*h(n1,n2) with h(n1,n2) in Figure 3.35(a). Depending on how the second-order derivatives are approximated, it is possible to derive many other impulse responses h(n1,n2), including those shown in Figures 3.35(b) and (c).

    Figure 3.36 shows an example where edges were detected by looking for zero-crossing points of . Figure 3.36(a) shows an image of 512 x 512 pixels. Figure 3.36(b) shows the zero-crossing points of , obtained from (8.15) and using the image in Figure 3.36(a) as f(n1,n2). Since zero-crossing contours are boundaries between regions, they tend to be continuous lines. As a result, edge thinning necessary in gradient-based methods is not needed in Laplacian­based methods. In addition, algorithms that force continuity in edge contours are not as useful in Laplacian-based methods as in gradient-based methods. As is clear from Figure 3.33(b), however, choosing all zero-crossing points as edges tends to generate a large number of edge points.

    The Laplacian-based methods discussed above generate many “false” edge contours which typically appear in regions where the local variance of the image is small. As a special case, consider a uniform background region so that f(n1,n2) is constant. Since  is zero and we detect edges from zero-crossing points of , any small perturbation of f(n1,n2) is likely to cause false edge contours. One method to remove many of these false contours is to require that the local variance is sufficiently large at an edge point, as shown in Figure 3.34. The local variance  can be estimated by




with M typically chosen around 2. Since  is compared with a threshold, the scaling factor      1/(2M+1)2 in (3.16a) can be eliminated. In addition, the local variance  needs to be computed only for (n1,n2) which are zero-crossing points of . Figure 3.38 shows the result of applying the system in Figure 3.37 to the image in Figure 3.36(a). Comparison of Figures 3.36(b) and 3.38 shows considerable reduction in the “false” edge contours.

    The system in Figure 3.34 can be interpreted as a gradient-based method. The local variance  is closely related to the gradient magnitude. Com­paring  with a threshold is similar to comparing the gradient magnitude with a threshold. Requiring that  crosses zero at an edge can be inter­preted as edge thinning. With this interpretation, we can implement the system in Figure 3.37 by computing  first and then by detecting the zero-crossing points of  only at those points where  is above the chosen threshold.