基于FAST和BRIEF的圖像匹配算法

周莉莉，姜 楓

（1.南京理工大學 泰州科技學院 電子電氣工程學院，江蘇 泰州225300；2.南京理工大學 泰州科技學院 計算機科學與技術系，江蘇 泰州225300）

0 引 言

圖像匹配的一般步驟分為三步：首先從圖像中提取“興趣點”，即特征點；然后使用特定的描述器對提取的特征點進行特征描述；最后根據特征描述器進行圖像匹配［1－5］。

特征點提取的算法最早使用的是Moravec角點檢測器、Harris角點檢測器等［6］，角點檢測器不僅能檢測圖像中的角點，而且可以檢測圖像中像素梯度較大的點。然而Har－ris角點檢測器對圖像的尺度敏感，不能用于匹配不同尺寸的圖像。Lowe等提出了一種基于尺度不變性的特征提取方法［7］，稱為尺度不變特征變換 （scale invariant feature transform，SIFT）方 法，SIFT 算 法 中 采 用DOG （difference of Gaussian）算子近似LOG （Laplacian of Gaussian）算子求取圖像中特征點，并據此構建梯度直方圖判斷局部圖像主方向，以實現尺度和旋轉不變性。在SIFT 算法的基礎上，又改進形成了PCA－SIFT、GLOH （gradient location and orientation histogram）等算法。著名的SURF （speeded up robust features）算 法 是SIFT 算 法 的 快 速 實 現 版 本［8］，當中使用了快速Hessian檢測器簡化了復雜的DOG 計算，以快速定位特征點，其運算速度遠快于SIFT。最近，Rosten等提出了可用于實時系統進行特征提取的FAST （features from accelerated segment test）算法［9］，不 同于SIFT和SURF算法，FAST 通過直接計算圖像中心像素點和周圍像素點的關系即可找出圖像中的關鍵點，其運算速度遠快于SIFT 和SURF算法。

關于特征描述算法，最著名的當屬SIFT 特征描述器，它是利用關鍵點附近區域像素的梯度直方圖進行運算的，使用了128維的向量來描述圖像局部特征，雖然該算法區分度極高，但其計算、存儲復雜性高，不適用于實時場合。SURF特征描述器原理和SIFT 描述器基本相同，也是基于局部圖像的梯度直方圖計算，該描述器維數為64 維。Ke采用PCA 算法對特征向量維數進行壓縮，減少了計算復雜性和存儲量，但該描述器的區分度不如SIFT。GLOH 描述器也屬于SIFT 一類，其性能好于SIFT 描述器，但計算更為復雜。最近提出的BRIEF （binary robust independent elementary features）是一種高速的特征描述器［10］，使用二進制字符串描述特征。除了表述簡單之外，BRIEF 表述器的另一大優勢在于特征匹配時只需計算海明距離 （Hamming distance），運算速度遠快于最近鄰等算法。

本文提出的圖像特征匹配主要基于FAST 和BRIEF算法。FAST 算法用于提取圖像中的特征點，為了進一步提高提取速度，使用了簡化的特征測試模板；再將特征點附近的圖像片段使用BRIEF 算法進行特征描述，為了克服BRIEF自身不支持圖像旋轉的不足，利用強度質心的方法計算圖像片段的主方向，并據此對特征描述器進行旋轉，以達到旋轉魯棒性；最后通過計算特征描述器間的海明距離匹配圖像。

1 FAST算法及其改進

