基于模糊理论的图像分割算法研究

论文关键词: 图像分割 边缘检测 模糊理论 遗传算法 Matlab

论文摘要：分割的目的是将图像划分为不同区域。图像分割算法一般是基于亮度值的两个基本特性之一：不连续性和相似性。第一类性质的已用途径是基于亮度的不连续变化分割图像，比如图像的边缘。第二类的主要应用途径是依据事先制订的准则将图像分割为相似的区域。门限处理、区域生长、区域分离和聚合都是这类方法的实例。遗传算法具有简单、鲁棒性好和本质并行的突出优点。其在应用领域取得的巨大成功，引起了广大学者的关注。在图像分割领域，遗传算法常用来帮助确定分割阈值。

本文介绍讨论了几种目前广泛应用的图像边缘检测、图像阈值分割的各种算法，并给出了对比分析;对遗传算法的基本概念和研究进展进行了综述;给出了标准遗传算法的原理、过程、实验结果及分析. 实验结果表明，本文提出的遗传分割算法优于传统分割算法。

第一章 绪论 1.1 图像分割综述

图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里所说的特性可以是灰度、颜色、纹理等，而目标可以对应单个区域，也可以对应多个区域。图像分割是数字图像处理中的一项关键技术，它使得其后的图像分析，识别等高级处理阶段所要处理的数据量大大减少，同时又保留有关图像结构特征的信息。而且，在数字图像处理工程中，一方面，图像分割是目标表达的基础，对特征测量有重要的影响；另一方面，图像分割是自动目标识别的关键步骤，图像分割及其基于分割的目标表达、特征提取和参数测量等将原始图像转化为更抽象更紧凑的形式，分割中出现的误差会传播至高层次处理阶段，因此分割的精确程度是至关重要的。只有通过细致精细的图像分割，才能使得更高层的图像分析和理解成为可能。因此，图像分割是由图像处理进到图像分析的关键步骤，在图像工程中占据重要的位置。

1.2 图像分割的研究意义与发展现状 作为计算机视觉和图像处理中的难点和热点之一，图像分割的研究受到了研究工作者的高度重视，对图像分割进行了深入、广泛的研究。作为一种重要的图像技术，图像分割在不同领域中有时也用其它名称：如目标轮廓(object delineation)技术，阈值化(thresholding)技术，图像区分或求差(image discrimination)技术，目标检测(target detection)技术，目标识别(target recognition)技术，目标跟踪(target tracking)技术等，但这些技术本身或其核心实际上也就是图像分割技术。图像分割作为图像处理、分析的一项基本内容，其应用非常广泛，几乎出现在有关图像处理的所有领域，并涉及各种类型的图像。在工业自动化、在线产品检验、生产程控、文件图像处理、遥感图像、保安监视、以及军事、体育、农业等行业和工程中，图像分割都有着广泛的应用。例如：在遥感图像中，合成孔径雷达图像中目标的分割、遥感云图中不同云系和背景分布的分割等；在医学应用中，脑部 MR 图像分割成灰质（GM）、白质（WM）、脑脊髓（CSF）等脑组织和其它脑组织区域（NB）等；在交通图像分析中，把车辆目标从背景中分割出来等；在面向对象的图像压缩和基于内容的图像检索中将图像分割成不同的对象区域等。在各种图像应用中，只要需对图像目标进行提取，测量等都离不开图像分割。

自 20 世纪 70 年代至今，已提出上千种各种类型的分割算法。如：门限法、匹配法、区域生长法、分裂－合并法、水线法、马尔可夫随机场模型法、多尺度法、小波分析法、数学形态学等。随着新理论、新技术的发展，一些新的图像分割方法也随之出现，但这些分割算法都是针对某一类型图像、某一具体的应用问题而提出的，并没有一种适合所有图像的通用分割算法。通用方法和策略仍面临着巨大的困难。另外，还没有制定出选择适用分割算法的标准，这给图像分割技术的应用带来许多实际问题。

1.3 本论文所作的工作 据此，在本论文中只对常用的、并在实践中行之有效的边缘检测方法和阈值分割方法进行深入的了解，并对阈值分割方法中的灰度直方图双峰法和基于遗传算法的最大类间方差法进行详细的讨论，同时用Matlab对上述两种方法进行验证并给出结果。

1.4 本论文的论述内容 本文对图像分割的整个过程中的一些常用的，经实践检验行之有效的算法进行了讨论和 改进。全文共七章。第一章为绪论，主要介绍了现阶段图像分割技术的发展现状和研究意义。其他六章分别在以下几个方面介绍了本文所做的工作：

1.对本文所采用的试验测试工具Matlab 进行简介。

2.简介数字图像的基础问题。概述了数字图像的基本概念和特点，简介了各种图像格式的特点和应用，为全文的讨论作一铺垫。

3.详细讨论了图像分割中的基于阈值的图像分割方法，给出了直方双峰法的算法和验证结果，并简要介绍了普通最大类间方差法的算法过程。

4.对遗传算法理论进行简介。详细讨论了遗传算法的定义和标准遗传算法的流程和要素。为应用此方法对最大阈值进行迭代寻优打下基础。

6.应用遗传算法改进了最大类间方差法。给出了整个遗传操作的使用函数与具体进程，并对实例图片进行处理，得到处理结果并得到迭代最优阈值M。

本文研究了图像分割的相关理论和常用技术，并对遗传算法进行了介绍,对遗传算法应用于图像分割进行了验证.

第二章 Matlab简介 2.1 MATLAB的概况和产生背景 2.1.1 MATLAB的概况 MATLAB是矩阵实验室（Matrix　Laboratory）之意。除具备卓越的数值计算能力外，它还提供了专业水平的符号计算，文字处理，可视化建模仿真和实时控制等功能。MATLAB的基本数据单位是矩阵，它的指令表达式与数学,工程中常用的形式十分相似,故用MATLAB来解算问题要比用C,FORTRAN等语言完相同的事情简捷得多.

当前流行的MATLAB包括拥有数百个内部函数的主包和三十几种工具包(Toolbox).工具包又可以分为功能性工具包和学科工具包.功能工具包用来扩充MATLAB的符号计算,可视化建模仿真,文字处理及实时控制等功能.学科工具包是专业性比较强的工具包,控制工具包,信号处理工具包,通信工具包等都属于此类.开放性使MATLAB广受用户欢迎.除内部函数外,所有MATLAB主包文件和各种工具包都是可读可修改的文件,用户通过对源程序的修改或加入自己编写程序构造新的专用工具包.

2.1.2 MATLAB产生的历史背景 在70年代中期,Cleve Moler博士和其同事在美国国家科学基金的资助下开发了调用EISPACK和LINPACK的FORTRAN子程序库.EISPACK是特征值求解的FOETRAN程序库,LINPACK是解线性方程的程序库.在当时,这两个程序库代表矩阵运算的最高水平.到70年代后期,身为美国New Mexico大学计算机系系主任的Cleve Moler,在给学生讲授线性代数课程时,想教学生使用EISPACK和LINPACK程序库,但他发现学生用FORTRAN编写接口程序很费时间,于是他开始自己动手,利用业余时间为学生编写EISPACK和LINPACK的接口程序.Cleve Moler给这个接口程序取名为MATLAB,该名为矩阵(matrix)和实验室(labotatory)两个英文单词的前三个字母的组合.在以后的数年里,MATLAB在多所大学里作为教学辅助软件使用,并作为面向大众的免费软件广为流传。1983年春天,Cleve Moler到Standford大学讲学,MATLAB深深地吸引了工程师John Little.John Little敏锐地觉察到MATLAB在工程领域的广阔前景.同年,他和Cleve Moler,Steve Bangert一起,用C语言开发了第二代专业版.这一代的MATLAB语言同时具备了数值计算和数据图示化的功能.1984年,Cleve Moler和John Little成立了Math Works公司,正式把MATLAB推向市场,并继续进行MATLAB的研究和开发.

