基于熵的图像二值化算法设计-二维最大熵分割

二维最大熵二维最大熵是一种基于最大熵原理的图像分割方法，它利用了图像的灰度信息和邻域的空间相关信息，通过构造二维直方图来选择最佳的分割阈值。

二维最大熵不仅反映了灰度分布信息，还反映了邻域平均灰度信息，因此在图像信噪比较低时，二维最大熵法明显优于一维最大熵法。

最大熵原理最大熵原理是统计学习的一般原理，它指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。

换句话说，我们应该选择使得信息熵最大的概率分布作为最优的预测模型。

信息熵是一种衡量随机变量不确定性的度量，它定义为：H(X)=−∑xP(x)log P(x)其中X是一个离散随机变量，P(x)是X取值为x的概率。

信息熵越大，表示X的不确定性越大。

按照最大熵原理，我们应该选择使得H(X)最大的概率分布P(x)作为最优模型。

当然，在选择模型时，还要满足一些已知的约束条件，例如期望值、方差等。

这样，我们就可以将最大熵模型转化为一个约束优化问题，利用拉格朗日乘子法或者其他优化算法求解。

二维直方图二维直方图是一种描述图像中两个相关变量之间分布关系的直方图。

在二维最大熵方法中，我们通常使用点灰度和区域灰度均值作为两个相关变量。

点灰度指的是图像中每个像素的灰度值，区域灰度均值指的是每个像素邻域内（例如3×3或5×5）所有像素灰度值的平均值。

这样，每个像素都对应一个点灰度-区域灰度均值对(f(x,y),g(x,y))，其中f(x,y)是点灰度，g(x,y)是区域灰度均值。

如果图像有L个灰度级（例如L=256），那么这样的数据对有L×L种可能的取值。

设n ij为图像中点灰度为i及其区域灰度均值为j的像素点数，p ij为点灰度-区域灰度均值对(i,j)发生的概率，则p ij=n ij N×N其中N×N是图像的总像素数。

则{p ij,i,j=0,1,…,L−1}就是该图像关于点灰度-区域灰度均值的二维直方图。

二维最大熵阈值分割算法[引用]杜峰，施文康，邓勇等：《一种快速红外图像分割方法》1. 二维最大熵阈值分割熵是平均信息量的表征。

二维最大熵法是基于图像二维直方图。

图像二维直方图定义如下：NM n P j i j i ⨯=,,其中N M ⨯表示图像大小，j i n ,表示图像灰度值为i ，邻域灰度平均值为j 的像素个数。

通常二维直方图的平面示意图可以用下图1表示：其中区域1和2表示背景和目标像素，区域3和4通常表示边界和噪声信息。

阈值向量(t ,s )，t 表示灰度值，s 表示像素邻域均值（通常是8邻域）。

