一种新的高速圆形匹配算法

黄廉真，吴晓军，康文雄

(1.哈尔滨工业大学深圳研究生院，518055 深圳广东;2.华南理工大学自动化科学与工程学院，510640 广州)

一种新的高速圆形匹配算法

黄廉真1，吴晓军1，康文雄2

(1.哈尔滨工业大学深圳研究生院，518055 深圳广东;2.华南理工大学自动化科学与工程学院，510640 广州)

针对现有圆形匹配算法无法同时满足高速度、低内存消耗以及高精度要求的情况，提出了一种基于击中率的新型圆形匹配算法.算法引入以轮廓作为匹配特征信息的圆环采样模板，匹配的结果由击中率表征，并进一步根据搜索目标与定位区域的灰度相关性剔除误检对象.实验表明，算法能够实现毫秒级快速定位，且在内存消耗和可靠性方面都获得较好的性能.

高速目标定位;圆形匹配;击中率

图像及视频中的圆形匹配是计算机视觉技术中的一项重要研究内容，广泛应用于目标识别、视频跟踪、工件定位等领域.根据算法实现基本原理的不同，圆形匹配算法可分为Hough变换和模板匹配两类.以标准Hough变换(SHT)为基础，研究人员提出了众多改进算法，例如改进Hough变换(IHT)［1－2］、随机 Hough 变换(RHT)［3］、3 点椭圆检测算法［4－5］、利用梯度方向信息检测圆算法［6］以及基于子图分解的多圆/椭圆检测算法［7］等.然而，由于处理对象为大量的轮廓信息，故都会存在运算量大和内存消耗大两方面的不足.模板匹配在目标识别和精确定位等领域中具有广泛应用，根据匹配信息的不同，模板匹配算法有基于灰度相关和基于几何特征两类.基于灰度相关算法根据图像灰度信息进行匹配，算法原理简单，但其抗干扰性差.基于几何特征的模板匹配算法以模板的几何基元［8－9］，如边缘、角点、模板重心等作为匹配信息进行匹配.如基于Hausdorff距离的模板匹配算法［10］和基于广义霍夫变换的模板匹配算法［11］等，此类算法的鲁棒性很强，模板匹配算法的实用性强，但其运算量大.为此，模板匹配算法经常利用金字塔分割法来提高计算速度，然而这样也带来了内存消耗剧增的问题.

针对上述问题，本文提出基于击中率的圆形匹配算法，算法基于图形轮廓信息实现快速图形匹配和定位，算法引入圆环采样模板、矩形采样区和击中率概念，运算则以整型加减运算和逻辑运算为主.计算量几乎恒定，与图像的复杂度和需要检测的目标的数量和大小无关;而且需要搜索的目标圆的半径越大，则运算速度越快.算法具有快速识别定位、低内存消耗、高稳定性的特点，并具有一定鲁棒性，属于基于几何特征的模板匹配算法范畴.实验证明，算法能够取得耗时“毫秒级”的效果，同时在内存消耗等方面也具有较好的性能.

1 算法原理

1.1 圆环采样模板

圆环采样模板由两个同心圆构成圆环，在圆环内有n个等距分布的矩形采样区，即

式中:r为小圆半径;R为大圆半径;(x，y)为圆心坐标.h为矩形采样区的高;w为宽;(xi，yi)为n个矩形采样区中心.

图1是一个由8个矩形采样区构成的圆环采样模板，其中对称的灰色矩形为矩形采样区.圆环采样模板是以圆心为原点，所有矩形采样区内点的坐标集合.

图1 圆环采样模板

1.2 击中率

本文通过n点确定一个圆，圆环采样模板的每一个矩形采样区内第1个被检测到的轮廓点都被认为关键点，同时认为该矩形采样区被击中.当在图2中灰色矩形采样区内找到关键点后，该矩形采样区内其他所有的点都将被忽略，无论这些点是否为轮廓点，同时认为在圆环采样模板的圆环内有目标圆弧长l，如图2所示.

当圆环采样模板有m个矩形采样区被击中，则击中率ρ为

图2 矩形采样区被击中示意图

理想情况下，当被检测图形的中心与圆环采样模板的圆心重合且半径满足要求，则击中率必为1.否则，击中率就会比较低，如图3所示.圆环采样模板的大圆和小圆的半径差越小，其筛检能力越强.

图3 各种情况下圆环采样模板的击中率

1.3 遮断容忍性

遮断容忍性，是指算法允许轮廓点部分丢失和图形被部分遮挡.设丢失的轮廓点总数为s，丢失率为σ.

