一种基于熵和聚类理论的图像阈值分割算法(共7页)

1、作者1等：稿件加工模板PAGE PAGE 7ADDIN CNKISM.UserStyle一种基于熵和聚类理论的图像(t xin)阈值分割算法张三(zhn sn)1，第2作者(zuzh)2(1.单位全名 部门(系)全名,省 市(省会城市不用加省名) 邮政编码；2. 单位全名 部门(系)全名)摘 要:基于聚类理论的Otsu算法和基于信息熵的Kapur算法是图像阈值分割中的两种经典思路。本文分析了这两种算法理论上的联系并结合它们的各自优势，提出一种新的算法。该算法能够抑制Otsu法均分像素点的趋势，又能够克服Kapur法易受干扰的不稳定性。实验结果表明，该算法对图像直方图不具有明显双峰、目标像素点占

2、比很小、图片存在干扰信息源等情况均能得到理想的分割效果。新算法具有更大的适用范围并且展现了更强的自适应性。关键词:Otsu算法; Kapur算法; 稳定性;自适应性中图分类号:* 文献标志码: A 文章编号：A novel image segmentation algorithm based on entropy and clustering theoryXING Ming-ming1, XING Ming-ming2(1.Dept.（School or College）of *, University, City Province Zip Code, China；)Abstract: The

3、re are two classical ideas in image thresholding. One is Otsus algorithm based on clustering theory, the other is Kapurs algorithm based on information entropy. At present work, the theoretical correlation between these two methods is analyzed. And their advantages have been combined to propose a no

4、vel algorithm, which can reduce the equally dividing trend of Otsus algorithm as well as the instability of Kapurs algorithm. The testing results show that the proposed algorithm can obtain good segmentations for images with non-ideal bimodal histogram, little targets, disturbing information, and so

5、 on. This algorithm can be used in a more generalized scope of image thresholding, and the self-adaptivity of it is illustrated.Key words: Otsu algorithm; Kapur algorithm; stability; self-adaptivity;引言在图像的阈值分割算法中，基于灰度直方图的熵阈值法（也称为Kapur法） REF _Ref354410367 h * MERGEFORMAT 1和基于灰度聚类的Otsu法 REF _Ref354411

6、178 h * MERGEFORMAT 2是两种不同的经典思想。近年来，以它们为基础已发展出多种丰富的算法且在各种类型的图像分割中取得了重要的成功 REF _Ref390941344 h * MERGEFORMAT 3。Kapur算法是假定目标和背景来自两个不同的信源，针对图像的灰度直方图，通过最大化后验熵，即:最小化传输中损失的信息量来获得一个合理阈值。这种分割思想充分考虑了信源的独立性，能够很好地提取图片中的特征信号，由此发展出的大量方法在目标检测、多目标提取等领域有着广泛应用 REF _Ref391204857 h * MERGEFORMAT 4 REF _Ref391204858 h

7、* MERGEFORMAT 5。Otsu算法的思想则与此不同，它分析的是图像像素点的灰度聚类，以像素点的灰度均值为基础考察目标部分与背景部分的类间方差，从而确定一个最佳的分割阈值。用该方法分割的图片不仅考虑了目标和背景的灰度均值尽量远离，而且倾向于均衡目标和背景的像素点数量 REF _Ref391368571 h * MERGEFORMAT 6。因此，在图像灰度直方图的形状有双峰但无明显低谷或者双峰与低谷都不明显时，采用Otsu方法往往能得到较为满意的结果。基于这个思想基础的方法在文本信息提取、医学图像分析等问题的研究中均取得了大量成果 REF _Ref391372963 h * MERGEF

8、ORMAT 7 REF _Ref391370551 h * MERGEFORMAT 8 REF _Ref391372725 h * MERGEFORMAT 9。经过多年的发展，基于聚类的算法和基于熵的算法已在图像阈值分割领域占有重要的地位，并取得了丰硕的成果 REF _Ref391370551 h * MERGEFORMAT 8 REF _Ref391372725 h * MERGEFORMAT 9 REF _Ref396378183 h * MERGEFORMAT 10 REF _Ref396378184 h * MERGEFORMAT 11。这两类方法的理论基础各异，因此它们所处理的图片类

