基于改進FREAK的圖像匹配算法

黃 坤,錢軍浩,王江文

(1.江南大學 物聯網工程學院,江蘇 無錫 214122; 2.西南交通大學 牽引動力國家重點實驗室,成都 610031)

0 概述

圖像匹配技術在計算機視覺領域得到廣泛的應用。圖像匹配可分為特征點檢測、描述符生成和根據描述符進行匹配3個步驟[1-2]。提高圖像匹配算法性能的關鍵在于生成區分度更高、運算量更小的描述符。因為二進制描述符表達緊湊且可利用位運算加速匹配,所以其所需的內存和運算量相比非二進制描述符大幅減小。近年來,研究人員提出了較多的二進制描述符算法。文獻[3]提出一種ORB算法,該算法根據機器學習選擇的點對生成二進制描述符,且引入方向信息使描述符具有旋轉不變性。文獻[4]提出一種BRISK(Binary Robust Invariant Scalable Keypoints)算法,該算法使用人為設計的采樣模式,點對只在采樣點里選取,大幅降低了訓練點對時的復雜度。文獻[5]基于BRISK算法固定采樣模式的設計思想提出了一種FREAK算法,該算法借鑒視網膜視覺感知細胞的分布設計采樣模式。借助設計合理的采樣模式,FREAK算法在很多場合獲得了優于其他二進制描述符的性能[6-8]。文獻[9]提出一種CS-FREAK算法,該算法將FREAK算法的視網膜模型由8層簡化為5層,然后增加中心對稱采樣點的領域強度信息。CS-FREAK算法的魯棒性在FREAK算法的基礎上有小幅改善,但是其描述符的計算和匹配過程更加復雜,實時性較低。文獻[10]提出一種局部二值模式(Local Binary Patterns,LBP)圖像特征點匹配算法,該算法不僅計算點對之間的差分大小關系,還計算點對與特征點之間的差分幅值關系來生成描述符。因為文獻[10]算法同時利用了差分大小和差分幅值這2種信息,所以該算法具有很好的噪聲抑制性能,但是其描述符長度較長且不具有旋轉不變性。

為進一步提升圖像匹配算法的實時性和魯棒性,本文提出一種結合LBP和FREAK的聯合特征匹配算法。根據文獻[9]算法的思路簡化FREAK視網膜模型,對簡化后的模型通過機器學習算法選擇高區分度、高非相關性的點對,在盡可能保證區分度的前提下減少點對數量以提高算法的實時性。在此基礎上,設計一種具有旋轉不變性的LBP對每個感受野進行編碼,以提高描述符的區分度[11]。

1 FREAK 描述符

1.1 視網膜采樣模型

FREAK 算法采用視網膜模型[5],該模型根據采樣點距特征點的距離決定采樣點的密度和高斯平滑內核。如圖1所示,處于中心的是特征點,其周圍分布著采樣點。每個圓的半徑大小表示對應采樣點高斯內核標準差的大小。為了減小噪音對描述符的影響,每個采樣點的像素值由對應的高斯內核對其所在感受野進行平滑處理得到。

圖1 FREAK算法采樣模型Fig.1 Sampling model of FREAK algorithm

從圖1可以看出,采樣點使用不同的高斯內核造成感受野之間存在重疊,這些重疊使得FREAK描述符能捕獲更多的信息,從而獲得更好的性能。假設在感受野A、B和C中測得的像素強度大小關系如式(1)所示:

IA>IB,IB>IC,IA>IC

(1)

如果感受野沒有重疊,那么式(1)中的IA>IC沒有為描述符添加任何有用信息。然而,如果感受野存在重疊,則部分新的有用信息能被添加到描述符中。正是因為感受野間存在重疊,FREAK算法用較少的采樣點就可對特征點進行充分描述。

1.2 由粗到精的描述符

FREAK描述符通過二值化采樣點對之間的像素值差分形成,如式(2)所示:

(2)

其中,F是生成的二進制描述符,Pa表示第a個采樣點對,N表示描述符的維度,T(Pa)由式(3)求得:

(3)

為選擇更具代表性的點對,FREAK算法利用機器學習算法選擇512個高區分度的點對,將其按區分度從高到低分為4組,每組128個,如圖2所示。

圖2 由粗到精的描述符示意圖Fig.2 Schematic diagram of descriptors from coarse to fine

