特征点匹配算法详解

特征点匹配的方法分为两类：一类是对特征点通过局部描述子进行描述，然后根据特征点描述子之间的距离进行匹配；另一类是基于点与点之间的几何约束，将特征点匹配问题转化为一个最优化问题进行求解。

1）基于局部特征描述子的特征点匹配

有效的特征描述子不仅需要具备很强的辨别能力，而且还需要有很高的稳定性。具有强辨别能力的特征描述子是指不同特征点的描述子能够被很好地区分开来。而能够使得不同图像中同一特征点得到很好的匹配的描述子称为具有高稳定性的特征描述子。比较经典的特征描述子有SIFT特征描述子、SURF特征描述子、Affine－SIFT特征描述子、GLOH特征描述子、基于灰度序的特征描述子等。

1999年British Columbia大学David G.Lowe教授正式提出了一种基于尺度空间的图像局部特征描述子，称为SIFT特征描述子。SIFT特征描述子是指通过特征点周围领域内的梯度直方图来描述该特征点。首先，划分特征点的支撑区域为4×4的子区域；然后，统计每个子区域里8维的梯度直方图；最后，用4×4×8＝128维向量来表示每个特征点，称其为该特征点的SIFT特征描述子。为了提高SIFT特征描述子的稳定性，在进行梯度直方图统计的时候，根据样本点的梯度大小及其到特征点的中心距离设定权重，并将该权重线性地分配到8个相邻bin上，以便减少直方图由于每个bin边缘上的点的变化而引起的不稳定性。由于SIFT特征描述子本质上就是要在不同尺度空间上查找特征点，这些特征点不会随着光照条件的改变而消失，例如暗区域中的亮点、亮区域中的暗点、边缘点、角点等。因此，SIFT特征描述子可以很好地解决在不同尺度下的图像特征点匹配问题。此外，梯度方向对于恢复线性变化是不变的，且分块梯度方向直方图统计方法对于仿射变换和噪声等图像变化有一定的鲁棒性。即SIFT特征描述子对图像缩放、旋转甚至仿射变换保持不变性，因此该特征描述子具有很强的辨别能力和很高的稳定性。图6－39为基于SIFT特征描述子在视角变化、旋转＋尺度变化、光照变化和尺度变化下特征点匹配的结果。

(www.xing528.com)

图6－39　基于SIFT特征描述子的特征点匹配结果

由于SIFT特征描述子是根据特征点的局部信息进行特征描述的，因此对于结构性比较好的图像，如建筑物的图像，往往包含很多重复性纹理，此时仅仅使用SIFT特征描述子对特征点进行描述往往得不到满意的匹配结果。针对此类图像，Mortensen等人提出了利用全局信息增强SIFT特征描述子。由于特征点周围的颜色信息可以为特征点匹配提供很重要的信息，因此Abdel－Hakim和Farag提出了对颜色变换更加鲁棒的适用于彩色图像的CSIFT特征描述子，是SIFT特征描述子的推广。

SURF特征描述子对SIFT特征描述子进行了改进，利用Haar小波近似SIFT特征描述子中的梯度直方图，并采用积分图技术提高运算速度，使得SURF特征描述子的计算速度是SIFT计算速度的3～7倍。Affine－SIFT特征描述子通过模拟所有成像视角下得到的图像进行特征匹配，可以较好地处理大视角变化下的图像匹配。GLOH特征描述子（Gradient Location and Orientation Histogram）采用极坐标分块，是对SIFT特征描述子中支撑区域划分方法的扩展。由于极坐标分块的策略特别重视靠近特征点的局部区域，且相应地增加了远离特征点区域的分块大小，因此相较于SIFT特征描述子，GLOH描述子的稳定性更高。此外，由于特征点外围的区域重要性逐渐变小，需要包含更多的信息以便增加描述子的区分能力，因此基于极坐标分块的区域分块方法似乎更加合理。基于恢复序的特征点描述子通过基于局部方向梯度和基于恢复差分符号的图像特征，采用基于恢复序的特征点支撑区域的划分方法，分别得到两种特征描述子：MROGH和MRRID。该特征点描述子包含了图像灰度之间的大小关系，且不依赖于估计主方向，因此具有很强的辨别能力，能够得到很好的匹配结果。基于恢复序的特征描述子，首先根据特征点支撑区域内样本点的恢复序对支撑区域进行划分；然后，在每个划分内统计样本点基于局部方向梯度或基于灰度差分符号的图像特征；最后，将每个划分内的统计结果串接在一起得到该特征点的MROGH或MRRID特征描述子。

2）基于几何一致性约束的特征点匹配

基于几何一致性约束的特征点匹配是作为特征描述子进行特征点匹配方法的一个补充。几何性质包括距离、角度以及局部仿射不变区域等，而几何一致性约束是假定在不同图像中相近特征点之间的几何性质是保持不变或近似不变的。基于几何一致性约束的特征点匹配方法是根据特征点之间的几何约束，从一组初始的匹配点中找出满足几何约束的匹配特征点。其中初始的匹配点通常是基于特征描述子的特征点匹配方法得到的。初始的匹配点不要求精度，仅仅需要包含正确的匹配特征点即可。因此，一个最简单的初始匹配点可以是特征点之间的两两匹配，然后通过优化特征点之间的几何约束来得到最优的匹配特征点。综上所述，基于几何一致性约束的特征点匹配能够处理更一般的特征点匹配问题，甚至是非刚体形变下的特征点匹配问题。然而，该方法需要求解的最优化问题通常是很难的，且需要很大的计算量。Zhang等人首先提出了基于几何一致性约束的特征点匹配思想。Berg等人根据邻近特征点对之间的距离和角度是不变的这一几何性质，结合特征点之间的表观差异（Geometric blur）建立目标函数。由于建立的目标函数是二次的，因此将二次目标函数通过多个线性目标函数来近似，从而将非线性优化问题分解为多个线性子问题进行求解。Leordeanu和Hebert对基于几何一致性约束建立的优化问题中的整数约束进行松弛，通过构造图和谱技术进行特征点匹配。其中，图的节点由所有可能的特征点匹配构成，而边的权重则根据两个特征点匹配之间的几何一致性确定。基于几何一致性约束可知，由正确的特征匹配点对构成的边的权重很大，即正确的点匹配之间必然会建立起很强的关联，而错误的点匹配之间只是偶尔存在较强的关联。因此，由正确的特征点匹配将在所构造的图中呈现很强的聚类，则可以通过谱技术进行特征匹配。