基于局部相似性的特征匹配篩選算法

馬正見，文志誠，尹歡一

（湖南工業大學 計算機學院，湖南 株洲 412007）

0 引 言

圖像匹配是計算機視覺的一個重要研究方向，在人臉識別[1]、遙感圖像[2]以及圖像分類[3]等方面具有重要作用?，F有的圖像匹配技術按匹配對象可以分為基于像素、基于特征和基于頻域三類[4]。這三類方法中，基于像素的配準方法存在處理效率低、對重疊區域要求高的不足，基于頻域的配準方法在面對圖像噪聲時匹配質量又較差。因此目前主要的研究方向還是基于特征的匹配方式。

在國內外學者的不斷研究下，目前已經提出許多基于特征的圖像匹配算法。其中由Lowe 提出的SIFT 算法通過構建空間金字塔的方式檢測穩定的特征像素點，以特征像素點鄰域的梯度直方圖為基準對特征像素點進行描述，所形成的特征像素點描述子對圖像的尺度以及旋轉變化適應性很強，但計算量過大也使該算法在效率上略顯不足。為了獲得效率上的提升，Bay 等人提出一種利用圖像積分檢測特征像素點的SURF 算法。該算法相對SIFT 算法在效率上有所提升，在遙感圖像[5-6]上也獲得了應用。

隨著對算法實時性要求的提高，研究者對之前的算法進行了優化[7-9]。同時，Rublee 等人提出更具效率的ORB 算法，算法在實時性上得到進一步提升，但也出現了特征像素點誤匹配率高的問題。為剔除誤匹配，許多優秀的篩選算法[10-12]被提了出來，其還是基于RANSAC算法的思想，通過不斷迭代求解像素點對間最優的線性變換矩陣，再用該矩陣重新對所有像素點對進行篩選。RANSAC 算法在處理平移以及模糊這一類特征像素點滿足線性關系的圖像時，篩選效果比較好，但對像素點間位置發生偏移的視角變化類圖像魯棒性不強，此外，迭代次數過多也使得篩選過程效率略低。

針對以上兩方面的不足，本文通過對非極大值抑制算法進行優化來降低初始誤匹配率，并在此基礎上提出一種基于局部相似性的篩選算法。通過待篩選像素點局部區域內其他像素點的相似性分布實現對誤匹配的篩選，降低了算法對像素點的線性要求，對視角變化的圖像具有更高的魯棒性。同時由于不需要過多的迭代，篩選過程中的效率也得到了提升。

1 ORB 算法

1.1 特征檢測

ORB 算法通過比較像素點與其鄰域內其他像素點的灰度值來檢測特征像素點。對任意位置的一個像素點P，選擇以該像素點為圓心，半徑為3 的圓上的像素點作為比較像素點。當存在連續的n個像素點的灰度值都大于或小于P點的灰度值時，就認為像素點P為特征像素點。當n取值為12 時，可以先與4 個頂點的像素灰度值相比較。當滿足條件的頂點少于3 個時，直接判定中心像素點P不是特征像素點。

此時檢測到的特征像素點還不具備方向屬性，因此還需要為特征像素點計算方向。這里使用像素的灰度質心描述當前特征像素點的方向，特征像素點的p+q階幾何矩定義為：

其中f(i,j)為圖像在坐標點(i,j)處的灰度值。幾何矩的質心為：

向量PC的方向即為特征像素點的方向，其值為：

1.2 特征描述子

對特征像素點進行描述時選擇一種改進的RBRIEF 算法，改進后算法生成的特征描述子具備旋轉不變性。算法以待描述特征像素點為中心，在S×S的鄰域窗口內按高斯分布選擇256 對像素點對，每對選擇的特征像素點對按式（4）進行描述。將所有描述按順序組合成最終256 維的特征描述子。

生成描述子時選擇的坐標系是以被描述的特征像素點為原點，向量PC的方向作為參考坐標系中x軸的正向。為了保證特征像素點描述子的旋轉不變性，需要將特征像素點在生成描述子坐標系中的坐標轉化至原圖像的坐標系中。兩個坐標系中的坐標轉換公式如式（5）所示：

將式（5）化簡有：

進行坐標轉換后的特征描述子就具備了旋轉不變性。

1.3 特征像素點的匹配

目前特征像素點的匹配主要采用暴力匹配方式，依據特征像素點描述子之間的Hamming 距離進行匹配。對待匹配圖像中的任意特征像素點，匹配圖像中與它距離最小的特征像素點即為它的匹配點。2 個匹配的特征像素點一起就組成了一對特征像素點對。

