基于直方图重构的极大交叉熵图像分割方法

フ 要:针对图像分割阈值选择问题，提出用动态参数将原始图像直方图分成两部分，构造两个新的相关直方图，分别对应于同原始图像等尺寸的虚拟图像，其中等概率像素是原始图像的相似像素。聚集计算两个构造直方图概率分布的交叉熵，分析其函数曲线极大值的峰谷关系，实现图像最佳多阈值分割。实验结果表明该方法的有效性。

ス丶词:图像分割；交叉熵；直方图重构；虚拟图像

ブ型挤掷嗪: TP391.41 文献标志码:A

Abstract: Concerning the thresholds selection in image segmentation, this paper proposed a method that used dynamic threshold to divide the histogram of original image into two new independent histograms. The two new histograms correspond to two fictitious images whose sizes are the same to original one，and pixels of the same probability are similar pixels of original image. The cross entropy can be assembled and calculated between probability distribution of the two new histograms. By analyzing the relationship between peak and valley of the maximum of entropy functional curve,the best multithresholds for segmentation image can be achieved. This method is simple and clear, and the experiment shows this method is effective.

Key words: image segmentation; cross entropy; histogram reconstruction; fictitious image

0 引言

在许多相关应用中，图像分割是最困难且最具挑战的问题之一，阈值分割方法由于算法简单、高效而最为著名［1］。阈值选择可以手工进行也可以自动化完成［2］。阈值方法可分为全局方法和局部方法，其中全局方法由于需要较少的计算代价因而更容易实施且快速［3-4］。文献［5］将阈值选择方法归为六类，其中，基于交叉熵的方法最受研究者关注［1］。文献［6］研究基于高斯分布的最小交叉熵最优阈值搜索；文献［7］则提出基于高斯分布的最小交叉熵迭代方法。

文献［8］提出最小交叉熵图像分割方法，并在文献［6-7］中得到进一步阐述，其主要贡献在于将交叉熵原理对图像分割问题进行了成功的数学建模，将分割前后的图像分别对应两个灰度概率分布，要求这两个分布在灰度守恒和信息熵差异最小的条件下获得优化。文献［9］则利用对称叉熵改进了文献［6］的方法。

文献［10］认为，现有最小交叉熵阈值化方法多是对交叉熵形式上的模拟［6,9］，或只是利用像素与类别的先验概率和条件概率［11］估计交叉熵中两个分布间的差异性而实现寻优，并提出了一种基于最大类间后验交叉熵准则的阈值化二值分割算法，该算法假设目标和背景像素的条件分布服从正态分布，利用贝叶斯公式估计像素属于目标或背景的后验概率，再搜索这两类区域后验概率之间的最大交叉熵。然而，文献［12］从理论上证明了文献［6,9］所提方法符合最小交叉熵概念，从而为最小交叉熵方法的广泛应用奠定了坚实的理论基础。研究认为，灰度守恒准则［6］的实质是将相似像素归为等概率事件［13］。

迄今，基于熵方法的自动多门限分割研究还比较少见。文献［14］介绍的自动多门限分割技术，需要进行直方图平滑等预处理，再对平滑直方图进行峰独立性判断，由平滑直方图确定分割类数。

最大交叉熵算法［10］具有两大缺点：1)需要假设目标和背景像素的条件分布服从正态分布，实际图像很难满足；2)需要利用贝叶斯公式估计像素属于目标和背景两类区域的后验概率，求解过于繁琐，而且对称交叉熵公式［10］的导出有一定经验性。

为解决上述的问题，本文提出一种基于直方图重构的极大熵搜索(Maximum Cross Entropy Based on Histogram Reconstruction，MCEBHR)算法。该方法将文献［6］的灰度守恒准则转换为等概率准则，应用极大交叉熵分析实现图像分割。该方法不对图像作任何分布假设，无需直方图平滑，直接搜索交叉熵曲线的极大值位置，再进行峰独立性判断，可实现自动多阈值图像分割。

