灰度图像的二维交叉熵阈值分割法(投出稿).doc

灰度图像的二维交叉熵阈值分割法* 国家自然科学基金资助（编号：60572133）范九伦 雷博，(.西安邮电学院信息与控制系, 陕西 西安710061; .西安电子科技大学电子工程学院, 陕西 西安710071)摘要：一维Otsu法是一个经典的阈值分割方法，遵循该方法的构造思想，Li 与 Lee基于交叉熵提出了一个阈值分割方法。本文在解释和说明Li 与 Lee的方法的基础上，将其推广到二维灰度直方图上，提出了二维交叉熵的图像分割算法并给出快速递推公式。与二维Otsu法相比，本文方法能够更好的适应目标和背景方差相差较大的情形，是一个有效的阈值分割方法。关键词：阈值分割；Otsu法；交叉熵中图分类号： TN911.73 文献标识码： ATwo-dimensional cross-entropy thresholding segmentation method for gray-level images(FAN Jiu-lun LEI Bo，) (.Department of Information and Control, Xian Institute of Post and Telecommunications, ,Xian, Shaanxi 710061,China;. School of Electronic Engineering of Xidian University, Xian Shaanxi 710071, China)Abstract: One-dimensional Otsus method is a classical thresholding segmentation method. Li & Lee proposed a thresholding segmentation method based on cross-entropy following this thought. In this paper, we extend the cross-entropy method to two dimensions and present a fast recursive formula based on the explanation and illustration of Li & Lees method. Compared with the traditional two-dimensional Otsus method, the new method can be better adapted to the cases that the variance between the object and the background is large. It is validated that the new method is an available thresholding selection method. Keywords: threshold segmentation; Otsus method; cross-entropy1 引言图像分割是图像分析、理解和计算机视觉中的难点。在图像分割的诸多方法中，阈值化技术是一种简单有效的方法1。Otsu法2是广泛使用的阈值分割方法之一，Otsu法也称为最大类间方差法或最小类内方差法，等效于一维硬c-均值聚类算法3。Kurita等4在各类方差相等的约束下运用条件相关混合概率模型对Otsu法进行了解释，从文3和4的描述可见Otsu法在理论上适用于目标和背景方差相差不大的混合正态分布情形。Otsu法涉及到阈值、目标均值和背景均值，如果用与构造的二值图像作为待分割图像的“理想图像”，则Otsu法的基本思想是从待分割图像和“理想图像”的匹配角度，通过最小化均方误差来获得最佳阈值。交叉熵（相对熵、有向散度）描述了两个概率分布的差异性程度，借用交叉熵并利用Otsu法的基本思想，Li 和 Lee给出了另一个阈值分割方法5。我们6从条件相关混合概率模型的角度，基于泊松分布对Li 和 Lee的方法进行了解释，这种解释使得Li 和 Lee方法的数学机理更加清晰，为其更好的使用奠定了坚实的理论基础。此外我们也给出了Li 和 Lee方法的一种快速迭代算法7。从概率论和数理统计的知识知道，泊松分布和正态分布是有密切关系的，当泊松分布的参数比较大时，可以用均值和方差均为的正态分布来近似。鉴于Li 和 Lee方法可以用泊松分布进行解释，我们可以有理由的说，Li 和 Lee方法能更好的适用于灰度图像中目标和背景的方差相差较大的情形。（注：这里假定了图像中方差较小的部分处于较小灰度值处；方差较大的部分处于较大灰度值处。若出现相反的情形，只需反色即可。）一维Otsu法对含噪图像的分割效果不好，为此人们引入了二维灰度直方图并提出了二维Otsu法8，为了提高运行速度，快速递推算法也已经给出9。近年来有许多基于二维Otsu法的图像分割方法研究及应用10-12。与二维Otsu法的研究成果相对应，本文给出Li 和 Lee方法的二维推广。和理论解释相对应，本文方法对于目标和背景方差相差较大的图像的分割效果优于二维Otsu法。因此，本文的方法在一定程度上弥补了Otsu法的不足，是一个有效的阈值分割方法。2 一维交叉熵阈值法我们用来表示一幅大小为的数字图像，其中表示图像中第点的灰度值，。图像中灰度为的象素点总数记为，则图像中每一灰度值出现的概率可表示为 （1）设阈值将图像分为目标和背景两类，分别记为 和，则这两类的先验概率分别为 （2） （3）背景和目标对应的均值分别为 （4） （5）我们用表示分割后的二值图像。则Otsu方法通过衡量待分割图像与二值化图像之间的均方误差来获取最佳阈值。建立的准则函数为最小化 （6）改用灰度直方图表示，可得简化表达式 （7）由公式（4）和（5），可将改写成 （8）于是最小化等价于最大化下式 （9）式（6）描述的是每一象素点上原图像的灰度值与分割后的灰度值之间的偏差，式（7）描述的是原图像的灰度直方图与分割后的灰度直方图之间的偏差。基于这种认识，运用描述两个概率分布之间偏差的交叉熵，Li 和 Lee 给出另一个刻画待分割图像与二值化图像之间偏差的阈值分割方法，具体如下：和的交叉熵定义为 （10）改用灰度直方图表示，可得简化表达式 （11） 由公式（4）和（5），可将改写成 （12）于是最小化等价于最大化下式 （13） 将（9）和（13）对比，二者之间有惊人的相似之处，仅有的区别是式（9）采用的是乘法运算，；而式（13）采用的是对数运算，。 Otsu法适用于图像灰度直方图中目标和背景的方差相差不大的正态混合分布，一般而言对目标和背景的方差相差较大的正态混合分布的分割效果较差。在文6中我们用Poisson分布对Li 和 Lee 提出的交叉熵阈值分割方法进行了解释，使得对该方法的认识更为深入。由概率论与数理统计的知识，服从Poisson分布，参数为的随机变量记为，那么的均值为，方差为。概率取值为 （14）当取值较大时，对泊松分布利用Stirling近似公式 （15）可将Poisson分布转化为正态分布： （16）即可以认为。这意味着对于服从混合正态分布，目标和背景的方差相差较大的灰度图像，使用Li 和 Lee 提出的交叉熵阈值分割方法具有一定的合理性。从这一点上讲，交叉熵阈值分割方法能够更好的弥补Otsu法的不足，具有一定的实用价值。3 二维交叉熵阈值分割法一维图像阈值分割方法常常对含噪图像的分割效果较差，为此人们提出了在二维灰度直方图上进行阈值选取。对于一幅的数字图像，我们用表示图像上坐标为的像素点的灰度值，表示图像上坐标为的像素点的邻域的平均灰度值，的定义如下： （17） 其中表示取整运算。K为邻域宽度，一般取奇数。从的定义可以看出，如果图像的灰度级为，那么相应的像素邻域平均灰度的灰度级也为，和组成的二元组记为。在此基础上定义图像的二维直方图，该二维直方图定义在一个大小的正方形区域上，其横坐标表示图像像元的灰度值,纵坐标表示像元的邻域平均灰度值。直方图中任意一点的值定义为，它表示二元组发生的频率。由下式确定 （18） 其中是出现的频数，。图1根据二维直方图的定义，假设在阈值处将图像分割成四个区域，如图1所示。其中，对角线上的两个区域1和2分别对应于目标和背景，远离对角线的区域3和4对应于边缘和噪声8-9。一般认为在区域3和4上所有的。由图1可知，利用二维直方图中任意阈值矢量对图像进行分割，可将图像分成目标和背景两类区域，分别记为 和，则这两类的先验概率分别为 （19） （20）满足 （21）目标和背景对应的均值矢量分别为 （22） （23）二维直方图上总的均值矢量为 （24）我们用表示原图像在灰度值处的概率，用表示邻域平均图像在灰度值处的概率，那么， （25） （26）用和分别表示原图像在阈值为时目标和背景的先验概率，和分别表示原图像在阈值为时目标和背景的均值。那么 （27） （28） （29） （30）用和分别表示邻域平均图像在阈值为时目标和背景的先验概率，和分别表示邻域平均图像在阈值为时目标和背景的均值。那么 （31） （32） （33） （34）对于原图像，在阈值为时的交叉熵分割方法的准则函数为 （35）对于邻域平均图像，在阈值为时的交叉熵分割方法的准则函数为 （36）因此，在二维直方图上建立的以为阈值点的准则函数为 （37）最佳阈值取为： （38）注意到，由于 （39）鉴于是常数，因此，最佳阈值也可选为 （40） 4 快速递推算法和二维Otsu法一样，用穷举搜索的方法得到二维交叉熵阈值的计算量很大，不能满足实时性的要求。为此本节给出二维交叉熵阈值法的递推算法。我们记，。那么 （41） （42） （43） （44）具体的递推过程如下： （45） （46） （47） （48） （49） （50） （51） （52） （53） （54） （55） （56）用以上快速递推公式，每次计算不必都从(0,0)开始，将计算复杂度从降低到，大大节省了计算时间。同时快速递推的过程还减少了计算过程所需的存储空间，提高了算法的效率。如果不使用递推公式，的所有值一直需要保留在存储空间中，而使用快速算法不需要保留中间结果，这样可以节省存储空间提高算法效率。5 实验结果及分析仿真实验是在Matlab6.5环境下，在奔腾4、2.8GHz CPU和256M内存微处理器上进行的。在实验中，采用两幅图像：SAR图像和加了均值为0、方差为0.005的高斯噪声的细菌图像，尺寸分别为340340，178178。我们分别采用一维Otsu法、二维Otsu递推算法、一维交叉熵法以及本文给出的二维交叉熵递推算法进行了比较。在二维灰度直方图的构造时取。 （a）原图 (b) 二维直方图 (c) 一维Otsu法 (d) 二维Otsu法 (e) 一维交叉熵法 (f) 二维交叉熵法 图2 SAR图像的分割结果 （a）原图 (b) 二维直方图 (c) 一维Otsu法 (d) 二维Otsu算法 (e) 一维交叉熵法 (f) 二维交叉熵法图3 细菌图像分割结果SAR图像的实验结果如图2所示。从图2（b）可见，目标和背景的方差相差较大。从图2（c）（f）可见，基于交叉熵的方法总体上优于Otsu法，而二维交叉熵法获得了最好的分割效果，将河流与背景区分开来。细菌图像的实验结果如图3所示。从图3（b）可见，目标和背景的方差相差较大。从图3（c）（f）可见，基于交叉熵的方法总体上优于Otsu法，而二维交叉熵法获得了最好的分割效果。综合图2和图3的实验结果，对于目标和背景的方差相差较大的灰度图像，交叉熵法的分割性能优于Otsu法，而二维交叉熵法的分割效果是最好的。这说明二维交叉熵法能更好的处理目标和背景的方差相差较大的情形。表1 四种算法的运行时间及阈值比较（s）SAR图像细菌图像运行时间(s)阈值运行时间(s)阈值一维Otsu法0.411060.41116一维交叉熵法0.40950.4395二维Otsu递推算法0.88（102, 115）0.62(118, 127)二维交叉熵递推算法1.68(70,87)0.92(96, 103)表1给出了四种方法在运行时间和阈值上的比较，由表1可以看出，一维Otsu方法和一维交叉熵方法耗时较少。二维交叉熵方法和二维Otsu方法耗时较多。这是由于二维算法的复杂性大，计算量大，但由表1所示的时间可以看出这并不影响二维阈值化方法的实用性。6 结论一维交叉熵阈值法提出的思想和一维Otsu法是相同的，二者在表述上有相似之处。本文通过分析一维交叉熵阈值法的理论基础，将其推广到二维情形。为了提高运行速度，给出了递推算法。实验表明交叉熵阈值法能够更好的适应目标和背景方差相差较大的情况，而二维交叉熵阈值法在抑制噪声方面的效果是较好的。因此，本文提出的二维交叉熵阈值法是一个有效的图像分割算法。参考文献1 Sahoo P K, Soltani S, Wong A K C, Chen Y C. A survey of thresholding techniquesJ, Computer Vision, Graphics and Image Processing, 1988,41:233-260.2 N.Otsu, A thresholding selection method from gray-level histograms J, IEEE Trans. System Man Cybernetic.1979,9:6266.3 Kittler J, Illingworth J, On threshold selection using clustering criteriaJ, IEEE Trans. System Man Cybernetic.1985,15(5):652655.4 Kurita T, Otsu N, Abdelmalek N. Maximum likelihood thresholding based on population mixture models J, Pattern Recognition,1992,25(11): 1231-1240.5 Li C H, Lee C K. Minimum cross entropy thresholdingJ. Pattern Recognition,1993,26(4): 6176256 Jiu-Lun Fan. Notes on Poisson distribution-based minimum error thresholdingJ. Pattern Recognition Letters 19(1998):4254317 吴成茂、范九伦，基于交叉熵阈值法的快速迭代算法J.计算机应用与软件，2007，Vol.24 No 6:68 Wu Cheng-mao, Fan Jiu-lun. Rapid Iterating thresholding algorithm based on mulual entropyJ. Computer Applications and Software. 2007，Vol.24 No 6:688 刘健庄, 粟文青. 灰度图像的二维Otsu自动阈值分割法J. 自动化学报, 1993, 19(1): 101-105.Liu Jian-Zhuang, Li Wen-Qing. The automatic thresholding of gray-level pictures via two-dimensional Otsu methedJ.Acta Automatica Sinica.1993, 19(1): 101-105.9 唐英干,刘冬, 关新平. 基于粒子群和二维Otsu方法的快速图像分割J. 控制与决策，2007，Vol.22 No.2: 202205Tang Ying-gan, Liu Dong, Guan Xin-ping. Fast image segmentation based on particle swarm optimizati