1、 本科 毕业 设计 (论文 ) （二零 届） 基于遗传算法的 WEB 图像分割研究与实现 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘 要 : 随着信息时代 的到来 ，数字图像大量涌入互联网， 并 已成为 人们 生活 中的 一个重要组成 部分。 WEB 图像分割是图像处理 中 的一个 关键步骤 ,其 目的是 将WEB图像中的 目标与背景分离， 能够为图像处理中的后续环节 提供 基础 。 开发一种 有效 而快速 的图像分割方法已成为当前 图像处理、 计算机视觉 和 目标识别等领域的 一个 研究热点。本文 提出了一种基于 直方图熵和改进遗传算法的
2、图像 分割 方法，能够利用 遗传算法 带有的 优化 操作 的 高 效 性， 自适应 加以 调整，从而 大幅度地缩短了寻找最优 阈值 的 时间。此外，对于遗传算法 中存在 的不足之处 ， 提出了一些修 正。通过 实验 对比可见 ， 提出的 算法 不仅得到了 更好的分割 效果 ， 而且 比传统阈值分割方法 的计算速度要快 。 关键词： 遗传算法；图像分割； 最 大类间方差 法 ；最佳直方图 熵 法 II The Research and Implementation of WEB Image Segmentation Based on Genetic Algorithm Abstract： Wit
3、h the coming of information age, a large number of digital images are emerged on the Internet, and they are acted as an important part in our daily lives. WEB image segmentation is a key step in image processing. And its aim is to distinguish the objects and background within an image. The segmentat
4、ion process will provide a basis for the following steps in image processing. Thus, it has been a research focus to develop an effective and fast segmentation method in image processing, computer vision, and target recognition. In this paper, we present a new image segmentation method based on histo
5、gram entropy and genetic algorithm (GA), which can adaptively adjust thresholds with the help of the efficient of GA in optimization. It can shorten the times took for finding the optimal thresholds as well. In addition, as for the inadequacies in GA, we propose some improvement schemes. In the expe
6、riment, our method is compared with traditional threshold-based segmentation methods. From the experimental results, we can see that our method achieves better segmentation result and faster computational speed as well. Key words: genetic algorithm (GA), image segmentation, Otsu method, KSW (Automat
7、ic thresholding of the best entropy) method目 录 1 绪论 . 1 1.1 研究的背景、目的和意义 . 1 1.2 本文的主要内容 . 2 1.3 本文的组织结构 . 3 2 WEB 图像分割相关研究 . 4 2.1 图像分割简介 . 4 2.2 图像分割阈值选取技术 . 4 2.3 阈值分割简介 . 5 3 基于遗传算法的 WEB图像分割法 . 6 3.1 最大类间方差法 . 6 3.1.1 一维 Otsu算法 . 6 3.1.2 二维 Otsu算法 . 7 3.1.3 Otsu 阈值分割的遗传算法设计 . 8 3.2 基于遗传算法的 KSW熵方法
8、 . 10 3.2.1 单阈值分割的遗传算法设计 . 11 3.2.2 双阈值分割的遗传算法设计 . 12 4 实验部分 . 14 4.1 实验设计 . 14 4.2实验结果及分析 . 14 5 结 论 . 22 致 谢 . 错误 !未定义书签。 参考文献 . 23 1 1 绪论 1.1 研究的背景、目的和意义 随着信息时代的到来 ,大量的数字图像纷纷涌入到互联网 ,逐渐成为我们生活中的一部分。对 WEB图像进行分割是对图像信息的提取和处理的关键步骤。图像分割的目的是将目标和背景分离 ,为计算机视觉的后续处理提供依据。 寻找一种快速而有效的图像分割方法现已成为当前计算机视觉、自动目标识别和图像
9、处理等领域研究的一个热点 1。 图像分割是图像处理中的一项关键技术 ,图像分割就是把图像划分成若干互补交叠区域的像素的集合 ,这些区域要么对当前的分割有意义 ,是目标物体与背景的边缘 ,要么有助于说明它们之间的对应关系。自适应图像分割为了响应参数的变化需要修改控制能力 ,保证图像在不同环境条件下的质量 2。随着 20世纪数字图像处理技术的兴起而受到人们广泛的深入的研究 ,提出了很多优秀的算法。但这些算法往往只在某一个方面表现出优秀的解决问题的能力 ,在另外的一些领域则需要其他的图像分割算法。因此 ,现有的图像分割算法并没有一般意义上的通用性。另外 ,图像分割效果的评估也没有相应的评判标准 ,通
10、常的处理方式只能是具体问题具体分析。在这其中遗传算法是 解决图像分割问题的最优算法之一 3。它不涉及具体的研究领域和内容 ,只关心相应的目标函数和辅助函数 ,即所谓鲁棒性。因此广泛应用于工业工程、计算科学、工控系统、交通、计算机、通信、电子科学与技术等领域。 遗传算法 （ Genetic Algorithm） 是一类借鉴生物界的进化规律（适者生存 ,优胜劣汰遗传机制）演化而来的随机化搜索方法 1。它是由 美国 的 J.Holland教授 1975年首先提 出 ,其主要特点是直接对结构对象进行操作 ,不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法 ,能
11、自动获取和指导优化的搜索空间 ,自适应地调整搜索方向 ,不需要确定的规则 2。 图像分割伴随着数字图像处理技术在实际中已经得到广泛的应用 ,例如在工业工程 ,产品检验 ,工业控制 ,图像处理 ,卫星图片 ,生物医学图像分析、保安监控以及军事、卫生、农业工程等诸多领域 3。概括来说 ,在各种图像应用中 ,只需对图像物体目标进行提取、测量等进一步操作都离不开图像分割 ,图像分割往往是这些处理步骤的 准备阶段 ,图像分割的效果直接影响后续任务的有效性 ,因此图像分割具有重要的研究意义 3。而遗传算法是一种通用的算法 4。 进入 90年代 ,遗传算法迎来了兴盛发展时期 ,无论是理论研究还是应用研究都成
12、了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃 ,不但它的应用领域扩大 ,而且利用遗传算法进行优化和规则学习的能力也显著提高 ,同时产业应用方面的研究也在摸索之 中2 4。此外一些新的理论和方法在应用研究中亦得到了迅速的发展 ,这些无疑均给遗传算法增添了新的活力 5。遗传算法的应用研究已从初期的组合优化求解扩展到了许 多更新、更工程化的应用方面 6。 其中图像分割是一大研究方向。谭志存 ,鲁瑞华提出建立在最大类间方差基础上的改进遗传算法 7。基于基因位的交叉概率充分体现了不同基因位不同程度的重要性 ,避免了传统等概率基因位交叉的缺点；基于染色体的交叉概率有效地保护了优良个体 ,算法也充
13、分利用了待分割图像的直方图信息 ,一定程度上减小了寻优空间。但由于引进了自适应算法 ,每一代都要进行染色体和基因位概率的运算 ,占用的运算时间较大 ,如何提高运算效率和解决最大类间方差的局限性是今后研究的方向 7。 最早将遗传算法用于图像分割的 Kapur 等人提出的最佳熵阈值确定法 (简称 KSW熵法 )中 ,进行了针对图像分割遗传程序所需的参数设计。 KSW 熵方法具有很多优点 ,但同时也存在弱点 :需要大量的运算时间 ,特别是在计算多阈值时 . 因此需要引入优化算法。 J . Holland 的遗传算法是具有鲁棒性和自适应性的搜索方法。采用遗传算法实现单阈值和多阈值图像分割 ,实验结果表
14、明分割速度快于传统的 KSW熵法 ,缩短了运算时间 3。而最大类别方差法是 Otsu在1979年提出的 ,在图像分割中有大量应用。 Otsu法利用了灰度直方图的 0阶和 1阶矩 ,它不仅是图像分割的 重要方法 , 而且也是模式识别中非监督分类问题的判断依据。 当前 ,图像分割与机器学习、神经网络、统计学、人工智能等学科的先进思想和理论紧密结合已经成为一个重要的趋势。本文针对基于遗传算法的 WEB图像分割方法中存在的最佳阈值的确定和参数设置的优化问题 ,将遗传算法和 KSW熵法相结合 ,将信息论中 Shannon 熵概念用于图像分割时 ,测量图像灰度直方图的熵 ,由此找出最佳阈值 ,其出发点是使
15、图像中目标与背景分布的信息量最大 .提出一种有效的混合图像分割算法 ,同时 ,在分割过程中尽可能地提高运行效率。 本文针对图像分割中现存的 一个重要而关键的问题进行研究 ,通过提出有效的方法 ,改进分割的精度和效率 ,这对医学、数字服务、网络安全相关领域的发展必将具有广泛的应用前景和重要的实用价值。 1.2 本文的主要内容 标准的遗传算法本身存在一些不足 ,对它进行如下两点修正： (1)在上述的选择方案中 ,由于选择方案是随机的 ,有可能适应度大的个体没有选中 ,适应度小的反而有可能被选中以产生下一代个体。根据类比生物论的思想 ,适应度小的个体产生下一代的质量一般不会很高。为了克服 GA的这个
16、弊端 ,在用赌轮法进行选择以前。先用精英策略选择一次 ,即按照一定的概3 率。 使那些适应度比较高的个体直接进入下一代； (2)在上述步骤中 ,每次选出来两个个体 ,它们之间先进行交叉操作 ,再分别对两个新个体进行变异操作 ,最后用新得到的新个体代替旧个体。但是新个体可能比旧个体的适应度小 ,即可能出现退化现象 ,为了减少退化的发生 ,使新个体以一定的概率代替旧个体 8。本文提出基于遗传算法的 KSW熵阈值分割方法对 WEB图像分割。 本文主要的研究内容如下： 基于遗传算法的 KSW熵阈值分割方法：将信息论中熵概念应用于图像分割时 ,其依据是使图像中目标与背景分布的信息量最大 ,即通过分析图像
17、灰度直方图的熵 ,找出最佳阈值。传统的 KSW熵法对于每个初始闽值要计算一次质量评估函数 ,然后取最大值来确定最佳门限 ,分割速度主要由质量评估函数的计算速度。对于 256级灰度的运算速度为 256T,实验结果表明当用改进的 GA的 KSW熵法采用每代 20个体 ,一般繁殖到第 6代就达到最优阈值 ,运算速度为 120T,比简单的 KSW熵法的运算速度小。 1.3 本文的组织结构 本文主要章节安排如下： 1 绪论 主要讨论了本文研究的背景、目的和意义 ,并且简要地概括了本文的主要内容和创新点。 2 图像分割相关研究 本章首先讨论了图像分割的发展过 程与研究现状 ,图象分割 的 三种不同的途径
18、,其一是将各象素划归到相应物体或区域的象素聚类方法即区域法 ,其二是通过直接确定区域间的边界来实现分割的边界方法 ,其三是首先检测边缘象素再将边缘象素连接起来构成边界形成分割。 并且介绍了研究中使用的图像分割的阈值选取技术概念及相关方法 ,最后介绍了阈值分割的技术。 3 基于遗传算法的 WEB图像分割方法 本章首先介绍了 最大类间方差法，提出了基于遗传算法的最大类间方差法的设计 ,然后提出了基于遗传算法的 KSW法，通过单阈值和双阈值的分割对 KSW法进行了诠释。最后对上述算法进行了实 验，并对实验结果进行了分析。 4 结论 本章主要的内容是总结了本文的研究内容 ,并且对未来的研究进行了展望。
19、 4 2 WEB 图像分割相关研究 2.1 图像分割简介 所谓图像分割是指根据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相交的区域 ,使得这些特征在同一区域内 ,表现出一致性或相似性 ,而在不同区域间表现出明显的不同。简单的讲 ,就是在一幅图像中 ,把目标从背景中分离出来 ,以便于进一步处理。图像分割是图像处理与计算机视觉领域低层次视觉中最为基础和重要的领域之一 ,它是对图像进行视觉分析和模式识别的 基本前提 8。同时它也是一个经典难题 ,到目前为止既不存在一种通用的图像分割方法 ,也不存在一种判断是否分割成功的客观标准 9。 图象分割有三种不同的途径 ,其一是将各象素划归到相
20、应物体或区域的象素聚类方法即区域法 ,其二是通过直接确定区域间的边界来实现分割的边界方法 ,其三是首先检测边缘象素再将边缘象素连接起来构成边界形成分割 9。早期的图像分割方法可以分为两大类。一类是边界方法 ,这种方法假设图像分割结果的某个子区域在原来图像中一定会有边缘存在；一类是区域方法 ,这种方法假设图像分割结果的某个子区域一定会有相同 的性质 ,而不同区域的像素则没有共同的性质。这两种方法都有优点和缺点 ,有的学者考虑把两者结合起来进行研究。现在 ,随着计算机处理能力的提高 ,很多方法不断涌现 ,如基于彩色分量分割、纹理图像分割 9。 2.2 图像分割阈值选取技术 阈值分割法是一种基于区域
21、的图像分割技术 ,其基本原理是：通过设定不同的特征阈值 ,把图像象素点分为若干类。常用的特征包括：直接来自原始图像的灰度或彩色特征；由原始灰度或彩色值变换得到的特征 10。 阈值法是一种传统的图像分割方法 ,因其实现简单、计算量小、性能较稳定而成为图像分割中最基 本和应用最广泛的分割技术。已被应用于很多的领域 ,例如 ,在红外技术应用中 ,红外无损检测中红外热图像的分割 ,红外成像跟踪系统中目标的分割；在遥感应用中 ,合成孔径雷达图像中目标的分割等；在医学应用中 ,血液细胞图像的分割 ,磁共振图像的分割；在农业工程应用中 ,水果品质无损检测过程中水果图像与背景的分割。在工业生产中 ,机器视觉运
22、用于产品质量检测等等 11。在这些应用中 ,分割是对图像进一步分析、识别的前提 ,分割的准确性将直接影响后续任务的有效性 ,其中阈值的选取是图像阈值分割方法中的关键技术 12。 5 2.3 阈值分割 简介 图像阈值化分割是一种最常用 ,同时也是最简单的图像分割方法 ,它特别适用于目标和背景占据不同灰度级范围的图像。它不仅可以极大的压缩数据量 ,而且也大大简化了分析和处理步骤 ,因此在很多情况下 ,是进行图像分析、特征提取与模式识别之前的必要的图像预处理过程。图像阈值化的目的是要按照灰度级 ,对像素集合进行一个划分 ,得到的每个子集形成一个与现实景物相对应的区域 ,各个区域内部具有一致的属性 ,
23、而相邻区域布局有这种一致属性。这样的划分可以通过从灰度级出发选取一个或多个阈值来实现 8。 设原始图像为 f(x,y),按照一定的 准则在 f(x,y)中找到特征值 T,将图像分割为两个部分 ,分割后的图像为 ., ., 10 tyxfb tyxfbyxg （ 2.1） 若取 ： b0=0（黑） ,b1=1（白） ,即为我们通常所说的图像二值化。 图 2.1 一般意义下 ,阈值运算可以看作是对图像中某点的灰度、该点的某种局部特性以及该点在图像中的位置的一种函数 ,这种阈值函数可记作 T(x, y, N(x, y),f(x, y) 式中 ,f(x, y)是点 (x, y)的灰度值； N(x, y
24、)是点 (x, y)的局部邻域特性根 据对 T 的不同约束 ,可以得到 3 种不同类型的阈值 37,即点相关的全局阈值 T T(f(x, y) (只与点的灰度值有关 )区域相关的全局阈值 T T(N(x, y),f(x, y) (与点的灰度值和该点的局部邻域特征有关 )局部阈值或动态阈值 T T(x, y, N(x, y),f(x, y)(与点的位置、该点的灰度值和该点邻域特征有关 )13。 图像阈值化这个看似简单的问题 ,在过去的四十年里受到国内外学者的广泛关注 ,产生了数以百计的阈值选取方法 14,但是遗憾的是 ,如同其他图像分割算法一样 ,没有一个现有方法对各种各样的图像都能得到令人满意
25、的结果 ,甚至也没有一个理论指导我们选择特定方法处理特定图像 8。 6 3 基于遗传算法的 WEB 图像分割法 3.1 最大类间方差法 由 Otsu 于 1978 年提出的最大类间方差法以其计算简单、稳定有效 ,一直广为使用。从模式识别的角度看 ,最佳阈值应当产生最佳的目标类与背景类的分离性能 ,此性能我们用类别方差来表征 ,为此引入类内方差 2W 、类间方差 2B 和总体方差 2T ,并定义三个等效的准则测量 14： 22WB , 22WT , 22TB . (3.1)鉴于计算量的考虑 ,人们一般通过优化第三个准则获取阈值。此方法也有其缺陷 ,当图像中目标与背景的大小之比很小时 ,方法失效。
26、在实际运用中 ,往往使用以下简化计算公式： 222 )()( BBAA ww (3.2) 其中 , 2 为两类间最大方差 ,WA 为 A类概率 , A 为 A类平均灰度 ,WB为 B类概率 , B 为B类平均灰度 , 为图像总体平均灰度 15。 即阈值 T将图像分成 A,B两部分 ,使得两类总方差 2 （ T）取最大值的 T,即为最佳分割阈值 16。 3.1.1 一维 Otsu 算法 设图像 f 中 ,灰度值为 i 的象素的数目为 Ni,总象素为： iLli nN ,各灰度 K 为门限将图像分为两个区域（目标和背景） ,灰度为 l-k的象素和灰度为 K+1-L 的象素分别属于区域A(目标 )和 B(背景 ),则区域 A和 B的概率分别为 ikilA pw (3.3) 和 iklB pw 0 1 , (3.4) 若定义 )(1),( kwwkww BA (3.5)
