改进遗传算法结合Ｏｔｓｕ算法的大田作物分割

赵明霞　吕致　郝雅洁　史维杰　李富忠

摘要：针对部分田间图像由于其背景复杂、光照不均匀等导致很难确定图像分割的最佳阈值问题，提出了一种基于结合遗传算法Otsu算法改进的图像分割方法。首先对采集的图像进行预处理，基于预处理图像通过改进遗传算法中的选择、交叉、变异三种方法以及基于Otsu优化个体适应度函数，实现了可以自动调整遗传控制参数，既确保了物种的多样性又加快其收敛速度，为Otsu图像分割提供了最佳阈值，最后经过图像形态学对图像进行填充。将改进遗传算法的Otsu算法与基于遗传算法+Otsu算法进行图像分割以及基于遗传算法+Ksw熵值图像分割进行了对比，发现该算法得到的阈值范围较为稳定，使得分割后的图像准确、清晰，对于后期进行作物株数的统计或者植株的覆盖度有一定的帮助。

关键词：全局阈值分割;遗传算法;大津算法

中图分类号：TP751         文献标识码：A

文章编号：0439-8114（2019）15-0119-05

DOI：10.14088/j.cnki.issn0439-8114.2019.15.028           开放科学（资源服务）标识码（OSID）：

Improved genetic algorithm combined with improved Otsu

algorithm for field crop segmentation

ZHAO Ming-xia，LYU Zhi，HAO Ya-jie，SHI Wei-jie，LI Fu-zhong

（Software College of Shanxi Agricultural University，Taigu 030801，Shanxi，China）

Abstract： For some field images， it is difficult to determine the optimal threshold problem of image segmentation due to its complicated background and uneven illumination. This paper proposes an image segmentation method based on improved Otsu algorithm optimization and improved genetic algorithm. Firstly， the acquired images are pre-processed. Based on the preprocessed images， the genetic control parameters can be automatically adjusted by improving the three methods of selection， crossover and variation in the genetic algorithm and optimizing the individual fitness function based on Otsu， so as to ensure the diversity of species and accelerate its convergence speed. The optimal threshold is provided for the Otsu image segmentation， and finally the image is filled by image morphology. In the result of the discussion， the algorithm results are compared with the Genetic Algorithm Based on the Otsu Algorithm and the Image Segmentation Based on Genetic Algorithm and KSW Entropy. It is found that the threshold range obtained by the algorithm is stable， which makes the segmented image accurate and clear. It is helpful to calculate the number of crops or the coverage of plants in the later stage.

Key words： global threshold segmentation; genetic algorithm; Otsu algorithm

圖像分割是结合图像的强度、图像的纹理特征、颜色特征以及图像的对比度等内在表现[1，2]，将图像分割成非重叠的感兴趣对象的技术。图像分割在图像识别、处理以及视频解析的过程中扮演着十分重要的角色，其分割效果对于检测目标、识别目标物以及跟踪目标的后续操作影响深远。图像分割的主要目的是根据一定的准则确定一个有效阈值（用于两级阈值）或多个阈值（用于多级阈值）[3]。

图像阈值分割是图像分割中较为热门的方法。近年来，图像阈值分割方法不断地创新，可分为固定门限阈值算法[4]、自适应门限阈值算法[5]、最大熵法[6]和Ostu法等多种分割算法。而遗传算法（GA）因其可作为图像分割过程中求取最佳阈值的一种高效算法，得到了广泛的研究和应用。Kirkpatrick[7]提出了利用遗传算法进行阈值优化的方法。文献[8]提出了一种基于遗传算法（GA）的MR图像分割算法，用于MR图像中未标记像素的自动分组。在实现过程中，成功地证明了迭代法和自定义法对于分割图像给出了几乎相同的阈值[9]。文献[10]提出了一种使用遗传算法和KSW熵法相结合的CT图像肺部分割方法。但是，传统的遗传算法因收敛速度缓慢、易早熟等不足之处，对于最佳阈值的选择并不是一个很好的方法。为此，研究提出了一种改进遗传算法同时结合改进Otsu阈值分割的方法，有效解决了收敛慢、易早熟的问题，从而求出最优解。

1  大津算法

