面向圖匹配的屬性關(guān)系圖模型

姚 強，朱 明，唐 俊，張 艷(安徽大學(xué)電子信息工程學(xué)院，合肥23060)

2(偏振光成像探測技術(shù)安徽省重點實驗室，合肥230031)E-mail:zhuming@ahu.edu.cn

1 引言

圖像匹配［1，2］是計算機科學(xué)理論中的一個基本問題，它涉及計算機視覺、模式識別和機器學(xué)習(xí)等各個研究領(lǐng)域［3-5］.利用圖模型［6-8］描述圖像特征點間的空間結(jié)構(gòu)關(guān)系完成匹配是近年來的研究熱點，它將圖像的結(jié)構(gòu)匹配問題轉(zhuǎn)化為圖匹配問題，圖匹配方法包括模型構(gòu)建和優(yōu)化算法兩部分.Leordeau 等［9］提出一種譜匹配算法(Spectral Matching，SM)，該算法首先為待匹配點集構(gòu)造分配圖，并利用成對約束條件構(gòu)造相應(yīng)的親鄰矩陣，然后用譜分解方法獲得親鄰矩陣的最大特征值對應(yīng)的特征向量，最后利用此特征向量實現(xiàn)點集之間的匹配.Aguilar等［10］提出一種圖變換匹配算法(Graph Transformation Matching，GTM)來實現(xiàn)特征點匹配，首先對兩幅圖像的特征點集構(gòu)造k近鄰圖，然后根據(jù)一個準(zhǔn)則去除離群點后，迭代地更新近鄰圖.文獻［11］提出一種迭代投影的匹配方法，該方法主要是在優(yōu)化匹配目標(biāo)函數(shù)的過程中，通過迭代投影，使得匹配的解最終能夠滿足匹配問題的約束要求.文獻［12］對相關(guān)點集構(gòu)造賦權(quán)完全圖，再對每個點關(guān)聯(lián)的部分邊構(gòu)造線圖，然后根據(jù)線圖的Laplacian矩陣分解后的特征值計算特征點間的匹配概率，最后通過KM算法求得最優(yōu)匹配.Yang［13］等提出了距離、方向矩陣和凸凹松弛求解策略，但是由所有特征點的中心位置構(gòu)造的參考方向，在圖像形變較大時存在較大偏差，導(dǎo)致匹配效果不好.文獻［14］在邊的屬性上考慮了方向性，提出了可用于無向圖和有向圖的親和度矩陣分解方法和對目標(biāo)函數(shù)求解的方法.在大多數(shù)圖模型的構(gòu)造中，對于特征點和邊的初始描述都是基于距離或者角度信息，但它們對圖像形變較大的場景下是敏感的，在邊上考慮了方向信息可以提高模型的信息量，但簡單而有效的，對圖像之間的變換具有不變、魯棒的特征描述是所有基于特征的匹配方法中的核心問題.

為了提高圖像匹配的精度和匹配方法的適應(yīng)能力，本文提出了一種面向圖匹配的屬性關(guān)系圖模型，利用圖像中特征點相對于特征中心點的分布情況為特征點設(shè)定屬性，根據(jù)特征點連線兩側(cè)的點數(shù)作為邊的屬性值，并可以為邊增加方向信息，以此構(gòu)造圖像之間的親和矩陣，然后根據(jù)整數(shù)約束下的迭代求解算法求解匹配問題.提出的特征模型能很好地描述圖像中特征點間和邊間的關(guān)聯(lián)信息，通過整數(shù)約束下的迭代求解算法能夠求得高正確率的匹配矩陣.

2 基本概念

圖能夠很好地描述圖像中目標(biāo)的結(jié)構(gòu)信息.設(shè)屬性關(guān)系圖G是由有限個非空的頂點集合V和節(jié)點間對應(yīng)的邊的集合E及頂點和邊屬性組成的四元組，記作G=(V，E，A，R)，V={v1，v2，…，vn}，n=|V|表示頂點或者節(jié)點的個數(shù)，E={e1，e2，…，em}，m=|E|表示圖G邊的個數(shù)，對于屬性關(guān)系圖G，圖的每個頂點vi∈V都賦有特征點屬性值ai∈A，圖的每條邊eij∈E也賦有關(guān)系屬性值rij∈R.為了實現(xiàn)兩個屬性關(guān)系圖的頂點匹配，首先要定義兩個圖的頂點間和邊之間的相似性或者親密性.

所以對無向圖的邊進行定向，可使圖像間的結(jié)構(gòu)信息更加豐富.在單有向圖上使用兩個特征點間的一些屬性值的大小來設(shè)定邊的方向，不僅可以區(qū)分出邊eij和eji的屬性不同，即rij≠rji，同時還可以隱含著有關(guān)特征點屬性值的大小關(guān)系信息.在這種情況下也可得到兩幅圖像間的不對稱的親和矩陣 K，即

3 屬性關(guān)系圖模型

