ELLIPSE DETECTION USING THE HOUGH TRANSFORM H.K. Yuen, J. Illingworth and J. Kittler
Department of Electronics and Electrical Engineering University of Surrey, Guildford, GU2 5XH. U.K.
We consider the problem of detecting elliptical curves using Hough Transform methods. Storage and efficiency problems are overcome by decomposing the problem into two stages. The first stage uses a novel constraint as the basis for a Hough Transform to detect the ellipse center while the second stage finds the remaining parameters using a simple but efficient focussing implementation of the HT. The method is applicable in many situations where previous HT schemes would fail. Results are demonstrated for complex image data containing several overlapping and occluding ellipses.
ently. At the end of the voting or accumulation process those array elements containing large numbers of votes indicate strong evidence for the presence of the shape with corresponding parameters. These properties mean that the method is insensitive to image noise but it can still detect shapes using the type of fragmentary evidence which results from both poor image segmentation and object occlusion. The principal disadvantage of the HT is that it is demanding both in terms of the amount of computer storage required to represent the multidimensional parameter space and the amount of computation to carry out the accumulation of votes in this space. Ellipse detection requires the determination of 5 parameters. Each parameter has a large range of values and if uniformly high accuracy of representation is needed over this range then resource demands become unpractically large. In this paper we consider how ellipse detection can be made a practical proposition by using edge direction information and decomposing the ellipse detection problem into two sequentially executed HT stages of first finding the center of the ellipse and then determining the remaining three parameters. Although this decomposition idea has been used by Tsukune and Goto'3' and Tsuji and Matsumoto'4' we propose an alternative method of ellipse center finding that will work in situations where the previous methods fail. In addition the second stage of our algorithm utilises a multiresolution approach to detect peaks in the HT space of the remaining three parameters. In Section 2 we discuss both the general principles of the ellipse finding problem and specific details pertaining to our method. Section 3 gives an approximate analysis of the complexity of the method and Section 4 includes results of experiments on complex image data containing several overlapping ellipses. Concluding remarks and comments are included in Section 5.
1. Introduction. The detection of elliptical curves or fragments of such curves is an important task in computer vision as these shapes occur commonly in many types of scene. Man made objects often have circular profiles which, when viewed obliquely, project to elliptical shapes in a 2D image. Ellipse detection is therefore a powerful method of cueing into specific geometric object models. Also, the measured values of ellipse parameters provide data from which it is possible to infer the relative orientation of object and camera. The importance of ellipse detection was recognised in the model based vision system, ACRONYM, developed by Brooks and BinfordW. They used the generalised cylinder as a basic modeling primitive and had to extract lines and ellipses as basic image features. Shortcomings of their system were largely ascribed to poor segmentation and consequent unreliability of the feature extraction process. The Hough Transform, HT, is a method of parameter extraction whose properties make it particularly appropriate for the detection of shapes within poorly segmented imagery'2'. It is a method which takes pieces of local evidence and votes for all parameter combinations which are consistent with this evidence. The votes are collected in an array of counters which is called the accumulator array. The accumulator array is a discrete partitioning of the multidimensional space which spans the possible parameter values. Image points on a shape vote coherently into the accumulator counter which represents the parameters of the shape while votes from isolated or random image points combine only incoher
2. General principles. The general equation of an ellipse is, X2 + B'Y2 + 2D'XY + 2E'X + 2G'Y + C' = 0, (1) where B', D', E', G' and C" are constant coefficients normalized with respect to the coefficient of X2. If we use
265
the standard HT method with this equation, we have to construct a five dimensional parameter space and if each parameter range is divided into a intervals then the accumulator space requires a5 storage locations. Even for modest values of a this becomes unpractically large. However the problem can be made much more tractable if we consider using edge direction information and decomposing it into a series of parameter estimation steps, each of which is computationally less demanding. The exact problem decomposition can be achieved in a variety of ways and this approach has been used by several authors'3'4'. The problem decomposition which we use ? in this paper includes a novel method to find the parameters which describe the ellipse center. This is followed by an efficient implementation to find the three remaining parameters. 2.1 Stage 1: Center finding. Center detection is probably the most important stage in the detection of ellipses. One commonly used method involves the determination of the midpoint of the line between two image points with parallel tangents. If these two points are on the same ellipse then the midpoint is the center of the ellipse. This principle can be used as the basis of a HT method. The first step of the procedure is to extract pairs of image points whose gradients are almost the same. The next step is to construct a two dimensional histogram of the midpoints of such pairs. The histogram locations which receive high counts become candidates for the center of an ellipse. This procedure is the one used by Tsukune and Goto'3' and Tsuji and Matsumoto'4'. A disadvantage of the above procedure is that it fails if the image does not contain segments which are symmetrical about the ellipse center. This type of situation is common where objects are viewed so that they are occluded by other objects or by parts of themselves. In this paper we propose another center finding procedure, which can be used to detect the center of an ellipse in a more general setting. The new procedure is based on a simple property of ellipses. Suppose P(xi,yi) and Q(x2,J/2) are two points on an ellipse with nonparallel tangents intersecting at a point T(ti,tz). Let Af(mi,m 2 ) be the midpoint of PQ. Then the center of the ellipse must lie on the straight line TM, as illustrated in Figure 1. The form of TM has been found
as,
where ft and ?2 are the slopes of the tangents to the ellipse at the points P and Q respectively. Lines in the form of equation 2 can be constructed from different pairs of image points, and they should intersect at the same location if they are on the same ellipse. A standard HT can be used to accumulate these lines in a two parameter accumulator array. The accumulator cell which receives the highest count is the candidate for the center of an ellipse. 2.2 Stage 2: Determination of remaining parameters. Once the location of the center of an ellipse has been estimated, the subset of image points which are consistent with it can be found by a second pass through data. The origin relative to which the points are described, can be translated so as to coincide with the estimated ellipse center and then the equation describing the points of the ellipse becomes X2 + BY2 + 2DXY + C = 0, B  D2 > 0. (3)
There are several ways in which the remaining parameters B, C and D can be estimated. Tsuji and Matsumoto'4' estimate all five parameters of the best ellipse formed by the subset of points using a least mean squares fitting procedure. As with all least squares procedures, this is likely to be highly sensitive to spurious outlier points. In the work of Tsukune and Goto!3' the three parameter estimation problem is decomposed into two further steps using the property that differentiation of equation 3 with respect to X yields
M
Using measured gradient values equation 4 forms the basis of a two dimensional HT method to determine B and D. Once B and D are known a simple one dimensional HT can be used to estimate C using equation 3. The drawback of this approach is that the range of the parameters is large and even a two dimensional parameter space can require a large amount of computer storage. Also the efficiency advantages of the decomposition into an increasing number of stages must be weighed against the systematic effects of propagating errors through several stages. As the number of stages increases so does the reliance of the results on the accurate determination of gray level edge directions. In this paper we determine all three remaining parameters simultaneously using equation 3 and a space efficient peak detection algorithm based on the Adaptive Hough Transform, AHT, method'5l. The peak detection algorithm locates the peak areas of the Hough Transform space without computing the background level in full detail. The algorithm is based on an iterative 'coarse
y(ti — mi) = x(*2 — rnt) +
)
(2)
with yi  y 2  s i 6 + J 2 6
66
66(^2

*i)
66
266
to fine' accumulate and search strategy. A small fixed size accumulator is used. In our work we use a 9x9x9 accumulator. The accumulator always partitions the current range of parameters into these few intervals. During the first iterative step the range of each parameter is large and thus each parameter is only coarsely resolved. The HT is accumulated and the accumulator cell with maximum counts is identified. The parameter range covered by the accumulator is then centered about the maximum cell and, if the parameter is not resolved to the required accuracy, the range of that parameter is reduced to one third of its previous value. This basic cycle of accumulation and parameter range reduction is iterated and the method focusses in on, and accurately defines, the position of the most prominent peak in the parameter space. In our ellipse finding application the subset of points from the first stage of the method are predominately from a single ellipse and therefore the focussing works well. Apart from its efficiency, another advantage of using the focussing is that it can dynamically and independently vary the resolution to which each parameter is measured. This is particular important for estimating the parameters B, D and C, because the range of values of C are usually much larger than those of B and D and therefore it needs to be more accurately determined. After determination of all three parameters, the length of the ellipse axes, a and b, and its angle of rotation, 9, can be calculated using
2C
\xi  x2\ > S2,
or
yi  y2\ > fa
where Si and S2 are some predetermined values. Let ? be the slope of the line TM determined in equation 2. The center histogram of the new method can be simplified further if we notice that
x<
m2
or x>
mi>
if III > 1.
where (x, y) is the coordinate of the center, say. If N is a point on the line TM such that the center of the ellipse lies on MN then instead of accumulating votes for all points along TM we only have to count the votes for the section MN. The length, L, of MN can be predetermined based on prior knowledge of the likely sizes of ellipses in the image. Once the center finding HT has been accumulated, the parameters of a possible ellipse center are identified by determining the accumulator cell with the largest numbers of counts. If the number of counts exceeds a predetermined threshold then the center is accepted as valid and the subset of image points supporting this cell are identified and passed to the second stage which finds three parameters B, D and C. Once points have been identified with a candidate center they are deleted and the remaining points can again be passed through the center finding accumulation stage. This center finding procedure is repeated until the maximum of the accumulator falls below the predetermined threshold.
a=
[(B
2C
6 =
3. Complexity of the algorithm. In this section we make an approximate calculation of the complexity of our algorithm making the simplyfying assumption that Si and 62 are suitably chosen so that there is little pairing between points of different ellipses. If there are k ellipses and each ellipse is composed of Hi image points then the number of votes cast by the Ph ellipse will be the product of the number of image point pairs in that ellipse and the number of votes which each pair contributes, viz 1) where L is the prespecified length of the incremented line MN. Note that the complexity of forming pairs is 0(n?) whereas the center finding methods used in [3,4] are only linearly dependent on n<. The total number of votes cast in determining the first centre location will be the sum of these votes for all A ellipses ;
(B + 1) + = itanlB
2.3 Practical considerations. In our proposed method of ellipse finding the HT space for center finding may become complicated when there are several ellipses in an image. This is caused by background votes generated by pairing image points on different ellipses. A complex parameter space makes peak detection a difficult task and is therefore highly undesirable. In order to overcome or reduce these effects we can invoke aprior knowledge of likely ellipse size or inter ellipse spacing to vote the pairing of image points which are unlikely to lie on a common ellipse. It is also not necessary to pair two image points if they are too close to each other. Based on these considerations, we only have to pair two image points, [xi, t/i) and (x2, y2), if they satisfy the conditions, ~x2\ < Si, and
(5)
267
In determining the second center location the image points associated with the first are removed and the HT is reaccumulated. This process of point removal and subsequent HT accumulation continues until all k ellipses have been found. Thus the total number of votes cast in the center finding stage is
klkj
y=o?=i The actual number of votes cast will be dependent on the rii and the order in which the ellipses are found. The minimum number of votes will occur when the largest ellipses are found before smaller ones. The simplest upper limit on the cost is to assume that no points are discarded and therefore in finding k ellipses the accumulation is iterated k times. Thus the cost of finding k ellipses would be O(k2) that of finding a single ellipse. A special case of particular interest, and maybe more indicative of the average case complexity, is when all ellipses are of the same size. In this case the cost for Vtot is O(fc(fc*^). Obviously, this method of iterative accumulation is undesirably inefficient but it seems to be necessary to achieve reliable identification in a complex center finding space. In future work we hope to investigate more efficient ways of analysing the parameter space. The second stage of the algorithm using the iterative focussing algorithm requires a 9x9x9 accumulator array. At each iteration, every image point has to be evaluated to determine the subset of accumulator cells that its parameter surface intersects. This procedure required 3x9 2 evaluations of the function in equation 3. Assuming the cost of each function evaluation is comparable to the basic operation of determining and incrementing a cell in stage 1 then the cost per iteration of the second stage is very approximately proportional to Cx = 3 X 92 X The maximum number of iterations required to localise the peak is governed by the parameter whose range needs to be most finely divided. However, as each iteration produces a range reduction to  of the previous value the process quickly converges. In our experiments the focussing never required more than 10 iterations to achieve the required resolution. Therefore the cost of the second stage will be C2 = 10 X 3 X 9 2 X
t=i
vtnt =
 1)
In this section we demonstrate the proposed two stage algorithm using computer generated ellipse data. Figure 2 shows 67 edge points from a segment of an ellipse with center at (116.8,85.72). The edge points along with edge gradient directions are extracted using Spaceks edge detection algorithm!6!. Other boundary detection methods which accurately measure edge gradient or curve tangent information can be used. For the center finding algorithm we set the values of < j and 5 82 to 5 and 30 pixels respectively. The length, L, of the line MN was taken to be 30 pixels. The HT was accumulated in a 256x256 accumulator array. Using the new center finding algorithm, the center is found at (116.5 ± 0.5,86.5 ± 0.5). It should be stressed that previous center finding methods based on parallel tangents axe not applicable in this situation. In the second stage of the algorithm the initial ranges for C, B and D were chosen arbitrarily large so that they encompassed the parameter values for any realistic ellipse which was contained wholly within the 256x256 image. The rapid convergence inherent in the focussing HT implementation meant that this incurred no significant extra computational cost. The parameter values eventually found were 5=0.93827 ± 0.25, D=0.17284 ± 0.25 and C=382.2588 ± 0.5. The lengths, a and b, of the major and minor radius and the angle of rotation, 8 of the ellipse were calculated from these estimates and were found to be a=21.948, 6=18.274 and 5=50.062°. These compare with true values of a—22.231, 6=18.437 and 0=50.675°. The image generated from the estimated parameters is given in Figure 3. Figure 4 shows a more complex image consisting of eight ellipses with a total of 657 edge points. Numbers have been overlayed on the figure and these are used in Table 1 which summarises the true and estimated values for the ellipse parameters. Figures 5a5d show edge points that remain at some of the intermediate stages of the method after particular edge points have been associated with candidate center locations. Most of the ellipses have their parameters estimated well except for the ellipse centered at (140.24,35.78). The center of the ellipse was found well but the method failed in the second stage. However it should be noted that this estimation is based on only 14 points and the curve fragment is so small that it may be equally well interpreted as part of some other ellipse. Figure 6 shows the image generated from the estimated parameters.
5. Discussion and conclusions. The new method of ellipse center finding which we suggest requires less restrictive assumptions than the one commonly used. It is likely to be applicable to a much larger range of practical problems because effects
4. Experimental results.
268
such as self occlusion lead to image fragments which, although elliptical, are highly asymmetric about the ellipse center. The price paid for this increased applicability is an increase in the number of computations. However, the basic operation in the center finding step is the voting for a line of points in accumulator space and this could become an inexpensive primitive operation if implemented in dedicated hardware. The focussing method used at the second stage works well and is efficient. At the moment, we overcome some of the peak detection problems in the center finding parameter space by deleting image points associated with candidate centers and then reaccumulating the HT with the reduced list of image points. This is an inefficient procedure and future work will attempt to develop ways of simplifying!7! the parameter space to avoid wasteful reaccumulation.
References. [1] Brooks R.A., Model Based Computer Vision, (Computer Science: Artificial Intelligence No 14), UMI Research Press, Ann Arbor, Mich. 1981. [2] Illingworth J. and Kittler J. ? A survey of the Hough Transform.", accepted for publication in Computer Vision, Graphics and Image Processing (1988). [3] Tsukune H. and Goto K. "Extracting elliptical figures from an edge vector field.", IEEE Computer Vision and Pattern Recognition Conf, Washington pp 138141 (1983). [4] Tsuji and Matsumoto F. "Detection of ellipses by a modified Hough transformation.", IEEE Transaction on Computers, C27, No 8, pp 777781 (1978). [5] Illingworth J. and Kittler J. "The Adaptive Hough transform.", IEEE Trans, in Pattern Analysis and Machine Intelligence, Vol 9, No 5, pp 690697 (1987). [6] Spacek L.A., "Edge detection and motion detection", Image and Vision Computing, Vol 4 No 1 pp 4356 (1986). [7] Gerig G., "Linking imagespace and accumulator space: a new approach to object recognition", 1'* IEEE Int. Conf. on Computer Vision, London, pp PP 112117 (1987).
Acknowledgements. This work was carried out as part of Alvey project MMI078, a collaborative project between Surrey University, HeriotWatt University and Computer Recognition Systems.
Fig.(l) Basic geometry for center finding. The center of an ellipse must lie on the line MN.
Fig.(2) The image of a segment of an ellipse.
Fig. (3) Reconstruction of the image of Fig. (2) based on the estimates of the parameters.
269
Fig.(4) The image of 8 ellipses.
(5c) (5d) Fig.(5ad) The remaining edge points at some of the intermediate stages after particular edge points have been associated with candidate center locations.
270
Fig.(6) Reconstruction of the image of Fig.(4) based on the estimates.
Table 1. The true and estimated values of the parameters of ellipses as shown in Fig. (4) and Fig. (6) respectively.
Ellipses 1
True 84.56 110.98 120.56 110.98 100.12 60.24 130.49 30.68
Centers Estimated 81.5 109.5 118.5 110.5 100.5 60.5 129.5 31.5 98.5 145.5 130.5 150.5 249.5 57.5 141.5 34.5
True 25.5 7.25 25.5 7.25 12.35 8.35 30.67 15.43 32.67 21.98 22.35 15.67 30.5 12.67 17.95 11.45
Radii Estimated 23.45 7.26 22.01 6.64 14.05 8.46 29.04 16.38 27.55 20.70 24.14 15.90 32.94 13.04 27.86 14.13
Angles of rotation True Estimated 20 19.76
2
20
20.41
3
80
74.43
4
145
145.36
5
99.25 140.56 130.90 150.56 250.05 56.90 140.24 35.78
85
66.26
6
33.75
31.17
7
128.34
127.52
8
32.49
19.20
271
272