一种新的不基于Hough变换的随机椭圆检测算法

A New non-HT-based Randomized Algorithm for Detecting Ellipses

椭圆检测在模式识别领域中占据着非常重要的位置。常见的基于Hough变换的椭圆检测算法(如RHT算法)存在着占用大量存储空间及计算耗时等缺点。本文提出一种高效随机的椭圆检测算法(RED)。该算法不基于Hough变换,其原理是:首先从一幅图像中随机地挑选出6个点,并定义一个约束距离以确定在此图像中是否存在一个可能的椭圆;当可能椭圆确定之后,引入椭圆点收集过程以进一步确定可能椭圆是否是待检测的真实椭圆。通过对具有不同噪声的合成图像以及真实图像进行测试,结果表明RED算法在低噪声与适度噪声的情况下,速度明显快于RHT算法。

Detecting ellipses from a digital image is very important in pattern recognition. Algorithms for detecting ellipses based on the Hough transform （HT）, such as RHT, with the defects of large requirement of the storage and more computing time needed. In this paper, an efficient randomized algorithm （RED） for detecting ellipses is presented, which is not based on the Hough transform （HT）. The main concept of the RED is that we first randomly select six edge pixels in the image and define a distance criterion to determine whether there is a possible ellipse in the image; after finding a possible ellipse, we use an ellipse＇s pixels-eollecting process to further determine whether the possible ellipse is a true ellipse or not. Then we apply the synthetic images with different levels of noises and two realistic images to do the work. Experimental results demonstrate that the proposed RED is faster than RHT methods between the light noise level and the modest noise level.