基于自适应量子遗传算法的图像阈值分割

关学忠，尹廷武，张新城，王文峰

（东北石油大学黑龙江大庆163318）



基于自适应量子遗传算法的图像阈值分割

关学忠，尹廷武，张新城，王文峰

（东北石油大学黑龙江大庆163318）

摘要：一维最大类间差法（Otsu）是一种广泛使用的图像阈值分割方法，虽然处理速度快，但是没有考虑到像素的领域空间信息，当图像受到噪声干扰等因素影响时，难以获得满意的分割效果，鉴于此，本文提出了一种基于自适应量子遗传算法和二维Otsu的分割方法。二维Otsu法兼顾了图像的灰度信息以及邻域信息，具有抗干扰以及分割精度高的优点，但存在计算量大、实时性差的缺点；利用自适应量子遗传算法则能迅速找到最佳分割阈值，提高运算速度。仿真实验表明，本文方法减少了阈值寻优的时间，提高了分割精度，同时兼具较强的抗干扰能力。

关键词：图像分割；二维Otsu；自适应量子遗传算法；阈值寻优

图像分割是图像预处理中的关键步骤，是更高层次图像识别和理解的基础，是图像处理中不可忽视的存在。阈值分割是图像分割中常用的方法，因为它简单并且有效，在计算机视觉以及图像识别等方面被广泛使用，人们熟知的阈值分割方法有最大熵法（KSW）［1］、最大类间差法（Otsu）［2］和区域生长法［3］等。

Otsu法基于图像的一维直方图灰度信息，以目标和背景的类间方差最大作为阈值选取准则，一方面由于图像的灰度直方图不一定出现明显的峰和谷，另一方面，图片受到噪声干扰、光照不均匀等不利因素影响时，致使分割效果不佳。刘健庄等人将Otsu法推广到适合二维直方图的情况，考虑了像素的邻域灰度信息，使得分割效果有了较大的改善，但同时所带来的计算量也是惊人的。为了克服此缺点，许多学者提出了多种基于二维Otsu的快速算法［4-5］。

考虑到量子遗传算法在函数寻优方面的快速性，本文将传统的二维Otsu法与改进的自适应量子遗传算法结合起来，并将其运用到图像阈值分割中。本文所采用改进的自适应量子遗传算法，该算法将量子比特用于染色体的编码，通过量子旋转门实现染色体向最大适应度方向进化，利用Hadamard门实现染色体种群的变异操作，能够根据种群进化代数自适应动态地调整量子旋转角步长，能够快速有效的得到最佳分割阈值，取得了较好的分割效果。

1　自适应量子遗传算法

1.1量子比特编码

量子遗传算法的染色体采用量子比特［6］表达和存储一个基因。该量子位可以是“0”态或“1”态，还可以是任意叠加态，从而染色体基因所表达的信息包含了所有可能信息，不再是单一信息，相比于传统的遗传算法，量子遗传算法具有更好的种群多样性特征。量子比特编码同时具有较好的收敛性，随着|α|2或|β|2趋于0或1，量子染色体将收敛到某个单一状态，并且满足|α|2+ |β|2=1。

量子比特位可以同时包含0和1的二进制信息，那么长度为m的量子染色体可以表示2m个不同的形态，在量子遗传算法中，种群Q（t）第t代中一个长度为m位的量子比特个体可表示为：

式中：n为染色体种群大小，j为当前进化代数。

1.2自适应量子旋转门

用于染色体进化操作的量子旋转门为：

其更新过程如下：

由上式可知，量子旋转门只是改变了量子比特的相位而没有改变量子位的长度，能够使染色体向适应度更高的个体进化。△θi为旋转角，符号和大小一般由设计好的调整策略表［7］确定，一般取（0.005π，0.1π），本文采用量子旋转门动态自适应调整策略［8］。公式如下：

在公式（4）中，α1和β1为当前解中某个量子位的概率幅，α0和β0为当前最优解中对应量子位的概率幅。当Ai=0时，旋转方向正负均可以；当Ai≠0时，转角方向为-sgn（Ai）。△θ用来确定转角的大小，采用公式如下：