1.4 特征像素點對的篩選

特征像素點進行匹配后存在許多錯誤匹配，這里需要對匹配的特征像素點對進行篩選，剔除那些錯誤匹配的特征像素點對。傳統方法采用RANSAC 算法進行篩選，RANSAC 篩選算法步驟為：

1）隨機選取多對特征像素點對，這里一般選擇4 對；

2）用選出的特征像素點對計算H矩陣；

3）用H矩陣對其他的特征像素點對進行校驗，計算其誤差，并將誤差范圍內的點記為內點；

4）統計本次計算中內點的數目；

5）重復以上過程，選取內點數目最多的一次的H矩陣，剔除不滿足該H矩陣的特征像素點對。

2 改進算法

2.1 優化非極大值抑制算法

引起特征像素點對誤匹配的原因主要有兩種：一種是圖像噪聲之類的外部條件影響，導致特征像素點生成描述子時鄰域內有部分像素點對取值錯誤，使暴力匹配時的距離計算產生誤差引起誤匹配，這種誤匹配難以避免；另一種是對特征像素點進行非極大值抑制時抑制過度引起，這種情況可以通過優化非極大值抑制算法來降低誤匹配率。

進行非極大值抑制算法（NMS）的目的是減少特征像素點的數目和讓特征像素點分布得更均勻。通過比較特征像素點與范圍內其他特征像素點的響應強度值進行抑制。保留的特征像素點Pi需要滿足：

式中：f是特征像素點的響應強度函數；U是滿足條件的特征像素點集合，它是由以Pi為圓心，r為半徑的圓內所有的特征像素點組成代表Pi與P的歐氏距離。

過度抑制指的是準確匹配的特征像素點對中的某一個被錯誤地抑制。由于檢測到的特征像素點大多集中在紋理變化大的地方，因此抑制半徑大時就容易發生。過度抑制使留下的那個特征像素點進行暴力匹配時誤匹配至其他特征像素點，從而引起連鎖反應，增加了初始的誤匹配率。

為了盡可能地降低誤匹配率，本文對傳統非極大值抑制方法進行優化，優化為一種自適應的非極大值抑制方法（SA-NMS）。以生成描述子時的鄰域半徑作為抑制半徑，通過計算范圍內特征像素點的數目自動調節抑制的數目，減少過度抑制的出現。此時對于能夠保留下來的特征像素點需要滿足：

式中NUM(Pi)是抑制區域內特征像素點響應強度值大于中心特征像素點的數目；Pj_NUM 表示抑制區域內除中心外其他特征像素點Pj的總數；V是抑制范圍內Pj的集合。

在尋找特征像素點抑制區域即ROI 區域（感興趣區域）內其他特征像素點時，需要計算它與其他特征像素點之間的歐氏距離。但在ROI 區域內的數目僅占總數很小的比例，這使得每一次確定ROI 區域時有過多無效的距離計算。為了提升抑制算法的效率，這里對查找方法進行優化。

優化后ROI 區域查找過程如圖1 所示。將檢測到的特征像素點集合映射至x軸，按由小到大的順序進行排序。對計算的特征像素點按圖1b）所示在x軸上尋找ROI 區域，由于已經進行排序，因此可以直接判定邊界外的其他像素點不在抑制范圍內，減少了無效距離計算。在對下一個特征像素點抑制時，僅需在x軸上進行圖1c）這樣的邊界移動，排序后特征像素點在x軸上靠得很近，因此每次邊界移動僅有少數特征像素點變化。確定x軸的界限后計算一次特征像素點在x軸的上下限即可確定如圖1d）所示的最終抑制區域，最后將抑制范圍內的特征像素點按式（8）進行抑制即可。

由于每次對新的特征像素點進行抑制時僅需要移動x軸邊界以及一次y軸的上下限計算，因此相較于傳統抑制方法減少了大量的無意義距離計算。同時自動調節抑制數目的方式也減少了因過度抑制引起的高誤匹配率問題。優化后算法的偽代碼如算法1 所示。

算法1 自適應非極大值抑制算法

圖1 抑制區域查找

2.2 基于局部相似性的匹配篩選算法

實驗發現，對于準確匹配的特征像素點，它們在圖像中的位置都相對固定，在局部范圍內與其他準確匹配的特征像素點之間距離遠近關系也保持高度相似。而那些誤匹配的特征像素點卻與它對應的位置相隔較遠，因此誤匹配的兩個特征像素點局部范圍內的其他特征像素點幾乎完全不同。

