吴一全 ,纪守新 , 吴诗婳 ,张国华,于素芬
(1. 南京航空航天大学电子信息工程学院,南京 210016;2. 中航工业洛阳电光设备研究所光电控制技术重点实验室,洛阳 471009;3. 南京大学计算机软件新技术国家重点实验室,南京 210093)
阈值分割是许多图像分析与识别系统首要解决的问题,其目的是按照灰度级将图像空间划分成与实际景物相对应的一些有意义的区域[1-2].各个区域内部灰度级是均匀的,而相邻区域的灰度级不同.由此可大大简化其后的分析方法和处理步骤,且分割质量直接影响着后续处理的结果.阈值分割的关键是如何选取合适的阈值,人们对此进行了广泛的研究.在较早提出的典型阈值选取方法中,由 Kapur等[3]提出的一维最大 Shannon熵方法因对不同信噪比和不同大小的目标均能产生较好的分割效果且实现简单,而成为实际中常被选用的方法.后来 Abutaleb[4]、Brink[5]分别将最大 Shannon熵方法拓展到灰度级-邻域平均灰度级二维直方图,较好地反映出图像局部空间信息,且抗噪性增强,但计算复杂度增加.为此,Chen等[6]提出了量化直方图的算法,龚坚[7]、张毅军等[8]分别提出二维最大 Shannon熵法的 2种快速递推算法.另外杜峰等[9]提出了基于粒子群优化的二维最大Shannon熵阈值选取方法,也使运行时间大幅减少.然而,上述二维最大 Shannon熵方法及其快速算法都将二维直方图分成4个矩形区域(称之为直分),计算阈值时引入一定的近似,得到的分割结果不够准确.于是吴一全等[10-11]通过 4条平行斜线将直方图分成内点区、边界点区和噪声点区(称之为斜分),提出二维斜分阈值选取方法,改善了分割效果,进一步缩短了运行时间.
但是上述最大 Shannon熵阈值选取方法中定义的 Shannon熵仅仅依赖于图像二维直方图中的概率信息,而没有直接考虑图像中目标和背景类内灰度的均匀性,因此分割效果不够理想;此外,上述阈值选取的优化方法中,基本粒子群优化算法易陷入局部极值,且存在进化后期的收敛速度慢和精度低等缺点.针对上述问题,本文定义了灰度熵.该灰度熵与现有的仅基于直方图分布的最大Shannon熵不同,反映了类内灰度级的差异,是同一类内像素共同作用的结果.灰度熵越大(小),类内的像素灰度级差异越小(大).另一方面,对于阈值选取的优化方法可考虑混沌粒子群优化算法,通过对停止进化的粒子产生混沌扰动,使其跳出局部极值区,与基本粒子群算法相比,可提高搜索最优阈值的速度和精确度.
基于以上分析,本文首先给出了灰度熵定义及其一维阈值选取方法,然后将其推广提出了二维直分和斜分的灰度熵阈值选取方法,导出了2种方法的快速递推算法,并利用混沌粒子群算法寻求二维直分灰度熵阈值选取方法的最佳阈值.最后在实验结果和分析中,给出了分割结果和运行时间,并与基于粒子群优化的二维直分及二维斜分的最大 Shannon熵阈值选取方法、二维斜分Otsu阈值选取方法进行了比较.
设尺寸为 M×N图像的灰度级 (,)f m n取0,1,,1L−…,对应的灰度级概率分布为现用阈值 t 按灰度级将像素点划分成目标类和背景类b{(,C m=.若令
则目标类的灰度熵定义为
同理,背景类灰度熵bH表示为
目标类和背景类的总灰度熵为
由于一维直方图仅反映图像中的像素灰度级分布,对噪声的影响十分敏感.下面将一维灰度熵阈值选取拓展到二维,既利用了像素点的灰度信息,又利用了像素点的邻域信息.
设像素点(m, n)的邻域平均灰度级为 g ( m, n),(灰度级f,邻域平均灰度级g)二元对出现的频数为h( i, j),即{h( i, j) } 为图像的二维直方图.假设阈值向量(s, t)将二维直方图分成 4个区域,由式(3)、式(4)分析可得二维直方图的目标类和背景类灰度熵Ho(s, t)及 Hb(s, t)分别为
与一维灰度熵阈值选取公式类似,可以定义二维直分阈值选取方法的准则表达式(,)s tΦ为
当准则函数(,)s tΦ达到最大时获得最佳阈值.(,)s tΦ的快速递推算法如下.
递推算法节省了存储空间,提高了运行速度.为了进一步降低寻找最佳阈值的时间,现引入混沌粒子群优化算法.
粒子群优化是一种通过粒子速度和位置的迭代更新来寻找最优解的算法,即
式中:Vl(m*)、Xl(m*)、Pl(m*)和G ( m*)分别为第 m*次迭代时刻,粒子l的速度、位置、最优解和全局最优解;Vl(m*+1)和Xl(m*+1)分别为第 m*+1次迭代时刻,粒子l的速度和位置;c1、c2为学习因子;r1、r2为均匀分布在(0,1)上的随机数;w*为惯性因子.迭代更新过程中,粒子速度和位置限制在允许范围内,最后输出的G为全局最优解.
但是,上述基本粒子群算法易陷入局部极值,难以保证收敛到全局最优解.为此本文将基于 Tent映射的混沌迭代变异[12-13]应用于基本粒子群算法,使得粒子跳出局部极值,加快收敛速度.
Tent映射方程为
当 Tent映射达到小周期点(0.2,0.4,0.6,0.8)或不动点(0,0.25,0.50,0.75)时,使用扰动方程
在迭代过程中,按下列方程对粒子种群的最优粒子G=[X1,X2,… ,Xj, … Xn]进行混沌迭代变异
式中mλ为收缩因子,
现将上述混沌粒子群优化算法应用于二维直分灰度熵阈值选取,具体步骤如下.
步骤 1 初始化混沌粒子群,设定 c1= c2= 2 ;其中为总迭代次数;分别为最大和最小惯性因子;粒子速度限制在[,]10 10−.
步骤 2 按式(8)计算每个粒子的适应度,更新个体最优位置和全局最优位置.
步骤 3 按式(13)对最优粒子的位置进行基于Tent映射的混沌迭代变异,重新计算其适应度,若大于原适应度,则更新当前最优粒子的位置.本文选取混沌迭代映射次数为10.
步骤4 按式(9)和式(10)更新粒子速度和位置.
步骤5 如果达到总的迭代次数 mm*ax,执行步骤6,否则返回执行步骤2.
步骤6 输出最佳阈值,并对图像进行阈值分割.
由于二维直分方法计算最佳阈值时采取了一定的近似,忽略了一部分阈值向量附近且像素灰度级与邻域平均灰度级相差不大的区域.为了更准确地分割图像,下面提出二维斜分的灰度熵阈值选取方法.
将二维直方图用斜线g fT=− + (T 为阈值)划分为2部分,斜线左下方为目标区域 Co,右上方则为背景区域 Cb[11].
(1)当0 < T ≤L −1时,斜线g=− f + T 左下三角部分对应目标,可从(0,0)点开始逐点累加,分别计算目标的 woi(T)、woj(T)、uoi(T)和uoj(T)为
(2)当 L − 1 < T ≤ 2 L −2时,斜线g=−f+T的右上三角部分对应背景,就从(L −1,L −1)点开始逐点累加,先求出背景的 wbi(T)、wbj(T)、ubi(T)和ubj(T).由于目标对应于斜线g =− f + T 的左下部分,可用 wi、wj、ui、uj分别减去 wbi(T)、wbj(T)、ubi(T)、ubj(T),便得到 woi(T)、woj(T)、uoi(T)和uoj(T ),即
与二维直分的灰度熵阈值选取方法类似,二维斜分灰度熵阈值选取准则函数()TΦ定义为
则当准则函数()TΦ达到最大时便获得最佳阈值.为了降低运算量,下面导出()TΦ的快速递推算法
图1 原始图像及其分割结果(从上到下依次为House图像、Peppers图像、Infrared图像、Wall图像)Fig.1 Original images and segmentation results(House,Peppers,Infrared and Wall image are set successively from top to bottom)
利用上述提出的基于混沌粒子群优化的二维直分灰度熵阈值选取方法、基于二维斜分的灰度熵阈值选取方法,对大量图像进行了阈值选取实验,并与文献[9]中基于粒子群优化的二维最大 Shannon熵阈值选取方法、文献[10]中二维斜分的最大 Shannon熵阈值选取方法、文献[11]中二维斜分Otsu阈值选取方法进行了比较,发现本文所提出的方法具有明显的优势.受篇幅限制,现以其中的 House图像(256 256×)、Peppers图像(512 512×)、Infrared图像(214 290×)、Wall图像(640 640×)4幅图像为例加以说明,如图1所示.
图1中,从左到右依次为上述图像的原始图像及基于粒子群优化的二维最大Shannon熵、基于混沌粒子群优化的二维直分灰度熵、二维斜分的最大Shannon熵、二维斜分 Otsu和二维斜分的灰度熵 5种阈值选取方法的分割图像,相应的最佳阈值列于表1.5种算法的运行环境为 Intel(R) Core(TM)2 Duo CPU 2.2G/1.99G 内存/Matlab7.0,相应的运行时间列于表 2.此外,基于混沌粒子群优化的二维直分灰度熵阈值选取方法及基于粒子群优化的二维最大Shannon熵阈值选取方法的粒子数均为12,最大迭代次数 mm*ax= 1 00.
表1 图像分割的阈值Tab.1 Threshold for image segmentation
表2 图像分割的运行时间Tab.2 Running time of image segmentation s
由于最大 Shannon熵阈值选取方法仅依赖于图像直方图的概率信息,没有直接考虑类内灰度级的均匀性,而灰度熵阈值选取方法不仅利用了直方图中的概率信息,也直接考虑了灰度信息,因此更能反映同一类灰度级的差异性.由图 1可以清楚地看到本文方法的分割图像(c)、图像(f)要明显优于基于粒子群优化的二维最大 Shannon熵阈值选取方法的分割图像(b)及二维斜分的最大Shannon熵阈值选取方法分割图像(d),能更好地反映图像的边缘、纹理及细节信息.由图1还可以看到,本文方法的分割图像与最大 Shannon熵阈值选取方法相比,House图像和Wall图像中砖块之间的层次更加分明,Peppers图像中辣椒的边缘更为准确,Infrared图像中行人目标更为完整清楚.本文方法分割效果整体上要优于最大Shannon熵阈值选取方法,但在个别区域二维斜分的最大 Shannon熵阈值选取方法也有可取之处,如House图像屋顶的纹理特征等.此外,二维灰度熵阈值选取方法对目标与背景比例悬殊的图像分割效果还有待于进一步提高.
由表 2可以看出,由于文献[9]中的方法没有采用递推,故与本文直分方法相比,运行时间明显要长.而本文斜分方法同时考虑了概率、灰度信息,与文献[10]中的斜分法相比,运行时间稍长,但分割效果明显改善.与 Otsu斜分法相比,本文斜分法在运行时间上也具有明显的优势.
本文提出的灰度熵阈值选取方法中的灰度熵与现有的仅基于直方图分布的最大Shannon熵不同,直接反映了类内灰度的均匀性;本文从一维灰度熵阈值选取拓展到二维,在此基础上提出的二维直分和二维斜分的灰度熵阈值选取方法合理;推导了直分和斜分2种情况下的快速递推算法,并进一步利用混沌粒子群优化算法寻求二维直分灰度熵阈值选取方法的最佳阈值,提高了运行速度.针对实际灰度图像进行的实验结果表明:本文提出的基于混沌粒子群的二维直分灰度熵阈值选取方法和基于二维斜分的灰度熵阈值选取方法行之有效,与基于粒子群优化的二维最大Shannon熵阈值选取方法、二维斜分的最大 Shannon熵阈值选取方法和二维斜分 Otsu阈值选取方法相比,分割性能更为优越.
[1] Wang S T,Chung F L,Xiong F S. A novel image thresholding method based on Parzen window estimate[J]. Pattern Recognition,2008,41(1):117-129.
[2] Bardera A,Boada I,Feixas M,et al. Image segmentation using excess entropy[J]. Journal of Signal Processing Systems,2009,54(1/2/3):205-214.
[3] Kapur J N,Sahoo P K,Wong A K C. A new method for grey-level picture thresholding using the entropy of the histogram[J]. Computer Vision,Graphics and Image Processing,1985,29(3):273-285.
[4] Abutaleb A S. Automatic thresholding of gray-level picture using two-dimensional entropies[J]. Pattern Recognition,1989,47(1):22-32.
[5] Brink A D. Thresholding of digital image using twodimensional entropies[J]. Pattern Recognition,1992,25(8):803-808.
[6] Chen W T,Wen C H,Yang C W. A fast two-dimensional entropic thresholding algorithm[J]. Pattern Recognition,1994,27(7):885-893.
[7] Gong J,Li L Y,Chen W N. A fast recursive algorithm for two-dimensional thresholding[J]. Pattern Recognition,1998,31(3):295-300.
[8] 张毅军,吴雪菁,夏良正. 二维熵图像分割的快速递推算法[J]. 模式识别与人工智能,1997,10(3):259-264.Zhang Yijun,Wu Xuejing,Xia Liangzheng. A fast recurring algorithm for two-dimensional entropic thresholding for image segmentation[J]. Pattern Recognition and Artificial Intelligence,1997,10(3):259-264(in Chinese).
[9] Du Feng,Shi Wenkang,Chen Liangzhou,et al. Infrared image segmentation with 2-D maximum entropy method based on particle swarm optimization(PSO)[J].Pattern Recognition Letters,2005,26(5):597-603.
[10] 吴一全,潘 喆,吴文怡. 二维直方图区域斜分的最大熵阈值选取算法[J]. 模式识别与人工智能,2009,22(1):162-168.Wu Yiquan,Pan Zhe,Wu Wenyi. Maximum entropy image thresholding based on two-dimensional histogram oblique segmentation[J]. Pattern Recognition and Artificial Intelligence,2009,22(1):162-168(in Chinese).
[11] 吴一全,潘 喆,吴文怡. 二维直方图区域斜分阈值分割及快速递推算法[J]. 通信学报,2008,29(4):77-83.Wu Yiquan,Pan Zhe,Wu Wenyi. Image thresholding based on two-dimensional histogram oblique segmentation and its fast recurring algorithm[J]. Journal on Communications,2008,29(4):77-83(in Chinese).
[12] 张 浩,张铁男,沈继红,等. Tent混沌粒子群算法及其在结构优化决策中的应用[J]. 控制与决策,2008,23(8):857-862.Zhang Hao,Zhang Tienan,Shen Jihong,et al. Research on decision-makings of structure optimization based on improved Tent PSO[J]. Control and Design,2008,23(8):857-862(in Chinese).
[13] 贾东立,张家树. 基于混沌变异的小生境粒子群优化算法[J]. 控制与决策,2007,22(1):117-120.Jia Dongli,Zhang Jiashu. Niche particle swarm optimization combined with chaotic mutation[J]. Control and Decision,2007,22(1):117-120(in Chinese).