聂方彦, 张平凤, 潘梅森, 张 奋



基于Renyi熵与PSO算法的图像多级阈值分割

聂方彦*, 张平凤, 潘梅森, 张 奋

(湖南文理学院 图形图像处理技术研究所, 湖南 常德, 415000)

在图像阈值分割方法中, Renyi熵法因其显著效能而得到大量应用. 为了更好地发挥Renyi熵在图像分割中的应用, 提出把Renyi熵法扩展到图像多级阈值化问题. 然而, 由于计算时间复杂度上的高要求, 很难把这种有效的技术推广到复杂图像多级阈值化问题. 为减少本方法的计算时间, 应用粒子群优化算法实施最佳阈值的搜索. 实验结果表明, 本方法能有效地对图像进行多级分割, 并且显著降低计算时间.

图像分割; 多级阈值化; Renyi熵; 粒子群优化

图像分割是图像处理和前期视觉处理中的基本技术, 是大多数图像分析及视觉系统的重要组成部分, 也是成功进行图像分析、理解与描述的关键步骤, 在计算机视觉研究领域一直受到国内外众多研究人员的高度重视[1—6].

在图像分割方法中, 基于阈值化的技术由于其简洁有效性在图像分割领域一直得到众多研究人员青睐. 近年, 基于熵的全局阈值化图像分割方法被许多学者提出[3—6]. 两级阈值化是常用的图像分割方法, 当要对复杂图像进行分析时有必要对图像实施多级分割分别提取感兴趣目标[7—9]. 然而, 在众多基于熵的阈值化方法中, 由于计算上的复杂性, 把熵方法扩展到图像多级阈值化问题应用于复杂图像分析却少有论及. Sahoo等人[3]提出一种基于Renyi熵的两级图像阈值分割方法, 把Renyi熵用于图像分割能使图像的目标与背景很好的分离. 粒子群优化(Particle swarm optimization, PSO)[10]算法在各领域的应用被证明是一种非常有效的工程优化方法, 为了有效的对复杂图像进行多级阈值分割, 并降低计算复杂性, 结合PSO算法本文提出一种基于Renyi熵的多级阈值图像分割方法.

1 Renyi熵图像分割

假设= {p|= 0, … ,-1}是一幅具有级灰度的图像灰度级概率分布. 对于一幅×的图像, 灰度级的概率可用图像的直方图估计出, 也即p=n/(×), 这里n表示第级灰度在图像中出现的频度. 在两级图像阈值化方法中, 图像背景与目标的概率分布可由下式给出:

其中p=0+1+ … +p,p=p+1+p+2+ … +p-1. 根据Renyi熵定义, 图像背景与目标的先验Renyi熵定义为:

把Renyi熵阈值分割扩展到图像多阈值分割问题时, 考虑有个阈值1,2, …,t把图像分割成+ 1类不同的区域, 各类的概率分布可定义为:

假设0=-1,t+1=-1, 其中P=p-1+1+ p-1+2+…+ p,= 1, 2, …,+1, 则每类的先验Renyi熵定义为:

根据Renyi熵阈值分割方法, 多阈值的图像Renyi熵分割为最大化1+2+ …++1, 也即:

2 粒子群优化算法

粒子群优化算法[10]是在模仿基于社会群体行为的基础上由Kennedy与Eberhart两人在1995年联合提出的一种并行演化计算技术. 其核心思想是通过群体中个体之间的协作和共享来寻找最优解. 由于算法易于实现和高效性而被广泛应用于各工程领域, 并取得了很好的效果. PSO在工作过程中, 随机产生一个包含有个粒子的群, 每一个粒子是问题的一个实验解, 通过若干代的迭代寻优, 最终得到最优解. 在每一代的优化过程中粒子群中的每一个粒子根据它的先前一代的自身最优解pbest与全局最优解best以速度v在维搜索空间中动态调整自身的位置p. 在迭代过程中, 每一个粒子的速度与位置根据下面两式进行调整.

式中,表示迭代数,是惯性加权系数,1、2是学习因子,1、2是服从均匀分布的位于[0, 1]之间的随机数. 在文献[10]中, Clerc与Kennedy在式(9)中使用了一个收缩因子以保证算法的收敛.

