Many shapes in medical images can be approximated by circles or ellipses. The principal idea of the Hough transform, the accumulation of votes in parameter space, can be applied to both circles and ellipses, since both shapes can be described analytically. A circle is described by three parameters: radius r and the two center coordinates, xc and yc:
Therefore, the Hough space for circles is three-dimensional. The projection of an individual pixel (xk,yk) into Hough space is a cone: If the pixel coordinates x and y in Equation (7.7) are assumed to be fixed with x = xk and y = yk, Equation (7.7) is satisfied by an infinite set of concentric circles with center (xk,yk). The radius of the circles increases as the circles are translated along the r-axis (Figure 7.8). If a number of pixels that lie on a circle in image space are projected into Hough space, the ensuing cones meet at the point (xc,yc,r). Accumulating votes along the cones (analogous to the sinusoidal traces in the line transform) will therefore yield a maximum at (xc,yc,r) that can be used to reconstruct the circle.
FIGURE 7.8 A pixel is projected as a cone in Hough space since a cone satisfies Equation (7.7) for increasing r. The cone tip rests at (xk,yk) for r = 0. The light gray plane is located at r = 50, and its intersection with the cone is therefore a circle of radius 50.
FIGURE 7.9 Detection of the pupil and iris with the Hough transform: (A) the original eye photo and (B) the edge image obtained by filtering, edge detection, and thresholding. (C) One plane in Hough space. In this plane (r = 60), the cones from the pupil pixels intersect and form a local maximum (arrow). The inverse Hough transform of this local maximum leads to the smaller circle in (D). Although the smaller circle represents the pupil very well, the larger iris circle is affected by various conflicting edges caused, for example, by the eyelids. As a result, the circle is smaller than the actual iris.
The circle Hough transform is frequently used to quickly determine the pupil diameter of the eye. An example is shown in Figure 7.9. In this example, isolation of the pupil and iris will be attempted. Whereas the pupil is well defined, the iris is partly occluded by the eyelids. In preparation of the Hough transform, image filtering and edge detection are necessary. Since edge detection increases the noise component, the image was first blurred by using a Gaussian convolution filter. Application of the Sobel edge detector was followed by manual thresholding. The resulting edge image is shown in Figure 7.9B. The pupil is represented by an almost perfect ring, while the iris caused multiple edges. Each pixel in Figure 7.9B is projected as a cone in Hough space. One plane in Hough space, similar to the plane in Figure 7.8, is shown in Figure 7.9C. In this plane at r = 60, the cones from the pupil pixels intersect and add up to a clear local maximum (indicated by an arrow). Multiple local maxima can be found at larger r values, because there are many edges related to the iris. The eyelids contribute additional edges. Therefore, several significant local maxima exist at large values of r in Hough space. It is not trivial to isolate the meaningful maxima, and a simple maximum-finding algorithm as used to generate Figure 7.9 does not necessarily find the pixel that best represents the iris circle. The two local maxima that represent pupil and iris were finally subjected to the inverse Hough transform and yielded two circles. The two circles, superimposed over the original image of the eye, are shown in Figure 7.9D. In this case, the edge at the left side of the iris (Figure 7.9A) where light is refracted and causes a dark rim is most dominant, and the maximum-finding algorithm picked a pixel that represents a circle that is too small. More sophisticated algorithms and the use of a priori knowledge, such as the approximate radius, strongly improve the results obtained from Hough transform-based methods.
An additional validation method would be the comparison of the reconstructed circles to the original edge image. Image values from the edge image can be averaged along the reconstructed circles and the average values thresholded to eliminate false positives. Furthermore, if the gradient information from the edge detection step is available, the circle detection algorithm can be further improved by using the first derivative of the circle.2 Consider the parametric form of the circle,where ^ is the angle of the line connecting the circle’s center with a point (x,y) on the circle. From Equation (7.8), the gradient follows:
Here
is the angle of the circle’s tangent. If the angle $ is available, the additional constraint reduces each circle of the cone to two points, and the point (x,y) with known gradient angle $ is represented by two slanted lines in Hough space. In practice, however, a larger angular range needs to be considered because of the discrete nature of the edge detectors. With the Sobel edge detector and the compass edge detector, the angle range can be reduced to 90° and 45°, respectively. Each point of the circle therefore casts votes over a cone segment rather than a full cone in Hough space. The addition of edge information is computationally more efficient and reduces the number of local maxima in Hough space, thus making the isolation of meaningful circles easier.
The ellipse needs five parameters to fully describe its position, shape, and rotation. Most frequently, the equation of an ellipse that is oriented parallel to the x-axis is found:
Here a and b are the long and short semiaxes, respectively, and xc and yc the center coordinates. However, ellipses found in images may have any orientation; therefore, a rotation of the coordinate system at an angle 0 must be considered. The general ellipse equation assumes either the stable polynomial form of Equation (7.11) with
The parameter space is now five-dimensional with the parameters xc, yc, a, b, and 0. This not only puts a heavy load on memory use and computational effort, but the accumulated votes will start to spread out in this high-dimensional space and become sparse. It becomes more difficult to detect meaningful local maxima in high-dimensional spaces with sparse votes. Generally, a straightforward approach as seen in the line and circle transforms is no longer possible, and more efficient algorithms are needed.
One early proposal19 involved the detection of majority votes for the ellipse center only, followed by a search for pixel clusters in the image that satisfied the ellipse equation. With multipass techniques, the five-dimensional space was broken down into low-dimensional subspaces: for example, into one two-dimensional space for (xc,yc), another two-dimensional space for (a,b) and finally, a one-dimensional space for the orientation 0.16 Breaking down the voting process into subspaces, like spreading out the votes into the five-dimensional parameter space, decreases the robustness of the algorithm.
Alternatively, it is possible to reduce the high-dimensional space by providing a one-dimensional space for each parameter. For the ellipse, five independent accumulators would receive the votes for the parameters xc, yc, a, b, and 0 independently. Each accumulator provides one or more majority votes for its respective parameter. The main advantage of this technique, apart from the memory efficiency, is the increased robustness achieved by concentrating the votes. On the other hand, the solutions are not unique. If each accumulator provides exactly one maximum, the shape is uniquely defined. However, if each accumulator provides multiple maxima, all shapes that are a possible combination of the maxima are shape candidates. If two ellipses exist in the image, for example, there will be two maxima in each accumulator. By combining these parameters, 32 ellipses can be identified as possible solutions. A subsequent validation step can identify the true shapes out of the candidate pool.
The eccentricity e = b/a and the coefficients given in Equation (7.12)12 or the polar form given in Equation (7.13) with the coefficients r and ^ defined in Equation (7.14).
A more advanced approach was presented by Yip et al.22 Under inclusion of the gradient direction, point pairs on opposite sides of the ellipse are sought. These point pairs have the same tangent direction and are connected by a line through the center of the ellipse. Provided that they are members of the ellipse outline, two of these point pairs are sufficient to compute all five parameters of the ellipse candidate. The accumulation can therefore be reduced to accumulating the x and y coordinates of the two point pairs, and ellipse candidates can be extracted from the histogram of the two-dimensional accumulator array. Similar approaches of reducing the dimensionality by using edge information and well-designed transformations were introduced by other groups.1,18,20 These advanced algorithms for extracting ellipse parameters are valid for circles as well, since the circle is a special case of the ellipse with a = b = r in Equation (7.10).
