?

首先，ORB算法來自于OpenCV Labs，相比于SIFT和SURF，ORB在使用中不必擔心專利的問題。但同時ORB在保證了一定性能的條件下做到了高效。在論文《ORB: An efficient alternative to SIFT or SURF》2011中，ORB在特征點檢測和描述子生成方面都做了改進，結果是ORB is at two orders of magnitude faster than SIFT, an order of magnitude faster than SURF,即可以比SIFT的速度快100倍，比SURF快10倍。這樣就不必借助GPU就可以實現算法的加速。作者還在智能手機上借助OpenCV port for Android進行了實驗。

ORB之所以快，是因為站在了巨人的肩膀上。ORB的特征點檢測和特征點的描述子分別使用了速度最快的FAST算法和BRIEF算法，但是又都針對他們的缺點進行了改善。對于FAST，使用圖像金字塔方法實現了尺度不變性；使用Harris角點濾波器剔除檢測到的邊緣并對檢測到的特征點評級（FAST算法對邊緣敏感Large responses），可以挑出表現最好的特征點。FAST的一大缺陷是沒有旋轉不變性，在SIFT中通過特征點鄰域的梯度直方圖的統計得到方向信息，SURF則是利用Haar小波在鄰域內進行近似計算。ORB的作者在Rosin分析各種角點方向的方法的基礎上，選擇了質心的方法。特征點的鄰域是一個patch，那么patch一定會有一個質心(intensity weighted centroid),特征點和質心一般不會重疊，即有一個offset，特征點到質心的連線構成的矢量就是該特征點的方向向量。至于patch到底是多大，文中沒有明說，但我個人理解應該是和FAST算法時使用的半徑大小是一致的。ORB作者在使用FAST算法時使用的是FAST-9，即半徑大小是9個像素。

質心是由矩計算得到的，質心?

矩的計算公式：?

為了使得方向不變性魯棒性更好，作者在計算矩的公式中x,y不是取相對于圖像原點的坐標，而是相對于特征點的坐標，x，y的范圍是[-r,r]。當質心C的模趨于0，即質心逼近與特征點，這種求特征點的方法變得不穩(wěn)定，但是這種情況很少出現。（這里的理解不知道是否正確）。

在描述子上，ORB主要使用的是BRIEF，但是BRIEF對于旋轉缺乏不變性，即在旋轉前后特征點的描述子是不同的。文中首先提出的方法和SIFT一樣，是借助于之前得到的主方向將特征點周圍的鄰域旋轉到主方向的方向上，這樣在其中統計梯度方向直方圖就會和旋轉之前一致。文中把這種方法叫steer BRIEF，但是BRIEF中需要注意的是即便旋轉到了主方向，BRIEF前后在特征點周圍的patch按照分布函數選擇的tests還是會不一樣，所以steer BRIEF直接使用旋轉之前選擇的tests坐標構成的矩陣與旋轉矩陣相乘，得到旋轉之后的tests。為了加快速度，steer ORB將角度離散化（間隔為12degrees），提前計算出了一個查找表。

??????????????????????????????????????????????????????????????????????????? ?

?????????????????????????????????????????????????????????????????????????????

這樣，只要視角角度與theta一致，就可以直接得到tests，進而得到二進制描述子。

但是steer BRIEF改變了BRIEF原有的幾個優(yōu)良特性：1.BRIEF的二進制描述子方差大。2. BRIEF的二進制描述子的均值為0.5。先來解釋一下為什么方差和均值有這樣的特性，并且為什么這樣的特性是優(yōu)良的。首先，這些對于一個特征點的長度為n的二進制01比特串，比特之間可以看作是獨立同分布的二項分布。那么它的方差=np(1-p)=n(-p^2+p),這是一個凸函數，p=0.5時取最大值，對于單個bit，方差最大可以達0.25；均值=np，但既然作者說均值是0.5，應該指的是每一位比特的均值。方差大，意味著01更分散，01的位數是差不多的，也就是tests更加隨機。原文的話是High variance makes a feature more discriminative, since it responds differentially to inputs.我理解的inputs是由tests得到的點對，比較大小進而由判斷條件得到0或者1，因為方差大，每一位bit的輸出的0,1可能性是一樣的，所以最終的二進制串更加獨特。方差的特性與均值相關，論文中就均值做了統計，畫出了幾種描述子方法的直方圖：

對100k個特征點，基本的BRIEF方法采取了典型的高斯分布，得到256bits的描述子。對每一個特征點，bit mean=number of 1/256.可以看到BRIEF算法的均值更接近于0.5，Steered BRIEF失去了均值為0.5的特性，而接近于均勻分布。rBRIEF是對Steered BRIEF的改進，在保留了旋轉不變的同時也保留均值接近0.5的特性。文中作者提到了另外一種理解的角度：有了方向信息的描述子因為更加歸一化(more uniform appearance)而均值才更加分散。

描述子還應該有的一個重要的特性就是它的tests之間是無關的。這個特性使得不同位的比特之間是獨立的，互不影響的，每個點對都對描述子做出了貢獻，我理解這樣構成的描述子才更穩(wěn)定，因為描述子包含了更多的鄰域信息。為了比較三種描述子方法的這一特性，論文中借助了PCA主成分分析：

圖中畫出了100k個特征點的描述子構成的矩陣的前40個最大的特征值，由這40個特征值的大小連成了曲線。特征值越大，說明描述子的信息越集中在少數的主成分中。Steered BRIEF的特征值更小，意味著方差更小（不太懂這個關系），所以特征點之間的區(qū)分度更低。

Steered BRIEF中特征點的與outliers的距離的均值更小，但是與inliers的重疊也更大。