9、型也各有侧重，基于聚类的算法多适用于直方图分布具有混合高斯型或其他解析函数型的图片，但对于小目标的分割存在局限性；基于熵的算法适用于目标与背景之间灰度差明显的图片，但对于直方图没有明显峰形的图片则效果不稳定。长期以来基于聚类的算法和基于熵的算法一直被视为相互独立的两类阈值分割法。现在，我们同时考虑这两类不同的图像信息处理方式，结合各自的理论基础，提出了一种新的算法。该算法能够充分吸收上述两类经典算法的优点，扩大阈值算法的适用范围，增强其自适应性。测试结果也进一步显示了该算法的先进性。 Otsu算法和Kapur算法 假定一个图片具有L阶灰度值,表示该图片内灰度值为i的像素点的数量，相应的总的像素

10、点数目,则灰度值i的分布概率为：其中且。Otsu阈值法：若有一个灰度阈值t将图片分割为背景A和目标B两类，, ，那么这两类的累积概率为： ， (1)A和B两类的灰度平均值为：， (2)图像(t xin)的灰阶总平均值为： (3)A和B各自(gz)的灰阶均方差(fn ch)定义为：， (4)则类内方差、类间方差、总方差及三者关系分别为 REF _Ref354411178 h * MERGEFORMAT 2: (5) (6) (7)对于一副给定的图片，是固定不变的。则从 REF _Ref391540189 h * MERGEFORMAT (7)式可以看出，Otsu法通过最大化类间方差选择最佳阈值等

11、价于最小化类内方差。于是，最佳阈值可由下式给出： or (8)Kapur算法:同样的将图片分为A和B两类，根据信息熵的定义： (9)联合 REF _Ref394500749 h * MERGEFORMAT (1)式，A、B两个区域的信息熵分别为：, (10)因为信息熵为广延量，则全局总熵为： (11)则Kapur算法的最佳阈值如下： (12)如上述公式所示，这两种经典算法的着重点各不相同。将 REF _Ref394658263 h * MERGEFORMAT (6)式代入 REF _Ref394330229 h * MERGEFORMAT (8)式可将Otsu法的目标函数改写为： (13) R

12、EF _Ref394658387 h * MERGEFORMAT (13)式包含以及两个因子，其中的最大化意味着目标和背景之间的灰度均值差异越大越好，符合图像分割的基本原则。但是达到最大值时有，即目标和背景像素点所占比例一样。虽然这两个因子一般不会同时达到最大，但二者会相互制约，导致Otsu法有均分背景和目标在图像中占比的趋势。因此，大部分时候该方法对小目标的提取效果不佳。对于Kapur法的目标函数同样可以改写为： (14)注意到 REF _Ref394330378 h * MERGEFORMAT (14)式中的概率分布已经对和进行过归一化。因此，该方法对目标和背景的像素点占比并不敏感，是对O

13、tsu法的一个重要补充。此外，由等概率原理可知， REF _Ref394330378 h * MERGEFORMAT (14)式的最大化倾向于将目标和背景分割为灰度均匀分布的两个部分。若图片的直方图没有明显的峰形层次，该方法的应用将会受到限制。新的算法基于上述两种算法的各自优缺点，我们提出一种综合算法。该算法能够充分吸收Kapur法以及Otsu法的优势，使得图像的阈值分割具有更强的自适应性。新算法的目标函数如下： (15)最佳分割阈值由下式确定： (16)(15)式的提出是基于一种理想化的混合高斯直方图分布，如Fig.1所示。因为Kapur算法在理论上指出熵函数的最优解将落在两峰之间的低谷处

14、REF _Ref354410367 h * MERGEFORMAT 1。同时，Otsu算法也是预期目标和背景各自的灰阶直方图是具有相同方差的两个正态分布。所以，对于具有如Fig.1(a)分布形式的图片，公式 REF _Ref394330229 h * MERGEFORMAT (8)和 REF _Ref395212040 h * MERGEFORMAT (12)将会得到相同的分割阈值，该值也是 REF _Ref395212179 h * MERGEFORMAT (16)式的结果。 (a)(b)Fig.1 (a)准理想混合高斯分布人工合成图的直方图 (b)Kapur和Otsu目标函数值随灰阶值变化

15、曲线 值得一提的是，虽然(surn)公式 REF _Ref394330229 h * MERGEFORMAT (8)和 REF _Ref395212040 h * MERGEFORMAT (12)的目标(mbio)都是关于的函数，但二者的数量级差异很大，如图Fig.1(b)所示：Kapur法的目标(mbio)函数值不但远小于Otsu法，而且在该坐标尺度下几乎看不出前者随t的变化关系。因此，不可以用简单的加法来构造新的目标函数，必须考虑 REF _Ref394330229 h * MERGEFORMAT (8)和 REF _Ref395212040 h * MERGEFORMAT (12)之间的

