基于人工生命的图像分割技术的研究及应用
摘要
图像分割是图像分析、识别和理解的基础。图像分割主要是指将图像分成各具特性的区域并提取出感兴趣的区域的技术，其研究多年来一直受到人们的高度重视。由于待分割图像的可变性比较大，且混有噪声，构成了图像分割所面临的主要困难。到目前虽然已经有了许多各种类型的分割算法，但是这些方法普遍存在问题和缺陷，影响了性能和应用，因此需要继续探索新的途径，对图像分割继续深入下去。
人工生命是一个新兴起的多学科交叉的研究领域，已经在解决现实世界中的许多复杂问题上显示了潜在的应用前景。在图像分割的研究中引入人工生命的思想，将具有广阔的研究空间和良好的应用前景，将有希望发现新颖的更优良的分割方法。
本文分别就单一的静态图像和图像视频序列提出了两个人工生命模型，基于细胞自动机的人工生命模型和基于多粒度的人工生命模型。在第一种模型中我们将待分割图像看作人工生命智能体的生存环境，通过生存在其上的人工生命智能体模型一代代繁衍、扩张来最终得到图像的分割结果。
在根据视频图像序列中图像的特征提出的基于多粒度的人工生命改进模型里是将视频图像序列看作是生命体的生存环境，不同的视频帧视为环境的变化。生命体个体体积的大小也不再仅仅局限在像素
级上，而是同时考虑了由小的生命个体聚集而成的更大规模的生命群落及群落之间的交互。生命体通过环境的变化获得能量才能够生存，它们能感觉到周围的变化并向着变化的方向不断扩张。每个智能体在规则的作用下自主选择自身的行为。该模型具有自底向上的，非全局受控等特点。通过生命个体和群体的繁衍，死亡，扩张，迁移等行为，使的前景图像被最终被分割出来。实验表明，该方法不仅具有很好的性能而且具有较好的应用潜力。
关键词：图像分割，人工生命，生命体，生存环境，目标提取THE RESEARCH AND REALIZATION OF IMAGE
SEGMENTATION BASED ON ARTIFICIAL LIFE
Abstract
Image segmentation is the base of image analysis, image recognition and the image understanding. Image segmentation is a technique which divides an image into some special areas and gets interesting areas. Many researchers have been working on it for a long time. Main difficulties or obstacles to image segmentation are the changing of image and the noise. So far there have been many image segmentation algorithms, however, each of them has its own problems that impact the algorithm’s performance and application. So we need to get more new methods and makes an intensive study of it.
Artificial Life is a new research area which is transdisciplinary. It shows its potential superiority on solving complex problems. If we apply
the artificial life to the image segmentation, there would be more extensive research space and good application prospects. And maybe we will find a lot of novel and much better methods.
This paper puts forward two artificial life modes based on frozen picture and video frequency sequence respectively. The first is an artificial life model based on the Cellular Automata, the other is a ALife mode which has a variety of size. In the first ALife model we take the image as the environment of the agents. Through some living action like propagation, death, expansion, moving and so on we finally get the result of image segmentation.
In the multi-granular ALife model which is extracted according to video feature of video sequence, we also take the image as the environment of agents. It’s not a single image at this time but a serial of images of a video. The difference of the images is the environment changing. Agents can live by getting the changing energy. They can detect the changing nearby and extensive to that direction. And in this model some small agents can aggregate a cluster as a big agent. Both of modes have their rules which every agent must observe. Under the rules each agent can choose its next action. The two models have bottom-up and non-overall control features. Through the results of experiments, we conclude that both models have a good performance and application prospect.
KEY WORDS: image segmentation, artificial life, agent, virtual environment, object extraction
毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作者签名：日期：
指导教师签名：日期：
使用授权说明
本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名：日期：
学位论文原创性声明
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。
作者签名：日期：年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名：日期：年月日
导师签名：日期：年月日
指导教师评阅书
评阅教师评阅书
教研室（或答辩小组）及教学系意见
目录
中文摘要 (1)
ABSTRACT (2)
第一章绪论 (7)
1.1研究的背景和动机 (7)
1.2研究工作内容和创新点 (8)
1.2.1针对静态图像分割提出的基于细胞自动机的人工生命模型 (9)
1.2.2针对视频序列特征提出的基于多粒度的改进的人工生命模型 (9)
1.3论文结构 (9)
第二章图像分割与人工生命 (11)
2.1 图像分割的定义 (11)
2.2 传统图像分割的方法及其局限 (12)
2.2.1 阈值法 (12)
2.2.2 基于区域的图像分割方法 (15)
2.2.3 基于边界的图像分割方法 (16)
2.3 人工生命的产生，发展和现状 (19)
2.3.1 人工生命的产生和发展 (19)
2.3.2 人工生命的研究现状 (20)
2.4 人工生命的研究思想 (21)
2.5 人工生命研究的领域 (22)
2.6 人工生命的应用与发展前景 (24)
2.7 本章小结 (27)
第三章基于细胞自动机的人工生命模型 (28)
3.1 细胞自动机简介 (28)
3.2 人工生命模型的设计思想 (29)
3.3 智能体及其生存环境 (30)
3.4 生存与扩张 (30)
3.4.1 智能体的生存规则 (30)
3.4.1 邻域的定义 (30)
3.5 智能体的繁殖 (31)
3.5.1 繁殖规则 (31)
3.6 实验过程及结果 (32)
3.6.1 分割结果定量评价标准 (32)
3.6.2 定量分析实验过程及结果 (34)
3.6.3 定性分析实验过程及结果 (37)
3.6.4 与其他分割方法比较的结果 (41)
3.7 本章小结 (43)
第四章基于多粒度的改进的人工生命模型 (45)
4.1 改进模型的设计思想 (47)
4.2 生命体及其生存环境 (48)
4.2.1 生存环境 (48)
4.2.2 生命体的划分 (50)
4.2.3 环境变化探测器 (51)
4.3 生存规则及扩张 (51)
4.3.1 生存的规则 (51)
4.3.2 邻域的定义 (51)
4.3.3 繁殖，扩张，死亡的规则 (52)
4.4 实验及结果分析 (52)
4.4.1 仿真环境 (52)
4.4.2 有效性测试 (53)
4.4.3 分割参数对分割效果的影响 (53)
4.4.4 模型对对象的敏感性测试 (56)
4.4.5 与已有算法的比较 (60)
4.4.6 实验小结 (60)
4.5 本章小结 (61)
第五章结论与展望 (62)
参考文献 (64)
攻读硕士学位期间发表的论文及参加的科研项目 (69)
致谢 (70)
第一章绪论
1.1研究的背景和动机
视频监控系统用于对指定的场景区域进行监视，并把场景内的信息传递给监控者，使其能根据相应的情况采取适当措施的系统，监控系统的发展大致经历了三个阶段:模拟视频监控系统;数字视频监控系统;智能视频监控系统。智能视频监控系统融入了视频图像序列理解和计算机视觉的相关知识，国际上对这方面的研究己经达到相当水平，国内则处于起步阶段[1，2，3]。
视频监控系统是多媒体技术、计算机网络、工业控制和人工智能等技术的综合运用，它正向着视频音频的数字化、系统的网络化和管理的智能化方向不断发展[4，5，6]。从视频图像序列中实时分割运动人体目标是一项基本而又重要的环节。运动人体分割的目的是从序列图像中将运动人体的变化区域从背景图像中提取出来,其运动区域的有效分割对于目标分类、跟踪和行为理解等后期处理是非常重要的，如图1-1所示。
图1-1 视频监控图像处理流程图
由于移动视频系统在特定环境下（抖动，光线模糊，相对速度等）得到的图像是不清晰的，从而不能为后继的决策提供可靠的依据，所以需要首先对图像进行分割，将目标与背景分离出来，从而能够得到图像所包含的相对准确的信息。图像分割是图像处理中的关键技术之一。图像分割指将图像分成各具特性的区域并提取出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤；是一种基本的计算机视觉技术。只有在图像分割的基础上才能对目标进行特征提取和参数测量，使得更高层的图像分析和理解成为可能。因此对图像分割方法的研
究具有十分重要的意义。
1.2研究工作内容和创新点
图像分割一直以来都是一个经典难题。从二十世纪七十年代开始就有很多很多研究人员为之付出了巨大的努力，在这几十年的过程中研究人员也不断把其它各个领域的方法论引入和应用到图像分割的领域内，创造了很多经典的图像分割算法比如：基于灰度直方图的方法，区域分割算法，边缘提取，基于数学形态学的方法，基于遗传算法的最优化参数设置的方法等等。但是这些方法都有其局限性，影响了它们的性能和应用。到目前为止，在图像分割领域还不存在一个通用的方法，也不存在一个判断分割是否成功的客观标准。因此，对图像分割需要探索新的途径，考虑引入新的理论，提出新的方法，进行进一步的深入研究。
人工生命是二十世纪八十年代末兴起的一门交叉学科，是计算机科学新的发展方向之一，其研究内容包括：物种进化、遗传算法、自组织、自适应、智能体、生命现象模拟、生物与社会、基因工程、人工化学、生命动力学、人工生命哲学、人工生命方法论、算法、人工智能等有关研究课题。人工生命研究那些“具有自然生命特征和生命现象的人造系统的理论模型生成方法和实现技术”，抽象地提取控制生物现象的基本动态原理，并且通过物理媒介(如计算机)来模拟生命系统动态发展过程。而且人工生命通过对生命世界的模拟不仅更好地理解生命现象，同时也为解决复杂问题提供新的思路和方法。虽然它还是新兴学科，但己在解决复杂问题上显示出很好的前景。过去的十多年，研究人员探索把人工生命应用到计算机图像处理中，开拓了研究思路，带来发现更新颖、更有效的理论和方法的可能性，并且已经在一些方面取得一定的成功。目前，己经有研究人员尝试将人工生命应用到图像分割领域中来，虽然相关的研究还比较少，但是取得的研究成果表明将人工生命引入到图像分割中能够获得有意义的成功。人工生命用于图像分割将有很好的应用潜力和前景，需要进一步深入研究下去。
本人经过阅读大量相关资料、实际编程实现等过程，实现了两个人工生命模型：基于细胞自动机的人工生命模型和多粒度的人工生命模型。这两种模型都是具有自主计算特点的多代理系统，每个生命个体具有简单的生存规则，在作为生存环境的图像序列上不断进行扩张，一段时间后整个生命群落将会自动得到需要
提取的目标物。整个系统具有并行的、自适应的、面向目标等特征。在研究该智能体模型的过程中，参阅了大量关于人工生命的思想和方法的论文后，形成了一些自己的想法，也作了一些原创性的研究，具体为以下几点。
1.2.1针对静态图像分割提出了基于细胞自动机的人工生命模型
在研究了Boids、人工协作细胞等人工生命模型之后，深刻理解了其中体现的群体智慧的思想，即:“个体的行为简单、局部并且带有随机性，但是整体的行为连贯、协调并且不盲目”。在这个思想指导下，提出了用于单一静态图像分割的人工生命模型，在设计该模型的过程中参考了许多真实的有群居行为的生物如蚂蚁、蜜蜂以及最大的群居生物人类等，参照它们的群体协作行为以及对环境变化的适应行为，最终实现了该人工生命模型。
1.2.2针对视频序列的特征提出基于多粒度的改进的人工生命模型
在基于细胞自动机的人工生命模型的基础上，提出了用于对视频图像进行分割的多粒度的人工生命模型。在该模型中，使用了不同粒度的人工生命模型用于图像分割的问题。以往的人工生命模型多是将单一的图像作为生存环境，该模型的生存环境则为视频图像序列。在已有的用于图像处理的人工生命模型中，大多是以像素点作为生命个体，也有人提出了带有形状的生命个体但是关注的一般都是单一粒度的个体与个体之间的交互。本模型中的个体将不再局限于只将像素点作为生命个体而是提出了将更大的具有相同特征的生命群落作为个体，并且交互行为也不再仅仅是发生在像素点这样的小的生命个体之间。通过实验验证，该模型对于提取视频序列的目标有较好的效果。
1.3论文结构
本论文分为五章：
第一章是绪论部分。主要介绍了图像分割的背景和动机，研究的内容和创新点，以及论文的结构。
第二章是图像分割与人工生命的研究背景介绍部分。主要介绍图像分割的基本概念和一些经典的算法，人工生命的发展和现状，相关概念及思想以及这一学科的发展前景和应用的情况。
第三章是作者的基于细胞自动机的人工生命模型介绍部分。主要介绍了作者研究的应用于单一静态图像上的人工生命模型，系统地介绍了模型的各个模块及
算法，并通过实验对人工生命模型分割出的图像做了定量定性的评价，也与其它的传统的方法作了一个比较，论证了基于细胞自动机的人工生命模型在静态图像上的良好的性能，分析了该模型的优点及缺陷。
第四章是根据图像视频序列的图像特征，针对目标提取的图像分割而提出的基于多粒度的改进的人工生命模型，完整的介绍了该算法的设计思想，模型的各个模块等，并通过实验来展示了多粒度人工生命模型用于目标提取的性能优势和发展及应用的潜力，并与其他经典算法的对比实验。
第五章是结论和展望部分，对两个人工生命模型作了简短的总结，并且对于模型的改进的方向和问题发表了一些看法以及对于图像处理领域结合人工生命的方法论的前景做出了展望。
第二章 图像分割与人工生命
2.1 图像分割的定义
图像分割是将整个图像区域分割成若干个互不交叠的非空子区域的过程。每个子区域的内部是连通的，同一区域内部具有相同或相似的特性，这里的特性可以是灰度、颜色、纹理等。连通是指在该区域内任意两个像素之间存在一条完全由这个区域的元素构成的连通路径。有两种可能的选择，如果只依据旁侧相邻的像素（上、下、左、右）来确定连通，叫做四连通；如果再加上45度角方向的像素，则称为八连通的。对于灰度图像来说，区域内部的像素一般具有灰度相似性，而在区域边界上一般具有灰度不连续性。图像分割的数学描述如下：
令集合R 代表整个图像区域，对R 的图像分割可以看作是将R 分成n 个满足如下规则的非空子集：R 1，R 2，…..R n ：
（1）……………………………………………………(2.1)
（2）对于所有的 i 和 j ，,
（3）对于1,2,,()i i n P R TRUE == 有
（4）,()i j i j P R R FALSE ≠= 对于有
（5）1,2,,,i i n R = 对于是连通的区域
P(Ri)=TRUE 指出在分割结果中，每个区域的像素有着相同的特性。P （Ri ∪Rj ）=FALSE 表示在分割结果中，不同的子区域具有不同的特性。（2.1）式表示子区域的并集是整个图像，这一点是保证图像的每个象素都被处理的充分条件
2.2 传统图像分割的方法及其局限
2.2.1 阈值法
阈值法是一种最简单的图像分割方法,是一种最常用的并行区域技术。阈值是用于区分目标和背景的灰度门限。如果图像只有目标和背景两大类,那么只需
选取一个阈值称为单阈值分割，这种方法是将图像中每个像素的灰度值与阈值相比较，灰度值大于阈值的像素为一类，灰度值小于阈值的像素为另一类。如果图像中有多个目标，就需要选取多个阈值将各个目标及背景分开，这种方法称为多阈值分割。阈值T 一般可写成：T = T[ x , y , p ( x , y) , q ( x , y) ]
其中p ( x , y) 代表点( x , y) 处的灰度值, q ( x ,y) 代表该点邻域的某种局部特性。
常用的选取阈值的方法有灰度直方图峰谷法、最大类间方差法（Otsu 法）等等。
灰度直方图峰谷法[7]。若图像的灰度直方图呈双峰状且有明显的谷,选择谷点的灰度值作为阈值就可把目标从背景中分割出来。选取直方图的谷点可借助求曲线极小值的方法，该方法对于目标和背景有很大灰度差异的图像能实现简单而有效的分割。
图2-1 阈值为81时的分割效果图
在众多的阈值选取方法中，Otsu [8]方法被认为是最优方法之一。其基本思想是用阈值把图像像素划分为两类，通过使划分后得到的两类的类间方差最大来确定最佳阈值。设图像f ( x , y) 灰度级范围为G = [ 0 , L -1]，各灰度级出现的概率为Pi ，阈值t 将图像像素分为两类C0 = [0 ，t ]和C1 = [ t + 1 ,L - 1 ]。两类的概率为和。两类的平均灰度为和，其中，。其中准则定义为两类的类间方差： 222200110101()()()()t σωμμωμμωωμμ=-+-=-………………………(2.2) 使取最大值的t ，就是分割目标和背景的最佳阈值T 。
如果图像中含有多个物体，尤其是含有多个灰度值存在差异的物体，显然不
能进行二值化分割。其次，还有许多使用多阈值的阈值化修正方法比如文献[9]利用遗传算法进行多个阈值的选取和文献[10]中提到的基于过渡区域的多阈值分割方法，其处理后的结果图像不再是二值的，而是一个有限的灰度值集合组成的图像。
其中每个是一个指定的灰度集。
图2-3 原始peppers图像
A 二值分割图像
B 三值分割图像
C 四值图像分割
D 五值图像分割
图2-4 Otsu 法应用到多阈值分割的效果图
Otsu 算法不仅适用于选择单阈值，也可用于多阈值的确定[11]。要M-1个阈值{t1,t2……tm -1}…….来将图像分成M 个子集，这些个子集包含的灰度值范围分别为：
[][][][]11212110,,1,,.....,1,,....,1,1i i i M M C t C t t C t t C t L --==+=+=+-
最佳阈值的公式为：
=112110...1{(,,...,)}M B M t t L Arg
Max t t t σ--<<<<-…………………(2.3)
其中，，。
阈值法优点是计算简单，速度快，易于实现。它的缺点是当图像中的目标和背景灰度差异不明显或灰度值范围有重叠时，全局阈值的分割结果不理想，而且这种方法只考虑像素本身的灰度值，一般不考虑空间特征，因而对噪声和灰度不均匀很敏感。
2.2.2 基于区域的图像分割方法
基于区域的分割方法得到的分割结果直接构成区域，基本思想就是将图像划分成最大一致性的分区。一致性是分区的最大的特征，也是分割的准则。一致性准则可以是基于灰度，色彩，纹理等的标准。在基于区域的分割方法中比较经典的方法有区域生长和分裂合并法。区域生长和分裂合并法是两种典型的串行区域技术，其分割过程后续步骤的处理要根据前面步骤的结果进行判断而确定。
先为每个需要分割的区域确定一个种子像素作为生长起点，然后按一定的生长准则把它周围与其特性相同或相似的像素合并到种子像素所在的区域中。把这些新像素作为种子继续生长，直到没有满足条件的像素可被包括，这时生长停止，一个区域就形成了。
区域生长法要解决的主要问题是区域生长准则的设计和算法的高效性。生长准则往往和具体问题有关，直接影响最后形成的区域，如果选取不当，就会造成过分割和欠分割的现象。区域生长法的优点是计算简单，对于较均匀的连通目标有较好的分割效果。它的缺点是需要人为确定种子点，对噪声敏感，可能导致区域内有空洞。另外，它是一种串行算法，当目标较大时，分割速度较慢，因此在设计算法时要尽量提高效率。
分裂合并法的基本思想[12，15，16]是从整幅图像开始通过不断分裂合并得到各个区域。一种利用四叉树表达方法的分割算法如下：R代表整个正方形图像区域，P 代表检验准则。
1）对任意区域R i，如果P（R i ）=FAlSE就将其分裂为不重叠的四等分。
2）对相邻的两个区域R i 和R j，如果P（R i U R j）=TRUE 则将它们合并为一个区域。
3）如果进一步的分裂和合并都不可能时则停止。
图2-5 分列合并法演示图
分裂合并法的关键是分裂合并准则的设计。这种方法对复杂图像的分割效果较好，但算法较复杂，计算量大，分裂还可能破坏区域的边界。
2.2.3 基于边界的图像分割方法
基于边界的分割方法是利用不同区域间象素灰度不连续的特点检测出区域间的边缘，从而实现图像分割。图像中相邻的不同区域间总存在边缘，边缘处像素的灰度值不连续，这种不连续性可通过求导数来检测到。对于阶跃状边缘，其位置对应一阶导数的极值点，对应二阶导数的过零点（零交叉点）。因此常用微分算子进行边缘检测，它是一种并行边界技术。常用的一阶微分算子有Roberts、Prewitt和Sobel算子、二阶微分算子有Laplace和Kirsh算子等。在实际中各种微分算子常用小区域模板来表示，微分运算是利用模板与图像卷积来实现。下面介
绍几种经典的边缘检测算子。
Sobel 算子[12]是实际应用中效果比较好的边缘算子。由于差分算子的抗干扰性很差，噪音会使得使用差分算子的时候在噪音边缘产生冲击，Sobel 算子通过先求加权平均然后再求差分的方法来增强抑制噪音干扰的能力：
'[(1,1)2(,1)(1,1)][(1,1)2(,1)(1,1)]x f f i j f i j f i j f i j f i j f i j =-++++++---+-++-'[(1,1)2(1,)(1,1)][(1,1)2(1,)(1,1)]y f f i j f i j f i j f i j f i j f i j =--+-+-+-+-+++++ 上述的Sobel 算子不是各向同性的，沿不同方向的梯度幅值不一样，因此通常使用改进的各向同性的Sobel 算子，它的加权系数是不是2。
拉普拉斯(Laplacian )算子，定义如下：
222
22(,)(,)(,)()()f x y f x y f x y x y ???=+??………………………(2.4) 拉普拉斯算子是一个标量，它没有边缘方向的信息，对噪音非常敏感，具有旋转不变性即各向同性的性质。由于拉普拉斯算子没有边缘方向的信息，并且对噪音非常敏感，因此实际应用中往往不直接用来获取边缘，而是先做图像滤波后再使用拉普拉斯算子，这种方法就是拉普拉斯一高斯(Laplacian of Gaussian )算子，此处不做过多介绍。
图2-8 拉普拉斯算子卷积模板
Roberts 算子是数字图像处理中最古老的边缘检测算子之一。它也是最简单的一种边缘检测算子。它的卷积模板如下：
图2-9 Roberts 算子卷积模板
卷积边缘检测算子的主要缺点是它们依赖于尺度且对噪声敏感。很少有合适的理由来解释为什么选择某个特别的局部邻域算子尺度。绝大多数基于边界的图像分割方法都集中在边界的检测方面，这些边界部分或全部对图像进行了分割处理。如果获得了完全的分割，边界将图像分割为区域，但是如果仅产生了部分分割，区域并没有唯一的定义，根据边界确定区域的问题可能是一个非常复杂的问题，需要与高层知识配合。
图像分割领域的方法和文献有很多，我们在上面仅仅介绍了几大类常用的方法。近年来随着其他领域的发展，很多研究人员将其它领域的方法不断引入到图