在当今30多个数学类科技应用软件中,就软件数学处理的原始内核而言,可分为两大类.一类是数值计算型软件,如MATLAB,Xmath,Gauss等,这类软件长于数值计算,对处理大批数据效率高;另一类是数学分析型软件,Mathematica,Maple等,这类软件以符号计算见长,能给出解析解和任意精确解,其缺点是处理大量数据时效率较低.MathWorks公司顺应多功能需求之潮流,在其卓越数值计算和图示能力的基础上,又率先在专业水平上开拓了其符号计算,文字处理,可视化建模和实时控制能力,开发了适合多学科,多部门要求的新一代科技应用软件MATLAB.经过多年的国际竞争,MATLAB以经占据了数值软件市场的主导地位.

在MATLAB进入市场前，国际上的许多软件包都是直接以FORTRANC语言等编程语言开发的。这种软件的缺点是使用面窄，接口简陋，程序结构不开放以及没有标准的基库，很难适应各学科的最新发展，因而很难推广。MATLAB的出现，为各国科学家开发学科软件提供了新的基础。在MATLAB问世不久的80年代中期，原先控制领域里的一些软件包纷纷被淘汰或在MATLAB上重建。

时至今日，经过MathWorks公司的不断完善，MATLAB已经发展成为适合多学科，多种工作平台的功能强大大大型软件。在国外，MATLAB已经经受了多年考验。在欧美等高校，MATLAB已经成为线性代数，自动控制理论，数理统计，数字信号处理，时间序列分析，动态系统仿真等高级课程的基本教学工具；成为攻读学位的大学生，硕士生，博士生必须掌握的基本技能。在设计研究单位和工业部门，MATLAB被广泛用于科学研究和解决各种具体问题。在国内，特别是工程界，MATLAB一定会盛行起来。可以说，无论你从事工程方面的哪个学科，都能在MATLAB里找到合适的功能。

2.2 MATLAB的语言特点 一种语言之所以能如此迅速地普及，显示出如此旺盛的生命力，是由于它有着不同于其他语言的特点，正如同FORTRAN和C等高级语言使人们摆脱了需要直接对计算机硬件资源进行操作一样，被称作为第四代计算机语言的MATLAB，利用其丰富的函数资源，使编程人员从繁琐的程序代码中解放出来。MATLAB最突出的特点就是简洁。MATLAB用更直观的，符合人们思维习惯的代码，代替了C和 FORTRAN语言的冗长代码。MATLAB给用户带来的是最直观，最简洁的程序开发环境。以下简单介绍一下MATLAB的主要特点。

1. 语言简洁紧凑，使用方便灵活，库函数极其丰富。MATLAB程序书写形式自由，利用起丰富的库函数避开繁杂的子程序编程任务，压缩了一切不必要的编程工作。由于库函数都由本领域的专家编写，用户不必担心函数的可靠性。可以说，用MATLAB进行科技开发是站在专家的肩膀上。　更为难能可贵的是，MATLAB甚至具有一定的智能水平，所以用户根本不用怀疑MATLAB的准确性。

2. 运算符丰富。由于MATLAB是用C语言编写的，MATLAB提供了和C语言几乎一样多的运算符，灵活使用MATLAB的运算符将使程序变得极为简短。

3. MATLAB既具有结构化的控制语句（如for循环，while循环，break语句和if语句），又有面向对象编程的特性。

4. 程序限制不严格，程序设计自由度大。例如，在MATLAB里，用户无需对矩阵预定义就可使用。

5. 程序的可移植性很好，基本上不做修改就可以在各种型号的计算机和操作系统上运行。

6. MATLAB的图形功能强大。在FORTRAN和C语言里，绘图都很不容易，但在MATLAB里，数据的可视化非常简单。MATLAB还具有较强的编辑图形界面的能力。

7. MATLAB的缺点是，它和其他高级程序相比，程序的执行速度较慢。由于MATLAB的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。

8. 功能强大的工具箱是MATLAB的另一特色。MATLAB包含两个部分：核心部分和各种可选的工具箱。核心部分中有数百个核心内部函数。其工具箱又分为两类：功能性工具箱和学科性工具箱。功能性工具箱主要用来扩充其符号计算功能，图示建模仿真功能，文字处理功能以及与硬件实时交互功能。功能性工具箱用于多种学科。而学科性工具箱是专业性比较强的，如control,toolbox,signl proceessing toolbox,commumnication toolbox等。这些工具箱都是由该领域内学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究。

9. 源程序的开放性。开放性也许是MATLAB最受人们欢迎的特点。除内部函数以外，所有MATLAB的核心文件和工具箱文件都是可读可改的源文件，用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。

2.3 MATLAB 遗传算法工具箱简介 鉴于Matlab强大的扩展功能和影响力，各个领域的专家相继突出了许多基于Matlab的专用工具箱。本文所采用的遗传算法工具箱，就是由英国谢菲尔德（Sheffield）大学设计推出的。相对于其他版本的遗传算法工具箱，如：美国北卡莱罗纳州立大学推出的遗传算法优化工具箱GAOT（Genetic Algorithm Optimization Toolbox），以及MathWorks公司最新的一个专门设计的Matlab遗传算法和直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox），本工具箱的出现最早，影响较大且功能较为完备。文中所采用的所有遗传操作函数大部分出自本工具箱。

第三章 数字图像基础简介 图像处理的首要一步，就是要了解图像的基本性质与特点。只有充分了解和掌握了所要处理得图像的特点和性质，才能在接下来的处理中根据图像的特点获取所需的信息，并对其进行相应的处理。

本章将介绍数字图像的基础知识，以及图像在计算机处理中的信息表达形式，并对几种常用的图像文件格式Bmp, Jpeg以及Png等做简要的介绍。

3.1 图像的基本概念及其特点 要对图像进行处理，必须清楚图像的概念。一般来说，二维或三维景物呈现在人眼中的样子就是图像。图像具有以下三个方面的特点:

①图像带有大量的信息，一幅图像顶得上千言万语;

②图像种类繁多，包括照片、绘图视频图像等;

③人类从外界获得的大部分信息来自视觉系统。

人们看到的任何自然界的图像都是连续的模拟图像。其形状和形态表现由图像各位置的颜色来决定。可以用f（x, y)表示一幅模拟图像，其中x, y表示空间坐标点的位置，f表示图像在点(x, y)的某种性质的数值，如亮度、颜色等，f、x、y可以是任意的实数。而把连续空间的图像在坐标空间(X, Y)和性质空间F都离散化，以便于计算机进行加工处理的离散化的图像则称为数字图像。数字图像用I (r, c)来表示，其中:r=row为行，c = col为列，表示空间离散点的坐标，I表示离散化的图像f。I, r, c都是整数。实际中仍习惯用f (x, y)表示数字图像。图像存储画面的形式为栅格结构:即将图像划分为均匀分布的栅格(像素)，显式的记录每一像素的亮度和颜色;而将像素的坐标值规则地隐含起来，其位置排列规则，通常为矩形排列。

3.2 图像的格式 组成数字图像的基本单位称为像素(Pixel)，把像素按不同的方式进行组织和存储，就得到不同的图像格式;把图像数据存为文件就得到图像文件。图像文件按其格式的不同一般具有不同的扩展名。常用的图像文件格式有位图文件、JPEG文件、GIF文件、PNG文件等。每一种格式都有它的特点和用途，在选择输出的图像文件格式时，应考虑图像的应用目的以及图像文件格式对图像数据类型的要求。下面我们介绍几种常用的图像文件格式及其特点。

3.2.1 BMP图像格式 这是一种DOS和Windows兼容计算机系统的标准图像格式。BMP格式支持索引色、灰度等色彩模式。图像存储为BMP格式时，每一个像素所占的位数可以是1位、4位、8位或32位，相对应的颜色数也从黑白一直到真彩色。对于使用Windows格式的4位和8位图像，可以指定采用RLE压缩。BMP图像文件含文件头、调色板数据和图像数据三个层次。其中文件头由定义文件标识、大小即图像数据偏移量的BITMAPF工LEHEADER以及指定BMP图像自身的若干参数的BITMAPINFOHEADER两部分组成。这种格式在PC机上应用非常普遍。

