成浩　崔文超

摘要：椭圆检测在图像识别与计算机视觉領域具有重要研究意义。为了对比分析出不同椭圆检测算法的优缺点，提高检测精确度和效率，针对基于Hough变换的椭圆检测4种算法（传统Hough变换方法、几何特征椭圆检测法、弦中点椭圆检测法和三点椭圆检测法）进行仿真，并对不同算法进行有效性分析。通过对检测结果进行客观评价，得出对比结论，并根据实验结果分析不同算法适用的对象。设计了椭圆检测对比分析软件平台，便于进行不同算法的对比分析。

关键词：椭圆检测；Hough变换；对比分析

DOIDOI：10.11907/rjdk.182095

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009011504

英文标题Contrastive Study of Elliptical Detection Based on Hough Transform

——副标题

英文作者CHENG Hao， CUI Wenchao

英文作者单位（College of Computer and Information Technology， China Three Gorges University， Yichang 443000，China）

英文摘要Abstract：Ellipse detection is of great importance in image recognition and computer vision. In this paper， in order to compare and analyze the advantages and disadvantages of different ellipse detection methods and improve the accuracy and efficiency of detecting ellipse from images，four Hough transform based ellipse detection methods have been simulated， including traditional Hough transform method， geometric feature ellipse detection method， string midpoint ellipse detection method and threepoint ellipse detection method. The detection effectiveness regarding different algorithms has been analyzed and tested through the objective evaluation on the experimental results. Finally， the relevant contrastive conclusions are drawn， and the applicable objects of different methods are analyzed. At the same time， a software platform for ellipse detection and comparative analysis is designed to facilitate the comparative analysis of different algorithms.

英文关键词Key Words：ellipse detection； Hough transform； contrastive analysis

0引言

随着计算机视觉技术发展，人们可用计算机从图像中确定椭圆的位置和形状大小，如在数字摄影测量领域， 椭圆检测可提高图像匹配自动化程度和匹配率[1]；在模式识别领域，人脸识别和行人头部的轮廓提取均可采用椭圆检测技术实现[2]。因此，椭圆检测有良好的应用前景，设计椭圆检测对比分析系统对椭圆检测算法的对比分析具有重要意义。

椭圆检测算法主要分为投票（类聚）和最优化两大类。最优化例如最小二乘法[35]，其通过最小误差的平方和寻找符合样本点的最佳函数，此类算法准确度高，但需要预先对数据进行分组处理，不能同时检测多个椭圆。基于Hough变换的算法[69]，运用两个坐标空间之间的变换，将样本点映射到参数空间，然后采用统计投票或建立累加器的方法，在参数空间中寻找峰值确定椭圆。这类算法具有很好的鲁棒性，对噪声的灵敏度低于前述算法。本文对几种基于Hough变换的改进算法进行对比分析。传统Hough变换面对含有五维参数的椭圆检测需要大量的内存空间和复杂的计算，因此降低Hough变换映射的参数维度是提高此类算法运算性能的关键。

大多数学者对椭圆检测的研究集中在样本点收集和降低参数维度方向。杨忠根等[10]详细证明了椭圆的极点-极弦性质，并首次提出利用该性质提取椭圆，陈燕新[11]提出了三点椭圆检测法，在椭圆上随机采样两个点，然后利用极点极弦性质确定另一个采样点，有效避免了无效采样。于海滨等[12]充分利用椭圆的轴对称特性，实现了参数空间累加列阵的降维，极大加快了椭圆检测时间。屈稳太[13]将SHT和RHT结合，提出一种新的基于弦中点的Hough变换检测算法。周祥[14]利用椭圆圆心的性质首先找到圆心，使参数维度降到二维，优化了传统算法。

本文在上述研究基础上，选取3种优化算法，简单阐述其基本检测原理，然后利用MATLAB软件对不同算法的检测效果进行分析比较，得出不同椭圆检测算法的优缺点和各自适用的对象。设计椭圆检测对比分析系统，能更直观方便地对图像检测效果进行评价。

1椭圆检测算法原理

1.1传统椭圆检测

平面上的椭圆用二次曲线方程表示为：

x2+Bxy+Cy2+Dx+Ey+F=0B2-4C<0（1+C）（4CF+BDE-D2C-B2F-E2）<0（1）

由于椭圆含有5个参数，直接采用Hough变换[15]中一对多的映射关系必然带来庞大的计算量。为此Xu等[1617]提出了随机Hough变换（RHT），采用多对一映射，主要思想如下：

假设要检测的椭圆数学模型为f（α，z）=0，这里α=[B，C，D，E，F]，包含5个参数，RHT在图像中随机采样5个点用来构造一个样本，通过求解5个方程组将这个样本映射到5维空间的一点上。若5个参数满足式（1）中的两个不等式，则该点对应的参数空间计数加1，重复上述过程，直至累加器中的计数超过设置的阈值，投票数最多的点对应的就是椭圆参数点。

