基于DoG檢測圖像特征點的快速二進制描述子

劉 凱，汪 侃，楊曉梅，鄭秀娟

(四川大學 電氣工程學院，四川 成都 610065)

1 引 言

圖像的局部特征獨特性好，對光照、旋轉、視角變化等圖像轉換都具有不變性，因此被廣泛應用于圖像拼接、目標識別、目標跟蹤和圖像檢索等領域[1-6]。尤其在大場景的三維重建[7-8]中，優(yōu)秀的特征描述能幫助我們以極高的效率重建出精細的三維模型。局部特征的提取分為兩個步驟：關鍵點檢測[9]和描述子生成[10-11]，本文主要討論描述子的設計。

關鍵點描述子按照描述子的表現(xiàn)方式分為浮點數(shù)描述子和二進制描述子。浮點數(shù)描述子中最典型的方法是尺度不變特征變換(Scale Invariant Feature Transform，SIFT)[12]。在對局部描述子的性能評估后，Mikolajczyk和Schmid[10]提出SIFT描述子具有最好的魯棒性和獨特性。但是SIFT描述子生成復雜，匹配效率低下，因此許多學者對SIFT算法進行了改進和擴展。Bay等[13]提出利用關鍵點鄰域的小波響應來生成64維描述子；Ke等[14]和顏雪軍等[15]提出用主成分分析的方法對SIFT梯度向量塊進行降維；Tola等[16]和曾巒等[17]通過提出新的分塊策略構建特征描述子，降低了描述子運算復雜度；耿慶田等[18]提出在邊緣檢測出的感興趣區(qū)域上構建全局SIFT組合特征向量，通過減少冗余極值點來提高SIFT算法的效率；唐永鶴等[19]在Schmid等[20]研究的基礎上提出了基于灰度差分不變量區(qū)域統(tǒng)計直方圖的算法來提高特征描述子的穩(wěn)定性。

浮點數(shù)描述子雖然有良好的性能，但是采用統(tǒng)計直方圖的方法計算量大，描述子占用存儲容量多，匹配時間復雜度高。而二進制描述子采用比特位的存儲方式，占用容量小，同時，其通過計算漢明距離來匹配。漢明距離通過異或運算實現(xiàn)，計算效率極高，經(jīng)典的二進制描述子主要包括：二值魯棒獨立單元特征(Binary Robust Independent Elementary Features，BRIEF)[21]、ORB[22]、二值魯棒不變尺度關鍵點(Binary Robust Invariant Scalable Keypoints，BRISK)[23]、快速描述神經(jīng)元類關鍵點(Fast Retina Keypoint，F(xiàn)REAK)[24]。上述二進制描述子均是基于灰度比較的描述子，隨著近年來機器學習方法的高速發(fā)展，越來越多的學者通過機器學習的方法來為特征點提取二進制描述子。在有監(jiān)督學習中, Trzcinski等[25]通過訓練將幾個弱分類器組成強分類器，進而將圖像特征投影為二值結果構成描述子；Balntas等[26]基于線性判別分析離線訓練不相關的二進制測試點對，在線訓練特征子集塊，提高了機器學習中二進制描述子提取的速度。在無監(jiān)督學習中，Lin等[27]提出DeepBit方法來學習生成緊湊的二進制描述子；Zieba等[28]提出新的正則化方法，并應用到對抗生成網(wǎng)絡上生成在圖像匹配和圖像檢索表現(xiàn)優(yōu)異的二進制描述子；Duan等[29]應用KAEs網(wǎng)絡在深度學習框架下共同學習參數(shù)和二值化功能。然而，這些通過機器學習提取二進制描述符的效率要遠低于傳統(tǒng)描述符的提取效率。

在上述描述子的基礎上，本文設計了一種時間復雜度低、魯棒性更好的二進制描述子。首先，結合傳統(tǒng)二進制描述子采樣模式的優(yōu)點，本文提出了新的采樣模式，新采樣模式的同心圓半徑和采樣點的濾波半徑均與尺度關聯(lián)，且采樣點采用均值濾波；然后，根據(jù)特征點主方向，我們將采樣模式中各采樣點旋轉到特定位置；接著，我們選擇最優(yōu)的最小相關點對比較模式，該模式通過機器學習的方法從采樣模式中選取獨特性最好、相關性最低的128對點對；最后，在點對灰度值比較的基礎上，我們添加梯度絕對值和比較來構建二進制描述子。

