（计算机科学与技术专业论文）基于互信息的图像配准并行算法研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 图像配准是图像融合、图像分析、目标变化检测与识别等问题中的重要步骤， 其应用遍及军事、遥感、医学、计算机视觉等多个领域。互信息( m u t u a li n f o n n a t i o n ) 来自于信息论，是两个随机变量统计相关性的度量，由于其具有无需预处理、自 动化程度高以及鲁棒性强等特点，近几年将互信息作为一种相似性测度进行图像 配准成为图像处理领域的研究热点。随着传感器、遥感平台等相关技术的发展， 信息的获取途径越来越多，获得的数据量也随之急剧增长，而许多应用领域对图 像配准处理速度的要求也越来越高。显然，传统的单处理器配准处理串行算法已 经无法满足这样的运算需求，而并行处理是解决这一问题的重要技术手段。 目前，国内外的研究主要集中在提高配准质量上，而针对海量数据配准和强 实时性配准的大规模并行算法研究尚处于起步阶段。因此研究并实现图像配准的 并行算法，将大大提高配准处理效率，具有广阔的应用前景。 本文针对上述需求，重点针对基于互信息的图像配准并行算法进行深入研究 和实践工作。本文的主要工作和贡献如下： 1 、深入研究了互信息理论的计算方法。采用直方图和p a r z e n 窗两种方法计算 互信息，并分析比较了这两种计算方法。实验结果表明，直方图法得到的结果比 较粗糙，但计算速度较快。基于p a r z e n 窗估计的计算方法，样本估计的效果取决 于窗函数的形式和宽度，在样本数目足够大时，计算精度高，但是在计算时需要 进行多个累加和，计算量很大。 2 、深入研究了图像配准算法的三种常用的相似性测度互信息、相关系数、 差方和，并通过实验从计算时间、锐度、对噪声的容忍性以及对多模图像配准的 影响等方面分析和比较了三种测度的优劣。实验表明，在多数情况下，互信息的 配准精度是这三种相似性测度中最高的。 3 、提出并实现了一种基于互信息的刚性图像配准并行算法。该算法基于刚性 变换模型，图像数据采用块( b l o c k ) 划分，在算法运行过程中实现了数据分块并 行读入，较好地解决了负载平衡问题。采用二叉树规约方法计算互信息，加快配 准速度。实验结果表明该算法获得了良好的加速比，可扩展性好，并行效率较高。 4 、提出了一类( 基于基函数) 非刚性图像配准并行算法设计模型，并应用该 模型对一种具体的非刚性串行算法进行了并行化。该模型采用并行读入交叉划分 数据、并行自动选取标记点、二叉树规约计算互信息和并行输出分块图像。理论 分析表明，该算法设计模型的并行效率高，通用性较强。 主题词：并行，图像配准，互信息，刚性，非刚性，相似性测度，二叉树规约， 算法模型 第1 页 国防科学技术大学研究生院学位论文 a bs t r a c t i i i l a g er e g is t c a t i o ni s 觚i m p ( 瓜锄tp r o b l e mi ni m a g em s i o n ，i m a g e 锄a l y s i s ， c h a n g ed e t e c t i o n 锄dt a 唱e tr e c o g i 血i o n a p p l i c 撕so fi l i l a g er e g i s t r a t i o na r ei l ln l e d o m a i l lo fn l i l i t a = d ，r e m o t es e n s e d p r o c e s s i n g ，m e d i c a l ，c o m p u t e rv i s i o n 锄d o n t h em u t u mi n f 0 蛐a t i o n ，w 1 1 i c ho r i g i n a t e s 丘_ 0 mi i l f o 加 1 a t i o nt h e o 巧，i st h em e a 剐l 佗 o f 觚。瑚d o m 谢a b l e ss l ：a ：t i s t i c a lr e l e v a i l c e ，a n dc 肌b ea p p l i e d 证i n l a g er e 酉g 嘣i o n 嬲as i m i l 撕够m e 嬲u r e s i i l c e 廿l em u t l l a li o r m a t i o nh 嬲a d v 卸舾g e si n c l u d i n g p r e - p m c e s s i n g ，r o b u s t i l e s s 锄dl l i g l la u t o m a t i cp c e s s i n g ，i tb e c o i n e sa1 1 0 tt o p i ci n i i i l a g er e g i 蛐r a t i o n w i n lt l l er 印i dd e v e l o p m e n to f n s o r 锄dr e m o t es e n s i n gp l a t f o m t e c l l i l o l o g y ，n l e r ea r em o r ca n dm o 他a p p r o a c h e s 趾ds o r t so fm ei i l f b m l a t i o nw ec 趾 g c t a sar e s u l t ，t 1 1 ed a ：t a s e t s g o t t e n 台1 0 m t l l es e i l s o ra r c i n c r e 弱i i l g n e m e n d o u s l y m e 锄、) v ! 1 1 i l e ，r a p i dp r o c e s s i n gt e c h n o l o 百e s 强dr e a lt i i l l ep c e s si l lm 锄y d o m a i l l sb e c o m em o r ea n dm o r eu 唱e n t ，髓dt l l e 缸a d i t i o n a ls i i 玛l e - p r o c e s s o rc 锄t a c l l i e v e 也er e q u h m e n t h o 、v e v e r ，廿l ek e yt 0 l v et h ep r o b l 锄i su s i n gp a r a l l e l p r o c e s s i n g s i i l c eb o 廿1t h en e e df o ri 1 1 1 a g er e 百s 删o n 雒dt h ea m o u n to fd a ：t at 0 r e g i s t e ra r eg r o w i n gt r e m e n d o u s l y ，m ei m p l e m e n t a t i o no fa u t o m a t i ci m a g er e g i 蛐眦i o n m e m o d so nl l i g h p e r f o m l 砒l c ec o m p u t e r sr l e e d st ob ei i l v e s t i g a t e d n o w a d a y s ，t h ec 岍e n tr e s e a r c hi sf o c u s i i 唱o ni i l l p r 0 v m gm er e g i s 妇t i o nq 叫i 够 m o s t l y ，b u tt h er c s e a r c ho f p 盯a l l e lp r o c e s s i n go nt l l el a 唱ei m m b e ro fd a t as e t s 趾dt l l e r e a l t i i i l er e q u e s ti i lr e g i s 仃a t i o na l g o r i m m sa r ei i lt h eb e g 蛐g s ow ed os o m er e s e 疵h o np 删l e la l g o r i m m sf o ri i i l a g er e g i s 衄t i o nt h a tc o u l dm a k eg r e a tp r o g r e s si 1 1t h e e m c i e n c y 觚dt l l es p e e do fi l n a g er e g i s 锄t i o n ，w h i c hc 觚b e 印p l i e db r o a d l y t l l i sp a p e r 抽sa tt 1 1 er e s e a r c h 觚di n l p l e m e n t a t i o no fp a r a l l e la l g o r i m l sf o r i i i l a g er e g i s 觚t i o np r o c e s s i i 培b 嬲e do nm 咖a li n f 0 姗a t i o n t h ec o m r i b u t i o 璐觚d 托l e v 锄tw o r ki i lm e p 印e ra r e 嬲f o l l o w s ： f i r s t l y ，、ed i s c u s s 廿l em u t i l a li i l f o 加1 a t i o nc o m p u t a t i o nm e t l l o d sw h i c ha r eb a s e d o nh i s t o g r a m 赳l dp a r z e nw i i l d o w a n dt l l 肌、wa n a l y z et h e m 锄dc o m p a r em e mw i t h e a c ho l c r ns h o w st 量l a tm em e m o db 嬲e d0 nh i s t o 鲫i sc o 盯s e r ， b u ti ti sf 奴e r 廿l 觚 t l l em e m o d b 弱e do np a r z e n 讹d o w 1 1 1 ep a r z e nw i i l d o wm 弛0 di sd e t e 吼硫db y 也e 讹d o w 劬c t i o n sf o ma n d 、) l ，i d m w i t l l “sm e l o d ，w h e ns 如1 p l e sa r ee l l o l l g l li ti s p r e c i b u ti t sc o s ti sg r e a tb e c 黜i tt 粥t ob ea d d e du pm a i l yt i m e s s e c o n d l y ，w ed i s c u s st h r e e 勺l ，p i c a lk i i l d so f s i i l l i l 撕够m e a s u r e ，w k c ha r em 毗u a l i 幽咖a t i o n ，c o n e l a t i o nc o e 笳c i e n ta n ds 啪o f s q u a r ed i 虢r e l l c e s n 磁l ，t 1 1 e p e r f o m a n c eo fm e s em e a s u r e si sc o i i l p a r e d 雒da n a l y z e db yc o m p u t i i 培t i i l l e ， 第u 页 国防科学技术大学研究生院学位论文 s h a 印n e s s ，s e n s i t i v i t ) ro fn o i s ea n de f r e c to nm u l t i m o d a ji m a g er e 西s t r a t i o n t h e r e s u h so fe x p e r i i n e n t ss h o wt h a tt l l e s es i i i l i l 耐t ) ，m e 鹊u r em e t l l o d sh a v ed i 伍：陀n te f f e c t 锄dp 刮f o m 幽c ei 1 1 也ed i 脑- e n ta p p l i c a t i o nc 沁u m s t 锄c e s ，b u tt 1 1 em 咖对i i l f o m 旧t i o n i s m o r e p r e c i t l l i r d l y ， ar i g i dp a r a l l e li n l a g er e g i s 乱龇i o na l g o r i t h mb 嬲e do nm u t l l a li i l f o m 掇t i o n i sp r e s e n t e d 锄dh p l e m e n t e d 1 k 2 l l g o r i l l 皿u 辩sr i g i d 仃趾s f o m ，a n d “l v e s 廿舱 p r o b l e mo fl o a db a l a n c i i 培w i d l 血a g ed a t av e n i c a ld i v i s i o n ，d a 诅b l o c k 阳r a l l e l i n p u t t i i l g b i 册d rt r e er e d u c t i o ni su s e di i lp a r a l l e lc o n l p u t i i l gm u _ t i 】a li i l ：f o m l a t i o n ， w 1 1 i c hs p e e d su pt 1 1 er e 西s 仃a t i o nr a t ea i l di 1 1 c r e a st h ec o m p u t a t i o ne f j f i c i e n c y t h e e x p e r i m e n tr e 叭l t ss h o w 如nt h ea l g 嘶n l l nh 嬲ag o o ds 】p e e d u p ，s c a l a _ b i l i 姚锄dk 曲 p a r a l l e le m c i e 眦y f i i l a l l l y ，w ep r e s e n tap a r a l l e ln o n - r i 西di m a g er e g i g n 锄i o na l g o r i m mm o d e l ( b 嬲e d o nb a s i cf u n c t i o n ) ，锄dt ：h e nw eu s et 1 1 er n o d e lt op a r a l l e la n o n r i g i da l g o r i t h m n 圮 p 删l e l t e c l l i l o l o g i e sa p p l i e dt 0m em o d e ia r ep 删l e li n p u n i n g 恤c r o s s 娟v i s i o no f t l l ed a t a ， p a r a l l e la u t o m a t i cs e l e c t i i l gm a r k e r ，b i 彻r y1 r e er e d u c t i o nc a l c u l a t i o no f 廿l e m u t u a li i l f o 肌a t i o n 觚d p a r a l l e lo u t p 戚迦也eb l o c ki m a g e s 1 1 1 e o 硎c a la 砌y s i s s h o w s 吐l a tm ea l g o r i m mm o d e lh 弱a1 1 i 曲p a r a j l e le f ! f i c i e n c ya 1 1 da r e l a t i v e l ys t r o n g v e r s a t i l i t ) r k e yw o r d s ：p a r a l l e l ，i m a g er e g i s t r a t i o n ，n l u t = u a li i 血m a t i o n ，r i g i d ，肿n 前g i d ， s i n l i l a r 时m e a s u r e ，b i i l a 叮行e er e m l c t i o n ，a l g o r i 曲mm o d e l 第1 i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1互信息的基本性质表1 4 表3 1 各种相似性测度计算时间表_ 2 0 表4 1互信息的计算与优化在整个计算过程中所占百分比表3 l 表4 2 四种图像的配准时间表( 单位s ) 3 7 第i v 页 国防科学技术大学研究生院学位论文 图1 1 图2 1 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图4 1 图4 。2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图5 1 图5 2 图5 3 图5 4 图 图 图 图 图目录 四种基本的图像空间变换图8 像素点变换图1 6 实验中使用的图像数据2 0 不同图像组的x 轴、y 轴平移以及旋转变换相似性测度曲线图2 2 图像金字塔表示情况下的各级图像的相似性测度曲线图2 4 不同信噪比情况下的相似性测度曲线图2 5 多模l e l 擒图像2 6 多模l e i l i l a 图像对x 方向平移的相似性测度曲线图2 6 p v 示意图2 9 p o w e l l 优化过程图3 0 刚性配准算法流程图31 三种图像数据划分方式图3 2 负载平衡的数据分布图3 2 二叉树归约算法图3 3 并行配准算法流程图3 4 待配准图像与配准结果图3 6 并行算法加速比3 7 并行算法效率3 7 非刚性配准的基本过程图4 2 非刚性配准算法过程图4 4 非刚性配准并行分析图4 5 交叉划分图4 5 边界选取图4 6 并行非刚性算法模型流程图4 7 非刚性配准算法流程图4 9 分层互信息非刚性配准并行算法过程图5 0 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：基王亘焦! 垦煎圈篮壁壅羞短簋洼珏窥生塞翌 一 学位论文作者签名：乏乙垄址 日期：z 9 。7 年月，7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王亘焦垦鲍图像壁准羞盈篡洼盟窥生塞趣 学位论文作者签名：刍圣堑丝 作者指导教师签名： 日期：加矿年么月7 日 日期：己一年f2 月7 日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究背景 目前我们所处的时代是一个信息的时代，无论是对信息的获得、加工、处理还是应用 都有了飞跃地发展。图像作为一种十分重要的媒体和手段已越来越受到人们的重视。随着 二十世纪九十年代的第三代计算机的问世，多媒体技术得到了前所未有的迅猛发展，这极 大地推动了计算机图像处理技术向更高级方向地迅速发展。同时，图像的处理技术也愈来 愈广泛地应用于众多的科学和工程领域。目前，图像已成为工程学、计算机科学、信息科 学、统计学、物理学、化学、生物学、医学甚至社会科学等领域各学科之间学习和研究的 对象。 在一些用图像进行研究和分析的领域中，常常是将图像通过打印在胶片上或挂在灯箱 上等手段来进行读片，但由于图像的分辨率和对比度的差异，以及成像时空间坐标的变化， 使得人们很难在脑海中精确地将这些图像综合起来。图像配准可以利用计算机图像处理技 术，将这些图像统一在公共的坐标系中，通过计算机的可视性来提供辅助。通过图像的配 准，我们可以综合从不同的传感器收集的信息、可以在不同时间或者在不同条件下所获得 的图像之间寻找变化、可以从移动的相机所拍的图像或者移动的物体的图像中收集三维信 息以及进行基于模板的模式识别等。 目前，图像配准已是数据融合、图像分析、目标变化检测与识别、图像镶嵌等实际问 题中的重要步骤，其应用遍及遥感、军事、医学、计算机视觉等多个领域。由于图像配准 的重要价值和广阔的应用前景，正日益受到国际上越来越多科研机构的高度重视，是图像 处理领域中重点和热门的研究课题。 1 1 1 图像配准的概念 图像配准是对不同时间、不同视场、不同成像模式的两幅或多幅图像进行空间几何变 换，使得各个图像在几何上能够匹配对应起来。图像配准的主要目的是去除或者抑制待配 准图像和模板图像之间几何上的不一致，包括平移、旋转和形变。 图像配准的处理过程中可以采用物理模型拟合或者是采用空间变换的方法进行处理。 对于在不同时间、不同视场、不同成像模式等不同条件下获取的两幅图像进行配准处理， 就要定义一个物理模型或者一个空间变换配准函数，并寻找一个变换关系，使得经过该变 换后，两幅图像间的相似性达到最大( 或者差异性达到最小) ，即两幅图像得到空间几何上 的致。我们用j 。( ) 和j ：( ) 表示待配准的两幅图像，其中( ) 表示图像可能为 2 d ( d i m e n s i o l l ) 或3 d 。当配准的图像是2 d 时，( ) = ( x ，力，2 ( ) = ，2 ( 墨y ) 。当配准的 图像是3 d 时，厶( ) = 厶( x ，y ，z ) ，：( ) = ，：( x ，j ，z ) 。不失一般性，不妨设，。( ) 为模板图像， ，：( ) 为待配准图像，也常称为浮动图像。首先，要选择合适的配准测度： 第1 页 国防科学技术大学研究生院学位论文 c ( r ) = c ( 小) ，2 ( ) ) ( 1 1 ) 式中，c 是相似性测度，也称为代价函数( c o s t f u n c t i o n ) 或目标函数( o b j e c t f u n c t i o n ) ， r 为待配准图像与模板图像之间的空间变换。图像配准的过程可归结为寻求以下最佳变换 o + = a r g m a x c ( r )( 1 2 ) 配准的过程就是求相似性测度的全局最大值。o 表示变换模型的参数，参数可能的搜 索范围为搜索空间，参数的个数称为变换模型的自由度。参数的个数跟变换模型有关，不 同的变换模型，其自由度往往是不同的。例如3 d 刚体变换，o = ( f ，f ，f ：，以，口，见) ，f ，f ，： 是待配准的两幅图像相对于x ，y ，z 坐标轴三个方向的偏移量，p ，秒。，见是绕x ，y ，z 坐标轴三 个方向旋转角度。对于2 d 变换，其自由度比3 d 少，只有三个自由度。 由于图像变换包含多个参数，图像配准是一个多参数优化问题。对于相似性测度函数， 是通过搜索函数的全局最大值来得到图像变换参数。图像配准中相似性测度的选择是配准 的核心所在，也是不同配准算法的差异所在。当前常见的相似性测度有相关系数、互信息、 差方和等。在图像配准中选择一种合适的相似性测度，是配准算法中的一个重要问题。 1 1 2 图像配准技术的发展 图像配准技术的发展历史大致可以分为三个阶段。2 0 世纪8 0 年代初，图像配准主要 应用在d s a ( 数字减影血管造影) 方面。它采用基于图像灰度的方法，针对二维图像，通 过检测相关性和灰度值的差异来决定刚性变换的参数。这种方法在今天用于三维变换中仍 可以借鉴。2 0 世纪8 0 年代中后期到9 0 年代初，人们开始认识到不同模态的图像提供的信 息可以进行处理( 如解剖信息和功能信息) 。这时候图像配准和图像融合也主要集中于二 维刚性变换。2 0 世纪9 0 年代，计算机技术飞速发展，它在图形处理能力上的加强及在性 能上的提高，为进行大数据量的三维图像重建提供了可能。在这期间引入了互信息作为相 似性测度，使得图像配准在三维方向和非刚性图形配准上取得了发展。 在过去的几十年里，随着计算机技术的飞速发展和广泛普及，图像配准处理技术也得 到了快速的提高和广泛的应用。1 9 9 2 年b r o w n 【l 】对当时已有的图像配准技术进行了比较全 面的总结分类。从那时到现在，图像配准技术又有了长足的发展和进步，新的技术和方法 不断出现。根据e i 核心期刊( e n g i i l e e 血gi i l d e xc o m p e n d e x ) 数据库统计，从1 9 9 2 年到2 0 0 7 年1 1 月，图像配准领域发表的论文已有1 2 0 0 0 余篇。 近2 0 年来，针对图像配准方法的研究一直是个国际性的热点问题，已经取得了一些 重要的研究成果，形成了一些成熟的配准方法。但仍然存在许多尚未解决的问题，例如对 配准过程中相似性测度的选择、提高非刚性配准算法的速度等都是一些亟待解决的问题。 1 1 3 互信息与图像配准 如何选择一个合适的相似性测度，使得它可以描述图像几何位置符合的程度并且易于 计算是图像配准中的一个重要研究问题。目前互信息由于其无需预处理以及鲁棒性强等特 第2 页 国防科学技术大学研究生院学位论文 点在图像配准领域中得到了广泛应用。c o l l i 鲷o n 【2 】等和v i o l a 【3 l 等1 9 9 5 年提出了将互信息 用于图像配准中，随后，互信息在遥感和医学等领域得到了广泛应用。 互信息( m u t u a li i 怕m a t i o n ) 来自于信息论，是信息论中的一个基本概念，是两个随 机变量统计相关性的测度。当两幅图像达到最佳配准，它们对应像素的灰度互信息应达到 最大。该测度不需要对不同成像模式下图像灰度间的关系作任何假设，也不需要对图像进 行分割或任何预处理，具有自动化程度高的特点，因此，最近几年将互信息作为图像配准 过程的相似性测度，利用最大互信息法进行图像配准成为了图像处理领域的研究热点【4 1 。 在图像配准中常常需要把来源于不同成像设备的图像进行配准处理，这些不同成像模 式的图像称为多模态图像。当前在遥感、军事、医学、计算机视觉等相关领域上对多模图 像配准技术都有着广泛的需求。例如在遥感图像处理方面，常常需要把微波、红外、雷达 图像、多光谱图像综合分析，有利于对地球资源的分析判断。在医学方面，要获得全面详 细的综合医学图像处理信息，常常需要把c t 、b 超等获得的图像进行综合分析。多模图 像配准在图像配准中是一个非常困难的任务，即便是同样场景下的同一物体，在不同的成 像模式下，其灰度属性也常常存在非常大的差异。采用互信息作为多模图像配准的相似性 测度，可以较好的解决这个问题。因此互信息的计算就成为多模图像配准的一个热点研究 问题，将互信息引入多模图像配准，可以使其在遥感、工业、生物医学、计算机视觉等应 用领域中可能发挥更大的作用【5 】【6 】。 1 1 4 图像配准对并行处理的需求 随着传感器、遥感平台等相关技术的发展，图像信息获取途径越来越多，得到的样式 也是多种多样的，获得的数据量也随之急剧增长【7 1 。图像配准处理面临如此急剧膨胀的海量 数据，运算规模迅速扩大到数干亿乃至数万亿次浮点运算。显然，传统的单处理器串行配准 算法已经无法满足这样的运算需求。具体说来，图像配准并行处理的迫切性主要表现在【8 】： 第一、配准处理的数据量巨大且配准过程操作复杂。 配准处理的数据量巨大。就卫星遥感图像而言，卫星遥感图像的空间分辨率、光谱分 辨率和时间分辨率大大提高，空间分辨率已达到分米级，光谱分辨率已达到纳米级，波段 数已增加到数十个甚至数百个，回归时间缩短到几天甚至几个小时，所得到的图像数据量 巨大，这对图像配准处理的精度与速度提出了更高的要求。随着卫星遥感技术的发展与进 步，遥感图像的分辨率在不断提高，伴随着数据量也越来越大。以目前主流的传感器一 推扫式的扫描仪为例，法国s p o t 卫星的全色 玎w 的地面分辨率为1 0 m ，像幅为 6 0 0 0 6 0 0 0 ，因此单幅图像的数据量约为3 6 m b ；而年美国发射的e a l t h w a t c h 地球观测卫 星上安装的q u i c k b 砷推扫式摄像机的地单幅图像的数据量将达到4 0 0 m b 1 2 g b 。我国目 前发射的“嫦娥一号”绕月卫星上的c c d 立体相机实现了对月球拍摄物的三维立体成像。在 工作时，采集三行c c d 的输出，分别获取前视、正视、后视图像，随后进行处理形成立 体图像，所获得图像的数据量巨大。要对如此庞大的数据量进行处理，是一个严峻的挑战， 目前单机系统的处理能力显然难以满足业务的需求。 第3 页 国防科学技术大学研究生院学位论文 配准过程操作复杂。在配准过程中最优变换参数的计算是一个计算量很大的过程。在 图像配准过程中，最优变换参数的获取必须执行一个优化过程，在一定的搜索空间内，应 用优化算法进行多次迭代计算相似性测度，寻找相似性测度的极值，是一个典型的计算密 集型过程，十分耗时。例如，美国w a y n e 大学神经图像实验室【9 j 的a m e e ne e t e m a d i 应用 a 瓜( 自动图像配准软件包) 【1 0 】配准两幅三维的m ( 核磁共振图像) 和s p e c t ( 单电子 发射计算机断层扫描图像) 图像，需2 0 多分钟；而一些更加复杂的非刚性配准算法在单 机上运行甚至需要花费数小时才能得到配准图像【l 。 因此，图像配准的并行处理成为快速处理和分析图像的高效解决途径，我们必须充分 利用现有的主流并行计算系统，实现图像配准并行处理。 第二、许多应用领域对实时性的要求日益迫切【1 2 1 。军事的目标识别和地形匹配，气象 的天气预报，地质的资源探测和地理导航，医学手术的实时操作等对图像配准速度的要求 十分强烈。 而以采用互信息作为相似性测度的配准过程为例，计算主要集中在每次迭代中求取互 信息的值，算法所需的时间是单次互信息的计算时间乘以迭代次数。非刚性变换模型和互 信息计算的复杂性以及大量的迭代，导致该类方法的计算复杂度更高，性能问题则更为突 出。为了达到实时性要求，有时采用简化变换参数，采用低阶互信息的方法，但由于低阶 互信息仅仅关注灰度的统计特性，忽略了空间信息，往往出现误配准。r u e c k 砸【1 3 j 等提出 了使用高阶互信息，结合邻域中的空间信息，可以降低误配准率，但是计算所花费的时间 也增加了。配准的每次迭代过程中都需要对图像进行插值，非刚性配准由于变形复杂，插 值过程更加复杂，计算时间更长。因此，随着各种新型卫星传感器、新型医学仪器的使用， 实时要处理的数据量迅速膨胀，要达到实时处理大数据量的目的，采用并行处理技术是一 个重要的技术手段。 基于上述背景，本文以基于互信息的图像配准算法为核心，针对其处理过程中的各项 关键技术展开了研究和探讨。面向主流的 m 仍结构的并行分布式计算系统，研究基于互 信息的并行配准算法。一 1 2 相关工作 本文重点研究了图像配准的相似性测度、互信息这种相似性测度的计算方法、基于互 信息的图像配准并行算法。因此本课题涉及到了图像配准领域的相关背景、概念，以及图 像处理的并行性和并行模式几部分相关内容，本节将对这些内容进行概述。 1 2 1 图像配准串行算法 对图像配准方法进行分类是非常困难的。一种配准技术常常是几种方法的综合运用， 很难确切地把它们明确划归那一类。根据不同标准，会得到不同的分类结果。按照相似性 测度可以分为基于相关系数、差方和、互信息等方法。按图像变换模型可以分为刚性和非 刚性配准；按照映射函数类型可以分为仿射、透视等：按照数据维度可以分为2 维和3 维； 第4 页 国防科学技术大学研究生院学位论文 按照特征空间可以分为基于特征、基于灰度的方法；按照应用领域可以分为遥感图像配准、 医学图像配准等；按照成像方式可以分为同模态图像配准和多模态图像配准；按照变换域 可以分为空间域配准方法和频域配准方法等。 在配准中相似性测度和变换模型的选择是最重要的两个方面，因此本小节将从这两个 方面对配准串行方法进行概括和分类，对具体的配准方法指出其主要贡献和合理的使用范 围，对我们以后将要研究的配准并行算法进行指导。 1 2 1 1 相似性测度 相似性测度有相关系数、差方和、互信息等。在图像配准初期采用的方法主要是相关 系数和差方和的方法。相关系数的方法通过计算图像内窗口间相关函数的极大值实现 【1 4 】【”】。如果要求达到子像素的精度，需要对互相关矩阵进行插值。相关系数配准方法可以 非常精确的对齐平移变化，对于带有小角度的旋转和小尺度缩放的图像，配准也很成功。 有些研究者提出来的改进的相关系数方法可以处理具有较大几何形变的图像，通过计算图 像间每一个预先假定的几何变换【1 6 】【l 刀，可以处理比平移更复杂的几何形变相似变换。 k 锄e k o 等【l8 】提出来选择性相关系数方法，对存在掩蔽、照度病态变化等情况下的图像配准 具有较强的鲁棒性。相关系数的方法只能处理特定的问题，通用性不强。 差方和的方法在应用中对两幅图像的像素点的差方累加。差方和达到最小时，认为两 幅图像达到配准，显然这种方法计算简单、速度快，但是精确度不高。w o l b e r g 和z 0 k a i l l 9 】 在分块图像配准中采用差方和的方法。k y b i c 【6 8 】等人采用差方和的平方来取代互信息作为 相似性度量，这样可以计算出梯度的解析表达式，但限制了算法只能应用于同模态图像配 准问题。 c o l l i g n o n 【2 】等和v i o l a 【3 1 等1 9 9 5 年提出了将互信息用于图像配准中。s t u d l l o l m e 【2 0 】等 比较了互信息和标准化互信息，认为归一化互信息的配准精度较高。r u e c k e r t 【2 l j 等通过将 仿射变换与基于样条的自由体变形相结合，采用互信息作为相似性测度，建立了图像间的 全局形变模型。p l u i m 瞄】等对基本的互信息配准方法和由粗到精的快速互信息方法作了比 较。上述的互信息方法是直接对整幅图像的灰度作处理。这些方法都是为了进一步提高配 准的精度，也取得了非常好的效果，但是在处理的过程中增大了计算量。 1 2 1 2 变换模型 在刚性配准算法的研究方面，g o s h t a s b ) r 【2 3 】提出了一种优化分割处理方法以便提高配准 的精度，图像的分割和配准通过交替迭代的运算过程来同时完成。p e l i z z a r i 【2 4 j 设计的“头和 帽”( ”h e a d - h a t ”) 算法，提取表面特征用来配准3 d 刚性医学图像。该方法最初用于头部的p e t 和c t ( 或m ) 配准，参考特征是头部的皮肤表面，然后用于头部的s p e c t 图像之间的配 准，参考特征变成头颅骨表面和大脑表面，算法的关键是头部的c t ，m r j 和p e t 图象中 皮肤表面的分割，因为这种分割比较容易实现，计算复杂性相对比较低，所以它的应用十 分流行。s t o c k m a l l 【2 5 】等提出来用聚类技术去匹配抽象边缘和分割线，假定的几何变换模 型是相似刚性变换。对每一对控制点都计算变换映射参数，并且把计算出来的参数作为变 换参数空间内的一点。b 撇w 【2 6 】等提出了斜切匹配的图像配准方法，通过最小化特征间 第5 页 国防科学技术大学研究生院学位论文 距离的方法实现图像i 。i l j 线条特征的匹配。如c a l l i l y 【2 7 】算子或者l 印l a c i a l l og a u s s i a n 【2 8 j 算子， 都可以用来检测线性特征，对刚性变换进行匹配。“掣2 9 】提出使用模板图像( 光学图像) 中已检测出来的线特征来检测待配准图像的线特征( 待配准图像是带有斑点噪声的s a r 图 像) 。m a i n t z 【3 0 3 l 】等对多模态医学图像中边缘检测算子和脊线检测算子作了比较。 在非刚性配准算法的研究方面，非刚性变换算法有采用物理模型拟合和采用空间变换 的方法。在采用物理模型的配准方法中，构造能够拟合这种变形的物理模型，有弹性模型、 粘流体模型、光流模型等。弹性模型在配准中的应用由b 4 j c s y 【3 2 】等基于弹性原理的n a v i e r 等式首次提出的，i b “3 3 j 对弹性模型在非刚性配准中的应用进行了详细的总结。 c l l r i s t e n s e n l 3 4 j 等提出了粘性流体模型。这种模型可以处理大规模局部化的变形，n i e l s 【”j 等提出了一种改进算法提高计算速度。光流的概念首先是在计算机视觉中提出的，为了补 偿时序图像的两幅连续帧之间物体和视点的相对运动。在采用空间变换的方法中，采用样 条变换的方法是一种经常用到的方法。尽管样条变换的方法己经在机械和工程上应用几十 年【3 6 1 ，但直到c 埘m s o n 【3 7 1 和b 0 0 k s t e i f l 【3 8 】之后，才引入到图像分析领域。最常使用的样条函 数是薄板样条函数( t p s ：1 n b l i l l p l a ：t es p l i n e s ) ，t p s 可以看作是一个非常薄的板，根据待配 准图像上控制点的x 和y 坐标，得出一个高度，在这个高度上待配准图像与模板图像对应 控制点之间的位置决定薄板的位置唧。t p s 最小化一个二次变化势能函数，这个函数反映 了函数的变化量，对于合适的映射函数这个量是很小的。m e y c r 的方法使用插值薄板样条， 根据特征点的位置对整幅图像用薄板样条插值函数计算非刚性变换，i h l e c k 瞰【2 l j 等人的方 法不依赖于薄板样条函数，而用建立在规则栅格上的b 样条函数来模拟形变场。冯林删 等提出了一种采用基于薄板样条的多次分层的变换方法。 从前人研究的串行算法中可以看出，图像配准的具体实现方法是多种多样的，但其主 要关注点是配准精度方面。而近年来随着图像配准应用范围的扩大，待配准数据量大和强 实时性这两个问题在速度方面的要求变的越来越突出，并行计算是当前解决这两个问题的 有效手段。 1 2 2 图像配准并行算法 1 2 1 节提到的配准方法都是串行算法，虽然精确度不断提高，但是计算量也是越来越 大。为了提高运算速度，人们提出了并行计算解决的方法。o z k 觚【4 l j 提出了一种基于遗传 算法的细粒度并行图像配准算法，平台是5 个处理器的仃锄s p u t e r 计算机，该算法采用全 局的遗传模型来实现并行图像配准，算法的可扩展性十分有限。基于多分辨率小波技术， l e m o i 弘e 1 4 2 j 提出了一种细粒度的并行算法，这种算法适合于s i m d 结构的并行系统，如 m p 2 ，但并不适用于当前主流的m n 仍结构的系统。t u n o n 【4 3 】提出了一种基于硬件的并行 图像配准算法，它借鉴了利用遗传算法进行配准的思想，该算法也是开发了细粒度的并行 性，并直接用硬件实现，但性价比和灵活性较差。e 1 g l 擒盟、) l ，i 】和c h a l e m w a t l 4 5 】先后提出 了一种粗粒度和细粒度相结合的方法，并在b e o m l f 和cr a ：y t 3 e 上实现，二者的区别是选 取的特征空间和搜索策略不同，但都没有进行通信优化和复杂度分析。z h o u 【4 6 】总结了基 第6 页 国防科学技术大学研究生院学位论文 于小波的刚性图像配准并行算法，并提出了一种新的并行策略。c m s t e n s e n 【4 7 】分别在m l m d ( s g ic h a l l e n g e ) 和s i m d ( m a r s p a r ) 机器上实现了3 d 图像非刚性配准的并行算法，采 用距离测度作为相似性测度，并证明了m i m d 上的算法比s m d 的算法性能最少快四倍。 w a r f i e l d 郴】研究了脑部变形图像的非刚性配准算法的并行算法，但是算法的负载均衡性还 有待