1.2弦中点椭圆检测法

椭圆的弦中点性质：在椭圆上任取一点，该点与椭圆其它边缘点连接形成一组弦，该组弦的中点构成一个新椭圆，则称新的椭圆是原椭圆在该点处的内切椭圆，如图1所示。在同一个椭圆内，所有内切椭圆都相交椭圆圆心，如图2所示。

由于非椭圆点相连的中点曲线只有很小的概率相交于椭圆圆心，因此在圆心处肯定会有较多的内切椭圆经过，这就是弦中点椭圆检测法的基本思想。该算法步骤如下：先建立一个累加数组，用来存储弦中点坐标，对于图像中的每个边缘点扫描，与其它边缘点中点对应的数组便加一，跳过已经经过计算的边缘点。设置阈值，累加数组的数值大于阈值便认为此处为一个椭圆圆心，确定了圆心后就能用传统Hough变换检测出其它3个参数。

1.3三点椭圆检测法

包括椭圆在内的二次曲线可以利用极点、极弦来定义，以曲线上随机两点P1、P2为切点做两条相交的切线，切线的交点T即为P1和P2的极点，过P1、P2的弦为二次曲线的极弦，根据极点-极弦性质，极点T、极弦的中点和椭圆中心C共线。如图3所示，利用此性质可以在椭圆上随机抽样三点，确定两条过圆心的直线，即可定位出椭圆圆心位置。另外，线段TM和椭圆的交点P3还具有一条性质：该交点处的切线l1平行极弦P1P2。

三点椭圆检测法就是利用上述性质确定椭圆参数。随机采样两个边缘点，以当前边缘点为中心，在一个小的邻域内进行最小二乘拟合，所确定的直线就是该边缘点的切线，若两条切线不平行则可找到交点T，在P1P2中点M与T之间寻找与椭圆的交点P3（若未找到P3，则认为P1，P2不在同一椭圆上，需重新采样），由交点P3处的切线与极弦P1P2平行的性质，确定得到的三点是否在同一椭圆上，这样可避免大量不在同一椭圆上的三点组合，有效排除了传统Hough变换中无效采样问题，即使出现了极少数情况下的误判，由于设置了多组独立的采样且后面还有投票的检验，该虚假点的影响也会被消除。若采样到的三点组P、K、Q在椭圆上，则可利用对应的极弦确定椭圆圆心。

1.4几何特征椭圆检测法

引入一条关于椭圆几何特征的数学定理，该算法就是基于这个定理提出的：任取椭圆平面上的一点p，其距离椭圆边缘点的最大距离一定大于椭圆的长轴，所以圆心是椭圆平面上距椭圆边缘点最大距离最小的点，性质证明参见文献[4]。几何特征椭圆检测法就是通过查找距离椭圆边缘点最大距离最小的点来确定圆心，同时这个最小的最大距离就是椭圆长轴，剩下的两个参数就能在二维参数空间进行统计。

具体算法如下：将要处理的图像进行边缘检测，将边缘图上的点存入数组A中，扫描二维图像上的每个点，计算与数组A中的每个点的距离，所有点中最大距离最小的点便是椭圆圆心，该距离就是椭圆长轴a。然后在二维参数空间对短轴b和角度θ进行统计，得到峰值超过一定阈值的一组参数即为椭圆。

2椭圆检测算法有效性分析

假設在一个图像中有N个特征点，其中有Ni个属于椭圆边缘点，Nf个噪声点，由于椭圆有5个独立参数，所以在传统的Hough变换中需要采样5个椭圆边缘点，而在图像中随机采样的5个点中全部落在椭圆上的概率为：

pvalid=c5Nic5N=Ni（Ni-1）（Ni-2）（Ni-3）（Ni-4）N（N-1）（N-2）（N-3）（N-4）（2）

显然，图像中的噪声点越多，采样的5个点落在椭圆上的概率就越小，无效采样越多，因此需要大量的内存空间和复杂计算。下面讨论改进算法的有效性。

利用三点椭圆检测法只需要2个有效采样点，则2点落在椭圆上的概率为：

p1=c2Nic2N=Ni（Ni-1）N（N-1）（3）

同样条件下，利用弦中点椭圆检测法，图像中有Nline=N（N-1）/2条线段，每条线段对应一个中点，但只有两个椭圆点连接的线段才对应椭圆圆心，则有效采样线段有Nvalid=Ni（Ni-1）/2线段，采样到有效中点的概率为：

p2=NvalidNline=Ni（Ni-1）N（N-1）（4）

对于几何特征椭圆检测法，大小为m×n的图像中每一个像素点与每一个特征点的距离计算次数为m×n×N，与椭圆边缘点的距离计算次数为m×n×Ni，则有效计算的概率为：

p3=m×n×Nim×n×N=NiN（5）

