2.2.1 图像匹配算法

模板匹配通过识别某一特定对象物的图案位于图像的具体位置，进而识别对象物，是图像处理中最基本、最常用的匹配方法。模板匹配具有自身的局限性，主要表现在只能进行平行移动，若原图像中的匹配目标发生旋转或大小变化，则该算法无效。

通常来说，模板就是一幅已知的小图像，而模板匹配就是在一幅大图像中搜寻目标。已知该图中有要找的目标，且该目标同模板有相同的尺寸、方向和图像元素，通过一定的算法可以在图中找到目标，确定其坐标。

模板匹配有一个缺点：当图像和模板中物体的尺寸不一致时，匹配度会大大降低，通常需要对模板图的长和宽分别进行缩放，而这会大大增加计算量。此外，模板匹配不能有效检测发生仿射变换的物体。

特征匹配是另一种常用的图像匹配方法，能有效应对上述情况。特征匹配方法首先对测试图像和模板分别进行关键点的检测，并生成关键点对应的特征描述子，与非密集特征的提取方式相同。提取关键点的特征描述子后，首先对模板和测试图像中的关键点进行匹配，获得两幅图像中关键点的匹配点对。然后对匹配点对进行检测，得到更为准确的关键点对。假设物体没有发生形变，则通过匹配点对的坐标计算出两幅图像的仿射变换矩阵，当关键点对和仿射变换都满足一定条件时，可认为图像中是有模板包含目标的。

从算法机制方面可以看出，特征匹配只需找到两幅图中一致的关键点，不受尺度和角度等因素的影响。当物体发生形变时，关键点的相对位置关系可能有较大的差别，例如模板和测试图像中包含同一个姿态不同的人，那么两幅图像中人体的头、手臂、腿、脚等部件的坐标可能无法通过线性变换完全对齐。

近年来，也有关于可形变的图像匹配方法，旨在检测有限形变下的物体。例如Tali Dekel等研究者提出的Best-Buddies相似度的概念，可以衡量两个特征描述子集合的相似度。这种度量在特征空间进行最近匹配，两个集合中互为最近邻的关键点被称为Best-Buddies配对，而不用空间坐标进行校验。

Itamar Talmi等人在此基础上提出了可形变多样性相似度（Deformable Diversity Similarity，DDS）。该理论认为，当两个图像块有相同物体时，应该会有很多Best-Buddies配对，即两个集合的匹配具有多样性，因此，一个关键点如果是另一个集合中很多点的最近邻，那么这个关键点的重要性会有所下降，这是因为其会影响匹配的多样性。Lior Talker等研究者又提出并验证了全局的多样性假设，从而减少了DDS算法的计算量。