FAST 算法起源于SUSAN 算法，其原理描述如下：對于圖像中某個中心點p，使用Bresenham 畫圓法檢測以之為圓心、半徑為3.4像素的圓上16個像素點的強度值，如圖1所示，下文將該檢測模板稱作M16。測試準則為，在這16個點中，如果有N 個連續點的強度值均大于p 的強度值Ip加上閾值t，或均小于Ip－t，則認為p 是一個角點（即特征點）。為了加速角點檢測速度，可以取N 的值為12，這樣只需要先檢測圖1中1、5、9和13這4個點的強度值，如果p 為角點，則這4個點中至少有3個點的強度值均大于Ip＋t或者均小于Ip－t。只有在上述檢測通過后才需要檢測剩余的12個點。這種方法雖然方便，但只適用于N 為12的情況，為了開發一個更為普適的算法，FAST算法中引入了機器學習方法。第一步，針對特定的N 和閾值t，使用上述分割測試準則從圖像集中檢測出所有角點，這個過程中需要檢測每個點周圍的所有16個點，將檢測過的圖像作為訓練樣本。第二步，利用第一步得到的訓練樣本，根據信息增益最大原則使用ID3算法，訓練得到可以對角點進行正確分類的決策樹。訓練完成后使用決策樹對圖像中的點進行分類，得到角點和非角點。

圖1 FAST 算法角點檢測模板

FAST 算法中推薦使用如圖1所示的M16模板，相比SIFT 和SURF算法而言其特征點檢測速度得到了極大提升。文獻 ［11］中指出，可以選擇不同的模板進行角點檢測。本文在M16模板的基礎上進行簡化，在角點檢測使用3種模板，如圖2所示。

圖2 角點檢測的3種模板

為了評估不同模板的角點響應效果，使用了如圖3所示的不同視角的圖片集進行測試。

圖3 不同模板角點響應實驗

圖4表示分別采用M16 （連續像素點數目N 分別為9，10，11），M12S，M12D 和M8模板對圖3所示的圖集進行角點檢測得到的效果。分析可發現，FAST 算法中使用的模板尺寸越大，得到的角點數也越多。在模板尺寸相同的情況下，N 值越大則生成的角點越少，且更接近真實角點位置，圖4 （a）、（b）在角點位置附件產生了多重響應，圖4 （c）產生的角點數少且更靠近真實位置。圖4 （f）中的檢測結果表明，M8模板的角點響應能力較強。在進行角點檢測時，根據Harris角點量［6］施加非最大約束 （non－maxi－mal suppression），以減少角點附近位置的多重響應。

圖4 不同模板的角點響應對比

此外，文中還對各種模板的算法運行時間進行比較。如表1 所示，FAST 算法比SIFT 和SURF 算法速度快很多，M16模板的FAST 算法運行時間基本相當，隨著模板尺寸的減少，算法運行時間呈逐步遞減趨勢，M8模板的運行時間約為M16模板運行時間的1/3左右。

表1 不同模板的角點檢測時間對比

2 BRIEF算法及其改進

BRIEF是一種圖像特征描述器，不同于SIFT 等基于局部圖像梯度直方圖的計算，BRIEF 算法在S×S 像素大小的圖像片段p 上定義了測試τ

式中：x，y——圖像片段p中的任意兩個像素點，p（x），p（y）——點x 和y 的強度值。接著，在圖像片段p中選擇n個點對 （x，y），定義一個二進制測試集，BRIEF描述器即為n維的比特字符串，定義如下

n 在實際使用時可以選擇128，256或512，對應描述器的長度分別為16字節，32字節和64字節，遠低于SIFT描述器的512字節 （128維實數）。

由于點對測試對噪聲非常敏感，因此在進行測試前需要對圖像進行平滑處理，文獻 ［10］中推薦使用高斯濾波器，并對不同的方差σ以及濾波窗口大小進行對比，得出方差為2，窗口大小為9×9比較合適。另外一個問題是如何在圖像片段p中選擇n 個點對，文獻 ［10］中給出了5種不同方案并通過實驗進行詳細比較，本文中選擇方案2，即 （X，Y）服從 （0，S2/25）的高斯分布。

BRIEF是一個高效的局部圖像特征描述器，其運算速度快、占用內存資源少，然而其缺陷在于對旋轉較敏感。本文采取的改進措施如下，在片段p中使用高斯分布選擇出n個點對

然后，將其根據特征點的主方向進行旋轉。計算特征點主方向使用強度質心 （intensity centroid）方法［12］，其原理是認為圖像片段主方向由其中心和質心間的偏移決定，圖像片段的矩定義為