1 直方图重构原理

最小交叉熵的灰度守恒条件［6］实质上是产生相关性时间序列函数的条件，它将每个像素灰度看作时间序列中的一个实现，假设存在与时间相关的灰度阈值，当给定阈值时，某像素必然处于某个可能所属的分割区域(目标或背景)之中，因此每个分割区域的灰度均值也是时间的函数。例如目标或背景，都被各自的灰度均值表示，显然，在图像分割过程中，每个具有特定灰度值的像素的概率测度就是时间相关实验的结果。图像分割是将相似像素归为一个均质区，灰度守恒条件则通过均质区内像素灰度的均值，产生交叉熵函数的约束准则，因此对验后分割图像而言，这些区域的每一个像素必然是等概率。所以，可以将分割阈值作为动态参数，对原始图像的目标与背景分别构造直方图［10］，它们各自对应一幅新的虚拟图像。应用交叉熵测度虚拟图像间信息的极大差异，就能得到优化分割结果。该方法无需对图像灰度分布作任何假设，也无需灰度守恒条件约束。

就简单图像而言，一般只包含目标和背景两个区域，其标准直方图特征就是呈现两个大小接近的波峰。为讨论方便，将直方图的亮灰度区域称为目标区(即直方图右侧或前段)，将直方图的暗灰度区域称为背景区(即直方图左侧或后段)，以下讨论中不再说明。

图1(b)是图像Lena的直方图，其数学表示为：Hist_g。假设存在一个阈值T=max(η(t))，它将直方图一分为二，前段为目标直方图，后段为背景直方图，分别用Pro_t_qian与Prb_t_houП硎尽S捎阢兄氮tУ乃阉鞴程是动态的，所以这两个分布不等长。假设阈值T=0.23时，两个构造直方图叠合在一起,如图1(c)所示。

两个直方图的成员个数相同，是进行交叉熵计算的必要前提。上述两个概率分布不等长，无法应用交叉熵测度它们之间的信息差异。由动态阈值tЫ原始直方图Hist_gХ直鸾囟铣闪礁龇植吉Pro_t_qianв氇Prb_t_hou，г颡

Hist_g=Pro_t_qian∪Prb_t_hou(1)

如果假设图像共有L个灰度级(一般L=256)，则两个分布的成员数(灰度级数)分别是［0,t)和［t,L］，Я礁龇植级杂Φ耐枷褡芟袼厥分别是sum［N0,Nt)和sum［Nt,NL]，N0表示灰度为0时的像素数，NL表示灰度为L时的像素数，Nt表示灰度为t时的像素数。显然，这两个分布的灰度级数(即成员个数)，所对应的图像总像素数都是tУ暮数。

为应用交叉熵原理测度两个概率分布的差异性，必须构造具有相同成员数的概率分布(用直方图表示)，同时，它们对应的图像像素总数也必须相等。

设目标和背景的构造直方图分别为Pro_t和Prb_t，г颍邯

Pro_t=(∑t-1j=0Prb_t_hou)∪ Pro_t_qian(2)

Prb_t=Prb_t_hou∪ ∑Lj=tPro_t_qian(3)

显然，Pro_tУ某稍笔为Вt-1,L］，П泉Pro_t_qianУ某稍笔Вt,L］，Ф嘁桓霆t-1；同样，Prb_tУ某稍笔为В0,t］，П泉Prb_t_houУ某稍笔В0,t)，Ф嘁桓霆t。同时，式(4)、(5)成立：

АLj=t-1Pro_t=1(4)

Аtj=0Prb_t=1(5)

相对于原始直方图，式(4)和(5)都是部分直方图。分析Pro_tУ某稍保只有t-1Щ叶任恢檬切槟獬稍保其概率是

Аt-1j=0Prb_t_hou(6)

式(6)表示全体背景像素灰度的概率之和，所以式(5)成立。同理，Prb_tУ某稍敝校只有tЩ叶任恢檬切槟獬稍保其概率是

