0 引言

    图像分割是图像处理中的一个关键步骤，也是图像分析和理解的基础，对图像目标进行提取、测量都离不开图像分割^[1]。

    目前，国内外学者采用不同方法对图像分割问题做了大量研究^[2-3]，这些方法各有优势，也存在一些问题。例如，基于图论的图像分割是一个研究热点，但此法属于NP-hard问题，也就是随着图中节点数的增大，问题的求解将变得复杂耗时。另外，目前还没有能够精确求出最优解的算法，实际中一般采用近似的求解算法，这使得图像分割中不可避免地存在一些误差，从而影响图像处理的效果。而遗传算法能使这些误差最小，从而使计算机视觉达到实用化的要求。而且，遗传算法进行图像处理时不像传统算法那样局限于邻域特性的最佳，而是考虑整幅图像的最佳，使图像处理效果接近人眼的观察效果^[4-6]。

1 使用遗传算法进行图像分割的思路

    图像分割关键因素是获得灰度图片的分割阈值。因此，在用遗传算法处理时，首先要用染色体表示阈值，目标是选出最佳阈值染色体。同时，应确立最佳阈值的评价指标，也就是适应度函数的建立。

    围绕这个主题，首先要建立染色体初始种群；而后，调用适应度计算模块，计算种群中各个染色体的适应度值，接着按照适应度值对种群中的染色体进行排序，并记录该代种群的最佳阈值；在选择步骤中，按照一定规则用上一代适应度大的个体替代当前代适应度小的个体组成新的种群；进入交叉处理环节后，按照设定的比例采用某种方式（例如随机方式）选择需要进行交叉的染色体对，在此过程中将产生不同于前辈的新的染色体个体；执行变异步骤，在此步，将按照设定的概率，以一定的方式（例如随机）找出发生变异的染色体基因位置，这个过程同样会产生全新的个体；当变异步骤执行完后，再次回到适应度计算步骤循环进行，直到达到设定的遗传代数^[7-8]；最后，依据算法给出的最佳阈值对图片进行处理并显示。算法的流程如图1所示。

2 算法中主要模块的设计

2.1 预处理和初始种群生成模块

    在预处理步骤中需要设计染色体表示方法。由于本文中灰度图的阈值最高限为255，是一个数值，因此这里采用二进制表示法即可^[9]。二进制的位数由式(1)确定。

其中，b_j、a_j分别表示染色体描述变量区间的最大和最小值，m_j表示采用的二进制位数。本文中阈值的取值范围为[0，255]，代入式(1)可以求得m_j=8，也即本文中用8位二进制表示染色体个体。为考虑整幅图像最佳，这里判别染色体个体优劣的适应度函数采用式(2)来描述。

其中，p₁、p₂分别表示目标像素和背景像素的个数，μ₁、μ₂分别表示目标像素和背景像素的平均灰度值，f表示适应度值。

    在算法的初始化操作中，采用随机生成的方案随机生成10个8位的染色体，构成初始种群。交叉概率和变异概率分别设置为0.7和0.2。

2.2 适应度计算模块

    在此操作过程中要设置代沟，这里设置为0.9，也就是将要淘汰10%的较差个体^[10]。在第二代以后的群体中，将90%的更优秀的个体保留进入后续处理程序；对群体中保留下来的个体计算其对应的阈值；分别统计低于和高于阈值的灰度值的总个数和总和，继而求出两类灰度的平均值，根据式(2)计算出对应于每条染色体的适应度值；对于本代和上一代，根据适应度值由小到大对染色体进行排序；统计每一代的最佳阈值和最佳适应度值。阈值到灰度值的转化见式(3)。

式中，h是灰度值，c是染色体对应的十进制数值，l是二进制染色体长度。

    本步骤的算法流程如图2所示。

