基于余弦相似度的改進ORB匹配算法

成 怡 ，朱偉康 ，徐國偉

（1.天津工業大學 電氣工程與自動化學院，天津300387；2.天津工業大學天津市電工電能新技術重點實驗室，天津300387）

目前，許多圖像特征點匹配算法都在使用二進制特征描述符，例如 BRIEF[1]、ORB[2]和 DAISY[3]等算法，這是因為它們相比于SIFT[4]、ASIFT[5]和SURF[6]這類使用梯度描述符的算法，擁有計算量少、存儲更緊湊的優點。二進制特征描述符通常采用漢明距離（Hamming distance）匹配方法進行特征匹配。

漢明距離[7]是通過將2個二進制特征描述符按位做異或操作求得，所求得的結果中1的數量越少，代表2個二進制描述符越相似。它相比于歐氏距離[8]、馬氏距離[9]和信息熵[10]這些相似性算法，在計算效率上遠遠超過后者。但是在某些特殊情況下，例如原圖像和目標圖像有許多相似區域時，會呈現出較高的誤匹配率。即使應用 RANSAC（Random Sample Consensus）算法消除誤匹配點，誤匹配率仍然很高，因為漢明距離只能證明兩特征點所在的鄰域信息相似，但是卻很難描述兩點的空間幾何狀態和位置信息。

目前改善這個問題的方法有許多，大致可以分為3類。第1類方法就是改善局部特征描述符，讓其具備空間幾何狀態和位置信息。例如融合全局環境描述符（integrate Global Context descriptor）[11]、嵌套 SIFT 描述符（Nested-SIFT descriptor）[12]、興趣點對描述符（pairs of interest point descriptor）[13]、空間幾何信息描述符（spatial geometric information descriptor）[14]等。以上方法可以改善這一問題，但是其特征描述符的計算往往比較繁瑣，導致匹配時間增加，從而降低匹配效率。第2類方法是改進匹配算法，例如Beis等[15]提出的NN算法，通過調整閾值（最近鄰向量和下一個最近鄰向量之比）來削減一些誤匹配。雖然該方法比較巧妙，相比于改善局部特征描述符的方法降低了計算量，但是因為其匹配閾值的變化，容易丟失一些正確的匹配點，導致遺漏正確匹配點。第3類方法是利用對極幾何的約束，例如Zeng[16]提出的RANSAC方法，首先使用文獻[17]中提及的K近鄰算法進行粗匹配，然后使用全局拓撲相似性約束條件篩選出精確匹配關系。該方法能從包含大量局外點的數據集中估計出高精度的參數。

近年來，國內外研究者針對此問題提出了一些改進方法。例如文獻[18]中提出的一種模塊分割算法，利用灰度變化率和子區域特征有效因子剔除低質量圖像模塊和關鍵點。其次,針對在兩幀圖像匹配過程中對過多無效特征點進行匹配產生誤匹配的問題,提出利用相機前一時刻位姿剔除當前幀圖像中不在前一幀圖像視野中的特征點。該算法意在通過對圖像進行模塊分割以及剔除不在前一幀圖像上的特征點的方法，來彌補特征描述子沒有空間幾何信息的缺陷，但該方法為保證剔除特征點的正確性上，使用了較多時間，且因為剔除低質量圖像模塊而丟失了圖像信息完整性，不能滿足算法實用性。文獻[19]中提出的融合顏色不變量和形狀信息的圖像匹配方法是通過提取特征點的主曲率信息進行全局形狀描述，最后將生成的描述子與二進制描述子融合，用于特征點匹配。該算法雖然一定程度上解決了多相似區域圖像特征點匹配誤匹配率高的問題，但因為其引入了SIFT算法的特征點提取算法，且計算特征點曲率耗時較高，不能滿足算法的實時性要求。綜上，要在保證實時性的基礎上提升算法性能，成為了解決該問題的關鍵。

本文從降低誤匹配率、保持正確匹配點數角度開展研究，提出一種融合漢明距離和角度余弦不變性[20]的方法。首先利用漢明距離來測量二進制特征值的相似度，然后計算匹配向量間的角度余弦，利用角度余弦的不變性，消除那些“良好”的誤匹配，最后再使用RANSAC算法消除誤匹配點。本方法以期在保證算法實時性的同時，提升算法性能。

