基于混沌布谷鸟优化的二维Tsallis交叉熵建筑物遥感图像分割

吴一全 周建伟

（1.南京航空航天大学电子信息工程学院，南京，211106；2.城市空间信息工程北京市重点实验室，北京，100038；3.数字出版技术国家重点实验室，北京，100871）

引 言

近年来遥感成像技术的迅速发展，使得获取的遥感图像质量越来越高。利用遥感图像进行人工地物信息的自动提取，可以有效地提升工作效率，避免繁琐的人工调查。建筑物作为一类重要的人工地物目标，利用遥感图像对其进行自动提取和识别在数字化城市的创建、地理信息更新及军事目标监测等方面有着重要意义和实际应用价值[1-3]。建筑物遥感图像分割是建筑物目标提取的首要且关键的一步，图像的分割效果对提取的准确性有着重要的影响[4]。

阈值分割作为一类有效的遥感图像分割方法，其最关键的是快速地选择一个特定阈值，最终实现分割[5-7]。其中关注最多的是基于熵的方法，Kapur等人[8]最早提出了基于一维最大熵法，这种方法简单有效，能得到较好的结果，然而因为无法反映图像的局部信息，对于有噪图像的分割不是很准确。Brink[9]将最大熵法推广到二维直方图，改善了图像的分割结果，但是增加了计算复杂度，难以满足实时处理的要求。Sahoo等人[10]在上述基础上运用了Tsallis熵，导出了基于二维Tsallis熵的分割方法，减少了运算时间，但是分割效果不理想。为了利用内部灰度的均匀性，文献[11]导出了基于二维Tsallis灰度熵法，提升了图像的分割效果，但在分割复杂背景的图像时结果不如意。Li等人[12]给出了基于二维最小交叉熵的方法，分割的结果较准确，然而与最大熵同样存在在零点处无定义值的问题。针对这一问题，文献[13]提出基于二维倒数交叉熵方法，避免了对数运算，在一定程度上加快了速度，但分割结果的准确性仍需提高。文献[14]则结合了最小交叉熵与Tsallis熵，给出了基于二维最小Tsallis交叉熵法，使得分割结果更加精确，然而该方法的运行时间仍旧较长，有待进一步缩短。

为了进一步加快阈值选取的运算速度，人们将群智能优化算法引入图像阈值分割领域。文献[15]利用遗传算法来搜寻最大模糊熵下的最佳阈值，进一步加快了方法的运行速度。文献[16]在二维阈值选取过程中引入粒子群优化算法，在一定程度上减少了运行的时间。文献[17]则利用人工蜂群优化阈值选取过程，有效地提升了方法的运行速度。近几年出现的布谷鸟搜索算法(Cuckoo search,CS)[18]相较于上述的智能优化算法，具有算法简便、需设置参数较少、实现容易、可沿较优路径搜索、可收敛到全局最优且收敛速度快等优点，目前已被应用于函数优化[19]、预测问题[20]等应用领域。然而CS算法可能会陷入局部最优点，为了解决这一问题，本文将混沌理论引入CS算法，利用混沌映射的伪随机性使算法避免陷入局部最优。

基于以上分析，本文提出了基于混沌布谷鸟搜索(Chaotic cuckoo search，CCS)的二维Tsallis交叉熵建筑物遥感图像分割方法。首先给出了二维Tsallis交叉熵的选取公式，然后使用Logistic映射，将混沌扰动引入布谷鸟搜索算法以加快算法的运算速度，最后利用该混沌布谷鸟搜索算法优化阈值的寻找过程，并以此分割建筑物遥感图像。针对大量建筑物遥感图像进行实验，并与二维倒数交叉熵法[13]、二维Tsallis熵法[10]、基于混沌粒子群优化(Chaotic particle swarm optimization，CPSO)的二维Tsallis灰度熵法[11]等方法进行比较，验证了本文的方法分割建筑物遥感图像时拥有明显的优势。

1 二维Tsallis交叉熵阈值选取公式

设图像f(m,n)的尺寸为M×N，灰度级总数为L，定义图像像素点(m,n)的8-邻域平均灰度f(x,y)，D一般取像素点的8-邻域，W表示邻域D中像素的个数。用h(i,j)代表二元对(f=i,g=j)在该图像中出现的个数(0≤h(i,j)≤M×N)，则二元对(i,j)的联合p(i,j)=1，由p(i,j)构成该图像的二维直方图，其区域划分如图1所示。假设i=t,j=s两条直线把直方图分割为4块区域，将图像中亮（暗）的区域设成目标（背景），则0，1分别表示目标及背景区域，2，3分别表示边界及噪声区域。在边界和噪声区域，其像素点与整幅图像的像素总数相比，数量很小，可以忽略不计，其p(i,j)≈ 0。

因此，目标类和背景类的先验概率分别为

对应的灰度均值向量分别为

图1 二维直方图区域划分Fig.1 Division of 2-D histogram region

则图像的二维Tsallis交叉熵为