從圖2可以看出,第1組點對主要連接外圍感受野,最后一組點對主要連接中心區域的感受野,這符合眼球觀測物體的行為,人類觀測物體時首先用眼球外圍的視覺感知細胞去大致確定目標的位置,然后用視網膜中心區域的視覺感知細胞進行確認。FREAK算法根據這種由粗到精的描述符結構提出一種掃視搜索匹配策略。匹配時首先比較前128個點對,即代表粗信息的部分,如果距離小于設定的閾值,則繼續比較后續點對,如果距離大于閾值,則停止比較。這種匹配策略加速了匹配過程。

1.3 描述符方向

FREAK算法描述符的方向通過計算局部梯度平均值獲得,如式(4)所示:

(4)

圖3 FREAK算法方向點對選取示意圖Fig.3 Schematic diagram of the selection of direction point pairs of FREAK algorithm

2 改進FREAK的描述符

2.1 簡化的采樣模型

FREAK算法區分度最高的第1組點對就可正確區分90%以上的特征[5],這在一方面說明FREAK算法選取的前128個點對具有很高的區分度,另一方面也說明后3組點對的作用相對較弱。本文算法的思路是拋棄區分度不是很高的點對以提高算法的實時性,另外設計一種具有旋轉不變性的LBP算法替代這些點對來生成區分度更高的描述符。為了簡化計算,根據文獻[9]算法的思路將FREAK算法視網膜模型由8 層43個采樣點簡化為5層25個采樣點,簡化后的采樣模型如圖4所示。

圖4 簡化采樣模型示意圖Fig.4 Schematic diagram of simplified sampling model

本文利用PascalVOC 2012[12]數據庫對簡化后的采樣模型挑選點對,此數據庫包含11 530個圖像,從中提取大約200萬個特征點,這個規模是FREAK算法訓練點對時特征點數量的50倍,大量的訓練樣本保證了訓練結果的魯棒性。本文參考FREAK[5]和文獻[13]設計一種貪婪搜索算法,該算法并非尋找高區分度和高非相關性點對集合的最優解,而是盡可能快地選擇一個可行解以提高點對選取速度,具體算法步驟如下:

步驟2計算D每列的均值,再算均值與0.5差的絕對值。將D矩陣各列按此絕對值從小到大排序,根據二項分布均值與方差的關系得到點對按區分度從高到低的排列。建立隊列T,將這些點對按序放入隊列T。

貪婪搜索算法流程如圖5所示。

圖5 貪婪搜索算法流程Fig.5 Procedure of greedy search algorithm

通常情形下,在全部300個點對中,算法選出的128個點對能正確區分95%以上的特征點,選出的64個點對能正確區分80%以上的特征點。根據現代計算機架構,位操作一般一次處理128位[5]。本文提出的旋轉不變LBP將對簡化采樣模型生成196位的描述符。為權衡正確率和運行開銷,本文從300個點對中用提出的訓練算法選取高區分度和高非相關性的64個點對,如圖6所示。

圖6 簡化點對示意圖Fig.6 Schematic diagram of simplified point pairs

根據選定的64個點對可生成64維的點對描述符,雖然此描述符盡可能包含更多的信息,但是對比FREAK描述符,維度從512維降到64維,這必然降低描述符的區分度。因此,本文算法用具有旋轉不變性的LBP 對感受野進行編碼,從而增加描述符的區分度。

2.2 編碼感受野信息

根據式(3),FREAK描述符中的每一位都由一對采樣點的像素值差分大小關系決定。FREAK算法的這種編碼方式僅用一個像素值描述一個感受野,沒有充分利用采樣模式本身的信息對感受野進行充分描述,這在一定程度上限制了FREAK描述符的區分度。

根據紋理特征可以通過中心像素與鄰域像素的差分關系進行表示這一原理,文獻[14-15]提出了LBP算法。該算法將中心像素看成一個特征點,LBP作為該特征點的局部描述符。選取鄰域像素時可以設置不同的數量P和不同的半徑R,如圖7所示。

圖7 LBP模型圖解示意圖Fig.7 Schematic diagram of LBP model

LBP的計算如式(5)所示:

(5)

其中,P表示選取鄰域像素的數量,R表示選取鄰域像素的半徑,gp-gc表示第p個鄰域像素與中心像素的差分,S(x)由式(6)求得:

(6)

文獻[10]根據這種LBP算法計算差分幅值信息從而增加描述符的區分度。然而原有LBP[14-15]不具有旋轉不變性,這是因為當發生旋轉時鄰域像素取值的先后順序將發生變化從而破壞旋轉不變性。雖然有文獻提出了改善LBP旋轉不變性的方法[16-18],但這些方法沒有利用FREAK采樣模式的特有信息而是引入額外的計算,若在FREAK算法中使用這些方法將降低算法的實時性。

