基于模板匹配的多圆识别算法

陈令刚

(安徽理工大学计算机科学与工程学院，安徽淮南232001)

基于模板匹配的多圆识别算法

陈令刚

(安徽理工大学计算机科学与工程学院，安徽淮南232001)

圆形是基本的几个图形，对圆形的识别也是计算机视觉的基本任务之一。圆形检测在工业制造、通检测、虹膜识别、生物医药、武器制造等领域都有着广泛的应用。模板匹配是图像识别的常用的方法之一，但是模板匹配仅能匹配图片视场中匹配度最高的位置。该文通过改进匹配策略，提出了一种基于距离的识别算法，使得能够匹配出视场中所有的圆形。合成图片上实验结果表明了该算法的有效性，精度为像素级。

圆形识别；模板匹配；计算机视觉

Abstract：Circle is one of the basic graphics.Circular recognition is also one of the basic tasks of computer vision.Circle detec⁃tion in the industrial manufacturing,traffic detection,iris recognition,bio-medicine,weapons manufacturing and other fields has a wide range of application.Template matching is one of the commonly used methods of image recognition,but which can only match the highest degree of location in the image field of view.In this paper,a new algorithm Based on distance is proposed by improving the match strategy,so that all the circles in the field of view can be matched.The experimental results on the synthetic image show that the algorithm is effective and the precision is pixel level.

Key words：Circle detection;Template matching;Computer vision

1 概述

圆形的识别是图像测量中最基本和最重要的任务之一，圆检测在工业制造、交通检测、虹膜识别、生物医药、武器制造等领域都有着广泛的应用。霍夫变换是最常用的圆形检测技术，但是该算法空间复杂度和时间复杂度的需求都比较高，且在噪声比较大的图片背景下识别效果并不理想[1]。模板匹配是一种重要的图像识别技术，已经在很多计算机视觉中得到了应用。如OCR、卫星遥感、PCB检测、视觉跟踪等。基本的模板匹配算法通过在源图像上滑动指定大小模板图模板图像，源图像与模板图像一一进行相似度的计算。源图像的每一个像素点都与模板图像计算之后就可以得到最佳匹配位置，也得到相应位置对应的相似值。最佳匹配位置的横纵坐标各加上模板的1/2高和宽，这样我们就得到了源图像中的一个圆形的圆心。通过计算其他各点相似度与最佳匹配点的距离判断其是否为圆形，当距离小于某一经验值时，则判断匹配到圆形。这样便能把圆形位置和非圆形位置区分开，也就匹配出了源图中所有的圆形。在检测圆形时，为了防止产生干扰，我们将匹配成功的像素点周围的像素值都不参与距离计算。最后，为了检验匹配的精度，我们随机选取圆形边缘上的三个点，通过三点拟合求出的圆心与模板匹配成功的圆心进行比较，从而确定该算法的精度。

2 模板匹配及三点拟合圆

2.1 模板匹配

模板匹配就是将模板以滑动窗口的形式遍历整幅源图像(待检测的图像)，每次滑动都会产生一个和模板等大小的ROI图像，基于某种度量方式，计算模板与当前ROI图像的相似性度量值。这样遍历完整幅图像后就会形成一个图像，找出最大值对应的位置(x,y)，它就是我们要寻找的目标的位置。已知源图中有要找的目标，且该目标同模板有相同的尺寸、方向，通过一定的算法可以在图中找到目标，确定其坐标位置。以8位图像(其1个像素由1个字节描述)为例，模板T(M×N个像素)叠放在被搜索图S(W×H个像素)上平移，模板覆盖被搜索图的那块区域叫子图Sij。i，j为子图左上角在被搜索图S上的坐标。搜索范围是：

1≤i≤W—M+1

1≤j≤H—N+1

通过比较T和Sij的相似性，完成模板匹配过程。衡量模板T和子图Si,j的匹配程度,可用的误差平方和算法(SSD)，这也是速度较快的一种方法。此外还有平均绝对差算法(MAD)、绝对误差和算法(SAD)、误差平方和算法(SSD)、平均误差平方和算法(MSD)、归一化积相关算法(NCC)、序贯相似性检测算法(SS⁃DA)、hadamard变换算法(SATD)等。本文采用的是SSD算法，公式如下：

模板大小的确定往往是一个经验值，一般紧贴目标轮廓的模板或者包含太多背景的模板都不好，本文使用的模板是用画图画出的标准的圆形模板，大小和源图中目标的大小基本一致。

2.1 三点拟合圆

模板匹配检测圆之后，为了验证其精确度，我们使用三点拟合圆的方法。三点拟合圆顾名思义是在圆形边缘上随机选取非共线的三点以确定圆的位置。圆的方程如下：