式中=1+2, 且> 4, 若取1= 2.1、2= 2.0, 则的一个典型值就是0.729 8.

在PSO算法中, 经过一定代数的迭代以后, 若粒子群中的问题最优解不再变化或迭代达到一个最大迭代数则算法终止.

3 图像多级阈值分割算法

有感于Renyi熵在图像阈值分割中的有效性及PSO算法在工程优化问题中的优良表现, 我们结合这2种方提出了一种新的高效的快速复杂图像多阈值分割算法. 对于级Renyi熵图像阈值化问题, 粒子群中的粒子表达式设计为:= (1,2, …,t), 式中向量中的每一个值表示一个阈值, 0 <1<2<…<t<. 在基于PSO算法的工程优化问题中, 粒子间通过一个适应值函数进行竞争产生best和best, 对于Renyi熵图像多阈值化问题, 可用式(5)作为粒子间竞争的适应值函数. 当算法迭代终止, 粒子群中的全局最优解即可作为问题的最优解. 基于PSO算法的Renyi熵图像多阈值分割算法描述如下.

Step 1: 初始化. 初始化个粒子位置、粒子自身最优解best、粒子速度, 最大迭代数MAXIT, 学习因子1、2, 并置迭代计数器= 0.

Step 2: 评估. 根据式(5)评估每个粒子的函数值().

Step 3: 选择. 比较粒子的个体最优解与它当前的适应值函数值, 根据下式更新它的个体最优解.

从个best中选出一个具有最大适应值函数值的个体最优解做为全局最优解best.

Step 4: 更新. 根据式(8)和(7)更新粒子的速度与位置.

Step 5: 迭代.=+1, 转到Step 2, 循环直到满足停机准则.

4 实验与分析

本实验在一台Intel(R) Core(TM)2 Duo CPU T8100 2.10GHz笔记本电脑上用Matlab(R2007b)语言实现了所提出的算法, 并用若干幅图像对所实现的算法进行了测试, 在这里仅列出众多图像处理相关文献常用的两幅具有多峰分布的标准测试图像的测试结果. 这2幅图像是尺寸为256 × 256、256级灰度级的Lena与Pepper图像. 从图1与图2可以看出, 图像Lena与Pepper具有复杂的灰度直方图分布, 单靠两级阈值化不能完全有效地把信息分离开来. 为了比较算法的有效性, 对所提出的算法与基于Renyi熵图像多阈值穷尽分割方法进行了比较. 在实验中, 算法的各参数设置为: 种群规模20, 最大迭代次数500,1= 2.1,2= 2.0, 故= 0.729 8, 参数根据文献[6]的经验值, 在这里设置为= 0.7, 停机准则为算法迭代到最大迭代次数或得到的最优解趋于稳定. 表1与表2列出了这两种方法分别对Lena及Pepper图像的实验结果.

图1 Lena图像及其直方图

图2 Pepper图像及其直方图

表1 Lena图像PSO法及穷尽法Renyi熵分割阈值比较

表2 Pepper图像PSO法及穷尽法Renyi熵分割阈值比较

从表1、表2可以看出, 在对复杂图像进行多阈值分割时, 用基于PSO算法的Renyi熵分割得到的多级阈值与用穷尽方法得到的多级阈值进行比较, 每个阈值的偏差没有超过5个灰度级, 从算法运行时间来看, 除两级阈值基于穷尽方法的算法运行时间比基于PSO算法的所需时间较少以外, 在另外几级阈值化问题上, 基于穷尽方法所需的时间远远高于基于PSO算法所需的时间. 从时间复杂度上进行分析, 基于穷尽方法的时间复杂度为(L), 其中为灰度级数,为阈值个数, 对于基于PSO算法的分割方法, 其最大时间复杂度为(×MAXIT), 其中为粒子个数, MAXIT为算法最大迭代次数, 在实验过程中发现MAXIT不必设得非常大, 一般算法迭代15代左右即收敛. 从这点来说, 本文提出的方法大大减少了Renyi熵多阈值分割所需时间, 很好地拓展了Renyi熵在图像多级阈值问题领域的应用.

图3列出了基于PSO算法的Renyi熵Lena图像的2—6级阈值及其分割图. 图3(a、c、e、g、i)分别为Lena图像的两级、三级、四级、五级及六级阈值化图, 图3(b、d、f、h、j)是各级阈值化在原始Lena图像直方图上标出的对应阈值. 从图3也可以看出用基于PSO算法的Renyi熵多级阈值化方法对图像进行分割能得到较好的分割结果.

