1995/6 Research Journal
Image, Speech and Intelligent Systems
A. S. Aguado and M. S. Nixon
Detecting geometric primitives in images is one of the basic tasks of computer vision. The Hough transform (HT) and its extensions constitute a popular method for extracting geometric shapes. Primitives on the HT are represented by parametric curves with a number of free parameters. The principal concept of the HT is to define a mapping between an image space and a parameter space. Each edge point in an image is transformed by the mapping to determine cells in the parameter space whose associated parameters are such that the defined primitive passes through the data point. The chosen cells are accumulated and after all the points in an image have been considered, local maxima in the accumulator correspond to the parameters of the specified shape.
Because a curve with n parameters requires an n-dimensional parameter space, many applications of the HT concern line and circle detection. In order to overcome the excessive time and space requirements for ellipse extraction, proposed techniques (Yip et al.[1], Pao et al.[2], Yoo and Sethi[3], Wu and Wang[4], Ho and Chen[5]) decompose the five dimensional parameter space into several sub spaces of fewer dimensions. The decomposition is achieved by using geometric features which define constraints in the organization of edge data. These constraints include distance and angular relationships which define relative positions between a set of edge points. Hence, the parameters are computed after labelling the points which satisfy the constraints in a computational intensive approach.
Here, we show how it is possible to decompose the parameter space, based on the polar definition of an ellipse. Angular information, defined from the variation of a position function, represents local change in the curvature of border points. This information is used to formulate expressions which define an ellipse by including local shape properties. We show that in order to achieve a parameter decomposition (due to the ellipse anisotropy) it is necessary to consider the angular change of the second derivative (tangent angle of the second directional derivative). We compute angular information by taking a pair of points and their gradient direction. This avoids the constraints which define relative position, as required by other approaches.
Gradient direction information has been used to reduce the computational requirements of the HT (Ballard[6], Davis[7], Conker[8]). Here we use gradient information for ellipse extraction by relating local geometric features of a parametric representation to the local features in an image (Aguado et al.[10]).
We represent an ellipse by the locus defined by the differentiable vector-valued function 
for 
, 
and
In this expression there are five free parameters defined by the two centre parameters 
and only three of the axis
parameters 
, 
is a position index. The remaining axis parameter can be computed by the orthonormality relationship defined
by: 
. In order to define a relationship between adjacent points in an ellipse we consider the local angular change on the position function. The tangent of the angle of the first and second order derivatives of the position vector 
are
where 
and 
are the first and second derivatives with
respect to 
.
By combining Equations (1) and (3) we obtain a mapping which relates the ellipse centre parameters and angular information
Figure 1: Geometry of two points on an elipse
Figure 2: Geometry of two points on an elipse
A map which relates the axis parameters and angular information is formulated by considering the property of orthonormality of the ellipse axes
where
Therefore, by defining Equations (4) and (5) as
mappings between an image and a parameter space it is possible to compute four ellipse parameters represented by
( 
,
)
and the ratios of
axes 
.
In order to obtain the axes after computing the ratio values, it is necessary to carry out a histogram accumulation process which obtains 
. An expression for the axis component
given an edge point and the values of
,
,
K and N is
for 
defined by
Consequently, by using Equations (4), (5) and (6) it is possible to decompose the parameter space for ellipse extraction into two independent accumulators and a histogram accumulator. This decomposition is based on the local change of a curve defined by the angle of the tangent vector functions 
and 
.
In order to obtain the angle of the first and second order directional derivatives on an edge point P, we consider the positional and directional
information of two arbitrary points 
and 
, by following the ellipse geometry presented in Yuen et al.[9].
Figure 1 shows the geometry of
two ellipse points and the relationship defined by their derivatives. The point P can be obtained by computing the intersection of the line MT with the ellipse. If 
and 
define the positions of the
points
and
, then the value of 
which specifies
the point P is the mean of 
and 
.
By considering of the relationship in Equation (1)
when 
, we obtain the angle of the first and second directional derivatives for the point P
for
and where 
and 
are the tangents of the angle of inclination of a tangent line to the points
and
respectively. This information can be obtained by the change of gradient on an image by using a local edge operator.
By combining Equations (4) and (5) with Equations (9) and (10) we derive an algorithm which accumulates evidence by taking pairs of points from an image. Although Equations (9) and (10) define the angular relationship for arbitrary points, to compute accurate values it is necessary to provide pairs of points for which Equations (9) and (10) do not suffer bias due to discretisation. The error due to discretisation increases when M and T are close. Consequently, we avoid pairing points spaced by less than 25 pixels as well as points whose tangent is similar.
If the centre of the ellipse is within the image, the accumulator 
and the histogram
are congruent to the image space. In order to accumulate evidence of the axis relationship 
in a finite range of values, 
and 
are stored in the second accumulator.
Experimental results have been assessed both on synthetic and real images.
Figure 2(a) shows a 256x256x8-bit real image.
Figure 2(b) shows the results of applying the
Canny edge detector operator and
Figure 2(c) shows the detected ellipse.
A mapping for ellipse extraction has been developed which includes edge tangent information. This mapping combines local information computed from pairs of edge points in order to decompose the space required for the HT and retains the original advantages of the HT. Since we include edge direction information, the proposed method only involves pairs of points without any geometric constraints. An important point in the implementation consists of defining pairs of points which produce accurate information.
Click here to download a PostScript (.ps) copy of the paper.
Click here to download an Acrobat (.pdf) version of the paper.
Click here to request a copy of the Research Journal on CD-ROM.
Copyright (c) 1996 University of Southampton, June 1996.