3.2.2 JPEG图像格式 JPEG是由联合照片专家组(JiontPhotographic Experts Group)开发的一种图像文件格式。它采用有损压缩方式去除冗余的图像和彩色数据，在获取极高的压缩率的同时也能展现十分丰富生动的图像。也就是说，可以用较少的磁盘空间得到较好的图像质。另外，JPEG还是一种比较灵活的格式，当将图像保存为JPEG格式时，允许用户用不同的压缩比例对文件进行压缩，就是可以指定图像的品质和压缩级别。

3.2.3 TIFF图像格式 TIFF文件主要由三部份组成，包括文件头、标识信息区和图像数据区。T工FF文件的图像数据区以行扫描的方式存取图像，存储图像前先将图像分割成若干部分，压缩后再存储。存储时，单色图像一个字节存储8个点，16色图像一个字节2个点，而256色图像就是一个字节存储一个点。TIFF图像格式是一种应用非常广泛的位图图像格式，几乎被所有绘画、图像编辑和页面排版应用程序所支持。TIFF格式常常用于在应用程序之间和计算机平台之间交换文件。

3.2.4 GIF图像格式 CIF是Graphics Interchange Format(图形交换格式)的缩写，是由ComputerServe公司推出的一种图像格式。该种图像格式的特点是压缩比高，可以极大地节省存储空间。最初的GIF只是简单的用来存储单幅静止图像，后来可以同时存储若干幅静止图像从而形成连续的动画;同时，GIF格式支持透明背景，可以较好地与网页背景融合在一起。因此，GIF常常用于保存作为网页数据进行传输的图像文件，成为网络和BBS上使用频率较高的一种图像文件格式。但是GIF最多只能处理256种色彩，不能用于存储真彩色的图像文件。

3.2.5 PNG图像格式 这种格式称为可移植网络图像文件格式(Portable Network Graphics)，由Thomas Boutell, Tom Lan。等人提出并设计。其特点是:①支持48位真彩色图像、16位灰度图像和颜色索引数据图像;②主要面向网络图像传输和图像编辑，其提供的二维交叉存储机制使用户在图像网络传输过程中能更快的观察到接近真实的近似图像;③对用户完全透明且无专利限制，用户可以从Internet上随时下载与PNG文件格式配套的图像数据压缩算法源程序代码:④ 具有比GIF高5-20%的压缩效率;⑤ 具有可扩展性。

作为目前最不失真的图像格式， PNG格式图像吸取了GIF和JPEG二者的优点。它可以把文件压缩到极限以利于网络传输，但由于采用无损压缩方式来减少文件大小，PNG格式能保留所有与图像品质有关的信息。同时，PNG支持图像背景透明，显示速度快。

本文的所有图像的处理都是对由JPG格式图像通过图像格式转化得来的Bmp格式的索引色图像进行的，其具体转换程序参见附录[一]。

第四章 图像分割 4.1 图像分割算法的定义与分类 在图像的研究和应用中，人们往往只对一幅图像中的某些部分感兴趣，这些感兴趣的部分一般对应图像定的、具有特殊性质的区域（可以对应单个区域，也可以对应多个区域），称之为目标或前景；而其它部分称为图像的背景。为了辨识和分析目标，需要把目标从一幅图像中孤立出来，这就是图像分割要研究的问题。所谓图像分割，从广义上来讲，是根据图像的某些特征或特征集合（包括灰度、颜色、纹理等）的相似性准则对图像象素进行分组聚类，把图像平面划分成若干个具有某些一致性的不重叠区域。这使得同一区域中的象素特征是类似的，即具有一致性；而不同区域间象素的特征存在突变，即具有非一致性。从集合的角度出发，图像分割定义如下：

设整个图像空间为一集合R 。根据选定的一致性准则P ，R 被划分为互不重叠的非空子集（或子区域）：{R1, R2,L, Rn}，这些子集必须满足下述条件：

（1） R =

（2） 对于所有的i和j ，当i ≠ j， =空集

（3） P(Ri) = True ,对所有的i

（4） 所有i ≠ j；Ri ,Rj相邻，P(Ri U Rj) = False

（5） 对i =1,2,L,n, Ri是连通区域

其中：P(Ri)为作用于Ri 中所有象素的形似性逻辑谓词，i, j =1,2,L,…n。上述条件

（1）指出分割后的全部子区域的总和应包含图像中的所有元素，或者说分割应将图像中每个象素都分进一个子区域中。

（2）指出各个子区域相互不重叠。

（3）指出分割后得到的属于同一区域中的元素应该具有某种相同特性。

（4）指出对于分割后得到的属于相邻两个区域中的元素具有某种不同的特性。（5）要求同一个子区域内的元素应当是连通的。

其中分割准则P 适用于所有象素，由它来确定各区域元素的相同特性。上述数学条件说明了图像分割算法的一些特点，凡不符合以上特点的图像处理算法则不能称为图像分割算法。

目前，在己提出的多种类型的分割算法中，大致可以分为基于边缘检测的方法和基于区域的方法。而在实际应用中，这些方法主要又可划分为三种类型: 边缘检测型、阈值型和区域跟踪型。本文的讨论正是基于阈值型图像分割方法展开的。

4.2 基于阈值的分割 4.2.1方法定义与特点 基于阈值的分割方法是一种应用十分广泛的图像分割技术。所谓阈值分割方法的实质是利用图像的灰度直方图信息得到用于分割的阈值。它是用一个或几个阈值将图像的灰度级分为几个部分，认为属于同一个部分的象素是同一个物体。它不仅可以极大的压缩数据量，而且也大大简化了图像信息的分析和处理步骤。因此，在很多情况下，是进行图像分析、特征提取与模式识别之前必要的图像预处理过程。它特别适用于目标和背景占据不同灰度级范围的图像。阈值分割方法的最大特点是计算简单，运算效率高，在重视运算效率的应用场合，它得到了广泛的应用。

4.2.2阈值的分割的描述 设(x,y)是二维数字图像的平面坐标，图像灰度级的取值范围是G= {0, 1, 2,…L-1 }(习惯上0代表最暗的像素点，L-1代表最亮的像素点)，位于坐标点(x, y)上的像素点的灰度级表示为f (x, y)。设t∈G为分割阈值，B= {b0, b 1}代表一个二值灰度级，并且b0, b1∈B。于是图像函数f 1(x,y)在阈值t上的分割结果可以表示为:

阈值分割法实际就是按某个准则函数求最优阈值t的过程。域值一般可写成如下的形式:

T=T［x，y, f (x，Y)，p (x，y)］

其中f (x, y)是在像素点(x, y)处的灰度值，p(x,y)是该点邻域的某种局部性质。4.3.3阈值分割方法的分类

通过上文的讨论，结合所给公式，可以将阈值分割方法分为以下3类:

1) 全局阈值:T=T[p(x,y)〕，即仅根据f(x,y)来选取阈值，阈值仅与各个图像像素的本身性质有关。

2) 局部阈值:T=T[f(x,y),p(x,y)],阈值与图像像素的本身性质和局部区域性质相关。

3) 动态阈值:T=T[x,y,f(x,y),p(x,y)],阈值与像素坐标，图像像素的本身性质和局部区域性质相关。

全局阈值对整幅图像仅设置一个分割阈值，通常在图像不太复杂、灰度分布较集中的情况下采用;局部阈值则将图像划分为若干个子图像，并对每个子图像设定局部阈值;动态阈值是根据空间信息和灰度信息确定。局部阈值分割法虽然能改善分割效果，但存在几个缺点:

1) 每幅子图像的尺寸不能太小，否则统计出的结果无意义。

2) 每幅图像的分割是任意的，如果有一幅子图像正好落在目标区域或背景区域，而根据统计结果对其进行分割，也许会产生更差的结果。