16、数量级关系，使得这两种分割思想具有可比拟的权重。Fig.1(a)的直方图是由两个高斯分布叠加而成，对于单个高斯分布，由 REF _Ref395213670 h * MERGEFORMAT (9)式可知其Shannon熵为： (17)式中为自由变量的概率密度函数。将正态分布代入上式得： (18)由于Fig.1(a)的最优分割结果是使得A、B分别为高斯分布，此时由 REF _Ref395253962 h * MERGEFORMAT (18)式易知： (19)将 REF _Ref395254130 h * MERGEFORMAT (19)式代入 REF _Ref395254133 h * MERGE

17、FORMAT (5)式，同时注意到此时以及，则可得： (20)其中常数。由 REF _Ref395262399 h * MERGEFORMAT (20)式可知，对于理想化的双峰分布，Kapur法和Otsu法所对应的最优目标函数在数值上存在对数关系，因此，与具有可比拟的权重，可用于构造如 REF _Ref395261372 h * MERGEFORMAT (15)式所示的目标函数并应用于图像的阈值分割，具体如下：输入： 一张灰阶度L=256的灰度图像输出： 图像分割最佳阈值Step.0 获得灰度直方分布H(t), Step.1 For t=0,255 利用(5)式计算目标和背景的类间方差Step

18、.2 For t=0,255 利用(11)式计算灰度分布的全局总熵Step.3 对做对数处理获得Step.4 利用(15)式计算新算法目标函数值Step.5 For t=0,255 计算及其对应的t值即为最佳阈值实验结果分析为了验证上述提出的新算法的有效性，本文对一些无损检测图片和热成像图像序列集进行了分割实验，并与Otsu、Kapur算法结果进行比较，发现Otsu、Kapur算法处理这些不同类型的图片时，有各自的优越性和适用图片范围，而结合两种算法优越性的新算法具有更强的自适应性，不仅可以自动选取Otsu和Kapur算法二者之间的较优结果，而且能够在这两种算法结果均不理想的情况下获得更好的分

19、割效果。现取其中的四幅图片为例，如Fig. 2-5所示，其对应的直方图及分割位置如Fig. 6所示。结合图片及其对应的直方图，我们可以看出新算法对Otsu法以及Kapur法各自优势的吸收以及创新。对于Fig.2(a)，目标和背景所占像素点数目差别不大且各自的峰形明显，此时Otsu算法获得的分割效果明显优于Kapur算法，而新算法的结果与Otsu算法的结果一致。对于Fig.3(a)，目标，培养皿，背景各自形成了三个峰，由于目标所占据像素点较少，Otsu算法具有均衡像素点的倾向，阈值被误判在培养皿与背景之间，而Kapur从信源独立性的角度考虑却能够获得合理的阈值。此时，新算法的结果与Kapur算法

20、的结果一致。对于Fig.4(a)，Otsu算法依然在处理小目标的问题上暴露缺陷，新算法可予以纠正。在Fig.5(a)建筑物图中，Otsu算法选择的阈值造成欠分割，而Kapur算法选择的阈值造成过分割，均不够理想。此时，新算法在综合权衡后，能够在欠分割与过分割之间找到一个合理的阈值，这也进一步说明了该算法的先进性。 (a) (b) (c) (d)Fig.2 (a) PCB原图 (b)Kapur算法结果 (c)Otsu算法结果 (d)新算法结果 (a) (b) (c) (d)Fig.3 (a) Cell原图 (b)Kapur算法(sun f)结果 (c)Otsu算法(sun f)结果 (d)新算法

21、结果 (a) (b) (c) (d)Fig.4 (a) Thermal image原图(yun t) (b)Kapur算法结果 (c)Otsu算法结果 (d)新算法结果 (a) (b) (c) (d)Fig.5 (a) Tall-Building原图 (b)Kapur算法结果 (c)Otsu算法结果 (d)新算法结果(a)(b)(c)(d)Fig.6 图片的直方图及算法选择的阈值 (a)PCB (b)Cell (c) Thermal image (d)Tall-Building上述四幅图像的灰度直方图分别如Fig.6(a)-(d)所示，利用Otsu算法、Kapur算法以及新的算法可分别得到它们

