融合GMS的ORB特征點提取與匹配算法

潘 峰，沈建新，秦 順，林 鑫

(南京航空航天大學 機電學院，江蘇 南京 210016)

0 引 言

特征點提取與匹配技術是圖像處理技術中的一個很重要的分支，對于目標檢測和同時定位與建圖(simultaneous localization and mapping，SLAM)等領域而言尤為關鍵[1]。現如今，特征點提取和匹配的算法種類及其變形數量很多。經典的算法包括將有方向的加速角點提取(features from accelerated segment test，FAST)[2]和帶旋轉的二進制獨立基本特征(binary robust independent elementary features，BRIEF)[3]融合在一起的ORB算法[4](oriented FAST and rotated BRIEF，ORB)、基于尺度不變特征的SIFT算法[5,6](scale-invariant feature transform，SIFT)、基于加速穩健特征的SURF算法[7](speeded up robust features，SURF)以及Harris Corner Detector[8]。這些算法在處理特定圖像變換時凸顯出了各自的優勢。ORB算法的一個特點就是檢測速度快，可用于實時圖像特征點提取與匹配，該算法中采用了旋轉不變性原則以此提高提取與匹配的準確性。

BRISK算法[9]、KAZE算法[10]以及AKAZE算法[11]也是極其優秀的算法，這些算法對旋轉和尺度變換都具有不變性，算法具有極好的魯棒性。

針對一些優秀的算法，國內的許多學者[12-14]也做了相關的算法變形，這些算法不僅擁有原算法的優點，還對原算法的一些不足進行了改進，讓算法性能顯得更加優秀。

由于傳統ORB算法提取的特征點分布不均勻，使得圖像有些區域提取不到特征點，從而浪費了圖像上的大量有用信息，同時在匹配的過程中利用運動平滑性約束剔除誤匹配的方法會導致仍然存在一些誤匹配，因此先利用四叉樹原理對圖像分區域提取ORB特征點，在提取完特征點之后使用GMS匹配方法[15]將運動平滑性約束替換成基于網格的剔除誤匹配的統計量，以此來剔除誤匹配，最終得到分布比較均勻且正確的匹配特征點對。

1 ORB算法分區域提取特征點

1.1 FAST角點檢測算法

ORB算法是目前特征點提取匹配中用的比較多的算法之一，該算法由Oriented FAST關鍵點和Steer BRIEF描述子兩部分組成。

FAST算法是一種二維圖像的特征檢測算法，它可以迅速地找出一張灰度圖片中潛在的特征點，而且速度飛快。

具體實現步驟如下：①以目標像素點p為中心，取半徑r上M個領域像素點。②分別計算取得像素點與目標像素點p的灰度之差的絕對值。③利用計算得到的灰度差的絕對值與所設定的閾值進行比較，如果大于閾值，則該點為FAST角點。

對原始ORB算法的特征提取進行改進，提出oFAST(FAST keypoint orientation)算法，在快速提取特征點后，又定義了特征點的方向，實現特征點的旋轉不變性。

1.1.1 粗提取

若判斷選擇的點是否是特征點，可以采取的方式是在該點周圍以一定半徑畫圓，來判斷這個圓里的點像素灰度大于圓心點灰度的數量是否大于某個閾值，若大于某個閾值，則說明圓心那一點為特征點，否則就不是特征點。FAST角點檢測原理如圖1所示。比較常用的是在圓心周圍選取9個像素點的FAST-9和選取12個像素點的FAST-12。通常可以先按垂直方向的關系選取4個像素點，如果這個4個像素點中有2個的像素灰度比圓心灰度大，有2個像素灰度比圓心灰度小，那么圓心點不是特征點。

圖1 FAST角點檢測原理

1.1.2 篩選最優特征點

篩選出最優特征點的方法有很多，其中機器學習的方式比較常見。把特征點周圍的像素點輸入到ID3算法訓練出來的決策樹中，以此來判斷該特征點是否是最優特征點，具體步驟如下：