根据击中率的分析，当要求击中率为1时，仅需要每个矩形采样区中都包含有至少一个轮廓点，其他的轮廓点则可忽略.因此，极限情况下

也即是n点确定一个圆，图4中4个示例的击中率分别为 1，0.875，1，1.图 4 表明即使轮廓点部分丢失也能准确检测对象.当图形被部分遮挡时，算法可通过降低击中率阈值实现对象的检测值，典型情况如图4(b)所示.

图4 模板在不同丢失轮廓情况下对圆的检测示意图

根据圆环采样模板的遮断容忍性，合理设置圆环采样模板的参数以及击中率阈值，可以使得算法在恶劣情况下依然能够检测目标.

2 快速圆定位实现流程

本文通过采用C++语言实现算法，并对50幅大小为640*480的各异图像进行测试，验证算法的性能.图5(a)为其中一幅待处理图像，图像中有半径各异的待检测3个同心圆，如图5(b)～(d)所示.

图5 试验图片以及3个待检测的半径不等近似圆

算法实现流程为:

1)对图片进行一定比率p的缩放，减少运算量.p主要由模板参数以及实际应用的计算时间要求决定.同时为了确保在缩放后R＞r，p必须满足p≤(R-r)/2.p越小，则内存消耗越小，速度越快，但精确度和准确性同时也减弱.本文设p为4.图像的缩放方式采用如图6所示的方式，即取左上角P11替代整个区域.

图6 缩放比率为4的示意图

2)对缩放后的图像采用Canny检测算子提取图像轮廓信息.

3)根据设置的圆环采样模板参数构建圆环采样模板.

4)用圆环采样模板在整幅轮廓图像中以间隔方式滑动搜索.滑动间隔q由缩放后的圆环大小圆半径决定，q的取值需满足q≤(R'-r')/2.此时，圆环采样模板在滑动计算时，中心位置的取值为

式中:R'、r'分别为缩放后圆环大小圆半径.本文根据实际情况设q为3.

5)每当采用圆环采样模板进行搜索获得的击中率值高于设定阈值时，则返回当前圆环采样模板的中心和各矩形采样区中获得的关键点，并以这些关键点确定圆的半径和圆心，然后，按照式(1)继续搜索，直至搜索结束.

6)对返回的一系列圆进行处理.圆心位置以及半径大小相近的圆认为是同一个圆，并取这些圆的圆心和半径平均值作为该圆的圆心和半径.

7)采用差方和(SSD)法计算步骤6)返回的圆心对应的图形与需检测目标图形的灰度相关性.如果相关性满足设定值则认为在该位置附近存在目标图形，否则丢弃.

3 实验结果与性能分析

3.1 快速定位

当建立模板后，算法的计算耗时主要集中在轮廓提取和对目标的搜索.本文通过将图像缩小至1/16，模板以间隔为3的方式滑动，使得计算量缩小为1/144.另外，如果计算过程中发现击中率低于设定停止阈值则停止计算.整个算法的主要运算操作是整数加减乘法和逻辑比较，算法执行效率非常高.表1是整个程序各本算法主要步骤的耗时数据和文献［14］算法的总耗时数据，该数据的取得是由Pentium Dual-Core CPU E5200 2.5 GHz，1.98 GB内存的计算机进行运算得到.由表1中数据可知，本文算法的计算耗时几乎不受圆半径大小影响.对比两种算法，当圆半径比较大的时候，本文算法的快速性能优势非常明显.当半径较小时，两者性能相近.

表1 各主要步骤耗时统计数据 ms

3.2 高可靠性

在实验过程中，为了避免出现漏检和误检情况，算法适当降低击中率阈值，同时在后期对检测的对象采用差方和(SSD)进行检验.表2为定位3种不同半径圆的结果.

表2 不同半径圆的检测结果

由于算法以轮廓作为匹配特征信息，因此算法对光照的变化不敏感.图7(a)是正常光照情况下图像的定位效果图;图7(b)、(c)则是光照不强和光照过强情况下的定位效果;图7(d)则是在受到部分遮挡时的检测效果.

3.3 低内存消耗

本文算法的内存消耗主要用于装载灰度图、存储缩放后灰度图及轮廓图，构建圆环采样模板.相比于Hough变化和金字塔分割法加速，本算法具有明显优势，表3中列出了当处理640*480图像时，本文算法、Hough变化、金字塔分割加速的主要内存消耗的比较数据.从表3中可以看出本文算法可以大大减低内存空间的消耗.

图7 算法在受到光照干扰或部分遮挡时的检测效果

表3 在处理640*480图像时本文算法与Hough变化和金字塔分割加速的内存消耗比较

