謝宜婷 王愛平 鄒 海

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)

?

基于局部近鄰圖的特征描述與特征匹配算法研究

謝宜婷 王愛平 鄒 海

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)

特征描述和特征匹配是計(jì)算機(jī)視覺領(lǐng)域的重要組成部分。近年來，為了實(shí)現(xiàn)圖像匹配上的可靠性和魯棒性，許多特征描述算法被提出來，例如SIFT、SURF、DAISY和BRIEF等。然而，當(dāng)圖像發(fā)生平移、旋轉(zhuǎn)、縮放等大視角變化時(shí)，這些描述符通常會失效。為了解決這個(gè)問題，在局部近鄰圖模型的基礎(chǔ)上，提出一種新穎的特征描述和相似性度量方法(LNFM算法)。所提出的描述符和相似度可以很好地應(yīng)用于各種流行的圖像匹配算法。實(shí)驗(yàn)結(jié)果表明：在特征匹配過程中，該算法可以檢測到可靠的匹配關(guān)系，性能較為優(yōu)越。

特征描述 局部近鄰圖 特征匹配 相似性度量

0 引 言

假如給定同一場景中的兩幅或多幅圖像，特征匹配的任務(wù)就是確定不同圖像中對應(yīng)特征點(diǎn)的匹配關(guān)系。圖像特征匹配是計(jì)算機(jī)視覺和模式識別領(lǐng)域中的一個(gè)基本問題，也是最核心的問題之一。據(jù)相關(guān)報(bào)道統(tǒng)計(jì)，它在60%的機(jī)器視覺問題中[1-5]，如圖像檢索、圖像合并、指紋識別、運(yùn)動目標(biāo)跟蹤、醫(yī)學(xué)圖像分析等都有著廣泛的應(yīng)用?；谔卣鼽c(diǎn)的匹配過程包括以下三個(gè)步驟：圖像特征的檢測；特征描述符的提?。惶卣髅枋龇南嗨菩远攘?。

其中，特征描述是基于特征點(diǎn)的匹配方法中一個(gè)很關(guān)鍵的步驟，對圖像匹配的效果起到了決定性作用。良好的特征描述符應(yīng)具有魯棒性和獨(dú)特性兩種性質(zhì)，魯棒性是指對灰度、光照、顏色等光度變化和平移、旋轉(zhuǎn)、尺度等幾何變形魯棒；獨(dú)特性是指所提取的描述符應(yīng)該具有充分的信息來辨別不同的特征點(diǎn)。特征描述符的構(gòu)造很多是基于局部結(jié)構(gòu)信息的，近幾年來，以SIFT為代表的基于描述符的特征匹配方法尤為突出，且應(yīng)用最廣。但是，當(dāng)場景中存在物體遮擋或者場景中存在較多復(fù)雜結(jié)構(gòu)時(shí)，離群匹配會大大增加。遇到這種情況，常用的方法是首先對圖像的局部結(jié)構(gòu)進(jìn)行相似性度量，然后在此基礎(chǔ)上，加入一些幾何約束條件，從而提高特征匹配的性能。為了更高效地描述特征點(diǎn)之間的局部幾何約束關(guān)系，通常將這些約束關(guān)系表示為屬性關(guān)系圖的結(jié)構(gòu)形式，其中，圖像里面提取的特征點(diǎn)表示為圖的頂點(diǎn)，特征點(diǎn)之間的幾何約束關(guān)系表示為圖的邊。因此，圖像特征匹配問題就可以轉(zhuǎn)化成為圖匹配問題去求解。

本文提出了一種新穎的特征描述方法，首先通過FAST和SURF算法檢測初始特征點(diǎn)，然后為每個(gè)特征點(diǎn)構(gòu)建局部圖，使用的是其近鄰特征點(diǎn)。與以往的特征描述符[6-7]不同，本文方法通過考慮每個(gè)特征點(diǎn)及其近鄰特征點(diǎn)，給出了一個(gè)相似性度量函數(shù)。在這種新穎的特征描述符和相似性度量函數(shù)的基礎(chǔ)上，提出了一種基于局部近鄰圖的特征匹配算法。該算法在理論上和實(shí)際應(yīng)用中都具有重要的意義。實(shí)驗(yàn)表明：該算法有良好的性能，提高了特征匹配算法的精度。

1 相關(guān)工作

