Robust Real-Time Multi-Circle Detection Algorithm Based on 1D Probabilistic Hough Transform

The state of the art in circle detection usually resorts to edge pixels as the voting components to perform parametric accumulation in 2D or 3D space, which generally incurs high computational cost and is thus unable to meet the real-time processing requirements in complex natural scene processing. Using edge sections as voting components, this paper presents a robust real-time circle detection algorithm based on 1D probabilistic Hough Transform. The algorithm first segments Canny edges based on their gradient directions into arc sections, from which seed sections meeting certain curvature criteria are selected. For each seed, a probability-weighted 1D Hough accumulation is then built along the radius dimension to detect a valid circle related to the seed and estimate the initial radius of the circle based on the peak magnitude and peak position of the 1D accumulation. Finally direct circular least square fitting is employed to further pinpoint the radius and center information for the detected circle. The experiment shows, when appropriate segmentation thresholds are chosen, the algorithm significantly outperforms the state of the art in processing speed while maintaining high reliability as far as the circle detection in complex natural scene images is concerned.