2 生成二進制描述子

2.1 設計采樣模式

BRIEF特征點的采樣區(qū)域是以特征點為中心的一個的鄰域塊，論文作者在鄰域塊中隨機選取點對進行二進制編碼；BRISK以特征點為中心，構建不同的同心圓，在每個圓上獲取一定數(shù)目的等間隔采樣點；FREAK算法的采樣模式接近于人眼視網(wǎng)膜接收圖像信息的采樣模型，在離中心點近的采樣點密度高，遠離中心點的采樣點密度低；惠國保等[30]提出采樣點密度和平滑范圍重疊度均對采樣模式有影響，在中心集中度為78%，重疊度為22%時能使描述子的獨特性最大化。本文分析了BRIEF，BRISK和FREAK的采樣模式特點，在其基礎上提出了新的采樣模式，如圖1所示。

圖1 采樣模式示意圖Fig.1 Sampling pattern

圖1是特征點組內(nèi)尺度σ=1.6時的采樣模式示意圖，其中每個圓形代表采樣點的平滑范圍。采樣模式共計5層，即有5個以特征點為中心的同心圓，同心圓的半徑分別為3σ，4.5σ，5σ，7σ，9σ。其中中心點的平滑半徑為2σ。采樣模式內(nèi)3層的每個同心圓上均勻分布著8個采樣點，每個采樣點的平滑半徑為1.3σ。各采樣點在坐標系下的位置如公式(1)所示：

(1)

其中：同心圓的半徑r=3σ，4.5σ，5σ，采樣點的序號k=0，1，…，7，采樣模式的層數(shù)t=1，2，3，p(t)函數(shù)在t為奇時取0，t為偶時取1，θ表示特征點主方向。

采樣模式外2層的每個同心圓上均勻分布著16個采樣點，每個采樣點的平滑半徑為1.6σ。各采樣點在圖像坐標系下的位置如公式(2)所示：

(2)

其中：同心圓的半徑r=7σ，9σ，采樣點的序號k=0，1，…，15，采樣模式的層數(shù)t=4，5，q(t)函數(shù)在t為奇時取1，t為偶時取0，θ表示特征點主方向。

本文提出的采樣模式與BRIEF，BRISK和FREAK的有很大不同。BRIEF在方形區(qū)域內(nèi)檢測隨機點對的響應值；BRISK的采樣模式有4層，每層上均勻分布著10，14，15和20個采樣點，采樣點平滑范圍彼此獨立，沒有重疊；FREAK采樣模式有7層，每層上均勻分布著6個采樣點，采樣點平滑范圍高度重疊，產(chǎn)生大量冗余信息。本文提出的采樣模式是在BRISK采樣模式的基礎上推廣而來。首先，采樣模式中同心圓的半徑和采樣點平滑范圍均和特征點的尺度關聯(lián)以確保采樣的尺度不變性，其次，相較于BRISK采樣模式，本文提出的采樣模式更密集，各個采樣點之間不存在空隙，更能充分利用特征點周圍的鄰域，而且本文對采樣點采用均值濾波替代BRISK中采用的高斯濾波，在減小計算量的同時，使相鄰的采樣點存在部分重疊，有利于提高描述子的獨特性，最后，采樣模式根據(jù)特征點尺度最小值選取平滑范圍，確保所有采樣點的平滑范圍在3×3以上，避免了BRISK采樣模式內(nèi)圈采樣點平滑范圍太小的缺陷。因此，本文提出的采樣模式相較于BRISK采樣模式有更大優(yōu)勢。

2.2 特征方向

為保證描述子的旋轉不變性，需要將特征點周圍的區(qū)域旋轉到主方向上去，對采樣模式中的每個采樣點編號如圖1所示。解決旋轉不變性主要包括以下兩個步驟：

(1)采用SIFT的主方向估計方法得到特征點的主方向θ；

(2)將采樣點1和特征點的連線方向與主方向θ對齊。

將特征點周圍整個區(qū)域旋轉到主方向的代價比較高，為減少運算量，本文僅將57個采樣點旋轉到相應位置。首先，在特征點組內(nèi)尺度為1.6，主方向為0時，建立查找表存儲57個采樣點的橫、縱坐標，然后對組內(nèi)尺度σ、主方向θ、編號n的采樣點，按如下公式計算其橫坐標x與縱坐標y：

(3)

其中X，Y是存儲表中編號為n的采樣點的橫、縱坐標。

2.3 特征描述