Otsu阈值技术是由Kittler等[11]和Otsu[12]提出的。最大类间方差法（Otsu）是基于二维类间方差法以及最小二乘法进一步推导得出的[13]。其核心思想是：通过设定阈值对图像进行分类，可分为：背景部分以及目标物部分。最优阈值是通过计算两者间的方差值，即当阈值t为某一值时，其方差值最大。此时阈值t为最佳图像分割阈值。其原理公式如下：

假设f（x，y）为图像M×N某一点的灰度值，其灰度级为L，则f（x，y）∈{0，L-1}，记作：GL。

灰度值i在图像中的概率为：

P（i）=■ i∈Gl  （1）

如上所述，设定阈值t将图像分为前景（0，t）和背景（t，L-1）两部分。则前景区域比例以及背景区域比例分别如下：

b0（t）=∑■p（i） （2）

d1（t）=∑■p（i）   （3）

前景部分以及背景部分平均灰度分别为：

u0（t）=∑■■   （4）

u1（t）=∑■■  （5）

图像总体均值为：

u（t）=b0（t）u0（t）=d1（t）u1（t）   （6）

两者之间的方差即最佳阈值取值，表述如下：

？啄■■=b0（u0-u）2+d1（u1-u）2  （7）

运行过程中于GL范围内依次为t赋值，当t为某一值使得？啄■■的值为最大时，表明此时的t值为最佳分割阈值。

2  传统的遗传算法

遗传算法作为一种基于自然选择和遗传进化思想的自适应元启发式搜索算法，以其变异算子[14]而闻名。其核心理念可以看成是以生物学中的自然选择以及生物遗传机制算法为基础的一种随机搜索算法。通过模拟自然界的繁殖、交叉和变异现象，在每次迭代中保留一组候选解，并根据某些指标从解组中选出较好的个体。将个体与遗传算子相结合，生成新一代候选解，并重复此过程，直到满足收敛指标[14，15]。

遗传算法的主要组成部分是：编码机制、适应度函数、遗传算子（选择、交叉和变异）和控制参数。若采用遗传算法进行解决问题时，其可能的解被编码到染色体中，即个体。几个人组成一个初始的解决方案组。通过计算适应度函数，输出满足终止条件的个体，算法结束。否则，遗传算法使用三个基本操作符（选择、交叉和突变）来操纵种群的遗传组成。选择是将当前代中适应度值最高的个体复制到新一代的过程。交叉操作符通过重新组合来自双亲的信息产生两个后代（新的候选解决方案）。突变是个体某些基因值的随机改变。每个基因的等位基因都是突变的候选基因，其突变概率决定了其功能。在新一代中，种群比上一代更适应环境，进化一直持续到满足优化准则为止。对最后一个个体进行解码，得到最优解。

3  基于遗传算法的阈值优化

3.1  改进的遗传算法

传统的遗传算法拥有高效的运算优势之时也存在仅仅局部优化的特点，为了避免因此产生的困境，对其进行了改进。主要针对其中的选择、交叉和变异算子进行优化。

首先，改进遗传算法中的轮盘选择法。基础的轮盘选择法中若变异产生了一个新的最大值（更接近于最优值），但是其种群数量就只有1，远远比不上当前的最大值（离最优值远一点）。若直接使用轮盘选择法，那么这个新变异出来的值就会被覆盖掉。通过强制将上一代中最大的值进行保留，来保证种群不会退化。核心代码如下：

for i in range（len（fitness_list））：

if fitness_list[i] == max_fitness：

new_populations.append（self.populations[i]）

else：

remain_populations.append（self.populations[i]）

其次，传统的算法中，交叉和变异值的选取是至关重要的，它们对于算法的行为或者性能有直接的影响，而且还能凸显出算法的收敛性。传统的遗传算法通常将两者设置为固定值（范围0.4～0.9），其缺点在于最优的图像阈值与真实值之间存在一定的差异，从而无法进行最优的图像分割。

本研究中，针对交叉算子Pc，使得Pc为两个不同的概率值。迭代前期，为了避免淘汰过多的个体造成的搜索全局最优困境，可将其值提高，所以前期设置为0.8;当处于中后期时，为了增强其收敛速度同时保证优秀个体，交叉概率值可适当的降低（即可取值为0.6）从而优化全局最优值的搜索，进而获得良好的分割效果。具体内容如下：

