唐 俊，劉志忠，周洪偉，闞?？?/p>

形狀匹配是計算機視覺、圖像分析和模式識別等領(lǐng)域中的一個關(guān)鍵問題.形狀可以用點、線段、曲線等不同層次的幾何基元來表示，但任何層次的幾何基元都可離散為一系列的點，所以用點模式描述形狀更具有普適性.因此，基于譜圖理論的點模式匹配問題受到了極大關(guān)注.Scott等［1］首次將譜理論引入對應(yīng)估計問題中，使用高斯加權(quán)函數(shù)構(gòu)造待匹配特征點集間的鄰接矩陣，然后對鄰接矩陣進行SVD分解，通過比較得到的有序特征向量，求解點集間的匹配關(guān)系，此方法能處理大小不同的點集，但當(dāng)點集間有較大旋轉(zhuǎn)和縮放時，匹配效果不佳.針對Scott算法的缺陷，Shapiro等［2］提出了一種改進算法，分別構(gòu)造兩個點集內(nèi)的鄰接矩陣，并對鄰接矩陣進行SVD分解，通過比較模態(tài)矩陣確定匹配關(guān)系;此算法對隨機點抖動、仿射變換和縮放具有很好的魯棒性，但該算法要求待匹配點集的大小相同.Carcassoni等［3］采取分層方法來抑制結(jié)構(gòu)性差異在匹配中的影響.王年等［4］提出了一種基于Laplace譜的點模式匹配算法，該算法首先為兩個特征點集分別定義了Laplace矩陣，隨后對矩陣進行SVD分解，并根據(jù)特征向量間的距離確定匹配關(guān)系.Tang等［5］為進一步提高魯棒性，提出將Laplace譜和雙隨機矩陣嵌入迭代變換與對應(yīng)估計的框架中，以此確定匹配關(guān)系.Wang等［6］提出利用核主成分分析算法解決點模式匹配問題，該算法具有很好的抗離群點和抗隨機抖動的能力.Leordeanu等［7］提出了基于成對約束的譜匹配算法，該算法能實現(xiàn)大小不同點集間的匹配，并在等距變換下可獲得較好的匹配結(jié)果.趙健等［8］提出了一種新的不變量——相對形狀上下文，并將其與譜方法結(jié)合，解決了Leordeanu算法在相似變換下匹配效果較差的問題.唐俊等［9］利用概率松弛方法，將形狀上下文與Laplace譜相結(jié)合以優(yōu)化匹配結(jié)果.文獻［1－9］的方法在處理形狀匹配時，并沒有考慮形狀本身的結(jié)構(gòu)特性，得到的匹配結(jié)果并不一定是最優(yōu)的.Thayananthan等［10］提出將形狀輪廓的連續(xù)信息和彎曲信息同形狀上下文相結(jié)合，以提升抗離群點的能力，并利用Viterbi算法求得聯(lián)合代價函數(shù)的最小值，進而確定匹配關(guān)系，該算法在旋轉(zhuǎn)角度不大的情況下能獲得較好的匹配結(jié)果.

為了進一步提升匹配精度，并具有旋轉(zhuǎn)不變性，作者提出一種新的形狀匹配算法，首先定義兩個形狀的Laplace矩陣，并計算出對應(yīng)的關(guān)系矩陣，然后將此矩陣代入Viterbi算法模型［12］，與形狀的自身特性(彎曲能和鄰接性［11］)相結(jié)合，從而得到更優(yōu)的匹配結(jié)果.

1 Laplace譜匹配算法

設(shè)形狀I(lǐng)包含n個特征點Ii(i=1，2，…，n)，定義Laplace矩陣如下

其中:d為任意兩點的歐式距離.

對LI進行SVD分解，得到

其中:ΔI=diag(λ1，…，λm)，λ1≥ … ≥ λm－1＞ λm=0;U=(u1，…，um)為正交矩陣.

類似地，對于形狀J可以得到

其中:ΔJ=diag{γi，…，γm}，V=(v1，…，vm).

當(dāng)Cij同時為所在行與列的最大值時，說明I的第i個特征點與J的第j個特征點匹配.

2 結(jié)合結(jié)構(gòu)信息的Laplace譜形狀匹配算法

在形狀匹配問題中，單獨的Laplace譜算法得到的匹配結(jié)果往往并不可靠.為了提高準(zhǔn)確率和魯棒性，作者考慮將形狀模型本身的結(jié)構(gòu)特性(彎曲能和鄰接性)融入對應(yīng)估計中.函數(shù)f(·，·)表示兩個特征點集間的對應(yīng)關(guān)系，則總的匹配代價函數(shù)可寫為