圖模型是一種典型的結(jié)構(gòu)描述模型，除了節(jié)點本身，它還可以描述節(jié)點與節(jié)點之間的關(guān)系.屬性關(guān)系圖是用來描述兩圖間頂點與頂點間，邊與邊之間的相關(guān)性，大多數(shù)構(gòu)造方法是基于兩個邊的邊長或者角度的關(guān)系，不適應(yīng)于圖像形變較大的情況下，所以簡單而有效的描述方法是十分必要的.

因為在圖像發(fā)生的各種變換下，比如旋轉(zhuǎn)、尺度變換等，圖像的特征點都會隨著圖像做變換，即各個特征點之間的相對方位基本是不變的，如圖1所示，V1={v1，v2，…，vn}是左邊圖G1中的特征點集，o是點集的中心點.V2={v'1，v'2，…，v'n}是右邊圖G2的特征點集，O'是點集的中心點，vi指向vj的連線lij將左圖G1分成兩部分，其在右圖G2上的匹配點v'i指向v'j的連線l'ij將圖G2分成兩部分，連線左邊的特征點數(shù)目都為1，右邊的特征點數(shù)目都為3.左圖G1上vi指向O的連線lio將點集分成兩部分，連線左側(cè)的特征點數(shù)目為3，其對應(yīng)的右圖G2上v'i指向O'連線l'io左側(cè)的特征點數(shù)目也為3.

圖1 方向描述符的構(gòu)造Fig.1 Construction of direction descriptors

在各種變換下，連線左邊的點在變換后一般是不會出現(xiàn)在連線右邊的，所以就保證了描述符的穩(wěn)定性.使用特征點與特征中心點連線左側(cè)的特征點數(shù)目作為特征節(jié)點的屬性值，則親和矩陣K的對角元素可由公式(2)計算得到.

其中，Nio表示圖G1特征點vi面向中心點O的連線lio左側(cè)的特征點數(shù)目，N'i'o表示圖G2特征點v'i面向中心點O'的連線l'io左側(cè)的特征點數(shù)目，γ是常數(shù)因子.

則親和矩陣K的非對角元素可由式(3)計算得到，

其中，Nij表示圖G1的特征點集中特征點vi面向特征點vj的連線lij左半部分的特征點的總數(shù)目，則N'i'j'表示圖G2的特征點集中特征點v'i面向特征點v'j的連線l'ij左半部分的特征點的總數(shù)目.對于連接線上的S(S≥2)個點，用特征中心點O的位置判斷，即對于在連線上的點，如果特征點中心在連線的左側(cè)，則計算的特征點數(shù)目增加S個.由于Nij≠Nji，則親和矩陣K 是非對稱的.

屬性關(guān)系圖模型匹配問題可用以下數(shù)學(xué)模型來描述，即

其中，置換矩陣X∈P保證了圖頂點匹配的一對一約束，P是置換矩陣集合，滿足式(5).

文中采用整數(shù)約束下的迭代求解方法［15］求解該匹配的數(shù)學(xué)模型，從而得到匹配結(jié)果.該整數(shù)約束下的迭代求解方法是以任意初始解vec(Xk)為輸入，通過迭代求解的方法，尋找滿足式(4)所示約束下的最優(yōu)解.

4 算法流程

根據(jù)式(1)-式(3)可計算得到圖G1和圖G2間的親和矩陣K，考慮到圖G2相對于參考圖G1可能存在鏡像變換，在對參考圖G1求頂點和邊的屬性時，利用連線左側(cè)的特征點求頂點和邊的屬性，對于圖G2會分兩種情況，一種是利用連線左側(cè)的特征點數(shù)目計算頂點和邊的屬性，另一種是利用連線右側(cè)的特征點數(shù)目計算頂點和邊的屬性，所以在兩種不同情況下會得到兩種不同的親和矩陣K1和K2，然后采用整數(shù)約束下的迭代算法求解對應(yīng)的匹配置換矩陣X1和X2，并可得到對應(yīng)的目標(biāo)函數(shù)值J1和J2，根據(jù)比較目標(biāo)函數(shù)值，選擇最大目標(biāo)函數(shù)值對應(yīng)的置換矩陣作為最終的匹配矩陣，從而得到兩幅圖像間特征點的匹配對應(yīng)關(guān)系.本文算法的具體流程如下:

1)對于圖 G1和圖 G2的特征點集 V1={v1，v2，…，vn}和，分別求出兩點集的中心點 O 和 O'.

2)求出V1特征點集中的所有特征點與中心點O連線的左側(cè)的特征點數(shù)目和V2特征點集中特征點與中心點O'連線的左側(cè)的特征點數(shù)目，按照公式(2)計算得到親和矩陣K1的對角元素值.再根據(jù)V1中特征點與中心點O連線的左側(cè)特征點數(shù)目和V2特征點集中特征點與中心點O'連線的右側(cè)的特征點數(shù)目，按照公式(2)計算得到親和矩陣K2的對角元素值.

3)對于V1和V2特征點集，求出所有不同特征點之間的連線左側(cè)的特征點的數(shù)目，然后根據(jù)公式(1)和公式(3)求出親和矩陣K1的非對角元素值.

4)然后根據(jù)親和矩陣K1，并采用整數(shù)約束下的迭代求解方法得到置換矩陣X1，計算得到對應(yīng)的目標(biāo)函數(shù)值J1.

