基于改进二维熵-量子遗传算法的图像多阈值变化检测方法*

仝 彤，慕晓冬，张 力

（火箭军工程大学，西安 710025）

0 引言

变化检测是指将同一地区、不同时期获得的两幅或多幅图像进行分析处理以提取所需的地物变化信息的技术。图像变化检测在资源与环境监测、辅助测绘、自然灾害的监测评估方面以及在军事领域的打击效果评估方面都有着广泛的应用[1]。合成孔径雷达（SAR）利用主动雷达波成像，受光照和天气情况的影响较小，可对地表进行稳定的、周期性的观测，因此，常常用于变化检测[1-4]。

针对中低分辨率SAR影像，目前常用的方法是基于差异图阈值选取的直接比较法。直接比较法的核心是差异图的生成和变化阈值的选取，其中难点是如何高效自动地确定变化阈值。目前，一般采用阈值分割的方法确定变化阈值，得到变化区域与未变化区域。经典的阈值分割方法主要有最小误差法、最大类间方差法（OTSU）和最大熵法[5]。基于最大熵的阈值分割方法是一种结合了信息论的图像分割方法，但是对于噪点比较多的图像中，该方法分割效果较差。二维最大熵分割方法同时统计了像素自身的灰度信息和像素周围邻域信息，与一维的最大熵阈值分割方法相比，该方法对噪声的鲁棒性较强，但是存在计算量大的缺点[6]。针对这个问题，国内外学者研究出了许多针对减小其计算复杂度的搜索算法[7-12]。大多数研究只考虑了单阈值分割的情况，当图像直方图呈现多峰形状时，单阈值分割就不能满足分割要求，或阈值搜索时间长。因此，本文研究展开了二维最大熵多阈值分割的研究，目标是提升分割精度和搜索时间性能并将其成功用于变化检测问题中。

本文提出了一种基于二维熵-量子遗传算法的图像多阈值变化检测方法。其优势体现在：1）研究了二维阈值量子染色体编码方法，解决了传统遗传算法优化二维最大指数熵阈值过程中速度慢、多样性小的缺点；2）提出了一种半随机策略产生阈值解的方法，加快寻优速度；3）改进了量子门旋转角度方式，提出了自适应旋转角度的方法，提高了算法的鲁棒性和收敛速度。

1 二维指数熵图像多阈值分割

指数熵克服了传统对数熵的缺点，提高了计算速度并减少了信息的损失。由于一维的指数信息熵基于图像原始分布直方图，仅考虑像素自身灰度而未考虑空间信息，因此，提出了二维指数熵。二维指数熵的分割方法基于图像的二维直方图，如图1所示。设图像I的大小为M×N，则图像的二维直方图计算式为：

其中，nij指的是图像中灰度值为i而邻域灰度均值为j的像素的个数。

图1 二维直方图

图2 二维直方图俯视平面

图2为二维直方图的俯视图，横轴代表i，纵轴代表j，设分割的阈值对数C=4，在图中阈值表示为，整个区域被直线i=j分割开来，离该直线距离近的点（阴影部分内的点）表示其灰度值和邻域灰度均值比较接近，应属于图像的目标或者背景，较远的点则表示该点为噪声点或者边缘点。二维最大熵图像多阈值分割方法的原理是：选取阈值，使阴影区域的信息量最大。

信息熵定义为

选取的最佳阈值T*应满足：

2 量子遗传算法

二维最大熵图像阈值的选择问题实质上是一个优化问题，可以用遗传算法等优化方法来求解。但是普通遗传算法（Conventional Genetic Algorithm，CGA）收敛速度慢[12-14]，因此，本文引入了量子遗传算法。

量子遗传算法（Quantum Genetic Algorithm，QGA）就是将量子理论的思想嵌入到普通遗传算法。CGA种群染色体是以0和1组成的数据串，而QGA的染色体是由量子比特组成的，量子理论对CGA的改进体现在以下两点：

1）CGA中染色体的编码是由若干个0或1组成的数据串，而QGA将量子学中的量子比特引入到了染色体编码，它是由若干个量子比特组成。量子比特是的一个线性组合。量子比特可以表达为：

3 改进QGA优化图像二维熵多阈值分割方法

