姜 楓，周莉莉，李 叢

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

1 引言

圖像匹配是計算機視覺中的一個基本問題，在現(xiàn)實生活中有著很多應(yīng)用，如物體識別、動作識別、三維圖像重建、視頻目標(biāo)跟蹤、全景圖像拼接等。其一般步驟是首先從圖像中選出“興趣點”，即特征點，然后對特征點進行特征描述，最后根據(jù)描述的特征進行匹配。

早期使用較多的特征點提取算法是Moravec角點檢測器、Harris角點檢測器等［1，2］，角點檢測器不僅能檢測圖像中的角點，而且可以檢測圖像中像素梯度較大的點。然而，Harris角點檢測器對圖像的尺度敏感，不能用于檢測不同尺寸的圖像。Lowe D G［3］提出了一種基于尺度不變性的特征提取 方 法，稱 為SIFT （Scale Invariant Feature Transform）方法，SIFT 算法中采用DOG（Difference of Gaussian）算 子 近 似LOG（Laplacian of Gaussian）算子求取圖像中特征點，并據(jù)此構(gòu)建梯度直方圖判斷局部圖像主方向，以實現(xiàn)尺度和旋轉(zhuǎn)不變性。著名的SURF（Speeded Up Robust Features）算法是SIFT 算法的快速實現(xiàn)版本［4］，當(dāng)中使用了快速Hessian檢測器簡化了復(fù)雜的DOG 計算來快速定位特征點，其運算速度遠(yuǎn)快于SIFT。Rosten E 等人［5］提出了可用于實時系統(tǒng)進行特征提取 的FAST（Features from Accelerated Segment Test）算 法，不 同 于SIFT 和SURF 算 法，F(xiàn)AST 通過直接計算圖像中心像素點和周圍像素點的關(guān)系找出圖像中的關(guān)鍵點，其運算效率遠(yuǎn)高于SIFT 和SURF算法。

關(guān)于特征描述算法，最著名的當(dāng)屬SIFT 特征描述器［3］，它是基于關(guān)鍵點附近區(qū)域像素的梯度直方圖進行運算的，使用了128維的向量來描述圖像局部特征，雖然該算法區(qū)分度極高，然而其計算、存儲復(fù)雜性高，因此不適用于實時場合。SURF特征描述器原理和SIFT 描述器原理基本相同，也是基于局部圖像的梯度直方圖計算，該描述器為64維［4］。Ke Y［6］采用PCA 算法對特征向量維數(shù)進行壓縮，減少了計算復(fù)雜性和存儲量，但該描述器的區(qū)分度不如SIFT。GLOH 描述器［7］也屬于SIFT 一類，其性能好于SIFT 描述器，但計算更為復(fù)雜。最近提出的BRIEF（Binary Robust Independent Elementary Features）［8］是一種高速的特征描述器，使用二進制字符串描述特征，除了表述簡單之外，在特征匹配時直接計算海明距離（Hamming Distance），運算速度遠(yuǎn)快于最近鄰等算法。Rublee E 等 人［9］在BRIEF 的 基 礎(chǔ) 上 提 出了ORB（Oriented FAST and Rotated BRIEF）算法，使用強度質(zhì)心（intensity centroid）方法克服了BRIEF不支持圖像旋轉(zhuǎn)的局限性。Trzcinsi T 等人［10］采用增強的二進制哈希函數(shù)進行計算得到光照和角度不變性的描述器。BRISK（Binary Robust Invariant Scalable Keypoints）［11］使 用AGAST［12］加速角點檢測速度，利用尺度空間金字塔實現(xiàn)圖像的尺度不變性，點對的采樣不同于BRIEF的隨機方式，而是以特征點為中心使用對稱模式采樣。

本文中，簡化FAST 算法模板提取圖像中的特征點，通過引入圖像金字塔使其具有尺度不變性；根據(jù)人類視覺系統(tǒng)原理，改進BRIEF的點對選擇方式描述特征，并通過計算特征點方向引入旋轉(zhuǎn)不變性特征；最后通過計算特征間的海明距離匹配圖像。

