基于凸包的椭圆检测方法

Ellipse detection approach based on convex hull

用于检测曲线的Hough变换及其改进方法都不同程度存在运算速度慢、需要大量的储存空间等缺点,因此本文利用椭圆的几何性质降低检测的时间及空间需求,提出了用凸包的方法和Pascal定理来进行椭圆检测。首先从边缘点中随机挑选六个点,进行凸包检测,并将此六点排序;然后利用Pascal定理来判断此六点是否来自同一个椭圆,随后利用拟合得方法求出候选椭圆参数,最后利用包含凸包的最小矩形内的边缘点对超过阈值的累加参数进行验证。实验结果表明,文中算法能快速检测图中的单个或者多个椭圆,并且在具有噪声的情况下,与改进的随机Hough变换算法相比,其检测速度快一倍左右。

Hough Transform （HT） and its variants have the disadvantages of computational slowness and large memory space, In this paper, those requirements were reduced by geometrical feature of ellipse, and a method using convex hull and Pascal theorem was proposed. First, six pixels were randomly selected from the edge map of input image. After confirming they constructed a convex hull and came from the same ellipse using Pascal Theorem, and LMS fitting method was applied to compute parameters of candidate ellipse, Finally, edge points in the minimum rectangle containing convex hull were used to verify the candidate ellipse. The experimental results demonstrate that the approach can quickly detect single or multiple ellipse with noises, The detection speed is an order of magnitude faster than that of improved random Hough transform.