2.3 选择模块、交叉模块和变异模块

    在选择步骤中，首先计算前一代中适应度值比当前群体适应度值大的个体及其数量；而后，用上一代适应度比当前代更大的个体随机取代当前代的个体；最后，将当前代的各项数据保存。

    在交叉操作中，首先依据交叉概率随机地选出参与交叉的染色体对；然后，按照随机选择方案选出交叉点位置进行交叉，这里的交叉选用单点交叉即可^[11]。

    在变异操作中^[12]，首先依据设置的变异概率计算出在群体中所有的基因里参与变异的基因数量；使用随机选取的方式确定变异基因所在的行列位置，然后对选择的变异基因进行取反操作；保存处理过的种群；最后，用上一代中最优的染色体补充到当前代群体中，以维持种群中染色体的数量。

    上述几部分操作的流程图如图3所示。

3 使用传统遗传算法进行图像分割的实例

    为验证上述传统遗传算法的效果，应用该法对某带有底部噪声的电力电子逆变系统图片进行了处理。

    原始图像如图4所示，处理后的图像如图5所示，最佳适应度值进化曲线如图6所示。

    由处理结果可见，传统遗传算法在进化过程执行到20代左右就已经收敛到最佳值了，而且能将底部颜色和文字噪声彻底清除，比较清晰地分割出目标图像。但是，传统算法处理的时间过长，系统显示运算时间为7.416 s，这么长的处理时间是无法满足需求的。

4 遗传算法的改进及算法改进前后图像实际处理效果的比较

4.1 算法的改进

    遗传算法若要收敛到全局最优解必须具备拓展性和收敛性，而这些性能与交叉概率p_c和变异概率p_m密切相关^[13-14]。增大p_c的值，虽然加强了对新的解空间拓展能力，但增大了高适应度的染色体结构被破坏的可能性；反之则会减缓算法的搜索进程，甚至停滞。如果p_m的值设定得过小，则可能造成早熟收敛；反之，则会使算法变成一个纯粹的随机过程。传统遗传算法的p_c和p_m值在算法的运行过程中是固定不变的。同时，从上面的算例可以看出，传统的遗传算法在图像分割中用时较长，难以满足现代社会对高效运行的需求。因此，为了提高运算效果和效率，需要对算法做出改进。

    为了克服存在的问题，在前人工作的基础上，运用一种自适应方法对传统算法进行了改进^[15]。它根据进化的代数自适应地调整种群的p_c和p_m。在进化初期取较大p_c的值，利用其全局搜索能力加强对新的解空间的拓展，从而使种群进行全局进化；随着进化的进行，高性能的解开始增多，这时应逐步减少pc值以减少对这些解的破坏，同时，应逐步提高p_m的值来维持种群的多样性，避免收敛到局部最优解；在进化后期，搜索已经接近最优解邻域，这时应主要利用p_m的局部搜索能力，使种群在局部重点进化，加速算法向最优解收敛。

    同时，p_c和p_m还应与个体的适应度值相关。对于同一代中的所有个体，适应度高的和低的个体发生交叉和变异的可能性应有差异。这能避免一些问题，例如，高性能的解不会和其他解一样受到同样的破坏，低性能的解不会和其他解一样被保留，这样就就确保了遗传算法能如预期一样在交叉的作用下接近最优解邻域，再在变异的作用下收敛到最优解。为此，应根据遗传代数和适应度值共同自适应地调整p_c、p_m。对于适应度高于种群平均水平的个体，应设定较小的p_c和p_m，使它们在进化中能得到较好的保护；反之亦然，使低适应度个体在进化中更可能被淘汰。

    在用传统算法进行图片处理时发现p_c和p_m的设置大小对运行速度影响较大，尤其是p_m。因此，若开始p_m较小，会加快算法的运算速度。结合上述分析，这里给出改进后的自适应遗传算子(p_c和p_m)的计算公式如式(4)、式(5)所示。

    另外，为了使进化过程更好地体现优胜劣汰，并加快算法的收敛速度，在选择模块，根据进化代数分段选择了替换染色体的方法。具体为，在前三分之一代，采用最优个体随机替换前代个体的方法；在中间进化段，采用前代最优个体替换当代最差个体的方法；在后三分之一代，使用上一代一半最优个体替代当前代中最差的一半的方法，加速算法寻优过程。

