基于遗传模拟退火算法的Otsu图像分割研究

刘紫燕，吴俊熊，毛　攀，帅　暘

(贵州大学　大数据与信息工程学院，贵州 贵阳 550025)



基于遗传模拟退火算法的Otsu图像分割研究

刘紫燕，吴俊熊，毛攀，帅暘

(贵州大学大数据与信息工程学院，贵州 贵阳 550025)

针对目前基本遗传算法在优化图像分割算法中存在的易于早熟、陷入局部最优的不足，以最大类间方差函数为适应度函数，提出了一种基于改进遗传算法的图像阈值分割算法。对交叉、变异算子进行自适应改进，同时将模拟退火算法融入到遗传算法中，使得对个体的评价更合理，既能克服种群退化现象，又改善算法的全局搜索能力，避免遗传算法陷入局部最优。实验结果显示，与Otsu图像分割法以及基于遗传算法的图像分割方法相比，使用该方法得出的阈值范围更加稳定，执行效率更高，在图像分割中获得的分割效果更佳。

图像分割；最大类间方差；遗传算法；模拟退火算法

图像分割[1](Image Segmentation)是图像处理领域不可或缺的重要步骤，长期以来受到专家学者的重视和研究，更在工程实践中得到广泛运用。常用的图像分割方法主要有三类：阈值分割法、边缘检测法和区域分割法等。其中阈值分割法由于实现的简单性而成为图像分割领域的一种重要方法[2]。但是，如何合理选择阈值，获得更佳的图像分割效果，一直以来都是学者需要解决的问题。目前常用的阈值法存在以下缺点：最小误差法[3]计算量大，不利于处理实时图像，而且仅对小目标图像具有好的分割效果；最大信息熵法[4]虽使图像的信息量丢失最小，但因引入对数运算，其数学计算量相当庞大；二维阈值算法[5]图像分割效果虽好，但计算量是以指数增长，运行时间较长；最大类间方差法对单峰的图像分割效果很好，但实际上，多数图像并不是简单的单峰，若仅仅利用Otsu准则进行目标分割，很难得到稳定可靠的分割结果。因此，为了解决上述问题，研究者们提出将遗传算法和Otsu法结合在一起使用。

文献[6]利用遗传算法能够改善传统阈值分割方法的分割效率，但由于基本遗传算法存在收敛性差、容易早熟等特点，给寻找准最优解带来很大困难。因此本篇文章对基本遗传算法进行优化，介绍一种改进的遗传算法与Otsu法则结合的算法。

1　Otsu阈值法

l979年，Otsu提出了一种阈值分割方法，该算法计算简单，不受图像对比度和亮度的影响。它主要是通过最大类间方差准则[7]来确定区域分割门限。其基本原理是任意选取某一灰度值为阈值门限将图像划分为两大类，计算两类灰度分布的方差。若差值越大，即表示目标和背景之间的区别更加明显，差值达到最大时的灰度值就是最佳阈值。其基本过程可以描述如下：

(1)

(2)式中：Ps0和Ps1分别为s0类和s1类对应灰度值i在(0,1,…,t)和(t+1,t+2,…,L-1)出现的概率之和。

s0类和s1类的灰度均值分别为

(3)

(4)

式中：μs0和μs1分别为s0类和s1类的灰度均值。

那么图像整体的灰度均值为

(5)

s0类和s1类的类间方差即Otsu法准则函数为

F(t)=Ps0(μs0-μ)2+Ps1(μs1-μ)2=

Ps0Ps1(μs0-μs1)2

(6)

式中：F(t)为s0类和s1类的类间方差函数。

方差度量的是灰度分布的均匀性，所以方差越大，表示图像的两部分灰度分布差别越大，即灰度分布越广泛，若目标中一部分被误分到背景中或背景中出的一部分被误分到目标中，均会造成两部分灰度差别变小。因此，要使错分概率达到最小就要求类间方差达到最大。

2基于遗传模拟退火算法的Otsu阈

值分割

2.1基于遗传算法的Otsu阈值分割

遗传算法[8]是一种在计算机上模拟生物自然选择和进化的寻优搜索算法，具有高度并行、自适应、随机等特点。主要通过模拟自然进化中的基因选择、交叉和突变现象来完成搜索过程。

由于遗传算法具有快速寻优的功能，而Otsu法计算最佳阈值的过程本质上是求取最优解的过程，因此，将遗传算法和Otsu法结合在一起，可以达到提高计算效率的目的。本节主要是利用遗传算法对Otsu法求解图像的最佳分割阈值的过程进行优化，如图1所示为图像分割的整体实现过程。