АLj=tPro_t_qian(7)

式(7)表示全体目标像素灰度的概率之和，所以式(4)成立。虽然式(4)和(5)成立，但是Pro_t和Prb_tУ某稍笔不对等，即没有实际图像与之对应。需要对式(2)和(3)的构造直方图进行修改。

设对Pro_t和Prb_tУ男薷慕峁分别为Pro(t)和Prb(t)，г颍邯

Pro(t)=∪t-2j=0∑t-1j=0Prb_t_hou∪ ∑t-1j=0Prb_t_hou∪ Pro_t_qian(8)

Prb(t)=Prb_t_hou∪ ∑Lj=tPro_t_qian∪Lj=t+1∑Lj=tPro_t_qian(9)

分析Pro(t)У某稍保从灰度位置为0直到t-1Ф际切槟獬稍保其概率都是：Аt-1j=0Prb_t_hou。同理，Prb_t的成员中，从灰度位置t直到L都是虚拟成员，其概率都是：∑Lj=tPro_t_qian。显然，

АLj=0Pro(t)≠1(10)

АLj=0Prb(t)≠1(11)

分析式(10)、(11)，可以理解为，式(8)和(9)分别对应两幅虚拟图像。

Pro(t)Ф杂Φ男槟馔枷袷悄勘晡原始图像灰度分布，而背景则是同一个灰度值。即，在直方图Hist_gе校被阈值tХ指畛龅哪勘晡实际图像的全体灰度，而背景则是同一个灰度值，它们在构造直方图中，占位于相应的背景灰度级位置，但是却是同一个灰度值，并拥有同一个概率值，为等概率像素，即式(6)。

同理，Prb(t)Ф杂Φ男槟馔枷袷悄勘晡同一个灰度值，而背景则是原始图像灰度分布。即，在直方图Hist_gе校被阈值tХ指畛龅谋尘拔实际图像的全体灰度，而目标则是同一个灰度值，它们在构造直方图中占位于相应的目标灰度级位置，但是却是同一个灰度值，并拥有同一个概率值，为等概率像素，即式(7)。

式(8)、(9)所表示的直方图概率分布是一个联合概率分布，虽然两个构造直方图的概率不归一，但是它们的成员数等同，并且Pro(t)和Prb(t)Ф际倾兄氮tУ暮数。对虚拟图像中的灰度均质区域，即假设被分割出来的目标或背景，虽然不知道它的每一个像素来自于原始直方图的哪一个灰度级，但是，它一定来自于原始直方图的被重新构造区域，Ъ词(8)中的∪t－2j=0（∑t－1j=0Prb_t_hou），或式(9)中∪Lj=t+1(∑Lj=tPro_t_qian)。オ

交叉熵关系式如下

D(Q,P)=∑Nk=1qk lb qkpk(12)

式(12)是对两个分布Q和PУ幕バ畔(信息差异)的测度。在实际应用中，一般都是针对两个归一化分布，但是归一化处理的目的是让两个分布Q和P具有共同的基准，即对问题描述具有一致性。从这个角度来看， ∑ni = 1pi = 1，即概率分布归一化，并不是交叉熵关系式成立的必要条件，它只是充分条件。因此，就广义来看，式(12)应用中，只要两个分布Q和P对问题描述具有一致性(基准一致)，则这两个分布如何构造都不会影响对问题的求解，推论过程详见文献［13］。オ

关于构造直方图函数式(8)和(9)的一致性问题，可以从以下几个方面进行讨论。

1)在构造直方图函数中，虚拟成员的概率如何赋值。

Т由厦娴姆治隹芍，式(8)中的∪t－2j=0（∑t－1j=0Prb_t_hou）和式(9)中∪Lj=t+1(∑Lj=tPro_t_qian)相对于原始直方图而言，Ф际嵌匀笔У母怕释臣瞥稍(原始图像的灰度级)的补充，即虚拟成员，这些虚拟成员在其虚拟图像中的灰度都是同一个值，例如“0”或“1”，所以，它们的概率都应该是一样的，并且应该分别是式(6)和(7)的计算值。这样构造直方图的数值关系与原始图像直方图具有稳定一致的数值联系，并且都是阈值tУ暮数，在阈值搜索中构成一个时间序列函数分布。