2 FAST算法及其改進

2.1 FAST算法簡介

FAST 算 法 起 源 于SUSAN 算 法［13］，其 原 理描述如下：對于圖像中某個中心點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這四個點的強度值，如果p為角點，則這四個點中至少有三個點的強度值均大于Ip＋t或者均小于Ipt。只有在上述檢測通過后才需要檢測剩余的12個點，從而提高了檢測速度。這種方法雖然方便，但只適用于N為12的情況。為了開發(fā)一個更為普適的算法，F(xiàn)AST 算法中引入了機器學(xué)習(xí)方法［5］。

第一步，針對特定的N和閾值t，使用上述分割測試準(zhǔn)則從圖像集中檢測出所有角點，這個過程中需要檢測每個點周圍的所有16個點，將檢測過的圖像作為訓(xùn)練樣本。

第二步，利用第一步得到的訓(xùn)練樣本，根據(jù)信息增益最大原則使用ID3算法，訓(xùn)練得到可以對角點進行正確分類的決策樹。訓(xùn)練完成后使用決策樹對圖像中的點進行分類，得到角點和非角點。

Figure 1 FAST corner detection mask圖1 FAST 算法角點檢測模板

2.2 簡化FAST檢測模板

文獻［14］中指出，用于快速角點檢測可以使用多種不同模板，圖2中即為本文用于角點檢測的三種不同模板。

為了評估不同模板的角點響應(yīng)效果，使用了如圖3所示的不同視角的圖片集進行測試。圖4表示分別采用M16（連續(xù)像素點數(shù)目N分別為9、10、11）、M12S、M12D 和M8模板對圖3所示的圖集進行角點檢測得到的效果。分析可發(fā)現(xiàn)，F(xiàn)AST算法中使用的模板尺寸越大，得到的角點數(shù)越多。在模板尺寸相同的情況下，N值越大則生成的角點越少，且更接近真實位置，圖4a和4b在角點位置附近產(chǎn)生了多重響應(yīng)，圖4c產(chǎn)生的角點數(shù)少且更靠近真實位置。圖4f中的檢測結(jié)果表明，M8模板的角點響應(yīng)能力較強。

Figure 2 3masks for corner detection圖2 用于角點檢測的三種模板

Figure 3 Images for corner response experiments圖3 角點響應(yīng)實驗用圖

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

Figure 4 Comparison in corner responses among different masks圖4 不同模板的角點響應(yīng)對比

Table 1 Comparison in corner detection time among different masks表1 不同模板的角點檢測時間對比

2.3 尺度不變性

FAST 算法雖然檢測角點的速度比較快，但也存在著兩個缺點：（1）無法衡量角點量（Cornerness）；（2）缺乏對多尺度的支持。因此，在ORB中，使用文獻［2］中提出的角點量的概念，結(jié)合圖像尺度金字塔，在金字塔的每一層根據(jù)Harris角點量施加非最大約束（Non－maximal Suppression）。然而，ORB 中僅在金字塔各層層內(nèi)施加非最大約束，各層之間并未使用，因此可能造成不同層次間潛在的角點重復(fù)探測。

在本文中，除了在金字塔各層內(nèi)部施加非最大約束外，在各層之間也進行非最大約束，具體做法如下：

首先，根據(jù)輸入圖像構(gòu)造n層的圖像金字塔（n取4），第0層金字塔對應(yīng)原始圖像，第1層金字塔為對第0層圖像實施1/2的下采樣所得，其余層金字塔的構(gòu)成依此類推。

Figure 5 Keypoints detection in scale space圖5 尺度空間特征點檢測

在進行角點檢測時，先在金字塔的每層使用相同的閾值t運行FAST 算法，計算出所有潛在的特征點區(qū)域。接著，對這些區(qū)域的點施加非最大約束條件，分為兩個步驟：（1）將該點與相鄰的8個點比較；（2）將該點與上層9個點及下層9個點進行比較。由于各個層次的尺度不同，因此在計算相鄰層次對應(yīng)點時需要進行插值運算，如圖5所示。為了在第0層圖像施加非最大約束，需要使用圖像上采樣，在第0層以下虛擬出一個－1層圖像。