其中，gen为当前进化代数，maxgen为全局最大进化代数。初始进化时，△θ较大，能够增大算法全局搜索范围，更易获得全局最优解，避免算法早熟，随着种群的不断进化，△θ逐渐减小，能够实现在局部区域的精确搜索。

1.3Hadamard门变异

为了提高染色体种群的多样性，本文采用Hadamard门对其进行变异操作，变异过程可描述为：

由公式（6）可以看出，对第i条染色体的第j个量子位施加Hadamard门变异，能够使该量子位的幅角逆时针方向旋转-2θij）度，从而增加了染色体种群的多样性。如果种群经过多代以后最优个体没有任何变化，就对群体进行灾变操作。

2　基于自适应量子遗传算法和二维0tsu的图像分割

2.1二维0tsu法

二维Otsu法是在二维灰度空间寻找最佳灰度阈值来分割图像。二维灰度直方图的平面示意图如图1所示，i表示像素灰度，j表示像素邻域灰度，阈值向量（s，t）将二维灰度直方图分成4个区域，区域A和C代表目标和背景，区域B和D表示边缘点及噪声，边缘点和噪声点的概率值很小，可以忽略不计，即p（B）=p（D）=0。

图1　二维灰度直方图

A和C两个区域的概率分别为：

那么两个区域对应的均值矢量分别为：

二维直方图总的均值矢量为：

目标和背景的类间离散度被定义为：

最佳阈值向量（s*，t*）满足下式：

由以上公式可以看出二维Otsu的计算量很大，为了实际应用的需要，结合本文提出的自适应量子遗传算法实现最优阈值的求取，从而实现减少计算量、提高计算效率的目的。

2.2图像分割算法步骤

自适应量子遗传算法能够在二维灰度直方图解空间中快速查找最佳阈值向量，使得目标与背景的灰度差异最大，其阈值寻优步骤如下：

Step1种群Q（t）初始化。相对于一维Otsu法中染色体的位数为8位，我们在二维Otsu中采用16个量子比特位编码染色体种群。

Step2对染色体种群Q（t）进行解码操作，得到解空间中的某一确定解P（t）；

Step3根据适应度大小评估各个解的优劣，保留适应度最高的个体；

Step4判断是否满足结束条件，如果满足则按照最佳适应度即最佳阈值对灰度图像进行分割，否则继续计算。

Step5分别利用量子旋转门和Hadamard门对染色体种群实施进化和变异操作，得到新的种群Q（t+1）。

Step6对新种群Q（t+1）进行解码操作，得到对应的确定解P（t+1）；

Step7根据适应度大小评估各个解的优劣，保留适应度最高的个体；

Step8如果种群最优个体连续多代没有变化时，对种群进行灾变操作，将迭代次数t加1，返回步骤4。

3　实验结果及分析

图像仿真实验是在MATLAB7.0环境下进行的。为了验证本文阈值分割方法的准确性，选取MATLAB仿真软件图库中Lena和cjrcujt两幅图像，在同等条件下，分别采用基于遗传算法的一维直方图Otsu分割方法和本文方法对两幅图像进行分割实验，分割结果如图2和图3所示。比较图2（b）、（c）两幅图的分割效果，可以直观的看到本文算法分割后的图片人物细节更加清晰、细腻，另外由图3（b）可以看到管线粘连在一起，看不出原来的样子，而图3（c）虽然有些管道粘连在一起，但是总体上实现对管线的分割，分割效果更好。

图2　Lena分割效果比较

图3　cjrcujt分割效果比较

为了验证本文分割方法的抗噪声能力，选取了一张含噪声的rjce图像进行试验，分别用分别采用基于遗传算法的一维直方图Otsu分割方法和本文方法对该图像进行分割实验，分割效果比较如图4所示。由图4（b）可以看到图像上有许多的噪声点，抗噪能力差，严重影响了分割效果，而图4（c）分割效果较好，噪声点很少，具有较强的抗噪声能力，分割效果较好。