对于L 个灰度级的图像，设在阈值(t,s)定义区域1和2的概率P1，P2：∑∑-=-==101,1s i t j ji PP ，∑∑-=-==11,2L s i L tj j i P P定义二维离散熵H 的一般表示：∑∑-=ijji ji P PH ,,lg对各区域概率j i P ,进行归一化处理可得区域1的二维熵：11)1lg(1lg 1)1(101,,P H P P P P P H s i t j j i ji +=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-=∑∑-=-= 同理区域2的二维熵：22)2lg()2(P H P H +=其中，H 1，H 2为：∑∑-=-=-=101,,lg 1s i t j ji ji P PH ，∑∑-=-=-=11,,lg 2L s i L tj j i j i P P H那么整个图像中目标和背景熵之和的函数)2()1(),(H H t s +=φ根据最大熵原则，存在最佳的阈值向量满足条件：图1 二维直方图平面示意图灰阶)},(max{),(t s t s φφ=**图2显示了一幅图像的二维直方图说明了背景和目标的主要分布情况，其中图2(b)横坐标表示邻域的均值，纵坐标表示灰度值分布：2. 微粒群寻优算法（PSO ）PSO 最早由Kenredy 和Eberhart 于1995年提出。

基于QPSO的二维模糊最大熵图像阈值分割方法
田杰;曾建潮
【期刊名称】《计算机工程》
【年(卷),期】2009(35)3
【摘要】针对运用图像分割方法求取阈值时存在的计算复杂、时间长、实用性差等问题,提出一种新的二维最大熵图像分割方法,该方法利用基于量子行为的微粒群算法对图像的二维阈值空间进行全局搜索,并将搜索到的二维熵最大值所对应的点灰度-区域灰度均值作为阈值进行图像分割.实验结果表明,该方法具有一定优越性,在执行时间与收敛性方面均得到较理想的分割效果.
【总页数】3页(P230-232)
【作者】田杰;曾建潮
【作者单位】太原科技大学系统仿真与计算机应用研究所,太原,030024;太原科技大学系统仿真与计算机应用研究所,太原,030024
【正文语种】中文
【中图分类】TP391
【相关文献】
1.一种基于二维最大熵的SAR图像自适应阈值分割算法 [J], 张红蕾;宋建社;翟晓颖
2.基于Sobel算子的图像快速二维最大熵阈值分割算法 [J], 李锋;阚建霞
3.基于二维最大熵阈值分割的坑识别方法 [J], 郭烈;王荣本;金立生;余天洪;顾柏园
4.基于二维最大熵原理和改进遗传算法的图像阈值分割 [J], 李宏言;盛利元;陈良款;
李更强
5.一种结合小波变换与二维最大熵法的图像阈值分割方法 [J], 刘耀辉;鲍苏苏因版权原因，仅展示原文概要，查看原文内容请购买。

二维最大熵阈值分割
二维最大熵阈值分割算法
若一幅图像的灰度级数为L，总的象素点数为N（m×n），设f i，j 为图像中点灰度为i及其区域灰度均值为j的象素点数，p i，j为点灰度－区域灰度均值对（i，j）发生的概率，即：p i，j＝f i，j／N，其中N （m×n）为图像的总象素数，则｛p i，j，i，j＝1，2，…，L｝是该图像关于点灰度－区域灰度均值的二维直方图。

图1为二维直方图的xoy平面图。

沿对角线分布的A区和B区分别代表目标和背景，远离对角线的C区和D区代表边界和噪声，所以应该在A区和B区上利用点灰度－区域灰度均值二维最大熵法确定最佳阈值，可使真正代表目标和背景的信息量最大。

于是，定义离散二维熵为：
3 二维最大熵阈值分割递推算法
在上述二维阈值化方法中，对于每个（s，t）对，都要从头开始计算P A（s，t）和H A（s，t），运算过程是一个4重循环，计算复杂性为，计算比较耗时。

实际应用中，为了提高运算速度，减少重复计算，必须对二维最大熵进行进一步优化。

对于一个固定的s，当t取1-L时，计算Φ（s，t）已经不存在重复计算，但同样s也要从1取到L，这样
这样通过优化，该递推算法可将计算的复杂性减至O（L2），大大减少了计算的复杂性，提高了计算速度。

具体算法实现如下：（1）计算原始图像中各个象素点的灰度值以及各个象素点的4邻域平均灰度值，并计算统计灰度信息P［i］［j］；
（2）相关计算
（3）求出最佳阈值（s＊，t＊），分割图像。

%%%%%%%%%%%%%%%%%%% 二维最大熵阈值分割法%%%%%%%%%%%%%%%%%%[filename,pathname]=uigetfile;img=imread(strcat(pathname,filename));figure(1);subplot(221);imshow(img);subplot(222);imhist(img(:,1));subplot(223);imhist(img(:,2));subplot(224);imhist(img(:,3));%%%%%%%%%%%%% 这个地方出现了一个问题就是为什么MidValue=img(i,j-1,1)+img(i-1,j,1)+img(i%%%%%%%%%%%%% +1,j,1)+img(i,j+1,1)最大值为256,难道是默认的一个BYTE类型吗？？？p=zeros(256,256);[m,n,k]=size(img);for i=2:m-1for j=2:n-1MidValue=img(i,j-1,1)/4+img(i-1,j,1)/4+img(i+1,j,1)/4+img(i,j+1,1)/4;MidValue=round(MidValue);p(img(i,j,1)+1,MidValue+1)=p(img(i,j,1)+1,MidValue+1)+1;end;end;%图像的四个角，只有2领域的点儿p(img(1,1,1)+1,round((img(1,2,1)/2+img(2,1,1)/2))+1)=p(img(1,1,1)+1,round((img(1,2,1)/2+img( 2,1,1)/2))+1)+1;p(img(1,n,1)+1,round((img(1,n-1,1)/2+img(2,n,1)/2))+1)=p(img(1,n,1)+1,round((img(1,n-1,1)/2+i mg(2,n,1)/2))+1)+1;p(img(m,1,1)+1,round((img(m-1,1,1)/2+img(m,2,1)/2))+1)=p(img(m,1,1)+1,round((img(m-1,1,1)/ 2+img(m,2,1)/2))+1)+1;p(img(m,n,1)+1,round((img(m,n-1,1)/2+img(m-1,n,1)/2))+1)=p(img(m,n,1)+1,round((img(m,n-1, 1)/2+img(m-1,n,1)/2))+1)+1;%图像周围的一圈，只有3领域的点儿for j=2:n-1MidValue=img(1,j-1,1)/3+img(1,j+1,1)/3+img(2,j,1)/3;MidValue=round(MidV alue);p(img(1,j,1)+1,MidValue+1)= p(img(1,j,1)+1,MidV alue+1,1)+1;end;for j=2:n-1MidValue=img(m,j-1,1)/3+img(m,j+1,1)/3+img(m-1,j,1)/3;MidValue=round(MidV alue);p(img(m,j,1)+1,MidValue+1)= p(img(m,j,1)+1,MidValue+1)+1;end;for i=2:m-1MidValue=img(i-1,1,1)/3+img(i+1,1,1)/3+img(i,2,1)/3;MidValue=round(MidV alue);p(img(i,1,1)+1,MidValue+1)= p(img(i,1,1)+1,MidV alue+1)+1;end;for i=2:m-1MidValue=img(i-1,n,1)/3+img(i+1,n,1)/3+img(i,n-1,1)/3;MidValue=round(MidV alue);p(img(i,n,1)+1,MidValue+1)= p(img(i,n,1)+1,MidValue+1)+1;end;p=p/(m*n);%%%%%%%%%%%% 忽略噪音的影响%%%%%%%%%%%%%%%%%%%%%%%%%%%pa=0;ha=0;hn=0;s=10;t=10;Qst=0;temp_t=10;temp_s=10;for i=1:256for j=1:256if(p(i,j)>0)hn=hn+log2(p(i,j))*p(i,j)*(-1);end;end;end;for t=10:256for s=10:256ha=0;pa=0;for i=1:tfor j=1:spa=pa+p(i,j);end;end;for i=1:tfor j=1:sif(p(i,j)>0)ha=ha+log2(p(i,j))*p(i,j)*(-1);end;end;end;if(pa>0&&1-pa>0)if(log2(pa*(1-pa))+ha/pa+(hn-ha)/(1-pa)>Qst)Qst=log2(pa*(1-pa))+ha/pa+(hn-ha)/(1-pa);temp_t=t;temp_s=s;end;end;end;end;for i=1:mfor j=1:nif(img(i,j,1)>temp_s)img(i,j,1)=255;img(i,j,2)=255;img(i,j,3)=255;elseimg(i,j,1)=0;img(i,j,2)=0;img(i,j,3)=0;end;end;end;figure(2);imshow(img);。

基于信息熵的指纹图像二值化算法①张理想1,3詹小四2,3张修如1(1.中南大学信息科学与工程学院湖南长沙 410075; 2.山东大学计算机科学与技术学院山东济南 250100; 3.阜阳师范学院计算机与信息学院安徽阜阳 236032)摘要：指纹图像的二值化处理是指纹图像预处理中的关键步骤，直接影响到指纹图像细化的质量和细节特征提取的准确性。

在深入分析指纹图像信息熵的基础上，将信息熵引入到指纹图像二值化算法中，通过求取对应指纹图像区域的最大信息熵估计二值化阈值，并依据此阈值实现对指纹图像的二值化处理。

实验结果表明，文中算法对噪声具有鲁棒性，能够有效实现对指纹图像的二值化，提高了细节特征提取结果的准确率。

关键字：信息熵；阈值分割；二值化；指纹识别Fingerprint Image Binarization Algorithm Based on Information EntropyZHANG Li-Xiang1,3 , ZHAN Xiao-Si2,3, ZHANG Xiu-Ru1(1. School of Information Science & Technology, Central South University, Changsha 410075, China;2. School of Computer Science & Technology, Shandong University, Jinan 250100, China;3. School of ComputerScience & Information, Fuyang Normal College, Fuyang 236032, China)Abstract: In fingerprint image pre-processing，fingerprint image binarization processing is a key step in a direct impact on the quality of fingerprint image thinning and accuracy of the extraction of the minutiaes. After anin-depth analysis of information entropy of fingerprint images, information entropy is introduced to thefingerprint image binarization algorithm. Through calculating a maximum entropy of the corresponding theregion in fingerprint image, binarization threshold is estimated, and based on the achievement of thisthreshold fingerprint image binarization processing is done. The experimental results show that thealgorithm is robust to noise and able to effectively realize the fingerprint image binarization.Keywords: information entropy; threshold segmentation; binarization; fingerprint identification指纹作为人体的生理特征，具有唯一性、不变性和排列的规律性等特点，从古至今一直作为身份认证的一种常用手段。

=计算机技术与应用>基于遗传算法的二维最大熵图像分割算法¹吴 薇 赵 旭 邓秋霞(武警工程学院通信工程系,陕西西安710086) =摘 要> 二维最大熵图像分割算法充分利用了图像象素的灰度分布信息和各象素间的空间相关信息,因此具有很好的分割效果。

但该算法的计算复杂度高、计算时间长。

为解决这一问题,本文提出了一种基于遗传算法的二维最大熵法。

该算法充分利用遗传算法的特点,极大地减少了计算量和存储空间。

实验结果证明了该算法的快速性、有效性和稳定性。

=关键词> 图像分割;遗传算法;二维最大熵图像分割是一种基本的计算机视觉技术,也是由图像处理进入到图像分析的关键步骤,一直是数字图像处理领域的一项重要研究内容。

在众多的分割方法中,阈值法是最为常用的一种方法。

现有的各种阈值法虽然是从不同的准则出发选取最佳阈值,但大多需要在全灰度范围内进行搜索,存在着搜索空间大、耗时多的缺陷。

寻找计算简单、自适应能力强的图像阈值,自动选取方法一直是阈值法研究的一个重要课题。

遗传算法是一种通过模拟自然进化过程搜索最优解的方法,其隐含的并行性和对全局信息的有效利用能力,使该方法只需检测少量结构就能反映搜索空间较大的区域,并获得稳定的最优解。

因此,遗传算法是21世纪关键智能计算技术之一。

本文将遗传算法和二维最大熵阈值法有机地结合起来,提出了一种基于遗传算法的图像分割算法。

该算法有效提高了算法的速度,增强了算法的实时处理能力。

1 遗传算法的基本原理遗传算法是基于自然选择和基因遗传学原理的搜索算法[1]。

在遗传算法中,通常将优化问题的解进行编码,以形成染色体(或称为个体),并随机产生一定数目的初始染色体。

随着算法的运行,优良的染色体被逐渐保留并加以组合,从而产生出更佳的染色体。

新一代染色体中既包含上一代的大量信息,又在总体特征上优于上一代,从而使整个群体向前进化发展,直至接近最优解。

一个基本的遗传算法由选择、交叉和变异等遗传算子组成,一般有如下几个步骤:(1)问题的表示,即对所求问题编码,并定义目标函数(适应值函数)。

基于遗传算法的二维Arimoto熵图像分割算法胡鹏博【摘要】为提高图像分割速度和抵抗噪声的能力,提出了一种基于二维Arimoto熵的阈值分割算法.该方法首先对图像进行小波变换,提取出描述图像整体信息的低频分量图像和描述图像局部细节信息的高频分量图像,然后计算二维Arimoto熵,根据最大熵原理将二维Arimoto熵作为遗传算法的适应度函数.最后对遗传算法进行了改进,通过选择、交叉和变异等遗传操作确定最佳分割阈值,实现图像分割.实验结果表明,该方法表现稳定,能够滤除图像噪声,而且分割速度快.【期刊名称】《电子世界》【年(卷),期】2016(000)019【总页数】2页(P118-119)【关键词】图像分割;Arimoto熵;小波变换;遗传算法【作者】胡鹏博【作者单位】华中光电技术研究所—武汉光电国家实验室【正文语种】中文图像分割是图像处理的一个重要领域，被广泛应用于计算机视觉领域。

在众多图像分割算法［1］中，阈值法因其简单、计算量少、性能稳定而成为图像分割中最基本的分割技术。

传统的阈值方法对噪声敏感程度不高，不具有抗噪能力。

为此，本文引用小波变换，其低频信息表征了图像的整体灰度信息，高频信息表征了图像的梯度信息，利用上述小波分量建立二维共生矩阵。

针对上述二维共生矩阵，构造Arimoto熵模型，利用遗传算法快速确定最佳分割阈值。

2.1 二维共生矩阵建立当图像含有大量噪声时，必然导致同质区域减少而梯度信息增加，因此传统二维熵模型不具有抗噪能力。

本文利用小波变换构建基于概貌-梯度共生矩阵［3］，其原因在于小波域中的低频信息中包含图像灰度特征的主要信息，对噪声不敏感；而高频信息中则含有图像的细节和边缘信息，弥补了低频子图的缺陷。

二维概貌-梯数共生矩阵建立步骤如下：1）对待分割图像进行三级小波分解，将反映图像灰度信息的低频系数重构为概貌图像，将最高级的反映图像边缘和细节信息的三级高频部分重构为梯度图像。

2）将概貌图像和梯度图像进行归一化处理，使其像素取值范围重新调整到［0，255］，然后构造传统概貌-梯度共生矩阵。

第14卷第6期2002年6月计算机辅助设计与图形学学报JOU RNAL O F COM PU T ER 2A I D ED D ES IGN &COM PU T ER GRA PH I CSV o l .14,N o.6June,2002图像分割的二维最大熵遗传算法陈　果 左洪福(南京航空航天大学民航学院　南京　210016)摘要　将遗传算法运用于二维最大熵图像阈值分割法.首先对二维阈值坐标进行编码,然后依据二维最大熵准则建立适应度函数,在适当的交叉率和变异率下,最终实现强噪声干扰下图像的有效分割.分割实验表明,文中方法较一维最大熵法具有更强的抗噪声能力,较普通二维最大熵法运算速度更快.关键词　图像分割,遗传算法,熵,二维直方图中图法分类号　T P 391.4;V 233.4;V 263.62-D M ax i m u m En tropy M ethod of I mage Segm en ta tionBa sed on Genetic A lgor ithmChen Guo Zuo Hongfu(C iv il A v ia tion Colleg e ,N anj ing U n iversity of A eronau tics and A stronau tics ,N anj ing 210016)Abstract 22D th resho lds are coded ,then the fitness functi on is established acco rding to the criteri on functi on of 22D m axi m um entropy .F inally the i m age w h ich is disturbed by seri ous no ise is segm ented effectively under the p roper cro ssover rate and m utati on rate .Segm entati on examp les show that the m ethod p ropo sed has greater resis 2tance capability to no ise than 12D m axi m um entropy app roach ,and is faster than the common 22D m axi m um entropy app roach .Key words i m age segm entati on ,genetic algo rithm ,entropy ,22D h istogram 原稿收到日期:2001204220;修改稿收到日期:2001211228.陈　果,男,1972年生,博士后研究人员,主要研究方向为图像处理与模式识别、信号分析与处理、机械振动以及故障诊断等.左洪福,男,1959年生,教授,博士生导师,主要研究方向为摩擦学、铁谱分析、机械设备故障诊断和磨损检测等.1　引 言图像分割是大多数图像分析及视觉系统的重要组成部分,也是图像处理和前期视觉中的基本技术.图像分割的目的就是把图像中的物体与背景分开,将人们感兴趣的目标从图像背景中提取出来,为后续处理提供基础.阈值分割法因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术.熵是平均信息量的表征,20世纪80年代初人们开始考虑用信息论中熵的概念进行阈值选取.1980年Pun [1]首先提出最大后验熵上限法;Johannsen 和B ile [2]1982年提出的最小信息互相关法也采用了图像灰度级的熵,该方法将灰度级范围划分为两部分,并使其在互相关(在信息论意义上)最小处选取阈值;1985年Kapur 等[3]提出最大熵阈值选取法;1989年A butaleb [4]将Kapur 等提出的一维最大熵法推广至二维,即考虑象素的灰度级及其邻域平均灰度级构成的二维直方图;1989年Pal 等[5]引入图像的q 阶局部熵与条件熵的概念,提出选取阈值的最大二阶局部熵法与最大条件熵法;1989年W ong 等[6]介绍了一种考虑均匀性与形状的最大熵阈值选取方法.在这些最大熵法中,Kapur 提出的一维最大熵法和被A butaleb 推广的二维最大熵法最为简洁有效,因此应用最广.当图像的信噪比降低时,应用一维最大熵法将产生很多分割错误.二维最大熵法应用二维直方图,不仅反映了灰度分布信息,还反映了邻域空间相关信息,因此在图像信噪比较小时,二维最大熵法明显优于一维最大熵法.但是,被推广的二维最大熵法只是简单地将一维寻优推广为二维寻优,因此导致运算量按指数增长,耗时太长,难以实用.为此,文献[7]提出了二维最大熵法的递推算法,并以加大存储容量为代价将速度提高了近两个数量级;文献[829]提出了二维直方图的最佳一维投影分割法和F isher 准则下的一维投影分割法,并将其运用于二维最大熵法,计算量基本上与一维最大熵法相当.遗传算法是一种通过模拟自然进化过程搜索最优解的方法[10].隐含并行性和对全局信息的有效利用能力是遗传算法的两大显著特点,前者使遗传算法只需检测少量结构就能反映搜索空间较大的区域,便于实时处理;后者使遗传算法具有较强的鲁棒性,可避免陷入局部最优.近年来,遗传算法已被成功地应用于各种优化问题,遗传算法仿效遗传学中生物从低级到高级的进化过程,将进行的操作应用于一群对搜索空间(或称参数空间)编码的基因串(或称染色体)中,在每一代,遗传算法同时搜索参数空间的不同区域,然后把注意力集中到解空间中期望值最高的部分.通过一群基因串一代又一代地繁殖和交换,遗传算法能搜索到多个局部极值,从而增加了找到全局最优解的可能性.本文在普通二维最大熵法[4,11]基础上,提出一种基于遗传算法的二维最大熵法,运用遗传算法的两大显著特点实现二维最大熵法的快速计算.2　二维最大熵阈值分割综合运用点灰度和区域灰度特征可以较好地表征图像的信息,二维最大熵阈值分割法正立足于此,其具体计算方法如下:以原始灰度图像(L个灰度级)中各象素及其8邻域的8个象素为一个区域,计算出区域灰度均值图像(L个灰度级),这样,原始图像中每一个象素都对应于一个点灰度2区域灰度均值对,则此数据对存在L×L种可能的取值.设n ij 为图像中点灰度为i及其区域灰度均值为j的象素点数,p ij 为点灰度2区域灰度均值对(i,j)发生的概率p ij=n ijN×N(1)其中N×N为图像的大小,则{p ij,i,j=1～L}就是该图像关于点灰度2区域灰度均值的二维直方图.图1所示为图像二维直方图(用灰度表示),从图中可以看出,点灰度2区域灰度均值对的概率高峰主要分布在平面的对角线附近,并且在总体上呈现出双峰状态.这是由于图像的所有象素中,目标点和背景点所占比例最大,而目标区域和背景区域内部的象素灰度级比较均匀,点灰度及其区域灰度均值相差不大,所以都集中在对角线附近,两个峰分别对应于目标和背景.远离平面对角线的坐标处,峰的高度急剧下降,这部分反映图像中的噪声点、边缘点和杂散点.图2为二维直方图的X O Y平面图,沿对角线分布的A区和B区分别代表目标和背景,远离对角线的C区和D区代表边界和噪声,所以应该在A区和B区中用点灰度2区域灰度均值,通过二维最大熵法确定最佳阈值,使真正代表目标和背景的信息量最大.设A区和B区具有不同的概率分布,用A区和B区的后验概率对各区域的概率p ij进行归一化处理,使分区熵之间具有可加性.如果阈值设在(s,t),则P A=∑s-1i=0∑t-1j=0p ij,　P B=∑L-1i=s∑L-1j=tp ij(2)定义离散二维熵为H=-∑i∑jp ij lg p ij(3)则A区和B区的二维熵分别为H(A)=-∑s-1i=0∑t-1j=0(p ij P A)lg(p ij P A)=-(1 P A)∑s-1i=0∑t-1j=0(p ij lg p ij-p ij lg P A)=(1 P A)lg P A∑s-1i=0∑t-1j=0p ij-(1 P A)∑s-1i=0∑t-1j=0p ij lg p ij =lg(P A)+H A P A(4)同理,H(B)=lg(P B)+H B P B(5)其中,H A=-∑s-1i=0∑t-1j=0p ij lg p ij,H B=-∑L-1i=s∑L-1j=tp ij lg p ij.由于C区和D区包含关于噪声和边缘的信息,概率较小,所以将其忽略不计,即假设C区和D区的p ij=0.可以得到P B=1-P A,H B=H L-H A.其中,H L=-∑L-1i=0∑L-1j=0p ij lg p ij,则H(B)=lg(1-P A)+(H L-H A) (1-P A).熵的判别函数定义为<(s,t)=H(A)+H(B)=H A P A+lg P A+(H L-H A) (1-P A)+lg(1-P A)=lg[P A(1-P A)]+H A P A+(H L-H A) (1-P A)(6)显然,如果不忽略对远离对角线的C区和D区的概率,则熵的判别函数为<(s,t)=H(A)+H(B)(7)其中,H(A)和H(B)的计算分别如式(4),(5).选取的最佳阈值向量满足<(s3,t3)=m ax{<(s,t)}(8)1356期陈　果等:图像分割的二维最大熵遗传算法3　二维最大熵图像分割的遗传算法将遗传算法同二维最大熵图像分割法联系起来首先要解决两个问题:一是如何将问题的解编码到基因中;二是如何构造适应度函数来度量每条基因串(染色体)对问题的适应程度.如果某条基因串的编码代表的阈值能使分割后的图像熵大,则其适应度就高;反之,其适应度就低.二维熵阈值分割法的目的就是要得到最佳分割阈值(s 3,t 3),使得图像的熵最大,可以直接对二维阈值矢量进行编码.由于在数字图像处理中,阈值的选取范围通常为0～255中的整数,因此采用8位二进制编码比较方便.本文根据二维阈值坐标值的取值范围,将其量化值(用二进制串表示)编码成基因串a ={Α0,…,Α7,Α8,…,Α15},其中,a 中的前8个量化值代表第一个阈值坐标,后8个量化值代表第二个阈值坐标.每个基因串由长度为16个比特位的串组成,此时的搜索空间有2562个点.适应度函数可直接选择二维熵的判别函数<(s ,t ),即f m =<(s ,t )(9)本文构造的基于遗传算法的二维最大熵图像分割法的计算流程如图3所示.其基本过程如下:Step 1.设定种群数目N ,对二维阈值进行二进制编码,并随机产生初始种群.注意,种群数目如果取得太小,遗传算法的性能将变得很差或根本找不出问题的解;如果取得太大,则会增加计算量,使收敛时间增长.种群数目一般取为30～50个.Step 2.对初始种群解码,并根据式(6),(7)和式(9)计算每条基因串的适应度.Step 3.将适应度最大的个体,即种群中最好的个体无条件地复制到下一代新种群中,然后对父代种群进行选择、交叉和变异等遗传算子运算,从而繁殖出下一代新种群的其它N 21个基因串.通常采用转轮法作为选取方法,适应度大的基因串选择的机会大,从而被遗传到下一代;相反,适应度小的基因串选择的机会小,将被淘汰.交叉和变异是产生新个体的遗传算子,若交叉率太大,将使高适应度的基因串结构很快被破坏掉,太小则使搜索停滞不前,一般取为0125～0175;若变异率太大,将使遗传算法变为随机搜索,太小则不会产生新个体,一般取为0101～012.Step 4.如果达到设定的繁衍代数,则返回最好的基因串,并将其作为二维分割阈值,算法结束;否则,回到Step 3继续下一代的繁衍.4　图像分割算例为了验证基于遗传算法的最大熵图像分割法的有效性,我们以一幅典型的真实磨粒图像为例进行分割实验.磨粒图像是通过在显微镜下对铁谱片进行观察,并由CCD 摄像头和图像采集卡所获取的数字图像.对磨粒图像的分割和磨粒目标的提取及识别是智能化铁谱诊断系统的关键技术.磨粒图像一般可以看成是由目标和背景两类象素构成的单阈值图像,图像中的目标即为金属磨粒(如铁、铜、铝及其合金等),对磨粒图像进行分割的目的就是要从图像中提取出我们所感兴趣的磨粒目标,从而为后续的磨粒识别提供基础.由此可见,磨粒图像的分割和目标提取对智能铁谱分析技术非常重要.图4a 为原始磨粒图像,图4b 为原始磨粒图像的一维直方图,图4c 为原始磨粒图像的二维直方图(用灰度表示);图5a 为在原始磨粒图像上叠加服从正态分布N (0,400)的随机噪声后形成的噪声图像,图5b 为噪声图像的一维直方图,图5c 为噪声图像的二维直方图;图6a 为噪声磨粒图像用一维最大熵法的分割结果,图6b 为噪声磨粒图像用本文基于遗传算法的二维最大熵法的分割结果,在本文遗传二维最大熵法中,种群数目N 取为30,基因串(染色体)二进制编码长度为16bits ,交叉率和变异率分别取为0150和011,经过10代遗传后即收敛到最佳阈值.从直方图上看,原始磨粒图像的一维直方图表现出了明显的双峰特性,如图4b 所示.二维直方图沿对角线分布且分布区域很窄,如图4c 所示;但是在噪声污染后,图像的一维直方图的双峰几乎完全被噪声掩盖,如图5b 所示,此时已很难分清直方图上的峰和谷.噪声图像的二维直方图同样沿对角线分布,但其分布区域变得很宽,如图5c 所示,致使目标和背景区域在点灰度轴上的投影产生了很多重叠,使一维直方图上的峰和谷很难辨别.从分割精度上看,对于受噪声影响后的噪声磨粒图像,一维最大熵法的分割结果显然很差,如图6a 所示.由于噪声的影响,使分割后的磨粒目标内部出现许多小洞,而且磨粒边界出现了大量的不连续,同时也导致了许多目标的失落.从图6b 和图6c 不难看出,本文提出的遗传二维最大熵法对噪声磨粒图像实现了最佳的分割.从分割结果可以看出,磨粒目标的内部区域完整,不存在受噪声污染的小洞,磨粒边界完全封闭,几乎没有局部断开的现象;与一维最大熵法相比,磨粒目标失落现象明显减少.由此可见,对于噪声污染下的图像,本文提出的遗传二维最大熵法的分割性能明显优于一维最大熵法;同时,对比图6b ,6c 不难看出,二者的分割结果几乎相同,是否考虑二维直方图上远离对角线的C 区和D 区的概率对分割结果影响很小.235计算机辅助设计与图形学学报2002年从计算速度上看,在种群数为30时,本文的遗传二维最大熵法通过10代遗传后,收敛到最佳阈值,共计算了n1=30×10=300次熵判别函数;但是如果采用简单推广的二维最大熵分割法[4],运用穷举搜索法求取最佳分割阈值,则需计算n2=256×256=65536次熵判别函数.相比之下,本文方法的速度提高S=n2 n1=65536 300≈218(倍).一维最大熵法由于仅考虑一维直方图,所以只需计算256次熵判别函数.显然,本文方法与一维最大熵法相比,计算速度基本相同.文献[8]提出的二维最大熵递推算法尽管速度也很快,但需要的存储空间要大得多,且方法的复杂性也大为增加.文献[4]中A butaleb曾认为穷举搜索法是二维最大熵法求取二维阈值矢量的唯一方法,二维最大熵法以计算时间为代价获取了比一维熵法更佳的分割精度.显然,本文提出的遗传二维最大熵法从根本上否定了A butaleb的观点,本文方法不仅在图像分割精度上达到了最佳,且计算速度也基本与一维最大熵法相同.由此可见,与其它方法相比,权衡其分割精度和计算速度,本文提出的遗传二维最大熵法不失为一种非常实用有效的图像阈值分割方法.5　结 论本文将遗传算法运用于二维最大熵图像阈值分割法,构造出了图像分割的遗传二维最大熵法.并以真实磨粒图像为例,同时叠加服从正态分布N(0,400)的随机噪声,对噪声磨粒图像进行了分割实验.对本文的基于遗传算法的二维最大熵法与一维最大熵法进行比较,结果表明本文方法对噪声图像的分割效果很好,其分割精度明显优于一维最大熵法,而计算速度基本与一维最大熵法相同.所以本文提出的遗传二维最大熵法是一种实用有效的图像阈值分割法.参考文献[1]Pun T.A new m ethod fo r gray2level p icture th resho lding us2ing the entropy of h istogram[J].Signal P rocessing,1980(2):223～237[2]Johannsen G,B ile J.A th resho ld selecti on m ethod using in2fo r m ati on m easures[A].In:P roceedings of the6th I CPR,1982.140～143[3]Kapur J N,Sahoo P K,W ong A K C.A new m ethod fo rgray2level p icture th resho lding using the entropy of the h is2togram[J].Computer V isi on,Graph ics and I m age P rocess2ing,1985(29):273～2853356期陈　果等:图像分割的二维最大熵遗传算法[4]A butaleb A S.A utom atic th resho lding of gray2level p icturesusing two2di m ensi on entropy[J].Computer V isi on,Graph2 ics and I m age P rocessing,1989(47):22～32[5]Pal N R,Pal S K.Entrop ic th resho lding[J].Signal P rocess2ing,1989(16):97～108[6]W ong A K C,Sahoo P K.A gray2level th resho ld selecti onm ethod based on m axi m um entropy p rinci p le[J].T he Insti2 tute of E lectrical and E lectronics Engineers T ransacti ons, 1989,S M C219(4):866～871[7]Zhang Yijun,W u Xueqing,X ia L iangzheng.Fast recurrencealgo rithm of i m age th resho lding using2D entropy[J].Pat2 tern R ecogniti on and A rtificial Intelligence,1997,10(3):259～264(in Ch inese)(张毅军,吴雪青,夏良正.二维熵图像阈值分割的快速递推算法[J].模式识别与人工智能,1997,10(3):259～264) [8]L iL iyuan,Gong J ian,Chen W einan.I m age segm entati onm ethod based on op ti m um1D p ro jecti on of2D gray h is2 togram[J].A cta A utom atica Sinica,1996,22(3):315～322 (in Ch inese)(李立源,龚　坚,陈维南.基于二维灰度直方图最佳一维投影的图像分割方法[J].自动化学报,1996,22(3):315～322)[9]Gong J ian,L i L iyuan,Chen W einan.I m age segm entati onm ethod based on F isher linear segm entati on of2D gray h is2togram[J].Pattern R ecogniti on and A rtificial Intelligence,1997,10(1):1～7(in Ch inese)(龚　坚,李立源,陈维南.基于二维灰度直方图F isher线性分割的图像分割方法[J].模式识别与人工智能,1997,10(1):1～7)[10]D avis L.H andbook of Genetic A lgo rithm[M].N ew Yo rk:van N o strand,1991[11]X ia L iangzheng.D igital I m age P rocessing[M].N anjing:Southeast U niversity Publish ing House,1999.223～228(inCh inese)(夏良正.数字图像处理[M].南京:东南大学出版社,1999.223～228)中国计算机学会全国第四次程序设计语言发展与教学学术会议征文通知全国第四次程序设计语言发展与教学学术会议定于2003年春季在江苏扬州召开.本次会议由东南大学承办,扬州大学、南京大学、武汉大学等院校协办,现将有关事项通知如下:一、征文范围A.程序设计语言历史、现状与发展B.面向对象语言及相关技术C.各类建模语言及其设计、实现与应用D.面向网络应用的程序设计语言(X M L,H TM L,PERL等)E.其它各种新型程序设计语言(包括逻辑型语言、函数型语言等)F.程序设计语言分析、评价与比较G.程序设计语言语法、语义与语用以及形式化描述技术与方法H.并发、并行与实时程序设计语言I.软件开发过程中各类描述语言(包括软件体系结构描述语言等)J.第四代语言与数据库语言K.程序设计语言教学、教材与课件L.各类写作语言与工具M.其它二、征文要求来稿一般不得超过6000字,并且未被其它会议、期刊录用或发表.为了便于正式出版论文集,来稿必须附中英文摘要、关键词与主要参考文献,注明作者姓名、工作单位、详细通讯地址(包括电子邮件地址与电话)与作者简介.欢迎电子投稿,来稿不退,请自留底稿.三、来稿地址南京东南大学计算机科学与工程系　徐宝文 邮编:210096电话:(025)3793977;E2m ail:bw xu@四、重要日期征文截止日期:2002年10月15日录用通知发出日期:2002年11月15日修改稿截止日期:2002年12月15日435计算机辅助设计与图形学学报2002年。

基于最大熵的阈值选取及图像分割在讲基于最大熵的阈值选取的具体算法之前先来简要介绍下相关原理。

熵：用来描述体系混乱度的物理量。

最大熵原理①：最大熵原理是在1957 年由E.T.Jaynes提出的，其主要思想是，在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。

因为在这种情况下，符合已知知识的概率分布可能不止一个。

我们知道，熵定义的实际上是一个随机变量的不确定性，熵最大的时候，说明随机变量最不确定，换句话说，也就是随机变量最随机，对其行为做准确预测最困难。

下面简单解释下最大熵原理：例：一个盒子中有三种小球，白球重量10g/个，红球重量20g/个，黑球30g/个，且三种球的重量占总重的比例分别为p1，p2，p3，盒子中球的平均重量为15g/个。

此时有约束条件为显而易见的是：在上述问题中有三个变量却只有两个约束条件。

此时必有无穷多组解满足已知约束，这些解就构成了一个随机变量的集合，而这个随机变量往往可以用一个概率密度分布函数来表示（显然这样的概率密度分布函数也有多个）。

而我们应该怎么选取呢？若假设满足已知约束条件的集合为A，在已知约束上再增加一个约束后，满足增加后的约束的集合为B，则必有B⊆A，即A出现的概率必然大于B。

这表明熵越大的决策在已知约束条件下出现的概率越大受到的其他位置约束条件越少。

这就是最大熵理论：熵值最大的理论即为最合理决策。

图像分割中最大熵的引入②：在图像分割中若假定以灰度级T分割图像，则图像中低于灰度级T的像素点构成目标物体（o）,高于灰度级T的像素点构成背景（B）那么各个灰度级在图像分割后的两区域中的概率如下：O： (0<=i<=t) B：(t+1<=i<=255) 其中ni为图像中灰度级为i的像素点个数，nt为灰度级从0~t的像素点总和，N为图像总像素点，t为假定灰度阈值T。

此时O区熵： (0<=i<=t)B区熵： (t+1<=i<=255)令H=HB+Ho则根据最大信息熵理论在已知条件下要对图像做出分割的最佳决策即为最接近实际图像分割的理想决策。