二维最大熵阈值分割法

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

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

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

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

信息熵是一种衡量随机变量不确定性的度量，它定义为：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年提出。

1设计目的与要求1.1 设计目的(1)熟悉和掌握MATLAB程序设计方法。

(2)学习和掌握MATLAB图像处理工具箱。

(2)了解图像分割和图像二值化的原理。

(3)掌握图像二值化技术阈值的选取。

(4)将原彩色图像变为二值化后的图像，通过二维最大熵图像分割法对图像进行分割达到预期目的。

1.2 设计要求(1)了解图像变换的意义和手段。

(2)熟悉最大熵和二值化的基本性质。

(3)通过本实验掌握利用MATLAB编程实现数字图像处理。

(4)理解图像分割的原理，了解其应用，掌握最大熵和二值化分割的方法。

2 设计方案2.1 图像二值化图像二值化是数字图像处理技术中的一项基本技术，二值化图像的显示与打印十分方便，存储与传输也非常容易，在目标识别、图像分析、文本增强、字符识别等领域得到广泛应用。

图像二值化是将灰度图像转化为只有黑白两类像素的图像，大多采用阈值化算法处理。

在不同的应用中，阈值的选取决定着图像特。

征信息的保留。

因此，图像二值化技术的关键在于如何选取阈值。

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

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

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

图像分割中最大熵的引入：在图像分割中若假定以灰度级T 分割图像，则图像中低于灰度级T 的像素点构成目标物体,高于灰度级T 的像素点构成背景那么各个灰度级在图像分割后的两区域中的概率如下：O ：ti N N (0<=i<=t) （3.2.1）B ：ti N N N - (t+1<=i<=255) （3.2.2）其中Ni 为图像中灰度级为i 的像素点个数，Nt 为灰度级从0～t 的像素点总和，N 为图像总像素点，t 为假定灰度阈值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);。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二维最大熵阈值分割
二维最大熵阈值分割算法
若一幅图像的灰度级数为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＊），分割图像。

第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年。

