面向圖匹配的屬性關系圖模型

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

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

1 引言

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

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

2 基本概念

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

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

3 屬性關系圖模型

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

因為在圖像發生的各種變換下，比如旋轉、尺度變換等，圖像的特征點都會隨著圖像做變換，即各個特征點之間的相對方位基本是不變的，如圖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分成兩部分，連線左邊的特征點數目都為1，右邊的特征點數目都為3.左圖G1上vi指向O的連線lio將點集分成兩部分，連線左側的特征點數目為3，其對應的右圖G2上v'i指向O'連線l'io左側的特征點數目也為3.

圖1 方向描述符的構造Fig.1 Construction of direction descriptors

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

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

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

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

屬性關系圖模型匹配問題可用以下數學模型來描述，即

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

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

4 算法流程

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

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

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

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

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

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

6)比較J1和J2的值，選擇大的目標函數值對應的置換矩陣作為最終匹配矩陣，輸出匹配結果.

5 實驗及結果分析

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

5.1 House圖像數據集匹配

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

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

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

5.2 真實數據圖像匹配

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

圖3 真實實驗數據圖像Fig.3 Real experimental data image

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

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

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

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

6 結束語

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