基于迭代重加權(quán)的高階張量圖匹配算法

徐國(guó)夏， 韓立新， 石冰,2

(1.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院， 南京 211100; 2.安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院， 安慶 246000)

0 引言

圖匹配問(wèn)題在計(jì)算機(jī)視覺(jué)和模式識(shí)別中是一個(gè)非?；A(chǔ)且重要的問(wèn)題。圖匹配作為圖像相似性度量的一種方法，多用于圖像分析處理等任務(wù)。例如遙感圖像融合處理、醫(yī)學(xué)圖像處理，航空影像自動(dòng)制圖等方面。在諸多應(yīng)用驅(qū)動(dòng)下產(chǎn)生了一系列實(shí)際場(chǎng)景，例如圖像檢索[1]、形狀匹配[2]、目標(biāo)追蹤[3]等。圖匹配基于圖模型描述圖像特征，通過(guò)節(jié)點(diǎn)和邊來(lái)表示圖像特征元素和圖像特征元素之間的關(guān)系。這是對(duì)圖像從像素級(jí)特征表示到高級(jí)語(yǔ)義級(jí)特征表示的拓展，具有表示復(fù)雜視覺(jué)模式的能力。近年來(lái)，研究工作者逐漸開(kāi)始關(guān)注高階圖匹配，其利用張量的結(jié)構(gòu)表示特征點(diǎn)集間的高階圖結(jié)構(gòu)關(guān)系，能更好地解決圖像特征表示與建模的歧義性問(wèn)題。高階圖匹配[7]利用超圖(Hyper-graph)來(lái)對(duì)應(yīng)構(gòu)建視覺(jué)特征集之間的關(guān)系，超圖是3個(gè)特征點(diǎn)或者是3個(gè)以上特征點(diǎn)集對(duì)之間的關(guān)系。

從優(yōu)化角度來(lái)說(shuō)，圖匹配問(wèn)題其本質(zhì)上是一種離散組合優(yōu)化問(wèn)題，其本身具有NP(non-deterministic polynomial) hard性質(zhì)。因此大多數(shù)圖匹配的解決方案是從優(yōu)化角度出發(fā)尋找有效的近似算法[4]，首先對(duì)匹配問(wèn)題的離散約束進(jìn)行一定程度上的松弛，再對(duì)松弛后的問(wèn)題利用優(yōu)化方法進(jìn)行求解。圖匹配方法中比較有代表性的方法有：基于譜方法，Leordanu等[5]提出了譜匹配SM(Spectral Matching)方法。 基于雙隨機(jī)約束松弛方法，Zaslavskiy等[6]基于凹凸松弛提出了一種(path-following)的方法，將圖匹配問(wèn)題松弛成了目標(biāo)函數(shù)的凸和凹松弛問(wèn)題。但是基于譜方法和雙隨機(jī)約束松弛的方法忽視了匹配問(wèn)題的離散約束性，故越來(lái)越多基于稀疏約束的匹配方法增加稀疏約束來(lái)獲得更有效的稀疏優(yōu)化解。

Duchenne等[7]將高階圖匹配TM(Tensor Matching)問(wèn)題形式化成一個(gè)三階張量的目標(biāo)函數(shù)，結(jié)合L1范數(shù)并得到匹配的稀疏解。文獻(xiàn)[9]證明了L1/2范數(shù)其具有無(wú)偏性、稀疏性等良好的理論性質(zhì)，其在變量選擇和特征提取上的表現(xiàn)優(yōu)于L1范數(shù)和L2范數(shù)。為進(jìn)一步探索稀疏優(yōu)化技術(shù)在圖匹配中的應(yīng)用，本文將高階張量圖匹配模型與L1/2范數(shù)結(jié)合，通過(guò)迭代重加權(quán)的優(yōu)化方式近似求解該正則子，提出了基于L1/2范數(shù)重加權(quán)改進(jìn)的高階圖匹配算法(Iterative Reweight High-order Graph Matching, IRHGM)，力求在所構(gòu)建的非凸非光滑的模型上取得最優(yōu)的解稀疏性和噪聲魯棒性。實(shí)驗(yàn)證明本文的算法比傳統(tǒng)方法具有更高的匹配正確率及更強(qiáng)的魯棒性。

1 原理背景

1.1 基于張量高階圖匹配模型

