基于特征点匹配的改进模板匹配算法*

朱鸣镝 陈 婵 孙东岳

（上海理工大学光电信息与计算机工程学院 上海 200093）

1 引言

图像匹配是许多计算机视觉算法的基本输入。因此，其速度，准确性和鲁棒性至关重要。当前，慢速（但可靠）的特征匹配器与快得多（但通常不稳定）的实时解决方案之间存在很大的性能差距。

局部不变特征如SIFT［2］，SURF［3］和ORB［4］。已广泛用于图像匹配和其他计算机视觉应用中，例如图像检索、对象类别识别、全景图构建、多光谱图像匹配和场景重建等［5～13］。近年来，如何有效地匹配功能成为热门问题。一般而言，实现此目的有两个方面的考虑。首先是为每个局部特征构造一个描述符。理想情况下，要求描述符具有高度的区别性，并且在由相机姿势和光照变化引起的变换中应尽可能不变。第二是匹配描述符向量。理想情况下，需要进行匹配步骤以获得更多的真阳性结果，而获得更少的假阳性结果，并且匹配时间成本应尽可能低。

在图像匹配的另一个领域：目标识别和跟踪中，模板匹配起着重要的作用［14］。模板匹配旨在找到其他图像中的特定区域，该区域与给定的模板具有最高的相似度，并将其选择为匹配区域。通过在另一幅图像上以给定模板的形状滑动小块，计算给定模板与小块所覆盖的当前区域之间的相似度，最后选择相似度最高的特定区域作为匹配区域。

通常模板匹配算法涉及两个关键方面：相似性度量和搜索策略［15］。

相似性度量确定一次匹配的计算。搜索策略在一帧中影响匹配时间。这两个方面都决定了目标识别的计算时间。平均差是常见的相似性度量，而逐点匹配是常见的搜索策略。

通过上述分析，提出了一种新颖的参数，为每个特征点计算“得分”，它的作用在于筛选出符合特征点存在的区域，加速匹配过程。在输入图像的特征点的基础上，我们使用特征点的坐标信息来计算每个特征点的“得分”，从而高“得分”的点在输入图像中提取出矩形模板，然后用暴力匹配算法在模板匹配区域之间分别进行特征点匹配。最后，使用描述符的汉明距离筛选提取的匹配项，以获得最终的特征点匹配结果。

2 改进模板匹配算法

实时性能是图像匹配的前提，因此提高算法的速度始终是一项重要的研究。在进行模板匹配之前，必须先从输入图像中提取模板，我们提出一种基于特征点的坐标分布的模板提取新方法。

我们计算所有的特征点的得分，目的是描述某个特征点与其周围特征点之间的位置关系，该“得分”是通过特征点附近的进行计算。每个特征点的“得分”可以通过以下公式计算：

其中，r是高斯核的模糊半径，σ是正态分布的标准偏差。

列出计算特定特征点“得分”的过程如下。

1）选择某个特征点Qi，并获取其二维坐标（xi，yi）。

2）选择另一个特征点Qj，得到其坐标（xj，yj），计算两个特征点之间距离Dij，如果没有其他特征点了，跳去5）。

3）用式（2）判断Dij的距离，εdis是提前设置好的阈值距离。如果Dij满足式（2），视为Qj是其中之一的周围点，跳去4）。否则，Qj应该被抛弃，重新回到2）选择点。

4）根据式（4），计算Qj的距离对Qi的贡献度，已经完成了Qj的整个计算过程，跳到2）选择另外一个特征点。

5）清点Qi周围每个点按高斯加权后的总距离之和，当作该Qi的得分值。

通过理论分析可以得出结论，具有较高得分的特征点更有可能位于特征点块的中心，而具有较低得分的那些点更有可能位于特征点块的边缘，甚至是孤立点。这里我们以TUM 数据集中的小熊为例，提取其特征点，从而计算其每个点的得分，实验结果如图1～3。

图1 TUM数据集

图2 输入图像提取完特征点

图3 不同颜色的***特征点的坐标位置表示其“得分值”

结果表明，得分较高的特征点的周围区域确实覆盖了图像中具有明显纹理的特定部分。因此，根据计算出的得分，我们可以获得覆盖特征点块的区域并将其提取为模板。根据“得分值”提取矩形模板的过程可以证明如下。

2）以Qi为中心提取输入图像的特定区域的矩形模型；

3）消除位于提取区域中的那些特征点，跳转到1）并循环执行此过程，直到其余点Kmax的最高“内部索引”低于阈值k0为止。

图4 TUM数据集图像

图5 提取出的图像块

3 基于改进模板匹配的特征点匹配

