（计算机应用技术专业论文）用于图像分割的人工生命模型的研究.pdf

用于图像分割的人工生命模型的研究 摘要 数字图像处理技术在近2 0 多年的时间里，迅速发展成- - i 独立的具有强大 生命力的学科。数字图像处理技术广泛应用于工业、军事、医学等领域，而且 现在对能快速自动处理海量图像数据库技术的需求越来越强烈。 图像分割是图像理解和物体识别的第一步，是图像处理中的一个主要问题， 也是计算机视觉领域低层次视觉中的主要问题。图像分割是许多图像处理任务 中的一个关键环节，例如：图像描述、图像识别和基于目标的图像压缩等。图 像分割的结果直接决定了这些图像处理任务的结果的质量。 图像分割是一个有挑战性的复杂问题。到目前，虽然已经有了各种类型的 分割算法，但是这些方法普遍存在问胚和缺陷，影晌了性能和应用，因此需要 继续探索新的途径，对图像分割继续深入研究。 人工生命是一个快速发展的多学科交叉的新兴研究领域，已经在解决现实 世界中的很多复杂问题上显示出了潜在的应用前景。在图像分割的研究中引入 人工生命的思想，将具有广阔的研究空间和很好的前景，将有希望发现新颖的 解决策略。 本文提出一种新颖的自动图像分割模型人工协作细胞模型( a r t i f i c i a l c o l l a b o r a t i v ec e l l s , a c o c e l i s ) 。在a c o c e l l s 中，图像被映射为环境。细胞 生存于图像环境中，按照系列体现生命特征的协作、繁殖、遗传、竞争等规 则进化。不需要预先得到任何图片信息，图像分割通过细胞的进化，自动涌现 出来。a c o c e l l s 模型是普适的，能够适应不同的应用的特定需求。实验结果 表明此模型在图像分割领域具有很好的性能和应用潜力。 关键字：图像分割；人工生命；人工协作细胞 用于图像分割的人工生命模型的研究 a b s t r a c t i m a g ep r o c e s s i n gs y s t e m sh a v ep r o v e nv e r yu s e f u li nm a n ys p a c e ，i n d u s t r i a l ， m i l i t a r y , a n dm e d i c a la p p h e a f i o n s t h e r ei sag r o w i n gn e e df o ri m a g ea n a l y s i s m e t h o d s ，w h i c hc a l lp r o c e s sl a r g ei m a g ed a t a b a s eq u i c k l ya n dw i t hl i m i t e dh u m a n i n p u t i m a g es e g m e n t a t i o n ，t h et e c h n i q u et op a r t i t i o ni m a g ei n t or e g i o n s ，i sa n e s s e n t i a l p r o c e s s f o rm o s ti m a g e p r o c e s s i n g t a s k ss u c ha si m a g ed e s c r i p t i o n ， r e c o g n i t i o n ，a n do b j e c tb a s e di m a g ec o m p r e s s i o n ，a n di so n eo ft h em o s tc h a l l e n g i n g r e s e a r c ht o p i c si ni m a g ep r o c e s s i n ga n dc o m p u t e rv i s i o n av a r i e t yo fs e g m e n t a t i o n a l g o r i t h m sh a v eb e e nd e v e l o p e d h o w e v e r ，t h e i rp e r f o r m a n c ei ss t i l lf a rf r o m s a t i s f a c t o r y t h e r ei sp l e n t yo fr o o ma n dn e e dt oe x p l o r ef u r t h e ra n dd e v e l o pn e w a p p r o a c h e st oi m a g es e g m e n t a t i o n a r t i f i c i a ll i f ei sj u s tan e we m e r g i n ga n dr a p i d l yg r o w i n gr e s e a r c hf i e l d ，b u ti t h a sp r o v i d e dm a n yn o v e ls o l u t i o n st oc o m p l e xr e a l - w o r l dp r o b l e m s i ti s h o p e f u l t h a ts o m ei n n o v a t i o n a la p p r o a c h e sf o ri m a g es e g m e n t a t i o n ，w h i c hc a n n o tb ef o u n d u n d e rt h et r a d i t i o n a lr e s e a r c hs t r a t e g i e s c u r r e n t l ya p p l i e dt o t h ef i e l d ，c a l lb e e x c o g i t a t e db ya p p l y i n gt h ea r t i f i c i a ll i f ec o n c e p t t h i sd i s s e r t a t i o n p r e s e n t sa ni n n o v a t i v ea r t i f i c i a ll i f em o d e lf o ra u t o m a t i c i m a g es e g m e n t a t i o n - a r t i f i c i a lc o l l a b o r a t i v ec e l l s ( a c o c e l l s ) i na c o c e l l s ， a ni m a g ei sv i e w e da sal a t t i c ee n v i r o n m e n tw h e r et h ec e l l sl i v ei n e a c hc e l ll o c a l l y i n t e r a c t sw i t hi t sl i v i n ge n v i r o n m e n t ，c o m m u n i c a t e sa n dc o l l a b o r a t e sw i t hi t s n e i g h b o r s ，a n de v o l v e sa c c o r d i n gt o as y s t e mo fr u l e st h a tr e f l e c t i m p o r t a n t b i o l o g i c a lp r o p e r t i e s ，i e ，r e p r o d u c t i o n ，i n h e r i t a n c e , c o l l a b o r a t i o n ，a n ds oo n t h e s e g m e n t a t i o nr e s u l t sa r ea u t o m a t i c a l l yo b t a i n e dw i t h o u ta n yp r i o rk n o w l e d g eo ft h e i m a g e a c o c e l l si sg e n e r i ca n di sa p p l i c a b l et ov a r i o u ss e g m e n t a t i o np r o b l e m s a n dt h ee x p e r i m e n t ss h o wt h a tt h i sm o d e lo f f e r s g o o dp o t e n t i a lf o ri m a g e s e g m e n t a t i o n 、 k e y w o r d s ：i m a g es e g m e n t a t i o n ，a r t i f i c i a ll i f e ，a r t i f i c i a lc o l l a b o r a t i v ec e l l s ， a c o c e l l s 用于图像分割的人工生命模型的研究 第1 章绪论 1 1 研究背景和动机 在人类接受的信息中有8 0 来自视觉或者说为图像( h a a g e ) 信息，这包 括图像、图形( 动画) 、视频、文本、数据等，这是人类最有效和最重要的信息 获取和交流方式。数字图像处理起源于2 0 世纪2 0 年代的海底电缆传输数字照 片，其后图像处理技术逐步得到相应发展。但是，由于技术手段的限制，图像 处理科学与技术发展相当缓慢。直到第三代计算机的问世和普及，数字图像处 理开始迅速发展并得到普遍应用。人们越来越多地利用计算机来帮助人类获取 和处理视觉( 图像) 信息。数字图像处理技术在近2 0 多年的时间里，迅速发展 成为一门独立的有强大生命力的学科，广泛应用于遥感、技术诊断、自主车导 航、医学成像( 2 d 和3 d ) 和自动监视等领域。而且，随着计算机技术的日益 发展，数字图像处理技术的日益完备，图像处理的应用范围将越加深入和广泛。 当人观察景物时，在视觉系统中对物体进行分割的过程是必不可少的。这 个过程非常有用，以至于使人所看到的并不是一个复杂的景物，而只不过是一 种物体的集合体。使用数字处理，我们必须设法分离图像中的物体，把图像分 裂成像素集合( 区域) ，每个集合代表一个物体( 或者是物体的某一部分) 的图 像，这就是数字图像分割。因此可以理解为图像分割将一幅图像划分成若干互 不交迭区域的集合，这些区域要么对当前的任务有意思，要么有助于说明它们 与实际物体或物体的某些部分之间的对应关系。图像分割是图像理解和物体识 别的第一步，是图像处理中的一个主要问题，也是计算机视觉领域低层次视觉 中的主要问题。图像分割是许多图像处理任务中的一个关键环节，例如：图像 描述、图像识别和基于目标的图像压缩等。图像分割的结果直接决定了这些图 像处理任务的结果的质量。 图像分割的应用非常广泛，几乎出现在有关图像处理的所有领域，并涉及 各种类型的图像。例如，在遥感应用中，合成孔径雷达图像中目标的分割；遥 感云图中不同云系和背景分布的分割等。医学应用中，脑部m r 图像分割成灰 质、白质、脑脊髓等脑组织和其他非脑组织区域等。在交通图像分析中，把车 辆目标从背景中分割出来等。在面向对象的图像压缩和基于内容的图像数据库 查询中，将图像分割成不同的对象区域。在这些应用中，分割通常是为了进一 步对图像进行分析、识别、压缩编码等，将一幅图像划分成若干互不交迭区域 的集合，因此，分割的准确性直接影响后续任务的有效性，因此具有十分重要 的意义。 用于图像分害4 的人工生命模型的研究 1 2 研究工作背景、内容和贡献 图像分割是一个经典难题，由于问题的重要性和困难性，从二十世纪七十 年代起图像分割问题就吸引了很多研究人员为之付出了巨大努力，虽然已有多 种分割算法，例如：灰度直方图的方法，区域的方法，基于数学形态学的方法， 基于遗传算法的最优化参数设置的方法等，但这些算法都存在一定的缺陷，影 响了它们的性能和应用。到目前为止，在图像分割领域还不存在一个通用的方 法，也不存在一个判断分割是否成功的客观标准。因此，对图像分割需要探索 新的途径，考虑引入新的理论，提出新的方法，进行进一步的深入研究。 人工生命是二十世纪八十年代末兴起的一门交叉学科，是联结信息科学和 生命科学的一条纽带，是计算机科学新的发展方向之一，其研究内容包括：物 种进化、遗传算法、自组织、自适应、智能体、生命现象模拟、生物与社会、 基因工程、人工化学、生命动力学、人工生命哲学、人工生命方法论、算法、 人工智能等有关研究课题。人工生命研究那些“具有自然生命特征和生命现象 的人造系统的理论模型生成方法和实现技术”，抽象地提取控制生物现象的基本 动态原理，并且通过物理媒介( 如计算机) 来模拟生命系统动态发展过程。而 且人工生命通过对生命世界的模拟不仅更好地理解生命现象，同时也为解决复 杂问题提供新的思路和方法。虽然它还是新兴学科，但已在解决复杂问题上显 示出很好的前景。 过去的十多年，研究人员探索把人工生命应用到计算机图像处理中，开拓 了研究思路，带来发现更新颖、更有效的理论和方法的可能性，并且已经在一 些方面取得一定的成功。目前，已经有研究人员尝试将人工生命应用到图像分 割领域中来，虽然相关的研究还比较少，但是取得的研究成果表明将人工生命 引入到图像分割中能够获得有意义的成功。人工生命用于图像分割将有很好的 应用潜力和前景，需要进一步深入研究下去。 生物学家发现生命具有同种族相互聚集协作实现种群进化，不同种族相互 竞争的特点，这种现象在计算机图像分割上具有很好的应用潜力。本文根据这 种现象提出一种新颖的用于自动图像分割的人工生命模型人工协作细胞 ( a r t i f i c i a lc o l l a b o r a t i v ec e l l s ，a c o c e l l s ) 。在这个a c o c e l l s 中，图像被 看作一个方格的环境。协作细胞生存在图像环境中，并按照系列体现生命特 征的规则进行进化。其中进化规则包括协作、繁殖、遗传、竞争等等。图像分 割的结果可以在不需要预先得到任何图片信息的情况下通过细胞的进化，自动 涌现出来。 用于图像分割的人工生命模型的研究 1 3 论文结构 本文主要由七个部分构成。第一部分是引言，主要介绍进行图像分割的背景 和动机，研究工作内容和贡献，以及整个论文的结构安排。第二部分为图像分割 的背景知识与相关研究，主要介绍了与图像分割的一些基本概念和图像分割的一 些经典的基本方法和相关工作。第三部分为人工生命的背景知识与相关研究，主 要介绍了人工生命这一新兴学科的发展和应用的情况和相关工作。第四部分介绍 了作者研究的应用于自动图像分割的人工协作细胞模型，系统地介绍了模型的各 个模块和整个算法。第五部分通过实验展示了人工协作细胞模型用于图像分割的 性能优势和发展与应用的潜力，分别进行了性能的定量和定性分析，以及与其他 经典方法的对比实验。第六部分对本文进行总结，同时讨论今后的工作。第七部 分是本文所用到的参考文献信息。 用于图像分割的人工生命模型的研究 第2 章图像分割 2 1 图像分割的定义 图像分割是将一幅图像划分成若干互不交迭区域的集合，每个集合代表一 个物体( 或者是物体的某一部分) 的图像，这些区域要么对当前的任务有意义， 要么有助于说明它们与实际物体或物体的某些部分之间的对应关系。 通用的分割定义，分割出的区域需同时满足均匀性和连通性的条件。其中 均匀性是指该区域中的所有像素点都满足基于灰度、纹理、彩色等特征的某种 相似性准则；连通性是指在该区域内任一两个像素之间存在一条完全由这个区 域的元素构成的连通路径。有两种可供选择的连通性准则，如果只依据旁侧相 邻的像素( 上、下、左、右) 确定连通，称为4 连通，物体也就被称为是4 连 通的。如果再加上对角相邻的( 4 5 度邻点) 像素也被称为时连通的，那么，得 到8 连通。这两种中的任意一种都可用，只要具有一致性即可。通常8 连那个 的结果与人的感觉更接近。【1 】 图像分割的数学形式化定义为【2 】【3 】： 设f 表示一幅图像中所有像素的集合，p ( o 是有关均匀性的假设，图像分 割定义为把f 划分成若干子集( 墨，s ：，s n ) ，其中每一个子集都构成一个空间 连通区域，即 u s , = f 且墨n s j - 0 ，i 一， ( 2 1 1 ) i - 1 且p ( 口) 满足 p ( s ) - t r u e ，v i( 2 1 2 ) 和 p ( 置u s ，) = 归b e ，若墨与s ，在空间相邻 ( 2 1 3 ) 显然图像分割就是要找到一个合适的划分将整个图像区域划分成若干个连通 子区域。 2 2 传统的图像分割方法 传统的图像分割方法，主要是基于在一个区域内灰度的同一性或相似性， 而不同区域灰度的不连续性或差异性的。根据操作单元，可以将传统的图像分 用于图像分割的人工生命模型的研究 割方法分为三类：基于像素点的方法、基于边界( 线) 的方法和基于区域的方 法。 2 2 1 基于灰度直方图的方法 在数字图像处理中，一个最简单和有用的工具是灰度直方图。灰度直方图 是灰度级的函数，描述的是图像中具有该灰度级的像素的个数；其横坐标是灰 度级，纵坐标是该灰度出现的频率( 像素的个数) ，图2 2 1 1 一示例。f 1 】 图2 2 1 1 一幅图像及其灰度直方图 很多物体或图像区域表征为不变的反射率或其表面光的吸收率，因此可以 确定一个灰度常量即阈值来分割物体与背景。一幅含有一个与背景明显对比的 物体的图像具有包含双峰的灰度直方图，图2 2 1 2 为一示例。两个尖峰对应于 物体内部和外部较多数目的点。两峰间的谷对应于物体边缘附近相对较少数目 的点。在类似这样的情况下，可以使用直方图来确定灰度阈值的值。 当使用闺值规则图像分割时，所有灰度值大于或等于某阈值的像素被判为 属于物体。所有灰度值小于该阈值的像素被排除在物体之外。边界则是这样一 些内部点的集合，这些点都至少有一个邻点不属于该物体。阈值化是输入图像 f 到输出图像g 的入下变换： g ( f ，小f j 嚣髂筹 ( 2 z - ) 其中丁是阈值，对于物体的图像元素g ( i ，) 一1 ，对于背景的图像元素g ( i ，) 一0 ( 或反之亦然) 。因此，选择正确的阈值是闽值分割成功的关键。 对于处理海量数据的图像库的应用，使用阈值分割必须解决闽值的自动选 取的问题。图像阈值自动选取方法的研究长期以来吸引着众多学者，寻找简单 实用、自适应强的阈值自动选取方法是这些研究者们的共同的目标。 o t s u 在1 9 7 9 年提出的最大类间方差法( 有时也称之为大津方法) 【4 】一直 被认为是阈值自动选取的最优方法。最大类问方差法的大致过程为：记f ( f ，f 1 为图像( f ，) 点处的灰度值，灰度级为l ( o l 一1 ) 。记p ( k ) 为灰度值k 的频率， 用于图像分割的人工生命模型的研究 其中n 是图像包含的像素点的数目。 假设用灰度值f 为阈值分割出的目标与背景分别为： f ( i ，j ) s f 】和 f ( i ，j ) f ) ，其灰度值范围分别为g = o ，1 ，r 】和c 1 = t + l t + 2 ，三一1 ) ， 于是 目标部分比例：( f ) 。薹p ( ) 目标部分点数：0 ( f ) ；n p ( i ) u m 鲥 目标部分平均灰度均值：( f ) 4 磊f p ( ) ( ) 背景部分比例：q ( f ) 2 磊p ( ) 背景部分点数：1 ( f ) = 。丕p ( ) 背景部分平均灰度均值：h ( f ) 。蒌驴( ) q ( ) 图像灰度总均值：肛( f ) = ( f ) 胁( f ) + q ( f ) 肫( t ) o t s u 算法求图像最佳阈值t + 的公式为： t 一曲苫肘缸 o ) o ) 一p 】2 + q ( f ) 地( f ) 一叫2 ( 2 2 _ 1 3 ) o t l o 。 一一。 该式右边括号内实际上就是类间方差值，阈值f 分割出的目标和背景两部分构 成了整幅图像，而目标灰度均值( t ) ，概率为( t ) ，背景灰度均值h ( t ) ，概 ( a )( b ) ( c ) 图2 2 1 2 图像阈值化：( a ) 原图像；( b ) 灰度直方图；( c ) 二值化阈值分割结果。 刁 l2 犯 l 了瓢， 一 昌 似 p 有则 用于图像分割的人工生命模型的研究 率为岫( t ) ，总均值p ( t ) ，根据方差的定义即得该式。因为方差是灰度分布均 匀性的一种度量，方差值越大，说明构成图像的两部分差别越大，当部分目标 被错分为背景或部分背景被错分为目标都会导致两部分差别变大，因此，使类 间方差最大的分割也意味着错分概率最小，这便是o t s u 方法的真正含义。【5 】 如果图像中含有多个物体，尤其是含有多个灰度值存在差异的物体，显然 不能进行二值化分割。应次，还有许多使用多阈值的阈值化修正方法，其处理 后的结果图像不再是二值的，而是有一个有限的灰度值集合组成的图像： g ( f ，) i 其中每个b 是一个指定的灰度子集。 ( d )( c ) 图2 2 1 3 图像多阈值化：( a ) 原始图像；c o ) 两目标分割结果； ( c ) 三目标分割结果；( d ) 四目标分割结果；( e ) 五目标分割结果。 q 乞互 埘叫州 硝 bbb b 州“州他 当当当 当其 1 2 3 一 n o 用于图像分割的人工生命模型的研究 o t s u 算法不仅适用于选择单阈值，也可用于多阈值的确定。【6 】假设需要 m 一1 个阈值 f 1 ，f ：，o 一。 来将图像分割成m 个子集，这些子集包含的灰度值 范围分别为：一 0 ，f 1 ，c j = k + 1 ，乞 ，c = k 一，+ 1 ， ，c m h 一，+ 1 ，l 一1 。 最佳阈值 ，t ：，一。 的公式为： ，f ，。 | a r g 胁x 司( ，铲，t u 一。) ( 2 2 1 5 ) 0 f i - - t u - * l 一1 其中以荟嗥( 尥一如) 2 ，o j r 。墨a ，段。荟慨，魄。图2 2 1 3 是使用o t s u 算法扩展到多阈值后的一个例子。 阈值化分割计算代价小、速度快，是最老的分割方法且在简单的应用中仍 然被广泛的使用着。 但是，如果图像或包含物体图像的区域面积不大且有噪声，那么，直方图 本身就会有噪声。除了凹谷特别尖锐的情况外，噪音会使谷的定位难以辨认， 或至少是不同幅图像得到的结果不稳定可靠。当一幅图像被压缩为直方图后， 所有的空间信息都丢失了。直方图描述了每个灰度级具有的像素的个数，但不 能为这些像素在图像中的位置提供任何线索。因此，任意特定的图像有唯一的 直方图，但反之并不成立极不相同的图像可能有着相同的直方图( 例如， 在图像中移动物体一般对直方图没有影响) 。【1 】阈值方法仅仅考虑了图像的灰 度信息，忽略了图像中的空间信息，对于图像中不存在明显的灰度差异或多个 物体的灰度值范围有较大重叠的图像分割问题难以得到准确的结果。 另外，使用基于灰度直方图的阈值化分割还存在一个难以解决的问题，那 就是待分割图像中的物体的数目。【2 】从图2 2 1 3 的例子可以看出，在设置不同 数目的分割目标后得到的分割结果是不同的，因此需要设置合适的与当前处理 图像相关的分割目标数目，而在实际的自动图像处理中( 海量图像数据无人为 指导的自动处理) 这是不现实的。 2 2 2 基于边界的方法 基于边界的分割代表了一大类基于图像边缘信息的方法，它是最早的分割 方法之一且现在仍然是非常重要的。 边缘检测方法试图通过检测包含不同区域的边缘来解决图像分割问题，基 于在不同区域之间的边缘上图像函数在灰度、色彩、纹理等图像特征方面的变 化往往比较剧烈。 基于边缘的分割依赖于边缘检测算子找到的图像边缘。图像边缘是赋给单 用于图像分割的人工生命模型的研究 个对应某个方向) 【7 】 啊2 叫矧 叫m l g ( i ，) 一g ( i + l ，y + 1 ) l + l g ( i ，+ 1 ) 一g ( f + 1 ，) i ( 2 2 2 2 ) 。 ；i 】- t 。f 1 c 2 - 2 z s ， 4 寻三 2 三寻三1 g 2 z 4 ) 啊5 主三三 如， 兰三副玛2 ；ii ；】 g 2 z 用于图像分割的人工生命模型的研究 啊4 【立 啊。 三 到如一e翊蚝2 三； 三1 三】啊。 圭三11 1 啊5e i 1 c 2 2 z 固 i 3331 3 3 3 1i 一5 3 3 l 啊= i 30 3 ih 2 一i - 5 0 3 i 坞= l - 5 0 3 i ( 2 2 2 7 ) 【一5 5 5 j【一5 - 53 j 一5 3 3 j 卷积边缘检测算子的主要缺点是它们依赖于尺度且对噪声敏感。很少有合 适的理由来解释为什么选择某个特别的局部邻域算子尺度。 边缘检测算子检测得到的图像结果( 边缘图像) 并不能用作分割结果。在 边缘图像中几乎没有0 值像素，小的边缘值对应于由量化噪声、弱且不规则照 明等引起图像特征方面的非显著的变化，而且这些因素的影响还可能导致在没 有边界的地方出现了边缘，以及在实际存在边界的地方没有出现边缘。因此， 需要对边缘图像进行处理排除这些小的数值，排除噪声等因素的影响，得到真 正属于边界的信息。 为通过边缘图像建立真正的边晃，可以使用几种方法：边缘图像阈值化、 边缘松弛法、边界跟踪等。边缘图像阙值化基于图像的边缘幅度由合适的阈值 处理实现。【8 】然而选择合适的全局阈值一般是困难的，有时甚至是不可能的。 边缘图像阈值化得到的边界受图像噪声的影响很大，经常会遗漏重要的部分。 在它们互相领域的上下文中考虑边缘的性质能够增加结果图像的品质。所有的 图像性质包括进一步的边缘存在性在内，都经过迭代评价而使精确性提高，直 至所有的边缘上下文完全清晰为止，这种评价是基于指定局部邻域内的边缘强 度进行的，每个边缘的信度或者被增加或减小。在两个强边缘间的一个弱边缘 构成一个上下文的例子；这个位于其间的弱边缘有很高的可能性属于结果的一 部分。另一方面，如果一个边缘( 即使是一个强的边缘) 置身于没有支持的上 下文中，它可能并不是任何边界的一部分。这就是边缘松弛法的思想。【9 】由于 边缘松弛法在整幅图像范围内搜索边缘一致性的全局最大值，因此边缘松弛法 在经过较大数目的迭代后常常会漂移，给出比预期差的结果。如果区域的边界 未知，但区域本身在图像中已经定义了，那么边界可以通过边晃跟踪唯一地被 检测出来。但是这样要求有针对具体图像的先验知识，实际的应用对应大量的 用于图像分割的人工生命模型的研究 不同图像，无法提供每幅图像的先验知识，因此无法实际的应用的需求。即使 将边缘图像通过途径转变成二值的主要留边界点组成的边界图像，基于边界的 图像分割还必须采用后续的处理将边缘合并为边缘链，使它与图像中的边界对 应得更好，最终的目标是至少达到部分分割，即将局部边缘聚合到一幅图像中， 使其中只出现对应于存在的物体或图像部分的边缘链。【7 】 绝大多数基于边界的图像分割方法都集中在边界的检测方面，这些边界部 分地或全部地对图像进行了分割处理。如果获得了完全的分割，边界将图像分 割为区域，但是如果仅产生了部分分割，区域并没有唯一的定义，根据边界确 定区域的问题可能是一个非常复杂的问题，需要与高层知识配合。因此，当前 研究的一个方向就是将边界信息与区域信息结合考虑来进行图像分割。【1 0 】 2 2 3 基于区域的方法 基于区域的方法直接构造区域，基本思想是将图像划分为最大一致性的分 区。一致性是区域的一个重要性质，在区域增长中用作主要的分割准则。一致 性准则可以是基于灰度、色彩、纹理、形状、模型等的标准，对应于公式( 2 1 2 ) 和( 2 1 3 ) 中的p 。下面简单介绍几种基于区域的图像分割算法的思想。【7 】 区域归并( 区域增长法) 最自然的区域增长方法是在原始图像数据上开始增长，每个像素表示一个 区域。这些区域几乎肯定不能满足公式( 2 1 3 ) 的条件，因此只要公式( 2 1 2 ) 的条件仍然满足区域就会被归并起来。 算法2 2 3 1 区域归并 1 定义某种初始化方法将图像分割为满足公式( 2 1 2 ) 的条件的很多小区域。 2 为归并两个邻接区域定义一个标准。 3 将满足归并标准的所有邻接区域归并起来，如果不再有两个区域归并后保持 条件( 2 1 2 ) ，则停止。 区域分裂 区域分裂与区域归并相反，从将整个图像标示为单个区域开始，该区域一 般不能满足条件( 2 1 2 ) 。因此，存在的图像区域顺序地被分裂开以便满足( 2 1 1 ) ( 2 1 2 ) 和( 2 1 3 ) 。 分裂与归并 分裂与归并的结合可以产生兼有两种方法优点的一种新方法。【1 1 】分裂和 归并方法在金字塔图像表示上进行，区域是方形的与合适的金字塔层元素对应。 用于图像分割的人工生命模型的研究 如果在任意金字塔层中的任意一个区域不是一致的，就将其分裂为4 个子 区域，他们是下一层的较高分辨率的元素。如果在金字塔的任意一层中有个区 域具有接近相同的一致性度量数值，就将他们归并为金字塔的上一层中的单个 区域( 参见图) 。分割过程可以理解为分割四叉树的创建，其中的每个叶子节点 代表一个一致区域，即某个金字塔层的元素。分裂和归并对应于分割四叉树的 删除或建立部分，在分割结束后，树的叶结点数对应于分割后的区域数。 分裂l v 1 归并 图2 2 1 3 算法2 2 3 2 分裂与归并 1 定义一个划分区域的初始分割、一致性准则和一个金字塔数据结构。 2 如果在金字塔数据结构中的任意一个区域不是一致的，就将其分裂为4 个子 区域；如果具有相同父节点的任意4 个区域可以归并为单个一致性区域，则 归并它们。如果没有区域可以分裂或归并，则转到第3 步。 3 如果任意两个邻接区域r 和r ；可以归并为一个一致性区域( 即使它们在金 字塔的不同层或没有相同的父节点) ，则归并它们。 4 如果必须删除小尺寸区域，则将小区域与其最相似的邻接区域归并。 从上面介绍的算法以及图2 2 1 3 可以发现，使用这些基于区域的方法进行 图像分割，产生的图像边界将是由一些矩形的边界组成，因此最后得到的区域 边界将是直线段组成，而不是自然边界的平滑。从区域归并法( 区域增长法) 的算法还可以发现，图像分割的结果会依赖于区域被归并的次序，这意味着如 果分割开始于左上角或右下角的话，分割的结果可能会不同。这是因为归并的 次序可能会造成两个相似的邻接区域没有被归并起来，原因是如果使用了的较 早归并且所产生的新特征不再允许与归并。如果归并过程使用了另一种次序， 这一归并可能就会实现了。【2 】【刀 2 2 4 其他方法 图像分割领域中的方法和文献很多，前面介绍了几大类较常用的方法，下 面大致介绍一下其它的一些比较典型的图像分割算法。 近年来数学形态学在图像处理中的应用日渐受到重视，比较有代表性的是 用于图像分割的分水岭算法( w a t e r s h e d ) 。分水岭算法的基本思想是将图像像 素点的灰度看成高度，图像中不同灰度值的区域就对应于山峰和山谷盆地，盆 用于图像分割的人工生命模型的研究 地的边缘就是所谓的水线。水线这个名称的来历是将图像逐渐沉入一个湖中时， 图像的最低点先进水，然后水逐渐漫过山谷盆地，当水位达到该盆地的边缘高 度时就将溢出该盆地，这时在水溢处建坝拦截，如此直到整个图像沉入水中， 所建的坝就成为分开山谷盆地的水线。【1 2 】分水岭算法不是简单地将图像在最 佳灰度级进行阈值处理而是从一个偏低但仍能正确分割各物体的阈值开始。 然后随着阈值逐渐上升到最佳值，使各个物体不会合并。此方法可以解决那些 由于物体靠得太近而不能用全局阈值解决的问题。只有采用最初闽值进行分割 的结果是正确的，那么最后的分割也是正确的。对最初和最终的阈值灰度级都 必须很好地选取。若初始阈值太低，则低对比度的物体开始时就会丢失，然后， 随着阈值的增加就会与相邻的物体合并。苦初始闽值太高，物体一开始就会被 合并。最终的阈值决定了最后的边界与实际物体的吻合程度。 许多现有的图像分割算法有很多的参数需要进行设置或调整，例如p h o e n i x 分割算法 1 3 1 有1 4 个参数需要设置，而且这些参数之间还存在着复杂的相互影 响，那么这样的搜索空间非常大。因此，研究人员尝试采用遗传算法确定参数 集来优化图像分割的结果。【1 4 】遗传算法是基于自然选择的思想，通过使用选 择、交配、遗传和变异的方法，淘汰不适合要求的对象，进化满足条件的对象， 来搜寻问题的最优解。但是，在对使用某个参数集得到的结果进行评价的时候， 需要考虑对图像分割结果进行评价的问题。虽然在图像分割的评价上已经有和 很多成果，出现很多评价方法，但是，直到现在如何评价图像分割的结果仍然 是一个困难的问题，还没有公认的评价标准1 1 5 1 ，不同的评价标准对同一个算 法的评价结果可能截然不n 1 6 1 。而且，这样的方法只是对原有经典方法的性 能的提升，并不能克服那些方法本质上的缺陷。 2 3 本章小结 图像分割是许多图像处理任务中的一个关键环节，例如：图像描述、图像 识别和基于目标的图像压缩等。图像分割的结果直接决定了这些图像处理任务 结果的质量。图像分割是一个有挑战性的复杂问题。到现在，虽然已经有了各 种类型的分割算法，但是这些方法都存在着很多问题，从而影响了它们的性能 和应用。人们逐渐认识到现有的任何一种单独的图像分割算法都难以对一般图 像取得令人满意的分割结果，因而人们在继续致力于将新的概念、新的方法引 入图像分割领域，进行进一步的深入研究。 用于图像分害4 的入t 生命模型的研究 第3 章人工生命 3 1 人工生命的发展和现状 1 7 世纪，伽利略创建了受控试验的科学方法，这种方法是近代科学产生和 发展的主要动力。它不仅产生了伽利略的运动学、牛顿的力学、法拉第的电磁 理论等物理科学，而且产生了生理学、分子生物学等生命科学。可以肯定，这 种方法仍然是推动现代自然科学向前发展的不懈动力【1 7 】然而，现代科学的许 多研究已经越来越多涉及到的是复杂的系统，这些系统涉及许多活动的主体 ( a g e n t s ) ，它们以多种方式不断改变自身的行为，这些行为很难用科学的旧规 范进行测量和观测。2 0 世纪的计算革命导致了自伽利略以来又一场新的方法论 革命：计算机仿真试验革命。这场方法论革命的产物之一是计算机和生物学交 叉的前沿学科人工生命的诞生。 3 1 1 人工生命的发展史 生命科学是研究生命现象的科学。它是以地球上的碳水化合物为基础的生 命为研究对象，因为在人们生活的地球环境中，只有这样一种以蛋白质为基础 的生命形式。其实，科学家们希望用非蛋白质的媒体表现生命的基本形式已经 很久了，当时还不知道d n a 的秘密。 阿兰图灵( a l a nt n r i n g ) 是人工生命的第一个先驱。他在2 0 世纪5 0 年代 早期发表了一篇蕴意深刻的论形态发生( 生物学形态发育) 的数学论文( 1 9 5 2 ) 【1 8 1 。在这篇论文中，他提出了人工生命的一些萌芽思想。他证明相对简单的 化学过程可以从均质组织产生出新的秩序。两种或更多的化学物质以不同的速 率扩散可以产生不同密度的“波纹”，这如果是在一个胚胎或生长的有机体中， 很可能以后产生重复的结构，比如腺毛、叶芽、分节等。扩散波纹可以在一维、 二维或三维中产生有序的细胞分化。在三维空间中，它们比如可以产生原肠胚， 其中，球形的均质细胞发育出一个空心( 最终变为管状) 。就像图灵自己所强调 的那样，进一步发展他的思想需要更好的计算机，而他自己只有很原始的计算 机帮助，所以，他的论文尽管对分析生物学是一个重大的贡献，但并没有立刻 产生作为一门计算学科的人工生命。 冯诺伊曼( v o nn e u n m a n n ) 也是人工生命的先驱。2 0 世纪4 0 年代和5 0 年代，他在数字计算机设计和人工智能领域做了很多开创性的工作。与图灵一 样，冯诺伊曼也试图用计算的方法揭示出生命最本质的方面。但与图灵关注生 物的形态发生不同，他则试图描述生物自我繁殖的逻辑形式。在发现d n a 和 用于图像分割的人工生命模型的研究 遗传密码好几年之前，他已认识到，任何自我繁殖系统的遗传物质，无论是自 然的还是人工的，都必须具有两个不同的基本功能：一方面，它必须起到计算 机程序的作用，是一种在繁衍下一代过程中能够运行的算法：另一方面，它必 须起到被动数据的作用，是一个能够复制和传到下一代的描述。这其实就是自 繁衍的本质所在。冯诺伊曼由此而建立了既能反映自我繁衍的本质又能简洁到 可以作数学分析的细胞自动机( c e l la u t o m a t i o n ，c a ) 模型【1 9 】：把一个长方 形平面分成很多个网格，每一个格点表示一个细胞或系统的基元，每一个细胞 都是一个很简单、很抽象的自动机，每个自动机每次处于一种状态，下一次的 状态由它周围细胞的状态、它自身的状态以及事先定义好的一组简单规则决定。 冯诺伊曼证明，确实有一种能够自我繁殖的细胞自动机存在，虽然它复杂到了 当时的计算机都不能模拟的程度。冯诺伊曼的这项工作表明：一旦我们把自我 繁衍看作是生命独特的特征，机器也能做到这一点。冯诺伊曼死后，a r t h u r b u r k s 填补了冯- 诺伊曼未来得及完成的细节，于1 9 6 6 年以自我繁衍自动机理论 名结集出版。该书的要点之一，就是冯诺伊曼构造了一个具有二十九种状态的 可以自我繁衍的细胞自动机。在2 0 世纪6 0 年代中期，a l v yr a ys m i t h 给出了 所需条件更弱，并且证明过程简洁得多的机器可以自我复制的存在性的证明。 冯诺伊曼和图灵的人工生命观念，被研究者忽视了许多年。这些人的注意 力主要集中在人工智能、系统理论和其它一些研究上，因为这些领域的内容在 早期计算技术的帮助下可以得到发展。而探讨图灵和冯- 诺伊曼的人工生命研究 的进一步含义则需要相当的计算能力，由于当时没有这样的计算能力，它的发 展不可避免地受到了限制。【2 0 】 冯诺伊曼未完成的工作，在他去世多年后由康韦( j o h nc o n w a y ) 、沃弗拉 姆( s t e p h e n w o l f r a m ) 和兰顿( c h r i sl a n g t o n ) 等人进一步发展。 1 9 7 0 年，剑桥大学的康韦编制了一个名为“生命”的游戏程序( t h eg a m eo f l i f e ) ，该程序由几条简单的规则控制，这几条简单的规则的组合就可以使细胞 自动机产生无法预测的延伸、变形和停止等复杂的模式。这一意想不到的结果 吸引了一大批计算机科学家研究“生命”程序的特点。最后终于证明细胞自动机 与图灵机等价。也就是说，给定适当的初始条件，细胞自动机可以模拟任何一 种计算机。因此，康韦不无自信地说，“在足够大的规模上，你将真正看到活的 配置。真正的生命，无论什么理性的定义你愿意给予它。演化，复制，为了领 土而斗争，变得越来越聪明，撰写学术上的博士论文。毫无疑问，在一个足够 大的板子上，在我心里有这种事物将发生”。【2 1 】 2 0 世纪8 0 年代，沃弗拉姆对细胞自动机( c a ) 做了全面的研究。他将细 胞自动机分成四种类型：类型i ，c a 演化到一个均质的状态；类型i i ，c a 演 用于图像分割的人工生命模型的研究 化到周期性循环的模式；类型i i i ，c a 的行为变成混沌，没有明显的周期性呈 现，并且后续的模式表现为随机的，随着时间的变化，没有内在的或持续的结 构：类型，c a 的行为呈现出没有明显周期的复杂模式，但是，展现出局域 化的和持续的结构，特别是，其中有些结构具有通过c a 的网格传播的能力。 2 2 类型i 和i i 的c a 产生的行为，在生物学的模型建构中显得太平淡而失去 了研究兴趣。虽然种类i 的c a 产生了丰富的模式，但是，那里没有突现的行 为，就是说，没有连贯、持久的、超出单一细胞层次的结构出现。在类型的 c a 中，确实发现了突现的行为：从纯粹局部相互作用的规则中突现出秩序。 为什么有些细胞自动机能够产生很有意义的结构，而另外一些却不能呢? 为研究这个问题，兰顿从细胞自动机活动性上分析。兰顿定义细胞自动机活动 性越高，细胞自动机的细胞转换为活的状态的概率也就越高，反之，细胞自动 机转为活的状态的概率就越低。兰顿用不同的细胞自动机活动性做了一系列试 验，结果发现，当活动水平非常低时，细胞自动机倾向于收敛到单一的、稳定 的模式：如果活动性非常高，无组织的、混沌的行为就会发生；只有对于中间 层次的活动性，局域化的结构和周期的行为( 类型i i 和类型i v ) 发生。类型i i 和类型的差别是，类型i i 中的局域化的、周期性的结构并不在空间中移动， 而类型的局域化的结构可以通过网格传播。兰顿推测，在类型中，传播结 构的存在意味着局域化的周期性结构和传播性的周期结构之间可能有任意复杂 的相互作用。2 3 1 因此，兰顿把类型的c a 看作是表达了部分发展了的混沌行为，并因此 把具有这种行为状态的c a 称为处于“混沌边缘”的c a 。在混沌的边缘，既有足 够的稳定性来存储信息，又有足够的流动性来传递信息，这种稳定性和流动性 使得计算成为可能。在此基础上，兰顿作了一个更为大胆的假设，认为生命或 者智能就起源于混沌的边缘。为了能够用计算机进一步探索生命的规律，兰顿 认识到应当有一门专门的研究领域或学科来做这方面的工作。这个新的研究领 域或学科，兰顿把它命名为“人：【生命”( a r t i f i c i a ll i f c ，简称a l i f e ) 。兰顿认 为人工生命是“研究那些具有自然生命现象的人造系统”；“人工生命是这