3) 局部阈值法对每一幅子图像都要进行统计，速度慢，难以适应实时性的要求。

全局阈值分割方法在图像处理中应用比较多，它在整幅图像内采用固定的阈值分割图像。考虑到全局阈值分割方法应用的广泛性，本文所着重讨论的就是全局阈值分割方法中的直方图双峰法和基于遗传算法的最大类间方差法。在本节中，将重点讨论灰度直方图双峰法，最大类间方差法以及基于遗传算法的最大类间方差法留待下章做继续深入地讨论。

4.2.3 直方图双峰法（mode 法） Prewitt 等人于六十年代中期提出的直方图双峰法(也称 mode 法) 是典型的全局单阈值分割方法。该方法的基本思想是：假设图像中有明显的目标和背景，则其灰度直方图呈双峰分布，如图所示：

当灰度级直方图具有双峰特性时，选取两峰之间的谷对应的灰度级作为阈值。如果背景的灰度值在整个图像中可以合理地看作为恒定，而且所有物体与背景都具有几乎相同的对比度，那么，选择一个正确的、固定的全局阈值会有较好的效果。例如图4.1所示：

图4.1

原始灰度图像

图4.2

灰度直方图

当选定阈值M为100时，分割效果如下：

图4.3

分割后图像

通过对上示图片的比照，对于简单的，背景图像和目标图像对比鲜明的图片，我们很容易通过其灰度直方图找到分割用的阈值（M=100），从而将图像按照灰度的不同区分开来。

这种方法虽然简单易行，但是因为同一个直方图可能对应若干种不同的图像，所以使用双峰法需要有一定的图像先验知识，而且该方法不适合用于直方图中的双峰差别很大或双峰之间的谷部较宽广而平坦或者只有单峰的图像。例如，在对于下示图4.4，图4.7，图片的处理：

图4.4

原始图像

图4.5

灰度图像

图4.6

灰度直方图

图片4.5的直方图平坦，无法找出两峰之间的峰谷。

图4.7

原始图像

图4.8

灰度图像

图4.9

灰度直方图

图片4.8的直方图的各峰差别大，无法通过峰谷判定阈值。因此，阈值的难以确定，导致对这两幅图片采用灰度直方图法的失败：

图4.10

分割结果

图4.11

分割结果

由于图片4.5直方图的平坦，无法找出两峰之间的峰谷，而图片4.8的直方图各峰差别很大，导致图片4.5和图片4.8都无法获得足够的图像先验知识，从而使本方法的使用遇到困难，阈值的寻找困难直接导致在采用本方法处理图片后，分割后的图像与原图像的差别很不明显，并未达到实际的分割效果。因此，本方法的使用的局限性很大，只适于对一些简单的背景和目标图像的灰度差别很大的图像的处理，（程序源代码参见附录一），而且不便于阈值的自动选择，无法完全自动的有程序实现。

第五章 模糊理论和遗传算法理论简介 传统的信息处理方法建立在概率假设和二态假设(Probality Assumption

&Binary-State Assumption)的基础上。概率假设使传统的数学应用范围从确定性现象扩展到随机现象，二态假设对应了人类的精确思维方式。但自然界客观存在的事物除了可以精确表示之外，还存在着大量的模糊现象，如“年轻人”、“高个子”等，究竟多大年龄之间算“年轻’，，多高个子为“高个子”，这是人们观念中的模糊的概念，模糊(Fuzzy)概念由此产生。模糊性也就是生活中的不确定性。实际上客观事物的不确定性除了随机性外，模糊性也是一种不确定性。所谓模糊性是指事物的性质或类属的不分明性，其根源是事物之间存在过渡性的事物或状态，使它们之间没有明确的分界线。

在自然科学中，人们长久以来习惯于追求精确性，总希望把事物以数学方式描述出来，然而，面对模糊现象，传统的数学方法遇到了实质性的困难。但对于人的大脑而言，它具有很高的模糊划分、模糊判断和模糊推理的能力，而且人们为了表达和传递知识所采用的自然语言中已巧妙地渗透了模糊性，并能用最少的词汇表达尽可能多的信息。但是，对于计算机来说，无论它怎样发展，总无法达到人脑的境界，所以，用计算机来处理模糊信息，就需要一种能够将模糊语言形式化的工具，用数学的方式处理这种模糊性。模糊数学的一个重要特点，就是让数学反过来吸收人脑的模糊识别和判决特点，并将之运用于计算机，使部分自然语言能够作为算法语言直接进入程序，让机器通过模仿生物的思维判别模式，使人们能够以简易的程序来调动机器完成复杂的任务，从而大大提高机器的灵活性。人工智能，计算生命，遗传算法等前沿学科正是模糊数学理论发展的结果。在面对工程领域中大量的无法采用传统优化方法解决的复杂的、非线性的优化问题时，遗传算法作为模糊数学理论中重要的一支，因其具有简单、通用，鲁棒性强，且易于并行性的特点，而广泛应用于工程设计的优化，系统辨识和控制，机器学习，图像处理和智能信息处理等领域。

本文正是以遗传算法这一新的,融生命科学与工程科学于一体的全局搜索算法为主要的研究与讨论方向，重点讨论了基于遗传算法理论的图像分割问题。

5.1遗传算法的基本概念 遗传算法(GA-Genetic Algorithms)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，由Michigan大学的J. Holland教授于1975年首先提出。它将“适者生存”的进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。通过遗传操作，使优良品质被不断保留、组合，从而不断产生出更佳的个体。子代个体中包含父代个体的大量信息，并在总体上胜过父代个体，从而使种群向前进化发展，即不断接近最优解。由于遗传算法是自然遗传学和计算机科学相互结合渗透的产物，因此借用了许多自然进化的基础术语。

·种群(population)和个体(individuals)

遗传算法处理的是染色体，或者叫基因型个体，通常以一维串结构资料来表现。一定数量的个体组成了种群(population )，或叫集团。

·种群规模(population size )

种群中个体的数目称为种群大小，也叫种群规模。

·适应度函数(fitness function )

各个个体对环境的适应程度叫做适应度。对于优化问题，适应度函数就是目标函数。遗传算法对适应度函数并不要求可导等条件，只要求适应度函数为可加以比较的非负函数。

·编码(coding)、译码(decoding)操作

遗传算法必须包含两个必须的资料转换操作，即把搜索空间中的参数或解转换成遗传空间中的染色体或个体，称为编码操作；反之，称为译码操作。

·选择(selection )、交叉(crossover)和变异(mutation)操作

这三个操作数是遗传算法的三个主要操作操作数，即遗传操作( genetic operation，是遗传算法的特点。(详细介绍将在下节。)

5.2遗传算法 5.2.1遗传算法的基本流程 标准遗传算法(( SGA)的基本流程如图所示，算法主要步骤如下图5.1示：

1)随机产生初始种群，作为第一代。个体长度、种群规模、交叉概率、变异概率为固定值;

2)对父代种群计算适应度值;

3)判断是否满足终止条件，是，则执行步骤4:否则，进行选择、交叉、变异操作形成子代种群，并将子代种群作为下一次叠代的父代种群，转入执行步骤2;

4)输出最佳个体，退出。

SHAPE \* MERGEFORMAT

5.2.2遗传算法的要素 遗传算法具有5个基本要素:编码机制，初始种群的设定，适应度函数的设定，遗传操作，控制参数的设定。具体步骤如下：

1.编码机制

编码机制是遗传算法的基础。通常遗传算法不直接处理问题空间的资料，而是将各种实际问题变换为与问题无关的串个体。对染色体串的遗传操作只与遗传算法的理论、技术有关，而与具体实际问题无关。这一特性增大了遗传算法的适用性。当实际问题变化时，可只改变适应度函数，而无需改变其它操作，加强了代码的通用性。最常用的方法是二进制串结构编码。

2.初始化种群设定

遗传算法处理流程中，编码设计之后的任务是初始种群的设定，并以此为起点一代一代的进化直到按照某种进化终止准则终止。最常用的初始方法是无指导的随机初始化。