在訓練圖片上利用FAST算法找到所有角點。為每個角點存儲一個向量，這個向量一般有16位，代表這個點周圍的16個像素。這個向量中的每一位都可以由式(1)所表示。在進行了上述處理以后，需要定義一個標志位變量來記錄這個點是否是角點，如果是角點，就將標志位記為True，如果不是角點，就將標志位記為False。最后利用ID3算法遞歸地查詢該特征點的每一個子集，遞歸終止的條件是所有子集的熵變成0

(1)

1.1.3 去除鄰域位置多個重復冗余的特征點

先計算某個特征點周圍像素灰度差值的絕對值來作該特征點的分數，如果該特征點鄰域范圍內還存在其它的特征點，也利用相同的方式，取其周圍像素灰度的差值來作為分數，最后統計這些鄰域特征點的分數，將其放在一起進行比較，選取分數最高的那個特征點作為該鄰域范圍內的唯一特征點，其它分數不是最高的特征點就不需要了，利用非極大值抑制的方式將其去除掉。非極大值抑制的公式如式(2)所示

(2)

ORB算法采用的Oriented FAST關鍵點采用灰度質心法實現了旋轉不變性，與FAST角點相比，不僅記錄了位置信息，同時也記錄了方向信息。若某個角點的坐標為O，則取該角點一定半徑內的像素灰度進行計算，灰度質心法中的矩的定義如下

(3)

其中，I(x,y) 為圖像灰度表達式。該矩的質心為

(4)

由式(4)的質心坐標可以計算得到特征點的方向，計算公式如下

(5)

1.2 BRIEF描述子生成算法

利用FAST角點檢測算法后可以在圖像上得到很多特征點，但這些特征點只有其自身信息，沒有周圍鄰域的信息，在紋理單一、灰度相同的地方沒法判斷這些點在兩幅圖像上的對應位置，因此需要將該點的鄰域信息也作為該點的一個屬性，這個屬性就是描述子，BRIEF算法就是一種描述子生成算法，該算法在FAST算法提取出來的特征點周圍鄰域選取多個點對，如果一個點對的灰度比較結果是大，則記錄為1，否則記錄為0，最后會生成一個類似的二進制編碼串，通常情況下N選取128、256或者512。

ORB算法的特征描述是由BRIEF算法改進的，稱之為rBRIEF(rotation-aware brief)，rBRIEF算法在原有特征描述算法的基礎上加入旋轉因子，以此來保證提取描述子的過程中能夠保證自身的旋轉不變性，不會影響到描述子的生成質量。

描述子生成步驟：

(1)利用方差為2，窗口大小為9×9的窗口對圖像進行高斯濾波，這樣做的目的是為了減少噪聲干擾。

(2)選取某一個特征點，在其鄰域范圍內隨機選取一個點對x和y，選取的次數根據所需要的描述子長度而定，每選取一個對點后，就進行這兩個點的灰度比較，如果x的灰度比y大，則記為1，否則記為0。具體計算公式如式(6)所示

(6)

其中，p(x),p(y)分別是隨機點x=(u1,v1)，y=(u2,v2) 的像素值。

根據所需要的描述子長度進行多次比較之后，即可得到一個長度為所需要長度，每一位的值都是0或1的二進制編碼串，這個串就表示該特征點的周圍鄰域信息，也就是它的描述子屬性，BRIEF描述子所對應的十進制數如式(7)所示

(7)

ORB算法采用的描述子是Steer BRIEF描述子，與BRIEF描述子相比，利用了關鍵點的方向信息，進而實現了描述子的旋轉不變性。具體方法是利用灰度質心法所得到的特征點的方向構建旋轉矩陣，利用該旋轉矩陣對隨機生成的BRIEF描述子矩陣進行變換，最終得到具有方向不變性的Steer BRIEF描述子。

傳統的ORB算法提取出的特征點過于集中，會出現扎堆的現象，不僅會降低一些需要對圖像進行特征點提取的算法的效果，比如說SLAM，同時也會減少一幅圖像上的信息量。通過對圖片劃分區域，從每個區域提取特征點可以保證最大程度上地使用圖片上的信息，同時也增加了算法的魯棒性。步驟如下：