2)两个构造直方图函数相互关系的同一性。

式(8)中Pro_t_qian和式(9)中的∪Lj=t+1(∑Lj=tPro_t_qian)，恰好与式(8)的实际成员与式(9)的虚拟成员相对应，其意义是：式(8)的实际成员概率被式(9)的虚拟成员概率所替代后所产生的信息差异，这正是交叉熵的意义所在。反之，式(8)中的∪t－2j=0（∑t－1j=0Prb_t_hou）和式(9)中的Prb_t_hou情况类似。所以，两个构造直方图的描述对象具有同一性。

3)两个构造直方图函数的空间(时间)基准的同一性是否稳定一致。

对式(8)或(9)来说，都包含原始直方图概率和构造直方图概率两个部分。对于原始直方图概率部分，每个灰度级的概率都是原始图像的统计概率；而构造直方图概率部分，每个虚拟成员(灰度级位置)的概率则都是所有虚拟成员对应原始直方图的概率之和，即原始图像中相应区域的所有灰度级的概率之和。也就是说，构造概率的各部分的概率基准不同一。MCEBHR方法采用构造概率的平均值作为基准，除以构造概率函数，将其归一化(标准化)。归一化重构直方图概率分布函数如下：

ИPro(t)=Pro(t)mean(Pro(t))(13)

ИPrb(t)=Prb(t)mean(Prb(t))(14)

式(8)和(9)都是t的函数，是一个动态概率分布，mean表示计算平均值。取其平均值作为动态归一化基准，是因为平均值来自于构造概率的全体成员(包括原始灰度级和虚拟灰度级成员)，具有稳定的一致性；并且，平均值都是来自于同一个原始直方图(对应于原始图像)，因而具有稳定的相关性。相反，其他基准，例如取其最大值或中值等，则都可能来自于构造概率的某个成员，从而导致基准失效。所以，平均值基准具有稳定的同一性。

2 基于直方图重构的极大交叉熵算法

基于直方图重构的极大交叉熵算法原理如下。

1)直方图重构。输入原始图像，设动态阈值为t，Ц据式(13)和(14)自动生成两个重构直方图概率分布。

2)交叉熵计算：根据式(12)~(14)，计算重构概率分布间的交叉熵。

根据式(12)写出它的对称形式如下：

D(Q:P)=∑Nk=1qk lb qkpk+∑Nk=1pk lb pkqk(15)

根据式(15)，写出重构概率分布间的交叉熵计算式如下：

Е(t)=D(Pro(t):Prb(t))= ∑Lj=0Pro(t)j lb Pro(t)jPrb(t)j+∑Lj=oPrb(t)j lb Prb(t)jPro(t)j(16)

3)交叉熵极值分析与阈值选取。在交叉熵函数式(16)中，由于灰度直方图概率不平滑，必然导致交叉熵函数曲线具有多局部极值，其中极大值点表示两个分布的信息差异较大，但是并非所有极大值都是有效的灰度阈值，需要进行阈值选取，具体在第3章进行分析。

4)阈值分割：应用第3)步的阈值选取策略，进行图像分割。

算法流程，参见图2【建议作者扩充上文，去掉图片】。相关实验与分析，参见第3章。

3 实验与分析

从直方图形状分析与阈值选取两个方面，以文献研究与目视判读相结合，对经典算法等与MCEBHR方法进行比较。对于实验图像Lena(如图1(a))，文献［6］认为,最小交叉熵方法是最好算法，Otsu算法公认较好，早期最大Shannon熵算法的分割效果最差。从文献实验结果以及直方图分析(如图1(b))来看，直方图第一个最低谷在［0,0.1］区间，但是以此阈值分割图像，则两类像素的总数差异较大，不可能达到交叉熵值最大，所以图1(a)的最佳阈值在［0.2,0.35］内。图2(b)表明，交叉熵曲线总体比较平滑，并在0.219B60灰度值处达到最大值，阈值0.219B60是图像灰度的转折点。

