采用轮廓向量特征的嵌入式图像匹配方法

倪健，白瑞林，李英，吉峰，李杜

1.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122

2.无锡信捷电气有限公司，江苏无锡214072

1 引言

图像匹配技术是机器视觉必不可少的一部分，在医学、交通、遥感监测、工农业检测等诸多领域内有着广泛的应用，尤其是工业流水线上的产品定位检测，要求图像匹配具有优秀的鲁棒性、实时性。

目前图像匹配仍是一个热点和难点问题。Zitova等[1]直接利用图像灰度信息进行相似度度量以定位目标。Low e[2]提出SIFT算法，利用尺度空间性质，以梯度方向的直方图为基础，给出了一种尺度不变关键点的检测方法。Bay等[3]提出一种新的特征提取算法SURF，它通过快速Hessian矩阵，非极大值抑制得到特征点，计算特征描述向量则通过计算区域Harr响应获得。U lrich等[4]提出一种分级广义Hough变换，将图像的空间域变换到参数空间，可以检测任意形状物体。另外还有诸多实例利用不变矩[5]、像素灰度值[6]、互信息量[7]或特征点[8]等特征，并基于神经网络、遗传算法、动态规划或松弛匹配等搜索策略进行图像匹配工作。

本文针对工业流水线上工件的图像匹配定位问题，且相机与流水线相对位置固定，考虑目标的平移、旋转、缩放、遮挡、光照变化、极性反转、聚焦不准、对比度低等问题，提出了一种基于关键轮廓向量特征，根据模板信息自动确定图像金字塔分层数、旋转角度步长和缩放步长，图像金字塔最高层二级筛选策略，以及非最高层同步局部搜索区域构建和匹配的实时图像匹配方法。

2 基于轮廓向量特征的图像匹配原理

轮廓特征相比较于点、面、统计量等特征，具有计算量小，抗噪能力强等特点，使图像匹配的鲁棒性、实时性得到提高[9]。同时，由于在待测图中目标坐标、方向角度和缩放大小均未知，模板需要进行图像变换以与某位姿上的对象进行相似度计算，通常将这种变换定义为包含旋转、平移和缩放的仿射变换，又因平移分量可由模板在待测图中的游走匹配代替，因而这种变换可表示为：

式（1）为坐标点逆时针旋转变换，其中(x0y0)T，(x1y1)T为点旋转前后的坐标，a为缩放系数，θ为旋转角度[10]。然后利用经式（1）变换过的多角度模板在待测图中进行遍历搜索匹配，当游走到某一位姿时，则利用式（2）基于模板和待测图轮廓点方向向量的相似度量法则，进行二者匹配判断：

K为模板轮廓点总个数；di=(ai，bi)为模板轮廓点上X、Y方向向量；ei=(wi，ri)为与di相关联模板坐标对应到待测图中轮廓点的X、Y方向向量组成；分别为方向向量对应的梯度强度值；s表示模板与待测图的相似度，取值范围为0～1，s越大相似度越高[11]。

式（2）相似度量不受遮挡、混乱影响，如果在模板或待测图中某个特征丢失，噪声将产生一个随机方向向量，这些方向向量平均起来将不会对总和造成影响。对于各向同性像素点，可以设置其方向向量为0，这样遮挡和混乱构成的特征就不会对这个总和造成影响。方向向量的长短又取决于图像的亮度，式（2）相似度量把所有的方向向量都变为1，相似度量就不会受任意光照变化影响。在分子部分取绝对值，可以保证在模板与目标明暗变换颠倒的情况下也能找到目标。

3 基于关键轮廓向量特征的图像金字塔匹配算法设计与实现

3.1 关键轮廓向量特征提取

现有轮廓检测方法虽能较好提取图像轮廓，但直接用于图像匹配之中，仍不能达到理想效果。

本文采用图像的关键轮廓特征，并以轮廓的X、Y方向的梯度向量作为特征描述。所谓关键轮廓特征应满足以下两点：满足轮廓单像素化；仅保留目标主体轮廓。既能减少相似度计算的输入量以及减少运算时间，又可提高存在遮挡、模糊聚焦等情况时的目标识别率。针对工业现场环境，本文改进现有轮廓检测方法，提出如下方法提取特征：