图1　遗传算法阈值分割实现流程

在传统的遗传算法中，交叉率和变异率都是预先设定的，这样得出的结果不能显示出群体适应度的变化，最终可能导致收敛速度变得比较缓慢的情况。因此，为了避免发散或陷入局部最优，要保持群体较好的多样性，这就需要自适应地调整pc和pm。所以，在自适应遗传算法中[9]，可以利用如下公式对pc和pm进行自动调整

(7)

(8)

式中：k1和k2是0～1之间的调整系数；Fmax为种群中最大适应度值；F′为交叉操作两个体中较大适应度值；Fav为群体平均适应度值；Fm为待变异个体的适应度值。

从式(7)、式(8)可以看出，个体适应度值高的解可以降低pc和pm的值，个体适应度值的解可以增大pc和pm的值。也就是说，当高适应度值的解加快遗传算法收敛的同时，低适应度值的解却可以规避GA陷入局部最优。

2.2基于遗传模拟退火算法Otsu图像阈值分割

虽然基于遗传算法的Otsu法在方差计算次数和所用时间上比传统Otsu法明显减少,但在实际中，由于基本遗传算法存在收敛能力差、容易早熟和其他不足，对图像分割的阈值寻优带来很大的困难，因此，如何极大地改善收敛速度和解决早熟已经成为至关重要的问题。而另一方面，模拟退火[10](SA)具有很强的局部搜索能力，对于这个特点，若能够将SA算法融入到遗传算法中，就可以提高遗传算法的运行效率和求解质量。针对这些情况，根据图像分割算法的特点，优化基本遗传算法，提出一种阈值分割效果更佳的改进遗传分割算法——遗传模拟退火算法。

遗传模拟退火算法是遗传算法和模拟退火算法共同组合构成的一种优化算法，可以克服各自的不足，实现优势互补。它是以遗传算法为主体，将模拟退火算法融入其中。

下面是具体算法描述：

步骤1，给定初始化种群规模N，初始温度T0，降温衰减因子α，随机产生初始种群。

步骤2，在当前温度Ti执行如下操作。直至产生下一代新的群体：

1)利用式(6)，求取群体中每个个体的适应度值；

2)从群体中任意选取两个个体xi和xj，进行交叉操作，交叉率依据式(7)，产生两个新个体，分别求取其适应度值，然后计算出新旧个体的适应度值差，若差值大于0，则一定接收新个体，若差值小于0，则以一定概率exp{-[F(x′)-F(x)]/Ti}接收新个体；

3)进行变异操作，变异概率依式(8)进行，产生新个体x′后，同样，新旧个体差值若大于0，则一定接收新个体，若差值小于0，则以概率exp{-[F(x′)-F(x)]/Ti}接收变异后的个体。

步骤3，当满足收敛条件时，即Ti≤Tfinal时，算法终止；否则，继续退火操作，Ti+1=αTi，转至步骤2。

3　仿真结果及分析

本文利用MATLAB R2014b平台进行编程，选择经典图像Rice和Lena作为测试，其分辨率为256×256，灰度级也是256。分别利用最大类间方差法、基于遗传算法的Otsu阈值分割和基于遗传模拟退火算法的Otsu阈值分割3种算法对图像进行实验测试，实验结果如图2、图3以及表1、表2所示。

图2　原图及3种分割算法结果

图3　Lena原图及3种分割算法结果

测试最大类间方差法遗传算法本文算法阈值时间/s阈值时间/s阈值时间/s11250.18801210.11001270.078021250.20301290.14101270.094031250.21901290.12501250.0790均值1250.20331260.12531260.0840

表2Lena图像分割阈值与运行时间比较

测试最大类间方差法遗传算法本文算法阈值时间/s阈值时间/s阈值时间/s11000.25001000.17901020.109021000.2810980.19001040.110031000.21801000.17501020.0939均值1000.2497990.18131030.1043

从图2和图3的仿真结果可以看到，遗传模拟退火算法分割的结果是最佳的，从肉眼可以看出，它的噪声最小，丢失的信息量最小，该算法更好地突出了感兴趣的区域，体现出大米、人脸、头发、帽子与背景的区别，图像的细节得到更多的体现。基于遗传算法的阈值分割法虽然较基本Otsu法有所改善，但是仍存在少量的噪声，信息量丢失也较严重。