基于以上特性，本文提出以特征像素點局部范圍內其他特征像素點分布的相似程度作為篩選標準的LSD篩選算法。算法分為兩個階段：第一階段從粗匹配中提取準確率高的點對作為參照對象，并通過局部相似性驗證從而確保準確性；第二階段利用反向局部相似性篩選剩余匹配點對。

首先定義特征像素點P的K近鄰特征像素點Pk為：

式中d(P,k)為特征像素點P和Pk的歐氏距離。定義特征像素點P的局部區域NNk(P)為：

將特征像素點P到局部區域內其他特征像素點的距離按由小到大的順序組成距離向量DP：

通過距離向量就可以計算特征像素點對的局部相似度。對某特征像素點對進行計算時，對于兩個距離向量內匹配的距離項，計算這兩個距離項在距離向量里的索引差值。在這里匹配的距離項指的是這兩個距離項對應的另一對匹配的特征像素點的距離。對不存在匹配距離項的，則默認索引差值為距離向量的總項數。將單個距離向量計算出的所有索引差值相加即為特征像素點對的局部相似性度S，越小說明這兩個特征像素點局部范圍內特征像素點的分布越相似，該像素點對準確匹配的幾率越高。

算法的第一階段需要從粗匹配中提取匹配準確率高的特征像素點對。實驗發現，粗匹配中Hamming 距離越小的特征像素點對的匹配準確率越高。因此第一個階段將粗匹配按距離由小到大的順序進行排序，挑出排列靠前的n對特征像素點對。這里n的取值依據粗匹配的數目確定。

為了確保挑出特征像素點對的準確率，需要對它們進行校驗。如圖2 所示，以正確匹配的T1，T2和誤匹配的F1為例，當局部范圍的k取值為3 時，T1的局部相似度計算的值為5（1+1+3），T2計算的值為0（0+0+0），而F1的值為9（3+3+3）。誤匹配的特征像素點對計算出的局部相似度值明顯要高于準確匹配，此時設定一個閾值就可以輕松地區分誤匹配。用以上方法對所有挑出的特征像素點對進行校驗，剔除超過閾值的誤匹配像素點對。雖然這一階段挑出的像素點對本身就有很高的準確率，但進行一次校驗仍是非常有必要的。

圖2 特征像素點對校驗

在完成第一階段特征像素點對的挑選后，接下來就要對剩余部分進行第二階段的篩選。由于第一階段經過校驗的特征像素點對的準確率遠遠高于第二階段，因此這一階段選擇反向局部相似性的篩選方法。同時考慮到距離對篩選結果的影響，在計算反向局部相似度時設定如下影響權重：

正在篩選特征像素點對局部區域內的特征像素點Pj的反向相似度因子為代表Pj認為正在篩選的特征像素點P準確匹配的程度，它的值為Pj距離向量里特征像素點P與Pj距離的索引差值。此時反向局部相似度RSP的計算公式如下：

按距離由小到大的順序每次選擇一對剩余的特征像素點對進行篩選。每次篩選進行以下操作：

按距離由小到大的順序每次選擇一對剩余的特征像素對進行篩選。每次篩選進行以下操作：

1）計算兩個特征像素點的局部區域；

2）計算局部區域內其他特征像素點的距離向量；

3）依據距離向量計算每個特征像素點的反向相似度因子；

4）將計算得到的所有相似度因子相加得到反局部相似度；

5）反局部相似度低于閾值則保留，否則剔除。

基于局部相似性篩選算法偽代碼如算法2 所示。

算法2 基于局部相似性篩選算法

3 實驗分析與比較

本文采用K.Mikolajczyk 和C.Schmid 所創建的標準開源數據集中的圖像進行測試。測試數據集包含圖像模糊、旋轉以及光照變化等8個系列，每個系列各含有6張圖像，對應同一場景受影響程度不同的圖像。在測試圖像集上進行仿真實驗，并將本文算法與傳統算法的實驗結果進行對比分析。

3.1 實驗環境

筆記本電腦處理器為Intel?CoreTMI5-4200U，主頻1.60 GHz，內 存 4 GB，64 位 Win7 操 作 系 統 ，Visual Studio 2015 和 OpenCV 3.1.0。

3.2 自適應非極大值抑制實驗分析

為驗證優化后的自適應非極大值抑制算法與傳統非極大值抑制算法在抑制效果和效率上的差異，在相同的實驗環境下，分別使用兩種算法對測試圖像集進行實驗。