基于張量的高階圖匹配算法在二階譜匹配的基礎(chǔ)上拓展而來(lái)，從點(diǎn)對(duì)點(diǎn)(point-to-point)、線對(duì)線(line-to-line)拓展到三角結(jié)構(gòu)到三角結(jié)構(gòu)(triple-to-triple)。拓展的不僅僅是比較的數(shù)量級(jí)，更多的是在模型上從原來(lái)的線性向非線性的推廣。利用三階張量結(jié)構(gòu)信息更能覆蓋目標(biāo)特征點(diǎn)之間的多重幾何組合關(guān)系，對(duì)噪聲、尺度不變性、仿射不變性、分辨率、視角變化等的干擾具有更強(qiáng)的魯棒性。張量(tensor)[8]是多維矩陣的拓展，張量可以由諸多基于若干個(gè)坐標(biāo)系中發(fā)生轉(zhuǎn)換關(guān)系改變的集合分量定義。N階張量表示為A∈RL1×L2×…×LN,A中的元素表示為xl1l2…ln。與矩陣的Frobenius范數(shù)類似，張量的F范數(shù)可以表示成式(1)。

(1)

高階圖匹配中利用高階圖結(jié)構(gòu)信息來(lái)構(gòu)建關(guān)系張量A，首先在特征點(diǎn)集中選取(i,j,k) 三個(gè)點(diǎn)，組成一個(gè)點(diǎn)集元組，該元組相似度量值由其組成的三角形結(jié)構(gòu)信息fi,j,k，和另一個(gè)相對(duì)應(yīng)元組fi′,j′,k′來(lái)度量為式(2)。

(2)

關(guān)系張量A是一個(gè)超對(duì)稱的張量，以稀疏存儲(chǔ)的方式存儲(chǔ)坐標(biāo)及相對(duì)應(yīng)度量值。基于張量表示的高階圖匹配模型能夠自然地對(duì)高階結(jié)構(gòu)內(nèi)在的幾何結(jié)構(gòu)和關(guān)聯(lián)關(guān)系進(jìn)行描述，解決了圖像特征表示的結(jié)構(gòu)化建模。

基于候選匹配進(jìn)行矩陣約束可以將其劃分成一個(gè)二次分配問(wèn)題，該目標(biāo)函數(shù)通過(guò)對(duì)關(guān)系矩陣的行列約束得到最優(yōu)匹配結(jié)果為式(3)。

(3)

高階圖匹配問(wèn)題是在矩陣基礎(chǔ)上推廣成高階張量表達(dá)，定義了與張量有關(guān)的目標(biāo)函數(shù)為式(4)。

(4)

在兩組點(diǎn)集中{P}和{Q}，其點(diǎn)集中特征點(diǎn)個(gè)數(shù)分別是p,q。該高階匹配模型的目標(biāo)是在點(diǎn)集中找到相對(duì)應(yīng)的點(diǎn)集對(duì)關(guān)系，匹配解X是由0,1組成的分配矩陣。高階匹配模型是在三組約束下，通過(guò)尋找相似三角形對(duì)來(lái)得到最優(yōu)匹配結(jié)果。將分配矩陣X重新向量化為x=vec(X)，大小為N=pq。模型(4)可以用tensor-vector乘法的定義為式(5)。

?ixi?jxj?kxk

(5)

?表示為Kronecker積的形式表達(dá)。

1.2L1/2范數(shù)

近些年發(fā)展起來(lái)的正則化方法在變量選擇和特征提取等工作上得到廣泛應(yīng)用。如圖1所示。

使用等距角度，將這些點(diǎn)投射在球上。使用標(biāo)準(zhǔn)圖的連接線繪制排序點(diǎn)，以前在2-norm或者1-norm球上的等距點(diǎn)現(xiàn)在非常稀疏接近0.5-norm球。從直觀的幾何角度分析上來(lái)看，L1/2范數(shù)與L2、L1范數(shù)相比較曲線更加平緩，處在兩者之下，更易于相交于等高線。因此L1/2范數(shù)的解會(huì)比其余兩者更具稀疏性。

在諸多范數(shù)中，L0對(duì)應(yīng)的是最優(yōu)的變量選擇結(jié)果，但是它本身就是一個(gè)NP問(wèn)題。故一些工作已經(jīng)證明L1已經(jīng)在某種意義下是等價(jià)于L0的。L1/2范數(shù)是更具有應(yīng)用價(jià)值的。Ochs等[10]研究將L1/2范數(shù)近似為重加權(quán)L1范數(shù)，更能產(chǎn)生稀疏的解。同時(shí)在求解L1/2范數(shù)的迭代算法問(wèn)題上，利用已有的L1范數(shù)進(jìn)行賦權(quán)求解。并且也證明了L1/2范數(shù)收斂性。

求解L1/2范數(shù)的算法流程如式(16)。

步驟1：初始化模型：

xt=(1,…,1)T,t=0

(6)