3.适应度函数

遗传算法在搜索过程中基本不采用外部信息，仅以适应度函数为依据引导搜索。它不受连续可微的约束且定义域可为任意集合。对目标函数的唯一要求是，对输入计算出能加以比较的非负结果。这使得遗传算法的应用范围非常广泛。个体的适应度值越大，表明该个体的生存能力越大，易于遗传产生后代。

4.遗传操作

遗传操作主要包括:选择(selection )、交叉(crossover)、变异mutation)三个操作数。

1)选择

选择过程是模仿自然选择现象，从父代种群中选出优良个体。个体的适应度值越大，在子代中将有更多的机会作为父代产生一个或多个子代个体。通常选用适应度比例法(赌方式roulette wheel )确定选择次数，该法中的各个体选择概率和其适应度值成比例。

2)交叉

最简单的交叉操作为单点交叉:首先，对父代个体进行随机配对;然后，配对个体随机设定交叉位置;最后，交换配对个体的部分信息。当染色体长度为l时，l-1有个交叉位置，单点交叉可实现l- 1种不同的交叉结果。

父代个体A 10011|011 10011100 新个体A’

父代个体B 01101|100 01101011 新个体B’

3)变异

变异操作随机选择变异基因序号，根据一定的变异概率Pm对该序号基因进行变异。对于二进制编码个体通常采用0变为l， 1变为0。

1 0 0 1 1 0 1 1 0 1 1 0 1

变异位

5.控制参数

控制参数主要有:种群规模、迭代次数、交叉概率、变异概率等。对此标准遗传算法都设为固定值。标准遗传算法的特点是:

1)赌选择方法:

2)随机配对;

3)单点交叉，生成两个子代个体:

4)种群内允许相同个体出现。

可见，遗传算法从任一初始化种群出发，通过选择(使优秀个体有更多机会传给子代)，交叉(体现优秀个体间的信息交换)，变异(引入新的个体，保持种群的多样性)操作种群一代一代的进化到搜索空间中最优点附近，直至收敛到最优解点。遗传算法不是直接作用在问题空间中，而是编码空间中，而且遗传操作非常简单。这使得遗传算法具有了简单，通用，鲁棒性强的特点。

第六章 基于遗传算法的最大类间方差分割法 6.1 普通最大类间方差法（Otsu法）简介 由 Otsu于 1978 年提出的最大类间方差法以其计算简单、稳定有效而一直广为使用。该方法又称为大津阈值分割法，是在判决分析最小二乘法原理的基础上推导得出的，算法较为简单。此方法由于其简便性和分割准确性在图像分割中被大量采用，但是缺点在于与，与后文所述的基于遗传算法最大类间方差法相比，要求得最佳阈值，需要遍历灰度范围0~L-1内的所有像素并计算方差，最后比较得出最大方差，计算量大同时效率也很低，运算时间偏长。鉴于本文着重讨论遗传算法最大类间方差法，因此对于普通最大类间方差法讨论只作简介，详细内容参阅参考文章[25]。

基本思路：选取的最佳阈值t应当使得不同类间的分离性最好。首先计算基于直方图得到各分割特征值的发生概率，并以阈值变量t将分割特征值分为两类，然后求出每一类的类内方差及类间方差，选取使得类间方差最大，类内方差最小的t作为最佳阈值。具体步骤如下：

设原始灰度图像灰度级为L，灰度级为i的象素点数目为ni，则图像的全部象素数为

按阈值t可将所有象素划分两类：C0= (0,1,2,…,t)和C1 = (t +1,t + 2,…,L -1) 。而C0和C1类的类出现概率w及均值μ 分别由下列各式给出：

式中：

。

不难得出，对任何t值，下式都能成立：

C0和C1类的方差可由下式求得：

定义类内方差σw、类间方差σB、总体方差σT 为：

引入

则最佳阈值t*可选择为：

t* = maxη(t)

在图像处理过程中，原有的图像分割方法都不可避免的会产生误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法其固有的并行性和不易陷入局部最优的特点使之非常适于大规模搜索空间的寻优，因此，己广泛应用于图像处理领域。图像分割是一个在复杂的参量空间中寻找最优分割参量的问题，遗传算法可以有效的寻找参量空间的全局最优值，从而为解决图像分割中的参量选择难题提供了有力的保证。本章将着重讨论基于遗传算法的最大类间方差分割法在图像分割中的应用。

6.2 最大类间方差图像分割的遗传算法描述 正如前文所述，最大类间方差的求解过程就是在解空间中找到一个最优解，使得类间方差最大。为了改进普通最大类间方差法，采用遗传算法，求其寻找最优解的过程进行改进。遗传算法的最大类间方差法步骤如下:

1) 建立初始种群并编码。

在Matlab中，通过函数crtbp建立初始种群，在0~255之间以同等概率随机产生初始种群，通常初始种群的规模选取不易过大。随机的在0~255之间以同等概率生成40个个体A 1 ~A40作为第一次寻优的初始的种群。通过函数bs2rv进行二进制码和实值的转变。因为图像的灰度级在0~255之间，所以将染色体编码成8位二进制码，它代表某个阈值。（函数源代码参见附录[二]、附录[三]）

2) 适应度函数计算各个体的适应度值。采用公式

P1=S1/I; P2=S2/J

F(k)=I*J*(P1-P2)* (P1-P2)/(256*256)

作为适应度函数对个体进行适应度计算。式中，F(k)为适应度函数；I为目标图像的像素数J为背景图像的像素数；S1 为目标图像的像素和，S2为背景图像的像素和。（函数源代码参见附录[四]）

3) 选择：:

与标准遗传算法略有不同，本例未采用赌方法进行选择操作，而是以Matlab中的高级函数select作为选择程序。在这种方法中，需要设定代沟，即整个种群在每一代中没有完全被复制，有部分剩余。本例设代沟GGAP=0.9，即每次遗传后子代数量为父代的90%。（函数源代码参见附录[五]）。

4) 交叉:

在Matlab中使用高级函数recombin实现。即在当前种群中每次选取两个个体按设定的交叉概率（0.7）进行交叉操作，生成新的一代种群; （函数源代码参见附录[六]）。

5) 变异:

在Matlab中使用函数mut实现。即根据一定的变异概率Pm，选取当前种群的每一行对应一个个体并用概率Pm变异每一个元素，从而形成新一代群体。（函数源代码参见附录[七]）

6) 终止

本程序中选择指定代数（50代）作为寻优循环跳出的判断条件。判断跳出条件是否满足，若不满足，则以新生成的群体作为第一代群体，转到步骤3继续寻优，否则转到步骤7。

7) 将最后一代群体中适应度最大的个体作为最优结果，将其反编码（采用bs2rv函数），即为所求的最佳分割阈值。

6.3 实验结果与效果对比图 为了验证算法的效果，选用一幅SHE的JPG图像进行实验，原始图像显示：

图6.1

原始图像

对上图进行灰度变化后的灰度图像如下：

图6.2

灰度图象

在对灰度图像转化为索引图像并将其数据类型转化为双精度型之后的图片如下：

图6.3

索引图像

此时，就可对上图进行基于遗传算法的最大类间方差分割法进行处理了。设定初始群体的数目N=40，交叉概率P c=0. 9，代沟为0.9，变异率为Pm采用默认值。最大迭代数G=50。实验结果及数据如下：

通过50次迭代寻优后，找到最优化阈值M=162:

图6.4

基于遗传算法的最大类间方差法分割后图像

图6.5

直方图双峰法分割后的图像