本文提出了量子染色体编码二维阈值方法、半随机策略产生阈值解的策略和一种新的自适应角度旋转方法。

3.1 量子染色体编码二维阈值

设图像灰度级L=256，二维最大熵多阈值分割的阈值为二维，这就需要对二维阈值进行染色体编码，本文二维阈值量子染色体编码方法是：设分割的阈值数为C，用8×2×C个量子比特组成的串来表示一个量子染色体，将每条染色体初始化为：

3.2 半随机策略产生阈值解

通常情况下，对二维熵阈值的编码是采用随机产生阈值解的方法，但是这些方法通常忽略了两个问题：1）阈值解需是从小到大依次排列的，且所有的解处于图像灰度值与邻域均值的范围内，如果随机产生的阈值解不符合上述要求，则需要重新产生阈值解，直至满足要求，导致算法的收敛速度显著降低；2）像素灰度值及其邻域灰度均值存在某种依赖关系，如果采用完全随机（Random）产生的方法，或使两个值从相差很大开始缓慢收敛到相近的状态。针对上述问题，本文提出了半随机（Half-random）产生二维阈值解的方法。

从式（11）可以看出，第2维阈值解由两项组成，第1项是通过第1维解转换得到，第2项与随机观察染色体产生的解相关，即在处理第2维阈值解时，将第1维数据与随机因素按照特定的权重因子相加形成第2维阈值解，这样就使得第2维阈值解不仅满足从小到大的变化规律，而且保持了与对应第1维阈值的相关性。

3.3 自适应旋转角度

QGA中，变异操作是常用量子旋转门完成，量子旋转门定义为：

则量子旋转变异操作为：

通常情况下，旋转角度θ是由经验确定的固定值，θ的大小影响算法的收敛速度，太小会使进化缓慢，太大可能造成发散或过早收敛。因此，本文提出了一种旋转角度的自适应策略（Adaptive angle rotation strategy），如式（12）所示：

3.4 算法流程

基于二维指数熵-量子遗传算法的图像多阈值分割方法流程图，如图3所示。

图3 本文算法流程图

1）设定种群的个数p、阈值对数C，代数g=0，最大进化代数gen以及结束条件μ，初始化全局最优多阈值对解为max_T，其相应的适应度值为max_H。按照式（5）产生初始种群；

2）用3.2小节中和半随机策略观察染色体种群产生多阈值解T（g）；

3）以式（2）作为适应度函数，评价 T（g）的适应度，从较大为原则更新max_T和max_H；

5）选择操作，将当代适应度最小的量子染色体替换为适应度最大的量子染色体；

6）如果两代平均种群适应度小于设定的值μ或者代数大于设定的进化代数gen，则结束，输出当前最优阈值对，程序结束；否则转向步骤2）。

3.5 多阈值变化检测算法

基于改进的量子遗传算法选取多阈值的SAR图像变化检测算法步骤如下：

1）使用中值滤波对两时相原始SAR图像进行滤波，降低图像中的噪声干扰；

2）生成差异图；

3）对差异图进行多阈值分割，具体分割流程如4.1；假设选取n个阈值，则差异图就被分成了n+1类；灰度最小的一类为未变化类；灰度最大的一类为变化类；灰度在未变化类与变化类中间的像素点则归为待分类点；

使用模糊C均值（FCM）算法确定待分类点类别。

4 实验结果与分析

本节设计实验测试本文算法的分割精度和时间性能。抗噪性和搜索性能试验中进行对比试验的4种量子遗传算法原理及测试图像如表1和下页图4所示。算法QGA1使用的是一维最大熵原理，算法QGA2使用的是随机产生阈值解的方法，算法QGA3使用的是固定旋转角度，QGA4是本文提出的算法。变化检测试验中比较了3种主要的阈值法：广义高斯假设的最小误差法（GG_KI）、最大类间方差法（OTSU）和期望最大化法（EM）。实验硬件环境：处理器CORE2 E7500，主频2.93 GHz，显卡ATI RADEON HD 4300/4500 Series，软件环境：Matlab R2014a。

表1 实验的4种算法

4.1 抗噪性测试

分别用算法QGA1和本文算法QGA4对Pillsetc图进行图像分割，用来对比二维熵与一维熵分割时的抗噪性。两种算法的实验参数均设定为：C=3，gen=500，population=20，μ=0.001，分割结果如图4所示。

