2.2.1.1Edge Detectors

Since the edge in an image corresponds to the discontinuity in an image (e. g., the intensity surface of the underlying scene), the differential edge detector(DED) is popularly employed to detect edges. Though some particularly and sophisticatedly designed edge operators have been proposed (Canny, 1986), various simple DEDs such as the Sobel, Isotropic, Prewitt, and Roberts operators are still in wide use. These operators are implemented by mask convolutions. Figure 2.1 gives the two masks used for Sobel, Isotropic, and Prewitt edge detectors. For the Sobel detector,d = 2; for the Isotropic detector,d = 21/2; for the Prewitt detector,d = 1.

These operators are first-order DEDs and are commonly called gradient operators. In addition, the Laplacian operator, a second-order DED is also frequently employed in edge detection. Figure 2.2(a, b) gives two commonly used Laplacian masks.

These operators are conceptually well established and computationally simple. The computation of discrete differentiation can be easily made by convolution of the digital image with the masks. In addition, these operators have great potential for real-time implementation because the image can be processed in parallel, which is important, especially in computer vision applications.

The problems with edge detection techniques are that sometimes edges detected are not at the transition from one region to another and the detected edges often have gaps at places where the transitions between regions are not abrupt enough. Therefore, the detected edges may not necessarily form a set of closed connected curves that surround the connected regions.

2.2.1.2Hough Transform

The Hough transform is a global technique for edge connection. Its main advantage is that it is relatively unaffected by the gaps along boundaries and by the noise in images.

A general equation for a straight line is defined by

$y=px+q(2.1)$

where p is the slope and q is the intercept. All lines pass through (x, y) satisfy eq. (2.1) in the XY plane. Now consider the parameter space PQ, in which a general equation for a straight line is

$q=-px+y(2.2)$

Consider Figure 2.3(a), where two points (xi, yi) and (xj, yj) are in a line, so they share the same parameter pair (p, q), which is a point in the parameter plane, as shown in Figure 2.3(b). A line in the XY plane corresponds to a point in the space PQ. Equivalently, a line in the parameter space PQ corresponds to a point in the XY plane.

The above duality is useful in transforming the problem of finding points lying on straight lines in the XY plane to the problem of finding a point that corresponds to those points, in the parameter space PQ. The latter problem can be solved by using an accumulative array as used in the Hough transform.

The process of the Hough transform consists of the following three steps:

One example illustrating the results in different steps is presented in Figure 2.4, in which Figure 2.4(a) is an image with a circular object in the center, Figure 2.4(b) is its gradient image, Figure 2.4(c) is the image of accumulative array, and Figure 2.4(d) is the original image with detected boundary.

2.2.2.1Major Components

The major components of a sequential edge detection procedure include the following:

Many algorithms in this category have been proposed. A typical example is the snake, which is also called the active contour (Kass, 1988).

2.2.2.2Graph Search and Dynamic Programming

Graph search is a global approach combining edge detection with edge linking (Gonzalez, 2002). It represents the edge segments in the form of a graph and searches in the graph for low-cost paths, which correspond to edges/boundaries, using some heuristic information and dynamic programming techniques.

A graph G = (N, A) is a finite, nonempty set of nodes N, together with a set A of pairs of distinct elements (called arcs) of N. Each arc connects a node pair (ni, nj). A cost c(ni ,nj) can be associated with it. A sequence of nodes n1, n2,..., nK, with each node ni being a successor of node ni–1 is called a path from n1 to nK. The cost of the entire path is

$c(n_1,n_K)={\displaystyle \sum _{i=2}^{K}c(n_{i-1},n_i)}(2.3)$

The boundary between two 4-connected pixels is called an edge element. Figure 2.5 shows two examples of the edge element, one is the vertical edge element and the other is the horizontal edge element.

One image can be considered a graph where each pixel corresponds to a node and the relation between two pixels corresponds to an arc. The problem of finding a segment of a boundary can be formulated as a search of the minimal cost path in the graph. This can be accomplished with dynamic programming. Suppose the cost associated with two pixels p and q with gray levels of f(p) and f(q) is

$c(p,q)=H-[f(p)-f(q)](2.4)$

where H is the highest gray level in the image.

The path detection algorithm is based on the maximization of the sum of the path’s merit coefficients. Usually, they are computed using a gradient operator, which replaces each element by some quantity related to the magnitude of the slope of the underlying intensity surface. The process of the graph search for the minimal cost path will be explained using the following example.

Consider a portion of the image as shown in Figure 2.6(a), where pixels are indicated by black discs and the numbers in the parentheses represent the gray levels of pixels. Here, H in eq. (2.4) is 7. Suppose a top-down path is expected. After checking each possible edge element, the minimal cost path corresponding to the sequence of the edge elements as shown by the bold line in Figure 2.6(b) can be found.

