基于線圖Q-譜的點模式匹配算法*

朱明梁棟?唐俊范益政顏普

(1.安徽大學電子信息工程學院，安徽合肥230039;2.安徽大學計算智能與信號處理教育部重點實驗室，安徽合肥230039;3.安徽大學數學科學學院，安徽合肥230039)

點模式匹配是計算機視覺和模式識別領域中的一個重要問題，其主要任務是尋找出相關點集之間的匹配關系，在立體視覺匹配、圖像配準、目標識別與跟蹤等方面有著廣泛的應用.近年來，譜圖理論［1］作為一種有效的數學工具被引入到點模式匹配問題的研究中，并發揮了重要作用.文獻［2］中最早將譜方法應用于點模式匹配，即通過構造圖像之間點的親近矩陣，并對此矩陣進行奇異值分解(SVD)來獲得對應關系.該方法可以處理不同大小點集的匹配問題，但對較大角度的旋轉效果較差.文獻［3］中采用了圖像內部點的親近矩陣來進行匹配，可以處理旋轉問題，但對不同大小點集的匹配效果較差.文獻［3］中方法實際上是對賦權圖的鄰接矩陣進行處理，王年等［4］從賦權圖的矩陣表示入手，用賦權圖的Laplacian矩陣來表示點集中點之間的關系，通過Laplacian譜來完成點集的匹配.為了進一步提高譜方法的性能，人們還使用了一些優化算法.Carcassoni等［5］將譜方法和EM(Expectation Maximization)算法結合起來，通過點的親近矩陣來獲得點匹配的概率，進一步提高算法對點集大小和位置噪聲的魯棒性;Tang等［6］將薄板樣條(TPS)變形模型用于提高Laplacian譜方法的匹配效果.

上述譜方法均側重于強調特征向量的作用，利用特征向量來求解點的匹配，忽略了特征值之間的相似性，雖然文獻［5］中將特征值作為權值加入到匹配概率的求解過程中，但沒有起到主要的作用.利用特征向量來解決匹配問題的優點是構造簡單、計算量小，缺點是當點集的大小不同時，很難獲得較好的匹配效果，這主要是因為特征向量對圖結構特別敏感，當點集大小不同時，所構造的圖結構差異較大，大大降低了特征向量間的相似性，導致匹配結果不理想.

目前，譜圖理論的研究主要集中在圖的特征值方面［7-10］，應用代數和組合的理論，建立圖的特征值和一些不變量之間的聯系.例如，圖的Laplacian矩陣的零特征值的重數等于該圖的連通分支數，Laplacian矩陣的次小特征值又稱為圖的代數連通度，若代數連通度大于0，則圖是連通的;反之，則圖是不連通的.在圖的矩陣表示中，矩陣的全體特征值稱為圖的譜，具有相同譜但不同構的圖稱為同譜圖.有關同譜圖的研究［11］也是譜圖理論的一個重要方面，它將特征值作為相應圖的數字特征，考慮一個圖能否由其特征值所唯一確定，目的是將圖的結構信息通過圖譜反映出來.圖的無符號Laplacian矩陣的研究是近期的一個熱點［11-14］，文獻［11］中指出，由于無符號Laplacian矩陣較其它矩陣(鄰接矩陣、Laplacian矩陣)的同譜圖少，因此無符號Laplacian矩陣的譜(簡稱Q-譜)能夠更好地反映圖的結構信息，更便于研究圖的性質.

文中利用Q-譜(即無符號Laplacian矩陣的全體特征值)來表示點的特征，通過這些特征計算點之間的匹配概率(相似性)，最后通過KM(Kuhn-Munkres)算法［15］來尋找點集之間的最優匹配以完成匹配，其中為了獲得每個點的Q-譜表示，對每個點定義了大小一致的線圖，對線圖的無符號Laplacian矩陣進行譜分解，利用分解所得的特征值來表示點的特征.

1 基本概念

圖是一個有序對(V，E)，V是頂點集，E是邊集，當集合元素個數有限時，(V，E)稱為有限圖，否則稱為無限圖.不含平行邊和自回路的圖稱為簡單圖.每對頂點都有邊相連的簡單圖，稱為完全圖.對于一個完全圖，若對其每條邊賦以一定的值(如邊的長度)，則稱此圖為賦權完全圖.

若頂點vi與vj由一條邊相連，則稱vi與vj鄰接.設G是一個含有n個頂點(v1，v2，…，vn)的圖，則圖G的賦權鄰接矩陣A(G)的元素定義為