其中:CL為Laplace譜匹配代價，Ccont為鄰接性代價，Cbend為彎曲能代價，λ和μ為權(quán)重參數(shù).下面對上述符號作具體說明.

2.3 兩組患者 BNP、COX-2、MMP-1、ACE2、TIMP-2水平比較 觀察組患者BNP、COX-2、ACE2、TIMP-2水平高于對照組，MMP-1水平低于對照組，差異有統(tǒng)計學(xué)意義（P＜0.05）。見表2。

(1)Laplace譜匹配代價項CL

Laplace譜匹配代價項等于由函數(shù)f(·，·)所確定的所有對應(yīng)點對的匹配代價之和，即

(2)鄰接性代價項Ccont

鄰接性約束是指在形狀I(lǐng)中相鄰的特征點Ii和Ik應(yīng)與目標(biāo)形狀J中的相鄰特征點Jf(i)和Jf(k)對應(yīng)，其中函數(shù)f(i)表示將形狀中的第i個點映射到目標(biāo)形狀中的第f(i)個點.假設(shè)Ii和Ii－1是相鄰點，則鄰接性約束可寫成如下形式

(3)彎曲能代價項Cbend

尖拐角或高曲率點具有高頻特性，并且頻率越高彎曲能也越高.因此，彎曲能可用于描述曲線的彎曲程度，且當(dāng)曲線長度趨于無窮小時，彎曲能可作為點的局部特征.

設(shè)曲線為v(s)，則彎曲能等于曲線的曲率平方之和，即

其中:κ(i)=(v(i－1)+v(i+1)－2v(i))2表示第i個點的彎曲能.

如果兩個特征點的彎曲能大小越相近，彎曲能代價項的值越小，那么兩個特征點的局部特征越相似.彎曲能代價項可寫成如下形式

Viterbi算法是十分有效的，它利用遞歸減少計算量，并使用整個序列的上下文來判斷，從而即使觀察序列中有一個“非尋?！钡氖录l(fā)生，也不會對結(jié)果產(chǎn)生很大影響.通常情況下，直接求解總代價函數(shù)的代價太高，為了簡化運算，作者將對其中一個形狀點集按順(逆)時針進行排序，并利用Viterbi算法找出一條最優(yōu)路徑，從而確定形狀點集間的匹配關(guān)系.

3 實驗結(jié)果

3.1 性能分析

3.1.1 旋轉(zhuǎn)不變性

點集中某一點的形狀上下文［13］描述了其他點相對于該點的直方圖分布，當(dāng)選取不同的方向作為極坐標(biāo)的正方向時，得到的形狀上下文是不同的，因此形狀上下文對旋轉(zhuǎn)變換是非常敏感的.形狀輪廓上某一點彎曲能的大小僅由當(dāng)前點和其相鄰兩點共同決定，不隨形狀旋轉(zhuǎn)而發(fā)生變化，具有旋轉(zhuǎn)不變性.點間的鄰接關(guān)系也不會因旋轉(zhuǎn)而發(fā)生改變，同樣具有旋轉(zhuǎn)不變性，同時基于Laplace譜的匹配算法［5］(LP算法)在等距變換(平移、旋轉(zhuǎn)和反射)下也是不變的.作者提出的算法是在LP算法的基礎(chǔ)上，在對應(yīng)估計過程中考慮了形狀自身的結(jié)構(gòu)信息，因此該文算法能獲得更好的匹配結(jié)果，并具有旋轉(zhuǎn)不變性.

3.1.2 復(fù)雜度分析

通過計算得到基于Laplace譜的初始匹配關(guān)系矩陣的復(fù)雜度為O(m3)，隨后利用初始匹配關(guān)系矩陣及形狀結(jié)構(gòu)信息，在Viterbi模型上計算出匹配關(guān)系的復(fù)雜度為O(m3)，所以該文算法的復(fù)雜度為O(m3).

3.2 實驗結(jié)果

在實驗中，作者選取了不同的手勢進行匹配，在每個手勢輪廓上提取135個特征點.為驗證可行性，將該文算法與LP算法和SCV算法［11］進行了比較.圖1為不同手勢的匹配結(jié)果，在一對手型中位置靠前的為原始手型，位置靠后的為目標(biāo)手型，在每幅圖中，都是將原始手型與目標(biāo)手型進行匹配.圖1中第1列為LP算法，第2列為SCV算法，第3列為該文算法，兩手之間的連線表示錯誤匹配，位于手型邊緣的方框中的“+”號交叉點表示未被匹配的點.