22、的阈值分割结果。这些结果充分显示，新算法能够(nnggu)继承Otsu以及Kapur这两种经典算法各自的优点，获得更好的分割视觉效果。为了进一步验证新算法的稳定性和良好的自适应性，我们(w men)分别对Kapur算法、Otsu算法以及新算法进行了如下三种检验 HYPERLINK l M2004 3：1）Misclassification error（ME），2）Relative foreground area error (RAE)，3）Modified Hausdorff distance (MHD).采用的测试集为25张具有基准图（ground truth image）的无损(w sn)

23、检测（NDT）成像图片，这些测试图片来源于参考文献 REF _Ref390941344 h * MERGEFORMAT 3、 HYPERLINK http:/homepages.inf.ed.ac.uk/rbf/CVonline/Imagedbase.htm l gesture CVonline图库及 HYPERLINK /otcbvs/bench/ OTCBVS基准数据集。限于篇幅，现展示其中的4张图片及其基准图： Fig.7 部分原图及其对应的基准图对于单阈值分割问题，ME定义为图片分割以后目标像素点误分到背景中，以及背景像素点误分到目标中的比例。ME的表达式如下 REF _Ref3962

24、44480 h * MERGEFORMAT 12： (21)这里分别表示基准图片的背景和前景像素点集，分别代表分割后图片的背景和前景像素点集，ME数值越小意味着分割越准确。RAE用以衡量分割目标与基准图之间的面积差异，表达式为 REF _Ref390941344 h * MERGEFORMAT 3 REF _Ref396244646 h * MERGEFORMAT 13: (22)其中分别代表基准图片和分割后图片目标区域的面积。所以，对于一个目标精确的理想分割，它的RAE值为0。MHD用以评估分割目标与基准目标之间的形状失真度，定义为 REF _Ref396375888 h * MERGEFO

