本文結構
為了看懂ORB特征提取算法，來看了BRIEF算法的原文，并查看了OpenCV中BRIEF的相關實現，來驗證論文的解讀正確與否。
BRIEF論文解讀
摘要
用二進制串描述局部特征，好處有二：一是很少的bit就能描述獨特的性質；二是可以用漢明距離計算兩個二進制串之間的特征，計算速度快。在實際應用中的好處是：算的準；算的快；省內存。
BRIEF特征的建立和用于匹配，都很快。性能測試表明，BRIEF比SURF和U-SURF快，準確度差不多。
Introduction
經驗表明，用256甚至128個bit表示一個BRIEF特征就夠用了。算的快，省內存，適合實時計算的應用，比如SLAM（省計算）或者三維重建（省存儲）。
先前一些算法，先計算浮點型特征描述向量，再轉化為二進制表示。這樣的算法，匹配很快，但是前期還是慢。
BRIEF是在keypoint周邊隨機取點對進行灰度計算，直接得到二進制特征描述向量。
Method
圖像patch先做平滑操作，再根據檢驗結果(response of test，比如t檢驗，即t-test)生成二進制描述符。
創建這樣的特征向量，需要考慮的是高斯模糊的模糊核kernel（即$\sigma$）值的選取，以及點對$(\vecx_1, \vecx_2)$的選取，其中$\vec x_1=(u,v)^T$_
模糊的作用是消噪。
識別率的實驗表明，sigma取2的效果最好，對應的高斯窗口為9x9規格。
論文提出了５種選擇[x,y]的方式，并根據識別率進行實驗，發現第二種性能最好：(X, Y) ∼ i.i.d. Gaussian(0, (1/25)S^2)
注意：這里的高斯分布容易引起混淆，詳細講是：每次t-檢驗中，要選取的兩個點為(X,Y)，其中X=(u1,v1)^T，Y=(u2,v2)^T，(X,Y)~N(0, (1/25)S^2)
實際測試發現sigma^2=(1/25)S^2能有最高的識別率。
我還是不明白，空域中到底要怎么選點？
看了OpenCV中的實現發現，所謂隨機選點，只是最開始的一個patch是隨機選點，并且這個選出來的點的順序要記錄下來給后面所有的patch使用。并且，這些選出的點并不是真正的、純粹的隨機，而是服從上述高斯分布的。
為什么patch在t-檢驗前要做平滑？
因為論文原文提出的t-檢驗，每次檢查的是兩個像素點。單個像素點是噪聲敏感的。因此要做平滑操作。（而平滑操作比較耗時，這也為后來的優化做了伏筆。Calonder等人又于2011年提出采用盒狀濾波器的處理方法來代替高斯平滑處理方法）
實驗和結果
在6種圖片上，分別使用SURF、U-SURF、BRIEF-16、BRIEF-32、BRIEF-64進行測試，發現BRIEF-32除了在涂鴉(Graffitti)上表現不如SURF和U-SURF好之外，其他圖片序列上基本都是最好的。而且顯然BRIEF-32也和BRIEF-64差不了太多，并且也基本勝過SURF和U-SURF。
上述比較過程中，keypoint是用的SURF的keypoint。實際上SURF的keypoint會吃掉BRIEF帶來的速度提升，一般用其他更快的keypoint檢測子，比如CenSurE(Center Surround Extremas Realtime Feature Detector and Matching這篇論文提出。也可以考慮FAST等算法，FAST:Rosten, E., Drummond, T.: Machine Learning for High-Speed Corner Detection. In: European Conference on Computer Vision）。但是，換用了更快的檢測子，能保證識別率嗎？
同樣的測試圖片，對比分別用SURF和CenSurE檢測的keypoint然后接上BREIF描述符，測量匹配的準確度，CenSurE在大多數情況下比SURF準確率還高；個別情況稍低于SURF。
旋轉角的討論
BRIEF沒有專門考慮旋轉的問題。那么就從０°～３６０°進行旋轉測試吧。
發現小范圍（0-15°）內，BRIEF識別率最高，其次是U-SURF,然后是SURF和o-BRIEF;
角度再大一點(15°～30°），BRIEF和U-SURF準確率迅速下降到０，角度再大，則這兩個算法的識別率保持為０．而SURF和o-BRIEF這兩個考慮旋轉方向的算法，始終能保持大于60%的準確率，而且在90°的倍數角度處，識別率有極大值。
這里的o-BRIEF是：用SURF算出旋轉角度，然后用BRIEF按照這個角度旋轉再進行描述的一個算法。
這里的BRIEF都是BRIEF-32。
o-BRIEF和SURF的識別率，在旋轉角度從０到１８０度變化時，幾乎是重合的。
實驗中還測量了SURF和BRIEF在description和matching兩個階段的對比，發現特征描述的計算時間上相差35-40倍，精確鄰近匹配的計算時間上相差3~10倍。
通常U-SURF比SURF快上3倍左右。
當前BRIEF的大多數時間消耗在高斯模糊操作上。基于積分圖像的近似平滑操作，能加速。
結論
BRIEF算的快（二進制描述，漢明距離匹配），算的準（這很重要），省內存（遠少于SIFT和SURF的描述符位數）。
下一步考慮方向和尺度。使用快速的方向估測子(fast orientation estimators),沒理由不相信速度不快！
OpenCV中的實現
對一個keypoint（及其所在區域，稱為patch），在生成其描述符之前，BRIEF要先對patch做高斯平滑，這會消耗時間。
OpenCV在具體的實現上，結合了平滑和積分圖像的思想，將t-檢驗中原本的兩個點p1、p2,替換成p1、p2各自一個模板區域內的像素之和，這個模板區域以p1或p2為左上角定點。也就是，從原來的單獨兩個點的像素值比較，換成了兩個模板區域內的像素和的比較，參與比較的點多了，降低了噪聲的影響。但是計算效率呢？沒關系，因為使用了積分圖像，因此計算時間是O(4)=O(1)的：
inline int smoothedSum(const Mat& sum, const KeyPoint& pt, int y, int x)
{
static const int HALF_KERNEL = BriefDescriptorExtractor::KERNEL_SIZE / 2;
int img_y = (int)(pt.pt.y + 0.5) + y;
int img_x = (int)(pt.pt.x + 0.5) + x;
return sum.at<int>(img_y + HALF_KERNEL + 1, img_x + HALF_KERNEL + 1)
- sum.at<int>(img_y + HALF_KERNEL + 1, img_x - HALF_KERNEL)
- sum.at<int>(img_y - HALF_KERNEL, img_x + HALF_KERNEL + 1)
+ sum.at<int>(img_y - HALF_KERNEL, img_x - HALF_KERNEL);
} 這里的積分圖像的使用，其實也就是盒狀濾波器：指定區域內的像素和，或者像素和的歸一化結果；也就是一個元素全為1，再乘以一個系數的矩陣。
當然，盒狀濾波器在實現的過程中可以有更快的實現方式，即分別指定一維的行內濾波器和列內濾波器，每個濾波器都是計算整個行或列的元素和：先逐列掃描，每列計算元素和，并存儲到臨時數組中；再對臨時數組使用行濾波器進行求和，這樣就得到一個區域的盒狀濾波結果了。
文章列表
留言列表
