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

周莉莉，姜 楓

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

0 引 言

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

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

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

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

1 FAST算法及其改進

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

圖1 FAST 算法角點檢測模板

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

圖2 角點檢測的3種模板

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

圖3 不同模板角點響應(yīng)實驗

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

圖4 不同模板的角點響應(yīng)對比

此外，文中還對各種模板的算法運行時間進行比較。如表1 所示，F(xiàn)AST 算法比SIFT 和SURF 算法速度快很多，M16模板的FAST 算法運行時間基本相當(dāng)，隨著模板尺寸的減少，算法運行時間呈逐步遞減趨勢，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，對應(yīng)描述器的長度分別為16字節(jié)，32字節(jié)和64字節(jié)，遠(yuǎn)低于SIFT描述器的512字節(jié) （128維實數(shù)）。

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

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

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

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

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

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

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

圖5 各種算法旋轉(zhuǎn)不變性測試

3 實 驗

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

3.1 算法旋轉(zhuǎn)不變性實驗

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

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

3.2 真實圖像匹配實驗

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

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

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

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

圖7 真實圖像匹配

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

4 結(jié)束語

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

［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］.計算機工程與應(yīng)用，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］.計算機學(xué)報，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）. ［樊博，楊曉梅，胡學(xué)姝.基于壓縮感知的超分辨率圖像重建 ［J］.計算機應(yīng)用，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）.［張明杰，康寶生.改進的目標(biāo)檢測與自動跟蹤方法研究 ［J］.計算機工程與設(shè)計，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］.計算機工程與設(shè)計，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）. ［張永，紀(jì)東升.一種改進的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 算法的并行實現(xiàn)及應(yīng)用 ［J］.計算機工程與應(yīng)用，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和動態(tài)ROI的實時視頻拼接 ［J］.計算機工程與設(shè)計，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.