原文：Stefan Leutenegger, Margarita Chli et al.《BRISK: Binary Robust Invariant Scalable Keypoints》

BRISK?

轉載請注明出處：http://blog.csdn.net/luoshixian099/article/details/50731801 CSDN-勿在浮沙筑高臺

摘要：從一幅圖片中高效地尋找關鍵點始終是一個深入研究的話題，以此形成了眾多的計算機視覺應用的基礎。正在這個領域中，先驅算法SIFT和SURF在各種圖形轉換中表現出了巨大的性能，特別是SURF在日益更新的高性能方法中被認為是計算最有效的方法。本文提出的BRISK算法是用于關鍵點檢測，描述和匹配的一種新方法。在基準數據庫中隊BRISK的綜合評價為：自適應和在大大降計算低成本下所表現的高質量的性能（這一些情況下，計算速度要比SURF快一個數量級）。速度的關鍵在于一種新的尺度空間的應用：基于FAST的檢測器結合組裝好的一位串描述子，該描述子從每個關鍵點附近專門取樣的強度比較檢索得到的。

1.引言

? 將圖像分解為本身感興趣區域或特征區域是一種在計算機視覺中廣泛應用的技術，用來降低當尋找原圖像表面特征的復雜度。圖像表示﹑目標識別﹑匹配﹑三維場景重建以及運動跟蹤都依賴于圖像中穩定的具有代表性的特征，這個問題促進了研究并產生了大量的方法。

理想的特征點檢測器發現突出的圖像區域，這樣以來盡管其角度變化，它們也可以重復檢測特征點；更一般的是對于所有可能的圖像轉換它都得是穩健的。同樣地，理想的關鍵點檢測器捕捉了最重要和獨特的信息內容，這些內容包含在檢測到的突出區域，這樣的話，如果遇到相同的結構區域也可以被識別出來。此外，在滿足這些屬性來實現所需的關鍵點的質量，檢測器和描述子的速度同樣需要優化來滿足手頭任務的時間約束。

? 在原則上，最先進的算法目標在于即應用于嚴格要求的實驗精度也應用于計算速度。Lowe’?的SIFT?算法是一個目前被廣泛接受的最高質量的選擇，對各種常見的圖像轉換具有有效的特殊性和不變性，然而，這種算法以計算代價為成本。在另一方面，FAST關鍵點檢測器和BRIEF方法的結合對描述子提供了更實時應用的選擇。然而盡管速度擁有明顯的優勢，但就可靠性和穩健性而言后一種方法更易接受，因為它具有最小的圖像扭曲和旋轉的承受度，尤其在平面旋轉和尺度變換上更明顯。結果，像SLAM這樣的試試應用程序需要對數據關聯運用概率性的方法來找到匹配一致性。

? 從圖像中提取合適的特征點的內在困難在于平衡兩個相互矛盾的目標：高質量的描述子和低計算需求。這就是這項工作的目的，即用BRISK方法建立一個新的里程碑。也許最相關的任務是解決這個問題：SURF已經演示了穩健性和速度的實現，只是，要得到的結果很明顯，在花費更少的計算時間BRISK獲得了更可觀的匹配效果。簡而言之，本文對從圖像中得到特征點提出了一個新的方法，得到的要點如下：尺度空間特征點檢測：圖像和尺度維度都是通過使用一個顯著性的標準來識別感興趣特征點。為了提高計算效率，在圖像金字塔的octave層和層于層的中間檢測特征點。通過在連續域擬合二次函數來獲得每個關鍵點的位置和尺度。關鍵點檢測：由點組成的樣本模式位于比例合適的同心圓上，在每一個關鍵點的相鄰位置使用該圓來檢測灰度值：就地處理強度梯度，決定了特征描述方向。最后，面向BRISK?的采樣模式用于獲得成對的亮度對比結果，將結果組合成二進制BRISK描述子。

? BRISK關鍵點一旦生成由于描述子的二進制本質特點就可以非常高效的匹配。強烈注意一下其計算速度，BRISK還利用存儲SSE指令在今天的架構中提供了廣泛的支持。

2.相關工作

??識別局部感興趣區域用于圖像匹配在文獻上可追蹤很長的一段路，由Harris和Stephens提出一個最早和最著名的角點檢測開始。Mikolajzyk等人的創造性工作在當時提出了一個綜合評價最具有競爭性的檢測方法，這揭示了沒有一個單一的通用檢測器用于檢測而是取決于應用上下文的不同方法的互補性質檢測。關鍵點檢測器最近的FAST標準已經成為越來越受歡迎的最先進的具有硬實時約束的方法，用AGAST擴展這些工作來提高性能。