表1 是兩種非極大值抑制算法的運行結果。通過表1 比較可以看出，優化后的自適應非極大值算法相較于傳統算法能保留更多的特征像素點，有利于特征像素點的匹配。從效率上來看，傳統方法每處理500 個特征像素點平均用時35 ms，而優化后算法僅需18 ms，總體上提升了50%左右。這也證明左右界限標記的方式能夠有效地減少距離計算，在效率上優化后的算法更佳。

表1 非極大值抑制結果

圖3 展現的是測試圖像經過傳統非極大值抑制算法與本文抑制算法后的特征像素點匹配時的誤匹配率?？梢钥吹接脙灮蟮姆菢O大值抑制算法所產生的誤匹配率均略低于傳統方法。尤其是在bikes、leuven 這一類紋理變化比較大的圖像上效果更為明顯。

圖3 非極大值抑制后的誤匹配率

3.3 基于局部相似性篩選實驗

為對比本文提出的LSD 篩選算法與RANSAC 算法對誤匹配特征像素點對的篩選性能，用圖像測試集中光照變化、模糊變化、視角傾斜以及旋轉變化系列進行4組特征像素點對篩選實驗，以剔除的特征像素點對的數目衡量算法篩選能力，同時記錄篩選算法的運行時間。

特征像素點對數目在篩選過程中的變化如表2 所示。其中由于wall、boat 圖像有方向上的旋轉，因此許多特征像素點對不能很好地滿足RANSAC 計算的H矩陣，所以在這兩組實驗中RANSAC 算法剔除的特征像素點對數目較多。而本文提出的LSD 算法減弱了特征點坐標的線性要求，因此方向旋轉對剔除的數目影響不大，并且由于本文提出的LSD 算法避免了過多的迭代，故在效率上也更高。

表2 匹配篩選實驗結果

3.4 對視角變化圖像魯棒性實驗

由于本文提出的篩選算法主要考慮匹配點對的局部相似性，因此可以用于視角變化這類圖像的篩選。以基準開源數據集中6 個不同視角拍攝的涂鴉（graf）圖像作為測試圖像，將測試圖像集中每2 張圖像分為一組，用LSD 算法進行實驗，得到的結果如表3 所示。

表3 視角變化圖像匹配篩選結果

由表3 分析可以得到以下兩個結論：一是視角變化下圖像的粗匹配產生的誤匹配比其他類型多，這點可以從被篩選的數目看出來；二是用本文提出的篩選算法對小視角變化圖像仍具備良好的篩選效果，篩選的效率以及篩選后的準確率都能達到其他類型圖像的標準，對視角變化的圖像具有魯棒性。

部分視角變化圖像篩選后的結果如圖4 所示。

可以看到：圖4 兩幅圖像中匹配的特征像素點并不滿足線性關系，此時用RANSAC 算法并不能計算出特征像素點間的線性變化H矩陣；而使用本文提出的篩選方法對視角有變化的圖像篩選后仍能保留大量準確匹配的特征點對，這也驗證了本文提出的LSD 篩選算法對視角變化的圖像的魯棒性。

圖4 視角變化圖像匹配篩選

當視角變化的程度不斷增大時，特征像素點的檢測也變得越來越難，同時描述特征像素點時它鄰域內的像素也發生了變化，使得特征像素點間變得難以匹配。對graf 圖像系列不同程度視角變化圖像進行實驗的結果如圖5 所示。

圖5 視角變化程度對算法的影響

可以看到，隨著視角變化的程度增大，圖像間匹配到的特征像素點對越來越少。在變化較小時還能保留較多的特征像素點對。一旦變化程度加大，特征像素點的描述子描述的信息區域發生改變，導致粗匹配能匹配到的特征點對迅速減少，雖然用本文提出的篩選算法還能保留少量匹配的點對，但篩選的效果也并不夠好。經過兩次的視角變化后，再進行篩選效果也不明顯。

4 結 語

針對傳統ORB 算法誤匹配率高、迭代速度慢的缺點，本文提出了一種基于局部相似性的特征篩選算法。為降低特征點粗匹配的誤匹配率，本文還對傳統的非極大值抑制方法進行了優化。實驗結果表明，優化后的自適應非極大值算法有更高的效率和更低的誤匹配率。此外，本文提出的特征篩選算法在保持高準確率的同時還減少了迭代計算，對視角變化的圖像也展示出了更強的魯棒性。