第22卷第8期計算機學(xué)報Vol. 22 No. 81999年8月CHINESE J. COMPUTERSAug.1999動力學(xué)松弛系統(tǒng)楊青馬頌德丁險峰(中國科學(xué)院自動化研究所模式識別國家重點實驗室北京100080)摘要傳統(tǒng)的松弛方法有兩個基本的更新策略: winner-take-al和 loser-take- nothing.這兩個策略有以下缺陷非一致性,局部極值問題和計算復(fù)雜性問題作者將通過構(gòu)造動力學(xué)系統(tǒng)來解決這些問題.這一思路的困難在于在逐步去掉不確定匹配的同時穩(wěn)定系統(tǒng)為此引入了特殊的非線性變換來構(gòu)造這個動力學(xué)系統(tǒng).與前人的工作相比,作者的算法較好地解決了計算復(fù)雜性和匹配準確率之間的矛盾關(guān)鍵詞匹配,松弛,動力學(xué)系統(tǒng),非線性變換分類號:TP391DYNAMIC RELAXATION SYSTEMYANG Qing MA Song-De DING Xian-Feng(National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100080)Abstract The existing updating strategies for the classical relaxation technique have variousdrawbacks such as nonuniformity, local minimum, and computational complexity. The authorsdesign dynamic systems to deal with these problems. The main difficulty of this idea is how to si-multaneously stabilize the system and obtained unambiguous match. Simple nonlinear transformations are introduced to construct the dynamic relaxation system for image matching. Comparedwith previous methods, The above-mentioned approach effectively overcomes the contradictionbetween matching accuracy and computational complexity.Keywords Matching, relaxation, dynamic system, nonlinear transformation的所有信息,且在單步迭代中不刪除候選匹配,因1引言此是穩(wěn)健的.但是這不是一個實用的算法,因為在系統(tǒng)的穩(wěn)態(tài)解中,只有一個主元素,也就是說,我松弛方法是傳統(tǒng)的匹配算法之一.它有兩個基們最終只能得到一對匹配點本的更新策略: winner-take-l(以下簡稱WTA)和為了解決這一困難,根據(jù)幾個準則,我們引入loser-take- nothing(以下簡稱LTN).這些方法有很了一類非常簡單的非線性變換在此基礎(chǔ)上,構(gòu)造明顯的缺陷,主要是:(1)非一致性;(2)局部極值冋了一個動力學(xué)系統(tǒng)來實現(xiàn)松弛過程·此算法中,題;(3)計算復(fù)雜性問題winner的選取(或 loser刪除)是在一個連續(xù)的動態(tài)本文中我們將構(gòu)造動力學(xué)系統(tǒng)來解決這些問過程中,而普通的方法都是在一步迭代中實現(xiàn)的題.一個直觀的想法是在迭代過程中將匹配強度[9因此,我們的算法魯棒性和準確率都很高.更重要計算公式中的某些參數(shù)(如相關(guān)系數(shù))用上次迭代所的是,所構(gòu)造的動力學(xué)系統(tǒng)的收斂速度很快.這樣,得到的匹配強度代替這一方案利用了上次迭代中準確中國煤化工效的解決本文1997-10-14收到,修改文199904-28收到本課題得到國家自然科YHCNMHG獲博士學(xué)位,研究方向為計算機視覺、人工智能馬頌德,男,1946年生,獲博土學(xué)位,研究員,博士生導(dǎo)師,研究方向為計算機視覺、模式識別丁險峰,男,1971年生博士研究生,研究方向為計算機視覺、圖像處理8期楊青等:動力學(xué)松弛系統(tǒng)817如下.每步迭代中,去掉具有最低的匹配強度的候2經(jīng)典的松弛方法選匹配直至得到確定的匹配為止.這是一個最慢下降方法,計算復(fù)雜性很高給定左右兩幅圖像中的點集{m1,i=1,2,…,n1}這兩個更新策略的局限性在于:和{m2,j=1,2,…,n2}.我們的目標就是找出這兩個(1)非一致性,不確定的匹配不是以一種一致點集的匹配關(guān)系.此問題的困難在于一幅圖像中的一的方式被去掉的,也就是說,某些點的候選匹配數(shù)點在另一圖像中可能有多個點與之對應(yīng)(這些可能的目減少速度可能比其它點快得多.這樣一部分點的點對應(yīng)我們稱之為候選匹配),反之亦然.去掉不確定匹配會被過早確定下來,如果這些匹配是錯誤的的候選匹配算法的種類很多,在這一節(jié)里,我們將簡誤差會在以后的迭代中傳播、積累,整個匹配過程可要介紹經(jīng)典的算法:松弛方法( Relaxation).松弛方能會因此崩潰,WTA和LTN都不是一致的法亦有多種形式,在此我們只選擇其中較簡單的一種(2)局部極小問題.因為下降速度太快,WTA來闡明基本原理,讀者很容易將其推廣到更一般的問過程可能會陷入效果很差的局部極小中.故而在很題,如圖匹配( Graph matching)4,多問題中,它的匹配準確率很差2.1候選匹配的匹配強度(3)計算復(fù)雜性.如果一個點的候選匹配較首先我們需要為每一對候選匹配定義匹配強多,LTN的速度可能很慢.理論上講,LTN是一種度.以下定義可以在文獻[9]中找到.考察候選匹配最慢下降方法,其準確率應(yīng)該較高,但實際上在很(m1,m2).令N(m1)和N(m2)分別為m1和mn的多情形下仍然不能令人滿意鄰域.我們定義(m1,m2,)的匹配強度為;m1k,m2)3主要結(jié)果max哪∈N(m1,)m∈N(m2ya+dist(m1i,mim,m2)本節(jié)中,我們首先給出一個直觀的想法,分析這里,和c分別是(m,mn)和(m,m2)的先驗的其優(yōu)點并指出它成為一個實用算法的內(nèi)在缺陷,然匹配系數(shù),如相關(guān)系數(shù)( Correlation);a是調(diào)整距離權(quán)后引入特殊變換來克服這一困難重的參數(shù);dist(m1,m21;m1k,my)=(‖m1-m‖+3.1一個直觀的想法m2-m2‖)/2是匹配點的平均距離;如果(m1,m2考慮匹配強度的定義式(1).其中,c和c是表是候選匹配且r1時(y=1的情形見下一小節(jié)的注記),若(i,winner,則(i,j)也是S的 wInner是c的 winner;則Ss=0;否則,S}∞=0.以上分這里,我們說(,)是S的一個 winner,如果(,析表明在此特殊情況下(T.1)-(T.3)滿足(C.1)j)是第i行和第j列的最大元素(C.4).可以證明對一般情況此結(jié)論亦成立(C.3)穩(wěn)態(tài)解S(+°包含盡可能多的0(正確匹從這個簡單的例子我們觀察到 winner的顯著配除外).理想情形是S(+是一個0-1矩陣,其中性是漸進增大的與之相反,在傳統(tǒng)的WTA和每行(列)至多有一個元素為1LTN,我們在一步迭代中選擇 winner(或刪除(C.4)每個 wInner的值相等.loser)(見2.2節(jié)中關(guān)于非一致性的討論),所以風險(C.1),(C.2)和(C.3)容易理解,(C4)需要解比漸進方法大,注意到y(tǒng)=+∞的極限情形就是釋一下.我們不能在相同的尺度下比較不同 wInner,例WTA.更進一步,我們指出如下事實:7越大,系統(tǒng)如,如果(,j)是最大的 winner(即S的最大元素),其顯收斂越快,但魯棒性降低著性(即S,與第i行和第j列元素的差)可能比其它3.4詳細的匹配算法winner的顯著性小.理想的情形是φ正比于顯著性度為完整起見,現(xiàn)將上面的內(nèi)容綜合成以下詳細量.但是在同時滿足(C.1)—(C.3)的情況下定義這樣的算法:度量十分困難,因此,我們將此想法簡化成(C.4)第1步.從(T.1)—(T.3)中選取一個變換,設(shè)定閾值在式(3)中,令中=d(恒等變換)即可得到式(2),T定義為不滿足(C.4).正如我們已經(jīng)看到的,這對系統(tǒng)成為Sg=[(S)],=[(S)],f[中(S)l>T實用算法是致命的0, otherwise.第2步.對i=1,2,…,n1;j=1,2,…,n2;t=0,1,2對=1,2,…,n1j=1,2,…,n2,令S的第…,迭代等式(3)直至迭代收斂行的最大元素為a,第j列的最大元素為b,即第3步.選取穩(wěn)態(tài)解S∞中的所有 wInner,即:若,n2}b,= max( Suk=1, 2,",n,, l= kS∞=1,則(m1,m2)是一對匹配點我們提出能夠滿足(C.1)-(C.4)的3種變換:4計算復(fù)雜性分析和仿真比較(T.1)S,=中國煤化工(T.2)SCNMHG決于:(1)所有鄰域n2)的平均半徑R;(2)候選匹配的總數(shù)目,記為(T.3)Nm;(3)兩個圖像的點數(shù),分別記為n1和n28期楊青等:動力學(xué)松弛系統(tǒng)819下面將我們的方法與WTA和LTN的計算復(fù)雜性用實驗進行比較圖像的點集是隨機生成的參5實驗結(jié)果數(shù)的選取如下:(1)n1=n2,即兩邊圖像點數(shù)相同記n=n1=n2;(2)鄰域半徑R=+∞;(3)候選圖1是兩幅合成圖像(233×261)的匹配結(jié)果匹配的總數(shù)目N=n1n2=n2.這意味著所有的點R=50pix,y=1,下同.左圖只有一個字母“A”.右對都是侯選匹配;(4)Y=2.圖包含4個字母“A”,“B”,“C”和“D”.注意兩邊字表1表明WTA是最快的算法我們算法的運行母的字體不同.這個問題是很簡單的,但是只有我時間約為WTA的兩倍.LTN最慢在很多實際問題們的方法給出了正確的結(jié)果(圖1b),注意其匹配中,LTN因其計算復(fù)雜性太高沒有什么用處是鏡象對稱的).其中圖1(a)為待匹配的圖像及其表1角點(由“+”標出),圖1(b)為用我們的方法給出的n(n,=n,) Dynamic relaxation Winner-take-all Loser-take-no匹配結(jié)果,運行時間為4s;圖1(c)為LTN的匹配結(jié)17果,運行時間為70s;圖1(d)為WTA的匹配結(jié)果運行279151時間為1sABAABCDCDAABAA 3CDCDYH=取圖2820計算機學(xué)報1999年圖2給出了兩幅真實圖像的匹配結(jié)果(因為足題比以上兩個要復(fù)雜一些.WTA給出的匹配效果球的角點是對稱的,有很多可能的匹配).WTA的很差我們的方法(圖2(b))和LTN(圖2(b))的結(jié)結(jié)果是完全錯誤的(圖2(d).我們的方法(圖2(b))果都是令人滿意的.如圖2一樣,但我們的方法的運和LTN(圖2(c))都給出了正確的結(jié)果(注意兩個足行時間(10s)比LTN(1099s)少得多.錯誤匹配的原球方向是相反的).但我們方法的運行時間(4s)比因在于:(1)角點匹配中存在誤差(如圖3(b)中點LTN(539s)少得多31的匹配);(2)距離較近的點易被混淆(如圖3(b)圖3給出了兩幅運動圖像的匹配結(jié)果.這個問中的點4和5).這是式(1)所定義的模型的局限性|[這些實驗表明:WTA的缺點在于匹配準確率3Lisz. Inexact matching of3 D surfaces, visIon, speech and往往太低;LTN的準確率高得多,但計算復(fù)雜性又signal processing. Department EEE, University of Surrey太高.總而言之,它們都是不實用的算法,UK: Technical Report VSSP-TR-3-90, 19904 Ma S D. Neural computation of graph matching. In: Proc of本文所發(fā)展的松弛方法較好地解決了這兩個難ICCAD, Hong Kong, 1988問題:它的計算復(fù)雜性不高,但相對而言,匹配準確5 pollards b, Mayhew JE W, Frisby JP.PMF: A stereo率和魯棒性是最高的respondence algorithm using a disparity gradient limit. Percep-tion,1985,14:449-1706結(jié)論6 Rosenfeld A, Hummel R A, Zucker S w. Scene labeling by re-laxation operations, IEEE Trans on SMC, 1976, 6(4):420本文提出了圖像匹配的一種新的松弛方法:動SM, Brady J M. SUSAN-a new approach to low level態(tài)松弛,通過構(gòu)造一個動力學(xué)系統(tǒng)來實現(xiàn)松弛過image processing. International Journal of Computer Vision程我們的方法與傳統(tǒng)的WTA和LTN的區(qū)別在于1997,23(1):45-78更新策略是漸進的.由此而導(dǎo)出的算法具有較低的Xu G, Zhang Z. Epipolar Geometry in Stereo, Motion and Ob-ject Recognition: A Unified Approach, Netherland: Kluwer A復(fù)雜性和高的準確率,較好地解決了復(fù)雜性和高準Hemic Press, 1996確率之間的矛盾Zhang Z, Deriche R et al. A robust technique for matching twocalibrated Images through the recovery of the unknown參考文獻epipolar geometry. Artificial Intelligence Journal, 1995,78:中國煤化工。nCorneil D G, Gotlieb CC. An efficient algorithm for graphs relaxation and lo-morphism. Journal of ACM, 1970, 17(1)CN MH Equivalence. IEEE Trans1,3(2):117-122 Haralick R M, Kartus J S. Arrangements, homomorphismsand discrete relaxation. IEEE Trans on SMC, 1978, 8(8)