6.4实验结论 本文所讨论的基于遗传算法的图像分割算法，采用标准遗传算法作为计算流程，但对其中的选择算子进行了改变，用高级选择函数select代替了传统的单一选择算子，使得在每次选择运算后所得的父辈更为健壮，更好的保持了第一代父辈的表现型，使得分割更加精确。通过设计变异概率，使得每次迭代遗传运算后，子代的表现型略有改变，从而更以获得最优的表现型（即最优阈值），减少了迭代寻优次数，降低了程序运行时间。同时考虑到过多迭代不利于降低程序运行时间，以及在寻优过程中的最佳值收敛问题，指定迭代次数为50次时即跳出整个程序，通过反编码求得最优阈值，并通过变量调用，直接应用于下面的分割程序，达到了整个算法的自动完成。

相对于灰度直方图双峰法，本方法对图像的先验信息要求不高，不需要像灰度直方图法那样，先通过获得图像的灰度直方图取得分割阈值后再对图像处理，整个程序的自动化程度高，且对于那些灰度直方图不呈双峰分布的图像，本算法程序一样可以处理，这就扩大了本算法程序的灵活性，从而更具有实际意义。而且，由于灰度直方图双峰法的阈值是通过人眼观察获得，其误差必然大于机器迭代运算所取得的最优阈值，而普通的阈值分割法，如ostu法，虽然实现了阈值的自动选择，但其运算时间与本算法相比偏长，实时性差于本算法。因此，在图像分割算法中，基于遗传算法的图像分割算法更优于其它传统的图像分割算法。

通过上述讨论，以及两种方法的处理结果图片的对比，基于遗传算法的最大类间方差法分割后图像与直方图双峰法分割后的图像像比，效果更明显，且无须事先测量图像的灰度直方图，更加灵活，更加精确。

其相关试验结论列于下表：

基于遗传算法的图象分割实验结论总表:

分割方法

自动化程度

阈值

灰度直方图

计算时间

分割结果

灰度直方图法

无法自动完成

——

基于遗传算法的Ostu法

高

阈值自动指定，阈值M=162，

短于普通Ostu法

普通Ostu法

高

阈值自动指定

偏长

参见参考文章[25]

参 考 文 献 [1]张兆礼，赵春晖，梅晓丹.现代图像处理技术及MAThAB实现.北京:人民邮电出版社，2001.1

[2]陈传波，金先级.数字图像处理[M].北京:机械工业出版社，2004.

[3]夏德深，傅德胜等.现代图象处理技术与应用[M].南京:东南大学出版社，1997.

[4]章毓晋.图象工程(上册)图象处理和分析.北京:清华大学出版社，1999.

[5]王小平，曹立明.遗传算法理论、应用与软件实现.西安:西安交大出版社，2002.

[6]徐立中，数字图像的智能信息处理。北京:国防工业出版社，2001

[7]王耀南，李树涛，毛建旭，计算机图像处理与识别技术，北京:高等教育出版社，2001

[8]雷英杰，张善文，李绪武，周创明.MATLAB遗传算法工具箱及应用，西安：西安电子科技大学出版社

[9]何新贵.模糊知识处理的理论与计算，国防工业出版社，1999

[10]徐建华.图像处理与分析，北京:科学出版，1992.

[11]阮秋琦.数字图象处理学，电子工业出版社，2001

[12]王博等.图像平滑与边缘检测的模糊向量描述，小型微型计算机统，Vol. 20(3), 1999

[13]吴谨，李娟，刘成云，基于最大熵的灰度阈值选取方法，武汉科技大学学报(自然科学版)，Vol. 27, No. 1, Mar, 2004

[14]李鉴庆，左坤隆，图像阈值选取的一种快速算法.计算机与现代化，2001年第6期

[15]魏宝刚，鲁东明，潘云鹤等.多颜色空间上的互式图像分割[J].计算机学报，2001, 24 (7):770-775

[16]杜亚勤，基于模糊集的图像边缘检测技术研究:[硕士学位论文].西安:西安工业学院，2004年4月

[17]王保平，基于模糊技术的图像处理方法研究[博士学位论文]，西安:西安电子科技大学，2004, 9

[18]杜亚娟，潘泉，周德龙等，图像多级灰度非线性模糊增强算法研究，数据采集与处Vo1.14 No.2

[19]Russ J C, The image processing handbook. New York:CRC Press,1994

[20]L A Zadeh.Fuzzy Sets[J].Information and Contro1,1965, (8):338-353

[21]Lotfi A.Zadeh,A fuzzy-set-theoretic interpretation of linguistic hedges, Journal of Cybernetic, 1972, 64(2):4-34

[22]S. K. Pal, R. A. King. Image Enhancement Using Fuzzy Sets. Electron. Let t.，1980 16 (9):376-378.

[23]S. K. PaI, R. :A. King, On Edge Detection of R-Ray Images Using Fuzzy Sets. IEEE Trans.Patt. Anal and MachineIntell.1983,PAMI-5 (1):69-77.

[24]Otsu N. A Threshold Selection Method From Gray Level Histograms. IEEE Trans on Syst Man Cybernet, 1979, SMC-9:62-66

附 录 附录 一 灰度直方图双峰法分割源代码

clear, close all

B=imread('2.jpg'); %读入原始jpg格式图像

figure(1);

imshow(B),title('原始jpg格式图像');

I1=rgb2gray(B); %将原图像转化为灰度图象

figure(2);

imshow(I1),title('灰度格式图像');

[I1,map1]=gray2ind(I1,255); %将灰度图像转化为索引图像

figure(3), imhist(I1) %画出灰度直方图，以判断域值

I1=double(I1); %将unit8数组转化为double型数组

Z=I1 %将double型数组I1转存到Z中

[m, n]=size(Z);

for i=1:m

for j=1:n

if Z(i,j)>240 %灰度值大于域值时是白色

Z(i,j)=256;

end

end

end

figure(4) %画出分割后目标图像

image(Z),title('分割后图像');colormap(map1);

图像I图像格式转化及灰度直方图双峰法分割源代码

clear, close all

B=imread('she.jpg'); %读入原始jpg格式图像she

figure(1);

imshow(B),title('原始jpg格式图像');

I1=rgb2gray(B); %将原图像转化为灰度图象

figure(2);

imshow(I1),title('灰度格式图像');

[I1,map1]=gray2ind(I1,255); %将灰度图像转化为索引图像

figure(3), imhist(I1) %画出灰度直方图，以判断域值

I1=double(I1); %将unit8数组转化为double型数组

Z=I1 %将double型数组I1转存到Z中

[m, n]=size(Z);

for i=1:m

for j=1:n

if Z(i,j)>240 %灰度值大于域值时是白色

Z(i,j)=256;

end

end

end

figure(4) %画出分割后目标图像

image(Z),title('分割后图像');colormap(map1);

图像II图像格式转化及灰度直方图双峰法分割源代码

clear, close all

B=imread('she.jpg'); %读入原始jpg格式图像月亮

figure(1);

imshow(B),title('原始jpg格式图像');

I1=rgb2gray(B); %将原图像转化为灰度图象

figure(2);

imshow(I1),title('灰度格式图像');

[I1,map1]=gray2ind(I1,255); %将灰度图像转化为索引图像

figure(3), imhist(I1) %画出灰度直方图，以判断域值

I1=double(I1); %将unit8数组转化为double型数组

Z=I1 %将double型数组I1转存到Z中

[m, n]=size(Z);

for i=1:m

for j=1:n

if Z(i,j)>240 %灰度值大于域值时是白色

Z(i,j)=256;

end

end

end

figure(4) %画出分割后目标图像

image(Z),title('分割后图像');colormap(map1);

附录 二

Crtbp 函数源代码：（由谢菲尔德大学Andrew Chipperfield编写）

% CRTBP.m - Create an initial population%

% This function creates a binary population of given size and structure.

%

% Syntax: [Chrom Lind BaseV] = crtbp(Nind, Lind, Base)

%

% Input Parameters:

%

% Nind - Either a scalar containing the number of individuals

% in the new population or a row vector of length two

% containing the number of individuals and their length.

%

% Lind - A scalar containing the length of the individual

% chromosomes.

%

% Base - A scalar containing the base of the chromosome

% elements or a row vector containing the base(s)

% of the loci of the chromosomes.

%

% Output Parameters:

%