The graph for the above search process is shown in Figure 2.7.

Example 2.1 Practical implementation of the graph search process.

The boundary of objects in noisy two-dimensional (2-D) images may be detected with a state-space search technique such as dynamic programming. A region of interest, centered on the assumed boundary, is geometrically transformed and straightened into a rectangular matrix. Along the rows (of the matrix in the transform domain), merit coefficients are calculated. Dynamic programming is used to find the optimal path in the matrix, which is transformed back to the image domain as the object boundary (Figure 2.8).

Straightening the region of interest in a 3-D image can be accomplished in several ways. In general, the region of interest is resampled along scan lines, which form the rows of the coefficient matrix. The layout order of these rows in this matrix is not important, as long as two neighboring elements in the image domain are also neighbors in the resampled domain. The way the scan lines are located in the region of interest depends on the image (e.g., the scan lines are positioned perpendicular to the skeleton of the region of interest), while at the same time overlaps between scan lines are avoided. Another approach is to resample the data on a plane-by-plane basis. In this case, the number of planes in the image equal the number of planes in the resample matrix.

2.2.3.1Technique Classification

Determination of appropriate threshold values is the most important task involved in thresholding techniques. Threshold values have been determined in different techniques by using rather different criteria. Generally, the threshold T is a function of the form given by the following equation.

$T=T[x,y,f(x,y),g(x,y)](2.6)$

where f(x, y) is the gray level of the point located at (x, y) and g(x, y) denotes some local properties of this point. When T depends solely on f(x, y), the technique is point-dependent thresholding. When T depends on both f(x, y) and g(x, y), the technique is region-dependent thresholding. If, in addition, T depends also on the spatial coordinates x and y, then the technique will be coordinate-dependent thresholding.

A threshold operator T can also be viewed as a test involving a function T of the form T[x, y, N(x, y),f(x, y)], in which f(x, y) is the characteristic feature functions of (x, y) and N(x, y) denotes some local property (e. g., the average gray-level value over some neighbor pixels) of the point (x, y). Algorithms for thresholding can be divided into three types depending on the functional dependencies of the threshold operator T. When T depends only on f(x, y), the threshold is called a global threshold. If T depends on both f(x, y) and N(x, y), then it is called a local threshold. If T depends on the coordinate values (x, y) as well as on f(x, y) and N(x, y), then it is called a dynamic threshold.

In the case of variable shading and/or variable contrast over the image, one fixed global threshold for the whole image is not adequate. Coordinate-dependent techniques, which calculate thresholds for every pixel, may be necessary. The image can be divided into several subimages. Different threshold values for those subimages are determined first and then the threshold value for each pixel is determined by the interpolation of those subimage thresholds. In a typical technique, the whole image is divided into a number of overlapping sub-images. The histogram for each subimage is modeled by one or two Gaussian distributions depending on whether it is a uni-modal or a bi-modal. The thresholds for those subimages that have bi-modal distributions are calculated using the optimal threshold technique. Those threshold values are then used in bi-linear interpolation to obtain the thresholds for every pixel.

2.2.3.2Optimal Thresholding

Optimal thresholding is a typical technique used for segmentation. Suppose that an image contains two values combined with additive Gaussian noise. The mixture probability density function is

$p(z)=P_1{p}_1(z)+P_2{p}_2(z)=\frac{P_1}{\sqrt{2\pi }{\sigma }_1}\exp \left[-\frac{{(z-{\mu }_1)}^2}{2{\sigma }_1^2}\right]+\frac{P_2}{\sqrt{2\pi }{\sigma }_2}\exp \left[-\frac{{(z-{\mu }_2)}^2}{2{\sigma }_2^2}\right](2.7)$

where μ1 and μ2 are the average values of the object and the background, respectively, and σ1 and σ2 are the standard deviation values of the object and the background, respectively. According to the definition of probability, P1 + P2 = 1. Therefore, there are five unknown parameters in eq. (2.7).

Now look at Figure 2.10, in which μ1 < μ2. Suppose a threshold T is determined, all pixels with a gray-level below T are considered to belong to the background, and all pixels with a gray-level above T are considered to belong to the object. The probabilities of classifying an object pixel as a background pixel and of classifying a background pixel as an object pixel are

$E_1(T)={\displaystyle \underset{-\infty }{\overset{T}{\int }}{p}_2(z)\text{d}z}(2.8)$

$E_2(T)={\displaystyle \underset{T}{\overset{\infty }{\int }}{p}_1(z)\text{d}z}(2.9)$

The overall probability of error is given by eq. (2.10):