（1）对灰度图利用均值滤波去噪、Sobel算子提取轮廓点的X、Y方向向量及对应的梯度值。

（2）对梯度图进行非极大值抑制细化轮廓，达到单像素化目的。

（3）对经处理的梯度图利用Otsu和高低阈值处理，提取目标的单像素主体轮廓。

（4）应用最小轮廓尺寸剔除法，筛除梯度图中小于某一尺寸的轮廓，以去除细小琐碎轮廓。

此时，细小、琐碎轮廓已去除，基本仅存单像素宽度的主体轮廓，且如图1（c）所示。

图1 关键轮廓提取

3.2 构建图像金字塔及自动分层

若直接将模板与待测图进行特征匹配，算法的复杂度将为O(whnm)，w和h是待测图的宽和高，n是模板的轮廓点数，m是模板搜索角度范围。面对如此高的复杂度，无法满足工业实时性要求。

为此提出利用2×2均值法构建图像金字塔，进行多分辨率图像搜索策略，并根据模板轮廓像素点数自动确定其构建层数。依据大量现场样本测试概率统计分析，对于大多数轮廓简洁且纹理较少的几何工件而言，当其图像金字塔在某层轮廓点数刚好大于20～30个，再高一层则小于此值时，则工件图像在该层仍能保持良好可分辨的外轮廓，可将该层定为图像金字塔最高层。

同时，为保证目标存在缩放情况时，也能正确构建金字塔，需保证最高层模板轮廓图缩小设定的最小缩小系数时，其轮廓像素点数仍大于20～30个像素。

3.3 自动确定模板旋转角度步长

因待测图中的目标角度具有随机性，在给出模板搜索角度范围后，需确定合适的匹配旋转角度步长。避免过度旋转致使丢失目标，或欠旋转造成重复匹配。因此，提出基于余弦定理和模板轮廓点分布情况自动计算模板旋转角度步长的方法。

（1）根据模板轮廓图计算其质心坐标(XC，YC)及轮廓总点数K，以下为质心点求解公式：

式中xiyi为轮廓点X、Y方向坐标值。

（2）根据余弦定理求解距质心最远轮廓点绕质心旋转过的角度以求旋转角度步长。点L、p为模板质心点、最远轮廓点，点w为点p旋转后的点，设边长为pw=1，Lp=Lw=a，由余弦定理求∠w Lp：

∠w Lp为可保证模板旋转后至少有轮廓点旋转出原坐标所对应的角度，但旋转角度步长需保证模板旋转前后能够区分开来。因此针对某些模板，点p需旋转大于1个像素距离。统计分析知，当pw在1～2之间取值时，可满足各种情况模板。

3.4 自动确定模板缩放步长

由于目标实际尺寸、目标与相机距离的随机性，导致模板和实际目标存在一定的缩放比例，为避免过缩放或欠缩放，需确定模板缩放步长。本文根据模板具体信息，自动计算出模板缩放步长：

（1）计算模板图金字塔某一层轮廓图质心点c和距质心点欧式距离最远轮廓点p的坐标。

（2）根据图像缩放性质，当点p以质心c为基准点，缩放1个像素单位，能保证模板轮廓上至少有1个像素移动出原来的坐标，据统计可知，当点p坐标缩放1～2个像素单位，即可满足各种情况，作为该模板的缩放步长。当点p缩放1个像素单位时对应的缩放步长s为：

减少环境应激原，以保持宝宝良好的稳定情绪，去除诱发因素，如花粉、灰尘、纤维、宠物、动物皮屑、室外污染物如汽车尾气，经常打扫暗角，晒洗被褥。

式中，pc为点p和点c之间的欧式距离。

3.5 图像金字塔最高层二级筛选匹配

虽然图像金字塔已极大降低了算法复杂度，但在最高层匹配时仍为传统的穷举遍历法搜索，计算量较大。因此，减少整体方法耗时的关键在于图像金字塔最高层的目标快速匹配定位。