5)對于V2特征點集，求出所有特征點之間的連線右側(cè)的特征點的數(shù)目，結(jié)合V1特征點集中特征點間連線左側(cè)的特征點數(shù)目，根據(jù)公式(1)和公式(3)求出親和矩陣K2的非對角元素值，并求出對應(yīng)的置換矩陣X2和對應(yīng)的目標(biāo)函數(shù)值J2.

6)比較J1和J2的值，選擇大的目標(biāo)函數(shù)值對應(yīng)的置換矩陣作為最終匹配矩陣，輸出匹配結(jié)果.

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

為驗證文中算法的性能，選用 SM 算法［16］、PM 算法［17］、FGM 算法［14］、Yang 算法［13］與文中算法 Ours進行對比.Yang算法中距離矩陣和方向矩陣的權(quán)值都為0.5.實驗分為在House數(shù)據(jù)集和真實圖像數(shù)據(jù)集上的實驗.

5.1 House圖像數(shù)據(jù)集匹配

CMU數(shù)據(jù)圖像庫中的House圖像序列經(jīng)常被用于測量圖匹配算法的性能，這個數(shù)據(jù)集由111個房屋組成，每個房屋上都有對應(yīng)的30個特征點，以0序列圖像作為參考圖像，以0:10:110的幀間隔圖像作為待匹配圖像，計算得到各算法的匹配正確率.幾種算法關(guān)于匹配正確率的對比結(jié)果如圖2所示.

圖2 幾種算法在house圖像上的匹配正確率對比Fig.2 Comparison of matching accuracy of several algorithms on house image

由圖2可知，隨著圖像間幀數(shù)的增加，House圖像間得形變變大，PM、SM算法的匹配正確率呈現(xiàn)明顯的下降趨勢，Yang算法只在110幀時出現(xiàn)了錯誤的匹配對，在所有的House圖像序列上，文中Ours算法和FGM算法都考慮了方向信息，它們的匹配正確率都等于1，都是完全正確的.

5.2 真實數(shù)據(jù)圖像匹配

為了進一步測量算法在形變較大的圖像上的匹配性能，采用四組真實實驗數(shù)據(jù)的序列圖像進行實驗，如圖3所示，第一、三、四組是來自Mikolajczyk測試數(shù)據(jù)集的包含視點變化的“graf”圖像和包含尺度和旋轉(zhuǎn)變換的“bark”和“boat”圖像，第二組為 MorelYu數(shù)據(jù)集中包含尺度和經(jīng)度變化的“paint”圖像，每組序列圖像中各取5幅逐漸變化的圖像，隨著序列數(shù)的增加圖像的形變逐漸變大.

圖3 真實實驗數(shù)據(jù)圖像Fig.3 Real experimental data image

在四組序列圖像上手動提取特征點對，對于第一組和第四組的序列圖像分別提取60個特征點，對于第二組序列圖像分別提取35個特征點，對第三組序列圖像分別提取30個特征點.對所有特征點集的順序隨機打亂，幾種算法在真實圖像上關(guān)于正確率的實驗對比結(jié)果如表1所示.

表1 幾種算法關(guān)于匹配正確率的對比Table 1 Comparison of matching accuracy with several algorithms

隨著圖像序列的增加，圖像間的形變在逐步增大，由表1知，本文Ours方法在兩組序列圖像上的匹配正確率均是最高，其它算法匹配正確率在逐漸降低，逐漸趨于0，F(xiàn)GM算法在構(gòu)造親和矩陣的時候考慮了方向信息，Yang算法在構(gòu)造鄰接矩陣的時候也考慮了方向約束，這兩個算法總的效果在除了文中Ours算法之外效果最好.在本文算法下對方向的判斷標(biāo)準(zhǔn)對仿射變換是不變的，所以能保證在兩幅圖像間構(gòu)造的親和矩陣能準(zhǔn)確的描述圖像間邊與邊，點與點間的親近值，在各類的圖像變換類型下能保證具有較高的匹配正確率.圖4為幾種算法在序列圖像上的匹配結(jié)果，其中圖4(a)-(e)為本文Ours算法與Yang算法、DGM算法、PM算法和SM算法在“graf”的“1-5”序列圖像上的匹配結(jié)果，圖4(f)-圖4(h)為本文 Ours算法在“paint”的“10-80”序列圖像上、“bark”的“1-6”序列圖像上和“boat”的“0-60”序列圖像上的匹配結(jié)果.

圖4 幾種算法在真實圖像上的匹配結(jié)果Fig.4 Matching results of several algorithms on real images

6 結(jié)束語

本文提出了一種面向圖匹配的屬性關(guān)系圖模型，該模型利用特征點集的分布情況構(gòu)造表示頂點之間和邊之間屬性的親和矩陣，在構(gòu)造邊的屬性時考慮了方向信息，并利用整數(shù)約束下的迭代求解算法求解匹配矩陣，得到特征點間的一對一匹配關(guān)系.實驗結(jié)果表明，該屬性關(guān)系圖模型的圖匹配算法有較好的匹配效果，且對于形變較大的圖像也有很好的匹配效果.