步驟2： 轉(zhuǎn)化為模型：

步驟3：當(dāng)t

2 改進(jìn)的基于L1/2范數(shù)的迭代重加權(quán)高階張量圖匹配模型

s.t.?x∈[0,1]

(7)

模型(7)對(duì)分配矩陣X中的每個(gè)列分量xi進(jìn)行約束，約束每一變量值在[0, 1]之間，λ控制模型復(fù)雜度。模型(7)是一個(gè)非凸非光滑的目標(biāo)函數(shù)，相較于原始模型，通過(guò)L1/2范數(shù)控制解的稀疏性。同時(shí)本文也提出相對(duì)應(yīng)的基于迭代重加權(quán)方法估計(jì)非光滑范數(shù)，將其近似為加權(quán)L1范數(shù)，如式(8)。

s.t.?x∈[0,1]

(8)

對(duì)于該模型的加權(quán)的L1范數(shù)，繼續(xù)利用張量?jī)绲M(jìn)行推導(dǎo)?；趶埩?jī)绲募s束優(yōu)化問(wèn)題(8)的Lagrange函數(shù)定義為式(9)。

(9)

(10)

算法1：基于迭代重加權(quán)的高階圖匹配算法(IRHGM)

輸出：分配矩陣X

1) 初始化X={1,…,1}T

直到收斂

3 實(shí)驗(yàn)結(jié)果及分析

本文提出的基于L1/2范數(shù)的IRHGM算法，實(shí)驗(yàn)對(duì)象在House dataset標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行驗(yàn)證。本算法實(shí)驗(yàn)平臺(tái)Intel(R) Xeon(R)， 3.47GHz，CPU，Window7操作系統(tǒng)的PC，算法使用Matlab+Mex混合編程實(shí)現(xiàn)。本文提出的算法在下列3個(gè)方面均衡評(píng)價(jià)，對(duì)解集稀疏性，匹配準(zhǔn)確率和抗噪魯邦性進(jìn)行實(shí)驗(yàn)比較。對(duì)比了基于L1范數(shù)張量匹配方法TM(Tensor Matching)[6]和基于L2范數(shù)譜匹配方法SM(Spectral Matching)[8]。

首先實(shí)驗(yàn)利用在準(zhǔn)備實(shí)驗(yàn)數(shù)據(jù)點(diǎn)的時(shí)候，利用SIFT描述子提取候選備用點(diǎn)，分別提取30，40，50，60個(gè)實(shí)驗(yàn)節(jié)點(diǎn)。然后利用knn算法尋找出盡可能相似的三角形組合，分別可以尋找出630000，1120000，1892800，2520000個(gè)組合。在此基礎(chǔ)上構(gòu)建稀疏張量，這是一個(gè)非常大的稀疏張量，在這個(gè)張量空間中挖掘匹配結(jié)果。匹配準(zhǔn)確率結(jié)果，如圖2所示。

圖2 不同實(shí)驗(yàn)節(jié)點(diǎn)個(gè)數(shù)下相應(yīng)TM，SM，

L1/2范數(shù)的高階圖匹配模型IRHGM的匹配準(zhǔn)確率結(jié)果要優(yōu)于其他算法。

分配矩陣X的稀疏性結(jié)果比較，如圖3所示。

表明了IRHGM優(yōu)于TM(基于L1范數(shù))算法收斂得到的解，體現(xiàn)了本文提出算法的優(yōu)越性。同時(shí)IRHGM稀疏性越高的基礎(chǔ)也提高了匹配準(zhǔn)確率。

本文同時(shí)在模型和優(yōu)化方法上進(jìn)行完善，該算法不僅考慮了解的稀疏保持性，同時(shí)更能抵抗匹配噪聲，體現(xiàn)了算法的魯棒性。在待匹配數(shù)據(jù)中增加了隨機(jī)噪聲，如圖4所示。

圖4中右邊圖片增加隨機(jī)噪聲點(diǎn)。不同實(shí)驗(yàn)節(jié)點(diǎn)再增加噪聲點(diǎn)的實(shí)驗(yàn)對(duì)比，比較匹配準(zhǔn)確率?？梢钥闯鯥RHGM在整體準(zhǔn)確率上優(yōu)于其余算法，對(duì)存在噪聲點(diǎn)的情況下仍然不會(huì)降低匹配準(zhǔn)確率，如表1所示。

圖3 本文提出的IRHGM匹配算法與TM匹配算法的解即對(duì)分配矩陣X的稀疏性結(jié)果比較圖(IRHGM匹配正確率93%，TM匹配正確率83%，50個(gè)節(jié)點(diǎn))