在無向圖G=(V，E)中，對邊集E的任一子集M?E，如果M中任意兩條邊都不關聯，則稱M為圖G的一個匹配.G中屬于M的邊稱為匹配邊，匹配邊的兩個端點互為匹配點，所有匹配邊的頂點稱為關于M的飽和點，否則稱為非飽和點.若G的每個頂點都是M的飽和點，則稱M是G的完美匹配.若完美匹配M中邊的權值之和是所有完美匹配中最大的，則稱M為最優匹配.若G中存在一條路徑R，路徑的邊是由屬于M的匹配邊和不屬于M的非匹配邊交替出現組成，且R的兩個端點都是M的非飽和點，則稱這條路徑為可增廣路.

2 線圖的Q-譜

設I、J是兩個相關點集，記I中的點為pi(i=1，2，…，m)，J中的點為qj(j=1，2，…，n)，不失一般性，設m≤n.

對點集I構造賦權完全圖，對任意兩點之間的邊賦以該邊的長度，如此可以得到一個階數為m的賦權完全圖.對于I中的點pi，有m-1條邊與pi相連，分別記為e1≤e2≤…≤em-1(按長度排序)，則前k(2≤k≤m-1)條邊e1，e2，…，ek與pi構成了一個星圖Xi，求Xi的線圖.由于e1，e2，…，ek中任意兩條邊都是關聯的，因此，Xi的線圖是一個k階完全圖Li，對Li構造賦權無符號Laplacian矩陣，其元素為

式中，rjh為ej與eh的長度差.

線圖的求解過程就是將邊變為點的過程，線圖中的點是原圖的邊，點是鄰接的當且僅當原圖中對應的邊是關聯的.如圖1(a)所示，e1、e2、e3為與pi關聯的邊，長分別為1、2、3，相應的線圖(見圖1(b))中，e1、e2、e3分別變為3個點，邊的權分別為e1、e2、e3之間長度差的絕對值.

圖1 線圖的構造Fig.1 Construction of line graph

由于D pi是一個對稱的半正定矩陣，因此對D pi進行譜分解，獲得k個非負特征值λ1(pi)≥λ2(pi)≥…≥λk(pi)≥0，將(λ1(pi)，λ2(pi)，…，λk(pi))作為pi(i=1，2，…，m)的特征.

按照上述方法，對J中第j個點qj(j=1，2，…，n)選取與qj相關聯的前k(2≤k≤m-1)個最短邊來構造線圖，同樣可獲得qj的特征表示

(θ1(qj)，θ2(qj)，…，θk(qj))，

其中θ1(qj)≥θ2(qj)≥…≥θk(qj)≥0.

構建匹配矩陣C，其第i(i=1，2，…，m)行第j(j=1，2，…，n)列的元素為

3 最優匹配

二分圖的最優匹配是圖論中的一個經典問題，它解決的一個典型應用問題如下:假設有n個員工、n項工作，每個員工都能勝任每項工作，但每個員工做每項工作的效率可能不同，并且每個員工最多只能從事一項工作，怎樣給出一個安排方案使總效率最大?

將二分圖的最優匹配應用到點模式匹配中，可以這樣表述，點集I中的每個點與點集J中的每個點都有匹配概率，I中的點與J中的點必須是一一對應的，如何判斷I與J之間點的匹配關系，才能使得總的匹配概率最大(即兩個點集的相似度最大)?解決這個問題的經典有效算法是KM算法［15］.KM算法的具體步驟如下:

1)給出初始標號

b(pi)

3)若I中的所有點都是M的飽和點，則M是G的最優匹配，計算結束.

4)在I中找一非飽和點p0，令

5)若NGb(A)=B，NGb(A)為與A中的點鄰接的所有點構成的集合，則轉步驟9).

6)找點q∈NGb(A)-B.

7)若q是M的飽和點，則找出q的配對點x，，轉步驟5).

8)存在一條從p0到q的可增廣路徑R，令為環和運算，E(R)為R的邊集，轉步驟3).

4 基于線圖Q-譜的點模式匹配

為了判斷I與J之間點的匹配關系，定義I與J之間的相似度為

式中，Pi為I中第i點與J中所選定的匹配點之間的匹配概率.判斷I與J中點之間匹配關系的準則是使得S(I，J)達到最大.在應用Q-譜方法獲得兩個點集中點之間的匹配概率后，以I、J為兩個部分構造二分圖，并在I部分中增加n-m個虛擬點，對二分圖兩部分之間的邊賦以其所連接兩點之間的匹配概率，I部分中n-m個虛擬點與J部分中點之間的邊權賦以0.不難發現，使得S(I，J)最大的匹配關系即是所構造的二分圖的最優匹配.