2 混沌布谷鸟优化的二维Tsallis交叉熵分割方法

2.1 布谷鸟搜索算法

CS算法由Yang Xinshe仿照自然界中布谷鸟的寄巢产卵特点和部分生物的莱维(Levy)飞行模式，于2009年提出。其主要思想是通过随机游走方式产生候选鸟巢以及采用贪婪策略更新鸟巢位置，最终使鸟巢位置达到或者接近全局最优解。CS算法假定了以下3个条件：

(1)布谷鸟每次仅仅产一只卵，孵化时鸟巢的选择是随机的；

(2)对于每组鸟巢，最好的可以留至下一代；

(3)可以用来放卵的鸟巢数目一定，鸟巢主人察觉布谷鸟卵的概率为Pα。

CS算法的鸟巢坐标位置与解空间中的解一一对应，在以上3个假定基础上，CS算法利用Levy飞行随机行走方式和偏好随机行走方式更新鸟巢位置。

(1)Levy飞行随机行走。主要利用式(5)产生新解

由于对Levy分布积分比较困难，文献[21]证明了可以采用Mantegana算法实现等价计算，即

式中：σv=1，β=1.5。 σu求解公式为

式中Γ()表示伽马函数。
(2)偏好随机行走。仿照寄主察觉布谷鸟的卵后将其丢弃的想法和原理。具体操作如下：任意得到一个满足[0,1]均匀分布的随机数r，并与发现概率Pα∈[0,1]进行比较，若r＞Pa，则按式(9)得到新解

通过上述两种方式所得的新解均采用贪婪选择操作，即得到新解后，将新解和原解的适应度函数值进行比较，与原解相比，若新解较优，那么将新解取代原解，反之保留原解。

2.2 混沌CS算法

在标准CS算法中，随机游走模式的单一导致其搜索时针对性不强。混沌具有伪随机性、规律性、对初值敏感等优点，在可行域内能够搜寻到所有状态。因此在CS算法中融入混沌序列，可以使算法更容易跳出局部最优点，提升算法在后期的收敛速度，提高算法解的质量。因此，本文使用Logistic映射的混沌扰动算子对CS算法进行改善，以期减少分割方法的求解时间。

Logistic映射的表达式如下

式中μ为控制变量。

为了提升算法的准确性，对每一次更新的最佳鸟巢位置添加混沌扰动，扰动方法可由式(11)确定

式中：γ为比例系数；Xbest,d为当代最佳位置的第d维向量；Xnewbest,d表示新的最佳位置的第d维向量；xd为当代由式(10)产生的混沌序列。

2.3 方法流程图与步骤

本文方法的基本思路为：根据建筑物遥感图像的二维直方图计算二维Tsallis交叉熵，采用混沌映射改进CS算法并优化阈值的选取过程，最终完成对建筑物遥感图像的分割。图2为本文方法流程图。

本文方法具体步骤如下：

步骤1 初始化算法的基本参数：鸟巢数目n=20，发现概率Pa=0.25，搜索精度ε，最大迭代次数Tmax=100；

步骤2 用鸟巢位置代表图像的二维阈值(t*,s*)，并且以随机方式生成n个鸟巢的初始位置，根据式(3)计算初始鸟巢位置的二维Tsallis交叉熵，求得初始最小的值；

步骤3 利用式(5—8)更新当前的所有鸟巢，求出当前所有鸟巢的二维Tsallis交叉熵，若新鸟巢的二维Tsallis交叉熵小于原鸟巢的二维Tsallis交叉熵，则替换鸟巢位置；

步骤4 根据式(9)采用偏好随机行走方式更新鸟巢的位置，仍旧用二维Tsallis交叉熵较小的位置取代原位置，求得当代最小的二维Tsallis交叉熵，且和前一代的值对比，记录最佳的鸟巢位置；

步骤5 利用式(10)和式(11)对最佳的鸟巢位置进行混沌扰动，并与扰动之前进行对比，保留二维Tsallis交叉熵更小的一组鸟巢位置；

步骤6 若未满足设定的搜索精度或未达到最大的迭代次数，重新回到步骤3，反之继续；

步骤7 输出最优阈值(t*,s*)，并以此分割建筑物遥感图像。

图2 本文方法流程图Fig.2 Flowchart of proposed method

3 实验结果与分析

对于多类建筑物遥感图像，采用本文提出的基于CS及基于CCS的二维Tsallis交叉熵法进行了大量实验，并与二维倒数交叉熵法、二维Tsallis熵法、基于CPSO的二维Tsallis灰度熵法进行对比，给出了5种方法分割后建筑物遥感图像结果及运行时间。受篇幅限制，现以其中3幅不同种类建筑物遥感图像的分割结果加以说明，分别为建筑物遥感图像1（500像素×274像素）、建筑物遥感图像2（543像素×366像素）、建筑物遥感图像3（454像素×473像素）。图3—5分别给出了3幅原始建筑物遥感图像及二维倒数交叉熵法、二维Tsallis熵法、基于CPSO的二维Tsallis灰度熵法、基于CS的二维Tsallis交叉熵法、基于CCS的二维Tsallis交叉熵法处理后的图像。其中，基于CPSO的二维Tsallis灰度熵法的粒子群数为20，最大迭代次数为100；基于CS的二维Tsallis交叉熵法和基于CCS的二维Tsallis交叉熵法的最大迭代次数为100，种群规模为20，概率Pa=0.25。本文实验的运行环境为Intel(R)Core(TM)i5 CPU 2.50 GHz/4 GB,Matlab R2015b。