$E(T)=P_2{E}_1(T)+P_1{E}_2(T)(2.10)$

In the case where both the object and the background have the same standard deviation values, the optimal threshold is

$T=\frac{{\mu }_1+{\mu }_2}{2}+\frac{{\sigma }^2}{{\mu }_1-{\mu }_2}\ln \left(\frac{P_2}{P_1}\right)(2.11)$

2.3.1.13-D Differential Edge Detectors

In 3-D space, there are three types of neighborhoods. It can also say that in the 3-D space, there are three ways to define a neighbor: voxels with joint faces, joint edges, and joint corners (Jähne, 1997). These definitions result in a 6-neighborhood, an 18-neighborhood, and a 26-neighborhood.

Let x = (x0, ..., xn) be some point on an image lattice. The $V_1^i$ neighborhood of x is defined as

$V_1^i=\left\{y\right|D_1(x,y)\le i\}(2.12)$

and the $V_{\infty }^i$ neighborhood of x is defined as

$V_{\infty }^i=\left\{y\right|D_{\infty }(x,y)\le i\}(2.13)$

These neighbors determine the set of the lattice points within a radius ofi from the center point.

Let x = (x0, x1) be some point on a 2-D image lattice. The n-neighborhood of x, where n = 4, 8, is defined as

$N_4(x)=V_1^1(x)N_8(x)=V_{\infty }^1(x)(2.14)$

Let x = (x0, x1, x2) be some point on a 3-D image lattice. The n-neighborhood of x, where n = 6, 18, 26, is defined as

$N_6(x)=V_1^1(x),N_{18}(x)=V_1^2(x){\displaystyle \cap V_{\infty }^1}(x),N_{26}(x)=V_{\infty }^1(x)(2.15)$

In digital images, differentiation is approximated by difference (e. g., by the convolution of images with discrete difference masks, normally in perpendicular directions). For 2-D detectors, two masks are used for x and y directions, respectively. For 3-D detectors, three convolution masks for the x, y, and z directions should be designed. In the 2-D space, most of the masks used are 2 × 2 or 3 × 3. The simplest method for designing 3-D masks is just to take 2-D masks and provide them with the information for the third dimension. For example, 3 × 3 masks in 2-D can be replaced by 3 × 3 × 1 masks in 3-D. When a local operator works on an image element, its masks also cover a number of neighboring elements. In the 3-D space, it is possible to choose the size of the neighborhoods. Table 2.2 shows some common examples of 2-D masks and 3-D masks.

Since most gradient operators are symmetric operators, their 3-D extensions can be obtained by the symmetric production of three respected masks. The convolution will be made with the x mask in the x–y plane, the y-mask in the y–z plane, and the z-mask in the z–x plane.

For example, the 2-D Sobel operator uses two 3 × 3 masks, while for the 3-D case, a straightforward extension gives the results shown in Figure 2.13(a), where three 3 × 3 × 1 masks for the three respective convolution planes are depicted. This extended 3-D Sobel operator uses 18 neighboring voxels of the central voxel. For the 26-neighborhood case, three 3 × 3 × 3 masks can be used. To be more accurate, the entry values of masks should be adapted according to the operators’ weighting policy. According to the Sobel’s weighting policy, the voxels close to the central one should have a heavier weight. Following this idea, the mask for calculating the difference along the x-axis is designed as shown in Figure 2.13(b). Other two masks are symmetric (Zhang, 1993c).

The Laplacian operator is a second-order derivative operator. In the 2-D space, the discrete analog of the Laplacian is often defined by the neighborhood that consists of the central pixel and its four horizontal and vertical neighbors. According to the linearity, this convolution mask can be decomposed into two masks, one for the x-direction and the other for the y-direction. Their responses are added to give the response of Laplacian. When extending this operator to the 3-D case, three such decomposed masks could be used. This corresponds to the 6-neighborhood example as shown in Figure 2.14(a). For the 18-neighborhood case, the mask shown in Figure 2.14(b) can be used. For the 26-neighborhood case, the mask would be like that shown in Figure 2.14(c).

2.3.1.23-D Thresholding Methods

Extending 2-D thresholding techniques to 3-D can be accomplished by using 3-D image concepts and by formulating the algorithms with these concepts. Instead of using the pixel in the 2-D image, the voxel is the 3-D image’s primitive. The gray-level value of a voxel located at (x, y, z) will be f(x, y, z) and its local properties will be represented by g(x, y, z), thus the 3-D corresponding equation of eq. (2.6) is (Zhang, 1990)

$T=T[x,y,z,f(x,y,z),g(x,y,z)](2.16)$

In the following, some special requirements to extend different groups of 2-D thresholding techniques will be discussed.

Point-Dependent Group: For a technique in point-dependent thresholding group, two process steps can be distinguished:

(i)The calculation of the gray-level histogram

(ii)The selection of the threshold values based on the histogram

When it goes from 2-D to 3-D using exclusively the individual pixel’s information, the only required modification is in the calculation of the histogram from a 3-D image, which is essentially a counting and addition process. As a 3-D summation can be divided into a serial of 2-D summations, this calculation can be accomplished by using the existing 2-D programs (the direct 3-D summation is also straightforward). The subsequent threshold selection based on the resulted histogram is the same as that derived in the 1-D space. In this case, real 3-D routines are not necessary to process 3-D images.

Region-Dependent Group: In addition to the calculation of the histogram from 3-D images, 3-D local operations are also needed for the region-dependent thresholding group of techniques. For example, besides the gray-level histogram, the filtered gray-level image or the edge value of the image is also necessary. Those operations, as the structural information of a 3-D image has been used, should be performed in the 3-D space. In other words, truly 3-D local operations in most cases require the implementation of the 3-D versions of 2-D local operators. Moreover, as it has more dimensions in space, the variety of local operators becomes even larger. For example, one voxel in the 3-D space can have 6-, 18-, or 26-nearest or immediate neighbors, instead of 4- or 8-neighbors for a 2-D pixel.

Coordinate-Dependent Group: Two consecutive process steps can be distinguished in the coordinate-dependent thresholding group. One threshold value for each subimage is first calculated, then all these values are interpolated to process the whole image. The threshold value for each subimage can be calculated using either point-dependent or region-dependent techniques. Therefore, respective 3-D processing algorithms may be necessary. Moreover, 3-D interpolation is required to obtain the threshold values for all voxels in the image based on the thresholds for the subimages.

2.3.1.33-D Split, Merge, and Group Approach

To adapt the SMG algorithm in last section to 3-D images, it is necessary to change the data structures that contain the 3-D information. The RAG structure can be left unchanged. The QT structure, however, depends on the image dimensionality. The 3-D equivalent is called an octree. The octree structure of a 3-D image is shown in Figure 2.15. Each father in this pyramidal structure has eight sons.

The initialization, split, and merge phases are analogous to those in the 2-D case because of the similarity of the quad-tree and the octree structures. The neighbor-finding technique also functions in the same way. Only the functions used to find the path in the tree from a node to its neighbor have to be adjusted for the 3-D case.

By simply replacing the quad-tree by an octree, the 3-D algorithm will be restricted to the image containing 2n × 2n × 2n voxels. In practice, 3-D images with lower z resolution are often encountered (anisotropic data). Three methods can be used to solve this problem (Strasters, 1991):

2.3.2.1Subpixel Edge Detections

In many applications, the determination of the edge location at the pixel level is not enough. Results that are more accurate are required for registration, matching, and measurement. Some approaches to locate edge at the subpixel level are then proposed.

Moment Preserving: Consider a ramp edge as shown in the upper part of Figure 2.16, where the ramp values at each position 1, 2, ..., n-1, n are indicated by f1, f2, ··· , fn-1, fn. Edge detection is a process used to find a step edge (an idea edge), which in some sense fits best to the ramp edge. One approach is to keep the first three moments of the ramp and step edges equivalent to each other (moment preserving)(Tabatabai, 1984).

Consider the following formulation. The pth order of the moment (p = 1, 2, 3) of a signal f(x) is defined by (n is the number of pixels belonging to the edge)

$m_p=\frac{1}{n}{\displaystyle \sum _{i=1}^n{[f_i(x)]}^p}(2.17)$

It has been proven that mp and f(x) have a one-to-one correspondence. Let t be the number of pixels that have gray-level value b (background) and n–t be the number of pixels whose gray-level values are o (object). To keep the first three moments of two edges equivalent, the following three equations should be satisfied

$m_p=\frac{t}{n}{b}^p+\frac{n-t}{n}{o}^p,p=1,2,3(2.18)$

where t is

$t=\frac{n}{2}\left[1+s\sqrt{\frac{1}{4+s^2}}\right](2.19)$

in which

$s=\frac{m_3+2m_1^3-3m_1{m}_2}{{\sigma }^3}\text{and}{\sigma }^2=m_2-m_1^2(2.20)$

The edge is located at t + 0.5. This value is normally a real value that provides the subpixel accuracy.

Expectation of First-Order Derivatives: This approach computes the expectation of first-order derivatives of the input sequence and consists of the following steps (consider 1-D case) (Hu, 1992):

$E={\displaystyle \sum _{k=1}^{n}k{p}_k}={\displaystyle \sum _{k=1}^n\left(k{g}_k/{\displaystyle \sum _{i=1}^n{g}_i}\right)}(2.22)$