基于Hough变换的椭圆检测改进算法
2015-11-17陆路梁光明丁建文
陆路+梁光明+丁建文
摘 要： 在背景复杂的图像中，针对多椭圆检测时椭圆中心定位不准、虚假椭圆过多的缺点，提出一种基于Hough变换的改进算法。该算法对参数空间和Hough变换计算的改进提高了椭圆检测的准确度，并利用参数方程判断候选椭圆的真假。实验结果表明，该检测方法具有较强地抗干扰能力，能够在复杂的环境中准确快速地检测出多个椭圆。
关键词： Hough变换； 椭圆检测； 参数方程； 检测方法
中图分类号： TN911?34； TP391.41 文献标识码： A 文章编号： 1004?373X（2015）16?0092?03
An improved algorithm of ellipse detection base on Hough transform
LU Lu1， LIANG Guangming2， DING Jianwen3
（1. College of information Engineering， Xiangtan University， Xiangtan 411105， China；
2. School of Electronic Science and Engineering， National University of Defense Technology， Changsha 410075， China；
3. R & D Center， AVE Technology Co.， Ltd， Changsha 410013， China）
Abstract： An improved algorithm based on Hough transform is proposed for detection of multi ellipses in image with complicated background to cope with the problems of inaccurate position of the ellipse center and overmuch pseudo ellipse. The accuracy of the ellipse detection is improved through the developed calculation of parameter space and Hough transform. The true ellipse is distinguished from the pseudo candidate ellipses by using the parameter equation. The experimental results show that the detection method can detect multiple ellipses in the complex environment quickly and accurately， and has strong anti?interference ability.
Keywords： Hough transform； ellipse detection； parameter equation； detection method
在复杂图像中如何快速而准确地检测椭圆目标一直是研究者们努力探索的一个重要问题。这在生物医学显微图像、工业自动化检测、机器人视觉、空间技术和军事防御等领域有重要的应用。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算法原理
椭圆一般性方程为：
[Ax2+2Bxy+Cy2+2Dx+2Ey+1=0] （1）
设椭圆中心为（x0，y0），则椭圆方程变为：
[Ax-x02+2Bx-x0y-y0+Cy-y02+1=0] （2）
式（1）有5个自由参数，文献[8]中CMHT算法采用2步检测法：第1步利用弦中点的几何特性投票统计得到关于椭圆中心的2个参数x0，y0；第2步结合椭圆方程式（2）计算出另外3个参数。
1.1 基于椭圆中心的投票
性质1：在椭圆上任取一点与椭圆上其他点的连线构成椭圆的一组弦，这组弦的中点构成一个新的椭圆，该椭圆称为原椭圆在该点的内切椭圆，如图1（a）所示。endprint
性质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，若某点统计值[Qx，y>Rmax]，则令[Rmax=Qx，y]，[Px，y=0]；若某点统计值[Qx，y≤Rmax]，则令[Qx，y=0]。对处理完参数空间所有点之后，参数空间的非零点即是极大值点，每个极大值点对应一个候选椭圆中心。设求出的n个候选椭圆中心为[Oi]（i=1，2，…，n），对原参数空间H中的每个点O，在其区域R中寻找统计值大于阈值的点组成点集S，S满足：
[SjSj∈R且Sjx，y>λ?Ox，y， j=1，2，…，m] （3）
式中：比例系数λ=0.8，计算点集S的中心坐标O′ 即为椭圆中心的修正值：
[O′=1mj=1mSj=1mj=1mxj，yj] （4）
2.2 Hough变换求解椭圆参数
为了更准确地计算椭圆参数，可采用Hough变换结合椭圆参数方程求解。在中心点Oi附近寻找关于中心点对称的边缘点进行采样存入数组Vi中。对于任意椭圆，设中心坐标为（x0，y0），椭圆长半轴长为a，椭圆短半轴长为b，椭圆倾斜角为θ。则参数方程为：
[x-x0cosθ+y-y0sinθ2a2+x-x0sinθ-y-y0cosθ2b2=1] （5）
将中心坐标Oi（x0，y0）带入椭圆方程式（5）中，从数组Vi中取出数据在三维空间中结合式（5）并采用Hough变换对a，b，θ进行量化投票统计，求出参数空间最大值对应的3个参数即为候选椭圆的a，b，θ。
2.3 虚假椭圆判断
对于候选椭圆E（x0，y0，a，b，θ），任意点P（x，y）落在椭圆上的判断公式如下：
[x-x0cosθ+y-y0sinθ2a2+x-x0sinθ-y-y0cosθ2b2-1 以点（x0，y0）为中心选取长方形区域D，[D=x，yx-x0≤a+2且y-y0≤b+2]。取T=0.1，若点[Px，y∈D]且满足式（6），则认为该点落在候选椭圆上。在区域D中计算原图中落在候选椭圆上的实际边缘点数目N1和组成候选椭圆的边缘点数目N2，因为组成椭圆的点数是随着a，b变化而变化的，所以应该以N1，N2的比值是否大于阈值λ来判断候选椭圆是否为真，即当[N1N2>λ]时，候选椭圆为真。 3 实验结果 为验证本文算法检测结果，采用2组图片对本文算法与CMHT算法进行了对比检测实验，重点对椭圆检测的准确度和速度进行考察。用Matlab 7.6编程实现了本文算法。测试平台为普通PC机，CPU为Pentium E5300，2 GB内存，操作系统为Windows XP。本文的测试程序把检测到的椭圆用红色和绿色画出，分别表示用CMHT算法和本文算法检测得到的椭圆。第1组实验采用简单的合成图像如图2所示，图像大小为248×180，所需检测椭圆1个。第2组实验为真实大便镜检图像的一部分如图3所示，图像大小为448×350，所需检测虫卵3个。从图2中可以看出，对于简单的图像，2种方法都能正确检测得到椭圆，CMHT算法速度稍快一些（见表1）。但对于图3中背景复杂的大便镜检图像，特别是图中处于右下方的椭圆有明显遮盖的情况，CMHT算法检测的椭圆会出现中心位置不准等较大误差，并且在图像右上方出现误检，而采用本文算法仍能较快地检测出多个椭圆，并定位准确（见表2）。由此可见，本文算法在检测精度和误检率上都有很大改善。 图2 简单图像的检测 图3 真实大便镜检图像的检测 表1 2种算法对图2处理的结果对比 4 结 语 本文提出了一种基于Hough变换的椭圆检测改进算法。利用对参数空间、椭圆参数计算的改进和虚假椭圆的判断，提高了椭圆检测准确度。由实验结果可以看出，即使在背景复杂的图像中，本文的改进算法也能准确快速地检测各个椭圆的参数，运算速度快，检测性能好，抗干扰性强，具有一定的实用性。 表2 2种算法对图3处理的结果对比
参考文献
[1] HOUGH V， PAUL C. Method and means for recognizing complex 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 comparisons [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 Letters， 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 Recognition 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.endprint
