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

The Hough transform is a robust technique for analysis of straight lines in images containing noise and occlusions, but involves a considerable computational load and storage problems when it is used to recover circles, ellipses or more complex patterns. This paper presents an efficient technique for circular are detection, called the circular direct Hough transform (CDHT), which aims to reduce the drawbacks affecting classical Hough-based approaches (i.e., low speed, loss of spatial information, and spurious-peak generation) without increasing the memory requirements. A modified parametrization is used to represent a circle by a couple of dependent equations of the first order (instead of the 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 circular arcs belonging to the same circle. Results are reported to describe and quantify the performances of the CDHT in terms of accuracy, robustness to noise, computational efficiency, and storage. Comparisons are made between the proposed method and some representative Hough-based algorithms (Yip et al., 1992; Duda and Hart, 1972), using both synthetic and real images. Circle detection in crowd images, where circular patterns are associated with human heads, is described as an application to show the robustness of the method.