图4　cjrcujt分割效果比较

为了验证本文算法的快速性，我们分别采用二维Otsu穷举法和本文算法对上述3幅图像进行了仿真实验，时间性能比较如表1所示。由表可知，本文方法计算时间远远少于传统二维Otsu法，降低了计算量，提高了计算效率。

4　结论

二维直方图Otsu法求取最佳分割阈值的问题，实际上就是函数寻优的问题，虽然对图像的分割较为准确性，抗噪性也较强，但存在计算量大，花费时间过长的缺点，本文在此问题上引入了自适应量子遗传算法来用于图像分割的最佳阈值求取，通过仿真实验表明，本文方法能够大大缩短分割时间，同时相比于一维直方图Otsu法，本文方法分割更准确，而且抗噪声能力更强。

表1　时间性能比较

参考文献：

［1］范九伦，雷博.灰度图像的二维交叉熵直线型阈值分割法［J］.电子学报，2009，37（3）：476- 480.

［2］李惠光，姚磊，石磊.改进的Otsu理论在图像阈值选取中的应用［J］.计算机仿真，2007，24（04）：217-219.

［3］夏晶，孙继银.基于区域生长的前视红外图像分割方法［J］.激光与红外，2011，41（1）：108-111.

［4］郝颖明，朱枫.2维Otsu自适应阈值的快速算法［J］.中国图像图形学报，2005，10（4）：485-488.

［5］唐英干，刘东，关新平.基于粒子群和二维Otsu方法的快速

图像分割［J］.控制与决策，2007，22（2）：203-205.

［6］李士勇，李盼池.量子计算与量子优化算法［M］.哈尔滨：哈尔滨工业大学出版社，2009：69-95.

［7］NARAYANAN A，MOORE M. Quantum -jnspjred genetjc a1gorjthms［C］.//Proceedjngs of IEEE Internatjona1 Conference on Evo1utjonary Computatjon，Nagoya，Japan，1996：61-66.

［8］于艾青，刘涛.基于自适应量子遗传算法的电力系统机组组合问题［J］.上海电力学院学报，2015，1（31）：25-28.

Image threshold segmentatlon based on AQGA

GUAN Xue-zhong，YIN Tjng-wu，ZHANG Xjn-cheng，WANG Wen-feng （Northeast Petroleum University，Daqing 163318，Chjna）

Abstract:One-djmensjona1 Otsu method js a wjde1y used jmage thresho1d method，a1though the processjng speed js fast，but jt do not take spatja1 jnformatjon of the pjxe1 jnto account，whj1e the jmage js affected by nojse and other factors，jt js djffjcu1t to obtajn satjsfactory segmentatjon resu1ts，jn vjew of thjs，a segmentatjon method based on adaptjve quantum genetjc a1gorjthm and 2D Otsu js proposed jn thjs paper. The 2D Otsu method consjders not on1y the gray 1eve1 jnformatjon but a1so the nejghborhood jnformatjon，jt has the advantages of antj-jnterference and hjgh segmentatjon accuracy，but the djsadvantages are computatjona11y jntensjve and poor rea1-tjme performance；by usjng adaptjve quantum genetjc a1gorjthm，we can qujck1y fjnd the optjma1 segmentatjon thresho1d，jmprove processjng speed. Sjmu1atjon resu1ts show that thjs method reduces the tjme of thresho1d optjmjzatjon and jmprove the accuracy of segmentatjon，jt a1so has re1atjve1y strong antj-jnterference abj1jty at the same tjme.

Key words:jmage segmentatjon；2D Otsu；adaptjve quantum genetjc a1gorjthm；thresho1d optjmjzatjon

中图分类号：TN01

文献标识码：A

文章编号：1674-6236（2016）07-0168-03

收稿日期：2015-05-26稿件编号：201505224

作者简介：关学忠（1960—），男，吉林蛟河人，博士，教授。研究方向：工业自动化、嵌入式系统。