? 在文獻中質量最近最好的特征點提取方法是SIFT。高描述力和魯棒性來啟發和觀點改變使得評價SIFT描述子在調查中處于最高位置。然而，這種描述子使得SIFT的高維度提取速度非常慢。PCA-SIFT?使得描述子從128維降到了36維，但是，影響其特殊性和增加描述子形成的時間幾乎使得增加匹配速度的性能毀于一旦。這里值得注意的是，GLOH描述符也屬于類SIFT方法家族，也已經證明其具有獨特性但是比SIFT要付出更多昂貴的計算。

? 對特征提出日益增長的高質量和高速度的需求已使得更多的算法研究能夠以更高的速率處理大量的數據。值得注意的是，Agrawal等人用中心對稱的局部二值化模式作為另一個SIFT方向直方圖的方法。最近的BRIEF算法是超高速描述符，匹配以及二進制串的組合設計的，包含了簡單的圖像增強在隨機預定的像素位置的比較。盡管這種方法簡單并且有效，但其對圖像旋轉和尺度變換非常敏感，以此限制了其通用功能的應用。

? 可能目前最吸引人的特征點提取方法是SURF，它已被證實比FAST?速度明顯快很多。SURF特征點檢測使用了Hessian矩陣（blob檢測器）的行列式，而其描述符是總結了Harris小波在感興趣區域的響應。SURF展示了令人深刻的最先進的計時，在速度方面，數量級仍然是遠遠不夠最快的，目前這些限制了其提取特征點的質量。

? 本文提出了一種新穎的算法稱為BRISK，其具有高性能，快速的特征點檢測和描述符以及快速匹配。意如其名，該方法在很大程度上具有旋轉不變性和尺度不變性，實現了高性能和最先進的同時極大地降低了計算成本。下面的特征描述子的方法是，目前在基準數據庫執行的實驗結果和使用標準化的評價方法。即提出了關于SURF和FAST的BRISK評價，這被廣泛地接受為在常見的圖像轉換領域內的比較準則。

3.BRISK

??在本節中，描述了BRISK的關鍵步驟，即詳細地描述特征檢測﹑描述符組成以及關鍵點匹配，激勵讀者更好的理解和創新。注意該方法的模塊化是很重要的，方法允許使用BRISK檢測器結合其他任何的關鍵點檢測算子，反之亦然，需要優化當前的算法性能和任務。

3.1?尺度空間的檢測

??注重計算效率，特征檢測方法是Mair等人對圖像感興趣區域檢測時的工作啟發。他們的AGAST本質上是現在流行的FATS算法性能的擴展，被證明是特征提取的一個給出有效的基礎。實現尺度不變性的目標對高質量的關鍵點是至關重要的，為了進一步得到極大值，不僅要在圖像平面上研究，而且在尺度空間使用FAST分數作為精確地測量。盡管在粗軸上離散化尺度軸比選擇高性能檢測器更難，但BRIEF檢測器估計了在每一個連續的尺度空間的每一個特征點的真實值。

? 在BRIEF的框架中，尺度空間金字塔的組成是n個octave層（用ci表示）和n個intra-octave層（用di表示），文章中n=4，i={0,1,...,n-1}。假設有圖像img，octave層的產生：c0層就是img原圖像，c1層是c0層的2倍下采樣，c2層是c1層的2倍下采樣，以此類推。intra-octave層的產生：d0層是img的1.5倍下采樣，d2層是d1層的2倍下采樣（即img的2*1.5倍下采樣），d3層是d2層的2倍下采樣，以此類推。則ci、di層與原圖像的尺度關系用t表示為：，

? 這里重要的是要注意FAST和AGAST都為特征點檢測的掩膜形狀提供了不同的選擇。在BRISK中，主要使用了9-16個掩膜，即在16像素的圓中至少需要9個連續的像素來提供足夠亮或暗的像素來實現，相比于FATS標準的中心像素的實現。

圖1圖2

? ?開始時，FAST?9-16?檢測器在每一個octave層和octave層分別使用相同的閾值T來識別潛在的感興趣區域。接著，屬于這些感興趣區域的點在尺度空間上進行非極大值抑制（同SIFT算法?的非極大值抑制）：首先，問題是特征點需要在每一層的FAST得分值s的8鄰域內實現最大值條件。分值S定義為在一幅圖像的塊區域的點的最大閾值。其次，每一層及其上下層的得分值也要盡可能的低。檢查同樣大小的正方形鄰域：在每一層中內部邊長為2個像素的最可能是最大值。因為相鄰層（因此其FAST的得分）代表有不同的離散化，對其鄰域邊界進行一些插值。圖1描述了這個過程采樣和極大值檢測的一個例子。