25、RMAT 14：( SEQ ( * ARABIC 23)其中 (24)分别表示基准图片和分割后图片的目标像素点区域，表示基准图中目标像素点与分割结果中目标像素点之间的Hausdorff距离，由于该距离是针对每一个像素点各自生成的，分割结果中的噪声点往往会产生较大的距离，但这部分像素点的数量较少，故在 REF _Ref409343154 h * MERGEFORMAT (24)式中采用对所有点的Hausdorff距离求平均的方法来定义分割结果与基准图之间的差异，这一数据可以客观地反映图像形状相对于基准图的失真程度。值得注意的是：由于图片的任意性，两个图形之间的Hausdorff距离均值无法设置上

26、限，因此 REF _Ref409119677 h * MERGEFORMAT (23)式获得的MHD值并未被归一化，该参量的变化范围与ME、RAE的范围不同，不局限在0,1之间。不过，MHD值越小仍然说明分割的失真度越小。综上，我们可以得到测试集中第i张图片的分割效果评估，如下表所示：表1 三种算法对测试集内25张图片的分割检验图片序列算法MERAEMHDKapur0.04410.05022.01851Otsu0.56370.64177.3633New0.04410.05022.0185Kapur0.87740.9315.9212Otsu0.0150.22681.9383New0.00140.

27、02090.3587Kapur0.01020.0030.57543Otsu0.55770.560613.0798New0.55770.560613.0798Kapur0.00710.24421.08314Otsu0.39090.965311.1604New0.00710.24421.0831Kapur0.16180.16814.83285Otsu0.02760.03331.1890New0.02760.03331.1890Kapur0.08620.49413.23086Otsu0.10330.60183.8108New0.08650.50283.2508Kapur0.00220.360.214

28、37Otsu0.63190.993910.3939New0.00220.360.2143Kapur0.29490.70446.22938Otsu0.11690.24383.4923New0.11490.31713.8532Kapur0.00070.20920.12519Otsu0.58890.99514.2661New0.00070.20920.1251Kapur0.04840.62872.254910Otsu0.24670.89615.5875New0.04840.62872.2549Kapur0.22640.61275.56611Otsu0.08840.04813.3471New0.089

29、60.06263.3948Kapur0.10890.11553.290612Otsu0.0480.05441.9793New0.05070.05732.0526Kapur0.02680.00892.190113Otsu0.0250.00642.1373New0.02680.00892.1901Kapur0.15010.55651.541714Otsu0.19340.94887.3194New0.01510.55651.5417Kapur0.11020.21674.026615Otsu0.08310.16333.5372New0.08740.17173.6243Kapur0.05070.0734

30、3.308616Otsu0.02570.01741.7468New0.02840.02611.923Kapur0.36530.763710.449917Otsu0.01140.02391.3902New0.01770.03711.7360Kapur0.62260.876113.00218Otsu0.12370.05314.6831New0.15840.11925.6969Kapur0.14080.27544.486219Otsu0.12490.24434.1723New0.13010.25444.2676Kapur0.00980.01851.120620Otsu0.00690.00900.06

31、54New0.00690.00840.0596Kapur0.08230.26843.548921Otsu0.03150.10262.2508New0.03570.11662.4182Kapur0.03680.07342.778722Otsu0.03130.05322.2970New0.02930.01482.4358Kapur0.00480.00180.503423Otsu0.00530.00390.4821New0.00480.00180.5034Kapur0.08460.14974.143424Otsu0.06020.09633.4116New0.01880.03221.7481Kapur

32、0.0060.00621.124925Otsu0.27230.283210.0817New0.0060.00621.1249从表1可以(ky)看出，由于图片具有(jyu)任意性，新算法不能保证(bozhng)对所有的测试图都得到最好的分割效果，但该表的25组数据可以进行统计分析，结果如下所示：表2 Otsu、Kapur以及新算法评估函数的均值和方差分析算法MERAEMHD均值方差均值方差均值方差Kapur0.13720.04420.31230.08763.902715.4500Otsu0.17460.04240.33030.13684.842516.2780New0.06470.01270.1

33、7570.04042.48346.8347表二的数据显示，新算法的三个性能指标(ME，RAE以及MHD)参量的均值全部小于Kapur算法以及Otsu算法的结果，由前述定义可知数值越小即分割效果越理想。所以新算法在阈值分割中具有统计意义上的优势，充分说明该方法具有更广阔的应用范围。此外，方差表示一个统计变量的离散程度，该值越小说明变量的变化范围越小。应用于算法的效果评估则代表稳定性，从表二可以看出，新算法在ME、RAE、MHD这三种检验中展现出的稳定性全面超越了前述的两种经典算法。结论本文综合考虑了灰度聚类分析以及直方图信息熵之间的理论关系，在Otsu和Kapur这两种经典算法的基础上提出一种新

34、的算法。该算法能够充分吸收Otsu法以及Kapur法的优点，很好地解决了Otsu算法对于直方图为单峰、三峰或不明显双峰时分割效果不理想的情况，同时避免了Otsu算法对小目标图片的过度分割。另一方面，由于Kapur算法对信息源具有较高的敏感度，因此在分割过程容易被冗余信息源或者次要目标干扰，使得结果不稳定，而实验结果表明，新算法能够在很大程度上提高分割的准确性和稳定性。因此，新算法的适用范围能够进一步扩大并且具有更高的自适应性。 参考文献1Kapur J N, Sahoo P K, Wong A K C. A new method for gray-level picture threshold

35、ing using the entropy of the histogramJ. Computer vision, graphics, and image processing, 1985, 29(3)：273-285.2Otsu N. A threshold selection method from gray-level histogramsJ. Automatica, 1975, 11(285-296)：23-27.3M. Sezgin and B. Sankur. Survey over image thresholding techniques and quantitative pe

36、rformance evaluation J. Journal of Electronic Imaging, 2004, 13(1):146-165.4吴一全, 沈毅, 刚铁, 等. 基于二维对称 Tsallis 交叉熵的小目标图像阈值分割J. 仪器仪表学报, 2011, 32(10): 2161-2167.Yijun Wu, Yi Shen, Tie Gang, et al. Thresholding for small target image based on 2-D symmetric Tsallis cross entropy J. Chinese Journal of Scient

37、ific Instrument, 2011, 32(10): 2161-2167. (in Chinese)5Soham Sarkar and Swagatam Das. Multilevel Image Thresholding Based on 2D Histogram and Maximum Tsallis EntropyA Differential Evolution Approach J.IEEE Transactions on Image Processing, 2013, 22(12):4788-4797.6Qiao, Y., Hu, Q.M., Qian, G.Y., Luo,

38、 S.H., Nowinski, W.L. Thresholding based on variance and intensity contrast. Pattern Recognition, 2007, 40: 596608.7刘健庄，栗文青. 灰度图像的二维Otsu自动阈值分割法. 自动化学报, 19(1), 101-105 (1993).JianZhuang Liu, WenQing Li. The automatic thersholding of gray-level pictures via two-dimensional Otsu method. Acta Automatica Sinica, 19(1), 101-105 (1993). (in Chinese)8Wen J, Li S, Sun J. A new binarization method for non-uniform illuminated document imagesJ. Pattern Re