Page 127 - 《软件学报》2021年第11期

霍星 等:改进的元启发式优化算法及其在图像分割中的应用 3453

the problem like the local optimum. It is concluded that the algorithm balances the local and global search, which effectively compensates
the shortcomings of the algorithm that is easy to fall into local optimum. In order to verify the effectiveness of the NBAS algorithm, this
study combines the NBAS algorithm with the two-dimensional Kaniadakis entropy algorithm, and proposes a fast and accurate NBAS-K
entropy image segmentation algorithm. The NBAS-K entropy solves the problems that the optimization algorithms used for image
threshold segmentation function are easy to fall into local optimum, and have the large number of optimization individuals and the high
design complexity, which results in large amount of computation and time-consuming. Finally, the NBAS algorithm is combined with the
two-dimensional K entropy algorithm to generate a fast and accurate NBAS-K entropy image segmentation algorithm. The experimental
results of the NBAS-K entropy algorithm, BAS-K entropy algorithm, BBAS-K entropy algorithm, Genetic-K entropy algorithm (GA-K
entropy), particle swarm optimization-K entropy algorithm (PSO-K entropy), and grasshopper optimization-K entropy algorithm (GOA-K
entropy) on Berkeley datasets, artificially noisy images, and remote sensing images show that the proposed method not only has better
anti-noise performance, but also has higher precision and robustness, and can realize complex image segmentation more effectively.
Key words: image segmentation; threshold; Kaniadakis entropy; beetle antennae search algorithm; particle swarm optimization
algorithm; genetic algorithm; grasshopper optimization algorithm

元启发式算法于 20 世纪 60 年代提出,得到了广泛应用,具有计算量低、优化效率高等优点.该类算法以模
仿自然界中各类运行机制为特点,具有自我调节的特征,解决了诸如梯度法、牛顿法和共轭下降法等传统优化
算法计算效率低、收敛性差等问题,在组合优化、生产调度问题、图像处理等方面均取得了很好的效果.也正
是因为该类算法的高效率性和强收敛性,越来越多的学者将其应用到了图像阈值分割中,进行最佳阈值寻优.遗
[1]
传算法(GA) 属于较早提出的一种元启发式算法.该算法基于达尔文进化论和遗传学原理,运算对象是一定规
模的种群,通过群体个体(染色体)之间的选择、交叉和变异这 3 个基本遗传操作来模拟生物的进化过程,保留优
[2]
秀个体,淘汰劣质个体,形成新的种群.经过反复迭代,最终得到最优解.刘健庄等人 将遗传算法与图像阈值分
割结合,提出了基于 GA 的多级阈值分割算法.后续不断地有学者将 GA 应用到图像阈值分割领域中 [3−6] .粒子群
[7]
优化算法(PSO) 是 Kennedy 等人提出的另一种元启发式算法.该算法基于鸟类集群活动规律性和群体智能活
动模型,通过更新个体历史最优值和种群全体最优值来寻找全局最优,与 GA 相比,PSO 算法没有“交叉”和“变
异”操作,相对简单.PSO 算法以其实现复杂度较低、精度高和收敛快等优点受到了众多学者的青睐.PSO 算法在
处理非线性、多目标优化和高维优化问题上有很好的健壮性,但在处理离散空间问题上表现得并不理想.为此,
[8]
Kennedy 等人 提出了离散二进制版本的粒子群优化算法(BPSO).在 BPSO 中,速度项转变为位置项中位取 1 的
概率.BPSO 算法是原粒子群算法的拓展版本,既可以处理连续系统优化问题,也可以处理离散系统优化问题.随
[9]
后,刘建华等人 分析发现,BPSO 具有过强的随机全局探索性而缺少后期的局部搜索性,通过改进 BPSO 算法,
提出了新的二进制离散粒子群算法(NBPSO).为了平衡原始 PSO 算法的局部搜索能力和全局搜索能力,Shi 等
人 [10] 在原始 PSO 的速度项中引入了惯性权重,动态调节收敛性和收敛速度.PSO 算法由于结构简单、涉及专业
知识少、易于实现,在许多领域如图像的阈值分割领域有着重要应用 [11−13] .蚱蜢优化算法(GOA) [14] 是近几年提
出的基于蚱蜢群体智能活动的另一元启发式算法,Sharma 等人 [15] 利用 GOA 算法来处理 SAR 图像分割的最优
阈值搜索,在分割时间和精度方面均有不错的效果.该算法性能虽好,但所需输入参数较多,且算法设计复杂度
高,不利于实际应用.上述优化算法存在 3 个共同问题:算法原理中涉及多个寻优个体,计算量大;算法设计复杂
度高;易陷入局部收敛.天牛须搜索算法(BAS) [16] 是由李帅等人提出的一种高效的智能优化算法,类似于粒子群
算法、遗传算法、蚱蜢算法等智能优化算法,BAS 优化算法不依赖于具体函数形式和梯度信息,能够有效实现
自动寻优过程.与其他算法相比,其优点在于算法设计复杂度低,可以在较短的时间内解决优化问题.
本文针对上述优化算法存在的寻优个体过多、算法设计复杂度较高、计算量较大、耗时长,且易陷入局部
收敛等问题,提出一种新的天牛须优化算法(NBAS).该算法首先将原始 BAS 算法拓展为二进制离散天牛须算
法(BBAS);然后利用其高全局搜索性,将其作为辅助算法与 BAS 结合,解决了 BAS 易陷入局部最优的不足;最后,
将二维 K 熵阈值分割准则函数作为目标函数,与 NBAS 结合得到基于 NBAS 优化的二维 K 熵阈值分割算法
(NBAS-K 熵),利用 NBAS 全局优化算法快速准确地搜寻最佳阈值,实现图像的有效分割.