? 尺度軸在octave?c0層的最大值檢測是一個特例：為了獲得FAST分數，因為c0層是最底層，故需虛擬有一個d-1層，在c0上使用FAST5-8。然而，在這種情況下，d-1層patch的分數需要比檢測的octave?c0的特征點低。

考慮到圖像的特點作為一個連續數字化不僅在圖像上也在尺度維度上，為每一個檢測到的最大值執行亞像素插值和持續的進行。為了限制細化過程的復雜性，首先，滿足一個二維最小二乘意義上的二次函數使得每3個score-patches（獲得該層和上下兩層的關鍵點）得到3像素突出最大值。為了比較重復采樣，考慮在每一層采用3x3的得分patch。接下來，這些突出的score用合適的一維曲線沿著尺度軸生成最后的得分估計和其最大值的尺度估計。最后一步，重復對圖像坐標在該層及鄰邊決定性尺度進行插值。BRISK檢測在Boat序列的兩幅圖中是近距離的的一個例子如圖2所示。

3.2?特征點描述

? 給定一組特征點（包含亞像素插值圖像位置和相關浮點型點的尺度值），BRISK描述子是由二進制串通過間接簡單的亮度比較測試的結果組成。這種觀點已證實是非常有效的，然而在這里使用更多的定性模式。在BRISK中，確定了每個特征點的特征方向以便得到方向均衡化的描述子，因此，實現旋轉不變性是一般魯棒性的關鍵。同時，精心選擇了注重描述最大化的亮度比較。

圖3

3.2.1??采樣模式和旋轉估計

?BRISK描述子關鍵的概念是利用采集關鍵點相鄰位置所使用的模式。該模式如圖3所示，以關鍵點為中心，在其周圍采集N個特征點的圓，定義多個相等局部圓形區域。這種模式類似于DAISY描述符，重要的是要注意到在BRISK中所使用的是完全不同的，DAISY專門為密集匹配建立的，刻意地捕捉更多的信息，因此，要求速度和存儲需求。

?為了避免混疊效果，對在模式中的采樣點Pi應用了高斯平滑，標準差δi正比于每個采樣點對應于各自中心的距離，定位和擴展模式在圖像中相應地為關鍵點k模式化，考慮一個N(N-1)/2個采樣點對，用集合（Pi，Pj）表示。這些點的平滑像素值分別為I?(Pi?,?σi?)?和I?(Pj?,?σj?)，用于估計局部梯度值g(Pi?,?Pj?)?的公式為：

???????????????(1)

所有組合方式的集合稱作采樣點對，用集合表示為：

????（2）

定義短距離點對子集S、長距離點對子集L（L個）為：

?????????????（3）

??????????

其中，閾值距離設置為：δmax=9.57t，δmin=13.67t，t是特征點k所在的尺度。

? 現在要利用上面得到的信息，來計算特征點k的主方向（注意：此處只用到了長距離點對子集），如下：

? 長距離的點對都參與了運算，基于本地梯度互相抵消的假說，所以全局梯度的計算是不必要的。這一點同時也被距離變量閾值δmin?的實驗確認了。

3.2.2??創建描述子

? 對于旋轉和尺度歸一化的描述子的建立，BRISK使用了關鍵點k周圍的抽樣點旋轉α?=?ARCTAN2?(gy?,?gx?)角度作為模式。和BRIEF類似，BIRSK的描述子也是一個包含512個比特位的向量，每個描述子由短距離點對(Pαi?,?Pαj?)?∈?S兩兩進行比較產生的，上標alpha表示旋轉的模式。這樣的每一位b對應于：

? 與BRIEF不同的地方是，BRIEF只是進行亮度比較，除了預設尺度和預先對樣本模式的旋轉之外，BRISK和BRIEF有著根本的區別:一.BRISK使用固定的樣本模式點，而且是以R為半徑圍繞關鍵點周圍的圓進行均勻取樣。因此特定的高斯核平滑不會突然地扭曲亮度內容的信息(模糊鄰近的兩個采樣點的亮度,從而保證亮度平滑過渡)二.與兩兩組成的點對比BRISK顯著的減少了采樣點的數量(例如，單個的樣本點參與了更多的比較)，限制了亮度查找表的復雜度三.這里的比較是受到空間的限制的，所以亮度的改變僅僅只是需要局部一致性就可以了。對于上面的采樣模式和距離閾值，獲得了一個長度為512個比特位串。BIRSK64的描述子也是一個包含512個比特位的向量，因此為一對描述子匹配將以同樣的速度進行定義。