Pc=0.8 gen≤200.6 gen>20   gen为迭代的次数  （8）

使得初期迭代时，个体选中的概率增大;同时后期又防止了优秀个体的损失。

针对变异算子Pm，将Pm设置为变化的概率值：

Pm=0.02 gen≤300.03  gen>300.02  gen>50&gen≤50，gen为迭代的次数（9）

3.2  改进的Otsu算法

阈值法进行图像分割的要点是阈值t的选择。若t的取值较高时，则会出现背景误认为目标部分的现象，干扰了后续的一系列图像处理操作，例如：特征的提前等;當t的取值偏低，则会将目标区域划分到背景区域，从而导致有用信息丢失。因此，最佳阈值t的选取对于精准的图像分割尤为重要。

结合上述所言，当（7）式？啄■■目标物与背景区域之间的差异越显著，图像的分割效果越好。也可以理解为获取的阈值使得图像的两部分与图像的中心相隔较大[即u0（t）与u1（t）]。图像两部分之间的距离可表示为（假设度量为1个距离）：

d2（t）=[u0（t）-u1（t）]2   （10）

原理同上，d2（t）的取值越大，其分割效果越好。而且，两部分中每个像素与其中心相距应尽量降低，表明像素间的内聚力较好。因此，提出了平均方差的理念，它可以描述像素间的内聚力。

■02（t）=■∑■[i-u0（t）]2p（i）  （11）

■12（t）=■∑■[i-u1（t）]2p（i）  （12）

■02与■12取值越小，其每个部分的像素分布越均匀，其内聚力越好，从而图像的分割效果好。

结合以上两种因素，在维持两部分相距较大的同时保证每部分间的像素内聚力好，从而更好地分割图像。因此，由上述分析的Otsu基础算法上衍生了一种新的最佳阈值获取办法。其体现在公式中可表示为：

G（t）=■=■（13）

可知，G（t）值为最大时，其所对应的灰度级便是最佳阈值Th。如下：

Th=argmax[G（t）] t∈GL  （14）

3.3  改进遗传算法结合改进大津算法

大津算法获取最优阈值的过程等价于（14）式的求解。因此，可将其与改进的遗传算法相结合进行完善。两种算法结合的主要核心步骤表述如下。

3.3.1  制定编码与解码规则  主要使用二进制编码原则，基于图像的灰度值取值范围（0～255），选择16位二进制串对阈值（s，t）进行编码。前8位代表阈值s，而后8位则是t;通过将16位二进制串分别解码为0～255间的数值来获取适应度的取值。

3.3.2  初始化种群  群体的初始值对于遗传算法的执行效率以及运行结果有直接影响。若取值过大，算法的复杂度增加;若取值偏小，因其空间有限，则很难获取最优的分割阈值。

3.3.3  选择适应度函数  通过将式（14）作为适应度函数，求取最佳适应度值。

3.3.4  选择  针对轮盘选择法进行改进。通过保留上一代中最大值来保证种群的多样化。

3.3.5  交叉  设置交叉概率值为两个不同的概率值。同时，从基因一半往后的位置开始交换，这样有利于保持当前的最优值，使得交换之后的种群不至于很差。

3.3.6  变异  将变异值设置为变化的概率值。但是，对于每一个个体，对任意位置产生一位变异，但是变异概率不宜设计的很大，这样会导致种群不易收敛。

3.3.7  终止条件  当满足种群迭代的最大值且种群的98%个体都指向同一个值时，算法停止运行，此时具有最高适应度值的个体即为最佳阈值。

图像分割流程如图1所示。

4  试验分析

自然环境复杂多变，想要获取很多的作物信息，需要优化图像分割的效果。为了验证改进遗传算法的Otsu图像分割算法在复杂背景下的可行性，通过相机（大疆精灵4pro）于山西农业大学资源环境学院实验站采集田间返青期、七叶期小麦（图像的像素为822×856）。在处理器Intel（R） Core（TM） i5-8300H CPU @2.30GHz，8.00GB内存的计算机上对基于传统的遗传算法解Otsu算法以及基于遗传算法与Ksw熵值作物图像分割两种方法进行了比较。试验流程图如图2所示。