圖6顯示了特征點檢測的效果，圖6a和圖6b中涉及尺度和旋轉(zhuǎn)變化，圖中圓的大小表示特征點的尺度，圓中的徑向表示特征點的方向，方向的計算在3.3節(jié)介紹。

Figure 6 Results of keypoints detection in a boat image set圖6 在Boat圖像集上進行特征點檢測結(jié)果

3 BRIEF算法及其改進

3.1 BRIEF算法簡介

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

其中，x、y是圖像片段p中的任意兩個像素點，p（x）、p（y）分別為點x和y的強度值。

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

3.2 點對采樣模式

BRIEF描述器中一個重要的問題是如何在圖像片段p中選擇n個點對，文獻［8］中給出了五種不同方案并通過實驗進行詳細(xì)比較，得出結(jié)論：當(dāng)（X，Y）服從（0，S2/25）的高斯分布時，效果最好。Vandergheynst P等人［14］提出在對特征點附近點取樣時應(yīng)模仿人類視覺系統(tǒng)成像原理。在取樣時為了匹配人類視網(wǎng)膜模型，越靠近特征點中心區(qū)域，取樣密度越大，離特征點越遠(yuǎn)，取樣密度越小。同時，為了增加采樣點對噪聲的魯棒性，對每一個采樣點都進行平滑濾波，為了和視網(wǎng)膜模型相匹配，本文對每個采樣點使用不同大小的模板進行濾波。這一點有點類似于BRISK 中的做法，區(qū)別在于本文采用的濾波模板大小與采樣點到特征點中心的距離呈指數(shù)關(guān)系，并且各個模板之間有重疊部分，如圖7所示。

Figure 7 Sampling pattern similar to the retinal ganglion cells distribution圖7 模擬視網(wǎng)膜神經(jīng)節(jié)細(xì)胞分布的采樣模型

采樣之后，可以根據(jù)式（2）選擇點對進行兩兩測試，以形成二進制描述器。假設(shè)采樣點的數(shù)目為N，則可能產(chǎn)生的點對數(shù)為N×（N－1）/2，一般取N為43，則點對數(shù)為903，即生成的二進制描述器為903位，這比ORB和BRIEF中使用的描述器都要復(fù)雜。因此，如何盡可能壓縮描述器位數(shù)，選擇最有效、最能描述圖像特征的點對是本文研究的另一個問題。文獻［9］中指出，可以通過分析BRIEF描述器向量的相關(guān)性和方差來選擇特征區(qū)分度大的點對。根據(jù)這一思想，本文采用如下方法從訓(xùn)練數(shù)據(jù)中選擇點對：

（1）根據(jù)從圖像中提取的特征點建立二維矩陣M，其行數(shù)為從圖像中提取特征點的數(shù)目，每一行對應(yīng)一個特征描述器，當(dāng)采樣點為43個時，如上所述，描述器為903維的向量。

（2）計算每一列的均值。為了使特征的辨識度最大，應(yīng)保持方差最大。對于二進制的變量來說，均值為0.5會產(chǎn)生最大方差。

（3）根據(jù)方差對矩陣的列進行排序。

（4）選出所有均值為0.5的列，在剩余的列中選擇與已選列相關(guān)性最小的列加入已選列，直至選擇的列數(shù)達(dá)到期望值。

3.3 旋轉(zhuǎn)不變性

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

《中國老年人潛在不適當(dāng)用藥目錄》判斷PIM情況 在795例社區(qū)老年患者中，有230例 （28．9%）存在PIM合計275項，其中存在2項以上PIM的患者36例。202例患者 （25．4%）使用了A級優(yōu)先警示藥物共226項，其中高風(fēng)險強度29項（12．8%）， 低風(fēng)險強度 197 項 （87．2%）。 44 例患者（5．5%）使用了B級常規(guī)警示藥物共49項，其中高風(fēng)險強度 36項 （75．5%），低風(fēng)險強度 13項（26．5%）。具體情況見表 6和表 7。

