基于Hough变换的椭圆检测改进算法

陆路1，梁光明2，丁建文3

（1.湘潭大学信息工程学院，湖南湘潭411105；2.国防科学技术大学电子科学与工程学院，湖南长沙410075；3.爱威科技股份有限公司研发中心，湖南长沙410013）

摘要：在背景复杂的图像中，针对多椭圆检测时椭圆中心定位不准、虚假椭圆过多的缺点，提出一种基于Hough变换的改进算法。该算法对参数空间和Hough变换计算的改进提高了椭圆检测的准确度，并利用参数方程判断候选椭圆的真假。实验结果表明，该检测方法具有较强地抗干扰能力，能够在复杂的环境中准确快速地检测出多个椭圆。

教育期刊网 http://www.jyqkw.com
关键词 ：Hough变换；椭圆检测；参数方程；检测方法

中图分类号：TN911?34；TP391.41 文献标识码：A 文章编号：1004?373X（2015）16?0092?03

收稿日期：2015?01?1392

在复杂图像中如何快速而准确地检测椭圆目标一直是研究者们努力探索的一个重要问题。这在生物医学显微图像、工业自动化检测、机器人视觉、空间技术和军事防御等领域有重要的应用。Hough 变换是曲线检测最有效的方法之一，于1962年由Paul Hough提出，并在美国作为专利被发表[1]。标准Hough变换（SHT）的主要特点是：对于图像中局部信息的缺损不敏感，对随机噪声的鲁棒性；但由于计算量与存储量随着参数空间维数成指数关系增加而难以实用。大量研究致力于改善Hough变换的实用性，并取得了一定的成果。Xu等提出了随机Hough变换（RHT）[2?3]。该方法是多到一的映射，避免了标准Hough变换一到多映射的巨大计算量。但是在处理干扰较多的复杂图像时，RHT 的随机采样会引入大量无效采样，大大降低了算法的性能。文献[4]提出了一种利用椭圆的极点、极弦中点与椭圆中心共线性质的RHT 改进方法，但该方法对于多椭圆的检测并不高效。陈燕新等利用梯度信息提出了一种较好地解决无效采样的RHT改进算法[5]，但对噪声比较敏感。还有一些利用几何特征降低参数空间维度的方法[6?10]，如屈稳太提出了一种新的基于弦中点的Hough变换（CMHT）检测方法[8]，利用椭圆上所有点的内切椭圆必经过椭圆中心的性质，先对图像边缘点进行累积求得椭圆中心，再利用椭圆方程计算椭圆另外3个参数；但此方法在处理背景复杂图像时，会出现检测出椭圆中心位置不准、虚假椭圆较多的情况。本文在CMHT算法的基础上，提出一种椭圆检测改进算法，用于真实大便镜检测图像中的虫卵细胞。本文算法对参数空间的计算以及椭圆参数的求解进行了改进，并结合参数方程进行了虚假椭圆的判断，从而提高复杂环境下椭圆的检测精度，降低了误检率。

1 CMHT 算法原理

椭圆一般性方程为：

设椭圆中心为（x0，y0），则椭圆方程变为：

式（1）有5 个自由参数，文献[8]中CMHT 算法采用2 步检测法：第1步利用弦中点的几何特性投票统计得到关于椭圆中心的2个参数x0，y0；第2步结合椭圆方程式（2）计算出另外3个参数。

1.1 基于椭圆中心的投票

性质1：在椭圆上任取一点与椭圆上其他点的连线构成椭圆的一组弦，这组弦的中点构成一个新的椭圆，该椭圆称为原椭圆在该点的内切椭圆，如图1（a）所示。

性质2：椭圆上外法线方向相反的2个点称为椭圆的一对对偶点，椭圆上所有对偶点连线的中点即为椭圆的中心，如图1（b）所示。

由性质1 可知椭圆上非对偶点之间连线的中点散布于各处；由性质2可知椭圆上所有对偶点连线的中点都集中落在椭圆中心处。另外其余非椭圆上的点即噪声点与其他各点连线的中点也散布于各处，并且落在同一点的可能性很小。因此如果把原图像边缘二值图中的每一个边缘点都与其他点相连，并对连线的中点在参数空间进行投票统计，则在每个椭圆中心处将出现统计值的峰值，这正是Hough变换的基本思想。CMHT算法会遍历参数空间中每个点的统计值，当某个点的值大于设定的阈值时则认为该点是一个椭圆中心。

1.2 椭圆参数计算

对每个椭圆中心（x0，y0），寻找关于中心对称的3组特征边缘点，代入式（2）中求解未知参数A，B，C。

2 本文改进方法

当处理复杂图像时，参数空间会出现多个大于设定阈值点的位置接近的情况，导致检测出较多虚假椭圆中心；且由于干扰点较多，计算出椭圆的另外3个参数会出现较大误差。因此根据出现的问题本文算法增加了以下3点改进。

2.1 参数空间计算的改进

检测参数空间统计值的极大值点作为椭圆中心，并根据极大值附近多个较大值点对中心点坐标进行修正。设参数空间H，根据先验知识取椭圆长半轴长为a，对参数空间任意点P，设以该点为中心，边长为2a 的方形块为局部区域R。先假设P 点统计值P（x，y）为区域R的极大值Rmax。遍历区域R，若某点统计值Q(x,y) > Rmax ，则令Rmax = Q(x,y) ，P(x,y) = 0 ；若某点统计值Q(x,y) ? Rmax ，则令Q(x,y) = 0 。对处理完参数空间所有点之后，参数空间的非零点即是极大值点，每个极大值点对应一个候选椭圆中心。设求出的n 个候选椭圆中心为Oi（i=1，2，…，n），对原参数空间H 中的每个点O，在其区域R 中寻找统计值大于阈值的点组成点集S，S 满足：

