第22卷第8期計(jì)算機(jī)學(xué)報(bào)Vol. 22 No. 81999年8月CHINESE J. COMPUTERSAug.1999動(dòng)力學(xué)松弛系統(tǒng)楊青馬頌德丁險(xiǎn)峰(中國(guó)科學(xué)院自動(dòng)化研究所模式識(shí)別國(guó)家重點(diǎn)實(shí)驗(yàn)室北京100080)摘要傳統(tǒng)的松弛方法有兩個(gè)基本的更新策略: winner-take-al和 loser-take- nothing.這兩個(gè)策略有以下缺陷非一致性,局部極值問(wèn)題和計(jì)算復(fù)雜性問(wèn)題作者將通過(guò)構(gòu)造動(dòng)力學(xué)系統(tǒng)來(lái)解決這些問(wèn)題.這一思路的困難在于在逐步去掉不確定匹配的同時(shí)穩(wěn)定系統(tǒng)為此引入了特殊的非線(xiàn)性變換來(lái)構(gòu)造這個(gè)動(dòng)力學(xué)系統(tǒng).與前人的工作相比,作者的算法較好地解決了計(jì)算復(fù)雜性和匹配準(zhǔn)確率之間的矛盾關(guān)鍵詞匹配,松弛,動(dòng)力學(xué)系統(tǒng),非線(xiàn)性變換分類(lèi)號(hào):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)健的.但是這不是一個(gè)實(shí)用的算法,因?yàn)樵谙到y(tǒng)的穩(wěn)態(tài)解中,只有一個(gè)主元素,也就是說(shuō),我松弛方法是傳統(tǒng)的匹配算法之一.它有兩個(gè)基們最終只能得到一對(duì)匹配點(diǎn)本的更新策略: winner-take-l(以下簡(jiǎn)稱(chēng)WTA)和為了解決這一困難,根據(jù)幾個(gè)準(zhǔn)則,我們引入loser-take- nothing(以下簡(jiǎn)稱(chēng)LTN).這些方法有很了一類(lèi)非常簡(jiǎn)單的非線(xiàn)性變換在此基礎(chǔ)上,構(gòu)造明顯的缺陷,主要是:(1)非一致性;(2)局部極值冋了一個(gè)動(dòng)力學(xué)系統(tǒng)來(lái)實(shí)現(xiàn)松弛過(guò)程·此算法中,題;(3)計(jì)算復(fù)雜性問(wèn)題winner的選取(或 loser刪除)是在一個(gè)連續(xù)的動(dòng)態(tài)本文中我們將構(gòu)造動(dòng)力學(xué)系統(tǒng)來(lái)解決這些問(wèn)過(guò)程中,而普通的方法都是在一步迭代中實(shí)現(xiàn)的題.一個(gè)直觀(guān)的想法是在迭代過(guò)程中將匹配強(qiáng)度[9因此,我們的算法魯棒性和準(zhǔn)確率都很高.更重要計(jì)算公式中的某些參數(shù)(如相關(guān)系數(shù))用上次迭代所的是,所構(gòu)造的動(dòng)力學(xué)系統(tǒng)的收斂速度很快.這樣,得到的匹配強(qiáng)度代替這一方案利用了上次迭代中準(zhǔn)確中國(guó)煤化工效的解決本文1997-10-14收到,修改文199904-28收到本課題得到國(guó)家自然科YHCNMHG獲博士學(xué)位,研究方向?yàn)橛?jì)算機(jī)視覺(jué)、人工智能馬頌德,男,1946年生,獲博土學(xué)位,研究員,博士生導(dǎo)師,研究方向?yàn)橛?jì)算機(jī)視覺(jué)、模式識(shí)別丁險(xiǎn)峰,男,1971年生博士研究生,研究方向?yàn)橛?jì)算機(jī)視覺(jué)、圖像處理8期楊青等:動(dòng)力學(xué)松弛系統(tǒng)817如下.每步迭代中,去掉具有最低的匹配強(qiáng)度的候2經(jīng)典的松弛方法選匹配直至得到確定的匹配為止.這是一個(gè)最慢下降方法,計(jì)算復(fù)雜性很高給定左右兩幅圖像中的點(diǎn)集{m1,i=1,2,…,n1}這兩個(gè)更新策略的局限性在于:和{m2,j=1,2,…,n2}.我們的目標(biāo)就是找出這兩個(gè)(1)非一致性,不確定的匹配不是以一種一致點(diǎn)集的匹配關(guān)系.此問(wèn)題的困難在于一幅圖像中的一的方式被去掉的,也就是說(shuō),某些點(diǎn)的候選匹配數(shù)點(diǎn)在另一圖像中可能有多個(gè)點(diǎn)與之對(duì)應(yīng)(這些可能的目減少速度可能比其它點(diǎn)快得多.這樣一部分點(diǎn)的點(diǎn)對(duì)應(yīng)我們稱(chēng)之為候選匹配),反之亦然.去掉不確定匹配會(huì)被過(guò)早確定下來(lái),如果這些匹配是錯(cuò)誤的的候選匹配算法的種類(lèi)很多,在這一節(jié)里,我們將簡(jiǎn)誤差會(huì)在以后的迭代中傳播、積累,整個(gè)匹配過(guò)程可要介紹經(jīng)典的算法:松弛方法( Relaxation).松弛方能會(huì)因此崩潰,WTA和LTN都不是一致的法亦有多種形式,在此我們只選擇其中較簡(jiǎn)單的一種(2)局部極小問(wèn)題.因?yàn)橄陆邓俣忍?WTA來(lái)闡明基本原理,讀者很容易將其推廣到更一般的問(wèn)過(guò)程可能會(huì)陷入效果很差的局部極小中.故而在很題,如圖匹配( Graph matching)4,多問(wèn)題中,它的匹配準(zhǔn)確率很差2.1候選匹配的匹配強(qiáng)度(3)計(jì)算復(fù)雜性.如果一個(gè)點(diǎn)的候選匹配較首先我們需要為每一對(duì)候選匹配定義匹配強(qiáng)多,LTN的速度可能很慢.理論上講,LTN是一種度.以下定義可以在文獻(xiàn)[9]中找到.考察候選匹配最慢下降方法,其準(zhǔn)確率應(yīng)該較高,但實(shí)際上在很(m1,m2).令N(m1)和N(m2)分別為m1和mn的多情形下仍然不能令人滿(mǎn)意鄰域.我們定義(m1,m2,)的匹配強(qiáng)度為;m1k,m2)3主要結(jié)果max哪∈N(m1,)m∈N(m2ya+dist(m1i,mim,m2)本節(jié)中,我們首先給出一個(gè)直觀(guān)的想法,分析這里,和c分別是(m,mn)和(m,m2)的先驗(yàn)的其優(yōu)點(diǎn)并指出它成為一個(gè)實(shí)用算法的內(nèi)在缺陷,然匹配系數(shù),如相關(guān)系數(shù)( Correlation);a是調(diào)整距離權(quán)后引入特殊變換來(lái)克服這一困難重的參數(shù);dist(m1,m21;m1k,my)=(‖m1-m‖+3.1一個(gè)直觀(guān)的想法m2-m2‖)/2是匹配點(diǎn)的平均距離;如果(m1,m2考慮匹配強(qiáng)度的定義式(1).其中,c和c是表是候選匹配且r1時(shí)(y=1的情形見(jiàn)下一小節(jié)的注記),若(i,winner,則(i,j)也是S的 wInner是c的 winner;則Ss=0;否則,S}∞=0.以上分這里,我們說(shuō)(,)是S的一個(gè) winner,如果(,析表明在此特殊情況下(T.1)-(T.3)滿(mǎn)足(C.1)j)是第i行和第j列的最大元素(C.4).可以證明對(duì)一般情況此結(jié)論亦成立(C.3)穩(wěn)態(tài)解S(+°包含盡可能多的0(正確匹從這個(gè)簡(jiǎn)單的例子我們觀(guān)察到 winner的顯著配除外).理想情形是S(+是一個(gè)0-1矩陣,其中性是漸進(jìn)增大的與之相反,在傳統(tǒng)的WTA和每行(列)至多有一個(gè)元素為1LTN,我們?cè)谝徊降羞x擇 winner(或刪除(C.4)每個(gè) wInner的值相等.loser)(見(jiàn)2.2節(jié)中關(guān)于非一致性的討論),所以風(fēng)險(xiǎn)(C.1),(C.2)和(C.3)容易理解,(C4)需要解比漸進(jìn)方法大,注意到y(tǒng)=+∞的極限情形就是釋一下.我們不能在相同的尺度下比較不同 wInner,例WTA.更進(jìn)一步,我們指出如下事實(shí):7越大,系統(tǒng)如,如果(,j)是最大的 winner(即S的最大元素),其顯收斂越快,但魯棒性降低著性(即S,與第i行和第j列元素的差)可能比其它3.4詳細(xì)的匹配算法winner的顯著性小.理想的情形是φ正比于顯著性度為完整起見(jiàn),現(xiàn)將上面的內(nèi)容綜合成以下詳細(xì)量.但是在同時(shí)滿(mǎn)足(C.1)—(C.3)的情況下定義這樣的算法:度量十分困難,因此,我們將此想法簡(jiǎn)化成(C.4)第1步.從(T.1)—(T.3)中選取一個(gè)變換,設(shè)定閾值在式(3)中,令中=d(恒等變換)即可得到式(2),T定義為不滿(mǎn)足(C.4).正如我們已經(jīng)看到的,這對(duì)系統(tǒng)成為Sg=[(S)],=[(S)],f[中(S)l>T實(shí)用算法是致命的0, otherwise.第2步.對(duì)i=1,2,…,n1;j=1,2,…,n2;t=0,1,2對(duì)=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)是一對(duì)匹配點(diǎn)我們提出能夠滿(mǎn)足(C.1)-(C.4)的3種變換:4計(jì)算復(fù)雜性分析和仿真比較(T.1)S,=中國(guó)煤化工(T.2)SCNMHG決于:(1)所有鄰域n2)的平均半徑R;(2)候選匹配的總數(shù)目,記為(T.3)Nm;(3)兩個(gè)圖像的點(diǎn)數(shù),分別記為n1和n28期楊青等:動(dòng)力學(xué)松弛系統(tǒng)819下面將我們的方法與WTA和LTN的計(jì)算復(fù)雜性用實(shí)驗(yàn)進(jìn)行比較圖像的點(diǎn)集是隨機(jī)生成的參5實(shí)驗(yàn)結(jié)果數(shù)的選取如下:(1)n1=n2,即兩邊圖像點(diǎn)數(shù)相同記n=n1=n2;(2)鄰域半徑R=+∞;(3)候選圖1是兩幅合成圖像(233×261)的匹配結(jié)果匹配的總數(shù)目N=n1n2=n2.這意味著所有的點(diǎn)R=50pix,y=1,下同.左圖只有一個(gè)字母“A”.右對(duì)都是侯選匹配;(4)Y=2.圖包含4個(gè)字母“A”,“B”,“C”和“D”.注意兩邊字表1表明WTA是最快的算法我們算法的運(yùn)行母的字體不同.這個(gè)問(wèn)題是很簡(jiǎn)單的,但是只有我時(shí)間約為WTA的兩倍.LTN最慢在很多實(shí)際問(wèn)題們的方法給出了正確的結(jié)果(圖1b),注意其匹配中,LTN因其計(jì)算復(fù)雜性太高沒(méi)有什么用處是鏡象對(duì)稱(chēng)的).其中圖1(a)為待匹配的圖像及其表1角點(diǎn)(由“+”標(biāo)出),圖1(b)為用我們的方法給出的n(n,=n,) Dynamic relaxation Winner-take-all Loser-take-no匹配結(jié)果,運(yùn)行時(shí)間為4s;圖1(c)為L(zhǎng)TN的匹配結(jié)17果,運(yùn)行時(shí)間為70s;圖1(d)為WTA的匹配結(jié)果運(yùn)行279151時(shí)間為1sABAABCDCDAABAA 3CDCDYH=取圖2820計(jì)算機(jī)學(xué)報(bào)1999年圖2給出了兩幅真實(shí)圖像的匹配結(jié)果(因?yàn)樽泐}比以上兩個(gè)要復(fù)雜一些.WTA給出的匹配效果球的角點(diǎn)是對(duì)稱(chēng)的,有很多可能的匹配).WTA的很差我們的方法(圖2(b))和LTN(圖2(b))的結(jié)結(jié)果是完全錯(cuò)誤的(圖2(d).我們的方法(圖2(b))果都是令人滿(mǎn)意的.如圖2一樣,但我們的方法的運(yùn)和LTN(圖2(c))都給出了正確的結(jié)果(注意兩個(gè)足行時(shí)間(10s)比LTN(1099s)少得多.錯(cuò)誤匹配的原球方向是相反的).但我們方法的運(yùn)行時(shí)間(4s)比因在于:(1)角點(diǎn)匹配中存在誤差(如圖3(b)中點(diǎn)LTN(539s)少得多31的匹配);(2)距離較近的點(diǎn)易被混淆(如圖3(b)圖3給出了兩幅運(yùn)動(dòng)圖像的匹配結(jié)果.這個(gè)問(wèn)中的點(diǎn)4和5).這是式(1)所定義的模型的局限性|[這些實(shí)驗(yàn)表明:WTA的缺點(diǎn)在于匹配準(zhǔn)確率3Lisz. Inexact matching of3 D surfaces, visIon, speech and往往太低;LTN的準(zhǔn)確率高得多,但計(jì)算復(fù)雜性又signal processing. Department EEE, University of Surrey太高.總而言之,它們都是不實(shí)用的算法,UK: Technical Report VSSP-TR-3-90, 19904 Ma S D. Neural computation of graph matching. In: Proc of本文所發(fā)展的松弛方法較好地解決了這兩個(gè)難ICCAD, Hong Kong, 1988問(wèn)題:它的計(jì)算復(fù)雜性不高,但相對(duì)而言,匹配準(zhǔn)確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本文提出了圖像匹配的一種新的松弛方法:動(dòng)SM, Brady J M. SUSAN-a new approach to low level態(tài)松弛,通過(guò)構(gòu)造一個(gè)動(dòng)力學(xué)系統(tǒng)來(lái)實(shí)現(xiàn)松弛過(guò)image processing. International Journal of Computer Vision程我們的方法與傳統(tǒng)的WTA和LTN的區(qū)別在于1997,23(1):45-78更新策略是漸進(jìn)的.由此而導(dǎo)出的算法具有較低的Xu G, Zhang Z. Epipolar Geometry in Stereo, Motion and Ob-ject Recognition: A Unified Approach, Netherland: Kluwer A復(fù)雜性和高的準(zhǔn)確率,較好地解決了復(fù)雜性和高準(zhǔn)Hemic Press, 1996確率之間的矛盾Zhang Z, Deriche R et al. A robust technique for matching twocalibrated Images through the recovery of the unknown參考文獻(xiàn)epipolar geometry. Artificial Intelligence Journal, 1995,78:中國(guó)煤化工。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)