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.