FREAK采樣模式本身帶有方向和尺度信息,本文利用這些信息為每個采樣點生成具有旋轉不變性的LBP。首先,每個感受野的半徑設為已知,則每個采樣點LBP的半徑可由式(7)求得:

R=k·radius,0

(7)

其中,k是系數,radius是對應感受野的半徑。此時,LBP的半徑與采樣點對應的感受野大小成比例,避免在對大小不同的感受野生成LBP時使用相同的半徑。當確定了某采樣點的LBP半徑R后,以采樣點為圓心、R為半徑畫圓,連接該采樣點與特征點畫線段。將線段與圓的交點設為該采樣點的第0個鄰域像素,其他鄰域像素按逆時針旋轉相應角度得到,如圖8所示。

圖8 旋轉不變LBP模型圖解示意圖Fig.8 Schematic diagram of rotation-invariant LBP model

從圖8可以看出,利用特征點與采樣點的相對位置關系選取LBP鄰域點,當旋轉發生時LBP鄰域點的順序也同時發生旋轉,因此生成的LBP具有良好的旋轉不變性。

各采樣點LBP鄰域點的位置可硬編碼到采樣模式中而無需實時計算。因為算法存儲采樣模式和計算積分圖所需的內存大小是固定的,所以計算描述符時無需動態分配內存。雖然本文算法與FREAK算法記錄各自采樣模式所需的具體內存大小不同,但2種算法的空間復雜度一致。LBP鄰域點取值時的高斯平滑可由積分圖近似實現,而積分圖在計算采樣點取值時就已經建立,所以生成LBP時僅多一個常量級的運算。因此,本文算法的時間復雜度也與FREAK算法一致。

2.3 描述符生成

本文描述符的生成過程可分為以下4個步驟:

步驟1對每個感受野生成旋轉不變的LBP描述符。

步驟2按感受野從外到里的順序連接所有LBP描述符,生成本文算法的LBP描述符部分。

步驟3根據2.1節選取的點對計算本文算法的點對描述符部分。

步驟4將連接的LBP描述符放在點對描述符之后,生成本文的描述符。由圖6可知,對簡化后采樣模型選取的64個采樣點對主要連接外圍感受野,而描述符的LBP部分也按感受野從外到里的順序連接。因此,本文提出的描述符也可使用掃視搜索策略進行匹配。

計算本文描述符方向的方法與FREAK一致[5],但選取的方向點對有所不同。在簡化采樣模型后,本文算法選取每層6個采樣點兩兩連接的點對來計算方向,共計60個方向點對,如圖9所示。

圖9 簡化模型的方向點對Fig.9 Direction point pair of simplified model

3 實驗結果與分析

本文實驗所使用的軟硬件平臺為:Visual Studio 2017,OpenCV 3.4,Intel Core i5-7200U頻率2.7 GHz處理器,DDR4 2 400頻率8 GB內存。

為驗證本文算法的實時性和魯棒性,實驗采用Mikolajczyk數據集[19]和day-night數據集[20]進行測試,這2個數據集中都是單通道圖片。Mikolajczyk數據集一共有8個圖像序列,分別為bark、boats、bikes、graf、tree、ubc、wall和leuven,每個圖像序列為6張圖片。其中,bark和boats涉及旋轉和尺度變換,graf和wall涉及視角變化,leuven涉及亮度變化,bikes和tree涉及模糊變化,ubc涉及圖片壓縮變化。day-night數據集共有17個圖像序列,每個序列都是同一個攝像頭在各種天氣環境下拍攝的相同場景。

本文使用召回率及召回率-查錯率曲線2種指標來衡量描述符算法,根據召回率分析算法查找出正確匹配的能力,根據召回率-查錯率曲線分析算法的魯棒性。召回率(recall)和查錯率(1-precision)的計算可由式(8)求得:

(8)

其中,correspondences是指2幅圖片間所有的正確匹配數。文獻[21]提出2個圖片區域之間的重疊錯誤若小于設定的閾值,則認為是一對正確的匹配。correct matches和false matches分別指描述符算法找到的正確匹配數和錯誤匹配數。

為了公平起見,本文實驗所有描述符都采用STAR特征點,其是CenSurE特征點在OpenCV 3.4中的變種,也是文獻[10]算法使用的特征點。Mikolajczyk數據集和day-night數據集都提供精確的單應矩陣,correspondences可根據此單應矩陣直接使用OpenCV 3.4的標準函數獲得,選取60%作為重疊錯誤的閾值。在生成LBP描述符時,根據經驗設置鄰域點數量P為8,半徑R為對應感受野半徑的一半,即式(7)中參數k取值為0.5。對Mikolajczyk數據集進行測試,部分測試結果如表1～表3所示,其中,n|m表示將圖像序列中的第n張圖片與第m張圖片進行對比。

