（生物医学工程专业论文）基于元胞自动机的图像拼接.pdf

上海大学硕士学位论文 a b s t r a c t i m a g em o s a i c i n gi sak i n do ft e c h n o l o g yt h a ts t i t c h e sp a r t i a l l yo v e r l a p p e d i m a g e si n t oo n es e a m l e s si m a g ew i t l lw i d e rv i s u a lf i e l da n dh i g h e rr e s o l u t i o n f e a t u r e b a s e di m a g em o s a i c i n gm e t h o dc a ns t i t c hi m a g e sw i t hh i g hp r e c i s i o na n dh i g hs p e e d ， s oi th a sg o ta ne x t e n s i v ec o n c e r n t h i sp a p e rd e s c r i b e sac e l l u l a ra u t o m a t ab a s e d i m a g em o s a i c i n gm e t h o d ，w h i c hi sb a s e do nt h ef e a t u r eb a s e di m a g em o s a i c i n g m e t h o d t h em e t h o dd e v e l o p e de n h a n c e st h eq u a l i t yo fi m a g es t i t c h e da n dt h e r e q u i r e dd e g r e eo f p i c t u r eo v e r l a pi sd e c r e a s e df r o m5 5 b e f o r et o3 3 n o w t h ep a p e ri n c l u d e sm a i n l yt h e f o l l o w i n ga s p e c t s ： 1 t h i sp a p e rd e v e l o p e da ne d g ed e t e c t i o nm e t h o db a s e do nc e l l u l a ra u t o m a t a t h i sm e t h o dc a nb ei m p l e m e n t e de a s i l ya n di th a st h ea c c u r a t ed e t e c t i o n r e s u l te f f e c t i v e l y 2 a ni m a g em o s a i c i n gm e t h o db a s e do nc e l l u l a ra u t o m a t ai s p r o p o s e d t h r o u g ht h et h o r o u g ha n a l y s i st ot h ee a c hm o d u l eo fo r i g i n a lm e t h o d ，w e f o u n dt h a tt h ee d g ed e t e c t i o nr e s u l t sg o tb yt h ee d g ec o r r e l a t i o nw i l lh a v et h e w r o n gf e a t u r ep o i n t s ，w h i c hi st h em a i nr e a s o nf o rt h ef a l s es t i t c hr e s u l t t h i sp a p e rd e s c r i b e sam e t h o dw h i c hd i s p l a c e dt h ec a - b a s e de d g ed e t e c t i o n m o d u l et ot h eo r i g i n a lo n e ，a n dt h er e m a i n i n gc o r r e s p o n dm o d u l e sw e r ea l s o m o d i f i e d t h em e t h o dp r o p o s e dc a ns u c c e s s f u l l ys t i t c ht h ei m a g e st h eo r i g i n a lm e t h o dc a n n o t s t i t c ha n di tn e e d sl e s si m a g eo v e r l a pd e g r e e c o m p a r e dw i t ht h eo t h e rs t i t c h i n g s o f t w a r e ，t h em e t h o dg i v e nh e r eh a st h ea d v a n t a g eo f s p e e d k e y w o r d s ：i m a g em o s a i c i n g , e d g ed e t e c t i o n ，c e l l u l a ra u t o m a t a i i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名：盘查! 垒日期：竺1 5 ：i ! 1 2 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：堑董t 垦导师签名： 上海人学硕士学位论文 1 1 引言 第一章绪论 在实际的科研和工程中，经常会用到超过人眼视角的高分辨率图像，而普通 相机的视角往往不能满足需要。由于距离的限制，某些超大尺寸的物体无法用一 张照片拍摄下来，这在航空航天照片的拍摄中显得尤为突出【1 】。利用广角镜头和 扫描式相机( p u s h - b r o o mc a m e r a ) 可部分解决视角不足这一问题 2 1 ，但这些设备都 有价格昂贵和使用复杂等缺点。另外，在一幅低分辨率的图像中得到超宽视角会 损失景物中物体的分辨率，而且，广角镜头的图像边缘会难以避免地产生扭曲变 形。图1 1 、图1 2 分别是采用广角镜头和扫描式相机而得到的图像。另一种方 法是使用目前的许多图像处理工具如p h o t o s h o p 等，但这种手动拼接方法不仅拼 接效果不够理想，如无法消除序列间光照差异以及图像间拼缝，而且对于多幅图 像的拼接，工作量大且重复运作繁琐。 图像拼接( i m a g em o s a i c ) 技术是指将两幅或两幅以上具有部分景物重合的相 邻图像进行无缝拼合，生成一幅具有较宽视角的高分辨率图像的技术。它最早来 源于人类的摄影知识，当相机的视野小于人类的视野时，人们自然考虑到将多个 照片拼接成一幅大的照片以增强相机的视野。随着计算机技术的进步而发展起来 的数字图像处理技术使得图像拼接技术的成功实现成为可能。这一类技术的出现 使采集图像的设备更普通化，利用普通的摄像机和数码照相机即可得到满足要求 的图像。 建立大型、高分辨率的自动图像拼接技术一直是摄影测量学、计算机视觉、 图像处理和计算机图形学的活跃研究领域。图像拼接有很多应用，它包括传统的 由图像集合建立大型航空和卫星照片，近来的应用如视频检索、图像的稳定性、 变化检测、视频压缩、增大相机的视野和分辨率，甚至能做简单的照片编辑。目 前流行的应用是数字全景图像，它可以应用于建立虚拟现实环境。 上海大学硕士学位论文 图1 1 采用广角镜头的图像。图像边缘带有桶状畸变。 图1 2 采用扫描式相机的图像。超过1 8 0 。的景象被压缩在一幅画面中，图像有所扭曲。 1 2 当前研究概况 图像拼接技术的核心技术是图像配准技术，早在1 9 9 2 年，剑桥大学的l i s a g o t t e s f e l db r o w n 就已经总结了各领域图像配准技术的基本理论以及它们的主要 方法【3 1 。这些领域包括有医学图像分析，遥感数据处理以及计算机视觉，模式识 别等。1 9 9 6 年，r i c h a r ds z d i s k i ( m i c r o s o f tc o r p o r a t i o n ) 提出了基于运动的全景图 像拼接模型，采用l e v e n b e r g - m a r q u a r d t 迭代非线性最小化方法( 简称l m 算法) ， 通过求出图像间的几何变换关系来进行图像配准 4 1 。由于此方法效果较好，收敛 速度快，且可处理具有平移，旋转，仿射等多种变换的待拼接图像，因此也成为 图像拼接领域的经典算法，而r i c h a r ds z d i s k i 也从此成为图像拼接领域的奠基 人，他所提出的理论己经成为一种经典理论体系，直到今天仍然有很多人在研究 他的拼接理论。 除了上述的经典算法之外，还有两种主要方法。一种是相位相关度法，另一 种是基于几何特征的图像配准方法。相位相关度法最早在1 9 7 5 年由k u g l i n 和 h i n e s 提出，具有场景无关性，能够将纯粹二维平移的图像精确地对齐。应用傅 上海大学硕士学位论文 立叶变换进行图像配准是图像拼接领域的另一研究成果，而且随着快速傅立叶变 换算法的提出以及信号处理领域对傅立叶变换的成熟应用，图像拼接技术也得到 了相应的发展。 基于几何特征的图像配准方法是图像拼接技术的另一研究热点【5 1 。2 0 0 0 年 h s u 和b e u k e r 提出了基于特征的多分辨率图像配准方法嘲。此方法利用小波变换 提取图像边缘，通过图像间边缘特征的匹配进行图像配准。2 0 0 3 年n r w a n i g a s e k a r a 将其成功应用于多组视频流的实时图像拼接1 9 。2 0 0 5 年张旭锋将此 拼接技术进行了进一步改进，将其成功应用于生物医学图像的拼接【1 0 】。上述研究 成果是本文工作的研究基础。 1 3 工作概要及创新 本论文是对静止拍摄的图像序列进行图像拼接的研究。针对多分辨率小波分 解进行图像拼接方法的缺点，本文提出一种基于c a 的图像拼接方法。该方法建 立c a 图像处理模型，并以之进行了图像特征提取，克服了原方法特征提取的缺 陷，提高了拼接准确度，同时减少了对图像重叠度的要求。 本论文的主要工作内容： 1 提出一种采用c a 模型进行图像边缘检测的方法。该方法实现简单，检 测结果准确有效。 2 提出一种基于c a 的图像拼接方法。经过对原方法各个模块的深入分析， 发现特征提取模块中采用的边缘相关法进行边缘检测进而提取图像特征 点时可能发生的错误，是造成错误拼接的主要原因。本文的方法用基于 c a 的图像边缘检测模块替代了原来的特征提取模块，并对其余模块进 行了相应的改变。使用本文方法，成功拼接了原来拼接失败的图像，同 时需要较少的图像重叠度。而且相比于其他的拼接软件，本文提出的方 法还有速度上的优势。 上海人学硕士学位论文 1 4 论文章节安排 本论文是以作者攻读硕士学位期间承担课题的工作为基础。本文的章节安排 如下：第一章介绍了图像拼接的意义、研究概况以及本文所作的工作与创新之处。 第二章介绍了图像拼接的一般方法与关键技术，以及相关背景知识。第三章介绍 了c a 的基本概念以及使用c a 模型进行图像边缘检测的方法。第四章具体阐述 了基于c a 的图像拼接方法。第五章给出了本文方法的实验结果与分析讨论。第 六章是对本论文工作的总结和对图像拼接算法的展望。 4 上海= 学硕士学位论文 2 1 引言 第二章图像拼接技术简介 图像拼接技术是一个跨学科的领域，它涉及到了计算机视觉、计算机图形学 和图像处理等多个领域的知识，同时，多种数学工具也被引入到这一项技术当中， 取得了很好的效果。因此，它是上述各个学科知识的综合运用1 2 】。本章将概要介 绍图像拼接技术所涉及的主要方面。 2 2 图像拼接的一般描述 图像拼接一般是一个多步骤的过程。总的来说，大概可分为有用信息提取、 信息匹配、效果评估、图像融合和生成目标图像等步骤。由于采用的方法各异， 不同的算法之间步骤也会有很大不同，但它们的大致过程是相同的1 4 】。下面用一 张图来说明图像拼接的大体过程，图2 1 是图像拼接的一般流程图。 输入图像 有用信息提取 | 一一一一 信息匹配 j 效果评估 l - - - - 图像融合 生成目标图像 图2 1 图像拼接流程图 上海大学硕士学位论文 对于某些算法，它们用到了迭代或循环的方法，对得到的结果进行多次评估， 在达不到满意的效果时，就重新进行信息的匹配，如图2 1 中的虚线所示。 2 3 图像的获取 图像获取方法的不同导致取得输入图像的不同，最终拼接结果也不同。图像 获取由照相机拍摄时的运动状态决定，一般有三种情况：( 1 ) 照相机固定在三角 架上，旋转照相机拍摄；( 2 ) 照相机放置于一个滑轨上，平行移动照相机进行拍 摄；( 3 ) 是一种普通的情况，人手持照相机，站在原地拍摄四周，或者沿着照相 机的光轴垂直方向走动拍摄。 ( 1 ) 旋转照相机拍摄 在这种情况下放置照相机的三脚架在拍摄过程中一直在同一位置。拍摄时， 照相机绕垂直轴旋转，每旋转一定的角度，拍摄一张照片，理想的情况下，照相 机不绕其光轴旋转。拍摄得到一系列照片中相邻两张必须有部分重叠，重叠区域 大小是图像拼接最重要的影响因素。重叠比例越大，拼接就越容易，但是需要的 照片越多。旋转照相机拍摄由于照相机固定，不需要恢复过多参数，较容易实现。 但是，拍摄图像不在一个平面上，需要投影到同一个平面上，这将会导致图像质 量下降。 ( 2 ) 平移照相机拍摄 平移照相机指的是照相机在一个平行于成像平面的方向上平移。在固定焦距 的情况下，照相机放置在一个滑轨上移动拍摄。物体和照相机的距离远近，或者 拍摄物体的大小的变化都会影响到最后的拼接结果。 ( 3 ) 手持照相机拍摄 这种方法比较容易做到，手持照相机原地旋转拍摄，或按一定的路线平行于 对象拍摄。但是，拼接手持照相机拍摄的照片是很困难的，因为在拍摄过程中， 照相机的运动非常复杂。原地旋转拍摄类似于固定照相机旋转拍摄，但是角度控 制、旋转控制都很差。沿一定路线移动时，类似于平移拍摄，控制距离和保持相 同的成像平面很困难。为了减少这些影响，可以增加重叠比例，使照相机旋转角 度、平移减小，因而减小相邻图像之间的不连续程度。 6 上海大学硕士学位论文 图像获取过程中最常见的问题就是相邻图像之间光强的变化较大。理想情况 下，相同的区域应该有相同的光强，但是因为光源变化或者照相机运动和光源平 角的变化，导致光强的差异。另外一个和光条件相关的问题是反光区域，例如镜 子和闪亮金属，高亮光将会降低相应区域的对比度。场景中物体移动和拍摄时透 镜引起的图像变形也将给配准拼接带来困难。现有的方法一般限制了照相机的运 动，但是实际中拍摄的图像存在小视差，不同比例的缩放和大角度旋转，这些都 增加了配准拼接的难度，因此很多文献( 如文献【4 ) 要求照相机以最小运动视 差旋转拍摄。 2 4 坐标系统 在图像拼接过程中，经常要将某幅图像变换到参考图像的坐标系下，这就需 要在不同的坐标系中考虑问趔2 0 1 ，本节将介绍各种坐标系统的相互关系，作为讨 论图像变换的基础。 在图像采集中需要将客观世界的三维场景投影到摄像机的二维像平面上，这 个投影可用成像变换描述。最常用的成像变换是几何透视变换，其特点是随着三 维场景与摄像机之间的距离变化，像平面上的投影也发生变化。在有些场合f 如 景物平面与相机距离很大时) 也有用正交投影变换近似透视变换的，此时景物在 像平面上的投影并不随三维场景与摄像机之间的距离变化而变化。 成像变换涉及到不同坐标系统之间的变换。考虑到图像采集最终结果是要得 到计算机里的数字图像，在对三维空间景物成像时涉及到的坐标系统主要有以下 几种： ( 1 ) 世界坐标系，也称真实或现实世界坐标系统x y z ，它是客观世界的绝对 坐标。一般的三维场景都是用这个坐标系来表示的。 ( 2 ) 摄像机坐标系统，以摄像机中心制定的坐标系统x y z ，一般常取摄像机 的光学轴为z 轴。 ( 3 ) 像平面坐标系统，在摄像机内所形成的像平面坐标系统x y 。一般常取 像平面与摄像机坐标系统的叫平面平行，wx 轴与x 轴，y 轴与y 轴分别重合， 上海大学硕士学位论文 未 = 蒌荔葶 羽或x ：尬 。， ：瞄- 嘲s i n 口o m 2 m s i nm 亿：， = l 护c o s 口 ，、 上海大学硕士学位论文 m ：f ，篡乏篡1q 10 0 1 m = 篡主辜 。“， 图2 _ 2 表示了各种变换的效果。 厂 1 _ j 原始图像刚性变换仿射变换投影变换 图2 2 图像的几何变换示意图 2 6 图像拼接的关键技术 图像配准是图像拼接的关键技术【1 6 】，在实时应用场合不仅要求配准精确而且 必须足够快。配准技术在图像处理领域的应用是非常广泛的。在图像配准和拼接 中，配准的依据是图像之间的相似性，根据相似性判断标准的不同，图像配准方 法大致可以分为三类：基于轮廓特征【”1 、基于模板匹配的穷尽搜索和基于频域变 换r 相位相关) 。 下面对这三种方法作一简单的介绍： ( 1 ) 基于轮廓特征的方法要求待配准的图像中可以提取出明显的轮廓特征， 但是并不要求待配准的图像来自于同样的图像源，所以轮廓匹配的方法多数被用 上海大学硕上学位论文 于纯配准应用中。近来国内也有人将同样的思想用于c t 图像的配准方面。然而 基于轮廓特征的方法同样也存在易受噪声干扰影响的缺点，其计算量随着图像中 包含轮廓数量的增多而快速增长。在物探地形图片或医学显微图像的拼接领域， 基于轮廓特征的方法是最可取的方法。同时，通过对轮廓匹配方法的各个环节进 行改进，使之更快速，形成一个完整的基于轮廓特征的图像拼接算法，完全可必 满足图像拼接应用的需要。 ( 2 ) 相位相关法最早是由k u g l i n 和h i n e s 在1 9 7 5 年提出的，并且证明在纯 二维平移的情形下，拼接精度可以达到1 个像素，多用于航空照片和卫星遥感图 像的配准等领域。该方法对拼接的图像进行快速傅立叶变换，利用频域中的相位 信息来实现图像拼接，计算量只与图像尺寸的大小有关，而与图像之间的平移量 的大小无关，且能有效地克服光照的变化和镜头产生的几何畸变所带来的影响。 基于频域变换的方法有准确率高和自动化程度高等优点，但是也有计算量大和受 噪声干扰影响大的缺点，而且不能处理旋转情况。 ( 3 ) 模版匹配拼接通常采用的方法是基于两幅图像重叠部分所对应r g b 或 c m y 颜色系统中灰度级的相似性，自动寻找图像的匹配位置。实际上可以归结 为如下的模式识别问题：设相邻两幅重叠图像中前一幅图像为矩形区域a ，后一 幅图像为矩形区域b ，己知a 中包含一个区域a 1 ，b 中包含一个区域b 1 ，a 1 与b 1 是相同的模块，求b 中b 1 相对于a 中a 1 的位置。常用的算法有以下几 种： 基于块的匹配。取第一幅图像处于重叠部分的一块作为模板，在第二幅 图像中搜索具有相同( 或最相似) 值的块，从而确定重叠范围。只要块取 得足够大，这种算法的精度就较高，但计算量过大。 比值匹配。在第一幅图像的重叠区域中，部分相邻的2 列上取出部分像 素，用它们的比值作为模板，在另一幅图像中搜索最佳匹配。该算法计 算量较前一种算法有所减少，但仍较大，并且在计算比值时需大量的除 法，精度也有所降低。 基于网格的快速匹配。在基于块的匹配基础上，为了减小运算量，在搜 索过程中，首先进行粗略匹配，每次水平或垂直移动一个步长，计算对 上海大学硕士学位论文 应像素点r g b 值( 或狄度值) 的差的平方和，记录最小值的网格位置。其 次，以此位置为中心进行精确匹配。每次步长减半，搜索当前最小值， 循环这个过程，直到步长为0 ，最后确定出最佳匹配位置。该算法虽然 在运算速度上较前2 种方法有所改善，但是在粗略匹配过程中，移动的 步长较大，很有可能将第一幅图像上所取的网格划分开，这样将造成匹 配中无法取出与第一幅图像网格完全匹配的最佳网格，很难达到精确匹 配。 2 7 小结 本章对图像拼接的流程以及其中的关键技术做了简要介绍。同时因为图像拼 接是一个跨学科的领域，我们也介绍了包括图像的获取、图像的几何变换以及坐 标系统等相关的背景知识。 上海大学硕士学位论文 3 1 引言 第三章基于c a 的边缘检测 c a 是空间和时间都离散，物理参量只取有限数值集的理想物理系绀“】。它 是一个数学、物理学、计算机科学、生物学和系统科学多学科的交叉和边缘领域， 是复杂系统的重要研究方法之一。c a 产生于2 0 世纪4 0 年代，由v o nn e u m a n n 首先提出。随着人工生命等复杂性科学的发展，8 0 年代以来，c a 日益受到国际 学术界的广泛重视，应用领域又扩及物理学、化学、计算机、生物学、军事学、 社会学、医学、地理学等各个领域，是当前复杂性研究中一个相当活跃的前沿领 域。 讨论二维c a 的论文很多，然而基于此模型作图像处理的不多23 1 ，c a 应用 于图像处理开始于2 0 世纪5 0 年代。作为一种并行处理的模型，c a 在图像处理 领域有着广阔的应用前景。 作为特征提取的前续工作，图像的边缘检测在本文论述的图像拼接方法中占 有十分重要的地位。因此使用c a 实现边缘检测是本文的工作重点之一。 3 2c a 的相关定义 3 2 1c a 的定义 在这一节里，我们引入c a 的严格定义。一般地，c a 要求： ( 1 ) 规整的元胞网格覆盖d 维空间的一部分； ( 2 ) 归属于网格格位，的布尔变量m ( ，f ) = 巾，( ，f ) ，中：( r ，) ，m 。( r ，f ) ) 给出 每个元胞在时间t = o ，l 2 一的局部状态； ( 3 ) 演化规则r = 隅，r ，咒 按下式决定状态巾( r ，) 的时间演化过程： m ，( ，+ 1 ) = r j 【m ( r ，f ) ，( r + 4 ，f ) ，中驴+ 8 2 ，r ) ，中p + 瓯，r ) 】 ( 3 1 ) 上海大学硕上学位论文 式中r + 皖指定从属于元胞r 的给定邻居元胞。 按上述定义，演化规则r 对所有格位都是同一的，且同时应用于它们中的每 个元胞，由此得到同步动力学。按定义时间t + l 的状态只随时间t 的状态而变化。 有时必须进行长期记忆，并引入对时间卜1 , t 一2 ，r k 等的状态的相依性。如果 要在当前状态保留以前状态的副本，则该定义中已经包含这种情况。 3 2 2 邻居 按定义，c a 演化规则是局部的，对指定元胞的状态进行更新只需要知道邻 近元胞的状态。某元胞需在其内搜索的空间域称为邻居。原则上，对邻居的大小 没有限制，只是所有元胞的邻居大小都相同。而实际上往往只由邻接的元胞构成 邻居，如果邻居太大，则演化规则的复杂性可能是不可接受的。 通常，二维c a 考虑两种邻居：一是v o nn e u m a n n 邻居，有一个中心元胞f 要 演化的元胞) 和4 个位于其邻近东西南北方位的元胞组成；另一是m o o r e 邻居， 它另包括次邻近的位于东北、西北、东南和西南方位的4 个元胞，共9 个元胞。 如图3 1 所示说明这两种标准邻居。 ( a ) v o nn e u m a n n 邻居( b ) m o o r e 邻居 图3 1 两种标准邻居 黑色单元是中心元胞由灰色区域内各元胞状态决定其更新状态。 3 2 3 边界条件 实际上，在模拟指定的元胞自动机演化规则时，不可能处理无限的网格，系 统必须是有限的、有边界的。显然，属于网格边界的格位不具有与其他内部格位 一样的邻居。为了确定这些边界格位的行为，可以制定不同的演化规则，以考虑 上海大学硕士学位论文 适当的邻居。即对边界格位上的信息进行编码，并根据这些信息来选择不同的演 化规则。按照这种方法，还可以定义几种具有完全不同行为的边界。 另一种方法，不是在系统边界上用不同的规则，而是在边界处扩展格位邻居。 例如，一种通用的解决办法是假设周期( 或循环的) 边界条件，就是假想网格嵌入 像环面一样的拓扑结构中。在二维网格情况下，指左右连接和上下连接。 图3 - 2 示出一维网格中几种可能的边界条件。假定用边界外的一组虚元胞扩 大网格。固定边界是用预先赋值的元胞使邻居完整。通过对虚元胞赋予格位值， 获得绝热的边界条件。映射边界相当于在虚元胞中复制其他邻居的值。 ( a ) 周期边缘 ( b ) 固定边缘 ( c ) 绝热边缘( d ) 映射边缘 图3 2 通过扩展邻居获得的各种边界条件 阴影单元代表虚元胞，它们为使邻居得以完整附加在网格末端( 这里为左侧) 3 3 基于c a 的边缘检测 随着实时图像处理高速要求的不断提出，并行算法取代串行算法的需要显得 越来越重要。作为一种内在的并行计算模型，c a 能够满足这一需求。 k a g a w a 使用人工生命的方法提出一种基于a u t o n o m o u sa g e n t s 的图像分割方 法 2 ”，其方法非常类似于传统图像处理中的区域分割。s a h a t a 使用受遗传控制的 自动机模型进行普遍意义上的图像处理问题【2 6 1 ，包括使用遗传算法进行边缘检 测，此方法能在理论上找到精确的c a 演化规则来解决给出的问题。但是这种方 法的问题是需要的计算量是巨大的。同时无法证明对于一个图像处理任务，是存 在一个规则还是存在多个规则。另一方面，v i s h e r 为解决女性卵巢超声图像中卵 泡的是识别问题，提出了一种具有特定转换规则的c a 拥，这种方法需要很强的 先验知识，因而不具有普遍性。 1 4 上海大学硕士学位论文 3 3 1 图像边缘的定义 图像的大部分主要信息都存在于图像的边缘中，主要表现为图像局部特征的 不连续性，是图像中灰度变化比较剧烈的地方，也即我们通常所说的信号发生奇 异变化的地方。奇异信号沿边缘走向的灰度变化剧烈，通常我们将边缘划分为阶 跃状边缘和屋顶状边缘两种类型。阶跃边缘中边缘两边的灰度值有明显的变化； 而屋顶状边缘中边缘位于灰度增加与减少的交界处。在数学上可利用灰度的导数 来刻画边缘点的变化，对阶跃边缘、屋顶状边缘分别求其一阶、二阶导数。如图 3 3 ，对于阶跃边缘点a ，其灰度变化曲线的一阶导数在a 点达到极大值；二阶 导数在a 点与零交叉。对屋顶状边缘点b ，其扶度变化曲线的一阶导数在b 点 与零交叉，二阶导数在b 点达到极值。 a ( a ) 阶跃型边缘 y ，“( x ，y ) n v 7 a y f ”( x ，y ) 八 八 f 。 b b ( b ) 屋顶状边缘 3 3 两种边缘类型及其导数 边缘检测的实质是采用某种算法来提取出图像中对象与背景间的交界线。我 们将边缘定义为图像中灰度发生急剧变化的区域边界。图像灰度的变化情况可以 上海大学硕士学位论文 用图像灰度分布的梯度来反映，因此我们可以用局部图像微分技术来获得边缘检 测算子。经典的边缘检测方法，是对原始图像中像素的某小邻域来构造边缘检测 算子。 记v f ( x , y ) = 罢f + 要，为图像的梯度，v f ( x , y ) 中包含局部灰度的变化信息。 珊却 记e ( 五y ) = 露( lj ，) + 形( x ，y ) y 撇v f ( x ，力的幅度，e ( x ，y ) 可以用作边缘 检测算子。为了简化计算，也可以将p ( x ，y ) 定义为偏导数正、工的绝对值之和： e ( x ，y ) = k ( 算，y ) i + 阮( x ，y ) j 以这些理论为依据，提出了许多算法，常用的边缘检测方法有：差分边缘检 测、r o b e r t s 边缘检测算子、s o b e l 边缘检测算子、p r e w i t t 边缘检测算子、r o b i n s o n 边缘检测算子、l a p l a c e 边缘检测算子等等。 3 3 3 基于邻域像素灰度之差的c a 边缘检测 基于梯度计算的方法通常需要很大的计算量，这就限制了这类方法的应用范 围。而其他不通过梯度计算的方法需要预先知道图像的先验知识，因而不具有普 遍性。基于上述原因本节提出一种基于c a 模型的边缘检测算法，其特点是：算 法简单，有效：算法的内在并行性，可用并行机实现。 如果将图像边缘看作是图像灰度发生剧烈变化的区域，那么比较容易设计出 一个函数来量化某一像素与其周围像素之间的灰度差。我们的目标是定义这样的 一个函数，它在图像灰度变化平缓的区域取较小的值，在图像灰度变化强烈的区 域取较大的值。 这个函数的一种简单的表达式是： f ( i ，j ) = 1 4 1 , ，一( 。，+ 扎，+ ，一。+ ，p ) i ( 3 2 ) 这里，表示图像中位于( f ，j ) 的像素灰度值。 1 6 上海大学硕士学位论文 由( 3 2 ) 式可知，在像素灰度比较相似的区域，f ( i ，) 为接近于0 的较小值， 而在边缘存在的区域( 像素变化相对较大) ，f ( i ，) 为较大的值。 在采用c a 模型进行图像处理时，为了使c a 的演化能够达到一个稳定的状 态。我们需要设定规则，使得元胞状态能够进入一个静止状态。我们将表达式 f ( i ，) 的值与预先取定的阂值相比较，若f ( i ，j ) a ，则中心元胞状态保持不 变，否则，中心元胞状态取0 值。 由此，我们得到c a 的规则如下： f + l ：j 一，f 4 ，一( - l ，+ 扎，+ ，一- + ，- “) i ( 3 3 ) 。 0 ， o t h e r w i s e 这里我们取半径为1 的v o nn e u m a n n 邻居。 图3 4 是采用本方法取不同阈值的边缘检测结果，表3 1 是与各阈值对 应的达到稳定状态所需的演化次数。 l e n a 原图 a = 1 5a = 2 5 = 3 0 a = 4 5a = 6 0 图3 4 取不同阚值的边缘检测结果 上海大学硕士学位论文 表3 1 阈值与达到稳定状态所需的演化次数 阈值a 1 52 53 04 56 0 l 演化次数n 1 02 22 43 0 1 1 由实验结果可见，本方法中闽值的选择影响了最终的边缘检测结果。过小 的值使得多余的边缘出现，过大的值使得边缘有丢失的趋势。因此，如何确 定准确的是此方法成功的关键。一般值的选择需要凭经验和试验数据预先取 定，这就使得这种方法的应用受到了限制。同时由表3 1 可见，c a 达到最终稳 定需要的演化次数是比较多的。 基于以上的原因，我们提出了一种自动取阈值，演化次数较少的c a 边缘检 测方法。 3 3 4 灰度相对变化率检测的c a 模型 我们考虑的基本思路基于上一节的讨论，将图像边缘定义为像素灰度发生剧 烈变化的区域。考虑到检测结果需要应用到拼接的后续流程中去，我们希望c a 演化的次数应该尽量的少。c a 达到稳定状态的最终分布应达到这样的结果：像 素灰度变化平缓的区域，元胞状态值较小；像素灰度变化剧烈的区域，元胞状态 值较大。 综合以上的考虑，我们提出如下的演化规则： “= m i n ( 1 。 ，l ) ( 3 4 ) 其中：a = e 。一l 。 j k = m a x ( n ( g ) ) ，l m 。= i n i n ( ( e ) ) 演化截止条件是：如果i “1 = i ，那么c a 停止演化。 式( 3 4 ) 表达的演化规则是中心元胞的状态值与其邻域的状态极大值和极小 值之差作比较，取两者的较小值作为中心元胞的新状态值。演化的结果总是使得 上海人学硕士学位论文 处于变化平缓区域的元胞状态值不断减小，直至零状态；同时变化剧烈区域的元 胞达到某个状态值。当某个元胞状态值为零时，在本规则作用下，其状态值不再 变化：当某个元胞的邻居状态值都为零时，则在本规则作用下，其状态值也不再 发生变化。从而，整个c a 系统达到稳定的构型。因此，本规则必然能够使c a 达到稳定状态。状态值非零的元胞代表信号变化的位置，其状态值代表信号变化 的大小。 取半径为1 的v o nn e u m a n n 邻域和循环边界条件利用上述演化规则对l e n a 图像进行c a 演化的结果，图3 5 是其演化结果。 ( a ) l e n a 图像 ( b ) 1 次演化( c ) 2 次演化( d ) 3 次演化( 稳定结果) 图2l e n a 图像以及演化结果 与上一小节所论述的方法相比，本规则不需要预先确定阈值，能快速地检测 出图像边缘，而且最终检测结果优于前一种c a 检测方法。 本节方法提出的c a 模型的规则、边界条件以及邻域类型对最终边缘检测结 果的影响，将在第五章第2 节具体讨论。 1 9 上海大学硕上学位论文 3 4 小结 本章首先介绍了c a 的概念，然后给出了它的严格定义。给出图像边缘的定 义之后我们概述了传统的边缘检测方法。最后我们给出了采用c a 模型进行了边 缘检测的2 种具体规则，其中第2 种c a 检测方法将用于下一章的图像拼接流程 中。 2 0 上海大学硕士学位论文 4 1 引言 第四章基于c a 的图像拼接方法 第二章介绍了图像拼接的一般流程和关键技术，第三章介绍了我们采用c a 进行图像边缘检测的方法。有了前两章的基础，本章将具体介绍基于c a 的图像 拼接方法。图4 1 是整个方法的算法流程图。 4 2 特征点提取 在基于特征的图像配准算法中，特征点集的选择是一个重要的问题【3 3 】。选择 特征点集最普遍的方法是挑选出具有高度相关性的对应点对而不考虑这些点的 空间分布和搜索复杂度。可能出现的情况是所有挑选出的特征点会位于整个图像 中比较集中的区域。在这种情况下，这些挑选出的特征点将无法说明整个图像的 真实运动参数。为解决这一问题，我们提出了一种考虑特征点在空间分布的情况 的方法。 首先，我们将图像分为特定尺寸的块，在每一块内留具保有最大灰度值的特 征点，这样在每一个图像中我们得到了一定数量的经过选择的特征点。相比于通 常采用的方法，这种方法得到的特征点具有均匀的空间分布，从而将提高图像配 准的精度。图4 2 是边缘检测后特征点提取的结果。 ( a ) l e n a 原图( b ) 边缘检测( c ) 特征点提取 图4 2l e n a 的特征提取结果图 2 l 上海大学硕士学位论文 图4 1 基于c a 的图像拼接方法流程图 上海人学硕士学位论文 4 3 寻找匹配特征点对 4 3 1 相似度测量 为了比较一幅图像中的a 区域与另一幅图像中的b 区域，b 需要和a 中的 每一个像素进行比较，这就需要区域a 与区域b 比较测量相似度的方法。当比 较图像区域a 和b 时，他们必须具有大小相同的尺寸。如果有一块图像大于另 一块图像，较大图像中超出较小图像的那一部分必须去除。 我们的目标是将这两个相同大小尺寸的图像之间的相似度用一个数值来表 达。解决这一问题的方法有多种，但实际中最常用的方法有两种，分别是s s d ( s u m o f s q u a r ed i f f e r e n c e ) 和c c c ( c r o s sc o r r e l a t i o nc o e f f i c i e n t ) 。这两种方法的选择不 是随意的。前者比较快但是结果较差，后者计算量较大但结果比较精确。 s s d 比较简单，它在a 和b 图像区域中取相同位置的像素狄度，作差，然 后对结果进行平方。在a 和b 中完成此运算。最终得到的数值之和表示a 和b 之间的相似度。 s s d 和c c c 的表达式如下： = ( i a x , ，y a - i b ( x , ，乃) ) 2 ( 4 1 ) ( ( l ( t ，y j ) - a ) - ( ( t ，乃) 一丘) ) ( 乏c c = f = = = _ = 皇= = = = = = = = = = = = = = = = = = = = = = = = 一( 4 2 ) ，( ( l ( 薯，y j ) 一) 2 ) ( ( 厶，乃) 一) 2 ) yl1l， a 和b 之间非常相似由s s d 表示为数值0 ，如果a 和b 相差较大，s s d 得 到的结果将大于0 。s s d 的结果取决于图像选择区域的尺寸。这就意味着对于不 同的图像尺寸不同的s s d 数值可能代表了相同的相似度。 与图像区域尺寸无关的方法是c c c ，它所给出的是一个在 - 1 ，1 】之间的数值。 4 3 2 寻找所有的匹配特征点对 在这里，任意两个特征点( p x ，以) 和( q x ，q ，) 之间的相似度由( 4 2 ) 式的归一化 互相关系数来表示，相似度测量的取值范围是 1 ，1 】。 上海大学硕士学位论文 对于每一个特征点p ，我们可以通过找到相似度测量最大的值( 这一值应当 大于某一预先指定的阈值) 来决定其匹配点g 。这样我们可以得到所有可能的匹 配特征点对。 4 3 3 消除错误匹配特征点对 基于图像旋转和缩放变化不大的前提，我们提出一致性检验的方法来消除错 误的匹配特征点对【3 5 1 。其原理是在相机的旋转和缩放运动相对于平移运动来说比 较小的前提下，两对正确的匹配特征点对之间的向量之间的差别很小。图4 3 是 一致性检测条件的示意图。 假设御= p k 营q k ，七= 1 ，2 ，虬 是一组匹配特征点对，虬代表脚中元素 的总数，p k 是图像中的特征点，q t 是图像t 中的特征点，r j z , 既和吼之间存 在关系： q k = 显咒巩+ 丁兰p k + 丁( 4 3 ) 瓠- 且r 兰( 舞嚣m ： 。 如果特征点对( b 营吼) 和 p j 营吼) 是正确的匹配点对，那么向量z = 吼一只 和巧= q l 一局之间的差值将会很小。 从而向量霉和写之间的差值决定了匹配特征点对是否一致。对当前某一向量 z ，考察其所有可能的匹配特征点对，记录满足一致性条件的特征点对数目。对 具有最大数目的符合一致性条件的匹配点对，我们比较它们的相似度，取具有最 大相似度测量的匹配点对作为一个可靠的匹配点对，并以此为基准，消除与之不 一致的特征点。 上海大学硕上学位论文 4 4 获得变换参数 4 4 1 刚体变换四参数的计算 图4 3 一致性检测 我们采用奇异值分解s v d 技术计算刚体变换模型的四参数( 即缩放比例， 旋转角度，两个方向的平移量) 。 假设m = ( 只吼，i = l 2 ) 是正确的匹配特征点对，这里札是正确匹配 特征点对的总数。基于下式，我们来推导刚体变换的四参数( s ，r 和r ) 。 铲她一s ( 篓尝纠 n 4 ， 铲她盯剐【s i n 口c 。s 目j 只+ 4 4 ) 误差函数定义为：m ：兰i 扛舰+ 丁一引1 2 。 从等：o ，我们得到： a t = 石一麒；( 4 5 ) 这蛄专；= 专 从票- o ，剐脚o ： 上海大学硕士学位论文 彰厨， p 号一 彰歹， f = l 这里e = p ，一芦，玩= q 。一虿。 从而中可以表示成： ( 4 6 ) ， r 札 o 虬i 艺彰膨一 中= 艺彰玩一生专j 。那么最小化巾可转化为最 1 f ；e = 降硒 。 可以按照如下步骤采用s v d 技术求解r ： 虬 ( 1 ) 计算2 2 矩阵日，日= 芦。藓； i = l ( 2 ) 计算日的奇异值分解，即h = p a q f ( 3 ) r = 妒。 将r 值代入( 4 6 ) 式我们可以得到s ，将r 和s 代x ( 4 5 ) 式可以得到丁。 4 4 2 精炼匹配点和投影变换八参数的计算 刚体变换的四参数将作为投影变换八参数的初始估计值，然后通过精炼的匹 配特征点计算最终的八参数。 如果p i = ( m ，毋) 和吼= ( 靠，唧) 是匹配特征点对，求解八参数的步骤如下： ( 1 ) 用s v d 技术求解刚体变换四参数( s ，0 ，0 ) ； ( 2 ) 用四参数作为投影变换参数的初始估计： p 海大学硕士学位论文 阱 ( 4 7 ) ( 3 ) 由( 4 7 ) 得到p 的精炼q ，重复步骤( 1 ) 和( 2 ) 得到最终的四参数和八参 数。 4 5 小结 本章主要介绍了一种基于c a 的图像拼接方法。首先采用第三章所述的边缘 检测方法得到图像的边缘特征点，然后通过相似度测量获得粗略的匹配特征点， 接着通过一致性条件的引入，获得精确的匹配特征点。在此之后，利用s v d 技术 获得刚体模型的四参数，最后通过四参数得到精炼的匹配点，得到投影模型的八 参数。 上海大学硕士学位论文 5 1 引言 第五章实验结果与分析 本章将给出采用本文提出的方法进行图像边缘检测和图像拼接的实验结果。 首先我们将具体讨论选择不同的c a 边界条件和邻域类型的对边缘检测结果的 影响。最后是采用本文方法后的实验结果，包括与其他方法相比的时问消耗的比 较。 5 2c a 边缘检测实验 5 2 1 边界条件的影响 本节我们讨论不同的边界条件对特征提取的影响。 我们使用3 3 4 节所提出的方法进行边缘检测。为了方便讨论，这里我们取 半径为l 的v o n n o a m a n n 邻域。 由第三章的介绍可知有四种边界可供选择：周期边界，固定边界，绝热边界， 映射边界。我们以特征点的选取结果作为讨论的对象。 周期