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

1、基于Hough 变换的椭圆检测改进算法-电气论文基于Hough变换的椭圆检测改进算法陆路1,梁光明2，丁建文3（1.湘潭大学信息工程学院，湖南湘潭411105 ； 2国防科学技术大学电 子科学与工程学院，湖南长沙 410075 ； 3.爱威科技股份有限公司研发中心，湖 南长沙410013）摘要：在背景复杂的图像中，针对多椭圆检测时椭圆中心定位不准、虚假椭圆过多的缺点，提出一种基于 Hough变换的改进算法。该算法对参数空间 和Hough变换计算的改进提高了椭圆检测的准确度，并利用参数方程判断候选 椭圆的真假。实验结果表明，该检测方法具有较强地抗干扰能力，能够在复杂的环境中准确快速地检测出多个椭

2、圆。关键词 ：Hough变换；椭圆检测；参数方程；检测方法中图分类号：TN911?34 ； TP391.41文献标识码： A文章编号：1004?373X （2015 ） 16?0092?03收稿日期：2015?01?1392在复杂图像中如何快速而准确地检测椭圆目标一直是研究者们努力探索的一个重要问题。这在生物医学显微图像、工业自动化检测、机器人视觉、空 间技术和军事防御等领域有重要的应用。Hough变换是曲线检测最有效的方法 之一，于1962年由Paul Hough提出，并在美国作为专利被发表1。标准Hough 变换（SHT ）的主要特点是：对于图像中局部信息的缺损不敏感，对随机噪声的 鲁棒性

3、；但由于计算量与存储量随着参数空间维数成指数关系增加而难以实用。大量研究致力于改善Hough变换的实用性，并取得了一定的成果。Xu等提出了随机Hough变换（RHT） 2?3。该方法是多到一的映射，避免了标准Hough 变换一到多映射的巨大计算量。但是在处理干扰较多的复杂图像时，RHT的随机采样会引入大量无效采样，大大降低了算法的性能。文献4提出了一种利用椭圆的极点、极弦中点与椭圆中心共线性质的RHT改进方法，但该方法对于多椭圆的检测并不高效。陈燕新等利用梯度信息提出了一种较好地解决无效采样的 RHT改进算法，但对噪声比较敏感。还有一些利用几何特征降低参数空间维 度的方法6?10，如屈稳太提出

4、了一种新的基于弦中点的 Hough变换（CMHT ） 检测方法8，利用椭圆上所有点的内切椭圆必经过椭圆中心的性质，先对图像 边缘点进行累积求得椭圆中心，再利用椭圆方程计算椭圆另外 3个参数；但此方 法在处理背景复杂图像时，会出现检测出椭圆中心位置不准、虚假椭圆较多的情 况。本文在CMHT算法的基础上，提出一种椭圆检测改进算法，用于真实大便 镜检测图像中的虫卵细胞。本文算法对参数空间的计算以及椭圆参数的求解进行 了改进，并结合参数方程进行了虚假椭圆的判断， 从而提高复杂环境下椭圆的检 测精度，降低了误检率。1 CMHT算法原理椭圆一般性方程为：1a1 4 2ZJn + Ct1 + 2bi t 2

5、 r I 0（ 1 I设椭圆中心为（x0，y0），则椭圆方程变为：/式（1）有5个自由参数，文献8中CMHT算法采用2步检测法：第 1步利用弦中点的几何特性投票统计得到关于椭圆中心的 2个参数x0，y0 ;第 2步结合椭圆方程式（2）计算出另外3个参数。1.1基于椭圆中心的投票性质1:在椭圆上任取一点与椭圆上其他点的连线构成椭圆的一组弦，这组弦的中点构成一个新的椭圆，该椭圆称为原椭圆在该点的内切椭圆，如图1（a）所示。性质2 :椭圆上外法线方向相反的2个点称为椭圆的一对对偶点，椭圆 上所有对偶点连线的中点即为椭圆的中心，如图1（ b）所示。由性质1可知椭圆上非对偶点之间连线的中点散布于各处；由

6、性质 2 可知椭圆上所有对偶点连线的中点都集中落在椭圆中心处。另外其余非椭圆上的点即噪声点与其他各点连线的中点也散布于各处，并且落在同一点的可能性很 小。因此如果把原图像边缘二值图中的每一个边缘点都与其他点相连，并对连线的中点在参数空间进行投票统计，则在每个椭圆中心处将出现统计值的峰值， 这 正是Hough变换的基本思想。CMHT算法会遍历参数空间中每个点的统计值， 当某个点的值大于设定的阈值时则认为该点是一个椭圆中心。1.2椭圆参数计算对每个椭圆中心（x0，y0），寻找关于中心对称的3组特征边缘点，代 入式（2）中求解未知参数A，B，Co2本文改进方法当处理复杂图像时，参数空间会出现多个大于

