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

（1.安徽大學(xué)計算機智能與信號處理教育部重點實驗室，安徽合肥230039；2.安徽大學(xué)電子信息工程學(xué)院，安徽合肥230601）

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

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

（1.安徽大學(xué)計算機智能與信號處理教育部重點實驗室，安徽合肥230039；2.安徽大學(xué)電子信息工程學(xué)院，安徽合肥230601）

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

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

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

1 圖匹配算法

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

式中：Ki表示X中第i個點即xi的k近鄰，Kj表示Y中第j個點即yj的k近鄰。

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

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

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

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

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

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

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

2 亮度序局部特征描述

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

2.1 區(qū)域劃分

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

Oω＝｛k1，k2，...，kn：I（xk1）≤I（xk2）≤...≤I（xkn）｝再將ω區(qū)域劃分為nbins個子區(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個子區(qū)域。因為亮度單調(diào)變化不改變序的關(guān)系，并且?guī)缀涡D(zhuǎn)也不改變圖像的亮度，因此這種基于亮度序的區(qū)域劃分方法同時具有幾何旋轉(zhuǎn)不變性和亮度單調(diào)變化不變性。

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

2.2 局部特征描述

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

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

圖2 N＝8時的特征值計算示意圖Fig.2 The diagram of feature value calculation for N＝8

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

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

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

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

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

3 算法流程

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

1）利用Hessian?Affine方法來檢測特征點及特征區(qū)域；

2）計算特征點的亮度序局部特征描述；

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

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

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

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

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

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

4 實驗及分析

4.1 亮度序局部特征描述實驗及分析

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

圖3、4分別為亮度變化和旋轉(zhuǎn)變換圖像序列，每一組圖像序列都包含5幀圖像（這里只列出了第1幀和最后一幀），將第1幀作為參考圖像，其他4幀和參考幀進行匹配，圖5、6給出了第1幀和第5幀相應(yīng)的匹配結(jié)果。從實驗結(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圖像序列實驗結(jié)果Fig.5 Results of image sequences of Leuven

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

4.2 圖匹配實驗及分析

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

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

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

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

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

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

5 結(jié)束語

針對基于松弛迭代的圖匹配方法中初始值估計問題，本文給出了一種結(jié)合亮度序局部特征描述的圖匹配算法。該算法利用亮度序約束關(guān)系對圖像局部特征區(qū)域進行劃分，并且通過改進CS_LBP來對這些區(qū)域進行特征描述，然后用得到的局部特征描述之間的距離初始化圖匹配關(guān)系矩陣，最后通過松弛迭代的方法得到最終匹配結(jié)果。大量實驗結(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］.自動化學(xué)報，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］梁棟，朱明，唐俊，等.基于局部相對形狀上下文與Q?譜的點模式匹配算法［J］.電子學(xué)報，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ò)出版時間：2015?01?09.

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

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

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