1 ORB圖像特征點匹配算法

ORB圖像特征點匹配算法可歸納為兩個步驟：一是特征描述符的生成；二是對特征描述符進行匹配。ORB特征描述符，是將FAST特征檢測和改進后的BRIEF描述符相結合的一種特征描述符。先通過FAST進行特征點檢測，特征點的方向通過獲取特征點附近的質心獲得。文獻[21]定義鄰域的質心計算方法如公式（1）所示：

式中：x，y是FAST特征點的位置，鄰域圓的半徑為r，x，y的定義域為[-r，r]。圓形鄰域內的質心計算公式如下：

FAST特征點的方向：

BRIEF描述符的主要思想是隨機選擇以特征點為中心，一定大小鄰域內的幾組點對，比較這些點對的像素的灰度值大小，并按位記錄結果（前者小于后者的像素值記1，其他記0），組成一組二進制字符串作為特征點的特征描述符。但是，當圖片旋轉度數超過15°時，匹配的效果很差，為了增加描述符的抗旋轉能力，ORB基于BRIEF描述符的生成方法進行了改進：

（1）先用oFAST算法，檢測關鍵點的位置。oFAST是帶有方向的FAST角點檢測算法，增加了計算角點方向，方向角為θ。

（2）將上述計算出來的BRIEF描述符定義為一個2N的矩陣，將矩陣旋轉角度θ，就得到了有方向的BRIEF描述符，也就是Steered BRIEF描述符。

（3）用一種貪婪學習算法篩選具有高方差和高不相關的Steered BRIEF描述符，結果稱之為rBRIEF。

所以，ORB特征描述符，實際上是oFAST和rBRIEF的組合計算所產生的。

ORB通常采用漢明距離匹配方法進行特征描述符的匹配，首先設定閾值M（最小值為零，最大值為特征描述符的長度），然后將2個進行匹配的特征描述符STR1、STR2按位進行異或操作，并計算所得結果STR3中的1的數量存于整型變量SUM中，如果SUM小于等于閾值M的值，則將此對特征進行匹配，否則不進行匹配。

通過ORB特征描述符的生成過程可以看出，ORB比較明顯的缺點有兩點：

（1）ORB特征描述符是通過隨機選擇特征點為中心，半徑為r的鄰域圓內的幾組點對比較大小，并按位記錄結果，所以當圖像出現尺度變化時，對應的鄰域也會發生變化，導致特征描述符發生變化，從而導致失配。

（2）ORB特征描述符本身不具備鄰域的位置和空間信息，它只能描述以特征點為圓心，半徑為r的鄰域圓的像素信息，如果圖像內部出現較多相似區域，會導致相似區域內的特征點其鄰域內的像素信息基本一致。這時如果使用漢明距離匹配算法進行匹配，結果會因為相似區域無法分辨而出現較多的誤匹配。

2 改進的ORB算法

漢明距離的單一方法會導致較高誤差的匹配率。為了保證匹配率以及匹配精度，本文提出漢明距離和余弦相似度相結合的方法，改進ORB算法，即用Hamming距離反映向量在數值特征上的差異，用余弦相似性反映向量在方向特征上的差異，再進行特征點匹配，然后采用RANSAC方法消除誤匹配來提高匹配性能。

余弦相似度是用余弦值來度量向量空間中兩個向量之間的差異大小，與距離度量相比，余弦相似度更關注兩個向量在方向上的差異，而不是距離或長度上的差異。余弦相似性是最常用的相似函數之一，其計算公式[22]如公式（4）所示：

式中：a，b為要求取余弦相似度的 2個向量；cos（θ）為2個向量的余弦相似度；向量余弦的范圍為[-1，1]。余弦值越大，表示2個向量之間的角度越小；余弦值越小，則2個向量之間的角度越大。

余弦可以用來評估幾何中2個矢量之間的方向差。本文采用這一原理來度量特征向量之間的差異。改進ORB算法步驟如下：

