基于特征点的图像匹配技术研究及应用
文献综述
1.图像匹配的概念
图像匹配[1]是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。
图像匹配中事先获得的图像称为基准图像（base image），在匹配过程中在线或者实时获得的图像称为实时图像（real time image）。基准图像可以比实时图像大也可以比实时图像小。当基准图像比实时图像大时，匹配过程就是在基准图像中搜寻实时图像位置的过程；当实时图像比基准图像大时，匹配过程就是在实时图像中寻找作为目标的基准图像的过程。在地图导航系统[2]中，基准图像比实时图像大。如图1.1所示。
M2
图1.1 地图导航系统中的图像匹配示意图
基准图像和实时图像是对同一对象有差别的近似描述，设和分别为基准图像和实时图像的灰度分布，在不考虑关照变换等影响下，两者存在如下关系：
鍏紡
其中是高斯白噪声，可以通过一定的滤波方法滤除。是上的点在X和Y方向上的位置偏差，称为定位噪声。位置偏差往往是因为图像的几何形变造成的。
实际上利用计算机进行处理的并不是连续图像，图像的位置和灰度都被划分为离散的值，常用像素矩阵来表示一副图像。在地图匹配导航中，通常基准图像比实时图像大。直接进行相关匹配的两幅图像应该是大小一样的，为了确定实时图像在基准图像中的位置，就必须在基准图像中提出与实时图像大小相等的基准子图，并逐个与实时图像进行比较，以便找出与实时图像匹配的那个基本子图，从而确定实时图像在基准图像中的位置。所以一般图像匹配的过程就是不断从基准图像中提取基准子图与实时图像进行相关运算的过程，这个过程
可以是线性遍历式的，也可以是非线性随机的搜索过程。
在本课题中，我们选取左上角为原点作为坐标基准。如图1.1所示，大方框为基准图像，小方框代表实时图像，虚线方框内事待选的实验匹配位置区域，也就是进行匹配的搜索区域。如果顺序匹配（即试验所有的搜索区域）的话，易知总共有脳个试验位置，其中只有一个是我们要找的匹配位置，即实时图像坐标原点在基准图像中的坐标：，称为匹配点。
2.图像匹配的方法
[3]图像匹配的方法有很多，由已知模式，也就是模板图（如实时图像，到另一幅图像（如基准图）中搜索相匹配的子图像的过程，称为模板匹配。一般地，图像的模板匹配分为两大类：基于灰度值的方法和基于特征提取的方法。
2.1灰度匹配
灰度匹配的基本思想:以统计的观点将图像看成是二维信号，采用统计相关的方法寻找信号间的相关匹配。利用两个信号的相关函数，评价它们的相似性以确定同名点。
灰度匹配通过利用某种相似性度量，如相关函数、协方差函数、差平方和、差绝对值和等测度极值，判定两幅图像中的对应关系。
2.1.1 ABS算法
[4]最基本的灰度匹配方法为ABS(Absolute Balance Search)算法，它用模板图像和待匹配图像上的搜索窗口间的像素灰度值的差别来表示两者的相关性。这个差别值有三种计算方法：
其中MAD为平均绝对误差(Mean of Absolute Differences)，SAD为绝对误差和(Sum of Absolute Differences)，SSD为平方误差和(Sum of squared Differences)，匹配时选择最大值处的为匹配点。这种方法简单，但一旦图像灰度值发生线性变换，就无所适从了；而且不同的基准图像阈值也各不相同，很难事先确定，误匹配率较高。这种方法只能用于模板图像是基准图像中一部分的情况。
2.1.2 归一化互相关算法
归一化互相关(Normalized Correlation)匹配算法是对ABS算法的改进，其基本原理是逐像素的把一个以一定大小的实时图像窗口的灰度矩阵，与参考图像的所有可能的窗口灰度阵列，计算互相关值，按互相关值的最大值来确定匹配位置，从理论上说就是采用图像相关技术。这种方法对图像灰度值的线性变换具有“免疫性”，不受灰度值的线性变换的影响。但这种方法在每一个像素点上都要计算互相关值，计算量太大，实际应用很难，只能作为理论分析。
2.1.3 幅度排序相关算法[2]
其主要思想为：首先把模板图像中德所有灰度值按幅度大小排成列的形式，然后对它进行二进制编码，最后根据二进制排序的结果，把模板图像转化为二进制阵列的一个有序组合；然后顺序地将这些二进制排列与实时图像进行由粗到细的相关计算，直到确定出匹配点位置。
以脳模板为例，如图2.1所示，对模板中的数值按照二进制大小编码，若为奇数，则中间不编码。
图2.1 幅度排序预处理
由图2.1中的①、②、③三列及其在模板图像中的位置，可以构成如图2.2所示的C1、C2、C3三个二进制阵列。这样匹配过程中，从左向右可以实现由粗到细的相关匹配。
图2.2 二进制阵列
2.1.3 序列相似性检测算法[5]
序列相似性检测算法(Sequential Similarity Detection Algorithms, SSDA)是一种快速的模板匹配算法，它是1972年Bamea和Silverman首先提出来的。该算法能很快丢弃不匹配的点，减少花在不匹配点上的计算量，从而提高匹配速度，算法比较简单，易于实现。
SSDA是对公式2.1所示MAD算法的一种优化，MAD在计算时，要顺序地在匹配检测区域内计算有关各个的差别值，然后找出最小值。而在SSDA中只计算局部匹配值，而不是每次匹配时都计算出模板图像中全部像素灰度绝对值，这样就可以大大节省计算量。
SSDA计算时：
a．定义绝对误差：
其中为基准图像，为模板图像，
b．取阈值T；
c．在中随机选取像素点，计算它同对应点的误差值，然后把误差求和，当累积到r次后误差超过固定阈值T，停止累加，记录上次数r，定义SSDA检测曲面：d．把值最大的点作为匹配点，因为这点上需要很多次累加才能使总误差超过T。
图2.3给出了三条不同的误差积累曲线，其中A，B不是匹配点。
图2.3 固定门限T误差积累曲线
2004年米长伟等人改进了SSDA，使门限T变为平行于图2.3中C的自适应值；并且把匹配过程分为粗匹配和精匹配两步，大大简化了计算量[6]。2009年胡凯等人把改进的SSDA用并行化实现，进一步降低了时间开销[7]。
综上所述，利用灰度信息匹配方法的主要缺陷是计算量大，对各种图像的变换较为敏感（如光照变化、角度旋转等），所以这些方法较少被用于实际。
2.2特征匹配
特征匹配是指通过分别提取两个或多个图像的特征（点、线、面等特征），对特征进行
