一种改进的轮廓曲线匹配算法

任家祥 张志刚 西安财经大学 信息学院

1 概述

图像形状匹配是计算机视觉的重要研究领域，目前轮廓曲线的匹配分为两种，一是基于区域，二是基于特征点。文献中将提取到的曲线进行最大公共子序列进行匹配，缺点是对于机器的性能要求较高，且匹配速度较慢。基于角点，采取粗、精两种匹配方法，粗匹配基于归一化角点距离矩阵，精匹配基于同心圆。因为需要进行同心圆计算，其匹配速率仍不高。将多边形逼近算法与提取曲率相结合，提出一种速度较快的匹配方法，但是在进行多边形匹配的时候，顶点的数目并不能确定，从而限制了匹配结果。

本文提出了一种轮廓曲线匹配算法：使用Canny 边缘检测算法提取出边缘，使用Shi-Tomashi 算法对目标边缘曲线角点进行提取。根据角点的位置点信息来建立出角点距离矩阵，并对其进行标准化处理。对处理过的角点距离矩阵视情况使用快匹配或慢匹配，分别适用于两种不同的图像匹配情况。

2 预处理

首先采用Canny 边缘检测算法得到细且明亮的轮廓曲线，再提取特征点，我们以角点作为图像中重要的局部特征。本文采用的Shi-Tomasi 角点检测算法基于灰度值，是对Harris 角点算法的改进。Shi-Tomasi 检测算法流程如下：

(1）使用差分算子计算出x，y 方向的偏导数，计算出Ix^2，IxIy，Iy^2 四个元素值组成的2x2 的矩阵

(2）使用高斯滤波器处理（1）中的2x2 矩阵，得到结构张量矩阵M。

(3）由M 求得行列式的特征值r1 和r2，根据r1，r2 中的最小值来判定该像素点为强角点

(4）设定阈值Tc 和Td，对提取的特征点的数目和相邻特征点的距离进行约束，这样便于匹配点对数目的衡量和防止描述区域的重叠。

3 RPCP 轮廓曲线匹配算法

3.1 归一化角点距离矩阵

在平移和旋转之后，角点的位置会发生变化，为描述角点之间的相对位置，计算N个角点的欧式距离，从而建立一个N*N的二维矩阵，其计算公式为：

其中的max 和min 表示二维矩阵中所有元素的最大值和最小值。

3.2 快匹配

由上式得到两个N*N 二维数组，如果将每个元素都与其余元素进行比较，那么总共需进行N^4 次比较操作。设两个不同图像的归一化角点距离矩阵A 和B：

在快匹配算法中，将距离最大值点作为基准点，若该点到其它点的距离都能与另一点相匹配，则可以确定所有点之间的位置关系成功匹配。

算法流程如下：

(1）对矩阵的每一行按从小到大的顺序进行快速排序。

(2）查找A、B 矩阵各自的最大值，记录其所在的行，记录结果为a1，a2，b1，b2。

(3）将a1，b1 进行匹配，若匹配结果不理想，则将a1，b2 进行匹配，记录两次匹配中的最优匹配结果。

(4）若匹配结果不理想，则将a1，a2 或b1，b2 换为次于当前距离的角点距离所在行。如果当前角点距离是前25%大，则进行（3），否则结束，将最优匹配结果输出。

如果算法进行第（4）步多次，则快速匹配算法失效，说明这两个矩阵之间极大值差距较大，则应采用慢匹配算法。

快匹配算法的时间复杂度在平均情况下是O(n).

3.3 慢匹配

慢匹配算法同样基于归一化角点距离矩阵，但慢匹配的目标不在于快速对两个归一化角点距离矩阵进行匹配，而在于最大限度得找出两个矩阵之间的匹配程度。

在快匹配算法之中，优先匹配极大值角点距离，而慢匹配对所有角点距离一视同仁，原则上需要将每个点同其它所有点进行匹配。为减少匹配的次数，先进行排序，这样匹配单位便由个上升为了行。其次，若该点与某一点的匹配程度理想，则应取消该点继续匹配下去，这样也能显著降低匹配次数。算法流程如下：

设有两条需要匹配曲线的归一化角点距离矩阵A、B，A、B 为N*N 二维矩阵。

(1）将A，B 的每一行按从小到达的顺序进行快速排序。

(2）将A 中的第n 行依次与B 中的每一行进行匹配，将匹配结果记录下来，若匹配结果理想，则终止该行的匹配。

(3）n 值加一，重复（2）中的操作，记录下每一行的最优匹配结果，直到所有行都匹配完毕。

(4）将每一行的最优匹配结果相加，得出最终匹配结果。

慢匹配算法的事件复杂度在平均情况下是O(n^3)

4 实验与分析

实验以某汽车品牌的标志为对象，共提取出了目标曲线20 个最优角点，建立归一化角点距离矩阵之后，进行匹配。最终匹配程度达到95%。说明快匹配算法对于同一曲线的匹配有效。之后将一张纸不规则撕扯成两半，并进行旋转，同样对图像进行预处理并提取轮廓曲线。提取出20 个最优角点，将角点标记出来，如下图：

图 4-1 原图和角点提取图

建立归一化角点距离矩阵之后，使用快匹配算法，匹配程度为10%。说明快匹配算法对于不同曲线的匹配并不合适。则使用慢匹配算法，慢匹配算法的匹配程度达到75%，符合预期。说明慢匹配算法相较于快匹配更具有普适性。在对于差异较大的两个矩阵进行匹配时采用慢匹配算法更为合适。

5 结论

本文提出了一种基于归一化角点距离矩阵的轮廓曲线匹配算法，根据应用场景的不同，提出了快匹配算法和慢匹配算法。经过测试，快匹配算法对差异反应强烈，更适合于对曲线相似度要求高的领域。慢匹配算法能耐心地寻找出两条轮廓曲线之间的最大相似程度，但时间复杂度较高。该算法的精度在一定程度上依赖于边缘检测算法和角点检测算法。