在提取的特征點附近使用3.2節(jié)所介紹的方法選出n個點對。然后，將其根據(jù)特征點的主方向進行旋轉(zhuǎn)。ORB 中使用強度質(zhì)心（Intensity Centroid）方法計算特征點主方向，其原理是認(rèn)為圖像片段主方向由其中心和質(zhì)心間的偏移決定。BRISK 中提出，將采樣點對分為短距離點對和長距離點對，其中長距離點對的局部梯度之和用于計算特征點主方向。本文在BRISK 的基礎(chǔ)上加以改進，如圖8 所示，以特征點為中心，選取對稱點對（圖中用直線表示的45個點對）用于計算主方向，計算公式為：

式（3）中，P表示用于計算特征點方向所選擇的所有點對，D為P的數(shù)量，Ki是點的空間二維坐標(biāo)，I（·）表示某個點的像素值。

為了測試本文算法的旋轉(zhuǎn)不變性，對測試圖像進行了人工旋轉(zhuǎn)并增加高斯噪聲，并將幾種常見算法加以對比。圖9表明，本文算法的旋轉(zhuǎn)魯棒性最強。

3.4 特征描述器匹配

Figure 8 Illustration of the selection of pairs for calculating main orientation of the keypoints圖8 計算特征點主方向的點對選擇示意圖

Figure 9 Rotation invariance tests of different algorithms圖9 各種算法旋轉(zhuǎn)不變性對比測試

對二進制描述器進行匹配是通過計算兩個描述器二進制串之間的海明距離直接進行的，其中海明距離定義為兩個二進制串之間對應(yīng)位置不同比特的數(shù)目，在實際計算時可直接使用計算機的異或操作（XOR）。

4 實驗結(jié)果及分析

在本節(jié)中，使用文獻［7］中推薦的標(biāo)準(zhǔn)測試圖像庫，將本文所提算法與SIFT、ORB、BRISK 等進行測試對比。測試庫中包含八個圖像集，如圖10所示，每個圖像集中包含相同場景不同條件下的六張圖像，如boats和bark 中是旋轉(zhuǎn)和尺度變換，graffiti和wall中包含視角變換，trees和bikes為圖像失真，leuven是光照變化，ubc是JPEG 壓縮。

實驗中，SIFT 算法采用五組金字塔，每組三層，采用128 維實數(shù)向量描述特征；ORB 中使用256位 特 征 描 述 器；BRISK 采 用AGAST 算 法［12］檢測特征點，512位向量描述特征點；本文算法采用M8模板結(jié)合FAST 算法，并在圖像金字塔各層間施加非最大約束條件，256位的特征描述器。實驗環(huán)境使用opencv 2.4.2以及visual studio 2010。

Figure 10 Test image set for experiments圖10 實驗用測試圖像集

測試算法性能使用了文獻［7］中推薦的recall/1－precison曲線圖。為使測試盡量公平，需要調(diào)整不同檢測算法的閾值，使檢測出的特征點數(shù)目盡可能相同。從圖11的實驗結(jié)果表明，本文算法性能在所有測試圖像集上均要優(yōu)于其他算法，算法性能的總體性能排名為本文算法＞BRISK＞ORB＞SIFT。而SIFT 算法總體表現(xiàn)不佳，尤其在trees、ubc、boats等圖像庫表現(xiàn)更差，是因為SIFT 檢測出的特征點可重復(fù)性較低。通過圖11b和圖11d分析可知，本文算法對于圖像旋轉(zhuǎn)和尺度變化適應(yīng)性較其他算法強，而ORB 算法由于不支持圖像的尺度變化，因此表現(xiàn)最差。圖11中顯示，所有算法在光照變化和圖像壓縮時均表現(xiàn)出較好的適應(yīng)性。在圖像失真情況下，尤其在圖11e中，bikes圖像庫總體表現(xiàn)比trees圖像庫要好，原因是為了平衡各種算法提取的特征點數(shù)目，前者提取的特征點數(shù)比后一個圖像庫提取出的多，因此查全率高。