式中：（x，y）——圖像中的像素點的坐標，I（x，y）——該點的強度值，為通過矩的計算可以得到質心

在中心和質心之間的向量方向決定了特征點的主方向

將選出的點對S 進行旋轉得到Sr＝RθS，其中Rθ為根據θ計算出的旋轉矩陣，接著在Sr上進行測試τ即可。

為了測試改進BRIEF算法的旋轉不變性，對測試圖像進行了人工旋轉并增加高斯噪聲，比較幾種常見算法。如圖5所示，SIFT 算法的旋轉不變性最優，BRIEF算法對旋轉最敏感，本文提出的改進BRIEF算法對抗旋轉能力略好于SURF算法。

圖5 各種算法旋轉不變性測試

3 實 驗

為了檢驗算法的有效性，分別使用人工合成圖像以及真實圖像數據庫對比SIFT、SURF、FAST＋BRIEF和本文算法。實驗在Windows 7和Visual Studio 2010環境下，使用OpenCV 2.2自帶的SIFT 和SURF算法進行測試。

3.1 算法旋轉不變性實驗

圖6顯示了在圖像上施加5%的高斯噪聲和在不同旋轉角度時特征匹配率的情況。由于標準的BRIEF算法不具備旋轉不變性，因此當旋轉角度大于20度時匹配率下降非常明顯。SIFT 算法使用梯度方向直方圖計算特征點旋轉方向，從實驗結果觀測，其算法特征匹配率最高，且穩定性能好。SURF算法是基于Haar小波響應的描述子，因此在旋轉角度為45度整數倍時性能下降最為明顯。本文算法比SIFT 算法匹配率略低，穩定性也較好，抗噪和抗旋轉能力都強于SURF算法。

圖6 各種算法在噪聲和不同旋轉角度下的匹配率對比

3.2 真實圖像匹配實驗

為了測試本文算法在實際圖像的運行效果，采用了如圖7 （a）所示的兩幅圖像，兩幅圖像中包括了尺度、旋轉和光照的變換，圖7 （b）是進行圖像匹配后得到的結果?？梢钥闯霰M管存在一些誤匹配，但總體匹配效果良好。

3.3 算法性能及運行時間實驗

圖像數據庫多種算法中使用標準測試庫，其下載地址為http：//www.robots.ox.ac.uk/～vgg/research/affine/，其中包含了8組不同的圖像，每組圖像包含了相同場景下的6張圖像，這些圖像涉及到圖像模糊、視角、旋轉、尺度、光照、壓縮等變化，以綜合測試算法的放射不變性能。實驗結果列在表2中。

表2 各種算法在真實圖像集的匹配率及時間

圖7 真實圖像匹配

實驗中，SIFT 算法采用5組金字塔，每組3層，采用128維向量描述特征，結果表明，該算法的平均匹配率最高，但是由于計算多尺度DOG 耗費了大量的運算時間，不適用于實時檢測。SURF算法采用64維的特征描述器，其匹配率較SIFT 稍差，但由于使用快速Hessian檢測代替了DOG 計算，整體運行時間比SIFT 算法快。FAST＋BRIEF算法采用普遍使用FAST9 角點檢測器，找到的特征數較多，BRIEF采用64位特征描述器，運行時間最短，但由于其對旋轉較敏感，匹配率不高。采用本文算法分別使用了3種不同模板，如表2參數一欄所示，其匹配率介于SIFT 算法和SURF算法之間，遠高于FAST＋BRIEF 算法，而由于增加了特征點方向計算，運算時間略有增加，但仍低于SIFT 和SUFR 算 法。

4 結束語

