A New Hough Transform Mapping for Ellipse Detection

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., Pao et al., Yoo and Sethi, Wu and Wang, Ho and Chen) 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 approac