特征描述是計(jì)算機(jī)視覺領(lǐng)域中的一個(gè)基礎(chǔ)性探究問題，在建立圖像之間的對應(yīng)關(guān)系以及物體識別中發(fā)揮著十分重要的作用。特征描述是特征匹配的基礎(chǔ)，在進(jìn)行圖像特征匹配的過程中，建立圖像之間特征點(diǎn)與特征點(diǎn)之間的可靠對應(yīng)關(guān)系通常都依賴于一個(gè)優(yōu)秀的特征描述符。

在眾多的特征描述符中，Lowe[8]提出的SIFT是其中應(yīng)用最廣的。它對平移、旋轉(zhuǎn)、尺度以及大視角和光照變化等都具有不變性，并且具有很好的可區(qū)別性。Bay等[9]提出的SURF是對SIFT的改進(jìn)，它利用Haar小波來近似SIFT方法中的梯度操作，同時(shí)利用積分圖技術(shù)進(jìn)行快速計(jì)算，其魯棒性很好且計(jì)算速度較快。Tola等[10]在2007年提出了DAISY，其本質(zhì)思想和SIFT是一樣的，不同的是，DAISY利用了高斯卷積的可快速計(jì)算性，可以快速稠密地進(jìn)行特征描述符的提取。Morel等[11]提出的ASIFT(Affine SIFT)通過模擬各種成像視角下得到的圖像進(jìn)行特征點(diǎn)匹配，可以高效地處理不同視角變化的情況，尤其是大視角變化下的特征點(diǎn)匹配。Calonder等[12]提出了BRIEF描述符用于實(shí)時(shí)匹配，它是基于二進(jìn)制位串的，不僅匹配速度快，而且存儲要求低。

優(yōu)秀特征描述符的獲取是為了更準(zhǔn)確地進(jìn)行特征匹配，近年來，很多基于圖理論的特征匹配算法被提出，受到了計(jì)算機(jī)視覺領(lǐng)域中很多專家和學(xué)者的關(guān)注。Leordeanu等[13]提出一種譜匹配算法SM(Spectral Matching)，該算法首先構(gòu)造親鄰矩陣，然后用譜分解方法獲得親鄰矩陣的最大特征值對應(yīng)的特征向量，以此實(shí)現(xiàn)特征點(diǎn)之間的匹配。Caetano等[14]提出了一種基于圖模型(Graphic model)的特征匹配算法，該方法的核心思想是將圖匹配問題轉(zhuǎn)換為概率推理問題去求近似解，在無噪聲的環(huán)境中，此算法獲得的圖像匹配效果良好。Bolles等[15]提出隨機(jī)采樣一致性算法RANSAC(Random Sample Consensus)來去除離群匹配，雖然該算法可以魯棒地估計(jì)模型參數(shù)，但是它只能從某個(gè)特定的數(shù)據(jù)集中估計(jì)出一個(gè)模型。如果存在兩個(gè)及其以上的模型，RANSAC算法則會失效。Aguilar等[16]提出了一種圖變換匹配算法GTM(Graph Transformation Matching)，該算法在k近鄰圖模型的基礎(chǔ)上，根據(jù)幾何一致性約束條件，從初始匹配關(guān)系中尋找相應(yīng)的匹配關(guān)系子集，最終可以獲得較多的正確匹配關(guān)系。Cho等[17]提出漸進(jìn)的圖匹配算法ProGM(Progressive Graph Matching)，通過貝葉斯框架不斷地更新目標(biāo)圖，從而在后續(xù)的圖匹配中增加匹配關(guān)系數(shù)目。

以上的圖像匹配算法使用傳統(tǒng)的特征描述符，通過一組特征點(diǎn)來描述對象，進(jìn)而找到初始匹配關(guān)系。然而，這些特征描述符存在固有的缺點(diǎn)，即在圖像發(fā)生顯著變化時(shí)，不能準(zhǔn)確地表示特征點(diǎn)。本文提出的算法克服了這個(gè)困難，通過使用圖像的局部近鄰結(jié)構(gòu)來表示特征點(diǎn)。

2 局部近鄰圖描述

算法1局部圖模型化

輸入：特征點(diǎn)集K，距離閾值Td，重疊閾值T0，近鄰節(jié)點(diǎn)個(gè)數(shù)最大值n。

步驟1：對每一個(gè)vi∈K、vj∈K且i≠j，計(jì)算vi和vj之間的歐式距離dij。如果dij

步驟2：如果|Vi|>n，取前n個(gè)最近鄰的特征點(diǎn)。將vi加入Vi，然后更新Vi的屬性，接著以vi為中心點(diǎn)，連接Vi中的其余節(jié)點(diǎn)，至此，形成了一個(gè)星狀局部圖，即Gi=(Vi,Ei,Ai)。