4.2 图像处理实例及算法改进前后处理效果的比较

    为验证改进后的遗传算法的效果，仍然使用图4所示原始照片，并应用改进后的算法对图片进行处理。处理后的图像和图5相似，目标图像被完全剔除了噪声，变得非常清晰。改进算法的最佳适应度值进化曲线如图7所示。

    由处理结果可知，改进后的遗传算法在进化过程执行到8代左右就已经收敛到最佳值了，收敛更快。相比较前面的分割效果而言，处理的时间较短，仅为0.751 s，运算效率提高了近10倍，改进效果显著。

5 结束语

    本文结合图像分割详细阐述了传统遗传算法的设计思想及其主要构成模块的工作机制。在此基础上，结合前人的工作给出了遗传算法的改进算法。传统遗传算法对噪声图片的分割处理表明遗传算法可以将目标图像从存在噪声和底色的背景中分离出来，而改进的遗传算法则拥有更好的效果和更高的效率。这说明遗传算法可以成功应用于图像处理技术中，改进的遗传算法可以有效地应用于更为深入的图像处理研究中。

参考文献

[1] 周莉莉，姜枫.图像分割方法综述研究[J].计算机应用研究,2017，34(7)：1921-1928.

[2] 唐思源，杨敏，苗玥，等.区域生长和水平集相融合的肺部CT图像分割[J].电子技术应用，2018，44(5)：135-139.

[3] 张瑞华.基于ECCC的细胞图像分割算法[J].电子技术应用，2016，42(7)：126-129.

[4] LI Q，URAL S，ANDERSON J，et al.A fuzzy Mean-Shift approach to lidar waveform decomposition[J].IEEE Transactions on Geoscience & Remote Sensing，2016，54(12)：7112-7121.

[5] DU Z，ZHANG G，WANG C.Research on algorithm of small target detection and preprocessing in infrared image[J].Computer & Digital Engineering，2003(4)：31-34.

[6] HU X.Image segmentation based on graph theory in multicolor space for maize leaf disease[J].Transactions of the Chinese Society for Agricultural Machinery，2013，44(2)：177-181.

[7] YANG J A，TAO L，ZHUANG Z，et al.Research and realization of image separation method based on independent component analysis and genetic algorithm[J].Proceedings of SPIE，2002，4875(2)：575-582.

[8] GOLDBERG D E.Genetic algorithms in search, optimization and machine learning[M].Addison-Wesley Professional，1989.

[9] TIAN F，YAO A M，SUN X P，et al.Dual population genetic algorithm based on individual similarity[J].Computer Engineering and Design，2011，32(5)：1989-1993.

[10] ANDERSON-COOK C M.Practical genetic algorithms[J].Publications of the American Statistical Association，2004，100(471)：1099-1099.

[11] ZENG X Y，CHEN Y W，NAKAO Z，et al.Signal separation by independent component analysis based on a genetic algorithm[C].International Conference on Signal Processing.IEEE，2000.

[12] SRINIVAS M，PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics，2002，24(4)：656-667.

[13] 游培寒，毕笃彦，马时平.自适应权值调整GS图像分割算法[J].中国图象图形学报，2018，11(7)：959-964.

[14] WANG B，YAN P，ZHOU Q，et al.State recognition method for machining process of a large spot welder based on improved genetic algorithm and hidden Markov model[J].Proceedings of the Institution of Mechanical Engineers，2017，231(11)：2135-2146.

[15] CANTU-PAZ E.On random numbers and the performance of genetic algorithms[J].Computer Science Preprint Archive，2002(10)：203-210.

作者信息:

安  霆

(临沂大学 自动化与电气工程学院，山东 临沂276000)