遗传算法实现图像分割（MATLAB）
本⽂是对于Omar Banimelhem and Yahya Ahmed Yahya 发表论⽂《Multi-Thresholding Image Segmentation Using Genetic Algorithm》的翻译。
⽤遗传算法对图像进⾏多阈值分割（Multi-Thresholding Image Segmentation Using Genetic Algorithm）
摘要：图像分割是计算机视觉和图像处理中的⼀个重要问题。将⼀幅数字图像分成多个区域或者集合。在多个问题和应⽤中，图像分割变得越来越重要，从⽽使得研究者提出并改进图像分割过程的算法。图像分割的⽅法有很多。本⽂使⽤基于遗传算法的阈值技术来寻不同⽬标和背景间的最优阈值。
关键词：图像分割；阈值；遗传算法。
1 引⾔
图像分割是区分⼀幅图像中的⽬标和背景的过程。对于许多依赖于计算机视觉的应⽤，如医学成像、卫星图像中的⽬标定位、机器视觉、指纹和⼈脸识别、农业成像等，图像分割是⼀个重要的预处理任务。图像分割阶段的准确性会对图像处理的后续阶段产⽣很⼤的影响。许多研究者对于图像分割问题已研究了多年；然⽽，由于图像具有如不同形式的直⽅图的特点，所以图像分割问题仍是⼀个公开的研究问题，
需要进⼀步的研究。
最近，提出了许多技术，包括基于图形的算法边缘检测的算法进和基于阈值的算法[1-5]，⽤于图像分割。由于阈值技术简单，在过去⼏年中得到了很⼤的关注。
另⼀⽅⾯，由于遗传算法能够为许多实际应⽤提供近似最优解，所以最近⽤其解决图像分割问题。⼀般来说，遗传算法（Genetic Algorithm，GA）是模拟⾃然选择的⽣物进化过程⼀种软计算模型（a soft computational model）[6]。
本⽂采⽤基于遗传算法的图像阈值⽅法，通过寻阈值，将阈值问题转换为优化问题。该⽅法的⽬标是最⼤化⽬标间的类内⽅差和最⼩化⽬标像素之中的背景像素间的类间⽅差[7]。在每个⽬标中，像素的灰度间的同质性会影响图像分割质量。如果⽬标像素灰度变化，结果将有可能变差[7]。
论⽂的其余部分组织如下。第2节详细描述了图像阈值⽅法。第3节讨论了遗传算法的概念。第4节讨论所提⽅法。第5节给出仿真结果。最后，第6节对本⽂进⾏总结。
2 图像阈值
数字图像可以视为⼆维矩阵或者⼆元函数。它由称为像素的离散点组成。在彩⾊图像中，每个像素有三个值：红、绿和蓝。每个值在0到L-1的范围中，其中L是精度的数量。另⼀⽅⾯，灰度图像由像素组
成，其中每个像素只有0到L-1之间的⼀个值，称之为灰度。对于许多图像处理问题，处理灰度图像⽐处理彩⾊图像更简单、有效。因此，在使⽤图像处理算法前，会将彩⾊图像转换为灰度图像。最常⽤的灰度为256（即每个像素值在0到255之间）。
图像阈值是⼀种⽤于灰度图像的图像分割⽅法。该想法是为了到⼀个阈值，如果像素低于阈值，就认为是背景，否则认为是⽬标的⼀部分。例如，图1-a中的图像有⼀个⽬标和背景。图像分割的结果如图1-b所⽰。
图1：原始图像（a）和分割结果（b）
基于阈值的⽅法分为单级阈值（single-level thresholding）和多级阈值（multi-level thresholding）。多阈值⽅法通常是通过寻将多个⽬标分开的多个阈值作为图像阈值。例如，图2-a中的图像有三个⽬标，图像分割的结果如图2-b所⽰。⼀般⽽⾔，分割⼀幅有n个⽬标和背景的图像，可以使⽤n个阈值。matlab直方图
图2：⼀幅图像（a）有3个⽬标和图像（b）是分割结果
对于到分开⽬标的最优阈值，处理图像的统计⽐处理图像本⾝要简单。图像直⽅图统计是图像中每个灰度出现的频率的⼀维表⽰。通过计算具有相同灰度的像素的数⽬得到。图1中的图像的图像直⽅图如图3所⽰。
图3：图1的图像直⽅图
将彩⾊图像转换为灰度图像，然后⽤图像的⼀维直⽅图简化阈值分割过程，提⾼计算效率，可以⽤于许多实时应⽤。
从图像直⽅图中到阈值的⽅法有很多。在单阈值的情况下，我们可以尝试0到L-1之间的所以值，然后我们选择得到最好的分割结果的值作为阈值。
然⽽，对于多阈值分割，尝试所有可能的组合需要L×(L-1)×…×(L-t+1)次，其中t是阈值的个数。很明显，尝试错有可能的阈值的朴素⽅法（naïve method）对于更⼤的t⽽⾔，并不是有效的，也不是可⾏的。事实上，朴素⽅法的计算复杂度表明，要使⽤更有效的算法来寻
t个阈值。
通过测量阈值处理的性能（goodness）来获知⼀组阈值是否是有效的阈值也是很重要的。在⾃然图像中，可以看到相同的物体（objects）像素相似，不同的物体像素不相似，这表明可以考虑使⽤类内⽅差和类间⽅差进⾏测量；即属于⼀个物体的像素间的灰度上的⽅差和不同物体中的像素间的⽅差。
朴素⽅法的计算复杂度和多阈值情况中的性能测量（goodness measure）的存在促使我们使⽤⼀个有效的搜索算法。在下⼀节，将描述如何⽤遗传算法实现它。
3 遗传算法
遗传算法（GA）是模拟基因的⾃然地元启发式算法。遗传算法在不存在确定性⽅法或者如果确定性⽅法计算复杂，GA是⼀个基于种（population）的算法（即每次迭代产⽣多个解）。每次迭代的解的个数称为种⼤⼩。每个解⽤染⾊体表⽰，每⼀条染⾊体都是由基因组成。
对于⼀个种⼤⼩为n的遗传算法，是从n个随机解开始。然后，选择最优解杂交产⽣新的解。将产⽣的最优解添加到下⼀个迭代中，⽽舍弃不好的结果。当算法对解进⾏了迭代时，可以实现将这些解在⼀定程度上改进到收敛⾄接近最优解。
当使⽤遗传算法时，有许多因素需要考虑。第⼀个因素是染⾊体和基因的表⽰，因为不好的表⽰可能会减慢收敛过程。遗传算法的另⼀个重要因素是从旧的解中产⽣新解的机制。最常⽤的机制是交叉和突变。第三个因素是如何到⼀个适应度函数（即评价解的⽅法）⽤于接受或者拒绝解，和如何选择最优的解来杂交。
⼀般来说，遗传算法有四个阶段：种初始化、适应度评估、复制（reproduction）和终⽌。
初始化是创建初始随机解的过程，可以通过将基因设置为随机值来完成。在初始化的过程中，创造n条染⾊体作为第⼀代解。初始化后，⽤适应度函数评价每条染⾊体的适应度（解的性能（solution goodness））。
复制过程有四个步骤：选择、交叉、突变和接受解。
·在选择步骤中，选择当前种中的最适解来复制得到新的解。然⽽，更少的适应度将有机会被选择。可⽤通过多种机制实现选择步骤。⼀种流⾏的⽅法是rollet wheel。该⽅法的⼯作原理如下：假设⼀个rollet wheel被分为n部分，每个部分表⽰⼀个染⾊体。每个部分的⾯积是根据染⾊体的适应度来映射。然后，在0到360之间随机选择⼀个数字，并将其映射到rollet。这给最是染⾊体更多的机会，⽽不太给不太合适的那些提供可能的机会。在实践中，这可以通过评估每⼀个染⾊体的适应度来实现，然后将总数归⼀化到1。这个过程将适应度测量转换为概率值，然后发现累积分布，并⽣成⼀个0到1之间的随机数。选择累积中的对应于随机数的染⾊体。这⼀选择在两条染⾊体上执⾏，每次复制两条新的染⾊体。
·选择染⾊体后，通过选择染⾊体上的⼀个随机的点和该点后交换基因来完成交叉操作，如图4所⽰。
图4：交叉操作
·交叉可能陷⼊局部最优。为了克服该问题，对随机选择的⼀个基因进⾏突变操作，改变其值，从⽽打
破平局。基因的⼀个常⽤的表⽰是⽐特（bits），每个基因都⽤⼀个bit来表⽰。在这种情况下，通过在染⾊体上随机翻转⼀个bit来完成变异。
·在交叉和突变之后，复制得到了两条新的染⾊体。最后⼀步是在新的种中接受这两条染⾊体。通常，如果新的染⾊体⽐它们的⽗代好，就会被接受。
终⽌是遗传算法的最后⼀步。通常，当满⾜某个条件时，遗传算法的迭代就停⽌了。最常⽤停⽌条件是迭代次数。当满⾜⼀个预定义的迭代次数时，遗传算法就停⽌了。⼀般的遗传算法如图5所⽰[6]。
图5：⼀般的遗传算法[6]的流程图
4 所提算法
所提算法⽤遗传算法来寻近似最优阈值。我们的⽬标是最⼤化类内⽅差并最⼩化类间⽅差。所提算法使⽤编码为bits的⼀个向量的然染⾊体。每个向量有L*n bits，其中L是log（灰度的个数），n是所⽤阈值的个数。染⾊体重⼤每个L bits表⽰⼀个阈值。染⾊体结构如图6所⽰。
图6：染⾊体结构
⾸先，到⼀个图像的直⽅图。直返图提供的信息将⽤于评价适应度。然后，随机产⽣K个初始染⾊体。之后，遗传算法迭代固定的迭代次数，最终选出最优染⾊体作为解。图所提算法的伪代码如图7所⽰。
所提图像分割算法
输⼊：图像Im、种⼤⼩、交叉率、变异率、迭代次数、阈值个数
输出：分割图像
图7：所提图像分割算法
适应度函数测量分割的性能（goodness）。通常，在⾃然图像中，不同物体的像素之间的⽅差⼤，⽽同⼀物体中像素间的⽅差⼩。这影响了适应度函数的设计。在所提算法中，我们使⽤如下的函数F，作为阈值i的适应度[7]：
其中
物体间的⽅差SBetween objects如下：
其中
是⽤阈值thsld i所分割的像素的平均，表⽰如下：
分割i的概率表⽰如下：
图像的全局平均是：
mg = mi × pi
分割i的的⽅差是：
图像的全局⽅差是
5 实现及结果
该算法在Matlab中实现。初始种的⼤⼩是10条染⾊体。交叉率和变异率分别是0.95和0.05。算法的迭代次数是500次。它运⾏在
2.27GHz核i3的处理器上。
该算法对于分割图像有⾼质量结果。⼀组输⼊图像和分割结果的样本如图8-11所⽰。
图8：（a）摄影师的原始图像（b）⼀个分割后的结果（c）直⽅图图像和在83 levels的阈值
图9：（a）⽶粒的原始图像（b）⼀个分割后的结果（c）直⽅图图像和在130 levels的阈值
图10：（a）渔夫的原始图像（b）两个分割后的结果（c）直⽅图图像和在111与168 levels的阈值

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。