如图3所示，建筑物遥感图像1中包含建筑物、道路及河流等目标，从分割结果中看出：二维倒数交叉熵法在分割时，部分建筑物和道路连在一起，因此误分割率很高，特征不鲜明；二维Tsallis熵法分割结果较差，未准确地分割出目标；利用基于CPSO的二维Tsallis灰度熵法得到的效果不是很理想，大部分建筑物无法分辨；而本文提出的基于CS及基于CCS的二维Tsallis交叉熵法则对建筑物轮廓及细节有着精确分割，边缘比较完整，且可以较好地将建筑物和河流及道路分开。

图3 建筑物遥感图像1及其分割结果Fig.3 Remote sensing image of Building 1 and its segmentation results

如图4所示，建筑物遥感图像2中建筑物聚集，且具有不同形状，复杂度较高。二维倒数交叉熵法分割较为准确，但仍有一部分背景误划分成了建筑物；二维Tsallis熵法误分割部分较多；基于CPSO的二维Tsallis灰度熵法未完全分离目标和背景，多数建筑物未被分割出来，效果不佳；而本文提出的基于CS及基于CCS的二维Tsallis交叉熵法效果较好，准确地将建筑物及背景分离，提取出的建筑物边界使得纹理细节更为丰富。

如图5所示，建筑物遥感图像3中建筑物周围有着植被和道路，干扰较多，分割结果显示：二维倒数交叉熵法和二维Tsallis熵法未能准确地分开建筑物与地面区域，势必会影响之后的检测识别效果；基于CPSO的二维Tsallis灰度熵法仍有部分道路误分割，且部分建筑物边缘模糊残缺，纹理特征不太丰富；本文提出的基于CS及基于CCS的二维Tsallis交叉熵法可以很好地将建筑物和道路分开，同时在有噪声干扰状况下，仍然能将建筑物准确地分割出来，说明抗噪性能强。综合所有结果，采用本文提出的方法对建筑物遥感图像进行分割，能得到明显良好的效果。

表1列出了5种分割方法的最佳分割阈值及运行时间。从表1能够看出，二维倒数交叉熵法和二维Tsallis熵法由于穷举了所有像素值，因此所需的运行时间较长；基于CPSO二维Tsallis灰度熵法因为使用了群智能算法，相对缩短了时间；而本文提出的基于CS及基于CCS的二维Tsallis交叉熵法方法进一步缩短了时间，且基于CCS比基于CS的方法平均节省了50%。

为了进一步分析CS算法及混沌CS算法的收敛特性，选取实验中的一幅图像，分别用两种方法进行50次独立实验并取平均，绘出迭代次数与目标函数的关系图如图6所示。从图中能够得到，CS算法会在迭代的过程中落入局部极值点，迭代更新的后期收敛速度变得缓慢，平均需要40次迭代达到收敛，影响算法的运行速度；而混沌CS算法却并没有陷入局部最优，收敛速度快，在16次迭代左右就已经收敛，大大减少了算法运行时间。

图4 建筑物遥感图像2及其分割结果Fig.4 Remote sensing image of Building 2 and its segmentation results

图5 建筑物遥感图像3及其分割结果Fig.5 Remote sensing image of Building 3 and its segmentation results

图6 CS算法和CCS算法的迭代过程图Fig.6 Iterative process of CS algorithm and CCS algorithm

表1 5种方法的最佳分割阈值及运行时间比较Tab.1 Comparison of five methods in optimal thresholds and running time

4 结束语

针对建筑物遥感图像，本文提出了基于混沌布谷鸟优化的二维Tsallis交叉熵分割方法。Tsallis交叉熵综合考虑了分割前及分割后图像信息的差异性和关联性，可以提高遥感图像的分割效果。首先给出了二维Tsallis交叉熵的阈值选取公式，然后采用布谷鸟搜索算法优化阈值搜索过程，同时为了进一步提升方法的收敛速度，利用Logistic映射生成的混沌序列来改进布谷鸟搜索算法，有效地减少了方法的运行时间。针对建筑物遥感图像进行了大量实验，并与二维倒数交叉熵法、二维Tsallis熵法、基于CPSO的二维Tsallis灰度熵法等方法相比，本文方法能够更准确地分割建筑物遥感图像，运算时间更短，可认为是一种行之有效的建筑物遥感图像分割方法。