基于特征点的形状匹配技术及其算法实现

目标识别和定位要求利用图像信息来确定被摄物体的几何和物理属性，其核心思想是匹配，该问题的有效解决可使自动目标识别、目标跟踪、影像理解和基于内容的图像检索等相近应用任务得到有实际收效的推进。图像匹配技术是近代信息处理，特别是图像信息处理领域中极为重要的技术。图像匹配就是要根据参考图像和实时图像来选定某些特征、相似性准则及搜索策略进行相关运算，以确定匹配的最佳空间对应点。它主要研究的问题有特征空间、相似性度量和搜索策略3个方面。寻找特征的过程被称为图像匹配。图像匹配关键是要确定有效的匹配方法，要求匹配概率高、误差小、速度快且适应性好。图像匹配的方法一般分为基于灰度的匹配方法和基于特征的匹配方法两大类。基于灰度值的模板匹配技术利用像素灰度值的相关性，根据相关系数确定被搜索图像中是否存在与模板图像一致的子图像，该方法受像素取值的影响较大，在光照变化的场合难以进行准确的匹配。基于特征的匹配算法，对景象类型的适应能力不如基于灰度的算法。

对于旋转图像匹配，当旋转角度大时就会出现误匹配，传统的相关匹配方法都很难满足实时性要求。目前，关于图像匹配的文献和技术成果很多。文献[1]研究了两种典型的基于灰度的图像匹配算法——ABS (absolute balance search )法和归一化相关法对高斯噪声和椒盐噪声的适应能力。文献[2]研究基于点特征的图像序列匹配方法，但图像匹配的时间比较长，不适合实时定位中的应用。文献[3]将基于灰度的图像匹配技术与基于特征的图像匹配技术相结合，定义了一种灰度值特征，并提出了一种基于图像灰度值特征点的快速匹配搜索算法。尽管作者的实验结果表明该算法比传统算法节省了时间，但平均时间还需要0.327s ，不满足实时计算的要求。文献[4]利用基于特征点的图像匹配算法进行印品缺陷检测，通过改进的Harris 算子提取特征点，减少了运算量，处理时间满足实时检测要求，但该算法针对具有一定排列规则的印品缺陷检测。文献[5]采用极大稳定区域检测算法获得图像的局部区域，提取区域的边缘轮廓，找出同一区域中的3个关键点作为特征点，对鱼眼图像进行了匹配研究。文献[6]提出了一种形状匹配和互信息相结合的配准方法，先提取参考图像和浮动图像中的

收稿日期：2009-03-03；修订日期：2009-06-09。

开发与应用

实际应用的要求是只要能够在图像中找到“与众不同”的像素区域，就能利用该像素区域的形状特征进行图像匹配。考虑机器视觉应用系统的实时性、物体位置有平移旋转等变化的特性，本文以文献[11]为参考，研究基于点的形状匹配技术。利用特征点组成形状特征，在搜索区域寻找与模板具有相同形状特征和位置关系的物体或者定位标志。特征点之间不需要存在连通关系，算法在金字塔分层上考虑模板和待搜索图像的匹配关系，在低分辨率图像上用低分辨率模板寻找特征的大致位置或者判断有无需要寻找的形状特征，找到特征之后再依次在高一层图像上用高分辨率模板在局部范围内进行精确匹配。通过引入旋转和缩放系列模板，解决了物体或者特征存在尺度、旋转等变化对特征搜索的影响。提取模板形状特征时，通过双阈值法解决噪声对提取特征的影响。

1算法的理论基础

定义1特征点：前景图像的轮廓点，或者与周围像素的像素值具有显著不同的像素点，由此可知，特征点一般为物体的轮廓点。

定义2形状：在模板与被搜索图像或者其ROI区域中，由提取的特征点组成的任意图案称为形状，特征点之间不一定要具有连通关系。

定义3形状匹配：在待搜索图像中寻找与模板形状具有一定匹配分值的过程，称为形状匹配。如果模板上离参考中心一定距离有一个特征点，则模板下的待搜索图像中同样位置处，也存在一个特征点，匹配点数加1，模板下待搜索图像中找到的匹配点数与模板上特征点的总数比值，称之为匹配分值。当匹配分值大于设定值时，认为找到了匹配的形状。匹配过程描述为：

(1)在图像中设定需要定位或寻找的模板区域，通过模板训练，提取模板中的特征点；