如图2(d)所示，交叉熵曲线包含两个极值点，如果选择0.509B80作为二值分割阈值，则［0.509B80,1］区间与［0,0.509B80］区间的像素总数差距较大，如图2(c)中的白色区域与灰黑色合成区域，这样的分割显然正确。选择0.219B60作为二值分割阈值，则证明了经典方法中，较好的阈值都落在［0.2,0.35］区间，而较差的阈值，如最大Shannon熵算法选择的阈值0.462B75，则比较接近0.509B80，可见MCEBHR方法具有必然性，它包含了经典方法所找到的全部阈值位置，只是合理程度不同，每种方法都具有有限合理性。

表1是不同分割算法对图1(a)的阈值。可以看出，对于图1(a)的分割阈值，最小交叉熵、基于最大类间后验交叉熵分割算法的分割效果比较接近，MCEBHR方法与最小交叉熵方法非常接近，因而属最好算法。此外，最大类间后验交叉熵方法需要假设目标与背景条件概率服从正态分布，其适应性较差。

下面验证MCEBHR方法对多阈值分割的有效性。图像3(a)虽然是单个目标的简单图像，但其灰度层次丰富，直方图(如图3(b))表现三个明显峰谷变化，所以用单个阈值对其分割，理论上具有不确定性，不同优化方法可能找到不同阈值，出错风险较大。从直方图分析，应该存在两个阈值将图像分为三个灰度区域比较合理，两个阈值的区间分别为［0.1,0.5］和［0.65,0.8］。

如表2，对图3(a)的分割阈值，就二值分割而言，最大Shannon熵算法的分割效果最差，其阈值为0.576B50；最大类间后验交叉熵分割算法较差，其阈值为0.658B82，它们都没有比较完善地分割出目标。Otsu算法阈值为0.388B20，最小交叉熵方法阈值为0.270B60，都获得了很好的分割效果，从直方图3(b)分析可知，

第一个波峰与后面两个波峰之间，具有较长的低谷区间，所以灰度阈值0.388B20和0.270B60对于目标的分割，区别非常小。另一方面，对于单个阈值分割而言，其最佳阈值落入第一个灰度区间［0.1,0.5］则是必然的，因为第二个区间［0.65,0.8］是目标灰度级间波峰的较大重叠区域，所以单个阈值分割方法必然将它们归为(或误认)为单个波峰，但是，如果目标的两个灰度波峰的重叠区域较小时，就可能发生错误。所以，MCEBHR方法相对比较严谨，它可以准确识别出两个阈值的位置：0.247B1以及0.721B6，用两种灰度共同表示分割目标，如图3(e)及图3(g)。

从图1(b)、图2(b)、(d)以及图3(b)、(d)、(f)、(h)可以看出，交叉熵曲线不是一条完全光滑的曲线，但是其主要波峰、波谷都对应于直方图曲线的特征阈值位置，可以用简单均值平滑方法消除曲线抖动，也可以直接应用独立峰判断准则［14］选择阈值。所以，图1(a)的最终分割结果如图2(a)。

对图3(h)搜索极大熵，可以获得22个极大熵值对应的候选阈值，包括0.517B60以及0.721B60和0.247B10(如图3(h)箭头所示)，其中有20个都处在［0.517B60, 0.721B60］区间内，在图3(b)直方图曲线的［0.517B60, 0.721B60］灰度区间中，存在较强的灰度变化导致了交叉熵曲线局部抖动。同样用文献［14］的方法，立即排除掉20个候选阈值，包括0.517B60。图3(h)交叉熵曲线中，阈值0.517B60是在较大谷底中的一个极小峰值，也是典型的可以被独立峰判断准则排除的对象。若取最大熵灰度阈值(如图3(d))作为唯一阈值，分割结果如图3(c)，显然，没有分割出目标的完整轮廓，可见，图3(a)不适合单个阈值分割。所以，最终分割结果如图3(e)。