(1)首先對圖像金字塔上的每層都劃分網格。

(2)利用FAST角點檢測器對每層金字塔圖像提取FAST角點，在紋理比較弱的區域如果沒法提取出特征點，就適當降低提取的閾值，以此保證能夠從整張圖像上獲取到足夠的FAST角點。

判斷是否是FAST角點的方法是比較某點像素與其周圍像素灰度的差值是否滿足某個閾值條件。利用角點響應函數和設置好的閾值T進行分析，倘若周圍16個像素點與p點的灰度差值之和大于T，則像素p即被判定為角點。角點響應函數如下

(8)

(3)利用四叉樹的思想，對每個網格中提取的特征點進行篩選，篩選方法是如果該網格中不存在特征點，則刪除該網格；如果該網格中存在特征點，則繼續將該網格劃分成四等分，再次判斷每個網格中是否存在特征點，最后按照一定的策略，挑選出分布均勻的FAST角點。

1.3 四叉樹策略篩選特征點

對于提取出的大量特征點，需要對這些特征點進行篩選，最終獲得滿足數量的特征點，但因為選擇策略的不同，會導致最終提取的特征點在圖像上的位置有所差別，影響最終特征點匹配的效果。因此本文采用四叉樹的篩選策略挑選特征點。

具體策略如下：

(1)首先需要確定初始的圖像中大概能分出幾個原始節點。將利用原始ORB算法提取過大量特征點的圖像分成幾份，一般將分辨率為640×480的圖像只分成一個節點，也就是四叉樹的根節點。

(2)若原圖像本來只有一個節點，則該節點在經歷第1次分裂后，1個根節點分裂成為4個節點，每個節點中的特征點就是落在該節點范圍內的特征點，都是來自原來的那個大節點。每次分裂完后需要統計每個節點中的特征點數量，如果某個節點所包含的特征點數量為0，那么就刪除該節點，如果某個節點里特征點數量為1，則該節點不再進行分裂，但不進行刪除，永遠保留下去，直到分裂終止再進行處理。如果該節點中特征點數量大于1，則表示節點還可以再分裂，每次分裂完后判斷此時的節點總數是否超過設定值，如果沒有超過則下次分裂時對那些仍然可以分裂的節點進行分裂。

需要注意的是，一個父節點在經過一次分裂之后就變成了4個子節點，而對于原來的父節點將不再需要，直接將其刪除，從總數量上來看，每次分裂都會增加3個節點，而不是增加4個節點。利用上述規律可以提前判斷大約分裂多少次之后就可以達到所需要的節點總數閾值，計算方式為：當前節點總數+即將分裂的節點總數×3。

(3)若新分裂的節點里的特征點還是大于1個，就再次分裂成4個節點。如此往復，一直分裂，分裂終止條件是節點的數量大于所需要提取出的特征點數量，或者所有節點都無法再分裂。

當出現很多個節點中所包含的特征點數量都大于1，都能進行下一次分裂的情況，這時采用的策略是優先分裂特征點數量最多的節點，然后分裂特征點數量次高的節點，以此類推，通過把特征點數量多的節點先分裂開來的策略可以使得特征密集的區域能夠更加細分。如果某些節點所包含的特征點比較少，可能會因為提前達到了節點閾值要求而不需要再分裂了，保證了提取時充分考慮到所有節點，提高了提取的準確性。

(4)當分裂達到節點閾值這個終止條件時，從所分裂出的每一個節點中利用非極大值抑制的思想選擇出角點響應值最高的特征點作為這個節點的代表特征點，而其它響應值低于該節點的特征點都將被刪除，不需要進行保留，通過四叉樹的策略從提取出的大量特征點篩選出合適的特征點，就得到了分布比較均勻且數目達到要求的特征點。

四叉樹策略篩選特征點如圖2所示。

圖2 四叉樹篩選特征點流程

2 GMS算法剔除誤匹配