圖1 不同手勢的匹配結(jié)果Fig.1 The match results of different gestures

表1給出了多種算法不同手勢的匹配結(jié)果比較.

表1 多種算法不同手勢匹配結(jié)果比較Tab.1 Comparison of the match results of different gestures with different algorithm

從表1可以看出，該文算法在正確匹配數(shù)和未匹配數(shù)方面均好于LP算法，而只有手勢C中的錯誤匹配數(shù)稍多于LP算法;相對SCV算法，除了手勢E外，該文算法在正確匹配數(shù)、未匹配數(shù)和錯誤匹配數(shù)方面均要好于SCV算法.SCV算法的一個致命弱點是不具備旋轉(zhuǎn)不變性.對手勢E進行5、10、15、30°的旋轉(zhuǎn)，使用3種算法得到的實驗結(jié)果如圖2所示.圖2中:一對手型中位置靠前的為原始手型，位置靠后的為目標(biāo)手型，在每幅圖中，都是將原始手型與目標(biāo)手型進行匹配;第1列為LP算法，第2列為SCV算法，第3列為該文算法;兩手之間的連線表示錯誤匹配，位于手型邊緣的方框中的“+”號交叉點表示未被匹配的點.

圖2 同一手勢在旋轉(zhuǎn)不同角度時的匹配結(jié)果Fig.2 The match results of the same gesture in different rotating angles

表2給出了多種算法同一手勢在旋轉(zhuǎn)不同角度時的匹配結(jié)果比較.

表2 同一手勢在旋轉(zhuǎn)不同角度時各算法的匹配結(jié)果比較Tab.2 Comparison of the match results of the same gesture in different rotating angles with different algorithms

從表2可以看出，在旋轉(zhuǎn)變換下該文算法和LP算法的匹配結(jié)果不受旋轉(zhuǎn)角度的影響，SCV算法隨著旋轉(zhuǎn)角度的增加，正確匹配率會急劇下降.

4 結(jié)束語

在形狀匹配問題中，傳統(tǒng)的譜算法只依據(jù)獨立的特征進行分析，并沒有考慮當(dāng)前形狀本身固有的特性，因此不能獲得好的匹配結(jié)果.針對存在的問題，作者將形狀本身的結(jié)構(gòu)特性與Laplace譜算法相結(jié)合，提出了一種新的形狀匹配算法，實現(xiàn)了形狀的匹配，實驗結(jié)果表明該文算法具有更高的準(zhǔn)確性和較強的魯棒性.

［1］ Scott G L，Longuet-Higgins H C.An algorithm for associating the features of two images［J］.Biological Sciences，1991，244:21 －26.

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

［3］ Carcassoni M，Hancock E R.Correspondence matching with modal clusters［J］.IEEE Pattern Analysis and Machine Intelligence，2003，25(12):1609 －1615.

［4］ 王年，范益政，韋穗，等.基于圖的Laplace譜的特征匹配［J］.中國圖象圖形學(xué)報，2006，11(3):332－336.

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

［6］ Wang H F，Hancock E R.Correspondence matching using kernel principal components analysis and label consistency constraints［J］.Pattern Recognition，2006，39(6):1012 －1025.

［7］ Leordeanu M，Hebert M.A spectral technique for correspondence problems using pairwise constraints［C］∥Proceedings of the Tenth IEEE International Conference on Computer Vision，2005:1482 －1489.

［8］ 趙健，孫即祥，李智勇，等.基于相對形狀上下文和譜匹配方法的點模式匹配算法［J］.電子與信息學(xué)報，2010，10(32):2287－2293.

［9］ 唐俊，王年，梁棟，等.一種結(jié)合形狀上下文分析的Laplace譜匹配算法［J］.系統(tǒng)仿真學(xué)報，2009，14(21):4344－4350.

［10］ Thayananthan A，Stenger B，Torr P H S，et al.Shape context and chamfer matching in cluttered scenes［C］∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition，2003:127－133.

［11］ Kass M，Witkin A，Terzopoulos D.Snakes:active contour models［J］.International Journal of Computer Vision，1987，1(4):259 －268.

［12］ Forney G D.The viterbi algorithm［J］.Proceedings of the IEEE，1973，61(3):268 －278.

［13］ Belongie S，Malik J，Puzicha J.Shape matching and object recognition using shape contexts［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(4):509 －522.