結(jié)合亮度序局部特征描述的圖匹配算法

鮑文霞，胡根生，梁棟，張艷

（1.安徽大學(xué)計(jì)算機(jī)智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽合肥230039；2.安徽大學(xué)電子信息工程學(xué)院，安徽合肥230601）

結(jié)合亮度序局部特征描述的圖匹配算法

鮑文霞1，2，胡根生1，2，梁棟1，2，張艷1，2

（1.安徽大學(xué)計(jì)算機(jī)智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽合肥230039；2.安徽大學(xué)電子信息工程學(xué)院，安徽合肥230601）

在圖匹配問(wèn)題中基于松弛迭代的方法能否收斂到全局最優(yōu)解在很大程度上依賴于初始值的估計(jì)，針對(duì)這個(gè)問(wèn)題，提出了一種結(jié)合亮度序局部特征描述的圖匹配算法。該算法首先利用Hessian?Affine方法提取圖像的特征點(diǎn)及局部特征區(qū)域，以特征點(diǎn)作為圖的節(jié)點(diǎn)并結(jié)合特征點(diǎn)的鄰近關(guān)系構(gòu)造結(jié)構(gòu)圖；其次，根據(jù)亮度序約束關(guān)系對(duì)局部特征區(qū)域進(jìn)行子區(qū)域劃分，利用改進(jìn)的中心對(duì)稱局部二值模式（CS?LBP）獲取局部特征描述；最后，將局部特征描述之間的相似性作為圖匹配關(guān)系矩陣的初始值，通過(guò)松弛迭代的方法獲取特征點(diǎn)的準(zhǔn)確匹配結(jié)果。實(shí)驗(yàn)結(jié)果表明該算法匹配準(zhǔn)確率較高。關(guān)鍵詞：亮度序；局部特征描述；圖匹配；中心對(duì)稱局部二值模式；松弛迭代

近年來(lái)，結(jié)構(gòu)圖作為一種非常有效的描述數(shù)據(jù)的工具，在圖像特征匹配問(wèn)題上得到了越來(lái)越多的應(yīng)用［1］。用結(jié)構(gòu)圖來(lái)描述圖像的特征，那么圖像特征匹配問(wèn)題就轉(zhuǎn)化為圖匹配問(wèn)題［2?3］。圖匹配問(wèn)題具有代表性的有基于譜分解和基于松弛迭代的2種方法［4］。

基于譜分解的圖匹配方法是通過(guò)分析圖對(duì)應(yīng)的鄰接矩陣的特征空間獲取圖的點(diǎn)（節(jié)點(diǎn)）之間的匹配關(guān)系［5?6］。基于松弛迭代的圖匹配方法是使用匹配的代價(jià)函數(shù)取代圖之間不相似性的度量標(biāo)準(zhǔn)，將圖匹配的離散組合優(yōu)化問(wèn)題轉(zhuǎn)化成為一個(gè)連續(xù)優(yōu)化問(wèn)題。例如，Zheng等根據(jù)形狀點(diǎn)局部鄰接關(guān)系表示的約束構(gòu)造匹配代價(jià)函數(shù)，將形狀上下文局部特征描述的相似性作為初始匹配值，然后采用松弛迭代的方法實(shí)現(xiàn)非剛體形狀匹配［7］?；谒沙诘姆椒芊袷諗康饺肿顑?yōu)解在很大程度上依賴于初始值的估計(jì)，而對(duì)于圖像特征匹配問(wèn)題，初始值一般由圖像局部特征描述的相似性獲得［8］。目前，關(guān)于圖像局部特征的描述最具有代表性的是SIFT描述［9］，Mikolajczyk等提出的GLOH算法對(duì)SIFT的分塊方法進(jìn)行了擴(kuò)展［10］，不同于SIFT的方格型分塊，GLOH采用極坐標(biāo)分塊，這樣得到的特征描述更加穩(wěn)定；而Heikkila等將SIFT與LBP（local binary patterns）相結(jié)合［11］，提出了一種新的局部區(qū)域描述子，該描述子優(yōu)于SIFT描述子，并且具有較低的計(jì)算復(fù)雜度。在此基礎(chǔ)上，本文給出了一種亮度序局部特征描述，以此作為匹配的初始值，然后利用松弛迭代的方法得到更精確的匹配結(jié)果。

