## Edge Based Segmentation

Edge-based segmentation approaches have two major components: (1) edge detection and (2) edge linking/following to determine the edges and the regions. Loosely speaking, an edge is a collection of connected pixels that lie on the boundary between two homogeneous regions having different intensities. Therefore, edges can be defined as abrupt changes in pixel intensity that can be reflected by the gradient information. A number of edge detectors have been defined based on the first-order or second-order gradient information of the image [1,20]. For a given image f (x, y), the gradient computed at location (x, y) is defined as a vector:

where Sfx and 8fy are gradients computed along x and y directions. The gradient vector points in the direction of maximum rate of change of f at (x, y). The magnitude and the direction of the gradient vector are given by

where the angle 6 is measured with respect to the x axis.

In order to obtain the gradient of an image, computation of partial derivatives Sfx and Sfy at every pixel location is required. Because the images have been digitized, it is not possible to compute Sfx and Sfy using differentiation and numerical approximation of the gradient by finite difference is used instead [20]. Implementation of edge detection can be accomplished by convolving the original image with a mask (also called window or kernel) that runs through the entire image. A mask is typically a2 x 2ora3 x 3 matrix. For example, Roberts edge operator has two 2 x 2 masks:

and Sobel edge operator has a pair of 3 x 3 masks:

 -1 0 0 -1 0 1 Sfy = 1 Detailed discussion on other edge operators such as Canny, Kirsch, Prewitt, and Robinson can be found elsewhere [1,20]. An edge magnitude image can be formed by combining the gradient components Sfx and Sfy at every pixel location using Eq. (3.4). As the computational burden required by square and square roots in Eq. (3.4) is very high, an approximation with absolute values is frequently used instead: After the edge magnitude image has been formed, a thresholding operation is then performed to determine where the edges are. The first-order derivatives of the image f (x, y) have local minima and maxima at the edges because of the large intensity variations. Accordingly, the second-order derivatives have zero crossings at the edges, which can also be used for edge detection and the Laplacian is frequently employed in practice. The Laplacian (V2) of a two-dimensional function f (x, y) is defined as There are several ways to realize the Laplacian operator in discrete-time domain. For a 3 x 3 region, the following two realizations are commonly used: It should be noted that all gradient-based edge detection methods (including the Laplacian) are very sensitive to noise because differentiation is a high pass operation that tends to enhance image noise. In some applications, it is possible to improve the results obtained with these methods by smoothing the image prior to edge detection. For example, a smoothing filter can be applied to an image before computing the Laplacian. Marr and Hildreth [24] proposed smoothing the image with a Gaussian filter followed by the Laplacian operation to determine edge information and this operation is called Laplacian of Gaussian, which is defined as h(x, y) = V2[g(x, y) f (x, y)] where f (x, y) is the original image, is the convolution operator, g(x, y) is a Gaussian function, and V2[g(x, y)] is the Laplacian of Gaussian function that is used for spatial smoothing of the original image. Edges can be determined from the resultant image, h(x, y), by simply thresholding it for zero value to detect zero crossing. Equation (3.8) represents a generic operation of taking the Laplacian on the spatial smoothing filter, g (x, y), which can be replaced by other filter function (e.g., directional low-pass filter [25]) to improve the performance of edge detection in a specific application. Faber et al. [26] applied the Laplacian edge detection technique to segment scintigraphic images and the results were promising. In practice, edge detection techniques produce only a series of edges for the structures/areas of interest. It is not uncommon that the edge pixels do not characterize an edge and that the edges do not enclose the ROI completely because of noise and some other acquisition artifacts that caused spurious discontinuities of edges. Therefore, the second component of edge-based segmentation techniques is to track and link the edge pixels to form meaningful edges or closed regions in the edge image obtained by one of the edge detection techniques. One of the simplest approaches for linking edge pixels is to analyze local characteristics of pixels within a small block of pixels (e.g., 3 x 3 or 5 x 5) for the entire edge image and linked all edge pixels that are similar to each others according to some predefined criteria. The Hough transform [27] can also be applied to detect straight lines and parametric curves as well as arbitrarily shaped objects in the edge image. It was shown by Deans [28] that the Hough transform is a special case of the Radon transform for image projection and reconstruction [29]. Thorough discussion and comparison of different varieties of the Hough transform and their generalizations are considered beyond the scope of this chapter and they can be found in Refs. [30,31]. There are several more powerful edge tracking/linking techniques such as graph searching [32,33] and dynamic programming [34,35] that perform well in the presence of noise. As might be expected, these paradigms are considerably more complicated and computationally expensive than the methods discussed so far.