表1和表2是使用3种算法分别对Rice图和Lena图的阈值和运行时间的对比图。阈值方面，由于遗传算法具有随机性，寻得的最优解可能不是准最优解，但一般都会在其附近；算法执行效率方面，最大类间方差法运行时间是最长的，随着算法的逐步改进，执行效率越来越高，本文提出的遗传模拟退火算法执行效率是最高的。在表1中遗传模拟退火算法比遗传算法平均缩短了大约40 ms，比Otsu法平均缩短了119 ms。在表2中遗传模拟退火算法比遗传算法平均缩短了大约77 ms，比Otsu法平均缩短了145 ms。因此，本文提出的算法在执行效率上有较大提高。

4　结束语

本文在研究最大类间方差法的基础上，利用遗传算法对最大类间方差函数进行了全局优化，然后将交叉概率和变异概率的计算公式进行自适应改进，防止陷入局部最优解，同时将模拟退火算法融合到遗传算法当中，避免了种群退化现象，很好地改善了算法全局收敛的稳定性，保证了算法初期种群的多样性，改善了后期较优个体的适应度。实验结果表明，本文提出的基于遗传模拟退火的阈值分割方法，相对于基本Otsu法和基于遗传算法的阈值分割法而言，能够大大缩短寻找阈值的时间，提高图像分割的质量，使得感兴趣区域信息量丢失最小，从而获得更好的分割效果，同时也便于计算机视觉的后续处理。因此，将遗传模拟退火算法用来处理图像分割问题，具有一定的应用前景。

[1]章毓晋.图像分割[M].北京：清华大学出版社，2001.

[2] CHENG Y B. The research on application of image segmentation upon bi-level threshold algorithm[J]. Advances in information sciences and service sciences，2012，4(3)：52-58.

[3] 龙建武，申铉京，陈海鹏.自适应最小误差阈值分割算法[J].自动化学报，2012，38(7)：1134-1144.

[4] WANG W Y，WANG F M. Maximum entropy method of image segmentation based on genetic algorithm[J]. Computer simulation，2011，28(8)：291-294.

[5] 何春华，胡迎春.基于改进遗传算法的自动阈值图像分割方法[J].计算机仿真，2011，28(2)：312-315.

[6] 刘秋生，楚来国，杨继昌.基于遗传优化的阈值选取方法[J].信号处理，2002，18(4)：374-377.

[7] 祁佳，刘紫燕.基于融合及形态学的自适应阈值图像边缘检测[J].电视技术，2014，38(13)：36-38.

[8] WANG F J，LI J L，LIU S W，et al. An improved adaptive genetic algorithm for image segmentation and vision alignment used in microelectronic bonding[J]. IEEE transactions on mechatronics，2014，19(3)：916-923.

[9] 李康顺，李茂民，张文生.一种基于改进遗传算法的图像分割方法[J].计算机应用研究,2009，26(11)：4364-4367.

[10] YANG Y F，WANG Y P. Simulated annealing spectral clustering algorithm for image segmentation[J]. Systems engineering and electronics，2014，25(3)：514-522.

刘紫燕(1977— )，女，硕士生导师，主要研究方向为无线通信、嵌入式通信；

吴俊熊(1991— )，硕士生，主要研究方向为压缩感知技术、图像重构；

毛攀(1991— )，硕士生，主要研究方向为协作通信、资源分配；

帅暘(1990— )，硕士生，主要研究方向为数字通信与信息系统。

责任编辑：时雯

Image segmentation on genetic simulated annealing algorithm

LIU Ziyan，WU Junxiong，MAO Pan，SHUAI Yang

(CollegeofBigDataandInformationEngineering，GuizhouUniversity，Guiyang550025，China)

To address some defects which basic genetic algorithm is exploded in this day and age，such as easy precocious and local optimum in optimizing image segmentation，the image threshold segmentation algorithm based on improved genetic algorithm is proposed in this article with considering Otsu as fitness function. The cross and mutation operators are optimized adaptively while the simulated annealing algorithm is fused into genetic algorithm. And then， individual evaluation is more rational. Not only can population degradation be overcome， but global search performance of the algorithm can be enriched by utilizing the optimized algorithm. The experimental result indicates that threshold range keeps more stable and operating efficiency is better，compared with Otsu and the basic genetic algorithm. As a result，the obtained image segmentation effect is more apparent and perfect.

image segmentation；Otsu；genetic algorithm；simulated annealing algorithm

TP391

A

10.16280/j.videoe.2016.08.003

国家自然科学基金项目(61263005)；贵州省软科学研究项目(黔科合R字[2014]2025号)

2016-01-14

文献引用格式：刘紫燕，吴俊熊，毛攀,等.基于遗传模拟退火算法的Otsu图像分割研究[J].电视技术，2016，40(8)：15-18.

LIU Z Y，WU J X，MAO P, et al.Image segmentation on genetic simulated annealing algorithm[J].Video engineering，2016,40(8)：15-18.