式中：比例系数λ=0.8，计算点集S 的中心坐标O′ 即为椭圆中心的修正值：

2.2 Hough变换求解椭圆参数

为了更准确地计算椭圆参数，可采用Hough变换结合椭圆参数方程求解。在中心点Oi附近寻找关于中心点对称的边缘点进行采样存入数组Vi中。对于任意椭圆，设中心坐标为（x0，y0），椭圆长半轴长为a，椭圆短半轴长为b，椭圆倾斜角为θ。则参数方程为：

将中心坐标Oi （x0，y0）带入椭圆方程式（5）中，从数组Vi中取出数据在三维空间中结合式（5）并采用Hough变换对a，b，θ进行量化投票统计，求出参数空间最大值对应的3个参数即为候选椭圆的a，b，θ。

2.3 虚假椭圆判断

对于候选椭圆E（x0，y0，a，b，θ），任意点P（x，y）落在椭圆上的判断公式如下：

以点（x0，y0）为中心选取长方形区域D，D = {(x,y)|| x - x0 | } ? a + 2且| y - y0 | ? b + 2 。取T=0.1，若点P(x,y)∈D 且满足式（6），则认为该点落在候选椭圆上。在区域D 中计算原图中落在候选椭圆上的实际边缘点数目N1 和组成候选椭圆的边缘点数目N2，因为组成椭圆的点数是随着a，b 变化而变化的，所以应该以N1，N2的比值是否大于阈值λ来判断候选椭圆是否为真，即当N1 N2 > λ 时，候选椭圆为真。

3 实验结果

为验证本文算法检测结果，采用2组图片对本文算法与CMHT算法进行了对比检测实验，重点对椭圆检测的准确度和速度进行考察。用Matlab 7.6编程实现了本文算法。测试平台为普通PC 机，CPU 为PentiumE5300，2 GB内存，操作系统为Windows XP。本文的测试程序把检测到的椭圆用红色和绿色画出，分别表示用CMHT算法和本文算法检测得到的椭圆。第1组实验采用简单的合成图像如图2所示，图像大小为248×180，所需检测椭圆1个。第2组实验为真实大便镜检图像的一部分如图3 所示，图像大小为448×350，所需检测虫卵3 个。从图2中可以看出，对于简单的图像，2种方法都能正确检测得到椭圆，CMHT 算法速度稍快一些（见表1）。但对于图3中背景复杂的大便镜检图像，特别是图中处于右下方的椭圆有明显遮盖的情况，CMHT算法检测的椭圆会出现中心位置不准等较大误差，并且在图像右上方出现误检，而采用本文算法仍能较快地检测出多个椭圆，并定位准确（见表2）。由此可见，本文算法在检测精度和误检率上都有很大改善。

4 结语

本文提出了一种基于Hough 变换的椭圆检测改进算法。利用对参数空间、椭圆参数计算的改进和虚假椭圆的判断，提高了椭圆检测准确度。由实验结果可以看出，即使在背景复杂的图像中，本文的改进算法也能准确快速地检测各个椭圆的参数，运算速度快，检测性能好，抗干扰性强，具有一定的实用性。

教育期刊网 http://www.jyqkw.com
参考文献

[1] HOUGH V，PAUL C. Method and means for recognizing com?plex patterns：US，3069654 [P]. 1962?12?18.

[2] XU L，OJ A E. Randomized Hough transform（RHT）：Basic mechanisms， algorithms and computational complexities [J].Computer Vision Graphic Image Process ：Image Understanding，1993，57（2）：131?154.

[3] XU L，KALVIA I H，HIRVON E P，et al. Probabilistic and non ? probabilistic Hough transforms ：Overview and compari?sons [J]. Image and Vision Computing，1995，13（4）：239?252.

[4] MCLAUGHLIN R A. Randomized hough transform：Improved ellipse detection with comparison [J]. Pattern Recognition Let?ters，1998，19（3/4）：299?305.

[5] 陈燕新，戚飞虎.一种新的基于随机Hough变换的椭圆检测方法[J].红外与毫米波学报，2000，19（1）：43?47.

[6] KALVIAINEN H，HIRVONEN P. An extension to the randomized Hough transform exploiting connectivity [J]. Pattern Recogni?tion Letters，1997（18）：77?85.

[7] 于海滨，刘济林.基于中心提取的RHT 在椭圆检测中的应用[J].计算机辅助设计与图形学学报，2007，19（9）：1107?1113.

[8] 屈稳太.基于弦中点Hough变换的椭圆检测方法[J].浙江大学学报：工学版，2005，39（8）：1132?1196.

[9] 黎自强，滕弘飞.基于局部搜索的多椭圆随机检测算法[J].计算机工程与应用，2006（12）：9?12.

[10] 周祥，孔晓东，曾贵华.一种新的基于Hough变换的椭圆轮廓检测方法[J].计算机工程，2007，33（16）：166?171.

作者简介：陆路（1988—），男，湖南衡阳人，工程师，硕士。主要研究方向为图像处理。

梁光明（1970—），男，湖南涟源人，副教授，硕士生导师，博士。主要研究方向为图像处理、现代通信与信息安全。

丁建文（1957—），男，湖南岳阳人。主要研究方向为机器视觉、检测识别。