基于線圖Q-譜的點模式匹配算法的基本思想是:先應用Q-譜方法獲得兩個點集間的匹配概率，然后構造二分圖，最后應用KM算法尋找最優匹配.算法具體步驟如下:

1)為待匹配點集I和J分別構造賦權完全圖GI和GJ;

2)根據GI和GJ，分別利用每個點的前k條最短邊構造相應的線圖;

3)為線圖構造無符號Laplacian矩陣;

4)對無符號Laplacian矩陣進行譜分解，獲得每個點的特征值表示;

5)根據式(3)計算匹配概率;

6)構造二分圖，利用KM算法求解最優匹配，輸出匹配結果.

5 實驗及結果分析

為驗證文中算法的性能，采用該算法與文獻［3-5］中算法進行實驗，其中文獻［3，5］中算法的高斯平滑系數均選為σ=50.

5.1 模擬實驗

模擬數據采用文獻［16］中的合成數據，即由98個離散點構成的魚圖像，分別用文中算法和文獻［3-5］中算法進行實驗.當兩個模擬數據大小一致時實驗結果如圖2(a)和表1所示.由表1可知，4種算法均有較高的匹配正確率，其中文獻［3-4］中算法可以達到80%以上，結合了優化算法的文中算法和文獻［5］中算法的匹配正確率更是達到了100%，這表明了譜方法與優化算法相結合的優勢.

在兩個模擬數據相差5個點的情況下，為了使得文獻［3-5］中算法能夠順利進行匹配，先按照文獻［5］中算法刪除多出的向量及向量中的分量，實驗結果如表1和圖2(b)所示.從表1可知，應用特征向量來求解點匹配的文獻［3-5］中算法，在點數不一致的情形下，匹配正確率下降較大，單純的譜方法(如文獻［3-4］中算法)幾乎很難獲得正確匹配點，而結合EM算法的文獻［5］中算法雖然在匹配正確率方面有了較大的提升，但依然不太理想.文中算法的匹配正確率最高，說明文中算法能夠處理大小不一致的點集匹配問題.對于點pi，選取與pi相關聯的前k條最短邊來構造線圖，k的大小決定了pi的特征是全局性的還是局部性的:當k較小時，選取的是pi與其鄰近點之間的邊，pi的特征是局部特征;當k很大時，選取的邊代表了pi與大部分點之間的關系，此時pi的特征傾向于全局性.一般情況下，在兩個點集大小不一致時，多出的點大部分是一些邊緣的噪聲點，因此，利用點集所構造的圖在局部上是很相似的，這是文中算法能夠處理一些大小不一致的點集匹配問題的原因.

表1 幾種算法對魚圖像的模擬結果比較Table 1 Comparison of simulated results of several algorithms for fish images

5.2 真實圖像實驗

文中通過大量的真實圖像實驗來驗證所提算法的有效性，實驗圖像來自CMU/VASC圖像數據庫的圖像序列，分別選取了第10、20、30、40、50、60幀圖像，在每幀圖像上選取30個點進行實驗.在圖像間幀數相差30、40、50的情況下幾種算法的實驗結果如表2和圖3、4所示.從表2可知:當幀數差變大時，幾種算法的匹配正確率均下降，單純的譜方法(如文獻［3-4］中算法)的匹配效果不如文獻［5］中算法與文中算法;在兩幅圖像相差30幀的情況下，文中算法與文獻［5］中算法均能獲得完全正確的匹配結果;在兩幅圖像相差40幀的情況下，文獻［5］中算法不能獲得完全正確的匹配結果;當兩幅圖像的幀數差變為50時，文中算法的匹配正確率下降，但依然高于其它3種算法.

表2 幾種算法對真實圖像的實驗結果比較Table 2 Comparison of experimental results of several algorithms for real images

圖3 幾種算法在圖像幀數相差30情況下的匹配結果Fig.3 Matching results of several algorithms when the difference in frame number is 30

5.3 性能分析

首先分析文中算法的復雜度，由于Q-譜方法的復雜度主要集中在譜分解上，譜分解的復雜度為O(n3)，需要O(n)次譜分解，所以Q-譜方法的復雜度為O(n4)，KM算法的復雜度為O(n4)，所以文中算法的復雜度為O(n4).

另外，還可以對文中算法進行優化，降低計算復雜度.如在能夠滿足算法精度要求的情況下，構造線圖時所選的邊數k盡可能地小，譜分解的復雜度實際上為O(k3)，則Q-譜方法的復雜度為O(nk3);采用文獻［17］中方法對KM算法進行優化，其復雜度降低為O(n3)，此時文中算法的復雜度降低為O(nk3+n3).

