Image segmentation of 2-D maximum entropy based on the improved whale optimization algorithm

图像分割是图像处理中一项基本技术，是图像简化、目标区突出和降低分析难度的一种重要手段，为图像识别与分类的前提。所谓图像分割是依据一定的准则，将图像中人们感兴趣区域的内容提取出，其分割精确度影响后续结果。因此图像分割仍是一个研究前沿与热点，对此国内外学者对其进行大量的研究，许多有效的方法也陆续被提出，主要分为：基于色彩类型、基于不同分割依据和基于所用理论差异等。其中基于不同分割依据主要包括：边缘检测法、阈值法和区域生长法等^[1-2]。阈值法是图像分割最常用的处理方法，其操作简单、效率高和稳定性能好，本文中讨论的2维最大熵分割算法是阈值法中的一种。20世纪80年代，学者们开始将信息论中熵的概念用于选取阈值，熵代表平均信息量，熵越大，表明包含的信息量多^[3]。其中, 1维最大熵图像分割法缺点在于：该方法仅考虑灰度信息，而图像分割过程中易受噪声的影响，导致较差的分割效果。所以学者们将1维推广至2维，将点灰度-区域灰度同时考虑，具有较好的分割效果和抗噪性能。传统最大熵法通过将全部灰度级遍历以获取最优阈值，该方式计算难度大、耗时长和速度慢，从而难以实现实时性分割要求^[4-5]。

针对最大熵中的阈值选择问题，一些学者结合粒子群优化算法、遗传算法的优化特性，采用这些方法图像分割效果在一定程度上有所提高，但陷入局部最优，早熟收敛等弊端未能克服，同时图像分割精度有待提高^[6-7]。2017年，MIRJALILI等人^[8]受鲸鱼特殊觅食行为的启发提出了鲸鱼优化算法(whale optimization algorithm, WOA)，因其具有可调参量少、可操作性强、迅速收敛等优点，广泛应用于各种各样的优化问题中，为2维最大熵分割方法选取最优阈值提供一种新的手段。为了图像分割精度有所提高，将改进鲸鱼优化算法用于寻求最优分割阈值，定义基准函数为最大熵函数，通过实验测试分割结果。结果表明，本文中改进的算法能准确找到最优阈值，也能满足图像分割实时性的要求。

鲸鱼被认为是具有情感的高智能动物，最有趣的行为是它们特殊的觅食行为。包括3种不同的捕猎方式，分别为：包围式捕猎机制、泡泡网式捕猎机制和随机式捕猎机制^[8-9]。

鲸鱼识别到猎物位置后将其包围，因最优值位置在搜索空间是未知的，所以WOA假设当前的候选解是最优的。最佳搜索代理被定义后，其它搜索代理将尝试将其位置更新为最佳，由下式说明：

式中，D=|C·X^*(t)-X(t)|；A=2a·r-a；C=2·r；t表示当前迭代; A和C是系数向量; X(t+1) 表示候选解位置; X^*(t)表示最优解位置; a在整个迭代过程中(在探索和开发阶段)从2线性下降到0;r是[0, 1]中随机向量。

鲸鱼泡泡网式捕猎机制有两种方法：第1种为收缩包围机制是通过降低a值来实现，搜索代理新位置可在原始位置和当前最佳位置之间任何地方定义；第2种为螺旋式更新位置机制，是通过计算位于(X, Y)鲸鱼和位于(X^*, Y^*)猎物之间的距离，在鲸鱼和猎物的位置之间建立一个螺旋方程，由下式说明：

式中，D′=|X^*(t)-X(t)|表示第i只个体到食物源的距离，即目前为止的最优解，b为常数(定义为对数螺旋的形状)，l是[-1, 1]中的随机数。

注意到鲸鱼在一个缩小的圆圈内围绕猎物沿着螺旋形的路径游动。为了模拟这种同时进行的行为，优化期间假设在收缩包围机制或螺旋式模型之间有50%的概率来选择更新鲸鱼的位置，更新公式由下式说明：

式中，概率p是[0, 1]中的随机数。

随机捕猎机制是基于矢量A变化的方法来寻找食物源，数学模型由下面两个式子来说明：

式中，X_r为鲸鱼随机位置，A和D的求解已在上面给出。