（1）首先通過原始ORB算法用Hamming距離進行一次漢明距離閾值為P的特征點匹配，然后抽取其中N組特征點對，計算每組中2個特征向量之間的余弦相似度，記為數組C。

（2）將這N組點對的余弦相似度C兩兩作差，得到所有特征向量的余弦相似度之差存于數組A，之后將A數組內的數值兩兩作差，找出A數組中出現頻率最高的一組數，將其余弦相似度賦值給θ，作為本次匹配過程的最優余弦相似度。簡單的講，θ是最接近這次匹配中，圖像發生變化的角度B所計算的余弦值的值cos（B）。

（3）根據實驗經驗，考慮實際情況中機器誤差等其他外界因素。用[θ-0.3，θ+0.3]作為閾值范圍。

（4）應用Hamming距離特征匹配方法重新對圖像進行自由度為m的特征點匹配（若閾值為P，則Hamming距離為[0，P+m]的均可先視為正確匹配），計算所有特征點對的余弦相似度存于數組D，如果余弦相似度在經驗閾值范圍內，則先視為正確匹配，若不在，則視為誤匹配剔除。

（5）篩選后若仍然存在一個特征點有N組匹配都在閾值范圍內的情況，則利用公式（5）進行篩選。

式中：Hi為第i個特征點與正在進行篩選的特征點之間的Hamming距離；H1為第1個特征點的二進制描述符的長度；cos（θi）為第i個特征向量與正在進行篩選的特征向量之間的余弦相似度；θ為最優余弦相似度；s為匹配相似度；m和n分別為距離權重和余弦相似度權重，代表二者在匹配過程中的重要程度。

（6）將N組匹配一次進行計算，保留s取得最大值的匹配視為最優匹配，其他的N-1個匹配消除。若N組的余弦角值都不在閾值范圍內，則視為誤匹配消除。

（7）應用RANSAC算法消除誤匹配。

改進ORB算法流程圖如圖1所示。

改進ORB算法降低了距離相似度在特征匹配中的權重，重視圖像之間存在的空間角度變化，該方法是以空間角度變化這一大方向為主導來進行特征點的匹配工作。

圖1 改進ORB算法的流程圖Fig.1 Flowchart for improving the ORB algorithm

3 改進ORB算法圖像匹配實驗

選擇3組圖片分別用原始ORB算法與改進后的ORB算法進行特征點匹配實驗，并將結果用RANSAC算法消除誤匹配。此實驗應用系統環境是WIN7系統，CPU處理頻率為3.7 GHz，軟件使用的是VS2013軟件，3組實驗中圖像匹配的參數設定如表1所示。

表1 3組實驗圖像匹配參數表Tab.1 Three groups of experimental images matching parameter table

改進ORB算法的參數設定如表2所示。

表2 改進ORB算法參數設定表Tab.2 Parameter setting for improving the ORB algorithm

3組圖片匹配后的結果如圖2所示。

圖2 3組實驗結果圖Fig.2 Three groups of experimental results

從圖2的3個圖片的原始ORB算法與改進ORB算法匹配結果看，改進后的算法的特征點對多于原始算法，降低了RANSAC剔除誤匹配后的特征，保持了匹配精度。實驗結果數據對比如表3所示。

表3 綜合實驗結果Tab.3 Comprehensive experimental results

由表3可知，在第1組實驗中，改進ORB算法的粗匹配成功率較原ORB算法提高了2%，誤匹配率下降了28.4%；第2組實驗中粗匹配成功率較原ORB算法提高了2.25%，誤匹配率下降了29.8%；第3組實驗中粗匹配成功率較原ORB算法提高了2.55%，誤匹配率下降了31.8%。改進算法誤匹配率僅為原算法的20%左右，降低了原算法誤匹配率近80%。

上述3組實驗證明了改進ORB算法在降低誤匹配率上的可行性。而其中粗匹配率提高是因為降低了對漢明距離的閾值要求，更加注重兩個特征向量的余弦相似度的相似性，使得有些原本應該被距離相似度剔除掉的特征點又有了成功匹配的機會。

4 改進ORB算法的對比分析