从图4可以看出，利用最大二维熵原理分割图像的噪点明显少于基于一维熵原理的分割结果。这是因为二维熵直方图加入了像素邻域像素的信息，对噪声具有鲁棒性。

4.2 搜索性能测试

分别利用QGA1、QGA2、QGA3与QGA4对baboon、Barbara、Peppers、Lena 图像进行分割，用来测试本文提出的半随机策略产生阈值解的方法与提出的自适应角度在优化算法性能方面的表现。各算法的参数均设定为：gen=500，population=20，μ=0.001，其中，QGA3采用的固定旋转角度θ=0.005π，QGA4对4幅图像的分割结果如图5所示。每种算法独立运行100次分割操作，当C=1，2，3，4时将分割后的平均最大熵（me）、平均代数（mg）、平均时间（mt，单位s）数据统计在下页表2中。

图5 本文算法对测试图像的分割结果

表2 4种算法进行100次分割平均熵、平均代数、平均时间

对比QGA1与其他3种算法，其信息熵均小于其他3种算法，这是因为其他3种算法采用的是二维熵原理，能够得到更高分割精度；对比QGA2与本文算法，可以看出QGA2产生的部分熵值与本文算法相近，但是消耗了过多的时间，这是因为QGA2在产生阈值解时使用了完全随机的策略，大量产生的解被判为无效被否定，直到产生了符合期望的阈值解，在这个循环的过程中消耗了大量的时间，而本文算法采用了半随机产生阈值解的策略，线性变换使得阈值解从小到大排列，而后将第1维数据与随机因素按照特定的权重因子相加起来形成第2维阈值解，保证了阈值的相关性，大大加快了寻优速度；QGA3与本文算法相比，本文算法总体上迭代的次数少，算法速度快，这是因为本文算法采用了自适应旋转策略，从而加快了收敛速度。

4.3 变化检测实验

基于差异图的变化检测实际上是对差异图进行目标和背景的分割。经过多次试验证明，当选取C=2，即确定两个阈值，分成3类时得到的结果性能最好。其他参数设定为 gen=200，population=20，μ=0.001。为了节省篇幅，实验数据选取一组拍摄于1997年5月和1997年8月的渥太华地区水灾变化图，大小为 290×350，图6（c）为变化参考图。实验结果如图7所示。

相对于参考图，对3种方法的检测结果定量分析如下页表3所示。

图6 Ottawa实验数据

图7 Ottawa数据集不同算法变化检测结果图

GG_KI算法在均值比差异图中找到的分割阈值为199，结果中漏检数非常高，效果很不理想。RFLICM算法正确率检测准确率和Kappa系数较高，效果较GG_KI好很多，但是计算量大、用时过长。本文提出的算法在均值比差异图找到的分割阈值为90和165，检测结果正确率及Kappa系数均比其他两种方法高，分割效果更好。且尽管如此，速度比单阈值的GG_KI还要快，比RFLICM算法甚至提高了4倍以上，算法实时性好。

表3 Ottawa实验数据各检测结果的定量分析指标

5 结论

针对多目标复杂图像的分割问题，提出了一种改进的二维熵-量子遗传算法的图像多阈值分割方法，定义了二维阈值量子染色体编码方式；提出了一种基于半随机策略产生阈值解的方法，加快了寻优速度；改进了量子门旋转角度方式，提出了自适应旋转角度的方法，提高了算法的鲁棒性和收敛速度。通过图像分割和SAR图像变化检测实验验证，得到如下结论：

1）基于二维最大熵原理的分割图像统计了领域像素的灰度信息，图像分割的噪点明显少于一维熵的分割图像，并且具有更高的分割精度；

2）算法采用半随机策略产生阈值解，保证了阈值的递增性和相关性，其寻优速度较完全随机产生阈值解的量子遗传算法提高了3倍～5倍；

3）采用量子门自适应旋转角度策略，能够避免算法发散或过早收敛，提高算法优化的精度和速度，使算法更具鲁棒性。

量子理论在图像处理领域的研究还处于初级阶段，如何充分利用到量子的特点来解决图像处理中的难题如图像增强、识别等领域将是下一步的研究重点。