动力学松弛系统

第22卷第8期计算机学报Vol. 22 No. 81999年8月CHINESE J. COMPUTERSAug.1999动力学松弛系统杨青马颂德丁险峰(中国科学院自动化研究所模式识别国家重点实验室北京100080)摘要传统的松弛方法有两个基本的更新策略: winner-take-al和 loser-take- nothing.这两个策略有以下缺陷非一致性,局部极值问题和计算复杂性问题作者将通过构造动力学系统来解决这些问题.这一思路的困难在于在逐步去掉不确定匹配的同时稳定系统为此引入了特殊的非线性变换来构造这个动力学系统.与前人的工作相比,作者的算法较好地解决了计算复杂性和匹配准确率之间的矛盾关键词匹配,松弛,动力学系统,非线性变换分类号: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引言此是稳健的.但是这不是一个实用的算法,因为在系统的稳态解中,只有一个主元素,也就是说,我松弛方法是传统的匹配算法之一.它有两个基们最终只能得到一对匹配点本的更新策略: winner-take-l(以下简称WTA)和为了解决这一困难,根据几个准则,我们引入loser-take- nothing(以下简称LTN).这些方法有很了一类非常简单的非线性变换在此基础上,构造明显的缺陷,主要是:(1)非一致性;(2)局部极值冋了一个动力学系统来实现松弛过程·此算法中,题;(3)计算复杂性问题winner的选取(或 loser删除)是在一个连续的动态本文中我们将构造动力学系统来解决这些问过程中,而普通的方法都是在一步迭代中实现的题.一个直观的想法是在迭代过程中将匹配强度[9因此,我们的算法鲁棒性和准确率都很高.更重要计算公式中的某些参数(如相关系数)用上次迭代所的是,所构造的动力学系统的收敛速度很快.这样,得到的匹配强度代替这一方案利用了上次迭代中准确中国煤化工效的解决本文1997-10-14收到,修改文199904-28收到本课题得到国家自然科YHCNMHG获博士学位,研究方向为计算机视觉、人工智能马颂德,男,1946年生,获博土学位,研究员,博士生导师,研究方向为计算机视觉、模式识别丁险峰,男,1971年生博士研究生,研究方向为计算机视觉、图像处理8期杨青等:动力学松弛系统817如下.每步迭代中,去掉具有最低的匹配强度的候2经典的松弛方法选匹配直至得到确定的匹配为止.这是一个最慢下降方法,计算复杂性很高给定左右两幅图像中的点集{m1,i=1,2,…,n1}这两个更新策略的局限性在于:和{m2,j=1,2,…,n2}.我们的目标就是找出这两个(1)非一致性,不确定的匹配不是以一种一致点集的匹配关系.此问题的困难在于一幅图像中的一的方式被去掉的,也就是说,某些点的候选匹配数点在另一图像中可能有多个点与之对应(这些可能的目减少速度可能比其它点快得多.这样一部分点的点对应我们称之为候选匹配),反之亦然.去掉不确定匹配会被过早确定下来,如果这些匹配是错误的的候选匹配算法的种类很多,在这一节里,我们将简误差会在以后的迭代中传播、积累,整个匹配过程可要介绍经典的算法:松弛方法( Relaxation).松弛方能会因此崩溃,WTA和LTN都不是一致的法亦有多种形式,在此我们只选择其中较简单的一种(2)局部极小问题.因为下降速度太快,WTA来阐明基本原理,读者很容易将其推广到更一般的问过程可能会陷入效果很差的局部极小中.故而在很题,如图匹配( Graph matching)4,多问题中,它的匹配准确率很差2.1候选匹配的匹配强度(3)计算复杂性.如果一个点的候选匹配较首先我们需要为每一对候选匹配定义匹配强多,LTN的速度可能很慢.理论上讲,LTN是一种度.以下定义可以在文献[9]中找到.考察候选匹配最慢下降方法,其准确率应该较高,但实际上在很(m1,m2).令N(m1)和N(m2)分别为m1和mn的多情形下仍然不能令人满意邻域.我们定义(m1,m2,)的匹配强度为;m1k,m2)3主要结果max哪∈N(m1,)m∈N(m2ya+dist(m1i,mim,m2)本节中,我们首先给出一个直观的想法,分析这里,和c分别是(m,mn)和(m,m2)的先验的其优点并指出它成为一个实用算法的内在缺陷,然匹配系数,如相关系数( Correlation);a是调整距离权后引入特殊变换来克服这一困难重的参数;dist(m1,m21;m1k,my)=(‖m1-m‖+3.1一个直观的想法m2-m2‖)/2是匹配点的平均距离;如果(m1,m2考虑匹配强度的定义式(1).其中,c和c是表是候选匹配且r1时(y=1的情形见下一小节的注记),若(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).可以证明对一般情况此结论亦成立(C.3)稳态解S(+°包含尽可能多的0(正确匹从这个简单的例子我们观察到 winner的显著配除外).理想情形是S(+是一个0-1矩阵,其中性是渐进增大的与之相反,在传统的WTA和每行(列)至多有一个元素为1LTN,我们在一步迭代中选择 winner(或删除(C.4)每个 wInner的值相等.loser)(见2.2节中关于非一致性的讨论),所以风险(C.1),(C.2)和(C.3)容易理解,(C4)需要解比渐进方法大,注意到y=+∞的极限情形就是释一下.我们不能在相同的尺度下比较不同 wInner,例WTA.更进一步,我们指出如下事实:7越大,系统如,如果(,j)是最大的 winner(即S的最大元素),其显收敛越快,但鲁棒性降低著性(即S,与第i行和第j列元素的差)可能比其它3.4详细的匹配算法winner的显著性小.理想的情形是φ正比于显著性度为完整起见,现将上面的内容综合成以下详细量.但是在同时满足(C.1)—(C.3)的情况下定义这样的算法:度量十分困难,因此,我们将此想法简化成(C.4)第1步.从(T.1)—(T.3)中选取一个变换,设定阈值在式(3)中,令中=d(恒等变换)即可得到式(2),T定义为不满足(C.4).正如我们已经看到的,这对系统成为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步.选取稳态解S∞中的所有 wInner,即:若,n2}b,= max( Suk=1, 2,",n,, l= kS∞=1,则(m1,m2)是一对匹配点我们提出能够满足(C.1)-(C.4)的3种变换:4计算复杂性分析和仿真比较(T.1)S,=中国煤化工(T.2)SCNMHG决于:(1)所有邻域n2)的平均半径R;(2)候选匹配的总数目,记为(T.3)Nm;(3)两个图像的点数,分别记为n1和n28期杨青等:动力学松弛系统819下面将我们的方法与WTA和LTN的计算复杂性用实验进行比较图像的点集是随机生成的参5实验结果数的选取如下:(1)n1=n2,即两边图像点数相同记n=n1=n2;(2)邻域半径R=+∞;(3)候选图1是两幅合成图像(233×261)的匹配结果匹配的总数目N=n1n2=n2.这意味着所有的点R=50pix,y=1,下同.左图只有一个字母“A”.右对都是侯选匹配;(4)Y=2.图包含4个字母“A”,“B”,“C”和“D”.注意两边字表1表明WTA是最快的算法我们算法的运行母的字体不同.这个问题是很简单的,但是只有我时间约为WTA的两倍.LTN最慢在很多实际问题们的方法给出了正确的结果(图1b),注意其匹配中,LTN因其计算复杂性太高没有什么用处是镜象对称的).其中图1(a)为待匹配的图像及其表1角点(由“+”标出),图1(b)为用我们的方法给出的n(n,=n,) Dynamic relaxation Winner-take-all Loser-take-no匹配结果,运行时间为4s;图1(c)为LTN的匹配结17果,运行时间为70s;图1(d)为WTA的匹配结果运行279151时间为1sABAABCDCDAABAA 3CDCDYH=取图2820计算机学报1999年图2给出了两幅真实图像的匹配结果(因为足题比以上两个要复杂一些.WTA给出的匹配效果球的角点是对称的,有很多可能的匹配).WTA的很差我们的方法(图2(b))和LTN(图2(b))的结结果是完全错误的(图2(d).我们的方法(图2(b))果都是令人满意的.如图2一样,但我们的方法的运和LTN(图2(c))都给出了正确的结果(注意两个足行时间(10s)比LTN(1099s)少得多.错误匹配的原球方向是相反的).但我们方法的运行时间(4s)比因在于:(1)角点匹配中存在误差(如图3(b)中点LTN(539s)少得多31的匹配);(2)距离较近的点易被混淆(如图3(b)图3给出了两幅运动图像的匹配结果.这个问中的点4和5).这是式(1)所定义的模型的局限性|[这些实验表明:WTA的缺点在于匹配准确率3Lisz. Inexact matching of3 D surfaces, visIon, speech and往往太低;LTN的准确率高得多,但计算复杂性又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本文所发展的松弛方法较好地解决了这两个难ICCAD, Hong Kong, 1988问题:它的计算复杂性不高,但相对而言,匹配准确5 pollards b, Mayhew JE W, Frisby JP.PMF: A stereo率和鲁棒性是最高的respondence algorithm using a disparity gradient limit. Percep-tion,1985,14:449-1706结论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态松弛,通过构造一个动力学系统来实现松弛过image processing. International Journal of Computer Vision程我们的方法与传统的WTA和LTN的区别在于1997,23(1):45-78更新策略是渐进的.由此而导出的算法具有较低的Xu G, Zhang Z. Epipolar Geometry in Stereo, Motion and Ob-ject Recognition: A Unified Approach, Netherland: Kluwer A复杂性和高的准确率,较好地解决了复杂性和高准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)