本文選擇FAST 算法作為圖像特征檢測器，使用BRIEF算法描述圖像局部特征。在此基礎上，對FAST 算法的模板進行改進，分別采用12點正方形、12點菱形、8點正方形模板，實驗結果表明改進模板的角點檢測器在保持角點響應能力的同時計算速度得到進一步提升。同時，為了解決BRIEF算法不支持旋轉的問題，通過強度質心的方法計算給特征點標注方向，使得特征描述器具有旋轉不變性。最后，通過對人工合成圖像以及標準測試圖像集的實驗，驗證本文算法和一些經典的算法相比，在各種視角、尺度、光照、壓縮變換等各種情形下，保持了和SIFT 算法近似的高匹配率，優于SURF 算法，而算法運行時間遠低于二者，是一種低計算量、性能強的特征匹配算法。

［1］FU Lisi，LIU Pengwei，LI Dandan.Improved moment invariant characteristics and object recognition ［J］.Computer Engineering and Applications，2012，48 （31）：183－185 （in Chinese）.［付立思，劉朋維，李丹丹.一種改進的不變矩特征與物體識別 ［J］.計算機工程與應用，2012，48 （31）：183－185.］

［2］HU Qiong，QIN Lei，HUANG Qingming.A survey on visual human action recognition ［J］.Chinese Journal of Computers，2013，36 （12）：2512－2524 （in Chinese）.［胡瓊，秦磊，黃慶明.基于視覺的人體動作識別綜述 ［J］.計算機學報，2013，36 （12）：2512－2524.］

［3］FAN bo，YANG Xiaomei，HU Xueshu.Super－resolution image reconstruction algorithms based on compressive sensing［J］.Journal of Computer Applications，2013，33 （2）：480－483 （in Chinese）. ［樊博，楊曉梅，胡學姝.基于壓縮感知的超分辨率圖像重建 ［J］.計算機應用，2013，33 （2）：480－483.］

［4］ZHANG Mingjie，KANG Baosheng.Modified object detection and automatic tracking method ［J］.Computer Engineering and Design，2014，35 （4）：1308－1311 （in Chinese）.［張明杰，康寶生.改進的目標檢測與自動跟蹤方法研究 ［J］.計算機工程與設計，2014，35 （4）：1308－1311.］

［5］JIAO Lilong，HAN Xie，LI Dingzhu.Improved image mosaic algorithm based on feature points matching［J］.Computer Engineering and Design，2014，35 （3）：918－922 （in Chinese）. ［焦麗龍，韓燮，李定主.改進的基于特征點匹配的圖像拼接融合算法［J］.計算機工程與設計，2014，35 （3）：918－922.］

［6］ZHANG Yong，JI Dongsheng.Improved Harris feature point detection algorithm ［J］.Computer Engeering，2011，37（13）：196－198 （in Chinese）. ［張永，紀東升.一種改進的Harris特征點檢測算法 ［J］.計算機工程，2011，37 （13）：196－198.］

［7］HANG Long，GUO Li，LI Yuyun.SIFT algorithm parallel implementation and application ［J］.Computer Engineering and Applications，2010，46 （20）：56－59 （in Chinese）. ［韓龍，郭立，李玉云.SIFT 算法的并行實現及應用 ［J］.計算機工程與應用，2010，46 （20）：56－59.］

［8］SHOU Zhaoyu，OUYANG Ning，ZHANG Huajun，et al.Research on real－time video stitching based on SURF and dynamic ROI［J］.Computer Engineering and Design，2013，34（3）：998－1003 （in Chinese）. ［首照宇，歐陽寧，張華俊，等.基于SURF和動態ROI的實時視頻拼接 ［J］.計算機工程與設計，2013，34 （3）：998－1003.］

［9］Rosten E，Porter R，Drummond T.Faster and better：A machine learning approach to corner detection ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32 （1）：105－119.

［10］Calonder M，Leptit V，Strecha C.BRIEF：Binary robust independent elementary features ［G］.LNCS 6314：Computer Vision－ECCV.Berlin：Springer Berlin Heidelberg，2010：778－792.

［11］Mair E，Hager G，Burschka D，et al.Adaptive and generic corner detection based on the accelerated segment test ［G］.LNCS 6312：Computer Vision－ECCV.Berlin：Springer Berlin Heidelberg，2010：183－196.

［12］Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF ［C］//In International Confe－rence of Computer Vision，2011：2564－2571.