L1/2norm

L1 norm

圖4 本文提出的IRHGM匹配算法和TM匹配算法結(jié)果示意圖(連接線兩端指向相同數(shù)字代表匹配正確，數(shù)字不相同和沒(méi)有數(shù)字都代表沒(méi)匹配上，且出現(xiàn)了一對(duì)多的誤匹配)。

本文提出的算法IRHGM融合了高階張量模型和更稀疏的L1/2范數(shù)稀疏約束，在保證全局優(yōu)化基礎(chǔ)上得到有效且稀疏的解，并且實(shí)驗(yàn)結(jié)果也驗(yàn)證了算法對(duì)于噪聲的魯棒性。

表1 在不同噪聲點(diǎn)不同算法的準(zhǔn)確率比較(%)

4 總結(jié)

圖匹配問(wèn)題一直是計(jì)算機(jī)視覺(jué)中的基礎(chǔ)問(wèn)題，本文利用高階張量超圖模型和L1/2范數(shù)，提出了基于L1/2范數(shù)的迭代重加權(quán)高階圖匹配算法，以迭代重加權(quán)的方式近似求解賦權(quán)L1范數(shù)，優(yōu)化高階圖匹配模型。實(shí)驗(yàn)證明本算法不僅得到了更優(yōu)的解稀疏性，更增強(qiáng)了對(duì)匹配噪聲的魯棒性，與相關(guān)算法比，得到了更高的匹配準(zhǔn)確率，能夠更好的將匹配算法輔助運(yùn)用到其他計(jì)算機(jī)視覺(jué)場(chǎng)景[12][13]中。未來(lái)我們考慮將稀疏約束引入多圖匹配中的相關(guān)算法，進(jìn)一步地提升多圖匹配的匹配準(zhǔn)確率。

[1] Helala M A E, Selim M M, Zayed H H. An Image Retrieval Approach Based on Composite Features and Graph Matching[C]. IEEE, International Conference on Computer and Electrical Engineering. 2009, pp:466-473.

[2] Ngo, Quoc-Tao, Duc-Dung Nguyen, and Shu-Chuan Chu. Similarity Shape Based on Skeleton Graph Matching. [J] Journal Info. Multi. Signal Processing, 2016 7(6):1254-1264.

[3] 王治丹, 蔣建國(guó), 齊美彬. 基于最大池圖匹配的形變目標(biāo)跟蹤方法[J]. 電子學(xué)報(bào), 2017, 45(3):704-711.

[4] 江波, 湯進(jìn), 羅斌. 計(jì)算機(jī)視覺(jué)中的圖匹配方法研究綜述[J]. 安徽大學(xué)學(xué)報(bào)(自科版), 2017, 41(1):29-36.

[5] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints [C]. IEEE International Conference on Computer Vision, Beijing, China, October, 2005, pp:1482-1489.

[6] M. Zaslavskiy, F. Bach, and J. Vert. A path following algorithm for the graph matching problem [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12):2227-2242.

[7] O. Duchenne, F. Bach, I.-S. Kweon, and J. Ponce. A tensor-based algorithm for high-order graph matching [J]. IEEE transactions on pattern analysis and machine intelligence, 2011, 33(12):2383-2395.

[8] Papalexakis E E, Faloutsos C, Sidiropoulos N D. Tensors for Data Mining and Data Fusion: Models, Applications, and Scalable Algorithms[M]. ACM, 2016.

[9] 張海, 王堯, 常象宇,和徐宗本. L_(1/2)正則化[J]. 中國(guó)科學(xué):信息科學(xué), vol.40, no.3, pp:412-420, 2010.

[10] P. Ochs A. Dosovitskiy, T. Brox, and T. Pock. On Iteratively Reweighted Algorithms for Nonsmooth Nonconvex Optimization in Computer Vision [J]. Siam Journal on Imaging Sciences, 2015, 8(1):331-372.

[11] Lathauwer L D, Moor B D, Vandewalle J. On the best rank-1 and rank-(R1, R2. . ,RN ) approximation of higher-order tensor[J]. Siam Journal on Matrix Analysis & Applications, 2000, 21(4):1324-1342.

[12] Du D, Qi H, Li W, Huang Q and Lyu S. Online Deformable Object Tracking Based on Structure-Aware Hyper-Graph[J]. IEEE Transactions on Image Processing, 2016, 25(8):3572.

[13] Dutta, Anjan, Josep Lladós, Horst Bunke, and Umapada Pal. Product Graph-based Higher Order Contextual Similarities for Inexact Subgraph Matching[OJ]. 2017. arXiv preprint arXiv:1702.00391