图3 Lena图像2—6级阈值化结果

5 结束语

本文针对Renyi熵在图像多阈值分割中计算复杂度高, 难以实现的难题, 提出了一种基于PSO算法的Renyi熵快速图像多阈值分割算法. 通过众多实物图像在所实现的算法上的验证, 我们所提出的算法在进行图像多阈值分割任务时, 所需时间大大降低, 所得阈值与穷尽方法相差微小, 经过多次重复实验, 应用所提出的算法得到的阈值稳定. 实验结果充分表明本文方法不仅对不同类型的复杂图像均能取得较好的多阈值分割结果, 而且在运算代价上具有明显的优势, 为基于Renyi熵的图像分割提供了一种新的思路.

在进行多阈值分割任务时, 现行算法在工作前需人为指定阈值个数, 在对复杂图像进行分割有时并不能事前知道需对图像进行几级阈值化, 而且确定图像的阈值级数也是一个非常复杂的难题, 我们下一步的工作将针对图像的自动多阈值分割问题结合所提出的算法展开研究.

[1] 翟艳鹏, 郭敏, 马苗, 等. 结合灰色理论和粒子群算法的归一化图像分割[J]. 计算机应用研究, 2011, 28(2): 776— 778.

[2] 聂方彦, 高潮, 郭永彩. 基于新模糊准则与DE算法的红外人体图像分割[J]. 计算机应用研究, 2010, 27(4): 1594— 1597.

[3] Sahoo P K,Wilkins C,Yeager J. Thresholding selection using Renyi's entropy[J].Pattern Recognition,1997,30(1): 71—84.

[4] Sahoo P K, Arora G. A thresholding method based on two-dimensional Renyi's entropy[J]. Pattern Recognition, 2004, 37(6): 1149—1161

[5] 黄金杰, 郭鲁强, 逯仁虎, 等. 改进的二维Renyi熵图像阈值分割[J]. 计算机科学, 2010, 37(10): 251—253.

[6] 聂方彦, 高潮, 郭永彩. 灰度图像的模糊Renyi熵多级阈值分割方法[J]. 系统工程与电子技术, 2010, 32(5): 1055— 1059.

[7] Horng Ming-Huwi. Multilevel minimum cross entropy threshold selection based on the honey bee mating optimization[J]. Expert Systems with Applications, 2010, 37(6): 4580—4592.

[8] Yin Peng-Yeng. Multilevel minimum cross entropy threshold selection based on particle swarm optimization[J]. Applied Mathematics and Computation, 2007, 184(2): 503—513.

[9] Sanjay Agrawal, Rutuparna Panda, Sudipta Bhuyan, et al. Tsallis entropy based optimal multilevel thresholding using cuckoo search algorithm[J]. Swarm and Evolutionary Computation, 2013, 11:16—30.

[10]Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58—73.

Image multi-thresholding using Renyi entropy and PSO

NIE Fang-yan, ZHANG Ping-feng, PAN Mei-sen, ZHANG Fen

(Institute of Graphics and Image Processing Technology, Hunan University of Arts and Science, Changde 415000, China)

In image segmentation, Renyi-based thresholding method has obtained widely application because of its remarkable effectiveness. In order to develop the latent ability of Renyi-based method in image segmentation, the method was extended to multi-thresholding field. However, due to the time complexity, the Renyi entropy-based method was very difficult extended to multi-thresholding scenario straightly. To overcome this problem, a fast multi-thresholding method combined with the particle swarm optimization algorithm for complex image segmentation was proposed based on Renyi entropy. The experimental results show that the proposed method can reduce the computation time greatly, and obtain ideal segmentation result.

image segmentation; multi-thresholding; Renyi entropy; particle swarm optimization

10.3969/j.issn.1672-6146.2013.03.010

TP 391.4

1672-6146(2013)03-0044-05

email: niefyan@163.com.

2013-05-02

湖南省普通高校青年骨干教师培养对象资助项目(湘教通(2011)388号); 湖南文理学院博士科研启动基金资助项目(107|13101022).

(责任编校:刘刚毅)