1 圖匹配算法

對(duì)于兩幅待匹配圖像I1和I2，利用Hessian?Affine方法［12］檢測(cè)特征點(diǎn)及對(duì)應(yīng)的具有仿射不變性的局部特征區(qū)域。設(shè)像特征點(diǎn)集分別為X＝｛xi｜i＝1，2，...，m｝、Y＝｛yj｜j＝1，2，...，n｝，點(diǎn)集之間的匹配關(guān)系為f：X→Y。點(diǎn)集之間的匹配代價(jià)函數(shù)定義為

式中：Ki表示X中第i個(gè)點(diǎn)即xi的k近鄰，Kj表示Y中第j個(gè)點(diǎn)即yj的k近鄰。

最佳匹配關(guān)系f＾為

求解式（2）的優(yōu)化問(wèn)題可以通過(guò)構(gòu)造結(jié)構(gòu)圖，轉(zhuǎn)化為圖匹配問(wèn)題進(jìn)行求解。

對(duì)于圖像特征點(diǎn)集X，按如下方式構(gòu)造點(diǎn)集X對(duì)應(yīng)的結(jié)構(gòu)圖G（X）：將點(diǎn)集X中的每一個(gè)特征點(diǎn)作為圖的節(jié)點(diǎn)，具有鄰近關(guān)系的特征點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)之間存在著一條邊，即此邊集滿足uv∈E（G）?u∈K（v）或v∈K（u）。因此，式（2）的優(yōu)化問(wèn)題轉(zhuǎn)化為求2個(gè)圖匹配邊數(shù)目最多的問(wèn)題。

匹配關(guān)系函數(shù)f可以寫成如下矩陣形式：

若xi和yj匹配，則pij＝1，否則pij＝0。矩陣P滿足如下正交化條件：

于是，匹配代價(jià)函數(shù)可以寫為

求解最優(yōu)的匹配關(guān)系矩陣P使C（X，Y，P）最大化的問(wèn)題是一個(gè)離散優(yōu)化問(wèn)題，使用松弛迭代方法首先將pij∈｛0，1｝松弛到pij∈［0，1］，從而將求解的問(wèn)題轉(zhuǎn)化為一個(gè)連續(xù)優(yōu)化問(wèn)題。

2 亮度序局部特征描述

針對(duì)匹配關(guān)系矩陣初始值的估計(jì)問(wèn)題，本文給出一種基于亮度序的局部特征描述。

2.1 區(qū)域劃分

設(shè)某個(gè)特征點(diǎn)對(duì)應(yīng)的局部特征區(qū)域規(guī)范化后為ω＝｛x1，x2，...，xn｝，I（x）表示點(diǎn)x的亮度值。根據(jù)ω內(nèi)所有點(diǎn)的亮度值按上升的關(guān)系排序，得到有序集合：

Oω＝｛k1，k2，...，kn：I（xk1）≤I（xk2）≤...≤I（xkn）｝再將ω區(qū)域劃分為nbins個(gè)子區(qū)域：ωi＝｛xj：ti-1≤I（xj）≤ti｝，1≤i≤nbins，其中

圖1給出了這種區(qū)域劃分方法的圖示，其中圖1（a）為規(guī)范化后的支持區(qū)域，圖1（b）、（c）、（d）、（e）為按照亮度序關(guān)系劃分的4個(gè)子區(qū)域。因?yàn)榱炼葐握{(diào)變化不改變序的關(guān)系，并且?guī)缀涡D(zhuǎn)也不改變圖像的亮度，因此這種基于亮度序的區(qū)域劃分方法同時(shí)具有幾何旋轉(zhuǎn)不變性和亮度單調(diào)變化不變性。

圖1 基于亮度序的區(qū)域劃分Fig.1 Regions based on brightness order

2.2 局部特征描述

為了使特征描述具有旋轉(zhuǎn)不變性，本文采用一種改進(jìn)的中心對(duì)稱局部二值模式方法來(lái)計(jì)算特征值。設(shè)xi為區(qū)域ω中的任一采樣點(diǎn)，選取點(diǎn)xi和區(qū)域中心點(diǎn)即特征點(diǎn)x的連線與圓周的2個(gè)交點(diǎn)距離特征點(diǎn)較近的點(diǎn)作為第一個(gè)采用點(diǎn)x0，然后沿逆時(shí)針?lè)较蛟趫A周上均勻的采樣其余的N-1個(gè)點(diǎn)，如圖2所示。則xi的特征值為