为此提出在图像金字塔最高层，基于搜索框优先剔除目标非潜在位置区域，再进行匹配的二级筛选快速匹配策略。具体操作为：

（1）构建搜索框。根据给出的缩放范围和缩放步长，在逐步递增的每一个模板缩放系数下，以最高层的模板质心为旋转基准点，构建包围全旋转角度范围下模板的最小外接矩形，并使该矩形4条边与坐标轴平行，即为搜索框，质心为其基准点。如图2所示，为三角形efg为模板，点N为质心，矩形abcd为模板，360°角度范围旋转构建的搜索框。

图2 搜索框构建示意图

（2）待测图目标非潜在位置区域筛选。设最高层模板轮廓总点数为K，相似度阈值为S，搜索框在待测图中遍历移动，判断搜索框所覆盖待测图范围内轮廓点数，若点数大于K×S，则标记搜索框基准点此时对应待测图中的点坐标，认为可能存在以它为质心的某角度目标；否则不予标记。

（3）基于关键轮廓向量特征的匹配判断。仅对待测图经上一步标记的位置，利用预先经旋转处理并存储的多角度模板进行全角度范围匹配。同时，改进式（2）的运算，先对模板和待测图的轮廓点方向向量归一化，再进行匹配判断，这样对每个轮廓点的判断可减少一次乘法和除法运算，改进公式如下：

为提高计算判断速度，设立终止条件，当计算了待测图与模板对应的T个轮廓点后，所得点相似度和值为

即使剩余的K-T个点完全匹配也不可能达到相似度阈值S，因此结束本次相似度计算。

3.6 图像金字塔非最高层快速匹配

（1）同步图像金字塔构建与目标匹配。改变原有预先建立图像金字塔进而匹配方法，实行在某一层定位到目标后，再构建其下一层图像金字塔，进行目标匹配的方案。据此可节省待测图像金字塔预先完整建立所占内存空间，也可避免待测图中目标不存在时，金字塔完整预建立所耗费的时间。

（2）局部待测图像区域金字塔构建。为节省内存空间，在建立待测图像金字塔非最高层图像时，利用其上一层定位出的目标信息，仅构建对应到该层的目标所在局部图像区域，从而节约本层非目标存在图像区域构建所浪费的时间和空间。

4 实验测试与分析

本测试实验均在W in7系统的MATLAB 2009a平台上完成，电脑硬件配置为奔腾双核CPU（主频2.2GHz），图片由实验室自主研发640像素×480像素分辨率的30万黑白相机拍摄。

本文主要从两个方面测试算法的优劣程度，即鲁棒性和实时性，认为满足此二者条件的算法可应用于工业现场生产。

4.1 鲁棒性测试

鲁棒性即指当待测图中目标存在遮挡，光照不均，图像噪声，灰度值属性变化，模糊聚焦成像等外界环境干扰时，仍能对其进行准确匹配定位，即识别率测试。

图3～图5分别为洗发水瓶盖、十字箭头型工件、文字在各种情况下的定位效果图，图中红色线为定位目标轮廓，蓝色点为目标质心点。

图3 洗发水瓶盖定位

图4 十字箭头型工件定位

图5 文字缩放定位

为验证算法识别率，对液晶屏标记、洗发水瓶盖、万字字符、十字工件、锂电池定位孔各自进行500张样品鲁棒性定位测试。如图6所示，为本文算法、Halcon软件和PatM ax软件进行的识别率比对分析，可以看出本文算法与两软件定位识别率相比，部分样品的识别率更高。

图6 识别率对比图

相似度阈值一般为人为设定，取值在0.6～0.8之间较宜，具体应根据现场目标可能受到的干扰而定。如图7所示，为识别率、漏检率和误检率随相似度阈值递增的变化趋势示意图。

图7 识别率、误检率和漏检率随相似度阈值变化趋势图

4.2 实时性测试

实时性即为算法在规定时间内是否能完成给定的工作，当然算法运算时间越短越好。针对此目的，由于图像匹配工作的部分参数需人为设定，在实际操作时还应注意以下几个方面：

（1）相似度阈值。该值过小会造成误检目标，图像金字塔向下层精定位时运算量会过大，该值过大则会使漏检率增加、识别率降低。