7、设定阈值点的位置接近的 情况，导致检测出较多虚假椭圆中心；且由于干扰点较多，计算出椭圆的另外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(xy) Rmax，则令Q(

8、x,y) = 0 。对处理完参数空间所有点之后，参数空间 的非零点即是极大值点，每个极大值点对应一个候选椭圆中心。设求出的n个候选椭圆中心为Oi (i=1 ，2，n )，对原参数空间H中的每个点O，在其区 域R中寻找统计值大于阈值的点组成点集S，S满足：j S, S e /t 1-15 (t, H A t 0( a , H |,/ a L2.L f式中：比例系数2=0.8，计算点集S的中心坐标0即为椭圆中心的修 正值：O二丄 Y F U 丄 Y1 (:11 I( 4 1I2.2 Hough变换求解椭圆参数为了更准确地计算椭圆参数，可采用Hough变换结合椭圆参数方程求解。在中心点Oi附近寻找关

9、于中心点对称的边缘点进行采样存入数组Vi中。对于任意椭圆，设中心坐标为(x0，y0)，椭圆长半轴长为a，椭圆短半轴长为b， 椭圆倾斜角为9o则参数方程为：sr-+一、, Ipifi|l 一毛al-( -rjrap#arA-1(S)将中心坐标Oi (x0，y0)带入椭圆方程式(5)中，从数组Vi中取出 数据在三维空间中结合式(5)并采用Hough变换对a, b , B进行量化投票统计，求出参数空间最大值对应的 3个参数即为候选椭圆的a， b， 0o2.3虚假椭圆判断对于候选椭圆E (x0 , y0 , a, b , 0),任意点P (x, y)落在椭圆上的 判断公式如下：以点(x0 , y0)为

10、中心选取长方形区域 D , D = (x,y)| x - X。| 日+ 2且| y - y0| b + 2。取T=0.1，若点P(x,y)且满足式(6),则认为该点落在候选椭圆上。在区域 D中计算原图中落在候选椭圆上的实际边缘点数目 N1和组成候选椭圆的边缘点数目N2，因为组成椭圆的点数是随着 a, b变化 而变化的，所以应该以N1 , N2的比值是否大于阈值 入来判断候选椭圆是否为 真，即当N1 N2入时，候选椭圆为真。3实验结果为验证本文算法检测结果，采用 2组图片对本文算法与CMHT算法进 行了对比检测实验，重点对椭圆检测的准确度和速度进行考察。用Matlab 7.6编程实现了本文算法。

11、测试平台为普通 PC机，CPU为PentiumE5300 ，2 GB 内存，操作系统为 Win dows XP。本文的测试程序把检测到的椭圆用红色和绿 色画出，分别表示用CMHT算法和本文算法检测得到的椭圆。第1组实验采用 简单的合成图像如图2所示，图像大小为248 X 180，所需检测椭圆1个。第2 组实验为真实大便镜检图像的一部分如图3所示，图像大小为448 X 350，所需检测虫卵3个。从图2中可以看出，对于简单的图像，2种方法都能正确检测 得到椭圆，CMHT算法速度稍快一些（见表1 ）。但对于图3中背景复杂的大便 镜检图像，特别是图中处于右下方的椭圆有明显遮盖的情况， CMHT算法检测

12、 的椭圆会出现中心位置不准等较大误差， 并且在图像右上方出现误检，而采用本 文算法仍能较快地检测出多个椭圆，并定位准确（见表 2）。由此可见，本文算法在检测精度和误检率上都有很大改善iibhl r Mtn甲M.T忙勿 ；4E|乍女如!听忙掛酩！Ihi:局辰卑此壮屍 l * ibi i 11 1112：IEICMtrr t +52$jKw4)血町1 14OJ 1d“ M tiS3145-71aw. 1201M44114K3452245.7140tiit.si参考文献1 HOUGH V, PAUL C. Method and means for recognizing com?plex patte

13、rns : US, 3069654 P. 1962?12?18.2 XU L, OJ A E. RandomizedHough transform(RHT): Basicmechanisms , algorithms and computational complexities J.ComputerVision Graphic Image Process: Image Understanding, 1993 , 57 (2):131?154.3 XU L , KALVIA I H , HIRVON E P , et al. Probabilistic and non ?probabilisti

14、c Hough transforms: Overview and compari?sons J. Imageand Vision Computing , 1995 , 13 (4): 239?252.4 MCLAUGHLIN R A. Randomized hough transform: Improvedellipse detection with comparison J. Pattern Recognition Let?ters, 1998 ,19 (3/4 ): 299?305.5 陈燕新，戚飞虎.一种新的基于随机Hough变换的椭圆检测方法J. 红外与毫米波学报，2000，19( 1

15、): 43?47.6 KALVIAINEN H ，HIRVONEN P . An extension to the randomizedHoughtran sformexploit ingconn ectivity J. PatternRecog ni ?ti on Letters , 1997 （18）: 77?85.7 于海滨，刘济林.基于中心提取的RHT在椭圆检测中的应用J.计算 机辅助设计与图形学学报，2007，19（ 9）： 110771113.8 屈稳太.基于弦中点Hough变换的椭圆检测方法J.浙江大学学报： 工学版，2005，39（8）： 1132?1196.9 黎自强，滕弘飞.基于局部搜索的多椭