从输入图像中提取矩形模板后，我们提出了一种基于模板匹配的改进的特征点匹配算法：使用我们刚刚提取的矩形模板，然后在另一幅图像上找到与特定模板匹配的区域，最后进行特征处理模板和匹配区域之间的点匹配。我们在匹配特征点时使用的方法是暴力匹配算法（BF）。在本节中，将解释我们提出的算法。

3.1 模板匹配

从输入图像成功获取图像块之后，对于每个单个模板，应在其他图像中平移该模板，直到遍历整个图像区域为止。然后，将与另一幅图像中所选模板具有最大相似性的特定区域视为该模板的匹配项。相似度函数R（x，y）如下计算，其中（x，y）表示所选特定图像块区域的位置：

其中T'(x',y')表示所选模板T 中该点的已降低灰度值，(x',y')代表了点的坐标。同时，I'(x+x',y+y')表示另一张图像I 中该点的已降低灰度值，(x+x',y+y')表示了图像I 中点的坐标。式中两个参数可以用以下公式计算得出：

其中w 和h 分别表示矩形模板T 的宽度和高度，x',x'',y',y''分别表示计算过程中使用的坐标，应该将其设置为0到w-1，或者到h-1。

此外，需对相似度函数R（x，y）进行归一化，因此我们可以通过下面等式得到归一化后的相似度函数Rˉ(x,y)：

在实验中，我们使用前一节中提取的模板来进行与同一数据库中另一幅图像的模板匹配过程。Rˉ(x,y)的阈值设为0.7。

3.2 在匹配区域的特征点匹配

完成模板匹配的过程后，这表示我们在另一幅图像中具有与从输入图像中提取的每个模板图像块相对应的特定匹配区域。然后，将匹配区域的特征点匹配过程如下所示。

1）选择任意一块特定的图像块模板；

2）提取位于模板中的所有特征点；

3）提取模板匹配上的另一幅图像中的图像块中的所有特征点；

4）使用蛮力匹配算法来匹配这两组特征点：首先，选择模板中的某个特征点，然后计算选定点与匹配区域中每个点之间的描述符汉明距离，最后，描述符的汉明距离最小的特定点应与所选点的匹配点有关。循环此过程，直到遍历模板中的所有特征点；

5）选择描述符的汉明距离较小的那些特征点对作为最终匹配结果。循环整个过程1）～5），直到遍历所有模板。

不同模板及其匹配区域之间的特征点的整体匹配结果如图6所示。

图6 整体匹配结果图

4 实验

为了验证上述提出的特征点匹配算法的可行性，利用TUM 数据集中的图片作为主要匹配的图像。我们的算法中使用的参数和阈值已针对不同的情况进行了调整，并且与其他两种常用的特征点匹配算法的匹配结果进行了比较。

1）暴力匹配算法（Brute Force matching algorithm）；

2）高维数据的快速最近邻算法（FLANN）。

由于本文提出的算法是改进模板匹配的基于BF 的特征点匹配算法，因此，通过与直接使用BF的匹配结果进行比较，可以看出本文算法的优势。现在，FLANN 在特征点的可用率和匹配结果的准确性上都超过了BF，通过将我们提出的算法与FLANN 的匹配结果进行比较，具有实验意义。实验和比较的结果显示在以下各节中。

我们的算法在不同场景下的匹配结果如图7所示。

图7 提出算法的匹配结果图

以TUM的bear图为例，我们提出的算法，BF和FLANN的匹配结果如图8所示。

结果表明，在bear 的场景下，我们提出的算法可以提取出更多的特征点匹配，而错误匹配更少。其他方案的匹配结果显示在图9的缩略图中。

图9 使用我们的不同场景的特征点匹配结果从上到下分别是提出了算法，BF和FLANN

选择了不同的指标，nmatch和ncorrect它们分别表示特征点匹配的数量和正确匹配的数量。统计结果如表1所示。

表1 特征点匹配结果的统计结果

特征点匹配δ的正确率可以计算如下：

最终的统计结果如图4～10所示。

本节以TUM 数据集中的图片来验证了改进算法实验的正确性。实验证明，改进算法能够减少图像中的误匹配对，提高匹配精度。

图10 分析不同场景下的不同匹配算法

5 结语

视觉里程计中常用flann 和暴力匹配算法进行匹配，而暴力匹配经常出现错误匹配是因为缺少特征匹配不是由于太少的正确匹配，而在于很难分辨真假，故加入模板匹配进行约束，提出一种改进模板匹配算法。为了提升匹配速度和精度，该算法通过提供特征点的坐标，可以计算出每个特征点的得分值，并将其用于从输入图像中提取模板。基于输入图像和另一幅图像之间的模板匹配，使用暴力匹配算法在模板和匹配区域之间进行特征点匹配。该算法可以将高匹配数转换为高匹配质量。在室内数据集TUM 的实验结果表明，该算法匹配速度较快、准确度较好。