對一張擁有相似內部區域的圖片進行尺度、旋轉、平移變化，將變化后的圖片與原圖片分別用SIFT、SURF、ORB及改進的ORB算法進行特征點匹配實驗，分析改進后的ORB算法的魯棒性。匹配結果對比如圖3所示，匹配結果數據統計分析如表4所示。

圖3 4種算法匹配結果圖Fig.3 Matching results of four algorithms

從圖3和表4可以看出，SIFT算法獲得最多的匹配點，但是時間耗時最久；SURF算法在效率方面是SIFT的近4倍；ORB算法特征點數量最少，但匹配速度卻是SIFT的20多倍。本文提出的改進ORB算法，通過余弦相似度進行匹配，在抗旋轉性能上效果顯著，是原算法匹配點對數的2.39倍，匹配精度明顯提高，而且匹配耗時相對較少。

表4 4種算法匹配結果數據統計分析表Tab.4 Statistical analysis table of matching results of four algorithms

通過上述對比實驗可以證明，本文提出的改進ORB算法，通過加入余弦相似度匹配與漢明距離匹配相結合，將圖像存在多區域時原ORB算法的誤匹配率降低，且隨著匹配特征點數目的增加，降低的百分比也會隨之增加。

5 標準數據集實驗及分析

上述實驗證明了本文改進的ORB算法相較于原ORB算法在多相似區域圖像特征點匹配問題上誤匹配率有明顯的下降。本章節將原始ORB算法、本文改進的ORB算法、文獻[15]提及的NN方法、文獻[18]提及的融合描述子法在Mikolajczyk 05標準數據集中，通過視角變化（wall）、光照變化（leuven）、尺度和旋轉變化（bark）、圖像模糊（bikes）這4種圖像變化，分析對比算法的性能。圖4給出了4種變化的測試圖像，每組圖像都進行了不同強度的變化。

本實驗通過改進最近鄰匹配閾值K，重復10次匹配，并畫出各算法錯誤率（1-precision）-查全率（recall）對比曲線。該曲線是圖像匹配算法的常用評價指標，其中查全率是正確匹配點數與圖像間一致區域數目比值，錯誤率是誤匹配點數與總匹配點數的比值，在查全率相同時，錯誤率越小匹配效果越好，在錯誤率相同的情況下，查全率越大越好。對于整體曲線，曲線位置越高效果越好。

查全率和錯誤率的計算方法如公式（6）與公式（7）所示：

正確匹配點數以及圖像間區域一致的區域，可通過公式（8）[23]進行計算：

圖4 4種變化的圖像序列Fig.4 Four variations of the image sequence

其中：ua和ub是2個特征區域；A為單應區域，與單應矩陣H對應；ε0為區域的交疊誤差，實驗中取20%。

實驗結果如圖5所示。

圖5 錯誤率（1-precision）-查全率（recall）曲線Fig.5 Error rate(1-precision)-recall curve

根據實驗結果分析，視角變化下，本文改進算法曲線位置相較于其他算法更高。由于視角變化圖像序列的紋理結構有很強的局部相似性，因此也證明了本文改進算法在處理多相似區域圖像特征點匹配時能力更為出色；尺度和旋轉變化下，本文改進算法也表現出了超過其他3種算法的能力。而光照變化和圖像模糊變化下，4種算法的性能基本相同，本文改進算法只是稍有優勢。

6 結論

本文提出了一種改進ORB算法，將漢明距離相似性度量與余弦相似性度量相結合，首先通過漢明距離低自由度粗匹配，計算特征向量的余弦相似度，其次通過梯度計算法計算余弦相似度的最優閾值范圍，然后在漢明距離高自由度粗匹配的基礎上，利用余弦相似度不變性剔除誤匹配點，最后用RANSAC算法再次精確匹配，解決了原ORB算法在匹配多相似區域圖像時誤匹配率高的問題。實驗表明，該算法降低了原算法相似區域失配率80%左右。并且超越了ORB算法原有的對于圖像變化的適應性（包括圖像尺度變化、旋轉變化、視角變化、圖像模糊、光照變化），同時仍然保持著其運算的實時性。