An efficient randomized algorithm for detecting circles

Detecting circles from a digital image is very important in shape recogniti on. In this paper, an efficient randomized algorithm (RCD) for detecting ci rcles is presented, which is not based on the Hough transform (HT). Instead of using an accumulator for saving the information of the related paramete rs in the HT-based methods, the proposed RCD does not need an accumulator. The main concept used in the proposed RCD is that we first randomly select four edge pixels in the image and define a distance criterion to determine whether there is a possible circle in the image: after finding a possible c ircle, we apply an evidence-collecting process to further determine whether the possible circle is a true circle or not. Some synthetic images with di fferent levels of noises and some realistic images containing circular obje cts with some occluded circles and missing edges have been taken to test th e performance. Experimental results demonstrate that the proposed RCD is fa ster than other HT-based methods for the noise level between the light leve l and the modest level. For a heavy noise level, the randomized HT could be faster than the proposed RCD, but at the expense of massive memory require ments. (C) 2001 Academic Press.