表1 boats圖像序列召回率Table 1 Recall of boats image sequence %

表2 wall圖像序列召回率Table 2 Recall of wall image sequence %

表3 leuven 圖像序列召回率

boats序列對應旋轉和尺度變化。由表1可知,在旋轉角度較小時(1|2圖片對),文獻[10]算法的召回率最高,本文算法次之。隨著旋轉角度的增加,文獻[10]算法的召回率下降明顯,獲得了最低的召回率,而此時本文算法仍優于其他算法,這是因為文獻[10]算法使用的LBP不具備旋轉不變性,而本文算法使用具有旋轉不變性的LBP。對于尺度變化(1|5圖片對),本文算法與文獻[10]算法幾乎持平且相對其他算法有較大的優勢。

wall序列對應逐漸加大的視角變化。由表2可知,視角變化較小時文獻[10]算法略優于本文算法,視角變化較大時本文算法略優于文獻[10]算法。而FREAK算法的視角不變性最弱,因此,本文算法對FREAK算法的視角不變性有較大提升。

leuven序列對應逐漸加大的光照亮度變化。由表3可知,文獻[10]算法具有較強的光照亮度不變性,本文算法次之,且本文算法對FREAK和CS-FREAK的光照不變性提升較大。

由圖10可知,對于旋轉及尺度變化,本文算法具有最強的魯棒性;對于視角變化,本文算法與文獻[10]算法性能相近,但在要求低查錯率時(小于30%),本文算法優于文獻[10]算法;對于簡單的光照明暗變化,文獻[10]算法具有最強的魯棒性,而本文算法僅次于文獻[10]算法,且對FREAK算法有較大提升。

圖10 描述符性能評估Fig.10 Evaluation of descriptor performance

現實世界中不僅存在像leuven序列那樣簡單的光照明暗變化,更多的是復雜的非線性光照變化,比如day-night數據集提供的圖像序列。選取day-night數據集圖片序列進行實驗,本文算法(下)和原始FREAK算法(上)的正確匹配結果如圖11所示。在圖11選取的序列中,各種算法的具體匹配結果如表4所示。

圖11 本文算法與原始FREAK算法正確匹配結果對比Fig.11 Comparison of correct matching results between this algorithm and original FREAK algorithm

表4 day-night圖片序列召回率對比Table 4 Comparison of recall of day-night image sequence

由表4可知,通常情況下,在復雜的光照環境中,本文算法具有最高的召回率,且對比原始FREAK算法,本文算法有較大提升。

除了魯棒性外,本文還對描述符的實時性進行測試。對各種算法計算1 000個描述符的時間進行統計,采用20次實驗的平均結果,如表5所示。

表5 描述符計算時間統計Table 5 Statistics of descriptor calculation time

從表5可以看出,本文算法的實時性最好,這是因為本文算法和FREAK算法在實現時都使用積分圖加快計算,且本文算法維度只有FREAK算法的一半。文獻[10]算法因其描述符長達1 024位,且生成過程中不僅要計算點對的差分大小,還要計算差分幅值,大幅增加了計算時間。CS-FREAK生成的描述符不是二值描述符,這不僅增加了描述符的生成時間,而且在匹配時也無法使用位運算來加快匹配。

4 結束語

FREAK算法根據人類視網膜設計采樣模型,該采樣模型優于BRISK算法中人為設計的采樣模型。因此,FREAK算法相比BRISK算法具有更好的旋轉和尺度不變性。但是,FREAK算法對每個感受野僅用一個像素值進行描述,沒有充分利用采樣模式信息,導致其視角不變性和光照不變性都比較弱。本文以FREAK算法為基礎,根據CS-FREAK算法的思想簡化FREAK采樣模型,利用機器學習算法在盡可能保證區分度的前提下減少點對數量,從而提高算法的實時性。根據采樣模式本身的信息設計一種具有旋轉不變性的LBP算法來提高描述符的區分度。實驗結果表明,本文算法具有較強的魯棒性和實時性,且對于光照環境復雜和實時性要求較高的場景具有一定的實際應用價值。本文算法在計算描述符的LBP部分時,需要選取參數k和R,如何針對不同的應用場景來選取最適合的參數將是下一步的研究方向。