步驟3：所有的vi進(jìn)行步驟1和步驟2兩步操作之后，形成了局部圖集S={Gi|i=1,2,…,M}。

本文算法采用MATLAB來實(shí)現(xiàn)，局部近鄰圖算法流程圖如圖1所示。

圖1 局部近鄰圖算法流程圖

在局部近鄰圖模型的基礎(chǔ)上，本文提出一個(gè)相似性度量函數(shù)F(i,j)，用來計(jì)算圖Gi和圖Gj之間的相似度，定義如下：

(1)

式中，a和b表示圖Gi和圖Gj中的節(jié)點(diǎn)指數(shù)，也就是說，1≤a≤n且1≤b≤n。G(·)是一個(gè)高斯分布函數(shù)，β和d分別是相對根特征點(diǎn)的角度和歸一化距離，相似性函數(shù)F(i,j)是所有節(jié)點(diǎn)的最大相似性值的聚合?；趫D論的描述符在特征域中生成之后，如果一些特征點(diǎn)由于大視圖更改或變形而消失，那么圖的幾何特性會被破壞，這與特征檢測器的性質(zhì)有很大關(guān)系。為了防止依賴于特征檢測器，我們只聚合每個(gè)節(jié)點(diǎn)的最大相似性值。因此，相似性函數(shù)F(i,j)的值越大，描述符之間匹配的可能性越高。

3 局部近鄰圖的特征匹配

算法2基于局部近鄰圖的特征匹配算法

步驟2：能量函數(shù)E(x)=∑φi(xi)+∑φij(xi,xj)由一元項(xiàng)φi(xi)和二元項(xiàng)φij(xi,xj)組成，根據(jù)式(2)和式(3)分別計(jì)算出φi(xi)和φij(xi,xj)的值，然后進(jìn)行累加求和，即可得到E(x)的值。

步驟3：最后利用x*=argminxE(x)解出x*，根據(jù)x*的取值，恢復(fù)出兩個(gè)局部圖集S和S′之間的對應(yīng)關(guān)系。

利用式(1)的相似性函數(shù)F(i,j)，一元能量函數(shù)φi(xi)定義如下：

φi(xi) =e-F(i,xi )

(2)

另一方面，二元能量函數(shù)φij(xi,xj)定義如下：

(3)

因此，根據(jù)以上一元項(xiàng)和二元項(xiàng)的定義，能量函數(shù)E(x)的計(jì)算公式如下：

E(x)=∑φi(xi)+∑φij(xi,xj)

(4)

通過使用最大積環(huán)路信念傳播算法[19]，可以獲得x*=argminxE(x)的解。

4 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)是在MATLAB R2014a、Win2007系統(tǒng)中運(yùn)行的，實(shí)驗(yàn)圖象數(shù)據(jù)來源于Caltech-101[20]和MSRC圖像庫[21]。為了驗(yàn)證算法的有效性和魯棒性，本文首先添加高斯噪聲進(jìn)行模擬實(shí)驗(yàn)，然后在真實(shí)圖像上做特征匹配實(shí)驗(yàn)，主要與SM方法進(jìn)行比較。其中，特征點(diǎn)是由FAST和SURF 算法進(jìn)行檢測。在本文算法中，局部圖中近鄰節(jié)點(diǎn)的最大個(gè)數(shù)n設(shè)置為12，距離閾值Td設(shè)置為5倍的特征尺度。對于實(shí)驗(yàn)參數(shù)的選擇，近鄰節(jié)點(diǎn)的最大個(gè)數(shù)n和距離閾值Td等都是為了構(gòu)建大小合適的局部近鄰圖。例如，在本文中設(shè)置近鄰節(jié)點(diǎn)的最大個(gè)數(shù)n=12，如果n值設(shè)置得較大，則獲得的局部近鄰圖個(gè)數(shù)會很少，導(dǎo)致正確匹配數(shù)目變少，從而影響算法的精度；如果n值設(shè)置得較小，則獲得的局部近鄰圖個(gè)數(shù)會很多，導(dǎo)致錯誤匹配數(shù)目變多，從而影響算法的精度。

4.1 高斯噪聲模擬實(shí)驗(yàn)

(a) 離群點(diǎn)實(shí)驗(yàn)

(b) 變形噪聲實(shí)驗(yàn)圖2 實(shí)驗(yàn)對比結(jié)果