假设选取的三点为(x1，y1)，(x2，y2)，(x3，y3)，将这三点带入方程(2)，得到：

运用Cramer法则解此方程组，得到参数a、b、c.

其中：

于是方程(2)可以重新写为：

于是可以得到圆心(x0，y0)和半径 r分别为(-a,-b)、(a2+b2-c)1/2。

3 实验仿真及分析

本文的模板匹配适用于源图像视场中的圆形大小基本一致的情况，比如在生物学领域，自动准确的确定细胞的位置；人脸识别方面，确定眼睛的位置等等。该实验是在合成的图像上进行的，图片像素大小1392*1040，模板像素大小100*100。图像1为源图像，图像2为模板，图片3为识别出的结果。表1列出了模板匹配识别及手动三点拟合的圆心坐标。圆形检测的步骤如下：

step1：根据源图片S(W×H个像素)中的圆形的形状生成模板图片T(M×N个像素)，源图片(图1)中的圆是空心圆,那么也生成空心圆的模板(图2)。生成的模板图像的半径要和源图像中圆形的半径要基本一致.

图1 源图像

图2 模板图像

Step2：运用公式(1)进行模板匹配，遍历完整幅图像后就会形成一个方差结果图像S，得到每一个源图像的像素点对应的方差值，找出图像S中方差值最小的位置min_Loc(x1,y1)及方差最大的位置max_Loc(x2,y2)，其方差值分别记为min_Loc_Value、max_Loc_Value。而min_Loc即为匹配到的第一个圆形的位置。圆心坐标为：Loc(x,y)=min_Loc(x1+M/2,y1+N/2)。

Step3：为防止产生干扰，方差结果图像S中min_Loc点附近1/2倍模板宽度和高度附近的值都不参与计算，我们将其均设置max_Loc_Value。

Step4：取排名第二个方差值最小的点new_min_Loc，其方差值为new_minValue，计算此点的方差值与min_Loc_Value的距离。计算方式如下：

如果distance＞=C，(C为某一经验值)，则判断此位置为匹配到的第二个圆形。为了防止产生干扰，依然将new_min_Loc点附近1/2倍模板宽度和高度方差值都设置max_Loc_Value。

Step5：重复Step4，直到distance＜=C。

Step6：画出匹配到的圆形，结果如图3，结果表明能够检测出源图像中所有的圆形。

图3 检测结果

Step7：用三点拟合圆的方法手动计算圆心，每个圆形选取10组计算圆心，最后求其平均。拟合圆的结果见表1。

4 实验结果与结论

实验采用对合成的图片进行模板匹配，整套算法在VS2010+opencv2.4.9的环境下编程实现[3]，我们手动选取圆形上的三点拟合圆心作为对比，实验对比结果表1所示。由此可见本文模板匹配方法能够识别源图像中的圆形且满足一定的精度要求。

表1 多圆图像的识别结果

5 结束语

本文提出了基于距离的多圆模板匹配算法，该算法能够检测源图像中有一定噪声下的多个圆形，识别的精度和手动三点拟合的圆心误差在1个像素之内。但是由于模板匹配技术本身的局限，仅当模板中的目标物大小基本能一致的时候才具有很好地识别效果。当源图像中的圆形大小不一致，可采用多模板匹配的方式实现。实际应用中，图片的情况是复杂多变的，由于光线、图像采集、遮挡等多种因素的影响，待检测的目标经常出现变异的情况，比如椭圆、边缘断续、多圆粘连等，也就是说在复杂背景下的圆检测依然是一件挑战性的工作。

[1]Atherton,T.J.and Kerbyson,D.J‘Using phase to represent ra⁃dius in the coherent circle Hough transform’,Proc,IEE Collo⁃quium on the Hough Transform,IEE,London,1993.

[2]Erik Cuevas,‘Automatic multiple circle detection Based on artificial immune systems’Expert system with Applications,2012(39)：713-722.

[3]刘瑞祯,于仕琪.opencv教程—基础篇[M].北京：北京航空航天大学出版社,2007.

[4]周丽莎.基于模板匹配的视觉定位技术研究与应用[D].大连：大连理工大学,2012.

[5]张显全,苏勤,蒋联源,等.一种快速的随机Hough变换圆检测算法[J].计算机工程与应用,2008,44(22)：62-64.

[6]梁路宏,艾海舟.基于多关联模板匹配的人脸检测[J].软件学报,2001(9).

[7]高聪,王福龙.基于模板匹配和局部HOG特征的车牌识别算法[J].计算机系统应用,2017(9).

A Algorithm for Multiple-Circle Detection on Images using Template Matching

CHEN Ling-gang
(The Academy of Computer Science and Engineering in Anhui University of Science and Technology,Huainan 232001,China)

TP311

A

1009-3044(2017)24-0173-02

2017-07-15