3.3.1. Gradient-Based Methods

 

    Consider an analog function f(x) which represents a typical 1-D edge, as shown in Figure 3.24(a). In typical problems, it is reasonable to consider the value x0 in the figure an edge point. One way to determine x0 is to compute the first derivative f’(x) or the second derivative f”(x). Figures 3.24(b) and (c) show f’(x) and f”(x). From the figure. the value x0 can be determined by looking for the local extremum (maximum or minimum) of f’(x) or by looking for a zero crossing of f”(x) where f”(x) changes its sign.

   In addition to determining the possible edge point x0, f’(x) can also be used in estimating the strength and direction of the edge. If If’(x)I is very large, f(x) is changing very rapidly and a rapid change in intensity is indicated. If f’(x) is positive, f(x) is increasing. Based on the above observations, one approach to detecting edges is to use the system shown in Figure 3.25. In the system, first |f’(x)| is computed from f(x). If |f’(x)| is greater than some threshold, it is a candidate to be an edge. If all values of x such that |f’(x)| is greater than a certain threshold are detected to be edges, an edge will appear as a line rather than a point. To avoid this problem, we further require |f’(x)| to have a local maximum at the edge points. It may be desirable to determine whether f(x) is increasing or decreasing at x = x0. The necessary information is contained in f’(x) at x = x0. The choice of the threshold depends on the application. As the threshold increases, only the values of x where f(x) changes rapidly will be registered as candidate edges. Since it is difficult to choose the threshold optimally, some trial and error is usually involved, it is also possible to choose the threshold adaptively. The system in Figure 3.25 is based on the particular type of edge shown in Figure 3.24(a), but it is generally applicable to detecting various other types of edges.

    The generalization of f’(x) to a 2-D function f(x, y) is the gradient Ñf(x, y) given by

 

 

where  is the unit vector in the x-direction and  is the unit vector in the y­-direction. A generalization of the edge detection system Figure 3.25 based on Ñf(x,y) is shown in Figure 3.26. The magnitude of Ñf(x,y) is first computed and is then compared with a threshold to determine candidate edge points. If all values of (x,y) such that |Ñf(x,y)| is greater than a certain threshold are detected to be edges, the edges will appear as strips rather than lines. The process of determining an edge line front a strip of candidate edge points is called edge thinning, in one simple edge thinning algorithm, the edge points are selected by

checking if  is a local maximum in at least one direction. The property that  achieves its local maximum in at least one direction is usually checked along a few specified directions. In most cases, it is sufficient to check for local maxima in only the horizontal and vertical directions. If  is a local maximum along any one of the specified directions at a potential edge point, the potential edge point is considered to be an edge point. One difficulty with this simple edge thinning algorithm is that it creates a number of minor false edge lines in the vicinity of strong edge lines. One simple method to remove most of these minor false edge lines is to impose the following additional constraints:

    (a)If  has a local maximum at (x0,y0) in the horizontal direction but not in the vertical direction, (x0,y0) is an edge point when

 

    with k typically chosen around 2

 

    (b)If   has a local     maximum at      (x0,y0) in the vertical direction but not in the        horizontal direction, (x0,y0) is an edge point when

    with k typically chosen around 2

 

When  has a local maximum at (x0,y0) in the horizontal direction but not in the vertical direction. Condition (a) requires that the rate of intensity change along the horizontal direction is significantly larger than that along the vertical direction. Condition (b) is the same as Condition (a) with the roles of x and y reversed. 


 

    An edge detection system that is based on a function such as  is called a nondirectional edge detector, since such functions do not have a bias toward any particular direction. If an edge detection system is based on a function that has a bias toward one particular direction, it is called a directional edge detector. If we use  instead of  in the system in Figure 3.26  for example, the system will detect edges in the vertical direction, but will not respond to edges in the horizontal direction.

    For a 2-D sequence f(n1,n2), the partial derivatives  and  can be replaced by some form of difference. For example,  may be replaced by

                       

                                                                           (3.7a)

                                                                                          (3.7b)

                                                                                     (3.7c)

 

Since the computed derivatives are compared later with a threshold and the thresh­old can be adjusted. the scaling factors 1/T and 1/2T can be omitted. Typically the expressions in (3.7) are averaged over several samples to improve the reliability and continuity of the estimate of . Examples of ‘improved’ estimates of  are

 

 

                                                                                                                               (3.8a)

or 

                                                                                                                                             (3.8b)

The unnecessary scaling factors have been omitted in (3.8).

    The differencing operation in (3.7) and (3.8) can be viewed as the convolution of f(n1,n2) with the impulse response of a filter h(n1,n2). Examples of impulse responses that can be used in developing directional edge detectors are shown in Figure 3.27. The filters h(n1,n2) in Figures 3.27(a) and (b) detect edges in the vertical and horizontal directions and can be viewed as approximating  and  respectively. The filters h(n1,n2) in Figures 3.27(c) and (d) detect edges along the two diagonal directions. The gradient  in (3.6) can also be expressed in terms of the first-order partial derivatives in a rotated coordinate system. When the rotation is 45 degrees, the directions of partial derivatives are along the two diagonal directions.

    Nondirectional edge detectors can be developed by discrete approximation of  in the system in Figure 3.26. From (3.6).

                                                                             (3.9)

From (3.9), nondirectional edge detectors can be developed by nonlinear combi­nation of the terms used in the development of directional edge detectors. An example of discrete approximation of (3.9) that can be used for nondirectional edge detectors is given by

 

                                                                         (3.10)

where                  

                           

 

and and  are shown in Figure 3.28. The method is based on (3.10) with and  shown in Figure 3.28. Another example is the method based on (3.10) with and  shown in Figure 3.29. Depending on exactly how  is approximated in the discrete domain, many other variations can be developed.

    Figure 3.30 shows the result of edge detection using a directional edge de­tector. Figure 3.30(a) shows an image of 512 x 512 pixels. Figure 3.30(b) and (c) show the results of a vertical edge detector and a horizontal edge detector, respectively, applied to the image in Figure 3.30(a). The vertical and horizontal edge detectors are based on h(n1,n2) in Figures 3.27(a) and (b). Figures 3.3 1(a) and (b) show the results of applying the Sobel edge detector and Roberts’s edge detector to the image in Figure 3.30(a). Both belong to the class of nondirectional edge detectors, and the specific method of determining the threshold value and checking the local maximum property of an edge used is the same as that used in Figure 3.30.

    There are many variations of the edge detection methods discussed in this section. For example, we could use a different nonlinear combination of  and  instead of

 

 

 

in the system in Figure 3.26. Many different methods can aiso be developed for edge thinning.

    The edge detection methods discussed in this section can be improved in various ways. Methods based on computing some form of gradient or differencing are typically sensitive to noise. A certain number of isolated edge points which appear randomly distributed throughout the edge maps in Figure 3.31 are most likely the result of some background noise or very fine image details. Some noise smoothing using the methods discussed in Section 3.2 or more sophisticated noise reduction methods that we will discuss in Chapter 4 may be desirable prior to applying an edge detection algorithm. Isolated random edge points may also be removed by some simple processing of the edge maps. Gradient-based edge de­tection methods also cause some discontinuities in the detected edge contours, as can be seen from the edge maps in Figure 3.31. Methods that impose continuity constraints in the detected edge contours can also be developed.