4 结论

1)本文提出基于击中率的圆形匹配算法以轮廓为特征信息进行匹配，实现快速识别定位.试验和理论证明，算法能够取得耗时“毫秒级”快速定位效果，同时在内存消耗和可靠性方面都取得较好的性能，具有较强的抗干扰能力，对光照变化不敏感.

2)算法的实现只需要整数加减乘法和逻辑比较，而且内存消耗低，因此，算法非常适合应用于嵌入式系统，例如利用FPGA进行实现.除此，在自动化运用过程中，由于本算法具有快速定位的特点，因此利用其作为一种辅助判断方法.

3)圆环采样模板计算依据是轮廓信息，因此当轮廓信息杂多，可能会出现多检或漏检，对此算法可根据实际应用附加其他特征信息进行2次验证，提高准确定性.另外，算法对参数的设置比较敏感，需要经过实验选择合适参数模板.

［1］KIM Heung-Soo，KIM Jong-Hwan.A two-step circle detection algorithm from the intersection chords［J］.Pattern Recognition Letters，2001，22(6/7):787 －798.

［2］YIN Peng-yeng.A new circle/ellipse detector using genetic algorithms［J］.Pattern Recognition Letters，1999，20(7):731－740.

［3］XU L，OJA E.Randomized Hough transform:basic mechanisms，algorithms and computational complexities［J］.Computer Vision Graphic Image Process:Image understanding，1993，57(2):131 －154.

［4］YOO J H，SETHI I K.An ellipse detection method from the polar and poles definition of conics［J］.Pattern Recognition，1993，26(2):307－315.

［5］陈燕新，戚飞虎.一种新的基于随机Hough变换的椭圆检测方法［J］.红外与毫米波学报，2000，19(1):43－47.

［6］陈燕新，戚飞虎.利用梯度方向信息的随机Hough变换［J］.红外与毫米波学报，1998，17(5):375－379.

［7］胡正平，王成儒，练秋生.基于图像分解的快速多圆/椭圆检测方法［J］.仪器仪表学报，2002，23(3):292－294.

［8］SHARK L K，KUREKIN A A，MATUSZEWSKI B J.Development and evaluation of fast branch-and-bound algorithm for feature matching based on line segments［J］.Pattern Recognition，2007，40(5):1432－1450.

［9］PARAMANAND C，RAJAGOPALAN A N.Efficient geometric matching with higher-order features［J］.Optical Society of America，2010，27(4):739－748.

［10］HUTTENLOCHER D P，KLANDERMAN G A，RUCKLIDGE W J.Comparing images using the hausdorff distance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15(9):850 －863.

［11］ULRICH M，STEGER C，BAUMGARTNER A.Realtime object recognition using a modified generalized Hough transform ［J］. Pattern Recognition，2003，36(11):2557－2570.

［12］TANIMOTO S L.Template matching in pyramids［J］.ComputerGraphics and Image Processing， 1981，16(4):356－369.

［13］STEGER C，ULRICH M，WIEDEMANN C.机器视觉算法与应用［M］.杨少荣，吴迪靖，段德山，译.北京:清华大学出版社，2008.

［14］邹光华.基于几何特征的快速模板匹配算法［D］.哈尔滨:哈尔滨工业大学，2011.

A new algorithm for rapid circle matching

HUANG Lian-zhen1，WU Xiao-jun1，KANG Wen-xiong2

(1.Harbin Institute of Technology Shenzhen Graduate School，518055 Shenzhen，Guangdong，China;2.College of Automation Science and Engineering，South China University of Technology，510640 Guangzhou，China)

For the existing circle matching algorithms could not simultaneously meet the requirements of highspeed，low memory consumption and high accuracy，a new algorithm based on hit rate was proposed.The Ring Sample Template was introduced and its edge was used as matching information.The matching result was determined by hit rate，and the Grey Scale Correlation between source and destination was calculated to eliminate wrong destination.The result showed that the algorithm could get destination position in milliseconds，and had good performances on both memory consumption and reliability.

rapid target locating;circle match;hit rate

TP391

A

0367－6234(2012)07－0087－05

2011－09－13.

国家自然科学基金资助项目(61105019);广东省自然科学基金资助项目(S2011040002474);广东省科技计划资助项目 (2011B010200023);华南理工大学中央高校基本科研业务费专项资金资助项目(2012ZZ0108);深圳市南山区科技研发资金资助项目(南科院201002);数字制造装备与技术国家重点实验室资助项目(DMETKF2009013).

黄廉真(1985—)，男，硕士.

康文雄，auwxkang@scut.edu.cn.

(编辑 张 红)