CIRCULAR ARE EXTRACTION BY DIRECT CLUSTERING IN A 3D HOUGH PARAMETER SPACE

The Hough transform is a robust technique for analysis of straight lin es in images containing noise and occlusions, but involves a considera ble computational load and storage problems when it is used to recover circles, ellipses or more complex patterns. This paper presents an ef ficient technique for circular are detection, called the circular dire ct Hough transform (CDHT), which aims to reduce the drawbacks affectin g classical Hough-based approaches (i.e., low speed, loss of spatial i nformation, and spurious-peak generation) without increasing the memor y requirements. A modified parametrization is used to represent a circ le by a couple of dependent equations of the first order (instead of t he classical equation of the second order (x - x(0))(2)+(y-y(0))(2)-r( 2)=0) and a clustering phase is introduced to detect different circula r arcs belonging to the same circle. Results are reported to describe and quantify the performances of the CDHT in terms of accuracy, robust ness to noise, computational efficiency, and storage. Comparisons are made between the proposed method and some representative Hough-based a lgorithms (Yip et al., 1992; Duda and Hart, 1972), using both syntheti c and real images. Circle detection in crowd images, where circular pa tterns are associated with human heads, is described as an application to show the robustness of the method.