% Chrom - A matrix containing the random valued chromosomes

% row wise.

%

% Lind - A scalar containing the length of the chromosome.

%

% BaseV - A row vector containing the base of the

% chromosome loci.

% Author: Andrew Chipperfield

% Date: 19-Jan-94

function [Chrom, Lind, BaseV] = crtbp(Nind, Lind, Base)

nargs = nargin ;

% Check parameter consistency

if nargs >= 1, [mN, nN] = size(Nind) ; end

if nargs >= 2, [mL, nL] = size(Lind) ; end

if nargs == 3, [mB, nB] = size(Base) ; end

if nN == 2

if (nargs == 1)

Lind = Nind(2) ; Nind = Nind(1) ; BaseV = crtbase(Lind) ;

elseif (nargs == 2 & nL == 1)

BaseV = crtbase(Nind(2),Lind) ; Lind = Nind(2) ; Nind = Nind(1) ;

elseif (nargs == 2 & nL > 1)

if Lind ~= length(Lind), error('Lind and Base disagree'); end

BaseV = Lind ; Lind = Nind(2) ; Nind = Nind(1) ;

end

elseif nN == 1

if nargs == 2

if nL == 1, BaseV = crtbase(Lind) ;

else, BaseV = Lind ; Lind = nL ; end

elseif nargs == 3

if nB == 1, BaseV = crtbase(Lind,Base) ;

elseif nB ~= Lind, error('Lind and Base disagree') ;

else BaseV = Base ; end

end

else

error('Input parameters inconsistent') ;

end

% Create a structure of random chromosomes in row wise order, dimensions

% Nind by Lind. The base of each chromosomes loci is given by the value

% of the corresponding element of the row vector base.

Chrom = floor(rand(Nind,Lind).*BaseV(ones(Nind,1),:)) ;

% End of file

附录 三

Bs2rv函数源代码： （由谢菲尔德大学Andrew Chipperfield编写）

% BS2RV.m - Binary string to real vector

%

% This function decodes binary chromosomes into vectors of reals. The

% chromosomes are seen as the concatenation of binary strings of given

% length, and decoded into real numbers in a specified interval using

% either standard binary or Gray decoding.

%

% Syntax: Phen = bs2rv(Chrom,FieldD)

%

% Input parameters:

%

% Chrom - Matrix containing the chromosomes of the current

% population. Each line corresponds to one

% individual's concatenated binary string

% representation. Leftmost bits are MSb and

% rightmost are LSb.

%

% FieldD - Matrix describing the length and how to decode

% each substring in the chromosome. It has the

% following structure:

%

% [len; (num)

% lb; (num)

% ub; (num)

% code; (0=binary | 1=gray)

% scale; (0=arithmetic | 1=logarithmic)

% lbin; (0=excluded | 1=included)

% ubin]; (0=excluded | 1=included)

%

% where

% len - row vector containing the length of

% each substring in Chrom. sum(len)

% should equal the individual length.

% lb,

% ub - Lower and upper bounds for each

% variable.

% code - binary row vector indicating how each

% substring is to be decoded.

% scale - binary row vector indicating where to

% use arithmetic and/or logarithmic

% scaling.

% lbin,

% ubin - binary row vectors indicating whether

% or not to include each bound in the

% representation range

%

% Output parameter:

%

% Phen - Real matrix containing the population phenotypes.

%

% Author: Carlos Fonseca, Updated: Andrew Chipperfield

% Date: 08/06/93, Date: 26-Jan-94

function Phen = bs2rv(Chrom,FieldD)

% Identify the population size (Nind)

% and the chromosome length (Lind)

[Nind,Lind] = size(Chrom);

% Identify the number of decision variables (Nvar)

[seven,Nvar] = size(FieldD);

if seven ~= 7

error('FieldD must have 7 rows.');

end

% Get substring properties

len = FieldD(1,:);

lb = FieldD(2,:);

ub = FieldD(3,:);

code = ~(~FieldD(4,:));

scale = ~(~FieldD(5,:));

lin = ~(~FieldD(6,:));

uin = ~(~FieldD(7,:));

% Check substring properties for consistency

if sum(len) ~= Lind,

error('Data in FieldD must agree with chromosome length');

end

if ~all(lb(scale).*ub(scale)>0)

error('Log-scaled variables must not include 0 in their range');

end

% Decode chromosomes

Phen = zeros(Nind,Nvar);

lf = cumsum(len);

li = cumsum([1 len]);

Prec = .5 .^ len;

logsgn = sign(lb(scale));

lb(scale) = log( abs(lb(scale)) );

ub(scale) = log( abs(ub(scale)) );

delta = ub - lb;

Prec = .5 .^ len;

num = (~lin) .* Prec;

den = (lin + uin - 1) .* Prec;

for i = 1:Nvar,

idx = li(i):lf(i);

if code(i) % Gray decoding

