2.2.2　特征点匹配算法

特征点又称兴趣点、关键点，它是在图像中相对比较突出的一些点，常把角点作为特征点。寻找特征点的方法有很多，如sift、surf、harris、shi-tomasi、brisk、orb等。不同的处理方法对图像缩放、旋转的处理效果不同，一般效果强大、适用性强的处理方法的速度相对较慢。本小节以ORB[1]为例介绍特征点匹配算法。

Step1：特征点提取FAST[2]。FAST（Features from Accelerated Segment Test）的基本思想是若某像素点p与其周围邻域内（1到16）足够多的像素值相差较大，则该像素可能是角点。原始的FAST特征点是没有尺度不变性的，OpenCV中ORB是通过构建高斯金字塔，然后在每一层金字塔图像上检测角点来实现尺度不变性。原始的FAST也不具有方向不变性，ORB的论文中提出用灰度质心法来解决这个问题。对于任意一个特征点p来说，定义p的邻域像素的矩为，其中I（x,y）为点（x,y）处的灰度值，图像的质心为：，特征点和质心的夹角即为FAST特征点的方向：。

Step2：特征点描述BRIEF[3]。BRIEF（Binary Robust Independent Elementary Features）算法的核心思想是在特征点p的周围以一定的方式选取N个点对，然后将这N个点对的对比结果组合成一个长度为n的二值码串，作为该特征点的描述子。ORB在计算BRIEF描述子的时候，建立的坐标系是以特征点为圆心，以特征点p和取点区域的质心q的连线为x轴建立的二维坐标系。圆心是固定的，以点pq连线为x轴，垂直方向为y轴，在不同的旋转角度下，同一特征点取出来的点对是一致的，这就解决了旋转一致性的问题。

Step3：特征点匹配。两个等长二进制串之间的汉明距离（Hamming Distance）是两个二进制串对应位置的不同字符的个数。ORB中用Hamming Distance来衡量两个描述子之间的距离。

Step4：匹配筛选。当特征点比较相似时，那么该如何进行点对之间的筛选呢？2004年，D.G.Lowe在论文“Distinctive image features from scale-invariant keypoints”[4]中提出了基于最近邻和第二近邻匹配距离的比例来剔除模糊的匹配。Ratio Test用来剔除距离相差过大的配对点，配对点之间的距离相差越大，能匹配上的概率也就越小。这里使用一个参数ratio来剔除距离在一定范围之外的特征点。

基于40000个特征点，统计分析最近邻和第二近邻的匹配比值和匹配正确的关系，其中实线表示匹配正确的概率，虚线表示匹配错误的概率，从而得到当累计密度概率为0.75时，可以最大概率地把正确匹配和错误匹配分开。伪代码如下：

good = []
for m,n in matches:
if m.distance < 0.75*n.distance:
good.append([m])

[1] Rublee E,Rabaud V,Konolige K,et al.ORB:an Efficient Alternative to SIFT or SURF[C].International Conference on Computer Vision.IEEE Computer Society,2011.

[2] Rosten E,Porter R,Drummond T.Faster and Better:a Machine Learning Approach to Corner Detection[J].IEEE Trans.PAMI,2010.

[3] Calonder M,Lepetit V,Strecha C,et al.Brief:Binary Robust Independent Elementary Features[C].ECCV,2010.

[4] Lowe D G.Distinctive Image Features from Scale-invariant Keypoints[C].IJCV,2004.