（计算机软件与理论专业论文）基于人工生命的图像边缘提取方法研究.pdf

摘要 摘要 边缘提取是指对数字图像中的边缘或者边界进行检测和描述。它足计算机视 觉中最基本也是最关键的问题之一。边缘提取对图像处理的其他方面例如图像分 割、纹理分析、物体模式识别等有重要的意义。传统常用的边缘提取方法是面向 局部信息的，这些方法的主要优点是简单易用，效果直观。但是它只关注了图像 中的细节信息，受噪音影响很大，不能从全局把握。面向全局信息的边界检测方 法也有很多。例如，霍夫变换( h o u g ht r a n s f o r m ) 和“蛇”( s n a k e ) 模型等等。但足 他们往往局限于所处理的图片的严格的范围，没有广泛的适用性。 人工生命的研究萌芽于2 0 世纪中叶，随着计算机性能的提高在最近_ 十年中 迅速兴起。入一 生命主要研究那些展示自然生命现象及其行为特征的人造系统。 个非常令人着迷的思想吸引着大批研究人员的关注，也是人工生命的重要基础 观点之一，那就是“个体的行为简单、局部并且带有随机性，但是整体的行为连 贯、协调并且不盲目”。启发了研究复杂性系统的不同于传统分析思想的可预见 前景的新思路。 用于边缘提取的人工杆菌模型受启发于自然界中普遍存在的真实的杆菌。首 先，杆菌直短线状的形状很有利于描述线条；其次，真实的杆菌在繁殖和移动的 过程中就会排列成有趣的曲线。人工杆菌模型是基于人工生命理论和真实杆菌群 落的、以数字图像的边缘提取为目标构建的。本文提出的人工杆菌模型反映了生 命世界的并行、动态、鲁棒等特点，具备了从图像中提取曲线的功能。 经过实验的验证，人工杆菌模型具有许多优良的特性。例如：良好的抗噪性、 迅速收敛以及稳定性、几乎无冗余以及完整性、带有方向信息及其精准性等等。 关键字：人工杆菌、人工生命、边缘提取、图像处理 a b s t r a c t a b s t r a c t a r t i f i c i a lb a c i l l im o d e li se n l i g h t e n e db yr e a lb a c i l l u s 诵d e l yl i v i n gi nn a t u r e t h es h a p eo fr e a lb a c i l l u sl i k e ss m a l lr o dw h i c hi sa d v a n t a g e o u st od e s c r i b ec u r v e i n t e r e s t i n gl i n es h a p ei sa r r a y e db yr e a lb a c i l l id u r i n gt h e i rm u l t i p l y i n ga n dm o v i n g a i m i n ga tc a l v ee x t r a c t i o no fd i g i t a li m a g e ，a r t i f i c i a lb a c i l l im o d e li sb u i l tb a s e do n r e a lb a c i l l u sa n da r t i f i c i a ll i f et h e o r y , i nw h i c ht h e r ei sa ni m p o r t a n tt h o u g h tt h a t i n d i v i d u a ll i v i n gr u l ei ss i m p l e ，l o c a l - o r i e n t e da n dd i s o r d e r , b u tt h ep h e n o m e n o no f c o l o n ym u l t i p l y i n gi sc o m p l e x ，g l o b a l - o r i e n t e da n do r d e r e d t h e a r t i f i c i a lb a c i l l i m o d e lp r o p o s e di nt h i sp a p e rr e f l e c t st h eb i o l o g i c a lw o r l d sc h a r a c t e r i s t i c ss u c ha s p a r a l l e l i s m a d a p t i v e n e s s 。r o b u s t n e s sa n ds oo n f u r t h e rm o r e ，t h i sm o d e lp o s s e s s e s t h ef u n c t i o no f e x t r a c t i n gc u r v e sf r o md i g i t a li m a g es u c c e s s f u l l y k e y w o r d s ：a r t i f i c i a lb a c i l l i ，a r t i f i c i a ll i f e ，b o u n d a r ye x t r a c t i o n ，i m a g e p r o c e s s i n g 2 第一章绪论 1 1引言 第一章绪论 众所周知，人们从外界环境获取的信息中，7 0 来自于眼睛摄取的图像。当 人们的眼睛从自己周围的环境获取大量信息，并传入大脑后，由大脑根据知识或 经验，对信息进行加工、推理等处理工作，最后识别、理解周围环境，包括环境 内的对象物体。从“信息论”的角度看，“图像”所包含的信息量最大，不仅有 灰度、还有色彩，不仅有平面、还有立体等，其内容极为广泛。这样的一系列特 点，使得对于用于信息处理的计算机系统来说，图像处理无疑是一个充满吸引力 和挑战的领域。 图像处理技术始于二：十世纪五十年代。1 9 6 4 年美国喷射推进实验室( j p l ) 使用计算机对太空船送回的大批月球照片处理后得到了清晰逼真的图像，这足这 门技术发展的重要里程碑，此后，图像处理技术在空间研究方面得到了广泛的应 用。二十世纪七十年代初，由于大量的研究和应用，数字图像处理已经具有自己 的技术特点，并形成了比较完善的学科体系，从而成为一门独立的新学科。从二 f 世纪八十年代中期到二十世纪末期，图像处理与识别技术作为一门跨学科的前 沿高科技技术，取得了突飞猛进的发展，现在已经广泛的应用在生物医学、工业 自动化、文件处理、机器人视觉、遥感、军事、地质、气象、银行、公安、交通、 电子商务等多个领域。 图像处理就是把在空间上离散的、在幅度上量化分层的数字图像，经过一些 特定数理模式的加工处理，以达到有利于人眼视觉或者某种接受系统所需要的图 像的过程。它主要包括图像滤波、图像增强、图像分割、特征提取、图像描述、 图像识别等等。其中图像分割是图像处理中的关键技术之一。图像分割是把数字 图像划分为若干个有意义的区域的处理技术。划分这些有意义的区域町以根据物 体的边缘，或者根据物体分布的区域等等。图像分割是进一步进行图像识别、分 析和理解的基础。因此，多年来该学术领域已经积累了大量系统、科学、实用的 算法和研究成果，并广泛应用于多个领域。但是，因为图像分割的本质是面向数 字图像的象素空间和灰度分布的分类，缺乏面向高层视觉分析和理解的处理能 力；并且分割后的图像质量评价受人的主观因素影响较大，难以建立精确的分割 质量评价标准。所以，在面对数字图像复杂的目标物体形状、三维空间位置、颜 色、纹理、以及人的视觉心理等等方面的因素，图像分割仍是图像处理中最困难 的问题之一，需要科研人员继续创立和发展新的算法和解决方式。 第一章绪论 人工生命的研究是人类千年来探究生命本质的自然延续。 1 9 5 2 年，阿兰图灵( a l a nt u r i n g ) 发表了一篇蕴意深刻的论形态发牛( 生物学 形态发育) 的数学论文【l 】，不仅奠定了生物形态发生的化学理论基础，而且也 为人工模拟生命提供了生物形态方面的理论依据。二十世纪四、五十年代，冯 诺伊曼0 0 h nv o nn e u m a n n ) n 试图从另一角度揭示生命的本质。他试图描述生物 自我繁殖的逻辑形式，致力于研究通过人工的方法实现机器自我繁殖的逻辑，并 提出了细胞自动机模型【2 】。这些努力可以看作是人工生命撮早的思想萌芽。这 些思想虽然对人：l 生命研究的意义重大，但由于当时的计算机速度的限制，并没 有立刻引起人们的关注。 - f 世纪七、八十年代，康韦o o h nc o n w a y ) 开发的“生命游戏”和沃弗拉姆 ( s t e p h e nw o l 丘a m ) 关于细胞自动机行为的分类等研究成果促进了人工生命这个学 科的诞生【3 】。兰顿( l a n g t o n ) 在前人的研究基础之上，对细胞自动机进行了更加深 入的研究，茸次提出了人工生命的概念 4 】。 1 9 8 7 年，兰顿在美国的圣塔菲研究所( s a n t af ei n s t i t u t e ) 筹备并主持了一个关 于生命系统合成与模拟的跨学科研讨会，在这次会议上，兰顿发表了一篇题为“人 工，扛命”的开拓性论文，并讨论了人工生命作为一门新兴的研究领域或学科存在 的意义。这次会议被认为是第一次国际人工生命会议，标志着人工生命这个学科 的创立。到日前为止，人工生命学术界举办了9 次里程碑式的国际学术会议，每 次会议都有一些重要的研究成果。 人工生命的独立研究领域的地位已被国际学术界所承认。在1 9 9 4 年创干0 并在 世界著名学府麻省理工学院出版的国际刊物人工生命( a r t i f i e i f l “f c ) ，是该 研究领域内的权威刊物。国际上有很多大学和研究机构都设立了人工生命研究 室。其中，人工生命科学的坚定支持者，就职于洛斯阿拉莫斯非线性研究中心的 多伊恩法默在题为人工生命：即将来临的进化的演讲i | 曾这样说道：“随 着人工生命的出现，我们也许会成为第一个能够创造我们自已后代的生物”，“当 未来具有意识的生命回顾这个时代时，我们最瞩目的成就很可能小在于我们本 身，而在于我们创造的生命。人工生命是我们人类潜在的最美好的创造”。 1 2研究工作内容和创新点 本人经过阅读大量相关资料、实际编程实现等过程，实现了将人工生命理论 用于图像处理中的图像边缘提取问题的模型杆菌模型。该模型是具有自主计 算特点的多代理系统，每个生命个体具有简单的生存规则，在作为生存环境的图 像上进行繁衍，一段时问后整个生命群落将会涌现出图像的特征。整个系统具有 4 第一章绪论 并行的、白适应的、面向目标等等特征。 在研究人工杆菌模型的过程中，参阅了大量关于人工生命的思想和方法的论 文后，形成了一些自己的想法，也作了一些原创性的研究，具体为以下几点。 1 2 1 提出生命本质的三层金字塔模型 从人工生命发展的历史开始，以解答“生命的本质是什么”的问题入手，在 前人从生物学、逻辑学、系统动力学等等角度解读生命问题的研究成果上，提出 了生命架构的三层金字塔模型( 详见第i 章) 。金字塔模型的最底层就是“物质 和能量”，这是生命存在的基础，是发生一切物理和化学变化的基础。中间层是 “形态和信息”，这是生命区别于非生命形式的主要本质，是发牛一切物理变化 和化学变化的层面。最顶层是“行为和目标”，它是能量和信息通过生命体这个 媒介必然表现出来的特征，是生命表现出适应性和智能的层面。 对应于这个金字塔模型，还设计了广义的人工生命模型架构( 详见第三章) ， 以“实体”和“交互”为两要素，分别对应金字塔的底层和中间层，最后观察到 的生命现象即为最高层的智能行为。 1 2 2 针对提取图像边缘问题的人工生命 在研究了b o i d s 等人工生命模型后，深刻理解其中体现的群体智慧( s w a r m i n t e l l i g e n c e ) 的思想，即：“个体的行为简单、局部并且带有随机性，但是整体的 行为连贯、协调并且不盲目”。在这种思想的指导下，针对图像处理领域的图像 边缘提取问题，参考了多种真实的生命形式，比如草履虫、水绵、杆菌等，最终 设计并实现了人工杆菌模型，对于提取图像中的边缘有较好的效果，这在很多图 像处理的方法中还是首次出现。 1 2 3 有形状的人工生命个体组成的群落 在人：i ：生命方法中，首次使用有形状的人工生命群落模型用于图像处理的问 题。已有的处理图像的人工生命模型，大多数是点状的生命个体，即只关注生命 个体的存在和分布，通常对应一个象素点：或者也有一些有形状的人工生命模型， 但是通常是单个体的演化，类似一个变形虫，逐渐勾勒出图像的边缘信息等等。 本模型中使用具有短杆形状的生命个体组成的群落，在图像处理领域还是很罕见 第一章绪论 的。并且短杆形状对于描述和表达图象边界或者曲线，具有可预见优势的便利性。 1 2 4 提取带精准方向信息的边缘 较好的解决了图像边缘提取问题中比较困难的曲线方向提取问题和减少冗余 的问题。边缘的确定除了灰度的突变，还很重要的是曲线的“走向”，它体现在 象素点的方向信息。传统的边缘检测算子难以得到边缘象素的方向信息，或者只 是根据局部邻域的梯度等等，边缘上相邻两点的梯度也可能差别较大。由于杆菌 个体具有方向角度，所以人工杆菌模型可以得到方向信息，而且方向是经过多次 迭代后的统计信息，比较精准。 1 3论文结构 本论文分为五章。 第一章是绪论部分，简要介绍了边缘提取和人工生命的概念、历史发展以及 应用领域。介绍了本人课题的创新点。 第二章是相关算法的介绍，包括边缘分割的常用算法、人二l ：生命的经典模型 等等，这些算法和模型是设计人工杆菌模型的基础以及对照。简要介绍了目前已 有的将人1 ：生命方法用于图像处理的模型，说明了这一领域的吸引力以及实用 性。 第三章详细介绍了人工杆菌模型的设计思想、模型细节等等，是本文内容中 自己所做的重要研究工作。 第四章是将人工杆菌模型用于边缘提取的实验设计与实现。简要说明了程序 结构。对实验过程和结果作了一定的分析和比较。 第五章是结论和展望部分，对于模型特点做了简短的总结，并且对于模型改 进的方向和问题发表了一些看法。 第二章边缘检测方法和人工生命模型简介 第二章边缘检测方法和人工生命模型简介 2 1 图像边缘分割 图像分割就是把图像分成若干个有意义的区域的处理技术。它的目的是将人 们对图像中感兴趣的部分或者目标从图像中提取出来作进步的分析应用。图像 分割的通用定义如下： 将- - n 离散图像信号f ( m ，n ) ( 其中0 - - m = m 1 并且0 - - n t 时，则( i j ) 为阶跃状边缘点。 2 1 2 2常用的一阶差分模板卷积算法s o b e l 算子 梯度算子在实际应用中常改进为f 邻域模板卷积来近似计算，针对x 方向和 y 方向各用一个模板。根据模板的大小和其中的系数不同，同前已经有了很多不 同的算子，比如r o b e r t 算子、p r e w i t t 算- 了、s o b e l 算子等等。这里相对洋细的介 绍s o b e l 算予，其他方法的思想与之相似。 s o b e l 算了足实际应用中效果比较好的边缘算子。由于差分算了的抗干扰性很 差，噪音会使得使用差分算子的时候在噪音边缘产生冲击，s o b e l 算子通过先求 加权平均然后再求差分的方法来增强抑制噪音干扰的能力： = 矿( f 一1 ，i ，+ 1 ) + 2 f ( i , y + 1 ) + f ( i + l ，+ 1 ) 卜 ，( f l ，一1 ) + 2 ( i , j 一1 ) + ，a + l ，一1 ) = 厂“一1 ，一1 ) + 2 f ( i 一1 , j ) + f ( i 一1 ，j + 1 ) 卜l ，i f + 1 ，j 一1 ) + 2 f ( i + 1 力+ ，o + 1 ，j + 1 ) 】 卜述的s o b e l 算子不是各向同性的，研不同方向的梯度幅值不一样，因此通 常使用改进的各向同性的s o b e l 算子，其加权系数不是2 而是2 。下图( 图2 - 3 ) 为s o b e l 算子的卷积模板( 图2 - 3 中( a ) 和( b ) ) ，以及各向同性的s o b e l 算子卷积模板 ( 图2 3 中( c ) 和( d ) ) 。 1o1 202 10 1 121 000 121 一l01 撕0压 101 1压1 0o0 1撕 一1 ( a )( b )( c )( d ) 图2 - 3s o b e l 算子卷积模板与备向同性s o b e l 算：f 的卷秘模板 2 1 2 3 基于二阶差分的方法l a p l a c i a n 算子 由图2 - 2 可以看到，二阶导数运算也可以用来获取边缘信息，常用的是拉普 抟斯( l a p l a c i a n ) 算子，定义如f ： v 2 脚，= 智+ 智 第一二章边缘检测方法和人工生命模型简介 差分形式为：v 2 ，( f ，- ，) = 【，( “，v ) 一f ( m ，一) 】 “，v ) e s 其巾s 可以足f ( 巧) 为中心的，上下左右4 邻域点的集合，如图2 - 4 ( a ) ，也可以是 8 邻域点的集合，如图2 - 4 ( b ) ，或者是对角线4 邻点的集合，如图2 - 4 ( c ) 。 甘口嚣 ( a )c o )( c ) 图2 - 4 拉普拉斯算子的差分集合种类 拉普拉斯算子是一个标量，它没有边缘方向的信息，对噪音非常敏感，具有 旋转不变性即各项同性的性质，证明如下： 假定坐标( x ，y ) ，经过坐标旋转后的坐标为( x 。，y 。) ， 一o f ：望堡+ 笪望一o f s i n o + 堑c o s 0印反砂。砂砂 舐 钞 一a f ：望皇+ 翌里一a f c o s o + o f - s i n 0 舐 缸础却砂 舐 砂 j | 1 0 有：x = 工c o s ，一j ，。- s i n 目 与 y = x s i n 0 一y 。c o s 0 一出争善并不是各向艘( 黔= ( 等 2 + 鼢 出卵 imjl 加jia r il 刁vj 因此证明拉普拉斯算予是各向同性的。 由于拉普拉斯算子没有边缘方向的信息，并且对噪旨非常敏感，因此实际应 用中往往不直接用来获取边缘，而是先同做图像滤波后再使用拉普拉斯算了，这 种方法就是拉普拉斯高斯( l a p l a c i a n o f g a u s s i a n ) 算子，此处不做过多介绍。 2 1 2 4 局部边缘连接 经过边缘算子得到边缘图像后；往往还需要把检测出来的边缘进行连接或者 分组形成有意义的特征，比如直线、曲线或者物体轮廓等。一般来说，由边缘信 息最终形成线特征需要两个过程：首先是边缘的抽取过程，需要把能够代表真实 边缘的边缘信息抽取出来；其次就足将滤出的边缘连接成曲线或者轮廓线。h 前 连接方法也比较多，常使用的是根据连接点附近各点信息的局部连接方法。 人多数的边缘检测算于在一个边缘点获取边缘强度e ( x ，y ) 的同时，还得到了 这个边缘点的局部方向信息o ( x ，y ) 。在这里介绍的边缘连接方法般从任意一个 第二章边缘检测方法和人t 生命模型简介 满足局部门限的边缘点开始，考虑它的邻接点，选择满足规则限制的点，规则一 般定义如：i e ( x ，y ，) 一e ( x o ，y o ) l s t r e n g t h t h r e s h o l d o ( x 。，y ，) 一o ( x o ，y o ) l d i r e c t i o n t h r e s h o l d 如果邻接点满足规则，就把该点归入到边缘点集合中，接着考虑该点的邻接 点，如此循环；如果该点不满足规则，那么表示已经找到了边缘的端点，则需要 重新寻找个满足局部门限的点开始上述连接，直到没有町以开始的点为止。在 c a n n y 算子算法中的边缘连接部分就是这种方法的改进。 边缘连接的方法很多，也很值得研究，更为理想的方法是采用启发式连接或 者其他应用更多先验知识的连接方法，这样才能取得更满意的结果。 2 1 3 使用全局技术的边缘检测 使用全局技术的边缘检测方法不拘泥于象素点的局部邻域内的信息，而是从 完全不同的角度，采用先验知识的指导，从全局意义上检测图像上的边界线或者 说轮廓线。比起局部边缘检测技术，它们显得更具有启发性，也完全避免了局部 检测中不连续、需要连接的难题，同时显示了更为强劲的抗噪音能力。并且在检 测出边界线的同时，全局边缘检测方法往往也得到了图像上边界线的描述或者称 为表示方法，这对于后续的图像处理更为便利，也是局部边缘检测方法需要花费 更多精力的另一个问题。 2 1 3 1 霍夫( h o u g h ) 变换 霍夫变换可以用来检测图像中的直线、圆、曲线等形状的，可以近似表示为 显示的函数方程的线条。对于边缘检测算子检测出来的边缘信息，往往有断线或 者缝隙，一般的连接方法很难解决这种问题，而霍夫变换则受其影响相当小，具 有良好的抗噪性。这是因为霍夫变换是对参数空间进行处理，并且是在参数空间 的一种统计意义上的结果。这里仅介绍霍夫变换检测直线的过程。 令图像空i 口jx y 中被检测的直线的方程为：y = k 】( + c ，考察其中点( x ，y ) ； 则这一点( x ，y ) 在参数空间k c 中的参数方程为：c = - x k + y ，表示为一条直线。 图像空间x _ y 中直线l 上两点p l ( x 1 , y i ) 和p z ( x 2 ，y 2 ) 满足： y - 27 + 。 y 22 肛2 十。 映射到参数空间分别为两条直线： 。2 一x - k ，+ y l c = 一x 2 疗十y 2 这两条直线交于点p ，p 的坐标是：p ( 笠二丛，y l x 2 - y 2 x i _ ) x 2 一而x 2 一x l 第二章边缘检测方法和人i ：生命模型简介 交点p 的含义是直线，在图像空间x - y 中的斜率和截距，也就是说，在图像空间 x y 中共线的点将映射成为参数空间k c 中交于一个同定点的寅线簇，这个固定 的交点在参数空间k c 中的坐标就对应着在图像空问x y 巾的1 条确定的直线 的斜率和截距。这就是霍夫变换的主要思想，如图2 5 所示。 ( a ) 图像卒闭x - y 叶| 共线的两点p l 和p 2 。( b ) 参数窄l 司k - c 中变与一点p 的两条直线 图2 - 5 h o u g h 变换的图像空间和参数空问 霍夫变换的实现中，常把参数空间设计成一个累加器阵列，表述离散的参数 值。依照变换方法，图像中的每一个点在参数空间中对应的条直线的所有点上 累加一次，最后累加器阵列的峰值就是表征，4 条直线的参数。具体如下： 1 适当地量化参数空间； 2 假定参数空间的每个单元是个累加器，初始化为零： 3 对图像空间中的每一点p ，在其参数方程对应的直线上的累加器上加一； 4 累加器阵列的最大值对应模型的参数。 需要指出，参数空间曲线的形状取决于用于表示曲线的的原始函数。实际应 用中，常常使用直线的极坐标形式，而不是显示表示，这样可以避免直线足垂直 线是带来的问题。 。 霍大变换只能检测具有严格的几何规则或者说具有显示的函数方程的曲线。 分析霍夫变换的实现方法，我们发现参数空间的离散范围和精度如何确定也是比 较困难的问题；另外，如果曲线的参数个数比较多，离散精度比较高，那么参数 空问会非常大，因为要针对图像空间中的每个点进行参数转换和计算，则运算量 和存储空间都很火；并且霍夫变换检测直线时必能得到直线的方程，直线的起点 和终点信息无法得到等等。这些都是研究人员感兴趣的问题。 2 1 3 2 “蛇”( s n a k e ) 模型 “蛇”模型是动态轮廓线模型( a c t i v ec o n t o u rm o d e l ，a c m ) 的常用名称。该模 型最早由k a s s 、w i t k i n 和t e r z o p o p u l o s 等人于1 9 8 8 年提出，称为传统s n a k e 模 型。此后该模型得到了极大的发展，被广泛应用于计算机视觉的许多领域，如边 第一二章边缘检测方法和人t 生命模型简介 缘提取、图像分割、3 d 重建、医学图像处理等等方面。 由于蛇模型是基于一条连续并且闭合的曲线的演化从而达到图像分割目的 的，医此得虱的分割边缘是闭合的，不需要另外进行边缘连接的过程。蛇模型是 通过最小化一个能量函数来驱动轮廓曲线趋向图像| | 】的物体边缘，这个能量函数 由图像特征和轮廓线属性共同决定。因此蛇模型叮称得上是一种高层图像分割算 法，它小同传统的底层分割算法，它具有全局搜索的特征。 定义一条参数曲线c ( s ，t ) = 【x ( s ，t ) ，y ( s ，t ) 】，其中，5 【0 , 1 】为归化参数，s n a k e 模型可以表示为该曲线到图像平面的映射。设待分割的图像为i ( x ，y ) ，根据轮廓 进化理论，s n a k e 在整个图像平面q 上进化，以最小化能量函数： j ( c ) = i ( e 0 。m ( c ) + e “( c ) ) d s 矗 能量函数包括内部能量e i 。悖m “和外部能量e 口【”兀l a l 两个部分。其中高层形状信息由 内部能量控制，外部能量则表征图像低层次信息，通常是边缘信息等等。 内部能量函数 内部能量e i n 。_ 通过调节参数控制轮廓线的弹性能e 。i a s l i 。和弯曲能e b e n 曲。， e m e m m = e e l 喊。c + e 沁俯z e 。= j 1 口。) l c + ( s ) f 2 毛。咖= 圭舯) 陬s ) 1 2 其中、b 为人工设定的控制参数，这两个参数控制着轮廓线的平滑性和连续 性。c ( s ) 为c ( s ) 的一阶导数，c ”( s ) 为c ( s ) 的二阶导数。在离散情况下，分别对麻 一阶差分和二阶差分。 e c 雠i 。控制轮廓的 “应力”，在点数不变的 情况下减小该项意味着 参数曲线的不断收缩，反 之则对应曲线的膨胀。从 这个意义上来讲叮以将 轮廓线理解为一根橡皮 筋。e b c n d i n g 反映了个点曲 率的大小，减小该项则曲 线膨胀，曲率减小：增大 该项则越线收缩，曲塞增 ， ， ， ， ， ， ( a ) 弹性e l a s t i c( b ) 弯曲b e n d i n g 图2 - 6 蛇模型的内部能量两部分 大。控制参数可以控制曲线的平滑性，可以平衡这两项的比重，使得s n a k e 曲线 1 4 第一二章边缘检测方法和人工生命模型简介 在满足能量最小化原则的基础上，其形状达到稳定状态，并日正确分割出图像中 感兴趣的目标。 外部能量函数 外部能量e 。a l 是定义在整个图像i ( x ，y ) 上的标量函数，它反映了图像的某 些特征比如边缘等等。最简单的外部能量函数为： j 0 ，。，“( x ，y ) = 叫v ，( 工，y ) l 于外部能量函数的定义是对图像的梯度取反，因此图像的边缘点的外部能 量最小，故对十一幅给定的图像，最小化外部能量函数e 。呵以驱动轮廓线被 吸引到目标边缘上。 ( a ) 图像( b ) 外部能量( c ) 局部放人 图2 7 蛇模型的外部能量图示 常用的外部能量函数为：e 。m = - v ( g ，( x ，y ) ，( 墨y ) ) 1 2 其【 ，g 。( x ，y ) 是均值为0 ，方差为a 的二维高斯函数，v 为梯度算子，+ 表示卷积 运算。采用二维高斯函数对图像卷积达到去噪的目的。 2 1 4 边缘提取问题及常用方法小结 曲线抽取( c u r v ee x t r a c t i o n ) 足指对数字图像中的边缘( e d g e ) 或者边界( b o u n d a r y ) 进行检测( d e t e c t i o n ) 和描述( r e p r e s e n t a t i o n ) 。它是计算机视觉中最基本也是最关键 的问题之一。曲线抽取对图像处理的其他方面例如图像分割、纹理分析、物体模 式识别等有重要的意义。曲线是多种机制综合作用的结果，比如表面连续性 ( s u r f a c ed i s c o n t i n u i t i e s ) 、纹t 里( t e x t u r e ) 、亮度( 1 i g h t i n g ) 、封闭性( o c c l u s i o n ) 以及噪 音( n o i s e ) 等等，是计算机视觉领域的个熏要挑战，四、五十年来引起国内外广 泛的关注和研究。 ；_d：1， -，lt；： l i：-it 豫囊萋箩。 誉妻誊。梦“篱莲辱罐学 9 第一章 边缘检测方法和人t 生命模犁简介 传统常用的曲线抽取方法足面向局部信息的，包含两个步骤。首先是运 用基于图像微分的极值和过零点的边缘检测算予【1 6 来标注曲线卜的点。然后再 运用边缘连接的算法对这些点处理后连接成曲线。其中使用各种不同的边缘检测 算予就足对标量图像用各种不同的模板( m a s k ) 进行卷积，它们的差别仅在- 丁 模板 ( m a s k ) 的阶数不同和配置不同。这些方法的主要优点是简单易用，效果真观。但 是它只关注了图像中m a s k 覆盖的细节信息，受噪音影响很大，不能从今局把握； 如果增大m a s k 的大小，将会迅速的提高计算时问和降低对局部特征的敏感性。 处理全局和局部信息的能力互为消长，如何找到平衡点也是曲线抽取未能很好解 决的问题。 面向全局信息的边界检测方法也有很多。例如，霍夫变换( h o u g ht r a n s f o r a o 【7 ，8 就是种基于物体边界形状建立严格几何变换的检测策略。使用一种合适的 几何变换，使检测的曲线与模板进行匹配。它对于噪音的封闭性有很好的健壮性， 被1 1 泛应用；但是它的性能强烈的依赖于形状的不变性而且很难适应普遍的变 化。“蛇”( s n a k e ) 9 - “】模型是找到一个由轮廓弹性定义的内力以及物体边界刚性 限制定义的外力构成的能量函数，使得能量函数达到最小的检测策略。但是它处 理凹陷曲线和开放曲线时力不从心，它的收敛强烈依赖于初始值的设置，并且容 易陷入局部极小。 近些年来不少学者和研究人员在图像处理领域不断引入和使用新的理论和方 法，诸如模糊集合理论、数学形态理论以及神经网络方法等，使得图像分析方面 有了新的发展并取得了比传统方法更好的效果。但是，尽管新的分割方法层出不 穷，到目前为止，仍无通用的图像分割算法和理论，需要我们继续研究，改进现 有算法，并且提出更好的、更新的分割方法。 2 2 经典人工生命思想和模型 2 2 1 人工生命的基本思想 在引言中已经简要介绍了人工生命萌芽、建立、发展的过程。其中讲到1 9 8 7 年，兰顿在荚国的圣塔菲研究所( s a n t a f e i n s t i t u t e ) 筹备并手持了第一次国际人：t = 生命会议。会议得到了广泛的反响，1 5 0 多名来自世界各地从事相关研究的学者、 科学记者参加了会议。这次会议的成功召开标志着人工生命这个崭新的研究领域 的j f 式诞生。提交的会议论文经过严格的同行评议，以人工生命为题出版。 兰顿把参加人工生命研讨会的人们的思想提炼成该书的前言和长达4 7 负的概论 1 6 第一二章边缘检铡方法和人f 生命模型简介 【5 】，在这些文字中，他为人工生命的丰要思想撰写了一份清晰的宣言，主要思想 如下： ( 1 1 人工生命所月的研究方法是集成的方法。人工生命不是用分析的方法， 即不是用分析解剖现有生命的物种、牛物体、器官、细胞、细胞器的方法来理解 生命，而是用综合集成的方法，即在人工系统中将简啦的零部件组合在一起使之 产生似牛命的行为的方法来研究生命。传统的生物学研究直强调根据生命的最 小部分分析生命并解释占们，而人工生命研究试图在计算机或其它媒介中合成似 牛命的过程和行为。 ( 2 ) 人工生命是关于一切可能生命形式的生物学。人工生命并不特别关心我 们知道的地球上的特殊的以水和碳为基础的生命，这种生命是“如吾所识的生 命”( 1 i f e a s w e k n o w i t l ，是传统的生物学的主题。人l ：生命研究的则是“如其所能 的生命 ( 1 i f e - a s i t - e o u l d 。b e ) 。因为生物学仅仅是建立在一种实例，即地球上的生命 的基础卜- 的，因此它在经验上太受限制而无助于创立真正普遍的理论。这里，一 种新的思路就是人：l ：生命。我们像我们这样出现，并不是必然的，这仪仅是因为 原先地球上存在的那些物质和进化的结果。然而，进化可能建立在更普遍的规律 之上，但这些规律我们可能还没有认识到。所以，今天的生物学仅仅是实际生命 的生物学。我们只有在“生命如乓所能”的广泛内容中考察“生命如吾所识”，才会 真正理解牛物的本质。因此，生物学必须成为任何可能生命形式的生物学。 0 ) 牛命的本质在于形式而不在于具体的物质。不管实际的生命还是可能的 生命都不由它们所构成的具体物质决定。生命当然离不开物质，但是生命的本质 并不在于具体的物质。生命是一个过程，恰恰是这一过程的形式而不是物质，4 是 生命的本质。人们因此可以忽略物质，从它当中抽象出控制生命的逻辑。如果我 们能够在另外种物质【 - 获得相同的逻辑。我们就可以创造 不同材料的另外一 种生命。闪此，生命在根本上与具体的媒质无关。 f 4 ) 人工生命中的“人工”是指它的组成部分，即硅片、计算规则等是人- t 的， 但它们的行为并不是人工的。硅片、计算规则等是由人设计和规定的，人工生命 展示的行为则是人工生命自己产生的。 ( 5 ) 白下而上的建构。人 ：生命的合成的实现，最好的方法是通过以计算机 为基础的被称为“自下而上编程”的信息处理原则来进行：在底层定义许多小的单 元和几条关系到占们内部的、完全是局部的相互作用的简单规则，从这种相互作 用中产l ! 出连贯的“全体”行为，这种行为不是根据特殊规则预先编好的。自下而 f ：的编程与人，l ：智能( a i ) 中主导的编程原则是完全不同的。在人工智能中，人 们试图根据从上到下的编程手段建构智力机器：总体的行为是先验地通过把它分 解成严格定义的子序列编程的，子序歹! 依次又被分成子程序、子子程，笋直至! 第一二章边缘检测方法和人i ：生命模型简介 程序自己的机器语言。人工生命中的自下而上的方法则相反，它模仿或模拟自然 中自我组织的过程，力图从简单的局部控制出发，让行为从底层突现出来。按兰 顿的说法，生命也许确实是某种生化机器，但要启动这台机器，不是把生命注入 这台机器，面是将这台机器的各个部分组织起来，让它们产生。巨动，从而使其具 有“生命”。 ( 6 ) 并行处理。经典的计算机信息处理过程是接续发生的，在人工智能中可 以发现类似的个时间单元一个逻辑步骤”的思维：而在人工生命中，信息处理 原则是基于发生在实际生命中的大量并行处理过程的。在实际生命中，大脑的神 经细胞彼此并行工作，不用等待它们的相邻细胞“完成t 作”；在一个鸟群中，是 很多鸟的个体在飞行方向上的小的变化给予乌群动态特征的。 ( 7 ) 突现是人工生命的突出特征。人工生命并不像人们在设计汽车或机器人 那样在平庸的意义上是预先设计好的。人工生命最有趣的例子是展示出“突现”的 行为。“突现”一词用来指称在复杂的( 非线性的) 形态中许多相对简单单元彼此 相互作用时产生出来的引人注目的整体特性。在人工生命中，系统的表现型不能 从它的基因型中推倒出来。这里，基因型是指系统运作的简单规则，比如，康韦 “生命”游戏中的两个规则：表现型是指系统的整体突现行为，比如“滑翔机”在牛 命格子中沿对角线方向往下扭动。用计算机的语言来说，正是自下而上的方法， 允许在上层水平突现出新的不可预言的现象，这种现象对生命系统来说是关键 的。 ( 8 ) 真正“活的”人工生命总有一天会诞生。在兰顿的人工生命“宣言”中，他虽 然非常谨慎地避免宜称人工生命研究人员所研究的实体“真正”是活的，但是，如 果生命真的只是组织问题，那么组织完善的实体，无论它是由什么做的，都应当 是活的。因此，兰顿确信，“真正的”人：r 生命总有一天会诞生，而且会很快地诞 生。 2 2 2b o i d s 模型 1 9 8 6 年c r m gr e y n o l d s 设计了一个具有互相协作的动物行为的计算机模型， 它类似于鸟群或者鱼群，并且称它为b o i d s 。在这个模型中，每个个体的行为只 和它周围邻近个体的行为有关，每个个体只需遵循以下3 条规则，如图( 2 8 ) ： 分离原则( s e p a r a t i o n ) ：与邻近的同伴们相互不能靠得太近，避免局部过 于拥挤。 一致原则( a l i g n m e n t ) ：与邻近的同伴们平均的速率和方向保持致。 聚集原则( c o h e s i o n ) ；尽量向着邻近的同伴们的平均位置运动。 第二章边缘检测方法和人工生命模型简介 ；粤震；攀攀攀_ 爹 瀵鬟 鋈蘩爹j 鬻i 基_ 1 瓣蘩鬻ii 。j 鬻薯誊譬。i i 弩喾= 誊ij 涌鬟漶一誉誊i 雾! 鎏? ( a ) 分离原, l j ( s e p a r a t i o n ) ( b ) 一致原则( a i g n m e n t ) 图2 - 8b o i d s 模型的三条原则 邻域是指以当前b o i d 个体的中心为圆心，d i s t a n c e 为半径；并且以当前的b o i d 个体的方向为基准，顺时针和逆时针各旋转a n g l e 角度的扇形范围，如图( 2 9 ) 所 示。在邻域外的同伴个体的影响被忽略。邻域可以看作是b o i d 个体的感应范围。 鸟群中的每只鸟在初始状态下是处于随机位置向各个随机方向飞行的，但是 随着时间的推移，这些初始处于随机状态的鸟通过自组织( s e l f - o r g a n i z a t i o n ) 逐步 聚集成一个个小的群落，并且以相同速度朝着相同方向飞行，然后几个小的群落 又聚集成大的群落，大的群落可能又分散为一个个小的群落。这些行为和现实中 的鸟类飞行的特性是一致的。甚至在躲避障碍物的实验中，b o i d 群体要飞过具有 静态障碍物的仿真环境时，它们也很聪明的绕过了障碍物，并且重又保持聚集城 群落的状态，如图f 2 1 0 ) 。 我们可以看出鸟群的同步飞行这个整体的行为只是建立在每只鸟对周围的局 部感知上面，而且并不存在一个集中的控制者。也就是说整个群体组织起来但却 没有一个组织者，群体之间相互协调却没有一个协调者( o r g a n i z e dw i t h o u t a n o r g a n i z e r ，c o o r d i n a t e dw i t h o u tac o o r d i n a t o r ) ，这和前面我们对这些系统的整体感 觉是一致的。 图2 - 9 一个b o i d 的邻域图2 1 0b o i d 群落躲避圆柱状的障碍物 1 9 第二章边缘检测方法和人工生命模型简介 2 2 3 s w a r m 系统和s w a r m 模型 九十年代初期，兰顿( c h r i s t o p h e rl a n g t o n ) 在圣塔菲研究所( s a n t af ei n s t i t u t e ) 主持研究并发布了一个可交互的多代理系统( m u l t i p l ei n t e r a c t i n ga g e n t ss y s t e m ) 的软件环境，称之为s w a r m 系统。该系统的基本组成部分就是s w a r m 的理论模 型。这个s w a r m 模型包括了个由多个代理个体( a g e n t ) 组成的集合，以及一组时 间序列卜的事件( e v e n t ) 的集合；每个代理个体也可以设计成一个嵌套式的s w a n n 模型。该模型的思想就是让一系列独立的a g e n t 通过独立事件进行交互，帮助研 究由多个体组成的复杂适应系统的行为。 s w a r m 系统是一个面向对象的，基于可重用组件的，能够显示、交互、分析 和控制的实验环境。它模拟了生物系统，并h 提供了讨论模拟技术和方法论的焦 点，还提供在特定的研究团体中共享模型组件和库，建立个用于模型定义的形 式化框架。s w a r m 系统就是一个高效率的可信的可重用的软件实验仪器，它给予 科学家们一个标准的软件工具集和研究开发平台。由于s w a r m 没有对模型和模 型要素之间的交互作任何约束，所以s w a r m 可以模拟任何物理系统、经济系统 或社会系统。事实上在各个广泛的研究领域都有人在用s w a r m 编写程序，这些 领域包括生物学、经济学、物理学、化学和生态学等。 s w a r m 模型有两个主要的组成部分：一个是代理个体( a g e n t ) 的集合；另 个足这些个体的行为事件( b e h a v i o re v e n t ) 集合。每个个体受行为事件的驱动而产 生自己的行为。对于个体集合来说，它们的行为是并行的；对于单个个体来说， 它的行为事件是串行的。 代理个体( a g e n t ) s w a r m 模型中的个体就象系统中的一个生命，是能够产生动作并影响自 身和其他个体的一个实体。有时候模型包括几组交匾的个体。例如，在 一个经济学模拟中，个体可能是公司、证券代理人、分红利者和中央银 行。 行为事件( b e h a v i o re v e n t ) 除了个体的集合，模型“s w a r m ”还包括模型中行为的时间表。时间表定义 了每个个体的独立事件发生的流程，即各事件的执行顺序。通过确定合 理的时间调度机制，叮以在没有并行环境的状况下也能进行研究工作， 也就是说，在并行系统下a g e n t 之问复杂的消息传送机制在该s w a r f n 中通 过行为表的方式可以在单机环境下实现。例如，在狼兔子这个模拟系 统中能有三种行为