(2)在待搜索图像上进行特征匹配和定位。参看图1(b)，设M为特征点构成的模板(蓝色矩形框中的红色点)，蓝色矩形框为模板ROI区域，ROI区域的中心为模板中所有特征点的参考点(蓝色矩形框的中点)。I为待搜索图像(图1(a))，可以在I中设定特征匹配搜索区域，或者在整个图上进行特征搜索。在特征匹配过程中，从搜索图像或者区域的左上角开始，不断移动模板参考点，并提取模板下子图像中的特征点，以模板参考点为中心，比较模板下面的待搜索图像上是否存在与模板特征点具有相同位置关系的特征点，累计具有相同位置关系的特征点总数，计算与模板特征点总数的比值，当这个匹配分值达到某个设定值时，当前模板所在位置的参考点就是匹配特征的中心点，或者说在搜索图像上找到了一个匹配特征。

(3)如果用于物体寻找和计数，则找到第一个匹配位置后，在搜索区域内继续进行特征匹配。寻找其它能够匹配的物体或者特征。

2提取特征点

特征点是与周围像素显著不同的点，可以利用像素灰度值判定是否为特征点，当灰度值与周围像素的差绝对值之和大于某个设定的阈值时，可以判断该点为特征点。传统的各种边缘提取算子都可以用来提取特征点。但对于实时处理的系统，实时性、准确率等要求，决定了不能采取复杂的寻阈值算法，而单一固定阈值缺乏抗噪声的能力。但同为高频信息的边缘点和噪声点具有不同的特征，噪声一般是孤立点，可以借助于Canny算子中的滞后阈值法提取特征点，对于特征之间具有连通关系的形状特征，再添加轮廓大小条件减少噪声的影响。

滞后阈值法设定两个阈值，首先选择一种梯度算子对图像进行梯度运算，并将梯度幅值大于高阈值的像素点作为特征点，这样选出的特征点比较少，然后将梯度运算的梯度幅值与低阈值比较，将高于低阈值且与高阈值获取的特征点具有连通关系的像素点加到特征点中，再考虑同一轮廓内像素的多少，将具有较少像素的轮廓去掉，进一步消除噪声的影响。图2(a)选取的对比度阈值过小，提取的特征中除了包含有完整轮廓外，加进了一些混乱的噪声；图(b)选取的对比度阈值过大，提取的特征中没有包括完整的物体边界，提取特征点不足；图(c)采用滞后阈值法提取特征点，高低阈值分别为52和26；图(d)采用单个阈值但轮廓大小提取特征点，高低阈值设为同一个参数，但同一轮廓像素的个数要大于12；图(c)、(d)这两种方法均能准确提取用于形状匹配的特征点。与其它特征点提取算法比较，计算简单，精度较高，而且参与特征匹配的点数也少。

3形状匹配算法中的关键技术

匹配算法的主要应用包括定位、查找、计数、配准等。基于特征点的形状匹配需要在模板上提取特征点，然后在被搜索图像上寻找是否存在同样的形状特征。下面结合AOI区域自动定位介绍本算法的应用和关键技术。

在实际检测过程中，为了减少图像处理时间，需要设置AOI区域，减少图像处理的区域。但由于输送带上被测物体位置有一定的变动性，需要使设置的AOI区域随着被测物体

的位置变化，自动进行调整。而物体是否发生变化，可以通过检测物体中的惟一标识是否发生了位置变化来确定，并计算出位置变化量，再根据ROI区域与标识之间的相对位置关系，决定AOI区域的位移量，从而确保AOI区域始终设置在准确的位置。

实际检测的时候，在预先拍摄的图像上，选取特征模板所在的AOI区域，提取特征点，形成以AOI区域中心的特征点群。考虑到待搜索图像与用于提取模板的图像之间存在位置旋转或者比例缩放等变化，造成不能进行准确的物体定位或者查找，再在特征模板的基础上形成具有一定角度旋转和比例缩放的系列模板。在搜索区域依次匹配序列模板，寻找满足匹配分值的特征区域，并以匹配分值之上区域的模板参考点作为匹配点。匹配计算时，选用金字塔分层算法，在低分辨率图像上利用低分辨率模板进行匹配特征的粗定位，利用粗定位的结果在高分辨率图像上进行精确定位。

(1)旋转模板及其旋转步距角的计算

一般地，模板图像与被搜索图像之间，发生的角度变化在一定范围内。通过设置搜索图像与模板图像允许旋转的角度范围和搜索步距，形成系列旋转模板，适应模板图像与待搜索图像之间存在的角度偏转关系。但允许的旋转角度越大，需要的系列模板越多；同样的旋转角度，序列模板之间的角度越小，搜索和定位精度就越高，但存储模板和匹配模板需要的时间也越多。计算旋转模板的偏转角度与搜索图片可能的偏转角度有关，而旋转步距角与特征点和基准点的最大距离有关。图3(a)为最大步距角的计算原理图和不同步距角对匹配结果的影响。设l为模板上特征点与基准最远的距离，d取两个像素，由此计算最大步距角；图3(b)所示右侧图中，由于选取的步距角过大，使两个系列模板之间的夹角过大，待搜索图像上具有图示旋转角度的物体不能与其中的任何一个模板进行很好的匹配。而图3(b)左边，总能匹配到其中的一个模板。

