图像配准的复制动力学方法

第27卷第11期计算机应用研究VoL 27 No. 112010年11月Application Research of ComputersNov.2010图像配准的复制动力学方法鄢余武,孙亚军,姚小强(空军工程大学导弹学院,陕西三原713800摘要:为了实现高精度图像配准把单个像素看做参与博弈的局中人,将图像配准视为图像中各个像素与其周边像素的演化博弈过程。为了寻求博弈的均衡点,根据配准问题的特点,对复制方程进行修改,提出基于修改后的复制方程的图像配准方法。新方法是完全基于问题域建立起来的,能实现对任意形变的高精度配准,并且配准精度与分辨率无关。针对刚性形变的遥感图像和非刚性形变的医学图像进行了两组实验,结果表明了新算法的有效性关键词:图像配准;演化博弈论;复制方程;适应度;形变中图分类号:TP391文献标志码:A文章编号:1001-3695(2010)114386-03doi:10.3969/j.isn.1001-3695.2010.11.110Replicator equation based image registration approachYAN Yu-wu, SUN Ya-jun, YAO Xiao-qiangMissile institute, Air Force Engineering Uninersity, Sanyuan Shaanxi 713800, China)Abstract: If model a pixel as a player, then image registration can be viewed as an evolutionary game, in which each pixelplay with its neighbors. To find an equilibrium point of the evolutionary game, this paper adapted the well known replicatorequation according to characteristics of image registration, and proposed a registration algorithm based on the adapted replicator equation, It developed the novel algorithm on problem domain totally, it could register any complex deformation with highand furthermore the accuracy was robust to image resolution. Experimentations on rigid-deformed remote sensing iages and nonrigid-deformed medical images are designed, the results show that the proposed approach is effectiveKey words: image registration; evolutionary game theory; replicator equation; fitness; deformation其他特征;E(T)是惩罚项旨在保证得到的变形场满足0引言某些必要的属性,如平滑性、正反变换的一致性、拓扑保持图像配准是通过寻求空间变换,使两幅或多幅图像的对应性等。点达到空间位置上的完全一致,如图1所示。图像配准算求取最优解T的常用优化算法有Powe法、梯度下降法、法最早是在1981年提出的lua- Kanade算法2中出现,经过遗传算法、模拟退火算法和粒子群算法等。这些算法将配准看多年的发展,图像配准算法在计算机视觉领域得到了广泛的应做单纯的优化问题,与问题域结合得不够紧密。由于能敏函数用,应用领域包括目标跟踪、运动分析、立体视觉和图像拼接般是逆凸和非线性的脱离问题域仅仅从函数优化的角度出等,因此研究优良的图像配准算法具有重要意义发很难实现高精度的图像配准本文在分析图像配准特性的基础上将其归结为像素博弈问题从演化博弈论的角度提出一种基于复制方程的图像配准方法。新方法是基于问题域建立起来的,能实现对任意形变的高精度配准,且配准精度与分辨率无关。1图像配准的博弈特性图1图像配准示意图设y为颜色空间,P:→为浮动图,P:Dp→为T:般地配准能量函数由相似性测度和惩罚项构成,分别参考图,其中n、m是图像的支撑域待寻求的空间变换为称为外力内力。配准是一个外力和内力互相竞争最终达到n→+D。为了求解最优解T,通常将配准问题转换为能量函平衡的过程外力驱动浮动图进行形变而内力则对形变过程数的极值求解问题,并采用优化法对能量函数进行迭代最优搜进行必要的约束。索。配准能量的一般表达式为将图像视为空间上有序的像素集合形变过程中每个像素E(P,P以7)=E(P,P+En(T也受到图像中其他像素的约束,即内力。其中:E(P,P)是相似性测度表示图像特征之间的匹配如果找中国煤化工则配准可以视为图像程度可以直接采用图像的灰度信息,也可以采用图像的中各CNMHG衡时认为配准结束。收稿日期:2010-05-24;修回日期:2010-07-2作者简介:都余式(1984-),男,江西上饶人,博士研究生,主要研究方向为图像配准与融合(yl25@163.com);孙亚軍(1982-),男,陕西风翔人,硕士研究生,主要研究才向为馆号与信息处理;姚小强(1983-),男,河南洛阳人,磺士研究生,主要研究方向为图像处理第11期鄢余武,等:图像配准的复制动力学方法4387博奔可以采取合作或非合作的方式进行非合作博弈论是在分布式决策环境下分析局中人为3基于复制方程的图像配准算法最大化个体效用的最优策略选择问题。演化博弈是非合作博弈的一个分支它以有限理性的群体为研究对象进一步分析3.1对复制方程的修改策略在群体中的长期稳定性问题较好地克服了经典博弈论中与生物系统相比,图像配准有如下特性理性假定及多重均衡的困难。演化博奔的纳什均衡具有群体a)复制方程描述的系统是伪动态的,系统的收益矩阵一稳定性,同时还可揭示采取均衡策略的个体比例般能事先确定;而图像配准表示了一个真实的动态系统,每轮迭代中每个个体的适应度都要重新计算。2复制方程b)在复制方程描述的进化过程中,演化行为由固定的收益矩阵确定;而演化图像配准过程的进化轨迹由参考图确定早在1930年, Fisher就提出了著名的自然选择基本原理c)复制方程假设种群中的个体可以被重复选择,而图像并被广泛用于研究生物进化过程的动力学行为。该原理配准要求每个个体至多只能被选择一次表明种群的适应度增长率等于同一时刻适应度方差的2倍d)复制方程对所有个体同等对待,而图像配准算法一般即E=2Σ1a1(e1-E)2。其中;a是个体i在种群中的出现要惩罚选择同一个点作为潜在复制子的竞争个体。几率;e,是i的适应度值;E是整个种群的加权平均适应度;E要对复制方程进行相应的修改,以适应精确自动图像配准是E对时间t的导数。在种群进化过程中,如果没有发生变的需求。首先将图像表示为像素点集:P=1P2i∈Dp},异,后代将完全继承父辈的特性,所有个体都根据预定义的模P=|perl式(称为纯策略)决定自己的行为。叫1对时间t的导数1)建立潜在的对应关系设变换T对n中的任一点i进行空间变换产生的位移为式(1)描述了自然选择的动力学系统称为复制方程。种a,N为i的邻域P,的配准能量为群在时刻t的状态向量u(t)={a(t),u2(l),…,an()}位于E(p…)=p-p…42+A减-4n维欧式空间S={w∈R:∑a1=1,o1≥0}的标准单纯形中。P2的演化目标是求取在种群遗传中种群表示所有可能的个体设A,表示个体i(2)的后代数量的期望值则种群的收益矩阵可以定义为U={2)参数推导AA}l。在博弈论中种群表示策略的集合,设山表示采用策略复制方程假设相对增长率aa1等于个体适应度与种群i对抗策略j所获得的收益则策略i的适应度为e=E,平均适应度E=∑叫的差。为了减小图像分辨率对最终配整个种群的加权平均适应度为E=Σ∑叫叫。复制方程具准结果的影响,本文用相对适应度差代替式(1)中的绝对适应有如下优异特性度差:a)因为Σ,ω=0,所以状态向量w(t)始终在单纯形S中。这意味着状态向量始终表示个体在种群中的出现几率的=的b)如果U={al}对称,则E始终随时间增长由于∑=0仍然成立,演化配准过程的轨迹仍然处于单c)如果U={ug对称则向量(t)和Uk(t)的点积是纯形S,内。Lyapunov函数。因此,复制动力学系统始终是稳定的将式(3)重写为d)如果w∈S是进化稳定的,则w是渐进均衡的。系统不收敛。当n≤3时,复制方程没有极限环;当n≥4时,对于特定的收益矩阵复制方程存在极限环。如果S内部不存在不积分,得到动点,则每条轨迹都收敛到Sn的边界上。如果边界具有排斥(0.5e;-E)性则S,内部存在一个唯一的不动点,该不动点对应于S内部所有轨迹的时间平均。)适应度估计特性a)实际上使得状态向量通过动力学本身实现了归设(P,P,4)是潜在的对应点则个体P的适应度定义为化;特性b)确保在特定条件下,系统能随时间的推进逐步改善性能;特性c)保证了在特定条件下进化系统是稳定的,不管系4)利用多对一映射建立潜在的对应关系统从哪个点开始进化;特性d)揭示了什么情况下存在最优解复制方程假设种群中的所有策略都可以被任意数目的局以及在何处取得最优解。这些特性对于图像配准来说都是成人采用而图像配准算法一般认为图像P中的一点至多只立的。特性a)对潜在对应点的概率进行归一化特性b)表示能对应于图像P中的一个点反之亦然。P中某个点的所有整个种群的平均配准误差随迭代次数近似单调递减;特性c)图像必须进行竞争,最终获得图像间可能的对应关系。此时的揭示了最终的配准结果与初始化参数无关因此极大地简化了对应关直实的对应关系需要通过以下三个步骤进参数的初始化过程:特性d)说明了如何有效地搜索最优状态行评估中国煤化工变量,如何评价最终的状态变量。当系统稳定时,=o(e1-CNMHGE)=0,则o4=0或E=e。a=0表示个体i死亡了,因此i是b)计界系积学,at+4+“;+,∈D;个已消亡的点;E=e表示讠存活着因此i是一个位于重叠c)重新评估每个对应关系(P,P,4)的概率,a区域的点a'4,i∈4388计算机应用研究第27卷5)平均场退火RMSE值越小配准效果越好。实验结果比较见图3,其中的横采用确定性退火优化潜在对应关系(P,P1,d)的概率坐标表示分辨率,如横坐标取值100表示分辨率为100×1其中:参数B(B>0)表示反转温度。3.2新算法综合以上因素得到如下算法图3不同分辨率下的配准性能比较(遥感图像)初始化。设初始反转温度B=岛,反转温度增加速率为由图3可知,RE算法的RMSE对分辨率变化不敏感,而β,终止反转温度为月终止时相邻代之间的相对变异为p,最NMl-A算法的RMSE随分辨率降低增加较快,并且RE算法的大选代数为l,选代数k=0,a(=l∥/Dp|。RMSE小于NM-A算法的RMSE。即在同一分辨率下,RE算a)若B=By,终止。法的平均精度高于NM|-A,而且对分辨率的变化具有较好的鲁b)若相邻代之间的相对变异小于p或k≥l,终止。棒性。同时,随着分辨率的降低,RE算法的计算量下降较快c)根据式(2)建立P、P间潜在对应关系(p,P4)的集但总体上看RE算法的计算量大于NM-A合;根据式(5)计算种群P中每个个体P的适应度e;计算整实验2非刚性形变的医学图像配准个种群的加权平均适应度E=∑汕1"c/Σa1;根据式(6)基于光流场模型的 Demons算法0是一种应用广泛的先更新状态变量a11);根据惩罚过程对多对一映射进行惩罚。进的图像配准方法。实验2将RE与 Demons算法进行比较,d)对目标函数进行寻优,更新位移向量d评价其性能。e)an←1(),k←k+1,转到b)实验数据采用经过仿射预配准的医学MR图像,灰度级为DB+BB,转到a)。0-255,原始图像取自BrainWeb(htp://www.bicmni.megillca/ brainweb)。取图4所示的MR图像作为参考图,并对参考4实验结果与分析图进行人工形变得到两种浮动图,如图5(a)所示。RE和De为了验证所提出算法的有效性,通过两组实验将本文提出mons算法的配准结果分别如图5(b)(c)所示。从配准结果可的基于复制方程的配准算法(以下简称RE算法)与两种典型算知, Demons算法不能正确配准第二种形变,因为图中一些点的法进行比较实验在PC(P43.06 GHz CPU,1GB内存, Fedora10形变很大(超过了10个像素),算法陷入了局部最优;而RE算操作系统 MATLAB1)上完成。两组实验中E算法的参数法仍然能够正确配准,寻优能力优于 Demons算法。均取A=0.0000.=1.05,B=L.0,=10,p=0.00l。实验1刚性形变的遥感图像配准实验采用的真实遥感图像取自 Vision Research Lab(hp://ion,ece.ucsb.edu),如图2所示。对图2中的图像进行多分辨率处理,得到一组大小为200×200、180×180、160160、140×140、120×120、100×100、80×80和60x60的图像并在各个分辨率上进行配准实验图4备考图(a)参考图(b)浮动图(c)标准图图2实验1用到的遥感图像基于互信息量的配准算法是目前公认较好的配准方法在图像配准领域取得了极大的成功。根据图像特点实验1采用基于归一化互信息( normalized mutual information,NM)和仿射(aine)变换模型的算法(以下简称NMl-A算法)与RE算法进行比较。NMlA算法的插值方法和优化方法分别采用双线性插值和遗传算法,遗传算法的实现采用 MATLAB的g函数参数 StallTimeLimit设为lnf,参数 HybridEn设为@ fminsearch,即遗传优化结束后继续进行局部寻优取运行时间t配准结果和标准图的均方根误差RMSE为中国煤化工指标(指标均取20次实验的平均值),对两种算法进行比较。RMSE定义为CNMHG结果√m与实验1类似,对参考图和形变1对应的浮动图进行多分辨率处理得到一组大小为200×20、180×180、160×160、140×140、其中:P2-p表示两幅图像在i处的颜色差,n为像素总个数,120×120、100×10080×80和60x60的图像,(下特第4393页第11期李建锋,等:一种基于PCN的医学图像边缘提取方法4393·4结束语[8]ECKHORN R, RETTBoECK H J, ARNDT M, ef al. A neural net-ork for feature linking via synchronous activity:本文通过分析基本PCNN的特性提出了一种改进的PCvisual cortex and from simulations[ M]. Cambridge: Cambridge Uni-NN图像边缘提取的方法,并将该方法应用于医学图像的边versity Press, 1989: 255-272提取该方法很好地结合了PCNN仿生物视觉的特性和经典边[9〕 RElTBOECK H J, ECKHORN R, ARNDT M,ea. A model for缘检测算子的优点。实验结果也表明,本文算法在医学图像的feature linking via correlated neural activity[ M]. New York: Spring-处理上无论是在边缘的提取能力还是对椒盐噪声的抑制能力方面都优于基本的PCNN以及Cany,sobe、 Prewitt Roberts等[ 10] ECKHORN R, RETTBOECK HJ, ARNDT M,cal. Feature linking经典边缘检测箅法,从而证明了本文方法的可行性。via synchronization among distributed assemblies: simulation of results参考文献[11]JOHNSON J L, PADGETT M L. PCNN models and applications[J][1] ELINABROUK A, AGGOUN A. Edge detection using local histogramIEEE Trans on Neural Networks, 1999, 10(3): 480-498nalysis[ J]. Electronics Letters, 1998, 34(12): 1216-1217.[ 12] LIU Qing, MA Yi-de, ZHANG Shao-gang. Image target recognitionDaviSLs.Asurveyofedgedetectiontechniques[j].computerusing pulse coupled neural networks time matrix[ CJ//Proe of theGraphics and Image Processing, 1975, 3(4): 248-270.26th Chinese Control Conference. 2007: 96[3] BASU M. Gaussian-based edge-detection methods: a survey [J). [133 Lu-ping. YT Zhang. A mixed noise image filtering method usingEEE Trans on Systems, Man, and Cybemetics-Part C: Applica-ighted-linking PCNN[ J]. Neural Computing, 2008, 71(13-15)tions and Reviews, 2002, 32(3): 252-2602986-3000.[4] TAO Hai, HUANG T S. Color image edge detection using cluster[14]MA Yi-de, LIN Dong-mei, ZHANG Bei-dou, e al. A novel algo-lysis[ C]//Proc of Intemational Conference on Image Processorrithm of image enhancement based on pulse coupled neural networktime matrix and rough set[ C]//Prmc of the 4th Intemational Confe-[5] RUSSO F. Edge detection in noisy images using fuzzy reasoningzry Systems and Knowledge Discovery. 2007: 86-90[C]//Proc of IEEE Instrumentation and Measurement Technology [15]u Min, CAl Wei, TAN Zheng. A region-based multi-sensor imageConference. 1998:369-372fusion scheme using pulse-coupled neural network[J]. Pattem[6] SIYAL M. Edge detection with BP neural networks[ C]//Proe of thRecognition Letters,2006,27(16):1948-19564th Intemational Conference on Signal Processing-. 1998: 1382-1384. [16]DI Lan, LIN Y, LU Li, An algorithm for image edge detection using[7] SIDDIQUE J 1, BURNER K E. Wavelet-based multi-resolutionimproved PCNN C//Proc of IEEE Intemational Conference onedge detection utilizing gray level edge mape[C]//Proe of IEEEGranular Computing. 2009: 136-139.(上接第43883页)并在各个分辨率上进行配准实验。以参考图两组配准实验表明了新算法的有效性。和配准结果的均方根误差RMSE和运行时间为标准比较两参考文献种算法对形变1的配准性能比较结果如图6所示。由图6可[1] ZIToVA B, FLUSSER J. Image registration methods:asmr[门知在相同分辨率下,RE算法的精度高于 Demon,并且对分辨Image and Vision Computing, 2003, 21(11): 977-1000率的变化具有鲁棒性;两种算法的计算量都随分辨率提升而增[2] LUCAS B D, KANADE T. An iterative image registration technique大,但总体上RE算法的计算量比 Demons大。相比于实验1with an application to stereo vision[ C]//Proc of Intemational Joint此处RE算法的计算量较少,这是由于所用的图像已经过仿射Conference on Artificial Intelligence. 1981 674-679预配准,且非刚性形变较小[3] GLOCKER B, KOMODAKIS N, TZIRITAS G, et al. Dense imageregistration through MRFs and efficient linear programming[J]. Med-ical image Analysis, 2008, 12(6): 731-741[4] ALEXANDER W, PAUL F. Fast phase-based registration of multimo-0dal image data[ J]. Signal Processing, 2009, 89(5): 724-73760182080100120140160180200[5] THOMAS L V, JOEL S B. Evolutionary game theory, natural selec.图6不同分辨率下的配准性能比较(医学图像tion, and Darwinian dynamics[ M]. Cambridge: Cambridge Universi-RE算法的良好性能根源于博弈论,由于将图像视为局中人(个体)集模型的自由度远大于传统的配准算法,有利于提[6]张维迎,博弈论与倌惠经济学[M]上海:上海人民出版社,高算法的配准能力和配准精度。从运行机制上看,RE算法是一种自下而上的方法每个个体都有自己的演化目标群体通7N0wAKM, SIRMUND K. Evolutionary dynamics of biological game过迭代的方式收敛到均衡点,具有“涌现”特性这使得算法能004,303(5659):793实现对任意形变的高精度配准,且配准精度对分辨率变化不敏8] STADLER B MR, SRADLER P F. Molecular replicator dynamic慼鲁棒性好,但相应的代价是计算量的增加1s,2003,6(1):47-77[9] YAN Yu-wu, uU Jin -mang, TONG Ming. A game-theoretic approach5结束语for nonrigid medical image registration[ C ]//Proc of Intemational中国煤化工 Computer Science.200研究配准能力强精度高的图像配准算法在遥感导弹成像制导、无人机导航、手术导航等领域具有重要意义。本文分[10]wCNMHGal. validation of析了图像配准具有博弈的特性并从演化博弈论的角度把迭代cele-rated'Demons'algorithm for deformable image registration in ra图像配准看做一个演化过程提出了基于复制方程的图像配准diation therapy[ J]. Physics in Medicine and Biology, 2005, 50算法。针对遥感图像(刚性形变)和医学图像(非刚性形变)的12):2887-2905