对大多数群智能优化算法，群体初始化方式影响算法的计算效率。为使种群的个体保持多样性以及尽可能地分布均匀，本文中不再采用原算法的方式来随机生成种群，而是采用混沌序列结合反向解的初始化策略，这样有助于寻求解的遍历性和提高算法收敛速度。近年来，由于混沌序列具有遍历性、随机性等优点，所以将其作为一种优化技术。如今，在优化领域中有多种多样的混沌映射，主要包括logistic映射、tent映射和猫映射等。其中logistic序列的概率密度函数服从切比雪夫分布，映射点呈现两头密度高而中间密度低，因其遍历性与均匀性表现不佳，将影响全局搜索效率^[10-11]。而tent映射易在小循环或不动点上出现问题，若最佳解仅为边缘值时，可求得最佳解。针对以上的问题，本文中采用经典猫映射来生成鲸鱼初始群体。猫映射(cat映射)也称作Arnold映射，因经常由用猫脸演示而命名，猫映射定义如下式所示^[12]：

式中，a₁和b₁为任意实数，mod 1表示求a₁的小数部分。值得注意的是，仅当线性转换矩阵行列式数值为1时，才能产生正确的猫映射, 而当a₁=b₁=1时, 为经典Arnold映射，其Lyapunov指数分别为L₁=ln(3+$\sqrt 5 $)/2>0，L₂=ln(3-$\sqrt 5 $)/2 < 0，由于L₁>0，所以猫映射具有混沌特性。利用猫映射来产生初始种群，因该映射结构简单、不易陷入小循环或不动点，且在[0, 1]间产生的混沌序列有更好遍历均匀性。