由表1可知，弦中点椭圆检测法和三点椭圆检测法都能大大提高有效采样概率，几何特征椭圆检测法在低信噪比情况下有效性较高。由于确定中心点需要准确的长轴信息，因此当椭圆内部的噪声点过多时会严重影响算法性能，导致算法失效。

3检测结果对比

为了测试3种椭圆检测算法性能，采用一组相同图片作为仿真图像，其大小为450×320，运用MATLAB软件编程实现检测试验，试验环境为Window10操作系统，Intel Core-i5主频为1.65 GHz处理器，内存为4 GB，不同的检测效果如图5所示。

仅从检测结果参数难以分析出不同算法间的差异，因此有必要引入两种综合测度。

4定量比较

在评价不同检测算法性能时，本文采用相似度与逼近度两种综合测度对检测结果进行定量分析。

（1）相似度S定义为：

S=[∑（x，y）E（x+i，y+i）]/dotR（6）

式（6）中dotR是区域内总的边缘点数目。

E（x+i，y+i）=1，点（x，y）在理想椭圆上有近似点0，点（x，y）在理想椭圆上无近似点 （7）

（2）逼近度D的定义为：

D=∑id（pi，c）/∑jd（pj，c）（8）

式（8）中：d（pi，c）是检测到的轮廓点集合中点pi与椭圆圆心的距离，d（pj，c）是椭圆边缘点集合中点pj与椭圆中心的距离。

进行仿真实验后检测出的椭圆相似度与逼近度计算结果如表3所示。

从表3数据可以看出，3种优化算法相比随机Hough变换在拟合准确度与耗时上都有很大提高。不同算法拟合准确度从高到低依次为：弦中点椭圆检测法、几何特征椭圆检测法、三点椭圆检测法。3种算法在实验中耗时也不相同，几何特征椭圆检测法耗时最少，弦中点椭圆检测法其次，三点椭圆检测法用时最长。

5综合分析

弦中点椭圆检测法更多考虑的是算法有效性问题，充分利用了椭圆内切圆必过中心点的性质，降低了传统Hough变换中无效采样概率，确保每次收敛映射结果一定是椭圆，从而在保证算法精度的前提下显著提高了效率。

三点椭圆检测法确保采样的三点组一定在椭圆上，使RHT每次的收敛映射结果都为椭圆参数，另外该算法对边缘数据集合的要求相当低，允许边缘不连续且含有一定比例的假边缘，所以此算法应用范围很广，对于一些较为复杂的图像检测效果优于其余两种算法。但此算法要求在采样点处有理想的边缘梯度方向，对采样点选择较为严格，因此算法耗时较长。当椭圆形变较大时，其检测效果下降。

几何特征椭圆检测法利用椭圆中心的几何性质对图像进行过滤，获得可能的椭圆中心位置，将计算复杂度下降到了两维，大大减少了运算时间和所需的参数空间，实现了椭圆特征的快速提取，且不受椭圆外部杂乱图像的影响，在处理噪声点较少的图像时很有效。但该算法对椭圆内部噪声敏感，因此适用于处理低信噪比下的简单图像。

为了更加方便地比较3种算法的优劣，设计了椭圆检测对比分析系统帮助分析。该系统不仅便于对检测效果进行对比，还能在参数区显示检测椭圆的参数及两种综合测度值。系统启动界面设有标题区、显示区、椭圆检测参数精准度比较区、控制区和算法选择区5大区域，界面简洁明了，操作方便，具有实验所需的基本功能。检测出的椭圆用红线圈出，与原图像都显示在显示区，从而能客观评价算法精确度。椭圆检测对比分析系统初始界面如图6所示。

6结语

本文阐述了4种主要的椭圆检测算法基本原理，并利用MATLAB软件编程实现了不同算法对图像的检测。根据检测结果对比，分析不同算法的优缺点与各自适用的图像，在实际中根据需要选择合适的算法。

对基于Hough变换的椭圆检测算法，大部分学者都在降低参数维度方面进行了深入研究，但都不可避免地出现计算量大、耗时长等问题。而在直线检测方面，已有学者提出将Hough变换与最小二乘法相结合的直线拟合算法[1820]，充分利用Hough变换抗噪声能力强和最小二乘法拟合精度高的特點，为椭圆检测研究带来了有益启示。将Hough变换与最小二乘法相结合用于椭圆检测是一个新的研究思路。

参考文献参考文献：

[1]齐晓娟，董明利，王君，等.数字摄影测量中椭圆的高效检测方法[J].北京机械工业学院学报，2005（4）：57.

[2]薛源，李艳萍.人脸识别技术的探讨和研究[J].机械管理开发，2010，25（5）：3941.

[3]别秀德，彭志勇.基于改进最小二乘法的一种椭圆检测与定位方法[J].可编程控制器与工厂自动化，2015（7）：99102.

[4]吕洪赫，姚振杰，易卫东.基于对称性的最小二乘拟合随机椭圆检测算法[J].电子测量技术，2011，34（5）：3741.