式中：xi+（N／2）表示以xi為圓心、R為半徑的圓上N個(gè)等距的鄰域點(diǎn)中關(guān)于xi中心對(duì)稱的點(diǎn)，T是一個(gè)閾值。

圖2 N＝8時(shí)的特征值計(jì)算示意圖Fig.2 The diagram of feature value calculation for N＝8

對(duì)于支持區(qū)域ω中任一采樣點(diǎn)的特征值的取值有nspies＝2N／2種情況，即

特征區(qū)域按亮度序劃分成nbins個(gè)子區(qū)域，在每一個(gè)子區(qū)域中，按照采樣點(diǎn)的特征值進(jìn)行統(tǒng)計(jì)，這樣就可以得到以特征點(diǎn)x為中心的支持區(qū)域的特征描述向量：χ（x）＝（χ1，χ2，...，χK），式中：i＝1，2，...，K，K＝nbinsnspies，NUMk為第k個(gè)亮度劃分子區(qū)域的像素?cái)?shù)目。χ（k，h）表示第k個(gè)子區(qū)域中特征值為第h種情況的采樣點(diǎn)的數(shù)目比例。

2.3 圖匹配關(guān)系矩陣的初始化

若兩特征點(diǎn)x和y對(duì)應(yīng)的亮度序局部特征描述分別為χ（x）＝（χ1（x），χ2（x），...，χK（x））和χ（y）＝（χ1（y），χ2（y），...，χK（y）），則它們之間的相似性約束可以用χ2距離來(lái)表示：

則圖匹配關(guān)系矩陣P按下式進(jìn)行初始化：

3 算法流程

本文結(jié)合亮度序局部特征描述的圖匹配算法具體步驟如下：

1）利用Hessian?Affine方法來(lái)檢測(cè)特征點(diǎn)及特征區(qū)域；

2）計(jì)算特征點(diǎn)的亮度序局部特征描述；

3）利用式（11）初始化匹配關(guān)系矩陣P；

4）設(shè)置松弛迭代次數(shù)為1；

5）按如下方式更新匹配關(guān)系矩陣：

6）將匹配關(guān)系矩陣P通過(guò)交替行列歸一化的方式將其轉(zhuǎn)化為雙隨機(jī)矩陣：

或者迭代次數(shù)等于Imax，迭代結(jié)束，否則迭代次數(shù)加1，并跳轉(zhuǎn)至5）；

8）根據(jù)匹配關(guān)系矩陣P來(lái)獲取點(diǎn)集之間的匹配關(guān)系。

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

4.1 亮度序局部特征描述實(shí)驗(yàn)及分析

為了驗(yàn)證本文給出的亮度序局部特征描述算法的性能，采用［13］中提供的數(shù)據(jù)集圖像序列，分別用SIFT、GLOH、CS?LBP以及本文提出的算法對(duì)圖像特征進(jìn)行描述，計(jì)算各特征描述之間的歐氏距離，并以最簡(jiǎn)單的最近鄰、次近鄰距離比作為度量進(jìn)行匹配，最后采用查全率和1?查準(zhǔn)率準(zhǔn)則［14］來(lái)對(duì)特征描述的性能進(jìn)行評(píng)價(jià)：

圖3、4分別為亮度變化和旋轉(zhuǎn)變換圖像序列，每一組圖像序列都包含5幀圖像（這里只列出了第1幀和最后一幀），將第1幀作為參考圖像，其他4幀和參考幀進(jìn)行匹配，圖5、6給出了第1幀和第5幀相應(yīng)的匹配結(jié)果。從實(shí)驗(yàn)結(jié)果可以看出，本文給出的特征描述算法具有更好的亮度和旋轉(zhuǎn)不變性。

圖3 Leuven（亮度變化）圖像序列Fig.3 Image sequences of Leuven（illumination changes）

圖4 New York（旋轉(zhuǎn)變換）圖像序列Fig.4 Image sequences of New York（rotation trans?form）