對于暴力匹配后的結果，存在大量的誤匹配，利用GMS算法可以剔除誤匹配。該方法通過統計正確和錯誤匹配鄰域的可區分度，來判斷該匹配是否正確，進而剔除誤匹配。GMS匹配方法基于假設：如果匹配是正確的匹配，那么這個正確匹配的小范圍內的匹配集中在三維空間的同一個區域。同樣地，一個錯誤匹配的小范圍內的匹配會出現在三維空間的不同位置，幾乎不會出現在同一個區域。

假設輸入圖像I1有N個特征匹配，輸入圖像I2有M個特征匹配；定義C={c1,c2,…,ci,…,cN} 來表示圖Ia到圖Ib的最近鄰匹配，其中ci表示像素點pi與qi的匹配；定義ci的領域為

Ni={cj|cj∈C,cj≠ci,d(pi,pj)}

(9)

根據式(9)可以得到ci的相似領域，如式(10)所示

Si={cj|cj∈Ni,d(qi,qj)

(10)

其中，Si中元素的個數，也就是匹配ci的運動支持，用 |Si| 表示，d(·,·) 是兩點之間的歐式距離，r1和r2為距離閾值。對 |Si| 建模，如式(11)所示

(11)

其中，錯誤匹配被其某個鄰域窗口匹配支持的概率用ε表示，正確匹配被其某個鄰域窗口匹配支持的概率用t表示，鄰域Ni內匹配對的數量用 |Ni| 表示。通過分析得到式(11)期望為

(12)

以及式(11)的方差為

(13)

正確和錯誤匹配的可區分度可以通過期望和方差來表示，如式(14)所示

(14)

利用基于劃分網格的算法可以對以上算法進行加速，將兩幅需要進行匹配的圖像按照某種策略劃分成很多個小網格：ω1以及ω2，ci表示落在網格Ga和Gb中的一個匹配對，在圖3中用一條實線段表示。于是鄰域(表示在網格Ga中的匹配)被重新定義為

Ni={cj|cj∈Ca,ci≠cj}

(15)

相似鄰域被重新定義為

Si={cj|cj∈Cab,ci≠cj}

(16)

圖3 基于網格的框架

式(15)和式(16)中，Ga表示某個網絡，Ca表示落在Ga中的匹配對，Cab表示同時落在Ga和Gb中的匹配對。算法定義鄰域為落在同一網格中的匹配，定義相似鄰域為同時落在兩個網格中的匹配，即區對。

算法的性能與網格的大小有關系，如果網格非常小，那么很多鄰域信息都將忽略，但與之相反，并不是網格越大越好，網格的大小過大會將很多不正確的對應關系也包含進來。因此網格大小的選取即為重要，既不能忽略太多的鄰域信息，也不能將太多的錯誤信息包含進去，為了解決鄰域信息包含太少的問題，采用運動內核來將更多的鄰域信息包含進去，同時為了提高算法的準確性，也需要將網格設置的比較小，如圖4所示。

圖4 運動核

根據網格設置較小，采用運動內核的思路，在原有網格鄰域的8個網格的基礎上構成了一個更大的網格 (Ca1b1,…,Ca9b9)。 由此重新定義了鄰域

Ni={cj|cj∈CA,ci≠cj}

(17)

重新定義相鄰鄰域

Si={cj|cj∈CAB,ci≠cj}

(18)

其中，CAB=Ca1b1∪Ca2b2∪Ca3b3…∪Ca9b9。

針對旋轉問題，利用旋轉運動核模擬不同方向的旋轉，如圖5所示，固定CA， 對CB按照順時針旋轉，這樣可以得到8個運動核，然后在所有運動核上使用GMS算法，然后選擇最好的結果(選擇匹配數量最多的那個)。

圖5 旋轉運動核

本文融合GMS的改進ORB算法的總體流程如圖6所示。

圖6 改進ORB算法總流程

3 實驗驗證分析

3.1 實驗平臺

本次實驗所使用的CPU為Intel i5-9300H，頻率為2.40 HZ，顯卡為GTX1650，所使用的操作系統為Ubuntu16.04，進行測試的圖片選自TUM數據集，選取的3張圖片其桌面物體的紋理比較豐富，但桌面和地板紋理單一，很適合本次實驗。實驗圖片如圖7所示。

圖7 實驗測試圖片

3.2 改進ORB算法圖像提取實驗

特征點提取算法種類很多，例如ORB算法、BRISK算法以及AZAKE算法等，但這些算法都沒法在紋理比較弱的地方提取出足夠的特征點，甚至可能一個特征點都提取不出來。上述算法提取出的特征點大多數都集中在紋理比較豐富的地方，使得圖片很大部分區域的信息都沒有利用上。因此針對上面的問題，將四叉樹策略應用到特征點提取中，對大量粗提取的特征點進行精提取，充分利用圖片上的信息，最終提取出分布比較均勻的特征點。

利用改進的特征點提取匹配方法對實驗圖片1進行特征點提取，分別對比了ORB算法、BRISK算法和AZAKE算法與改進后的ORB特征點提取匹配方法的效果。

如圖8的實驗結果所示，ORB算法、BRISK算法和AKAZE算法提取的特征點分布比較密集，基本集中在紋理比較豐富的桌子上的物體，但對于紋理比較弱的地板和桌面，基本提取不出特征點，很不利于對整張圖片信息的利用。而對于改進的ORB算法提取的特征點分布比較均勻，可以從圖8(d)中看出，地面以及桌面等紋理比較弱的地方，也可以提取出比較多的特征點，最大程度地保留了圖片上的有用信息。

圖8 4組實驗結果

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

傳統的暴力匹配的方式在匹配完后存在一些誤匹配的情況，匹配的準確性將影響到很多算法的準確性，因此在暴力匹配結束后，利用GMS算法基于網格模型對匹配后的特征點進行誤匹配剔除，最終可以獲得非常準確的匹配結果。

利用3組圖片分別對原始ORB算法、BRISK算法、AKAZE算法以及改進的ORB算法進行特征點匹配實驗。

如表1所示，對實驗圖片1進行特征點提取與匹配，改進的ORB算法，如圖9所示，匹配率達到28.2%，比ORB算法高了4.5%，其效果與AKAZE算法效果相當，但特征點提取用時上卻比ORB算法用時高了3倍時間，匹配用時也比其它算法用時高一些，但總體上并不影響該算法的實時性。

表1 4種算法特征點提取匹配效果對比(采用實驗圖片1)

圖9 改進ORB算法匹配效果

表2中顯示的是原始ORB算法、BRISK算法、AKA

表2 4種算法在不同圖片上的匹配率/%

ZE算法以及改進ORB算法在不同圖片上的匹配率。對于實驗圖片1，改進后的ORB算法匹配率為28.2%；對于實驗圖片2，算法的匹配率為24.7%；對于實驗圖片3，算法的匹配率達到23.1%；可以看出，改進的ORB算法匹配率與其它算法相比，顯得更加優秀，可以獲得更高的匹配率。

表3顯示的是原始ORB算法、BRISK算法、AKAZE算法以及改進的ORB算法在不同圖片上的匹配用時。從中可以看出，由于引入GMS算法，整體的匹配用時變長了一些，但在某些圖片上與其它算法的用時相差不大，甚至比一些算法的匹配用時短，對于基本的實時性，改進后的ORB算法可以滿足。

表3 4種算法在不同圖片上的匹配用時/s

4 結束語

針對傳統的ORB特征點提取算法提取的特征點位置分布不均勻的問題以及存在誤匹配的問題，提出了一種改進的ORB算法，對圖像分區域提取特征點并與GMS匹配算法相結合，首先對圖像整體提取特征點，然后利用四叉樹原理對提取出的特征點分區域進行挑選，最終得到分布相對均勻的特征點，其次通過GMS算法將特征點的運動平滑約束轉變為剔除誤匹配的統計量，對提取出的特征點進行匹配和誤匹配剔除。

實驗結果表明，改進后的ORB算法在測試圖片1上的匹配率達到了28.2%，比原始ORB算法提高了4.5%，達到了更高的匹配率，且所匹配出來的特征點與其它算法相比更加均勻，能夠有效地利用到整個圖片的信息。同時該算法用時雖然有些許增加，但并不影響其實時性。