(2)图片缩放

模板中的物体与待搜索图像中的物体之间允许存在一定比例的缩放。但缩放比例越大，存储系列缩放模板所需的空间就越大，搜索目标所用的时间就越多。比例缩放的步长

≤＝

２

式中：

（ｂ）

不同步距角对匹配中结果的影响

图44层金字塔模板及其模板上提取的特征点为参考点，寻找模板上有特征点的地方，模板下的相应位置是否也是特征点。统计出模板上、模板下搜索图像上同时存在特征点的像素个数，与模板上的特征点总数相比，就是基于形状的匹配分值。当这个匹配分值大于设定值的时候，模板ROI 中心位置，就是找到的匹配点。如果是定位，则找到后，就停止搜索。对于计数，则找出满足匹配分值的所有特征点。

4实验研究

为了验证算法准确性，我们选择德国balser601面阵相机、computer镜头、1394卡、CCS红色条形光源作为图像采集设备，生产线上触发方式采图，用3.0CPU的计算机实时对采集图像进行处理，处理结果由并口输出开关量信号给PLC，控制气动系统实时分拣处理。图5为高速生产线上实时采集到的图像，以黑色框内的“腾讯”印刷字体定位数字“95993080”的打印区域，找到准确的数字区域后，进行字符分割和识别。

图像处理时，首先以“腾讯”这两个汉字区域为ROI区域，提取该区域内的模板特征，并放大搜索模板的ROI区域，然后设定“95993080”这个数字串的打印区域，通过模板学习，建立模板区域和数字区域之间的相对位置关系。当生产线上下一张卡片来临的时候，利用基于形状的匹配技术找到模板中设定的“腾讯”字符的位置并计算变动量，从而确定数字区域的ROI位置，在调整后的数字ROI区域，利用二值化处理提取字符特征，数学形态学的方法连接字符串，消除面积过小的斑点区域，在剩下的区域内进行字符分割，从而为准确的字符识别创造条件。

大量实验表明，在高速运动中拍摄80*60mm大小的物体，图像大小为0*480，利用上述算法进行形状匹配寻找图片中的目标，可以实现100%的目标区域精确定位，定位时间不超过15ms，从为而机器视觉的后续处理过程赢得了时间[12]。与其它方法相比，由于匹配不直接依赖于图像区域的灰度信息，而是通过提取图像特征点进行，因而匹配速度较快，而且对旋转、尺度变换、灰度变化具有较好的抗干扰信息。

5结束语

图像匹配过程需要重点解决匹配速度、匹配精度、匹配容易受比例缩放、图像旋转、光照影响等关键问题。基于特征点的形状匹配技术，通过双阈值法提取组成形状特征的点，消除了噪声对提取特征点的影响，直接以提取的特征点而不是这些特征点组成的形状特征参数进行形状匹配，减少了图像处理的时间。金字塔分层搜索算法在不影响匹配精度的同时，大大缩短了搜索时间。匹配过程中，利用缩放和旋转系列模板，有效地解决了模板和后续图像之间存在的位置变化、比例缩放对处理结果的影响。

参考文献:

[1]祝明波,张东兴,范照盛,等.灰度相关图像匹配算法噪声适应性

仿真[J].海军航空工程学院学报,2009(1):62-.

[2]魏志强,黄磊,纪筱鹏.基于点特征的序列图像匹配方法的研究

[J].中国图象图形学报,2009(3):525-530.

[3]甘进,王晓丹,权文.基于特征点的快速匹配算法[J].电光与控

制,2009(2):-66.

[4]张二虎,冯江.基于特征点的印品图像匹配算法[J].计算机工程,

2008,34(23):202-204.

[5]赵晓宁,陈建,田亚平.基于特征点的鱼眼图像匹配方法[J].山西

大学学报(自然科学版),2008(2):40-43.

[6]张素,苏和,陆雪松,等.基于形状匹配的快速图像配准[J].天津

大学学报,2008(4):433-438.

[7]李卓,仇慧娟.基于相关系数的快速图像匹配研究[J].北京理工

大学学报,2007(11):998-1000.

[8]胡页初,杨世明.图像匹配算法研究[J].仪器仪表用户,2009(2):

16-17.

[9]张红源,陈死力.图像匹配经典算法及其改进方法研究[J].兵工

自动化,2008(9):91-94.

[10]张聪,张慧.图像匹配技术在大米粒形识别中的应用研究[J].粮

油加工,2008(4):98-100.

[11]斯蒂格,尤里奇,威德曼.机器视觉算法与应用[M].杨少荣,吴迪

靖,段德山,译.北京:清华大学出版社,2008.

[12]朱铮涛.一种新的快速字符定位算法研究[J].计算机测量与控

制,2007(6):775-776.