圖5 Leuven圖像序列實(shí)驗(yàn)結(jié)果Fig.5 Results of image sequences of Leuven

圖6 New York圖像序列實(shí)驗(yàn)結(jié)果Fig.6 Results of image sequences of New York

4.2 圖匹配實(shí)驗(yàn)及分析

為了驗(yàn)證結(jié)合亮度序局部特征描述的圖匹配算法的精度，設(shè)計(jì)了如下實(shí)驗(yàn)：從數(shù)據(jù)集中取出2幅“graf”待匹配的圖像，利用Hessian?Affine方法對(duì)其中一幅圖像檢測(cè)特征點(diǎn)及特征區(qū)域，由提供的單應(yīng)矩陣獲取另一幅圖像中對(duì)應(yīng)的特征點(diǎn)的特征區(qū)域，然后利用本文的算法進(jìn)行匹配，統(tǒng)計(jì)正確匹配點(diǎn)對(duì)的數(shù)目。實(shí)驗(yàn)提取的待匹配的特征點(diǎn)數(shù)目為95對(duì)，初始匹配后得到67對(duì)正確匹配點(diǎn)對(duì)，匹配正確率為70.5%；經(jīng)過(guò)12次迭代后，正確匹配點(diǎn)數(shù)88對(duì)，正確率為92.6%，如圖7所示。圖8給出了正確匹配率隨迭代次數(shù)變化的曲線。從實(shí)驗(yàn)結(jié)果可以看出，由于初始匹配正確率較高，使得在松弛迭代匹配過(guò)程中收斂較快。

圖7 迭代12次匹配結(jié)果Fig.7 Result of 12thiteration

圖8 正確匹配率隨迭代次數(shù)變化曲線Fig.8 The change curve of correct matching rate

接著，將本文的圖匹配算法與文獻(xiàn)［5］中基于譜分解的圖匹配算法（N?SVD）及文獻(xiàn)［7］中基于局部形狀上下文局部特征描述的松弛迭代匹配算法（QLRSC）進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)采用了數(shù)據(jù)集中Boat序列圖像中的第1幀和第5幀，分別利用本文算法、N?SVD譜匹配算法和QLRSC算法對(duì)該序列圖像進(jìn)行匹配，表1給出了匹配的結(jié)果。

表1 Boat序列圖像在不同算法下的匹配結(jié)果數(shù)據(jù)Table1 The matching results for Boat image sequence in different algorithms

從實(shí)驗(yàn)結(jié)果中可以看出，當(dāng)圖像之間存在較小的仿射變換時(shí)，3種算法算法都能取得較好的匹配結(jié)果，但是隨著仿射變換的增大，本文算法匹配正確率明顯高于基于譜分解的圖匹配算法和基于局部形狀上下文的松弛迭代算法。

5 結(jié)束語(yǔ)

針對(duì)基于松弛迭代的圖匹配方法中初始值估計(jì)問(wèn)題，本文給出了一種結(jié)合亮度序局部特征描述的圖匹配算法。該算法利用亮度序約束關(guān)系對(duì)圖像局部特征區(qū)域進(jìn)行劃分，并且通過(guò)改進(jìn)CS_LBP來(lái)對(duì)這些區(qū)域進(jìn)行特征描述，然后用得到的局部特征描述之間的距離初始化圖匹配關(guān)系矩陣，最后通過(guò)松弛迭代的方法得到最終匹配結(jié)果。大量實(shí)驗(yàn)結(jié)果表明，本文的亮度序局部特征描述在亮度單調(diào)變化、縮放以及JPEG壓縮等條件下優(yōu)于SIFT、GLOH等傳統(tǒng)局部特征描述，并且本文提出的圖匹配算法匹配精度較高。

［1］CONTE D，F(xiàn)OGGIA P，SANSONE C，et al.Thirty years of graph matching in pattern recognition［J］.Special Edition of the International Journal of Pattern Recognition and Artificial Intelligence on Graph Theory in Vision，2004，18（3）：265?298.

［2］DUCHENNE O，BACH F，KWEON I S，et al.A tensor?based algorithm for high?order graph matching［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（12）：2383?2395.

［3］ZASLAVSKIY M，BACH F，VERT J P.A path following al?gorithm for the graph matching problem［J］.IEEE Transac?tions on Pattern Analysis and Machine Intelligence，2009，31（12）：2227?2242.