分别使用遗传算法+Ksw熵算法、遗传算法+Otsu算法以及改进遗传算法的Otsu图像分割算法针对返青期、七叶期小麦进行了图像分割，结果分别见图3和图4。从最终的图像分割图来看，图3和图4均存在着过分割的情况，而改进遗传算法的Otsu图像分割算法得到的分割图像相对较好。除了使用这种定性的分析外，研究通过对比三种算法所获得的阈值、所需时间以及精准率来比较三者的区别（其中种群数量设置为20以及迭代次數为300）。结果如表1所示。结合表1与表2可发现，改进遗传算法的Otsu图像分割算法在准确率方面较另外两种算法较高（准确率可以看作是在所操作的测试数据集中，其正确分类的样本数量占总样本数量的比例）。因改进遗传算法与Otsu算法相结合，导致算法的复杂度增加，运算过程耗时较长，但与基本遗传算法结合Ksw或者大津算法相比，在保持迭代次数等同的条件下，改进遗传算法既可以维持种群的多样化又提高了收敛速度。

两种改进算法相结合与改进前的算法以及基于遗传算法的Ksw熵值分割算法进行比较，其最佳阈值的获取更加有效，在提升了图像分割精度的同时又保证了图像有效信息的展现。改进的算法其稳定性较好，结果精确度高，对于作物图像分割的效果有很大的帮助。

5  小结

通过将改进的遗传算法与Otsu阈值分割算法相结合对田间植物图像进行处理，在对适应度函数进行全局优化的同时，对交叉、变异两者的概率值有一定的改进，达到了可以自动调控参数且在保证群体不退化的前提下又提高了其收敛速度的目的。最终使得图像分割的阈值范围稳定在2～3个像素以内，算法的稳定性得到进一步加强，实现了图像的高效分割。

改进遗传算法的Otsu图像分割算法因其分割精度高、收敛速度快等特点，被广泛应用于各个领域的图像识别与分析中，拥有较高的实用性。

参考文献：

[1] 谭  优，王泽勇.图像阈值分割算法实用技术研究与比较[J].微计算机信息，2007，23（24）：298-299，233.

[2] SHARMA S，SHAH D. A practical animal detection and collision avoidance system using computer vision technique[J].IEEE Access，2016（99）：1.

[3] HORNG M H. Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J].Expert Syst Appl，2011，38（11）：13785-13791.

[4] ABUTALEB AS. Automatic thresholding of gray-level pictures using two-dimensional entropy[J].Computer vision graphics and image processing，1989，47（1）：22-32.

[5] CHANG D，ZHAO Y，LIU L，et al.A dynamic niching clustering algorithm based on individual-connectedness and its application to color image segmentation[J].Pattern recognition，2016，60： 334-347.

[6] 刘桂红，赵  亮，孙劲光，等.一种改进粒子群优化算法的Otsu图像阈值分割方法[J].计算机科学，2016，43（3）：309-312.

[7] KIRKPATRICK S. Optimization by simulated annealing： quantitative studies[J].J Stat Phys，1984，34（5-6）：975-986.

[8] SOURAV DE，BHATTACHARYYA S，PARAMARTHA D.Automatic magnetic resonance image segmentation by fuzzy intercluster hostility index based genetic algorithm：An application[J].Applied soft computing，2016，47：669-683.

[9] JUANG C F. A hybrid of genetic algorithm and particle swarm optimization for recurrent network design IEEE Trans[J].Syst Man Cybern B：Cybern，2004，34（2）：997-1006.

[10] 姚立平，潘中良.使用遗传算法和KSW熵法相结合的CT图像分割[J].电视技术，2018，42（11）：1-6.

[11] KITTLER J，ILLINGWORTH J. Minimum error thresholding[J]. Pattern recognition，1986，19（1）：41-47.

[12] OTSU N.A threshold selection method from gray-level histogram IEEE Trans[J].Syst Man Cybern，1979（9）：62-66.

[13] 張东生.基于阈值的图像分割算法研究[D].黑龙江大庆：东北石油大学，2011.

[14] HOLLAND J H.Adaptation in natural and artificial systems：An introductory analysis with applications to biology，control，and artificial intelligence[M].East lansing：University michigan press，1975.

[15] AZAMATHULLA H M，WU F C，AB GHANI A，et al.Comparison between genetic algorithm and linear programming approach for real time operation[J].J Hydro-environ Res，2008，2（3）：172-181.