（2）搜索区域。应根据目标在待测图中可能出现的区域，尽量规定较小的搜索区域。

（3）搜索角度范围。应根据目标实际可能出现的最大角度范围设定，较小该值可提速算法，对于几何对称的目标，更应根据其对称特性设置该值。

（4）目标缩放范围。根据目标可能出现的缩放大小情况，尽可能确定一个较小的缩放范围。

（5）图像金字塔分层数，分层越多，算法耗时越少，但是当层数达到一定值时，模板图的信息量就会较少，可能会造成误检、漏检的发生。

如图8所示，对液晶屏标记、洗发水瓶盖、十字箭头型工件分别进行50张图片定位的耗时统计图。为获取算法最大耗时，除十字箭头型工件搜索角度范围设为0°～90°，其余工件为0°～360°，缩放系数为0.8～1.2，未设置搜索个数上限，搜索区域为640像素×480像素全图，相似度阈值在0.6～0.8之间浮动，金字塔自动分层，分别为5、5、6层。

图8 目标耗时统计

由图8看出，虽然耗时在100～180ms之间，但适当设置影响耗时的几个方面，将算法用C语言实现，嵌入实验室开发的软硬件平台后，可控制耗时在100m s以内甚至更少，可工业现场实时性要求。

5 结论

本文针对工业现场工件快速、准确定位问题，提出一种采用关键轮廓向量特征的实时图像匹配方法。主要特点是：

（1）提取基于X、Y方向向量的关键轮廓特征，能表达主要轮廓信息，并保证轮廓点数尽量精简，极大减少运算时间。

（2）提出根据模板图像具体信息，自动计算出合适的金字塔分层数、每层金字塔模板匹配旋转角度步长和缩放步长，确保识别率和耗时的均衡。

（3）利用图像金字塔搜索策略，并创新采用图像金字塔最高层二级筛选策略，根据待测图具体内容优先剔除目标非潜在位置区域，然后仅对剩余的少量区域进行匹配，同时预存多角度模板和设置相似度截止条件，能大大提高匹配速度。

（4）在图像金字塔非最高层进行局部待测图区域构建，同步图像金字塔构建和目标匹配的方法，节省内存空间和减少计算时间。

实际测试表明，本文方法鲁棒性好，抗图像畸变、噪声、遮挡、光照变化、极性反转、聚焦不准、对比度低等能力强，耗时为毫秒数量级，可实现任意角度、坐标、缩放下的目标匹配定位，正确率达97%以上，满足了工业现场应用要求。

[1]Zitova B，Flusser J.Image registration methods：a survey[J].Image and Vision Computing，2003，21（11）：977-1000.

[2]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[3]Bay H，Ess A，Tuytelaars T.Surf：speeded up robust features[J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[4]Ulrich M，Steger C，Baumgartner A.Real-time object recognition using a modified generalized hough transform[J].Pattern Recognition，2003，36（11）：2557-2570.

[5]Singh C，Walia E.Fast and numerically stable methods for the computation of zernike moments[J].Pattern Recognition，2010，43（7）：2497-2506.

[6]Kim H Y.Rotation-discriminating template matching based on Fourier coefficients of radial projections with robustness to scaling and partial occlusion[J].Pattern Recognition，2010，43（3）：859-872.

[7]Rajwade A，Banerjee A，Rangarajan A.Probability density estimation using isocontours and isosurfaces：applications to information-theoretic image registration[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（3）：475-491.

[8]Teke M，Tem izel A.Muti-spectral Satellite Image Registration Using Scale-restricted Surf[C]//Proceedings of International Conference on Pattern Recognition，Istanbul，2010：2310-2313.

[9]Tuytelaars T，M ikolajczyk K.Local invariant feature detectors：a survey[J].Computer Graphics and Vision，2008，3（3）：177-280.

[10]Steger C，U lrich M，W iedemann C.机器视觉算法与应用[M].杨少荣，吴迪靖，段德山，译.北京：清华大学出版社，2008：238-345.

[11]邹广华.基于几何特征的快速模板匹配算法[D].哈尔滨：哈尔滨工业大学，2008.