混沌序列结合反向解初始化策略步骤为：首先可用猫映射产生当前种群的一个可行解{X=(x₁, x₂, …, x_d)(d为搜索空间的维度；x_j∈[u_j, v_j], 其中u_j和v_j表示可行解的上下界。)，则反向解定义为X′=(X₁′, X₂′, …, X_d′)，x_j=k(u_j+v_j)-x_j，k服从[0, 1]上的均匀分布^[13-14]。

在鲸鱼优化算法中，鲸鱼位置更新有着重要作用。鲸鱼捕食过程中，食物源位置有可能会发生位置的突变，以此来增加种群随机性。为避免WOA出现早期成熟而收敛及易陷入局部最优解，采用“疯狂算子”，用疯狂算子对鲸鱼位置更新机制进行建模^[15]。确保鲸鱼在提前设置的疯狂概率下，产生扰动因子对食物源位置进行扰动，目的是保持种群个体多样性，则(3)式位置更新公式为：

式中，C_r为疯狂算子，且C_r=P(c₄)×sign(c₄)×X₁。变量c₄是区间[0, 1]中均匀分布的一个随机数，X₁是一个取值非常小的一个常数，试验中取X₁=0.0001。其中P(c₄)和sign(c₄)由下面两个式子来说明：

式中，P_c为疯狂概率，本文中P_c=0.3。该概率下鲸鱼在位置更新过程中所捕获食物位置发生变化有较小可能性。因P_c取一个很小的数值，那么c₄将有很高的概率去超过P_c，而仅当c₄≤P_c时，疯狂因子P(c₄)的取值为1。实际上C_r的取值仅在3个数徘徊，目的是在鲸鱼位置更新过程中，很快地跳出局部最优，增加全局的收敛速度。

2017年, TANYILDIZI提出黄金正弦算法^[16](golden sine algorithm, Golden-SA)，该算法的灵感是来自数学上的正弦函数，其优点有易实现、收敛速度快和调节参量少。鲸鱼觅食行为包括3种机制：包围式捕猎机制，泡泡网式捕猎机制(收缩式机制与螺旋式机制)和随机式捕猎机制。其中随机捕猎机制是基于矢量A的变化，此阶段为探索阶段。事实上，鲸鱼可根据彼此位置随机搜索，因此，使用随机矢量值A>1或A < -1来迫使搜索代理远离其它无关的鲸鱼。与开发阶段不同，更新了搜索代理的位置，而不是目前为止找到的最佳搜索代理。这种机制和|A|>1一样都强调探索，并允许WOA进行全局搜索，随机捕猎机制数学模型已在上文给出。

XIAO等人将黄金正弦算法引入螺旋式狩猎机制中，在收敛速度上有所改善，但在测试函数上寻求最优解时，易陷入局部最优^[17]。本文中采用黄金正弦算法对鲸鱼优化算法随机式捕猎机制进行一定的改进。通过原始鲸鱼优化算法描述，随机捕猎阶段为探索阶段，此阶段强调全局搜索。将黄金正弦算法引入此阶段，有利于全局最优解的充分探索，减小了个体向最优解靠近的搜索空间，同时有利于平衡在“探索”和“开发”两个阶段。从而使算法的精度以及速度有一定提高，引入黄金正弦算法在随机捕猎机制后，(4)式和(5)式更新为下式：

式中，D=|x₁·C·X_r-x₂·X|；其中黄金分割系数分别为x₁=-π+(1-v)·2π；x₂=-π+v·2π; v=($\sqrt 5 $-1)/2，R₁∈[0, 2π]中的随机数和R₂∈[0, π]中的随机数，决定个体更新方向和移动距离^[18]。基于(7)式和(10)式两种手段，将本文中算法命名为IWOA，并将其应用于图像分割。

图像分割中应用信息论的香农熵，理论上是使图像中背景和目标信息量达到最大。1维最大熵虽有较快的处理速度，但仅考虑图像像素的点灰度信息，而区域相关性被忽略，从而表现出较差的分割效果以及抗噪性能^[19]。2维最大熵基于图像直方图将像素点灰度特征与区域灰度特征两者结合，从而图像有用信息能有效地被提取，通过使图像2维熵达到最大来获取最佳阈值。因此通过此方法可获得良好分割效果与抗噪性，其计算方法如下：设原始图像f(x, y)(x= 0, 1, …, M；y= 0, 1, …, N；M×N为分割图像的大小；f(x, y)= 0, 1, …, L)的灰度级为L(L=256)，以其中一个像素f(x, y)及其八邻域作为一个计算区域，可得到该像素的灰度均值。其中n_ij表示原图点灰度是i而区域灰度是j的像素点数, p_ij是点灰度和区域灰度均值对发生的概率^[20]：

图像的2维直方图由(11)式得到，如图 1所示。

Figure 1.  2-D histogram

典型的情况下，图像中目标或背景的像素占有最大比例，所在区域灰度级分布均匀，且点灰度与区域灰度均值无较大差别。由图 1可知，分布在对角线A区和B区，反映了图像中目标和背景。点灰度-区域灰度均值对发生的概率主要集中在对角线周围，即图 1中A区、B区。在对角线的C区、D区，概率值呈下降的趋势，这两个区反映图像中的边缘点和噪声点等。所以综上所述，为使目标和背景信息熵达到最大，应该在A区和B区运用2维最大熵法来确定图像分割的最佳阈值(s, t)。根据熵的定义，图像2维熵与阈值可通过如下公式得到:

式中，2维离散熵的定义为$H = - \sum\limits_i {\sum\limits_j {{p_{ij}}} } \ln {p_{ij}}$；则A区和B区的2维熵为：

同理，$H(B) = \ln {P_B} + \frac{{{H_B}}}{{{P_B}}}$。其中${H_A} = - \sum\limits_{i = 0}^{s - 1} {\sum\limits_{j = 0}^{i - 1} {{p_{ij}}} } \times \ln {p_{ij}}$, ${H_B} = - \sum\limits_{i = s}^{L - 1} {\sum\limits_{j = t}^{L - 1} {{p_{ij}}} } \ln {p_{ij}}$。因C区和D区主要是关于噪声与边界的信息，具有很小的概率(p_ij=0)，可忽略不计。则可得到P_B=1-P_A, H_B=H_L-H_A, 其中H_L=$\sum\limits_{i = 0}^{L - 1} {\sum\limits_{j = 0}^{L - 1} {{p_{ij}}} } \ln {p_{ij}}$，H(B)=ln(1-P_A)+(H_L-H_A)/(1-P_A), 则熵的判别函数由下式定义：

由以上公式可得熵函数(s, t)=H(A)+H(B)所选取的最佳分割阈值(s^*, t^*)应满足：

采用2维最大熵法并不仅是1维图像分割的简单扩展，因为每一对点灰度-区域灰度均值对的2维熵都进行计算，计算量呈指数增加，因此群智能优化算法有必要引用。

本文中选取了粒子群优化算法(particle swarm optimization, PSO)、灰狼优化算法(grey wolf optimizer, GWO)、蚁狮优化算法(ant lion optimization, ALO)以及原鲸鱼优化算法(whale optimization algorithm, WOA)与本文中算法(IWOA)在同等实验条件下进行对比。其中所有用于进行对比的算法迭代次数为500，种群大小为30。不同算法参量取值见表 1。其中，v_max表示飞行速度，w表示惯性权重, c₁和c₂都表示学习因子。

为验证本文中算法(IWOA)鲁棒性及改进点的优化效果优于其它算法，作者在多个不同特点的基准函数上进行寻优并进行对比，本文中的测试函数见表 2。

本文中算法(IWOA)与其它群智能算法试验结果对比见表 3。

函数f₁, f₂, f₃, f₄和f₅是单峰函数，这些函数只有一个全局最优，用来评价算法的开发能力。最优值和平均值反映了算法的寻优能力和有效性，而标准差反映算法的稳定性。从表 3中可以看出，IWOA在函数f₁和f₃能得到最优值0。其它3项指标也都达到了0，虽然在函数f₂, f₄和f₅没达到理论最优，但它们最优值、平均值和标准差都远远优于其它算法。其中函数f₂和f₄的标准差都达到0，说明IWOA稳定性强。同时也可以看出原始WOA的各项指标与其它算法相比，寻优能力次之，而ALO表现最差。

函数f₆, f₇, f₈, f₉和f₁₀为多峰函数，包括许多局部最优，用来评价算法的探索能力。从表 3中可以看出，函数f₇和函数f6上IWOA与WOA算法都能得到最优值，但IWOA在最先跳出局部最优。在函数f₈上，其各项指标都优于对比的算法。在函数f₉和f₁₀上，其理论值分别为0.00030, -3.32，IWOA最为接近理论值，且其余两项指标均优于其它算法。为进一步验证IWOA的收敛性，本文中选取实验中测试函数f₁, f₂, f₆, f₈和f₉的收敛曲线图进行展示，如图 2~图 6所示。其中横坐标表示迭代代数，纵坐标表示目前最佳值。

Figure 2.  f₁ convergence curve

Figure 3.  f₂ convergence curve

Figure 4.  f₆ convergence curve

Figure 5.  f₈ convergence curve

Figure 6.  f₉ convergence curve

基于本文中算法IWOA阈值优化步骤如下：(1)采用猫映射初始化IWOA参量，包括种群大小、初始位置X_i=(s_i, t_i)和迭代次数T；(2) 利用IWOA求分割阈值，目标函数表达式由(14)式说明; (3) 基于(7)式和(10)式更新鲸鱼位置；(4)基于(15)式求鲸鱼的适应值，将最小的适应值作为最优值；(5)判断是否达到最大迭代次数，结束计算，输出最佳阈值X^*=(s^*, t^*), 否则返到步骤(3)。

为验证本文中的算法IWOA优化最大熵获取最佳分割阈值，选择传统最大熵法、大津法和IWOA在同一编译语言进行实验对比。种群规模为20，迭代次数为30。本文中在MATLAB自带图片数据集football.jpg和coins.png两组图片进行验证。

本文中所有对比算法均采用MATLAB语言。实验环境为：Window10系统，4G内存，MATLAB R2016b平台。

从图 7b~图 7d及图 8b~图 8d中可以看出，大津法虽能从背景中分割出目标，但细节几乎没有体现。从图 7c可以看出，传统最大熵法相比大津法在细节上有所提高，但效果不佳。从图 7d的分割结果中可看出，利用IWOA结合最大熵分割图像，目标相对全面清晰，可看出硬币大致轮廓、纹理和痕迹都有体现。图 8d中足球上的英文字母及线条都能看清, 表明熵值越大，所包含的信息量越多，说明可使图像中大量信息量被提取。试验表明，IWOA结合最大熵对图像分割是可行的。从表 4可以看出，每经过一次阈值筛选，都要进行熵的计算，假设计算时间为一个固定数G，那么对于一个灰度级为256的图像，当进行1维熵分割时，需计算熵256次，总共计算时间为256G。而当进行2维熵分割时总计时间256×256G，从而可以看出，2维熵分割时间计算量大，导致分割消耗时间长，采用IWOA结合传统最大熵对图像进行分割，分割时间所消耗时间最少。

Figure 7.  a—original coins.png b—segmentation image of 2-D Ostu c—segmentation image of 2-D maximum entropy d—segmentation image of IWOA

Figure 8.  a—original football.jpg b—segmentation image of 2-D Ostu c—segmentation image of 2-D maximum entropy d—segmentation image of IWOA

与很多群智能算法一样，鲸鱼优化算法对大多数优化问题依赖性小。为能精准在图像分割过程中找到目标区域及能很好地解决计算量大问题，将改进鲸鱼优化算法用于2-D最大熵图像分割，为避免WOA算法出现过早收敛和易陷入局部最优解，在其位置更新公式上引入疯狂算子，提高算法的收敛速度。同时在随机捕猎机制在引入黄金正弦算法，使种群多样性得以保证及算法的精度有一定提高。结合IWOA和2维最大熵各自优点实现图像有效分割，实验结果表明，与其它分割算法相比，IWOA能实时地分割出目标图像，目标图像视觉效果表现较为理想，且分割消耗时间最短。鲸鱼优化算法鲁棒性强，可用在多个领域，不取决研究问题的领域，因此具有广泛地研究意义。