從表2和表3不難發(fā)現(xiàn)，在特征點的檢測中，ORB使用了FAST 算子，因此速度遠(yuǎn)比SIFT 快，BRISK 中使用了AGAST、本文算法簡化了FAST檢測模板，所以速度又優(yōu)于ORB。在特征點描述中，ORB、BRISK 和本文算法都使用二進制描述器，因此速度都比SIFT 快，BRISK 和本文算法的點對匹配有固定模式，所以耗時小于ORB。在特征匹配中，SIFT 由于描述器長度最長（512字節(jié)），因此平均耗時最長，ORB、BRISK 和本文算法均是根據(jù)二進制間的海明距離匹配，所以速度較快，BRISK 描述器長度為512位，而ORB 和本文算法描述器長度為256，所以匹配速度相對較快。

Figure 11 Performance evaluation for different algorithms圖11 幾種算法性能測試對比

Table 2 Time of detection and descriptor for keypoints表2 特征點檢測和描述時間

Table 3 Matching time for keypoints of boat－1and boat－3images表3 boat－1和boat－3圖像特征點匹配時間

5 結(jié)束語

本文以FAST 算法作為圖像特征檢測器，使用BRIEF算法描述圖像局部特征。在此基礎(chǔ)上，對FAST 算法的模板進行簡化，實驗表明，簡化模板的特征點檢測器在保持特征點響應(yīng)能力的前提下計算速度得到進一步提升，并通過構(gòu)造圖像金字塔的方法提升了算法的尺度不變性。同時，模仿視網(wǎng)膜模型改進了BRIEF 算法中點對的采樣方式，通過點對之間局部梯度的計算為特征點標(biāo)注方向，使得特征描述器的旋轉(zhuǎn)不變性更強。最后，通過對標(biāo)準(zhǔn)測試圖像集的實驗表明，和一些經(jīng)典的算法相比，本文所提出的算法是一種性能強、運算速度快的特征匹配算法。

［1］ Moraver H.Rover visual obstacle avoidance［C］∥Proc of International Joint Conference on Artificial Intelligence，1981：785－790.

［2］ Harris C，Stephens M.A combined corner and edge detector［C］∥Proc of the 4th Alvey Vision Conference，1988：147－151.

［3］ Lowe D G.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［4］ Bay H，Tuytelaars T，Gool L V.SURF：Speeded up robust features［C］∥Proc of European Conference on Computer Vision，2006：404－417.

［5］ 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.

［6］ Ke Y，Sukthankar R.Pca－sift：A more distinctive representation for local image descriptors［C］∥Proc of Computer Vision and Pattern Recognition，2004：506－513.

［7］ Mikolajajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615－1630.

［8］ Calonder M，Leptit V，Strecha C.BRIEF：Binary robust independent elementary features［C］∥Proc of European Conference on Computer Vision，2010：778－792.

［9］ Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF［C］∥Proc of International Conference on Computer Vision，2011：2564－2571.

［10］ Trzcinski T，Christoudias M，F(xiàn)ua P，et al.Boosting binary keypoint descriptors［C］∥Proc of Computer Vision and Pattern Recognition，2013：510－517.

［11］ Leutenegger S，Chli M，Siegwart R.BRISK：Binary Robust Invariant Scalable Keypoints［C］∥Proc of International Conference on Computer Vision，2011：2548－2555.

［12］ Mair E，Hager G，Burschka D，et al.Adaptive and generic corner detection based on the accelerated segment test［C］∥Proc of European Conference on Computer Vision，2010：183－196.

［13］ Smith S M，Brady J M.SUSAN—a new approach to low level image processing［J］.International Journal of Computer Vision，1997，23（1）：45－78.

［14］ Vandergheynst P，Ortiz R，Alahi A.FREAK：Fast retina keypoint［C］∥Proc of Computer Vision and Pattern Recognition，2012：510－517.