［4］劉智勇.圖模型匹配：一種新的凹松弛函數(shù)及算法［J］.自動(dòng)化學(xué)報(bào)，2012，38（5）：725?731.LIU Zhiyong.Graph matching：a new concave relaxation function and algorithm［J］.Acta Automatica Sinica，2012，38（5）：725?731.

［5］TANG Jun，LIANG Dong，WANG Nian，et al.A Laplacian spectral method for stereo correspondence［J］.Pattern Rec?ognition Letters，2007，28（12），1391?1399.

［6］YUE Sicong，WANG Qing，ZHAO Rongchun.Robust wide baseline point matching based on scale invariant feature de?scriptor［J］.Chinese Journal of Aeronautics，2009，22（1）：70?74.

［7］ZHENG Y，DOERMANN D.Robust point matching for non?rigid shapes by preserving local neighborhood structures［J］.IEEE Transactions on Pattern Analysis and Machine Intelli?gence，2006，28（4）：643?649.

［8］梁棟，朱明，唐俊，等.基于局部相對(duì)形狀上下文與Q?譜的點(diǎn)模式匹配算法［J］.電子學(xué)報(bào)，2012，40（4）：636?641.LIANG Dong，ZHU Ming，TANG Jun，et al.A point pattern matching algorithm based on local relative shape context and Q?spectra［J］.Acta Electronica Sinica，2012，40（4）：636?641.

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

［10］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Transaction on Pattern Anal? ysis and Machine Intelligence，2005，27（10）：1615?1630.

［11］HEIKKIL? M，PIETIK?INEN M，SCHMID C.Description of interest regions with local binary patterns［J］.Pattern Recognition，2009，42（3）：425?436.

［12］MIKOLAJCZYK K，TUYTELAARS T，SCHMID C，et al.A comparison of affine region detectors［J］.International Journal of Computer Vision，2005，65（1?2）：43?72.

［13］KRYSTIAN M.Test image data［EB／OL］.（2012?12?20）.http：／／www.robots.ox.ac.uk／～vgg／research／affine／.

［14］FAN B，WU F C，HU Z Y.Rotationally invariant descrip?tors using intensity order pooling［J］.IEEE Trans on Pat?tern Analysis and Machine Intelligence，2012，34（10）：2031?2045.

A graph matching algorithm with brightness order local feature description

BAO Wenxia1，2，HU Gensheng1，2，LIANG Dong1，2，ZHANG Yan1，2
（1.Key Laboratory of Intelligent Computing＆Signal Processing，Ministry of Education，Anhui University，Hefei 230039，China；2.School of Electronics and Information Engineering，Anhui University，Hefei 230601，China）

In the graph matching problem，whether the method based on relaxation iteration can converge to a global optimal solution depends on the initial estimate to a great extent.Therefore，a graph matching algorithm combined with brightness order local feature description is presented.Firstly，feature points and local feature regions are ex?tracted by Hessian?Affine.The structural graph is obtained by using each feature point as a node and combining with adjacency relationship of feature points.Secondly，each local feature region is partitioned into sub regions u?sing the constraint of brightness order.Then the improved center?symmetric local binary pattern（CS?LBP）is used to describe the local feature.Finally，the similarity of local feature description is used to initialize the matching of the graphs，and after relaxation iteration，the exact matching of feature points is achieved.Experimental results showed that the algorithm has high matching accuracy.

brightness order；local feature description；graph matching；CS?LBP；relaxation iteration

10.3969／j.issn.1006?7043.201311085

http：／／www.cnki.net／kcms／detail／23.1390.U.20150109.1456.002.html

TP391

A

1006?7043（2015）03?0399?05

2013?11?24.網(wǎng)絡(luò)出版時(shí)間：2015?01?09.

國(guó)家自然科學(xué)基金資助項(xiàng)目（61401001，61172127）；安徽省自然科學(xué)基金資助項(xiàng)目（1208085QF104）；安徽省高校優(yōu)秀青年人才基金資助項(xiàng)目（2012SQRL017ZD）.

鮑文霞（1980?），女，副教授，博士；梁棟（1963?），男，教授，博士生導(dǎo)師.

梁棟，E?mail：dliang＠ahu.edu.cn.