參考局部二值模式[31]與ORB，本文提出以下三種采樣點對模式方案：

(1)中心點比較模式(Center Comparison Pattern，CCP)，即同心圓上任意一點與中心點組成點對；

(2)中心對稱比較模式(Centrosymmetric Comparison Pattern，CSCP)，即同心圓上一點與其關于中心點的對稱點組成點對；

(3)最小相關點對模式(Minimum Correlation Pattern，MCP)，其算法步驟如下：

a.從ImageNet Large Scale Visual Recognition Challenge 2012測試集數(shù)據(jù)集中選取1 000張圖片共提取K=276 696個特征點。對于每個特征點，從其周圍鄰域的57個采樣點中選取兩個采樣點(xp，xq)組成點對進行灰度值大小比較。點對的選取如公式(4)所示：

A={(xp,xq)|1≤p<57∧p

(4)

對于每個特征點有M=1 596個二進制測試結果，將K個特征點的測試結果排列成K×M的矩陣；

b.令S為測試結果矩陣中列的集合，計算S中每列均值，從中選取均值為0.5的列加入集R，對于S中剩下的列，從中挑選出均值與0.5的絕對距離在0.1以內(nèi)的列，計算其與集R中每列的相關性，若均小于一定的閾值則添加到集R中，直到R中有128列；

c.確定集R中每列所對應的點對。經(jīng)選擇后的最小相關點對如圖2所示，其中每條線段連接的兩個采樣點為一對點對。

圖2 采樣點對示意圖Fig.2 Sampling point pairs

從測試集數(shù)據(jù)集中另選130幅圖片共提取32 264個特征點對三種采樣點對模式的優(yōu)劣進行比較，結果如圖3所示。

圖3 描述子均值、特征值測試結果圖Fig.3 Results of descriptor mean value and eigenvalues

從圖3(a)中可以看出，MCP生成的描述子每個比特位均值靠近0.5，表明每個比特位方差靠近最大樣本方差0.25，這使得描述子不同比特位之間有著較大的區(qū)分度，即描述子獨特性較好。而CCP描述子比特位均值分布較為寬泛，CSCP描述子比特位均值分布離0.5較遠，因此這兩種模式生成的描述子比特位方差較小，描述子之間區(qū)分性較差，容易造成誤匹、錯匹。圖3(b)是主成分分析后，三種點對模式描述子最大的20個特征值分布情況。MCP和CCP描述子的初始特征值較大，表明兩種描述子各比特位之間的相關性較弱，而CSCP描述子的初始特征值較小，描述子各比特位之間的相關性強，即各比特位之間的采樣結果相互影響。綜上比較可知，MCP描述子每個比特位均值和方差為最大，不同比特位之間的相關性弱，描述子獨特性最好，區(qū)分度最高，故以下實驗中的描述子均采用MCP描述子。

2.4 灰度差分不變量比較

傳統(tǒng)的二進制描述子采樣點之間僅僅比較灰度值信息，比較結果受噪聲的影響較大。受文獻[18,19]的啟發(fā)，本文在采樣點灰度值比較的基礎上，增添新的灰度差分不變量比較，如公式(5)所示：

(5)

其中：V[0]表示該采樣點的灰度值，V[1]表示梯度絕對值和，V[2]表示二次梯度和。同時，為減少噪聲的影響，用采樣點平滑區(qū)域所有像素點V[i]和的均值代表采樣點的V[i]值：

(6)

其中：Rn表示編號n的采樣點的平滑區(qū)域，N表示平滑區(qū)域像素點的個數(shù)。二進制編碼規(guī)則如下公式所示：

(7)

其中s(x)的表達式如下：

(8)

(9)

(10)

3 測量實驗與結果

本文采用牛津標準圖像集和Fountain，Herzjesu數(shù)據(jù)集評估特征描述子。牛津標準圖像集下共有8個子集，涵蓋有不同程度的幾何和光度轉換，包括：圖像旋轉、尺度變化、光照亮度變化、圖像模糊、視角變化和JPEG壓縮。Fountain和Herzjesu數(shù)據(jù)集主要測試小角度視角變換和非平面幾何的影響。本文采用的評估標準是Mikolajczyk和Schmid提出的查全率(Recall)：

(11)

和錯誤率(1-precision)：

(12)

其中：#correctmatches是在匹配成功的點對#matches中通過隨機抽樣一致性確定的正確匹配的點對數(shù)，#pointcorrespondence是所有能匹配上的點對數(shù)，在實驗中取SIFT描述子最近鄰匹配(即距離閾值α=1.0)后通過隨機抽樣一致性確定的點對數(shù)。本文在Intel(R) Core(TM) i3-3240 CPU @3.40 GHz雙核四線程CPU的平臺上，采用C++編程。

3.1 描述子維數(shù)評估

圖4 不同維數(shù)MCP描述子匹配結果Fig.4 Matching results of MCP descriptors with different dimensions

二進制描述子維度對描述子性能有很大影響，描述子維度太低不能充分挖掘采樣點鄰域信息，而描述子維度太高會增大錯匹率。本文對提出的三種MCP描述子進行圖像匹配性能評估，測試圖像選擇為牛津標準圖像集中Graffiti圖像集的第一幅和第三幅圖片，測試結果如圖4所示?？梢钥闯?，為MCP描述子添加梯度信息后，能顯著提高描述子的性能，同時，MCP-256描述子和MCP-384描述子的性能相當，即添加二次梯度信息并不能有效地提升MCP描述子性能。

三種維度描述子的實時性測試結果如表1所示，測試的數(shù)據(jù)主要包括：兩幅圖片所有描述子的生成時間(Time of Descriptors，TD)、平均每個描述子的生成時間(Mean Time of Descriptors，MTD)、兩幅圖片描述子的總匹配時間(Time of Matching，TM)、平均每個匹配的花費時間(Mean Time of Matching，MTM)。實驗中兩幅圖片生成的描述子個數(shù)分別為2 681、3 521，匹配的總數(shù)為距離閾值α=0.95時兩幅圖片的匹配個數(shù)。

表1 不同維數(shù)MCP描述子實時性測試結果

Tab.1 Real-time performance of MCP descriptors with different dimensions

MCP-128MCP-256MCP-384TD/ms1157201 327MTD/μs18116214TM/ms189305429MTM/μs132226334

MCP-256描述子需要計算梯度絕對值信息，從表1可以看出，其MTD比MCP-128描述子多出一個數(shù)量級，同時，由于MCP-256描述子優(yōu)秀的性能增加了匹配數(shù)，MTM并沒有達到MCP-128描述子的兩倍。MCP-384描述子的MTD和MTM均大于MCP-256描述子，但描述子性能卻沒有提高。因此，在以下描述子的實時性和魯棒性評估中，均使用MCP-256描述子。

3.2 描述子實時性評估

實時性是檢測二進制描述子性能的一個重要方面。實驗中描述子的測試圖像為Graffiti圖像集中的第一幅和第三幅圖片，實驗給出五種描述子算法(SIFT，ORB，BRISK，F(xiàn)REAK和MCP)性能的測試結果，其中SIFT，ORB，BRISK和FREAK的關鍵點檢測、描述子生成均使用OpenCV3.1.0中的封裝函數(shù)，所有描述子的匹配采用暴力匹配法。實驗中取20次測試結果的平均值作為測量的實際值,圖像匹配的距離閾值α=0.95，測試結果如表2所示。

從表2中可以看出，二進制描述子的MTD和MTM均要小于浮點數(shù)描述子。同時，MCP描述子的MTD要大于BRISK和ORB的MTD，但小于FREAK的MTD，比SIFT的MTD小84%；MCP描述子的MTM僅略大于ORB的MTM，比SIFT的MTM小67%。

表2 不同描述子實時性測試結果

Tab.2 Real-time performance of different descriptors

SIFTORBBRISKFREAKMCPTD/ms1 96316484194311MTD/μs7327245144116TM/ms1 147220261166305MTM/μs677195315321226

3.3 描述子魯棒性測試

實驗中采用DoG檢測關鍵點，匹配測試圖像選用Bark圖片集(尺度+旋轉變化)、Bikes圖片集(模糊變化)、Leuven圖片集(光照變化)、Graffiti圖片集(大角度視角變化)、Fountain及Herzjesu圖片集(非平面幾何)中的第二張與第四張圖片，測試圖片如圖5所示，測試結果如圖6所示。在查全率-錯誤率曲線中，描述子匹配曲線越往上，描述子的魯棒性越好。實驗中選用的#pointcorrespondence是SIFT描述子最近鄰匹配后通過隨機抽樣一致性篩選的匹配數(shù)。

圖5 描述子魯棒性測試圖片F(xiàn)ig.5 Test images of descriptor robustness

參與比較的五種描述子中，SIFT是128維浮點數(shù)描述子，其他均為二進制描述子，ORB，BRISK，F(xiàn)REAK和MCP分別是256維、512維、512維和256維描述子。從圖6中可以看出，MCP描述子的性能好于其他二進制描述子，尤其體現(xiàn)在視角變化(Graffiti)和非平面幾何變換(Fountain，Herzjesu)上，這跟MCP描述子好的采樣模式、獨特的特征描述以及添加灰度差分不變量比較測試均有直接的聯(lián)系。但是，二進制描述子相對于SIFT描述子仍有不足。在采用DoG檢測關鍵點的前提下，二進制描述子在大多數(shù)圖像變換下達不到SIFT描述子的高召回率。

圖6 不同描述子魯棒性測試曲線圖Fig.6 Diagram of different descriptor robustness

用4種二進制描述子分別匹配Fountain圖像集的第2張和第4張圖片、Graffiti圖像集的第4張和第5張圖片，結果分別如圖7、圖8所示。從下面兩幅圖中可以看出，在非平面幾何變換(Fountain)和視角變化(Graffiti)下，MCP描述子的正確匹配數(shù)要遠高于其他二進制描述子。

對Bark，Bikes，Graffiti，Leuven，Ubc和Wall圖片集中相鄰圖片兩兩匹配，對描述子進行魯棒性測試。距離閾值α=0.95，P/R表示準確率/召回率，Ave表示均值。其中SIFT浮點數(shù)描述子作為基準參考不參與比較，黑色加粗部分表示該圖像集下二進制描述子的最優(yōu)值。比較結果如表3～表8所示。

從表3～表8可以看出，在六種圖像變換中，相較于其他二進制描述子，MCP描述子的準確率、召回率在四種變換下更高。尤其在視角變化(Graffiti，Wall)下，其準確率要比其他二進制描述子高3%～5%，召回率平均要高30%以上。

圖7 不同描述子的Fountain圖像對匹配結果Fig.7 Matching results of different descriptors on Fountain

圖8 不同描述子的Graffiti圖像對匹配結果Fig.8 Matching results of different descriptors on Graffiti

表3Bark圖像集描述子魯棒性測試結果

Tab.3 Robustness results of different descriptors on Bark

(%)

表4Bikes圖像集描述子魯棒性測試結果

Tab.4 Robustness results of different descriptors on Bikes

(%)

表5Graffiti圖像集描述子魯棒性測試結果

Tab.5 Robustness results of different descriptors on Graffiti

(%)

表6Leuven圖像集描述子魯棒性測試結果

Tab.6 Robustness results of different descriptors on Leuven

(%)

表7Ubc圖像集描述子魯棒性測試結果

Tab.7 Robustness results of different descriptors on Ubc

(%)

表8Wall圖像集描述子魯棒性測試結果

Tab.8 Robustness results of different descriptors on Wall

(%)

3.4 三維重建實驗

選擇Fountain圖像集、Herzjesu圖像集中的8張圖片，分別用MCP描述子、SIFT描述子重建三維稀疏點云，結果如圖9所示。

從圖9可以看出，MCP描述子重建的稀疏點云密度SIFT描述子的相近，這跟SIFT描述子、MCP描述子的高召回率有直接的關系。但MCP描述子的重建效率要遠遠高于SIFT描述子。

圖9 Fountain，Herzjesu三維稀疏點云Fig.9 Sparse point cloud of Fountain and Herzjesu

5 結 論

本文針對SIFT描述子構建時間、匹配時間長和傳統(tǒng)二進制描述子對尺度、視角變化和非平面幾何變換魯棒性差的問題，提出了一種新的二進制描述子算法。算法優(yōu)化采樣模式，根據(jù)特征點主方向旋轉采樣點到特定位置，并選擇機器學習訓練后的128對獨特性好、相關性低的采樣點對，在傳統(tǒng)二進制描述子灰度值比較的基礎上，添加梯度絕對值和比較測試構建描述子。實驗結果表明，本文提出的二進制描述子在描述子構建時間、匹配時間分別比SIFT描述子少84%，67%，在有視角變化的圖像匹配上，準確率比傳統(tǒng)的二進制描述子高3%～5%，召回率平均要高30%以上。但是本文提出的二進制描述子召回率不如SIFT描述子，下一步的工作將為提出的描述子選擇合適的關鍵點檢測器，增加描述子的匹配數(shù)總量，提高描述子的召回率。