3.3?描述符匹配??

? 匹配兩個BRISK描述符是簡單的計算他們在BRIEF中漢明距離：比特位數量是不同的兩個描述符它們的衡量是不同的。注意他們各自通過位計數來減少按位操作的運算操作，在今天的架構中它們都可以非常有效地計算。

3.4??實現說明

? 這里，對一些方法實現的問題給出了一個簡短的概述，這些問題對整體的計算性能和該方法的重現性具有顯著的貢獻。所有基于OpenCV的常見的二維特征點界面的BRISK功能都可以用存在的特征點提取算法(SIFT,SURF,?BRIEF,?等等）簡單的整合和互換。

? 為計算顯著性得分檢測過程使用了AGAST算法實現。非最大值抑制受益于早期的終止能力，以此限制了顯著得分計算到最小值。建立圖像金字塔使用了一些SSE2和SSE3指令，這兩個指令都是關于半抽樣以及下抽樣的1.5倍。

? 為了有效地用采樣模式檢索灰度值，生成了一個離散旋轉的和已尺度化的BRISK模式版本的查找表，包括取樣點的位置和高斯平滑內核的屬性以及長短距離配對的索引，這些消耗了大約40MB的RAM內存，所有這些仍然可接受受限的計算能力低的應用。另外,在一個簡化的高斯內核版本使用積分圖像，使用的激勵該內核為：在沒有任何增加計算復雜度的情況下改變σ時內核是可伸縮變換的。在最后的實現中，在浮點邊界和邊長為ρ?=?2.6?·?σ使用了一個簡單的平方均值濾波器誤差估計。因此，不需要在整幅圖片中使用許多不同內核的高斯平滑來浪費時間，而是使用一個任意的參數σ檢索單個值。本文還整合改進了SSE漢明距離的測量來實現目前OpenCV六倍的速度來實現匹配，例如帶有BRIEF的OpenCV版本。

4?實驗

? 本文提出的方法在廣泛地測試后，現在在首先由?Mikolajczyk?和?Schmid提出的領域中建立了評價方法和數據庫。為了在其他的工作提出一致性的結果，本文也使用了在線的MATLAB評價版本。每一個數據庫包含了一個六個圖像的序列，變現出越來越多的轉換數量。這里所有的比較都在每一個數據庫上對比第一張圖片實現的。圖4顯示了一幅分析每個數據集的圖片。

圖4

? 這個變換包含了角度改變（Graffiti?和?Wall），縮放和旋轉（Boat），濾波（Bikes?and?Trees），亮度變化（Leuven），以及JPEG壓縮（Ubc）。因為角度變化場景是平面的，相比于OpenCV2.2版本的SIFT和OpenCV初版的SURF，在所有序列的圖像對上提供了一個地面真實的單一性矩陣用于BRISK的檢測和描述器的展示。評估使用了相似性匹配，該匹配認為每對特征點的描述子距離都低于某個閾值匹配，例如相比于最近鄰匹配，用最低的描述子距離來尋找數據庫的位置。最后，展示了BRISK在屬比較計時的計算速度方面的一大優勢。

4.1?BRISK檢測重復性

? 檢測重復性定義為，在兩幅圖中計算相應的關鍵點和最小關鍵點的數量。相應標志是通過查看一幅圖中關鍵點區域的重疊區域（即提取圓）和從其他圖形中得到的關鍵點區域的投影：如果相交的區域大于共同區域的50%，就被認為是一個相應標志。用這種方法標記在很大程度上依賴于關鍵點圓形區域的工作，即尺度和半徑之間的常數因子。像這樣選擇用BRISK檢測器獲得的平均半徑和SURF和SIFT獲得的平均半徑大致匹配。

? 重復性評價得分（選擇的結果如圖5所示）在一個序列中實施使用連續的BRISK檢測閾值。為了達到與SURF檢測器相當的比較，選擇使用了各自的Hessian閾值在相似的基本的匹配步驟下使其大概輸出一樣的相應標志數量。

? 如圖5所示，BRISK檢測器展示了和SURF一樣的重復性只要應用的圖像轉換不是很大。然而鑒于在計算速度上BRISK比SURF更具有明顯的優勢，本文提出的BRISK方法成為了強有力的競爭對手，即使在大尺度變換上似乎也稍遜一籌。

圖5

??

4.2???總體評價和比較BRISK算法

? 因為任務的目的在于提供一個總體及速度快有具有健壯性的檢測器，描述子和匹配，所以評估了BRISK中相比于SIFT和SURF的所有步驟的共同表現。圖6?顯示了在選擇不同數據集的圖像對，準確性-記憶曲線使用基于閾值的相似匹配。對這個評估又適應于檢測閾值，以此輸出一個在公平的意識下相應標志大致相等的數量。注意這里的評價結果與[3]中的不同，那里所有的描述子都是在相同的區域中提取的（用Fast-Hessian獲得的）。

? 如圖6?所示，BRISK在所有數據集上比SIFT和SURF更有競爭優勢，甚至在一些情況下遠遠勝過其他兩個。BRISK在樹的數據集上的降低性能是由于檢測器的性能：當SURF檢測到2606和2624圖像區域時，BRISK在圖像4中只檢測到2004個圖像區域，相比于在圖片1中找到5949個圖像區域，實現了相應標志的大致相等的數量。這樣的方法同樣適用于其他的濾波數據集，Bikes：FAST的突出本質上比其他的類blob檢測子更敏感。因此，顯示了從SURF區域中為樹的數據集提取BRISK描述子的評價。

?圖6

? 顯然，SIFT在圖Trees,?Boat,?和Ubc?datasets中的性能明顯惡化，這可以解釋在這些情況下檢測器重復性受限的原因。另一方面，SIFT和BRISK處理純平面旋轉的重要情況很好，比SURF更好。

? 為了完成實驗的這個部分，聯系到了BRIEF算法。圖7?顯示了不具有旋轉的單尺度的BRISK版本（SU-BRISK）和64字節的BRIEF特征點在相同的（單尺度）AGAST特征點上的比較。還包括了旋轉不變性，單尺度的BRISK（S-BRISK）以及標準的BRISK。實驗用兩幅圖像對進行：一方面使用了前兩幅圖片，在圖Wall數據集中證明SU-BRISK和BRIEF64在沒有單尺度和平面旋轉的情況下都表現出非常相似的性能。注意到，BRIEF算法設計的真實條件。另一方面，應用不同的版本到圖Boat序列的前兩幅圖片：本次試驗顯示了一些就小規模旋轉和尺度變化的魯棒性而言SU-BRISK比BRIEF更讓你更具有優勢。此外，眾所周知的和明顯代價的旋轉和尺度不變性是很容易觀察到的。

4.3?時間安排

? 時間控制已經記錄在配備四核i7?2.67?GHz處理器（雖然只用了一個核）運行Ubuntu?10.04?(32位）的筆記本電腦中，使用了上面詳細的實現和設置過程。表1?給出了有關在圖Graffit序列的第一幅圖片的檢測結果，而表2?顯示了匹配時間。運行平均值超過了100次。注意到，所有的匹配器在沒有任何提前終止優化的前提下都做了暴力描述符距離計算。

表1表2

? 計時顯示了BRISK的一個明顯的優勢，它的檢測盒描述子的計算通常比SURF的速度快一個數量級，這被認為目前存在的最快的具有旋轉不變性和尺度不變性的特征點匹配。同樣重要的是，要強調BRISK可以容易更快地執行尺度化，通過在以匹配質量為代價的模式下減少采樣點的數量，這是一個特定的應用下可能承擔得起。此外，尺度或旋轉不變性可以省略，在不需要的應用上增加速度和匹配質量。

4.4?例子

? 對以上的提出補充廣泛的評價，也提供了一個使用BRISK作為匹配的真實例子。圖8顯示了一幅圖像對展現了各種變換。一個閾值為90的相似性匹配在沒有明顯的異常值得情況下得到的魯棒性匹配（超過512對特征點）。

圖7

5?結論

? 本文提出了一種新穎的方法稱之為BRISK，解決了經典的計算機視覺的檢測問題，在現場和照相位置沒有足夠的先驗知識下描述和匹配圖像關鍵點。相比之下，與已建立且證明具有高性能的算法如SIFT和SURF相比，本文的方法實在地提供了一個戲劇性更快的按可比的匹配性能的選擇，基于一個廣泛評價的一份聲明中使用既定的框架。BRISK依賴一個簡單地可配置的圓形的采樣模式，模式從它形成一個二進制描述符字符串計算亮度的對比。BRISK的獨特特性可用于廣泛的應用，特別是對硬實時約束或有限的計算能力。最后，BRISK在費時的應用中提供了高端的特征點質量。

? 在對BRISK進一步研究的道路上，目標是探索能替代尺度空間最大值收索突出得分到生成更好高的可重復性，同時保持速度。此外，目標在于分析理論和實驗上的BRISK模式和配置的比較，這樣的描述子的信息內容或魯棒性是最大化的。

總結

以上是生活随笔為你收集整理的BRISK的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。