SLAM前端 ---------特征提取之ORB（ORB与SIFT与SURF）
ORB 論文翻譯： 一種特征匹配替代方法：對比SIFT或SURF
1.ORB特征簡介?
ORB是Oriented FAST and Rotated BRIEF（oFAST and rBRIEF）的簡稱，ORB的名字已經說明了其來源，其實ORB特征是采用FAST方法來檢測提取特征，但FAST特征本身是不具有方向性的，所以在ORB特征中添加對特征方向的計算；另外，ORB采用BRIEF方法計算特征描述子，BRIEF的優點在于速度，但是缺點也很明顯：不具備旋轉不變性，對噪聲敏感，不具備尺度不變性。orb-slam重點解決的是旋轉不變性和噪聲問題。接下來，首先針對orb特征進行詳細說明，并在下一章節中針對orb-slam（version1）中的orb代碼部分進行解析測試。
［以下為個人學習理解，如果錯誤，歡迎指正］?
2.orb特征之oFAST
如何確定特征點？?
FAST特征以其計算速度快被廣泛使用，ORB特征除了使用FAST方法定位特征點位置之外，還針對特征點的方向進行了補充添加。
FAST特征的基本原理是對于當前像素點，取鄰域離散圓周上若干采樣像素點（如下圖的p點表示當前像素位置，以3個像素點為半徑，標號1-16的16個點表示圓周上采樣的16個像素點）
我們認為一個像素如果是“角點”（即特征點），那么這16個采樣點中至少有N（N可以等于9，12等，對應于FAST-9，FAST-12等）個連續像素點要么大于當前像素點加上一個閾值，要么小于當前像素點減掉一個閾值，我們設這個閾值為t。但實際上，通常在圖像中，“角點”的數量要遠小于非“角點”的數量，所以可以采用一種更快速的方法來確定當前像素點是否為“角點”（實際上是快速的排除非特征點的像素），方法是，?
1）當前像素點p與標號為1，9的像素點進行比較，如果有Ip?t<Ii<Ip+t,i=1 or 9 ，則當前像素點肯定不是“角 ? ? ? ? ? ?點”，否則的話進行下一步判斷;?
2）當前像素點p與標號1，5，9，13的像素點進行比較，如果至少有三個像素點滿足Ii<Ip?t?or?Ii>Ip+t,i=1 or 5 or ? ? ? 9 or 13，則認為當前像素點可能為“角點”，進行下一步判斷；?
3）當前像素點p與所有標號的采樣像素點進行比較，如果至少有N (N可以等于9，12等，對應于FAST-9，FAST-12等)個連續 ? ? ? ? ? ? 像????素點滿足Ii<Ip?t?or?Ii>Ip+t,i=1...16?，則認為當前像素點為“角點”，即FAST特征點，進行下一步非 ? ? ? ? 極大值抑制；?
4) 非極大值抑制主要是為了避免圖像上得到的“角點”過于密集，主要過程是，每個特征點會計算得到相應的響應得分，然后以當前像素點p為中心，取其鄰域（如3x3 的鄰域），判斷當前像素p的響應值是否為該鄰域內最大的，如果是，則保留，否則，則抑制。
?
非極大值抑制，排除不穩定角點。采用強度響應函數：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
即一個角點強度值定義為中心點與邊上的12個角點像素差值的絕對值累加和。
上面針對如何選擇特征點進行了說明，需要補充的是，orb特征中使用不同尺寸圖像構成的圖像金字塔，并分別在每一金字塔層圖像上提取FAST特征，這樣每一個被提取的特征具有“尺度”這一屬性。
如何確定特征點方向？?
現在我們已經知道如何在當前尺度空間中提取FAST特征，而特征點除了坐標／尺度（層）屬性之外，還需要確定特征點的方向。接下來，將闡述orb如何為每一個特征點分配方向。
orb特征確定特征點方向的思路很簡單，首先根據“矩”概念確定當前特征點鄰域塊的重心位置C?，然后根據當前像素點中心O?和C?的連線方向確定特征點方向θ?像素塊區域的“矩“定義為，?mpq=∑x,yxpyqI(x,y)
則重心坐標公式為，?C=(m10m00,m01m00)。那么，特征點的方向角度定義為，θ=atan2(m01,m10)?
3.ORB特征之rBRIEF
如何計算特征點描述符？?
上面已經介紹了如何提取圖像中的FAST特征以及如何計算特征點的方向，接下來將介紹如何計算每一個特征點的描述子。
ORB特征描述子采用BRIEF描述子并進行了改進，BRIEF描述子占用空間小，得益于BRIEF描述子的每一位要么是0要么是1，其基本思想是：在特征點鄰域塊內，按照一定的規則選擇若干對像素點p,q?，如果有Ip>Iq,則當前位的BRIEF描述子的值為1，否則為0。對于比較像素點對的個數，通?？梢赃x擇128，256不等。
但實際上，這樣會存在一個很嚴重的問題，就是得到的描述子會對噪聲很敏感，如果比較的像素點屬于噪聲，將對描述子的可靠性造成重要影響。所以，將上述的比較規則進行了調整，?
τ(p;x,y):=1:p(x)>p(y);τ(p;x,y):=0:p(x)≤p(y)
其中,p(x)?表示像素點x的強度值,可以選擇高斯濾波值作為當前像素點的強度值，這樣比較的兩者不會是單獨的兩個像素點值，而是像素點鄰域塊的加權平均值，從而有效地降低了噪聲的影響。
?
steered BRIEF?
BRIEF描述子本身沒有解決旋轉不變性的問題，所以在orb特征中對這個問題進行了解決，解決思路也很簡單，就是在計算特征點描述子的過程中，將其鄰域的若干比較對根據特征點的方向進行相應的旋轉變換，即，如果n?個測試對坐標表示為S=(P1,P2,...,Pn),Pi=(xi,yi)
特征點方向角度為θ?，對應的旋轉矩陣為Rθ，那么修正后的比較點對坐標Sθ為，?Sθ=RθS
將修正后的坐標Sθ?帶入描述子的計算，這樣得到的描述子是具有據轉不變性的。
rBRIEF?
上面闡述中有一個關鍵問題，那就是應該如何選擇比較點對呢？這樣考慮，如果比較點對的個數為256，那么最終的BRIEF描述子的位數就是256位，一個好的BRIEF描述子的每一位的變化性（variance）應該是足夠大的，或者說每一位的數值分布是比較均勻的，不會過于密集或稀疏；另一個方面，BRIEF描述子的不同位之間應該是不相關的（也就是任意一位的表示應該具有代表性，而不會被其他的若干位線性表示）。
orb特征采用下面這樣的算法來選擇比較點對的坐標，?
首先從數據集中確定300k個關鍵點。對于31x31的像素塊，窮舉所有5x5的子窗口像素塊，也就是31x31像素塊中所有的子窗口可能性有N=（31-5）＊（31-5）種.那么從N種子窗口中選擇2個子窗口進行比較的可能性就有C2N，除去存在重疊的比較子窗口對，最終有M=205590種測試可能（比較子窗口對）。
接下來，?
1）對于M種中的每一種測試可能性，在300k個關鍵點上計算比較結果（每一種可能性對應于BRIEF描述子中的一位）；?
2）對于每一種測試可能性在關鍵點上的比較結果，計算300k個數據上的平均值，并按照距離0.5的遠近大小由小到大進行排序，構成集合T（距離0.5越近，認為數據分布越平均，可以考慮這樣的例子，100個數據中，有50個1，50個0，這樣的數據是分布最均勻的，均值為50/100=0.5；而如果100個數據中均為1，則均值為100／100=1，是數據分布最為密集的情況）。這一步是考慮選擇盡可能使得每一位BRIEF描述子的數據分布分散的比較對。?
3）采用貪心算法?
3.1）首先將T中的第一個測試對放入集合R；?
3.2）從T中取下一個排序測試對，并與R中的所有測試對計算關聯度，如果關聯度超過一定的閾值，則放棄當前從T中取到的測試對；反之，則將當前的測試對加入集合R中；?
3.3）重復前兩步，直至R中有256個測試對。
R中挑選的256個測試對就是滿足：?
a 每一位描述子的variance盡可能大；?
b 不同位描述子之間的關聯度盡可能小。
4.總結?
總而言之，ORB特征是采用FAST方法定位特征點坐標，采用矩方法計算特征點方向，使用BRIEF計算特征點描述子并根據特征點方向使得描述子具有旋轉不變性，另外，通過貪心算法確定測試對。
ORB 論文翻譯
繼”ORB-SLAM: Tracking and Mapping Recognizable Features”，”Bags of Binary Words for Fast Place Recognition in Image Sequences”后已經對ORB SLAM的基本框架
摘要：
特征匹配是許多計算機視覺問題的基本問題，如目標（物體）識別或運動分析的三維結構信息。目前特征查找和匹配的特征向量描述計算代價巨大。本文提出了一種基于BRIEF的快速二進制特征向量描述器，稱為ORB。它具有旋轉不變特性和噪音抑制的特性。我們通過各種狀態下的實驗，演示了ORB如何在兩個維度上，運算速度快于SIFT，并且在智能手機上測試了物體識別和跟蹤的應用程序。
1.?? 簡介
SIFT關鍵點檢測和特征向量描述，這項技術的發明已經有超過10多年的歷史，它成功應用于各種使用視覺特征的場合，包括物體（目標）識別，圖像配準與拼接，視覺地圖構建。但由于需要大量運算而受限，尤其是實時應用的系統中，如視覺里程計或像在手機這樣低成本的設備中。于是出現了較小運算代價，用于大量密集數據的圖像像素查找算法的出現，其中最優秀的是SURF。還有一些研究旨在提高SIRF的運算效率，大部分是帶有GPU的設備。
本文提出了一種高效算法，與SIFT有相同的特征匹配性能，同時具有較強的圖像噪聲抑制行性能，能夠用于實時系統中。我們的目的是加強通用型圖像匹配程序的功能，使得無GPU加速的低功耗設備能夠處理全景圖像拼接和圖像塊追蹤，以減少物體識別的運算時間。在這些維度上，我們的特征向量描述方法和SIFT性能一樣，優于SURF。我們的特征描述基于FAST關鍵點檢測和BRIEF特征向量描述器，因此我們把它叫做ORB（Oriented FAST and Rotated BRIEF）。這些技術性能優良、成本較低，非常有吸引力。本文中，相對于SIFT，我們提出了這些技術的局限性，尤其是BRIEF不具備旋轉不變性。我們的主要貢獻在于：
- 對于FAST算法，增加了快速準確的方向指向功能；
- 高運算效率的具有指向功能的BRIEF特征；
- 具有指向功能的BRIEF特征的方差及相關性分析；
- 基于旋轉不變且去關聯性的BRIEF特征的方法，用于減少近鄰取樣（點取樣）應用中。
為了檢驗ORB，我們對ORB，SIFT，SURF的相關特性進行了對比實驗，主要是原始數據匹配能力和圖像匹配性能。我們還在智能手機上演示了ORB圖像區塊追蹤的應用。另外，ORB的使用并不會受到SIFT和SURF的使用許可的限制。
2.相關工作
關鍵點? FAST和它的變形方法是實時系統中用于視覺特征匹配查找關鍵點的主要方法，比如在PTAM中的使用。盡管仍然需要金字塔模型在尺度上對該方法進行增強，但這個方法還是可以很有效地查找合理的角關鍵點，在我們的例子中，哈里斯角點檢測濾除邊緣并提供了一個合理的分值。
很多關鍵點檢測模型都包含了定位算子（比如SIFT和SURF），FAST算法卻沒有。有很多方法可以描述關鍵點的方向信息，大多采用方向梯度直方圖計算，比如SIFT或者類似于SURF圖案區塊。這些方法要么計算量要求大，要么像SURF那樣只是近似估計。論文22，分析了各種測量角點方向的方法，我們借用了他的質心方法。與SIFT中的定位算子中單個關鍵點有多個值的狀況有所不同，質心算子只給出一個主要的結果。
特征向量描述子? BRIEF是特征向量描述子，其結果是在平滑圖像塊中使用簡單的二進制比較兩個像素的值。在很多方面和SIFT的性能非常相近，包括對于光照，模糊，圖像變形的魯棒性。但它對于平面旋轉非常敏感。
BRIEF的研究源于用二進制結果生成一個樹形分類模型。一旦對500個左右的典型關鍵點完成訓練，樹狀模型就可以用于判斷任何關鍵點并返回特征標記。同樣的方法，我們就可以查找對方向最不敏感的比較結果。用于查找不相關比較結果的經典方法是主因分析法，SIFT的主因分析法（PCA）可以去掉大量冗余信息。但是，二進制的比較結果太多占用大量內存不能采用PCA方法，而采用窮舉搜索算法。
視覺字典方法采用離線聚類查找不關聯的樣本用于匹配。這些方法用于搜索不關聯的二進制比較結果也有可能有用。
與ORB最相似的方法是論文3，它提出了一種多尺度的哈爾斯關鍵點和圖案方向描述子。這種描述子用于圖像配置和拼接，表現出良好的旋轉和尺度不變特性。但計算效率沒有我們的高。
3.? oFAST：FAST關鍵點方向
FAST特征方法由于運算速度快而被廣泛采用。但FAST特征卻不具備方向特性。在這一章，我們將為它添加一個高效的方向特性。
3.1 FAST特征點檢測
我們開始偵測圖像的FAST特征點。FAST算法的一個參數，是一個亮度閾值判斷中心像素（目標像素）和它周圍一圈像素的比值。我們采用性能最好的FAST-9算法（半徑為9個像素）。
FAST算法并不生成角點，我們發現它在邊緣上有明顯特征。我們采用Harris角點(也叫特征點，關鍵點，興趣點) 檢測器算法來規則化局部FAST關鍵點。對于N個局部關鍵點，首先設置一個很低的閾值以足夠獲得N個關鍵點，再根據Harris角點檢測器來把它們規則化，選取前N個點。
FAST算法并不能產生多尺度的特征點。我們采用圖像金字塔尺度模型，在金字塔的每層采用Harris濾波生成FAST關鍵點。
/*作者寥寥數句話，就把FAST特征和Harris角點檢測算法給說完了，這背后巨大的知識量，額，我還沒完全消化。這里就停下來先搞懂<圖像處理>里面的基于<圖像表達>,<圖像數據結構>之后的<圖像預處理>部分的<圖像特征檢測>中的<角點檢測>。*/
3.2灰度質心定位方法
我們采用灰度質心定位的方法計算角點的方向?；叶荣|心定位方法的基本假設是角點與中心像素的亮度不同，這個向量可以推導出質心的方向。
《Measuring Corner Properties》（1999年）的作者Rosin定義了圖像塊的矩：mpq=∑x,yxpyqI(x,y)
其中I(x,y)為點(x,y)處的灰度
那么我們可以得到圖像區塊的質心為：C=(m10m00,m01m00)
那么我們可以從圖像區塊的角點中心O到質心(中心)像素的方向，構建一個向量 。
那么圖像區塊的方向可以簡單表示為：θ=atan2(m01,m10)
其中，atan2是象限相關的arctan函數。
Rosin認為，這跟角點灰度是亮還是暗有關，然而，我們并不關心這些，最重要的是角度的測量。
為了提高方法的旋轉不變性，我們要盡量確保用于計算矩的像素點（x,y）位于半徑為r的圓形區域內。既然圖像區塊的面積是半徑為r的圓形區域，那么x,y∈[?r,r]。當|C|接近0時，該方法就變得不穩定。但采用FAST角點情況下，這種情況基本不會出現。
我們對比了質心定位法與基于梯度的方法，BIN（直方圖概念相關）和MAX（高等數學方向導數和梯度）。在這兩種方法中，可以通過計算平滑圖像的X和Y梯度。MAX選擇圖像區塊關鍵點中最大的梯度方向。BIN在10個區間里面選擇最大的形成直方圖的梯度方向。盡管只選擇了一個方向，但BIN和SIFT算法比較類似。圖2給出了平面旋轉帶噪聲的圖像的數據集上的方差比較。它們的梯度方向測量都沒那么好，但在有圖像噪聲的情況下，質點定位法給你出的方向比較一致。
?
《ORB: an efficient alternative to SIFT or SURF》是Rublee等人在2011年的ICCV上發表的一篇有關于特征點提取和匹配的論文，這篇論文介紹的方法跳出了SIFT和SURF算法的專利框架，同時以極快的運行速度贏得了眾多青睞。下面我簡單介紹一下ORB算法的流程。
ORB算法的主要貢獻如下：?
（1）為FAST算法提取的特征點加上了一個特征點方向；?
（2）使用帶方向的BRIEF算法高效的對特征點描述符進行計算；?
（3）分析了BRIEF算法得到的特征點描述符的方差和關聯性；?
（4）介紹了一種基于學習的去特征點關聯性的BRIEF算法，優化了特征點求得的最近鄰點。
下面我按照論文的結構對ORB算法進行介紹。
1、oFAST: FAST Keypoint Orientation
1.1 FAST Detector
ORB算法使用的是FAST算法提取的特征點，在作者的實驗中使用的FAST-9的算法，得到了很好的結果。?由于邊緣位置對FAST算法得到的特征點有很大的影響，因此作者使用了Harris 角點檢測方法對于得到的特征點進行排序，取前N個較好的角點作為特征點。
FAST算法是一種非常快的提取特征點的方法，但是對于這里來說，有兩點不足：?
（1）提取到的特征點沒有方向；?
（2）提取到的特征點不滿足尺度變化。?
針對特征點不滿足尺度變化，作者像SIFT算法中那樣，建立尺度圖像金字塔，通過在不同尺度下的圖像中提取特征點以達到滿足尺度變化的效果。?
針對提取到的特征點沒有方向的問題，作者采用了Rosin提出的一種稱為“intensity centroid”的方法確定了特征點的方向。?那么，就來看一下確定特征點方向的方法。
1.2 Orientation by Intensity Centroid
這種方法的主要思想就是，首先把特征點的鄰域范圍看成一個patch，然后求取這個patch的質心，最后把該質心與特征點進行連線，求出該直線與橫坐標軸的夾角，即為該特征點的方向(同上)。??
2、rBRIEF: Rotation-Aware Brief
2.1 rBRIEF特征描述
rBRIEF特征描述是在BRIEF特征描述的基礎上加入旋轉因子改進的。下面先介紹BRIEF特征提取方法，然后說一說是怎么在此基礎上修改的。
BRIEF算法描述
BRIEF算法計算出來的是一個二進制串的特征描述符。它是在一個特征點的鄰域內，選擇n對像素點pi、qi（i=1,2,…,n）。然后比較每個點對的灰度值的大小。如果(pi)>?I(qi)，則生成二進制串中的1，否則為0。所有的點對都進行比較，則生成長度為n的二進制串。一般n取128、256或512，opencv默認為256。另外，值得注意的是為了增加特征描述符的抗噪性，算法首先需要對圖像進行高斯平滑處理。在ORB算法中，在這個地方進行了改進，在使用高斯函數進行平滑后，又用了其他操作，使其更加的具有抗噪性。具體方法下面將會描述。
關于在特征點SxS的區域內選取點對的方法，BRIEF論文(附件2)中測試了5種方法：
1）在圖像塊內平均采樣；
2）p和q都符合(0,S2/25)的高斯分布；
3）p符合(0,S2/25)的高斯分布，而q符合(0,S2/100)的高斯分布；
4）在空間量化極坐標下的離散位置隨機采樣；
5）把p固定為(0,0)，q在周圍平均采樣。
五種采樣方法的示意圖如下：
論文指出，第二種方法可以取得較好的匹配結果。在旋轉不是非常厲害的圖像里，用BRIEF生成的描述子的匹配質量非常高，作者測試的大多數情況中都超越了SURF。但在旋轉大于30°后，BRIEF的匹配率快速降到0左右。BRIEF的耗時非常短，在相同情形下計算512個特征點的描述子時，SURF耗時335ms,BRIEF僅8.18ms；匹配SURF描述子需28.3ms，BRIEF僅需2.19ms。在要求不太高的情形下，BRIEF描述子更容易做到實時。
改進BRIEF算法—rBRIEF（Rotation-AwareBrief）
（1）steered BRIEF（旋轉不變性改進）
在使用oFast算法計算出的特征點中包括了特征點的方向角度。假設原始的BRIEF算法在特征點SxS（一般S取31）鄰域內選取n對點集。
經過旋轉角度θ旋轉，得到新的點對
在新的點集位置上比較點對的大小形成二進制串的描述符。這里需要注意的是，在使用oFast算法是在不同的尺度上提取的特征點。因此，在使用BRIEF特征描述時，要將圖像轉換到相應的尺度圖像上，然后在尺度圖像上的特征點處取SxS鄰域，然后選擇點對并旋轉，得到二進制串描述符。
2.2 Efficient Rotation of the BRIEF Operator Brief overview of BRIEF
下面我們隊BRIEF算法進行一個簡單的回顧：?
BRIEF算法提取得到的特征點描述符是一個二進制的字符串，建設當前的一個特征點的鄰域空間patch，設為p，那么對該面片p定義的一個二進制測試
其中p(x)表示的是在點x處的圖像灰度值，那么這樣我們就可以得到一個n位的二進制串
fn(p):=∑1≤i≤n2i?1τ(p;xi,yi)對于x和y的坐標分布在本文中使用的是以特征點為中心的高斯分布，這種分布情況在Brief的論文原文中被證明是最好的。同樣，本文中選擇的n=256。?
考慮到圖像中有噪聲的干擾，在實際的求取特征點描述符的過程中，需要對圖像進行平滑操作。論文中使用的方法是，在對比操作τ進行的時候，不是對比的一個點，而是對比的在31?31的patch中的若干個5?5的子窗口。?
上面就是BRIEF算法的一個簡單回顧，BRIEF算法形成的描述符對于旋轉操作非常敏感，當旋轉的角度增大時，利用BRIEF算法的描述符進行匹配的結果極大的降低。如下圖所示：?
圖中x軸表示的是旋轉的角度，y軸表示匹配結果中正確匹配所占的百分比。可以看出，隨著旋轉角度的增大，BRIEF算法的匹配效果迅速的降低，旋轉角度在45度以上時，正確率幾乎為0。那么這就引出了我們接下來要介紹的Steered BRIEF算法。
?
Steered BRIEF算法介紹
想要讓BRIEF算法具有旋轉不變性，那么我們需要使特征點的鄰域旋轉一個角度，該角度就是我們上面求得的特征點的方向角θ。但是這樣整體旋轉一個鄰域的開銷是比較大的，一個更加高效的做法就是旋轉我們前面得到的那些鄰域中的匹配點xi、yi。?
設生成特征點描述符的n個測試點對為(xi,yi)，定義一個2×n的矩陣
利用角度θ形成的旋轉矩陣為Rθ，那么旋轉后匹配點的坐標為
Sθ=RθS這樣，在求取特征點描述符的時候，就使用Sθ中的像素點即可。
?
2.2 Efficient Rotation of the BRIEF Operator Brief overview of BRIEF
下面我們隊BRIEF算法進行一個簡單的回顧：?
BRIEF算法提取得到的特征點描述符是一個二進制的字符串，建設當前的一個特征點的鄰域空間patch，設為p，那么對該面片p定義的一個二進制測試
?
其中fn(p):=∑1≤i≤n2i?1τ(p;xi,yi)
p(x)表示的是在點x處的圖像灰度值，那么這樣我們就可以得到一個n位的二進制串。
對于x和y的坐標分布在本文中使用的是以特征點為中心的高斯分布，這種分布情況在Brief的論文原文中被證明是最好的。同樣，本文中選擇的n=256。?
考慮到圖像中有噪聲的干擾，在實際的求取特征點描述符的過程中，需要對圖像進行平滑操作。論文中使用的方法是，在對比操作τ進行的時候，不是對比的一個點，而是對比的在31?31的patch中的若干個5?5的子窗口。?
上面就是BRIEF算法的一個簡單回顧，BRIEF算法形成的描述符對于旋轉操作非常敏感，當旋轉的角度增大時，利用BRIEF算法的描述符進行匹配的結果極大的降低。如下圖所示：?
圖中x軸表示的是旋轉的角度，y軸表示匹配結果中正確匹配所占的百分比?？梢钥闯?#xff0c;隨著旋轉角度的增大，BRIEF算法的匹配效果迅速的降低，旋轉角度在45度以上時，正確率幾乎為0。那么這就引出了我們接下來要介紹的Steered BRIEF算法。
2.3 Variance and Correlation
作者提到，BRIEF的一個比較好的特性是，對于所有的特征點上的每一位（bit）上的值的平均值都非常接近0.5（這里的平均值比較難理解，舉個例子，比如說n個特征點中的所有的第i位的平均值），同時平均值的分布的方差較大。這樣很顯然有一個好處，就是方差越大說明數據的差異性越大，也就是說更能很好的區分不同的點。下圖為作者取100k個特征點中的256位中各位的平均值分布，其中橫坐標為平均值與0.5的差值，縱坐標是位的個數：?
?
可以看出BRIEF的所有特征點各個位上的平均值分布為以0.5為均值，方差很大的一個高斯分布。?
同樣看上面這個圖，我們發現steered BRIEF算法的結果中，所有特征點在各個位上的平均的分布則比較平均，這是因為進行旋轉角度θ?以后，均值就漂移到更加均衡的模式。?
作者同時對BRIEF、Steered BRIEF和rBRIEF（后面會講到）提取的100k個特征點的描述符(256)進行PCA提取主成份，根據得到的特征值進行分析，如下圖所示：?
?
可以看出BRIEF和Steered BRIEF中前幾個特征值比較大，那么基本上所有的信息都集中在這面的若干維中，而Steered BRIEF算法得到的特征值比BRIEF的特征值小很多，因此Steered BRIEF得到的描述符的方差分布小，也就意味的區分能力比較差。?
我們從另一個角度也可以證實這一點，如下圖所示，實線表示的是匹配成功的點的距離的分布，虛線表示的是匹配失敗的點的距離的分布，橫坐標是距離，縱坐標是頻率：?
?
可以看出相比BRIEF和rBRIEF，steered BRIEF得到的匹配結果中，匹配失敗的點的距離分布的平均值推左（論文中的push left，其實就是平均值偏小）了，這也就造成了成功和失敗的點的距離中有更多的交集。同時也就意味著匹配結果的不理想。
2.4 Learning Good Binary Features
rBinary
為了彌補Steered BRIEF算法造成的方差變小的缺陷，同時降低各個特征點的鄰域內的匹配點對的相關性，作者使用了一種學習的方法來從鄰域的所有可能的匹配點對中選出一個表現較好的子集用來生成特征點描述符。?
作者首先從PASCAL 2006的圖像庫中提取了300k個特征點作為訓練集，然后從每個特征點的31×31大小的鄰域中窮舉出所有可能的5×5的匹配子窗口。假設wp為總鄰域的邊長，wt作為子窗口的邊長，那么再這個鄰域中一共有N=(wp?wt)2個子窗口存在，從其中任意挑選2個子窗口，則有(N2)種可能的選擇，然后去掉其中重疊的子窗口的匹配可能，對于作者的實驗中，總共有205590種可能的匹配子窗口。?
然后算法運行如下：?
（1）對于每個特征點的鄰域中所有可能的子窗口進行匹配，則得到205590個匹配結果，這作為一行，由于一共有300k個特征點，因此能夠形成一個300000×205590的矩陣；?
（2）對于這個矩陣，求各列的平均值，并按照離0.5的大小從小到大進行排序，并記錄每列是由哪一對位置x和y的比較構成的，每隊看做一個元素，構成向量T；?
（3）貪婪搜索：?
*（a）取出距離0.5最近的兩個位置放到R，并在T中刪除；?
（b）在去除T中距離0.5最近的兩個位置，判斷該位置與R中已經存在的關聯性是否達到閾值，如果達到則拋棄當前的位置，如果沒有達到則把它加入到R中；?
（c）反復執行（a）、（b）中的操作，直到R中有256對，如果執行一遍沒有達到256，那么提高（b）中的閾值，再次進行此操作，直到選出256對為止。*?
利用這樣搜索出來的256對位置生成特征點描述符的方法就是我們前面提到的rBRIEF。?
至此我們講的oFAST + rBRIEF即為ORB算法。
?
3.? rBRIEF：具有方向旋轉的BRIEF算法
?
在這一章，將介紹Steered BRIEF (轉向BRIEF)特征描述子，帶有方向旋轉變量后BRIEF性能變差，我們將演示如何有效地改進算法。我們提供了具有更少關聯性的二值測試方法用來獲得更好的rBRIEF特征描述子，還與SIFT和SURF做了比較。
4.1BRIEF方向旋轉
BRIEF概覽
BRIEF（BinaryRobust Independent Elementary Features）特征描述子，是對圖像區塊二值字符串的描述，圖像區塊由二值灰度比較的結果構成。對于平滑的圖像區塊P，二值判斷方法τ如下定義：
具有方向旋轉的BRIEF
我們希望BRIEF具有旋轉不變的特性。如圖7所示，BRIEF的匹配性能在較小的角度內劇烈下降。
Calonder建議針對一組旋轉和每個區塊的圖像形變計算BRIEF特征描述子，但計算代價昂貴。一個更有效率的方法是根據關鍵點的定位調整BRIEF的方向。對任何在點（Xi, Yi）上的n個二值測試特征組，定義2xn的矩陣：
采用圖像區塊旋轉角度θ和相應的旋轉向量Rθ，我們構建一個可轉向的S版本Sθ: ?
那么具有旋轉方向BRIEF就變成：?
我們將角度分散到2π/30（12度）增量中，構建一個存儲已經計算的BRIEF模式的查找表。關鍵點方向θ對多視圖具有一致性，校準的點Sθ將被用于計算它的特征描述子。
4.2方差和相關性
BRIEF的一個最好的特征就是每個特征位的方差比較大，均值接近0.5。圖3給出了典型的高斯BRIEF模式包含256bits和100K關鍵點。對一個特征位，均值0.5的最大樣本方差0.25。另外，一旦BRIEF根據關鍵點方向進行定位形成方向旋轉BRIEF，均值就會呈分散模式，如圖3所示。對這種情況的理解是，具有方向的角點關鍵點對二值比較結果具有更高的均衡性。
由于對數據輸入反饋不同，方差越大，特征區別越明顯。每個比較都對結果有影響，另一個期望的特性是使二值結果不相關。為了分析BRIEF向量中二值測試結果的相關性和方差，我們考查具有100K關鍵點的BRIEF和具有方向旋轉的BRIEF的反饋情況。測試結果如圖4所示。我們采用PCA算法對數據分析，繪制了40個最高的特征值（經過2個特征描述子的聚類）。BRIEF和旋轉BRIEF都具有很高的初始特征值，也提供了二值比較結果的相關性------更重要的是這些信息分布在前10-15個主成分上。旋轉BRIEF具有明顯的很低的方差，但是特征值也很低，那么區別就不明顯。很明顯，BRIEF依賴于關鍵點的隨機方向來獲取更好的性能。圖5所示旋轉BRIEF在有效數據和無效數據的距離上的效果。對旋轉BRIEF，外輪廓向左平移，與內輪廓有重疊。
4.3二值特征
為了使steered BRIEF方差增大，減少二值比較結果的相關性，我們開發了一種方法來選擇一組二值比較結果。一種策略是使用主因分析法或減少其他維度的方法，從二值比較結果的數據組開始，選出256個有大方差，不關聯（通過大量數據訓練）的新特征。既然新特征是由大量二值結果組成，可能計算效率要比steered BRIEF要低。那么，我們就搜索所有可能的二值結果尋找那些大方差（均值接近0.5），且不相關的二值。
具體方法：首先從PASCAL 2006圖像數據集里提取300K個關鍵點建立訓練數據。通過畫31x31的像素區塊，枚舉所有可能的二值結果。每個測試結果都是一對5x5的圖像區塊子窗口。如果圖像區塊的寬度wp=31，測試子窗口的寬度wt=5，那么就有N=（wp-wt）2個可能的子窗口。我們從里面再作配對，那么我們就有?二值結果。我們去掉那些重疊的結果，那么我們就有M=205590可能的結果。
具體算法：
- 針對所有的訓練圖像區塊，對每個關鍵點做測試。
- 根據測試結果到均值為5的距離進行排序形成向量T。
- 貪婪算法搜索：
- 將第一個測試結果放入向量R，并將其從向量T中移除。
- 在T里面進行下一次測試，比較R里面所有的結果。如果絕對相關值大于閾值，就丟掉；反之就添加到R。
- 重復上面的步驟，直到R里面有256個測試結果。如果少于256個結果，就提高閾值，然后再試。
在均值為0.5左右的一組不相關的測試結果中進行貪婪搜索。結果稱為rBRIEF。rBRIEF在方差和相關性特性上有明顯增強，如圖4所示。PCA的特征值也比較高，但它們下降沒那么快。如圖6所示，算法產生的高方差二值結果。左圖里未經訓練的比較結果里有很明顯的垂直趨向，高度相關；經過訓練的結果表現出更好的多樣性和更低相關性。
4.4評估
我們評估ORB，將oFAST和rBRIEF融合，使用兩個數據集：一組圖像經過平面旋轉和高斯去噪聲，另一組是不同視角下真實世界的紋理化平面圖像。對每幅圖像，我們都計算oFAST關鍵點和rBRIEF特征，每幅圖像500個關鍵點。對每幅圖像（融合旋轉或真實世界視角轉換），我們執行暴力搜索查找最好匹配。根據正確匹配的百分比提供測試結果，而不是旋轉角度。
圖7 是融合高斯噪聲的數據集測試結果。標準BRIEF算法在10度左右急劇下降。SIFT性能優于SURF，由于Haar小波成分在45度角的地方有很大不同。ORB性能最好，優于70%有效數據模型。
與SIFT不同，ORB不受高斯噪聲影響。如果對比有效數據和噪聲，SIFT在噪聲增加5的情況下有10%的緩慢下降。如圖8所示，ORB也有所下降，但下降幅度更小。
為了測試ORB對實時圖像的性能，我們用了兩組圖像數據集，一組是室內圖像有高度紋理化的雜志放在桌子上，如圖9所示，另一組是室外環境。數據集有尺度、視角、光線變化。
測試之后，我們得到了ORB和SIFT，SURF的性能對比。測試方法如下：
- 選擇參考視圖V0.
- 對所有視圖Vi，查找單值映射Hi0，Vià V0.
- 以Hi0作為基準，用于特征描述子匹配，對比SIFT,SURF和ORB。
?
?在室外環境下，ORB性能優于SIFT和SURF。室內環境，性能一樣；論文6提到SIFT斑點偵測的關鍵點在涂鴉類型的圖像上性能更好。
5.? 二值特征不同尺度匹配
大量圖像數據集下，ORB最近鄰搜索匹配性能優于SIFT/SURF。ORB的評價標準之一是方差，它使得鄰近搜索更有效率。
5.1rBRIEF局部敏感哈希方法
rBRIEF是二值模式，所以我們選擇局部敏感哈希方法作為最近鄰快速查找。在局部敏感哈希方法中，點被存儲到幾個哈希表里，被哈希到不同桶里。給定一個要檢索的特征描述子，提取匹配的桶，用暴力匹配的方法匹配里面的元素。這個方法的作用在于將一個在超大集合內查找相鄰元素的問題轉化為了在一個很小的集合內查找相鄰元素的問題，在給定哈希表的情況下查找成功概率比較高。
對于二值特征，哈希表示超大集合的一個子集：哈希表對應的桶包含了相同的特征描述子，它們在同一個子集里。它們的距離用漢明距離計算。
我們增強了多點探測局部敏感哈希方法，來增強傳統局部敏感哈希方法，哈希映射變換后，原始空間中相鄰的數據落入相同的桶內，那么在該數據集合中進行近鄰查找就變得容易了，我們查找特征描述子落入的相鄰的桶。然而，這可能需要確認更多的匹配，需要的表的數量少一些，更長的子集，因此可以用小一點的桶。
5.2關聯與分層
rBRIEF增強了局部敏感哈希方法的速度，它將哈希表映射的桶分得更平均：二值結果的關聯性更小，哈希方法能夠更好地劃分數據。如圖10所示，與steered BRIEF和BRIEF相比，哈希桶平均更小。
5.3評估
我們比較了具有kd樹的rBRIEF LSH和采用FLANN的SIFT特征描述子的性能。我們基于PASCAL 2009數據集訓練了不同的特征描述子，測試了仿射變換后的圖像。
我們的多點探測局部敏感哈希方法采用二值數據加速了對哈希查找表的鍵值搜索。它也可以用來計算兩個特征描述子的漢明距離。
圖11對比了SIFT kd樹（SURF是一樣的）和rBRIEF LSH的速度和精度。圖像數據庫里面超過50個特征描述子的時候就會有一個成功的匹配圖像。我們發現LSH比kd樹快，主要是由于距離計算上的簡化和加快。LSH對精度的調整也有彈性，可以通過特征詞袋方法來獲得，如論文21,27。我們也發現steered BRIEF由于不平均的哈希桶速度更慢。
6.? 應用
6.1對比測試
ORB的速度在標準CPU上的計算效率更高。ORB采用oFAST特征偵測和rBRIEF特征描述，它們在5個圖像尺度上分別計算，尺度因子是 。我們采用局部差值方法10去1。
ORB系統運算時間劃分如下表所示，典型的圖像幀的分辨率是640x480。代碼在單線程Intel i7 2.8GHz處理器上處理。
?
ORB計算5個尺度下的2686張圖像，42秒內偵測計算了超過2x106個特征點。相同尺度的1000個特征點的對比測試如下：
?
ORB比SURF快一個數量級，比SIFT快兩個數量級。
6.2紋理化的目標物體偵測
rBRIEF物體識別的方法：先偵測oFAST特征和rBRIEF特征描述子，將它們與數據庫匹配，然后執行PROSAC和EPnP算法得到一個位姿估計。
6.3嵌入式系統特征追蹤
通過當前幀與之前的圖像幀匹配實現手機上的追蹤。關鍵幀里的特征描述子，包含平面物體表面紋理。ORB處理新進的圖像，通過暴力搜索匹配特征描述子。通過PROSAC適配單映射H。
實時的手機圖像特征追蹤在比較小的分辨率上運行（比如120x160），特征點非常少，如論文30所示。ORB可以以7Hz幀率640x480分辨率運行在1GHz ARM處理器512MB RAM系統上。在Andriod系統上移植OpenCV。下面是每個圖像400個特征點的對比測試：
7.? 結論
我們通過OpenCV 2.3實現了ORB。ORB具有尺度不變特性。
參考文獻
[1] M. Aly, P. Welinder, M. Munich, and P. Perona. Scaling object recognition: Benchmark of current state of the art techniques. In First IEEE Workshop on Emergent Issues in Large Amounts of Visual Data (WS-LAVD), IEEE International
Conference on Computer Vision (ICCV), September 2009. 6
[2] H. Bay, T. Tuytelaars, and L. Van Gool.?Surf: Speeded up robust features. In European Conference on Computer Vision,May 2006. 1, 2
[3] M. Brown, S. Winder, and R. Szeliski.?Multi-image matching using multi-scale oriented patches. In Computer Vision and Pattern Recognition, pages 510–517, 2005. 2
[4] M. Calonder, V. Lepetit, and P. Fua.?Keypoint signatures for fast learning and recognition. In European Conference on Computer Vision, 2008. 2
[5] M. Calonder, V. Lepetit, K. Konolige, P. Mihelich, and P. Fua. High-speed keypoint description and matching using dense signatures. In Under review, 2009. 2
[6] M. Calonder, V. Lepetit, C. Strecha, and P. Fua.?Brief: Binary robust independent elementary features. In In European Conference on Computer Vision, 2010. 1, 2, 3, 5
[7] O. Chum and J. Matas.?Matching with PROSAC - progressive sample consensus.?In C. Schmid, S. Soatto, and C. Tomasi, editors, Proc. of Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pages 220–226,Los Alamitos, USA, June 2005. IEEE Computer Society. 7
[8] M. Everingham. The PASCAL Visual Object Classes Challenge 2006 (VOC2006) Results. http://pascallin.ecs.soton.ac.uk/challenges/VOC/databases.html. 4
[9] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2009 (VOC2009) Results.http://www.pascalnetwork.org/challenges/VOC/voc2009/workshop/index.html.6, 7
[10] A. Gionis, P. Indyk, and R. Motwani.?Similarity search in high dimensions via hashing. In M. P. Atkinson, M. E. Orlowska,P. Valduriez, S. B. Zdonik, andM. L. Brodie, editors,VLDB’99, Proceedings of 25th International Conference onVery Large Data Bases, September 7-10, 1999, Edinburgh,Scotland, UK, pages 518–529. Morgan Kaufmann, 1999. 6
[11] C. Harris and M. Stephens.?A combined corner and edge detector. In Alvey Vision Conference, pages 147–151, 1988. 2
[12] Y. Ke and R. Sukthankar. Pca-sift: A more distinctive representation for local image descriptors. In Computer Vision and Pattern Recognition, pages 506–513, 2004. 2
[13] G. Klein and D. Murray.?Parallel tracking and mapping for small AR workspaces. In Proc. Sixth IEEE and ACM International Symposium on Mixed and Augmented Reality (ISMAR’07), Nara, Japan, November 2007. 1
[14] G. Klein and D. Murray.?Improving the agility of keyframebased SLAM. In European Conference on Computer Vision,2008. 2
[15] G. Klein and D. Murray.?Parallel tracking and mapping on a camera phone. In Proc. Eigth IEEE and ACM International Symposium on Mixed and Augmented Reality (ISMAR’09),Orlando, October 2009. 7
[16] V. Lepetit, F.Moreno-Noguer, and P. Fua.?EPnP: An accurate O(n) solution to the pnp problem. Int. J. Comput. Vision, 81:155–166, February 2009. 7
[17] D. G. Lowe.?Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision,60(2):91–110, 2004. 1, 2
[18] Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li.?Multi-probe LSH: efficient indexing for high-dimensional similarity search. In Proceedings of the 33rd international conference on Very large data bases, VLDB ’07, pages 950–961. VLDB Endowment, 2007. 6
[19] M. Martinez, A. Collet, and S. S. Srinivasa. MOPED:?A Scalable and low Latency Object Recognition and Pose Estimation System. In IEEE International Conference on Robotics and Automation. IEEE, 2010. 7
[20] M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP, 2009. 6
[21] D. Nist′er and H. Stew′enius.?Scalable recognition with a vocabulary tree. In CVPR, 2006. 2, 6
[22] P. L. Rosin.?Measuring corner properties. Computer Vision and Image Understanding, 73(2):291 – 307, 1999. 2
[23] E. Rosten and T. Drummond.?Machine learning for highspeed corner detection. In European Conference on Computer Vision, volume 1, 2006. 1
[24] E. Rosten, R. Porter, and T. Drummond. Faster and better:A machine learning approach to corner detection. IEEE Trans. Pattern Analysis and Machine Intelligence, 32:105–119, 2010. 1
[25] S. Se, D. Lowe, and J. Little. Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks.International Journal of Robotic Research, 21:735–758, August 2002. 1
[26] S. N. Sinha, J. michael Frahm, M. Pollefeys, and Y. Genc.Gpu-based video feature tracking and matching. Technical report, In Workshop on Edge Computing Using New Commodity Architectures, 2006. 1
[27] J. Sivic and A. Zisserman.?Video google: A text retrieval approach to object matching in videos. International Conference on Computer Vision, page 1470, 2003. 2, 6
[28] N. Snavely, S. M. Seitz, and R. Szeliski. Skeletal sets for efficient structure from motion. In Proc. Computer Vision and Pattern Recognition, 2008. 1
[29] G.Wang, Y. Zhang, and L. Fei-Fei. Using dependent regions for object categorization in a generative framework, 2006. 6
[30] A. Weimert, X. Tan, and X. Yang. Natural feature detection on mobile phones with 3D FAST. Int. J. of Virtual Reality, 9:29–34, 2010.
翻譯參考資料：
計算機視覺目標檢測的框架與過程??? blog.csdn.net/zouxy09/article/details/7928771
學習OpenCV——ORB & BRIEF（特征點篇）&Location? blog.csdn.net/yangtrees/article/details/7533988
學習OpenCV——Surf（特征點篇）&flann????? blog.csdn.net/yangtrees/article/details/7482960
structure from motion????? blog.csdn.net/sway_2012/article/details/8036863
基于稀疏矩陣的k近鄰（KNN）實現??????? blog.csdn.net/zouxy09/article/details/42297625
對論文Learning 3-D Scene Structure from a Single Still Image的理解?? 用單張2D圖像重構3D場景??? blog.csdn.net/zouxy09/article/details/8083553
Bundler: Structure from Motion (SfM) for Unordered Image Collections?????www.cs.cornell.edu/~snavely/bundler/
Fast Approximate Nearest Neighbor Search
http://opencv.itseez.com/2.4/modules/flann/doc/flann_fast_approximate_nearest_neighbor_search.html?highlight=flann#fast-approximate-nearest-neighbor-search
Harris角點檢測http://www.cnblogs.com/doucontorl/archive/2011/01/02/1924157.html
Harris角點?????www.cnblogs.com/ronny/p/4009425.html?utm_source=tuicool&utm_medium=referral
Opencv學習筆記（五）Harris角點檢測??? blog.csdn.net/crzy_sparrow/article/details/7391511
更多的資源與參考：
Photo Tourism: Exploring Photo Collections in 3D???? phototour.cs.washington.edu/Photo_Tourism.pdf
Modeling the World from Internet Photo Collections????? phototour.cs.washington.edu/ModelingTheWorld_ijcv07.pdf
理解矩陣????? blog.csdn.net/zouxy09/article/details/8004724
數學之美番外篇：平凡而又神奇的貝葉斯方法????? blog.csdn.net/zouxy09/article/details/8005109
計算機視覺的一些測試數據集和源碼站點??????? blog.csdn.net/zouxy09/article/details/8768561
計算機視覺、機器學習相關領域論文和源代碼大集合--持續更新……??? blog.csdn.net/zouxy09/article/details/8550952
圖像處理和計算機視覺中的經典論文??????? blog.csdn.net/zouxy09/article/details/8233198
計算機視覺領域的一些牛人博客，研究機構等的網站鏈接????? blog.csdn.net/zouxy09/article/details/8233094
總結
以上是生活随笔為你收集整理的SLAM前端 ---------特征提取之ORB（ORB与SIFT与SURF）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 微信网名内涵
- 下一篇： SLAM之特征匹配(二)————RANS