4 结语

本文提出了一种新的极大交叉熵图像分割方法，可以实现多值分割。用直方图重构来实现图像分割的交叉熵分析是一个新尝试，从大量实验和分析来看，这个方法的理论和实践可行。基于直方图重构的交叉熵曲线是不完全平滑的凸曲线，所以并不能得出最大熵的阈值分割结果。但是这个曲线相对于原始直方图来说，是一条比较平滑的特征曲线，除了曲线的局部抖动外，其极大值特征点都对应于原始图像直方图有意义的阈值位置。如果对曲线进行适当处理和判断，可以获得图像的自动多阈值分割结果。

虽然交叉熵曲线仍然需要附加处理，但是与直接在直方图上进行预处理不同。一般地，图像直方图都具有非常频繁的灰度变化，直接在直方图上确定阈值，需要比较复杂的平滑预处理，平滑参数的确定等都是比较繁琐的问题［14］。重构直方图的原理及其交叉熵的求解表明，交叉熵曲线相对于原始直方图比较平滑具有必然性，因此，在交叉熵曲线中，进行阈值的选择，比直接直方图选择阈值更可靠、简便。

但MCEBHR方法依然需要对交叉熵曲线进行简滑和独立峰判断。下一步的改进包括，在进行交叉熵计算的同时，设法抑制邻域熵值的抖动，这样就可以更好地解决图像分割阈值自动化确定的难题。

げ慰嘉南:

[1] ALATTAS R. Multilevel minimum cross entropy thresholding using gamma distribution[D]. Riyadh: King Saud University, Department of Computer Science, 2007.

[2] HUANG Q, GAI W, CAI W. Thresholding technique with adaptive window selection for uneven lighting image［J］. Pattern Recognition Letters, 2005,26(6):801-808.

[3] HEMACHANDER S, VERMA A, ARORA S, et al. Locally adaptive block thersholding method with continuity constraints［J］. Science Direct, 2007,28(1):119-124.

[4] SAHOO P, ARORA G. Image thresholding using twodimensional TsallisHavrdaCharv~t entropy［J］.Pattern Recognition Letters, 2006,27(6):520-582.

[5] SEZGIN M, SANKUR B. Survey over image thresholding techniques and quantitative performance evaluation［J］. Journal of Electronic Imaging, 2004,13(1):146-165.

[6] LI C H, LEE C K. Minimum cross entropy thresholding［J］. Pattern Recognition Letters, 1993,26(4): 617-625.

[7] LI C, TAM P. An iterative algorithm cross entropy thresholding［J］. Pattern Recognition Letters, 1998,19(8):771-776.

[8] LI C H, LEE C K. Segmentation of die patterns using minimum cross entropy［C］// Proceedings of the 1992 International Conference on Industrial Electronics, Control, Instrumentation, and Automation. New York:IEEE,1992:721-724.

[9] BRINK A D, PENDOCK N E. Minimum crossentropy threshold selection［J］. Pattern Recognition Letters, 1996, 29(1): 179-188.

[10] 薛景浩, 章毓晋, 林行刚. 基于最大类间后验交叉熵的阈值化分割算法［J］. 中国图象图形学报, 1994, 4(2): 110-114.

[11] PAL N R. On minimum crossentropy thresholding［J］. Pattern Recognition Letters, 1996, 29(4): 575-580.

[12] 陆军, 王润生. 一种改进的最小互熵门限法［J］.计算机工程与科学, 1999, 21(4): 69-73.

[13] 曹建农.博士后科研工作报告［R］. 西安：西安测绘研究所,2010.

[14] 王润生.图像理解［M］.长沙：国防科技大学出版社,1995.