Chrom(:,idx)=rem(cumsum(Chrom(:,idx)')',2);

end

Phen(:,i) = Chrom(:,idx) * [ (.5).^(1:len(i))' ];

Phen(:,i) = lb(i) + delta(i) * (Phen(:,i) + num(i)) ./ (1 - den(i));

end

expand = ones(Nind,1);

if any(scale)

Phen(:,scale) = logsgn(expand,:) .* exp(Phen(:,scale));

end

附录 四 适应度函数target源代码：

function f=target(T,M) %适应度函数,T为待处理图像,M为域值序列

[U, V]=size(T);

W=, , length(M);

f=zeros(W,1);

for k=1:W

I=0;s1=0;J=0;s2=0; %统计目标图像和背景图像的像素数及像素之和

for i=1:U

for j=1:V

if T(i,j)<=M(k)

s1=s1+T(i,j);I=I+1;

end

if T(i,j)>M(k)

s2=s2+T(i,j);J=J+1;

end

end

end

if I==0, p1=0; else p1=s1/I; end

if J==0, p2=0; else p2=s2/J; end

f(k)=I*J*(p1-p2)*(p1-p2)/(256*256);

end

附录 五 选择函数Select源代码：（由谢菲尔德大学Hartmut Pohlheim编写）

% SELECT.M (universal SELECTion)

%

% This function performs universal selection. The function handles

% multiple populations and calls the low level selection function

% for the actual selection process.

%

% Syntax: SelCh = select(SEL_F, Chrom, FitnV, GGAP, SUBPOP)

%

% Input parameters:

% SEL_F - Name of the selection function

% Chrom - Matrix containing the individuals (parents) of the current

% population. Each row corresponds to one individual.

% FitnV - Column vector containing the fitness values of the

% individuals in the population.

% GGAP - (optional) Rate of individuals to be selected

% if omitted 1.0 is assumed

% SUBPOP - (optional) Number of subpopulations

% if omitted 1 subpopulation is assumed

%

% Output parameters:

% SelCh - Matrix containing the selected individuals.

% Author: Hartmut Pohlheim

% History: 10.03.94 file created

function SelCh = select(SEL_F, Chrom, FitnV, GGAP, SUBPOP);

% Check parameter consistency

if nargin < 3, error('Not enough input parameter'); end

% Identify the population size (Nind)

[NindCh,Nvar] = size(Chrom);

[NindF,VarF] = size(FitnV);

if NindCh ~= NindF, error('Chrom and FitnV disagree'); end

if VarF ~= 1, error('FitnV must be a column vector'); end

if nargin < 5, SUBPOP = 1; end

if nargin > 4,

if isempty(SUBPOP), SUBPOP = 1;

elseif isnan(SUBPOP), SUBPOP = 1;

elseif length(SUBPOP) ~= 1, error('SUBPOP must be a scalar'); end

end

if (NindCh/SUBPOP) ~= fix(NindCh/SUBPOP), error('Chrom and SUBPOP disagree'); end

Nind = NindCh/SUBPOP; % Compute number of individuals per subpopulation

if nargin < 4, GGAP = 1; end

if nargin > 3,

if isempty(GGAP), GGAP = 1;

elseif isnan(GGAP), GGAP = 1;

elseif length(GGAP) ~= 1, error('GGAP must be a scalar');

elseif (GGAP < 0), error('GGAP must be a scalar bigger than 0'); end

end

% Compute number of new individuals (to select)

NSel=max(floor(Nind*GGAP+.5),2);

% Select individuals from population

SelCh = [];

for irun = 1:SUBPOP,

FitnVSub = FitnV((irun-1)*Nind+1:irun*Nind);

ChrIx=feval(SEL_F, FitnVSub, NSel)+(irun-1)*Nind;

SelCh=[SelCh; Chrom(ChrIx,:)];

end

% End of function

附录 六 交叉函数recombin的源代码：（由谢菲尔德大学Hartmut Pohlheim编写）

% RECOMBIN.M (RECOMBINation high-level function)

%

% This function performs recombination between pairs of individuals

% and returns the new individuals after mating. The function handles

% multiple populations and calls the low-level recombination function

% for the actual recombination process.

%

% Syntax: NewChrom = recombin(REC_F, OldChrom, RecOpt, SUBPOP)

%

% Input parameters:

% REC_F - String containing the name of the recombination or

% crossover function

% Chrom - Matrix containing the chromosomes of the old

% population. Each line corresponds to one individual

% RecOpt - (optional) Scalar containing the probability of

% recombination/crossover occurring between pairs

% of individuals.

% if omitted or NaN, 1 is assumed

% SUBPOP - (optional) Number of subpopulations

% if omitted or NaN, 1 subpopulation is assumed

%

% Output parameter:

% NewChrom - Matrix containing the chromosomes of the population

% after recombination in the same format as OldChrom.

% Author: Hartmut Pohlheim

% History: 18.03.94 file created

function NewChrom = recombin(REC_F, Chrom, RecOpt, SUBPOP);

% Check parameter consistency

if nargin < 2, error('Not enough input parameter'); end

% Identify the population size (Nind)

[Nind,Nvar] = size(Chrom);

if nargin < 4, SUBPOP = 1; end

if nargin > 3,

if isempty(SUBPOP), SUBPOP = 1;

elseif isnan(SUBPOP), SUBPOP = 1;

elseif length(SUBPOP) ~= 1, error('SUBPOP must be a scalar'); end

end

if (Nind/SUBPOP) ~= fix(Nind/SUBPOP), error('Chrom and SUBPOP disagree'); end

Nind = Nind/SUBPOP; % Compute number of individuals per subpopulation

if nargin < 3, RecOpt = 0.7; end

if nargin > 2,

if isempty(RecOpt), RecOpt = 0.7;

elseif isnan(RecOpt), RecOpt = 0.7;

elseif length(RecOpt) ~= 1, error('RecOpt must be a scalar');

elseif (RecOpt < 0 | RecOpt > 1), error('RecOpt must be a scalar in [0, 1]'); end

end

% Select individuals of one subpopulation and call low level function

NewChrom = [];

for irun = 1:SUBPOP,

ChromSub = Chrom((irun-1)*Nind+1:irun*Nind,:);

NewChromSub = feval(REC_F, ChromSub, RecOpt);

NewChrom=[NewChrom; NewChromSub];

end

% End of function

附录 七 变异函数mut源代码 ：（由谢菲尔德大学Andrew Chipperfield编写）

% MUT.m

%

% This function takes the representation of the current population,

% mutates each element with given probability and returns the resulting

% population.

%

% Syntax: NewChrom = mut(OldChrom,Pm,BaseV)

%

% Input parameters:

%

% OldChrom - A matrix containing the chromosomes of the

% current population. Each row corresponds to

% an individuals string representation.

%

% Pm - Mutation probability (scalar). Default value

% of Pm = 0.7/Lind, where Lind is the chromosome

% length is assumed if omitted.

%

% BaseV - Optional row vector of the same length as the

% chromosome structure defining the base of the

% individual elements of the chromosome. Binary

% representation is assumed if omitted.

%

% Output parameter:

%

% NewChrom - A Matrix containing a mutated version of

% OldChrom.

%

% Author: Andrew Chipperfield

% Date: 25-Jan-94

function NewChrom = mut(OldChrom,Pm,BaseV)

% get population size (Nind) and chromosome length (Lind)

[Nind, Lind] = size(OldChrom) ;

% check input parameters

if nargin < 2, Pm = 0.7/Lind ; end

if isnan(Pm), Pm = 0.7/Lind; end

if (nargin < 3), BaseV = crtbase(Lind); end

if (isnan(BaseV)), BaseV = crtbase(Lind); end

if (isempty(BaseV)), BaseV = crtbase(Lind); end

if (nargin == 3) & (Lind ~= length(BaseV))

error('OldChrom and BaseV are incompatible'), end

% create mutation mask matrix

BaseM = BaseV(ones(Nind,1),:) ;

% perform mutation on chromosome structure

NewChrom = rem(OldChrom+(rand(Nind,Lind)<Pm).*ceil(rand(Nind,Lind).*(BaseM-1)),BaseM);

附录 八

基于遗传算法的最大类间方差法对JPG格式图像分割的程序源代码：

clear, close all

B=imread('she.jpg'); %读入原始jpg格式图像

figure(1);

imshow(B),title('原始jpg格式图像');

I1=rgb2gray(B); %将原图像转化为灰度图象

figure(2);

imshow(I1),title('灰度格式图像');

BW1 = edge(I1,'sobel');

BW2 = edge(I1,'canny');

figure(6),imshow(BW1),title('边缘检测1'); %边缘检测

figure(5), imshow(BW2),title('边缘检测2');

[I1,map1]=gray2ind(I1,255); %将灰度图像转化为索引图像

I1=double(I1); %将unit8数组转化为double型数组

Z=I1 %将double型数组I1转存到Z中

figure(3) %画出未进行分割的原始图像

image(Z),title('未进行分割的原始图像');colormap(map1);

NIND=40; %个体数目(Number of individuals)

MAXGEN=50; %最大遗传代数(Maximum number of generations)

PRECI=8; %变量的二进制位数(Precision of variables)

GGAP=0.9; %代沟(Generation gap)

FieldD=[8;1;256;1;0;1;1]; %建立区域描述器(Build field descriptor)

Chrom=crtbp(NIND,PRECI); %创建初始种群

gen=0;

phen=bs2rv(Chrom,FieldD); %初始种群十进制转换

ObjV=target(Z,phen); %计算种群适应度值

while gen<MAXGEN %代沟(Generation gap)

FitnV=ranking(-ObjV); %分配适应度值(Assign fitness values)

SelCh=select('sus',Chrom,FitnV,GGAP); %选择

SelCh=recombin('xovsp',SelCh,0.7); %重组

SelCh=mut(SelCh); %变异

phenSel=bs2rv(SelCh,FieldD); %子代十进制转换

ObjVSel=target(Z,phenSel);

[Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入

gen=gen+1;

end

[Y, I]=max(ObjV);

M=bs2rv(Chrom(I,:),FieldD); %估计域值

[m, n]=size(Z);

for i=1:m

for j=1:n

if Z(i,j)>M %灰度值大于域值时是白色

Z(i,j)=256;

end

end

end

figure(4) %画出分割后目标图像

image(Z),title('分割后图像');colormap(map1);

target求适应度函数代码：

function f=target(T,M) %适应度函数,T为待处理图像,M为域值序列

[U, V]=size(T);

W=length(M);

f=zeros(W,1);

for k=1:W

I=0;s1=0;J=0;s2=0; %统计目标图像和背景图像的像素数及像素之和

for i=1:U

for j=1:V

if T(i,j)<=M(k)

s1=s1+T(i,j);I=I+1;

end

if T(i,j)>M(k)

s2=s2+T(i,j);J=J+1;

end

end

end

if I==0, p1=0; else p1=s1/I; end

if J==0, p2=0; else p2=s2/J; end

f(k)=I*J*(p1-p2)*(p1-p2)/(256*256);

end;