于是，繼續(xù)改進，我們的目標不僅是使得描述子對旋轉不變，還要有大方差，0.5的均值，在tests之間還要保證低相關性，這就是rBRIEF方法。一個思路是繼續(xù)使用PCA，這也在SIFT基礎上被使用過，可以從高維向量中提取出互不相關的特征向量，從而減少了冗余的信息。但是，二進制tests的空間過大，不便使用PCA，且為了得到256bits大小的無關的描述子，我們就必須在最初找到更高維的描述子，這就反而降低了效率。所以我們最好可以直接找到不相關的tests。文獻21,27使用offline clustering找到不相關的examplars。在ORB論文中，在所有可能的二進制tests中貪婪查找，找到滿足三個條件的tests。

初始的tests有205590個，先按照其均值接近于0.5的程度進行排序（保證均值，進而保證高方差），挑選均值最接近于0.5的放入集合R中，再挑選下一個均值最接近0.5的test，并且求與R中的test的相關性，如相關性小于閾值，才將其加入R中，這樣就保證了低相關性。文章將這種由貪婪算法獲得的tests稱為learned tests，將改進之前的算法稱為unlearned tests，下圖是二者的對比。

左圖是改進之前的算法，首先左圖有很多接近豎直的點對構成的連線，表明了tests之間有很多相關性。顏色表示了每一個test與其余tests的最大相關值，在右圖中紫色更多，也表明改進之后的算法中tests的相關性更低。

oFAST和rBRIEF算法組合構成了ORB算法。使用了兩種數據集進行測試。一種是添加了高斯噪聲的in-Plane旋轉圖像，一種是真實世界中從不同視角獲得的Highly-textured圖像。對reference image和test image都提取500個特征點，然后使用暴力匹配brute-force matching尋找最佳對應點。比較rBRIEF、SIFT、SURF的Percentage of inliers，BRIEF在10度就開始急劇下降，SIFT優(yōu)于SURF，SURF由于haar小波分解，以45度為周期呈現規(guī)律性的起伏。ORB抗噪性也優(yōu)于SIFT。對于real-world images，又分別使用了作者自己的indoor數據集和outdoor，在outdoor dataset中，ORB優(yōu)于SIFT和SURF，indoor set中也近似這樣。文獻6表明SIFT在graffititype images中表現更好。

在尋找最近鄰NN點的時候，作者使用了multi-probe LSH局部哈希來提高效率。哈希方法分為離線建立索引和在線查找兩部分。傳統哈希方法是將相同的數據映射到相同的bucket中，局部哈希是近似最近鄰查找ANN的一種，它將兩個距離相近的數據也以很大的概率映射到相同的bucket中，根據距離的度量方式的不同又可以選取對應的映射函數。實驗表明LSH比通過FLANN構建的特征點的kd樹還要快。

使用Python3和OpenCV庫實現ORB算法。參考的是鏈接7簡書中的代碼，需要注釋的是Python的縮進。之前沒怎么接觸Python，在學習的過程中順便對代碼做了一些注釋。

#!/usr/bin/env.python # coding=gbk 支持中文注釋 import numpy as np import cv2 img1=cv2.imread("beaver.png",0) img2=cv2.imread("beaver_xform.png",0)#定義函數 def drawMatches(img1, kp1, img2, kp2, matches):rows1=img1.shape[0]#height(rows) of imagecols1=img1.shape[1]#width(colums) of image#shape[2]#the pixels value is made up of three primary colorsrows2=img2.shape[0]cols2=img2.shape[1]#初始化輸出的新圖像，將兩幅實驗圖像拼接在一起，便于畫出特征點匹配對out=np.zeros((max([rows1,rows2]),cols1+cols2,3),dtype='uint8')out[:rows1,:cols1] = np.dstack([img1, img1, img1])#Python切片特性，初始化out中img1，img2的部分out[:rows2,cols1:] = np.dstack([img2, img2, img2])#dstack,對array的depth方向加深for mat in matches:img1_idx=mat.queryIdximg2_idx=mat.trainIdx(x1,y1)=kp1[img1_idx].pt(x2,y2)=kp2[img2_idx].ptcv2.circle(out,(int(x1),int(y1)),4,(255,255,0),1)#藍綠色點，半徑是4cv2.circle(out, (int(x2) + cols1, int(y2)), 4, (0, 255, 255), 1)#綠加紅得黃色點cv2.line(out, (int(x1), int(y1)), (int(x2) + cols1, int(y2)), (255, 0, 0), 1)#藍色連線return out# 檢測器。ORB 直接換成AKAZE也可以，KAZE需要將BFMatcher中漢明距離換成cv2.NORM_L2 detector = cv2.ORB_create()kp1 = detector.detect(img1, None) kp2 = detector.detect(img2, None) kp1, des1 = detector.compute(img1, kp1)#計算出描述子 kp2, des2 = detector.compute(img2, kp2)bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)#暴力匹配 matches = bf.match(des1, des2) img3 = drawMatches(img1, kp1, img2, kp2, matches[:50])#找到50個匹配對cv2.imwrite("orbTest.jpg", img3) cv2.imshow('orbTest', img3) cv2.waitKey(0)

?

Reference：

見過的介紹ORB最清楚的博文https://blog.csdn.net/yirant7/article/details/51332881

大神一步步教你讀懂ORB算法https://blog.csdn.net/fsfengqingyangheihei/article/details/73572856

OpenCV-Python Tutorials：https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_orb/py_orb.html

源碼解析https://www.cnblogs.com/wyuzl/p/7856863.html

ORB算法介紹圖四https://blog.csdn.net/lhanchao/article/details/52612954

https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_orb/py_orb.html

簡書https://www.jianshu.com/p/5083f8d75439

總結

以上是生活随笔為你收集整理的ORB论文研读与代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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