第27卷第3期 哈　尔　滨　工　程　大　学　学　报 Vol.27№.32006年6月 Journal of Harbin Engineering University J un.2006利用二维熵自动确定图像分割的阈值张云飞1,2,张　晔2(1.哈尔滨工业大学理学院,黑龙江哈尔滨150001; 2.哈尔滨工业大学电子与信息研究院,黑龙江哈尔滨150001)摘　要:阈值法是图像分割的一种重要方法,在图像处理与目标识别中广为应用.因此,如何确定阈值是图像分割的关键.建立二维直方图并借助二维熵可以自动确定图像分割的阈值.传统方法产生二维直方图时,选择4邻域中心灰度值和邻域像素的灰度均值.事实上,水平或垂直方向上的灰度变化不能完全地反映邻域像素的整体特性.提出构造二维直方图的新方法,新方法选择3×3邻域中心灰度值和4邻域以外的4个像素的灰度均值.应用新方法和传统方法进行对比实验,分割结果可以看出新方法的有效性.关键词:阈值;二维熵;二维直方图;条件熵;图像自动分割中图分类号:TP391　文献标识码:A 文章编号:100627043(2006)0320353204Autom atic threshold of im age segmentation using 22D entropyZHAN G Yun 2fei 1,2,ZHAN G Ye 2(1.College of Science ,Harbin Institute of Technology ,Harbin 150001,China ;2.College of Information Engineering ,Har 2bin Institute of Technology ,Harbin 150001,China )Abstract :Thresholding is an important form of image segmentation and is used in many applications t hat involve image p rocessing and object recognition.Thus ,how to acquire a t hreshold of image segmentation is key.To realize automatic segmentation and build a 22D histogram using 22D ent ropy ,t raditional met h 2ods research t he cent ral gray value and mean value of pixels in t he same neighbor.However ,t he horizontal or vertical change of t he grayscale value cannot rep resent t he total characteristics among neighbor pixels very well.A new met hod is proposed to build a 22D histogram by utilizing t he center gray value and mean value of four ot her pixel gray values except four -neighbor pixels in t he same 3×3neighborhood.Experi 2mental result s o n a classical image show t he effectiveness of t he new met hod.K eyw ords :t hreshold ;22D entropy ;22D histogram ;conditional ent ropy ;automatic segmentation收稿日期:2005211225.基金项目:国家自然科学基金资助项目(60272073).作者简介:张云飞(1963-),男,讲师,博士研究生,E 2mail :zhangyun 2fei @ ;张　晔(1960-),男,教授,博士生导师. 图像分割是把图像分成互不重叠的不同区域的过程,同一区域内具有特性相似性,不同区域间具有特性相异性.图像分割是图像分析和理解的基础.图像分割的方法中阈值法为常用方法,同时阈值法也是其他许多分割方法的基础[1-2].近年来基于熵的方法,特别是基于二维熵的方法受到研究者的重视.因为二维熵相对于一维熵除了可以提供图像的灰度信息外,还能够提供图像中位置关系确定的像素间的统计规律.建立二维熵的方法可以从建立图象二维直方图入手,然后对此直方图用矩阵表示,对矩阵按阈值分割后选择包含边缘的象限定义二维熵,当二维熵达到极大值时就可以实现图像的自动分割.建立二维直方图的方法除了利用图像的灰度-梯度共生矩阵的方法外[3-4],另一类受关注的方法是Abutaleb 提出的使用4邻域中心的灰度值与其余像素的灰度均值构成二维直方图的方法,这种方法把二维直方图的矩阵用阈值分成4个象限,但在计算中只考虑目标的边缘和背景的边缘所在的两个象限,而忽略另外两个象限,当二维熵达到极大值时即获得图像的自动分割[5].这种对二维直方图矩阵的处理方法被许多研究者采用,如Sahoo 等选择邻域中心的灰度值和邻域中全部像素灰度均值得到二维直方图,并运用二维Renyi 熵达到极大值时实现图像的自动分割[6].刘正光等对图像灰度值引入模糊函数,用模糊函数来刻画某些灰度是属于目标还是属于背景,在二维直方图中引入模糊熵后,仿照Abutaleb 处理图像分割的后续方法得到效果理想的分割结果[7].Abutaleb 方法在建造二维直方图时,只关心邻域中心像素和邻域中直接与其水平或垂直方向相邻的像素,并不关心邻域中的其它像素;Sahoo 等的方法把邻域中的像素平等对待.事实上,通常情况下,水平或垂直方向的灰度变化相对于对角方向的灰度变化较“缓慢”或连续性“较强”.为克服这一不足,文中提出新方法创建二维直方图,新方法在3×3邻域中利用邻域中心的灰度值和4邻域以外的4个像素的灰度平均值,这样既可以避免定义二维熵时所关心的对象位置过于“密切”,又可以提高邻域中心像素的灰度值与所参考象素灰度值的差异.1　二维直方图建立的新方法及性质111　一维Shanno n 熵及性质设离散型随机变量X 的概率分布为p i =P r{X =x i },i =1,2,…,n ,则X 的Shannon 熵H (X )定义为H (X )=-∑ni =1p i log c p i (1)式中:{x 1,x 2,…,x n }是随机变量X 的取值空间,c 常取2、e 、3、10.式(1)满足:0≤H (X )≤log c n ,当且仅当p i =1/n ,i =1,2,…,n 时,H (X )=log c n 成立.112　二维直方图建立的新方法设f (x ,y )表示灰度级是256的图像,g (x ,y )表示当前像素(x ,y )的3×3邻域内4邻域以外的4个像素的灰度平均值,即g (x ,y )=(14[f (x -1,y -1)+f (x -1,y +1)+f (x +1,y -1)+f (x +1,y +1)].(2)式中:(r )表示r 的整数部分.f (x ,y )和g (x ,y )可以构成二维直方图.即h (k ,m )=p{{(f (x ,y )=k}∩{g (x ,y )m}}.(3)式中:P{A}表示事件A 发生的次数,h (k ,m )表示f (x ,y )=k 并且g (x ,y )=m 发生的次数.式(3)反应的关系可以表示成如图1的矩阵形式.对于这个矩阵,如果向量(s ,t )是阈值向量,那么(s ,t )把这个矩阵分割成4个象限,分别设为A ,B ,C和D.h (k ,m )可用下式归一化:^h (k ,m )=h (k ,m )/∑255i =0∑255j =0h (i ,j ).图1　二维直方图矩阵的象限Fig.1　Quadrants in the 22D histogram matrix定义联合概率p ij 为二维直方图矩阵中(i ,j )元素h (i ,j )与∑255k =0∑255m =0h (k ,m )的商,即p ij =h (i ,j )/∑255k =0∑255m =0h (k ,m )　i ,j=0,1, (255)式中:p ij 满足概率分布的完备性准则,即:0≤p ij ≤1,并且∑255i =0∑255j =0p ij =1.由此定义:P B =∑si =0∑255j =t+1pij,P D =∑255i =s+1∑tj =0pij.(4) 对不同的象限得到下面的概率:PBij=p ij P B =h (i ,j )/∑s k =0∑255l =t+1h (k ,l ).(5)式中:0≤i ≤s ,t +1≤j ≤255;pDij=p ij P D=h (i ,j )/∑255k =s+1∑tl =0h (k ,l ).(6)式中:s +1≤i ≤255,0≤j ≤t.113　二维S hannon 熵及自动阈值的确定从二维直方图矩阵的构成上,象限A 和象限C 中的元素的特性为:图像3×3邻域中心灰度值和4邻域以外的4个像素平均灰度值的差别“不明显”(相对于象限B 和象限D 中的元素),这种特性与目标或背景的内部元素特性接近,那么不妨假设象限A 和象限C 分别对应于背景的内部和目标的内部;象限B 和象限D 中的元素的性质为:图像中3×3邻域中心灰度值和4邻域以外的4个像素平均灰度值的差别“明显”(相对于象限A 和象限C 中的元素),这种性质与目标的边缘和噪声的性质接近,由对象限A 和象限C 的假设,可以认为象限B 和象限・453・哈　尔　滨　工　程　大　学　学　报 第27卷D 分别对应于背景和目标的边缘或噪声.利用式(1)～(6),Shannon 条件熵可写作:H (E |B )=-∑si =0∑255j =t+1p B ij log 2p Bij ,H (E |O )=-∑255i =s+1∑tj =0pDijlog 2p Dij . 综合考虑以上二式,图像的二维Shannon 熵H T(c )(s ,t )可写为H T(c )(s ,t )=(H (E |O )+H (E |B ))/2.(7)H T(c )(s ,t )的最大值为目标背景分类给出的优化阈值向量(s 3,t 3):(s 3,t 3)=arg {max0≤S 255,0≤t 255H T c(s ,t )}.(8)使H T (c )(s ,t )最大时的向量(s 3,t 3)即实现图像的自动分割.2　实验结果为说明新方法的有效性,选择pearlite.tif 作为原始图像,见图2(a );图2(b )是Abutaleb 方法的分割结果,图2(c )是新方法的分割结果.从实验结果可以看到:新方法比Abutaleb 方法明显清晰;选择另一幅图像bacteria.tif 作为原始图像,见图2(d ),图2(e )是Abutaleb 方法的分割结果,图2(f )是新方法的分割结果.从对细菌阴影部分的分割效果可以看到:新方法总体上好于Abutaleb 方法.为进一步说明新方法的有效性,对其他的传统图像blood1.tif ,bonemarr.tif ,cameraman.tif ,cell.tif ,debye1.tif ,ic.tif ,kids.tif ,rice.tif ,shadow.tif ,shot1.tif 和tire.tif ,使用传统方法和新方法进行对比实验,实验中的自动分割阈值放在表1中,其中表1所引用图像的扩张名部分被省略,Abutaleb 方法阈值是按照文献[5]的实验结果.表1中不同分割方法的阈值“差值大”的图像图2给出对比图;差值是零或“差值不大”的图像,必能获得相同或相近的分割效果,因此图2没有给出后面这些图像的分割对比图.因此得出结论:该方法总能取得较好或与传统方法相当的视觉效果.图2　不同的分割方法的结果比较Fig.2　The result contrast between different segmentation methods・553・第3期 张云飞,等:利用二维熵自动确定图像分割的阈值表1　传统方法和新方法阈值对比T able1　The contrast betw een Abutaleb method threshold and new one图像bacteria blood1bonemarrcameraman cell debye1ic kids pearlite rice shadow shot1tireAbutaleb法阈值10268113116129115723710610811413858新方法阈值84741111101291717542141109114138573　结束语在创建二维直方图时,新方法的邻域中心所参考的像素与其相距“较远”并与其成“对角”关系,传统的Abutaleb方法的邻域中心所参考的像素与其直接“相邻”并与其成水平或垂直关系;新方法邻域中心的灰度值所参考的像素的灰度值与其“间断”,而传统的Abutaleb方法在产生二维直方图时,邻域中心所参考的像素的灰度值与其“连续”,因此新方法所反映的灰度的差异相对于Abutaleb方法会“更大”.对比实验表明新方法与Abutaleb方法在计算速度上基本相当,说明新方法是有效的.参考文献:[1]GONZAL EZ R C,WOODS R E.Digital image process2ing:2nd ed[M].Beijing:Publishing House of Electronics Industry,2002.[2]章毓晋.数字图像处理和分析[M].北京:清华大学出版社,1999.[3]ZHU Hongqing,SHU Huazhong,L UO Limin.Bloodvessels segmentation in retina via wavelet transforms u2sing steerable filters[A].Proceedings of the17th IEEE Symposium on Computer2Based Medical Systems (CBMS’04)[C].[s.l.],2004.[4]周德龙,申石磊,蒲小勃,等.基于灰度-梯度共生矩阵模型的最大熵阈值处理算法[J].小型微型计算机系统, 2002,123(12):136-138.　ZHOU Delong,SH EN Shilei,PU Xiaobo,et al.Maxi2 mum entropy thresholding algorithm based on the gray level2gradient co2ocurrence matrix[J].Mimi2micro sy2 seem,2002,123(12):136-138.[5]ABU TAL EB A S.Automatic thresholding of gray2levelpictures using two2dimensional entropies[J].Comput Vi2 sion Graphics Image Process,1989,47(1):22-32. [6]SA HOO P K,AROR G.A thresholding method basedon two2dimensional Renyi’s entropy[J].Pattern Recog2 nition,2004,37:1149-1161.[7]刘正光,林雪燕,车秀阁.基于二维灰度直方图的模糊熵分割方法[J].天津大学学报,2004,37(12):1101-1104.　L IU Zhengguang,L IN Xueyan,CH E Xiuge.Fuzzy entro2 py segmentation method based on2D gray histosram[J].Joural of Tianjin University,2004,37(12):1101-1104.・653・哈　尔　滨　工　程　大　学　学　报 第27卷。

基于VSAR的二维最大熵阈值分割算法
汪敬华;杜树新
【期刊名称】《计算机应用研究》
【年(卷),期】2004(21)12
【摘要】基于对传统二维最大熵算法各种改进方法分析,提出了一种基于判决域自动约束的二维最大熵改进算法.该算法提出了可以自动确定判决域大小的经验公式,与以往的改进算法相比,不仅减少了算法的运算量,同时具有自适应性,因而在某些应用场合具有较强的实用性.
【总页数】3页(P29-30,42)
【作者】汪敬华;杜树新
【作者单位】浙江大学,智能系统与决策研究所,浙江,杭州,310027;浙江大学,智能系统与决策研究所,浙江,杭州,310027
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于最大熵阈值分割算法的改进研究 [J], 叶文浩;张淼;罗芳
2.基于二维最大熵阈值的SAR图像分割算法 [J], 张红顺;杨凯达;张浩
3.一种基于二维最大熵的SAR图像自适应阈值分割算法 [J], 张红蕾;宋建社;翟晓颖
4.基于Sobel算子的图像快速二维最大熵阈值分割算法 [J], 李锋;阚建霞
5.基于Canny算子的二维最大熵阈值分割算法 [J], 张允;焦斌
因版权原因，仅展示原文概要，查看原文内容请购买。