周莉莉，姜 楓

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

0 引 言

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

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

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

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

1 FAST算法及其改進(jìn)

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

圖1 FAST 算法角點(diǎn)檢測模板

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

圖2 角點(diǎn)檢測的3種模板

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

圖3 不同模板角點(diǎn)響應(yīng)實(shí)驗(yàn)

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

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

此外，文中還對各種模板的算法運(yùn)行時(shí)間進(jìn)行比較。如表1 所示，F(xiàn)AST 算法比SIFT 和SURF 算法速度快很多，M16模板的FAST 算法運(yùn)行時(shí)間基本相當(dāng)，隨著模板尺寸的減少，算法運(yùn)行時(shí)間呈逐步遞減趨勢，M8模板的運(yùn)行時(shí)間約為M16模板運(yùn)行時(shí)間的1/3左右。

表1 不同模板的角點(diǎn)檢測時(shí)間對比

2 BRIEF算法及其改進(jìn)

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

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

n 在實(shí)際使用時(shí)可以選擇128，256或512，對應(yīng)描述器的長度分別為16字節(jié)，32字節(jié)和64字節(jié)，遠(yuǎn)低于SIFT描述器的512字節(jié) （128維實(shí)數(shù)）。

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

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

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

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

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

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

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

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

3 實(shí) 驗(yàn)

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

3.1 算法旋轉(zhuǎn)不變性實(shí)驗(yàn)

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

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

3.2 真實(shí)圖像匹配實(shí)驗(yàn)

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

3.3 算法性能及運(yùn)行時(shí)間實(shí)驗(yàn)

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

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

圖7 真實(shí)圖像匹配

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

4 結(jié)束語

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

［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ìn)的不變矩特征與物體識(shí)別 ［J］.計(jì)算機(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）.［胡瓊，秦磊，黃慶明.基于視覺的人體動(dòng)作識(shí)別綜述 ［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(jì)算機(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）.［張明杰，康寶生.改進(jìn)的目標(biāo)檢測與自動(dòng)跟蹤方法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(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ìn)的基于特征點(diǎn)匹配的圖像拼接融合算法［J］.計(jì)算機(jī)工程與設(shè)計(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）. ［張永，紀(jì)東升.一種改進(jìn)的Harris特征點(diǎn)檢測算法 ［J］.計(jì)算機(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 算法的并行實(shí)現(xiàn)及應(yīng)用 ［J］.計(jì)算機(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和動(dòng)態(tài)ROI的實(shí)時(shí)視頻拼接 ［J］.計(jì)算機(jī)工程與設(shè)計(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.