由圖2(a)和(b)的模擬結(jié)果可以看出，本文在局部近鄰圖模型的基礎(chǔ)上，提出的特征匹配算法，即LNFM算法的平均精度要比SM算法的高。因此，LNFM算法的性能比SM算法有優(yōu)勢。

4.2 真實(shí)圖像特征匹配實(shí)驗(yàn)

在Caltech-101和MSRC圖像庫上，本文所提出的局部近鄰圖的特征匹配算法與SM算法用于檢測同一對圖像上的目標(biāo)所獲得的匹配關(guān)系數(shù)目是不同的。為了便于觀察，每對圖像中正確匹配用一般直線表示，錯誤匹配用帶有標(biāo)記的直線表示。圖3—圖8分別是6個(gè)不同目標(biāo)的特征匹配結(jié)果。

(a) LNFM算法匹配結(jié)果

(b) SM算法匹配結(jié)果圖3 目標(biāo)1匹配結(jié)果

(a) LNFM算法匹配結(jié)果

(b) SM算法匹配結(jié)果圖4 目標(biāo)2匹配結(jié)果

(a) LNFM算法匹配結(jié)果

(b) SM算法匹配結(jié)果圖5 目標(biāo)3匹配結(jié)果

(a) LNFM算法匹配結(jié)果

(b) SM算法匹配結(jié)果圖6 目標(biāo)4匹配結(jié)果

(a) LNFM算法匹配結(jié)果

(b) SM算法匹配結(jié)果圖7 目標(biāo)5匹配結(jié)果

(a) LNFM算法匹配結(jié)果

(b) SM算法匹配結(jié)果圖8 目標(biāo)6匹配結(jié)果

雖然以上這些圖像發(fā)生了平移、旋轉(zhuǎn)、視角、尺度等復(fù)雜變換，但是用本文的方法仍能獲得較多的正確匹配關(guān)系。為了定量分析，在此定義匹配精度來對兩種算法進(jìn)行比較。

(5)

每對圖像，手動地標(biāo)記正確匹配關(guān)系的個(gè)數(shù)，根據(jù)式(5)，計(jì)算出匹配精度的值，記為MK_i，其中下標(biāo)i∈{1,2}代表兩種不同的方法(i=1是本文方法，i=2是SM方法)。如果MK_1>MK_2，則表明本文算法比SM算法有優(yōu)勢，反之亦然，表1為相應(yīng)的對比結(jié)果。

表1 Caltech-101和MSRC圖像庫上特征匹配精度

由表1的統(tǒng)計(jì)結(jié)果和圖2—圖8的匹配效果可以看出，本文在局部近鄰圖模型的基礎(chǔ)上，提出的特征匹配算法在真實(shí)圖像特征匹配的過程中，LNFM算法的性能明顯比SM算法要優(yōu)越得多，本文LNFM算法的匹配精度要比SM算法的高。

5 結(jié) 語

本文在局部近鄰圖模型的基礎(chǔ)上，提出了一種新穎的特征匹配算法。在所提出的方法中，初始特征點(diǎn)首先通過FAST和SURF算法進(jìn)行檢測，然后為每個(gè)特征點(diǎn)構(gòu)造局部圖，每個(gè)局部圖是由根特征點(diǎn)及其近鄰特征點(diǎn)組成的?；诰植拷張D模型，本文給出了一個(gè)相似性度量函數(shù)，用于計(jì)算兩個(gè)局部圖之間的相似度。在特征匹配過程中，利用相似性度量函數(shù)，本文提出一個(gè)能量函數(shù)來找到兩個(gè)局部圖集之間的對應(yīng)關(guān)系，最終達(dá)到圖像匹配的效果。本文算法與SM算法進(jìn)行了比較，實(shí)驗(yàn)的實(shí)例圖、定量分析結(jié)果，以及高斯噪聲模擬實(shí)驗(yàn)結(jié)果都表明本文算法在匹配精度上顯示性能優(yōu)越。本文算法可應(yīng)用于車牌字符的識別。為了識別車流量較大的市區(qū)道路上的車牌號碼，首先給出一個(gè)標(biāo)準(zhǔn)字符模板樣式，運(yùn)用本文局部近鄰圖的特征匹配算法，將標(biāo)準(zhǔn)化的車牌區(qū)字符和字符模板進(jìn)行匹配，進(jìn)而達(dá)到車牌字符識別的目的。對實(shí)際交通環(huán)境中的各種車牌類型運(yùn)用本文算法進(jìn)行識別，識別率約達(dá)92%，結(jié)果較為滿意。