為驗證文中算法在不同點數差下的穩定性，選取100個隨機點進行實驗，在按一定比例將點刪除后，再與原點集進行匹配，同時使用文獻［3-5］中算法進行對比實驗，結果如圖5所示.從圖5可知，在兩個點集的點數相差接近自身點數的50%時，文中算法依然能夠獲得90%以上的匹配正確率，但其它3種算法的匹配正確率下降較大，文獻［5］中算法的效果要稍好于文獻［3-4］中算法.

圖5 幾種算法在兩個點集的點數相差一定比例下的性能比較Fig.5 Performance comparison of several algorithms when the point numbers of two point sets differ in a certain ratio

6 結語

針對大多數譜方法不能夠較好地處理不同大小點集匹配的問題，文中提出了一種基于線圖Q-譜的點模式匹配算法.該算法首先利用無符號Laplacian矩陣的譜來表示點的特征，然后通過這些特征計算點之間的匹配概率(相似性)，最后通過KM算法來尋找點集之間的最優匹配來完成匹配.實驗結果表明，文中算法具有較高的匹配精度，可以處理不同大小的點集匹配問題.如何利用文中算法來處理一些更加復雜的圖像匹配問題是今后研究的主要方向之一.

［1］Chung Fan R K.Spectral graph theory［M］.Providence:American Mathematical Society，1997.

［2］Scott G L，Longuet-Higgins H C.An algorithm for associating the features of 2 images［J］.Proceedings of the Royal Society London B:Biological Sciences，1991，244:21-26.

［3］Shapiro L S，Brady JM.Feature-based correspondence:an eigenvector approach［J］.Image Vision Computing，1992，10(5):283-288.

［4］王年，范益政，韋穗，等.基于圖的Laplace譜的特征匹配［J］.中國圖象圖形學報，2006，11(3):332-336.Wang Nian，Fan Yi-zheng，Wei Sui，et al.Feature matching based on Laplace spectrum of graph［J］.Journal of Image and Graphics，2006，11(3):332-336.

［5］Carcassoni M，Hancock E R.Spectral correspondence for point pattern matching［J］.Pattern Recognition，2003，36(1):193-204.

［6］Tang J，Liang D，Wang N，et al.A Laplacian spectral method for stereo correspondence［J］.Pattern Recognition Letters，2007，28(12):1391-1399.

［7］Mohar B，Juvan Martin.Some applications of Laplace eigenvalues of graphs［M］∥Harn G，Sabiussi G.Graph symmetry:algebraic methods and applications.Dordrecht:Kluwer Academic Publishers，1997:227-275.

［8］Grone R，Merris R，Sunder V S.The Laplacian spectrum of a graph［J］.SIAM Journal Matrix Analysis Applications，1990，11(2):218-238.

［9］Merris R.Laplacian matrices of graphs:a survey［J］.Linear Algebra and Its Applications，1994，197/198:143-176.

［10］Oliveira C S，de Lima L S，de Abreu N M M，et al.Bounds on theQ-spread of a graph［J］.Linear Algebra and Its Applications，2010，432(9):2342-2351.

［11］Van Dam E R，Haemers W H.Which graphs are determined by their spectrum?［J］.Linear Algebra and Its Applications，2003，373:241-272.

［12］Cvetkovi'c D，Simi'c SK.Towards a spectral theory of graphs based on the signless Laplacian，I［J］.Publications De L’InstitutMathématiques，2009，85(99):19-33.

［13］Cvetkovi'c D，Simi'c SK.Towards a spectral theory of graphs based on the signless Laplacian，II［J］.Linear Algebra and Its Applications，2010，432(9):2257-2272.

［14］Cvetkovi'c D，Simi'c SK.Towards a spectral theory of graphs based on the signless Laplacian，III［J］.Applicable Analysis Discrete Mathematics，2010，4(1):156-166.

［15］肖位樞.圖論及其算法［M］.北京:航空工業出版社，1993:134-142.

［16］Chui H，Rangarajan A.A new pointmatching algorithm for non-rigid registration［J］.Computer Vision and Image Understanding，2003，89(2):114-141.

［17］張超，曾顯華，齊凱隆.基于二分圖匹配的一類多機調度問題研究［J］.軟件導刊，2009，8(7):73-75.Zhang Chao，Zeng Xian-hua，Qi Kai-long.Research of a class of scheduling problem ofmulticomputer based on bipartite graph matching［J］.Software Guide，2009，8(7):73-75.