[1] Ma J, Zhou H, Zhao J, et al. Robust feature matching for remote sensing image registration via locally linear transforming[J].IEEE Transactions on Geoscience and Remote Sensing, 2015, 53(12): 6469-6481.

[2] Arnfred J T, Winkler S. A general framework for image feature matching without geometric constraints[J].Pattern Recognition Letters, 2016, 73: 26-32.

[3] Zhou W, Yang M, Wang X, et al. Scalable feature matching by dual cascaded scalar quantization for image retrieval[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(1): 159-171.

[4] Chen H Y, Lin Y Y, Chen B Y. Co-segmentation guided hough transform for robust feature matching[J]. IEEE transactions on pattern analysis and machine intelligence, 2015, 37(12): 2388-2401.

[5] Ma J, Ma Y, Zhao J, et al. Image feature matching via progressive vector field consensus[J]. IEEE Signal Processing Letters, 2015, 22(6): 767-771.

[6] Murala S, Maheshwari R P, Balasubramanian R. Local tetra patterns: a new feature descriptor for content-based image retrieval[J]. IEEE Transactions on Image Processing, 2012, 21(5): 2874-2886.

[7] Ma B, Chai X, Wang T. A novel feature descriptor based on biologically inspired feature for head pose estimation[J]. Neurocomputing, 2013, 115: 1-10.

[8] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

[9] Bay H, Ess A, Tuytelaars T, et al. Speeded-up robust features (SURF)[J]. Computer vision and image understanding, 2008, 110(3): 346-359.

[10] Tola E, Lepetit V, Fua P. Daisy: An efficient dense descriptor applied to wide-baseline stereo[J]. IEEE transactions on pattern analysis and machine intelligence, 2010, 32(5): 815-830.

[11] Morel J M, Yu G. ASIFT: A new framework for fully affine invariant image comparison[J]. SIAM Journal on Imaging Sciences, 2009, 2(2): 438-469.

[12] Calonder M, Lepetit V, Ozuysal M, et al. BRIEF: Computing a local binary descriptor very fast[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1281-1298.

[13] Leordeanu M, Hebert M. A spectral technique for correspondence problems using pairwise constraints[C]//Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. IEEE, 2005, 2:1482-1489.

[14] Caetano T S, Caelli T, Schuurmans D, et al. Graphical models and point pattern matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(10): 1646-1663.

[15] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[16] Aguilar W, Frauel Y, Escolano F, et al. A robust graph transformation matching for non-rigid registration[J]. Image and Vision Computing, 2009, 27(7): 897-910.

[17] Cho M, Lee K M. Progressive graph matching: Making a move of graphs via probabilistic voting[C]//Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012:398-405.

[18] Rublee E, Rabaud V, Konolige K, et al. ORB: An efficient alternative to SIFT or SURF[C]//2011 International conference on computer vision. IEEE, 2011: 2564-2571.

[19] Felzenszwalb P F, Huttenlocher D P. Efficient belief propagation for early vision[J]. International journal of computer vision, 2006,70(1): 41-54.

[20] Fei-Fei L, Fergus R, Perona P. One-shot learning of object categories[J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 28(4): 594-611.

[21] Winn J, Criminisi A, Minka T. Object categorization by learned universal visual dictionary[C]//Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1. IEEE, 2005, 2:1800-1807.

RESEARCHOFFEATUREDESCRIPTIONANDFEATUREMATCHINGALGORITHMBASEDONLOCALNEIGHBORHOODGRAPH

Xie Yiting Wang Aiping Zou Hai
(CollegeofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

Feature description and feature matching are important parts in the field of computer vision. In recent years, many feature description algorithms have been proposed to achieve reliable and robust performance in image matching, such as SIFT, SURF, DAISY and BRIEF. However, their descriptors usually fail when the images have undergone large viewpoint changes such as translation, rotation and scaling. To solve this problem, on the basis of local neighborhood graph model, a novel feature description and similarity measure method (referred to as LNFM algorithm) is proposed. The proposed descriptor and similarity can be well applied to a variety of popular image matching algorithms. The experimental results show that: in the process of feature matching, the proposed algorithm can detect reliable matching relationship, and the performance is relatively superior.

Feature description Local neighborhood graph Feature matching Similarity measure

2016-08-06。國家自然科學(xué)基金項(xiàng)目(61573022)。謝宜婷，碩士生，主研領(lǐng)域：圖像匹配與識別。王愛平，教授。鄒海，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.08.033