Journal of Computer Applications 计算机应用，2012，32( 6) : 1526 － 1528 ISSN 1001-9081 CODEN JYIIDU 2012-06-01 http: / / www． joca． cn 文章编号: 1001 － 9081 ( ) 2012 06 － 1526 － 03 : doi 10． 3724 / SP． J． 1087． 2012． 01526 基于分解的三维 Otsu 图像分割快速算法 龚 劬 * ，倪 麟，唐萍峰，王菲菲 ( 重庆大学 数学与统计学院，重庆 401331) ( * 通信作者电子邮箱 nilin871124@ 163． com) 摘 要:针对三维 Otsu 图像分割算法计算复杂度高、运算量大的问题，提出一种基于分解的三维 Otsu 图像分割 快速算法。首先将三维 Otsu 分解为三个一维 Otsu; 然后，在分析一维 Otsu 的基础上，结合类间距离和类内距离，提出 一种新的阈值识别函数设计算法，并给出了快速实现方法。实验结果表明，该算法不仅可以取得较好的分割效果，而 且计算量较小，比三维 Otsu 阈值分割递推算法快 1 400 倍左右。 关键词:图像分割; Otsu 法; 类间距离; 类内距离; 阈值识别函数 中图分类号: TP391． 41 文献标志码:A Fast three-dimensional Otsu image segmentation algorithm based on decomposition GONG Qu * ， NI Lin， TANG Ping-feng， WANG Fei-fei ( College of Mathematics and Statistics， Chongqing University， Chongqing 401331，China) Abstract: Concerning the high the computational complexity and huge calculation of the three-dimensional Otsu， a fast three-dimensional Otsu image segmentation algorithm based on decomposition was presented in this paper． Firstly， the original three-dimensional Otsu algorithm was decomposed into three one-dimensional Otsu algorithms． Then， based on the one- dimensional Otsu algorithm， a new algorithm with a new threshold recognition function was proposed， which combined between-class distance with within-class distance， and the fast realization method was also presented． The experimental results show that the proposed algorithm does not only get satisfactory segmentation result， but also improves the calculation speed， about 1 400 times the recursive algorithm for the three-dimensional Otsu method． Key words: image segmentation; Otsu algorithm; between-class distance; within-class distance; threshold recognition function 0 引言 图像分割技术是计算机视觉和人工智能领域中一个重要 而又难以处理的研究内容。到目前为止，人们基于各种立场 和观点，提出了各式各样的图像分割方法［ 。在这些方法 中，阈值方法因其简单且性能稳定而成为图像分割中的基本 技术之一，众多国内外学者对此进行了深入、广泛的研究，提 出了不少应用算法［ ］ 是一种基于阈值的图像 分割方法，在大多数情况下都能取得良好的分割效果。但是， Otsu 法无法区分图像中与目标的灰度相近的噪声。 。Otsu 法［ 3 － 6 1 － 2 ］ ］ 7 9 8 10 为此，刘健庄等［ ］提出了二维 Otsu 方法，以像素灰度作 为一维，邻域平均灰度作为另一维，以此来达到较好的去噪效 ］提出基于分解的阈值选取算法，求解两个一维 果。岳峰等［ Otsu 法的阈值来代替原始的二维 Otsu 法的最佳阈值。景晓 ］在二维 Otsu 方法的基础上，加上邻域中值作为第三 军等［ 维，将二维 Otsu 方法推广到了三维，取得了非常好的分割效 果，但是时间复杂度为 O L3 ) ］ 也做出了改 进，但是时间复杂度仍然在 O ］提出了加权的 三维 Otsu 方法，时间复杂度降到 O ) ，达到了很好的去噪效 果并且大幅度地提高计算速度，但权系数的确定依赖于具体 图像，比较费时。 。对此，范九伦等［ L3 ) ; 吕燕等［ ( L 11 12 ( ( 针对三维 Otsu 算法计算量大的问题，本文提出一种基于 分解的三维 Otsu 图像分割算法。首先利用分解的思想来降 低算法的时间复杂度，然后在分析一维 Otsu 算法的基础上， 结合目标类和背景类两类之间的距离以及类内距离，提出了 一种新的阈值判别函数设计算法。通过大量的实验表明，相 对于分解的二维 Otsu 算法［ 、加权三 ］而言，本文算法分割效果更为理想，同时计算 维 Otsu 算法［ 速度也具有明显的优势。 1 三维 Otsu 算法 、三维 Otsu 递推算法［ ］ 9 ］ 11 12 10 景晓军等［ ］利用原始图像、邻域平均图像以及邻域中值 图像联合直方图，提出了三维 Otsu 算法。该方法不仅充分利 用了图像像素点的信息，而且还考虑到了邻域图像像素点以 及邻域中值图像像素点的空间相关信息，具有很好的抗噪性。 三维 Otsu 算法在文献［ 10 2 分解的三维 Otsu 算法 ］中有详细叙述，在此不再赘述。 根据岳峰等［ 9 ］的二维分解的 Otsu 算法，推导出三维分解 的 Otsu 算法。 根据三维直方图，假设三元组 ( ) 出现的频数为 Cijk 那么像素灰度值 i、邻域均值 j 和邻域中值 k 出现的频数分别 ， j ， k i ， L －1 为 fi = ∑ j = 0 L －1 ∑ k = 0 L －1 L －1 Cijk 、gj = ∑ i = 0 ∑ k = 0 Cijk L －1 和 hk = ∑ i = 0 L －1 ∑ j = 0 Cijk ，由此得 收稿日期:2011-11-23;修回日期:2012-01-14。 作者简介:龚劬( 1963 － ) ，女，四川威远人，教授，博士，主要研究方向: 图像处理、小波分析; 倪麟( 主要研究方向: 图像处理; 唐萍峰( 阳人，硕士研究生，主要研究方向: 图像处理。 1987 － ) ，男，四川广安人，硕士研究生，主要研究方向: 模式识别、图像处理; 王菲菲( 1987 － ) ，男，四川威远人，硕士研究生， ) ，女，河南濮 1987 － 

第 6 期 龚劬等: 基于分解的三维 Otsu 图像分割快速算法 7251 到 边 缘 概 率 为 Qi = ∑ L －1 j = 0 L －1 ∑ k = 0 L －1 L －1 pijk 、Rj = ∑ i = 0 ∑ k = 0 pijk 、Hk = L －1 L －1 ，并分别作为 i ， j ， k 的一维直方图的值，其中 0 ≤ i ， ， j j = 0 i = 0 pijk ∑ ∑ k ≤ L － 1。由一维 Otsu 方法的原理，得到求 s 类间散度函数如下。 像素灰度值的类间方差: ， t ， q 最佳阈值的 ( ( ) ， μ0 ) 是 对 应 各 自 类别 元 素 均 值 。可 以 看 出， ) 越大，类间距离就越大，目标和背景就分得越开，分割效 s ( s 其中 μ1 sb 果就越好。 s 定义 2 设用值 s 将一组离散的数据分为了两类， Pi 是数 ) 分别是两类所占的概率， ) 是对应的两类的均值，那么这两类的类内距离 ) 和 W1 s s ( ( 据 i 出现的概率， W0 μ0 分别为: ) 和 μ1 s s ( ( ( ) s σBi = ( s ∑ i = 0 Qi ( L －1  ) ∑   ∑ 邻域均值的类间方差: ∑ i = s +1 L －1 Qi i = s +1 i = s +1 iQi Qi ( ) t σBj = ( t ∑ j = 0 Rj s  ) ∑   ∑ i = 0 s iQi Qi i = 0 L －1 L －1 － ∑ i = 0 iQ 2   i + L －1 － ∑ i = 0 iQ 2   i t j = 0  ) ∑   ∑ t jRj Rj j = 0 L －1 L －1 － ∑ j = 0 jR 2   j + L －1 － ∑ j = 0 jR 2   j ( L －1  ) ∑   ∑ 邻域中值的类间方差: ∑ j = t +1 L －1 j = t +1 Rj j = t +1 jRj Rj ( ) q σBk = ( ( q ∑ k = 0 Hk L －1 ∑ k = q +1 Hk q  ) ∑   ∑ k = 0 q k = 0 kHk Hk kHk L －1  ) ∑   ∑ k = q +1 L －1 Hk 由一维 Otsu 方法知，最佳阈值 ( s0 = arg max 0≤s≤L －1 σBi k = q +1 ( ) { s ) t ( ( ) q t0 = arg max 0≤t≤L －1 σBj q0 = arg max 0≤q≤L －1 σBk 3 本文算法 L －1 － ∑ k = 0 kH 2   k + s0 2   k ) 由式( L －1 － ∑ k = 0 kH ， t0 s0 ， q0 ( ) 3 ) 得到: 4 ( ) 4 由于本文已经成功地将三维分解为三个一维即将三维 ) ，所以在 Otsu 递推算法的计算复杂度从 O 求取最佳阈值时，就放在一维的 Otsu 中求取最佳阈值，这样 ) ，可大幅度地提高计算速度，提 算法的计算复杂度就为 O 高算法的实用性。 L3 ) 降到了 O L L ( ( ( 传统三维 Otsu 算法和加权的三维 Otsu 算法的阈值识别 函数都只考虑目标类和背景类的方差大小，也就是说类间的 方差越大，分割的效果越好。然而，上述的两个算法都没有考 虑到目标类和背景类的每个类自身像素的分类信息，也就是 说没有考虑类内的内聚性。因此，本文从同时考虑类间距离 和类内距离出发，提出了一个新的阈值识别函数。 定义 1 设用值 s 将一组离散的数据分为了两类，对于这 两个类，定义其类间距离为: ( ( ) ( ) sb s = μ1 s － μ0 s ) ( ) 5 ( ) 1 ( ) 2 ( ) s d0 = s ∑ i = 0 Pi L －1 i － μ0 ( ) W0 s ( ) ∑ i = s +1 Pi i － μ1 ( ) s = d1 两类的总体类内距离为: W1 s ( ) s ( ) s ( ) 6 ( ) 7 ( ) 8 ) 的值取得最 ( s ( ) = W0 s sw 显然，式( 8 ) ( ) s d0 ( ) 表现为类内的内聚性，当 sw + W1 d1 s s s ( ) ( ) 小时，分割效果最好。 因此，同时考虑以上两个因素，既要保证类间距离最大， 又要做到每个类的内聚性最好，这样才能获得更好的分割效 果。基于这个要求，本文在分析 Otsu 的基础上，提出了一个 新的阈值判别函数，阈值求取公式为: ( ) s W0 ( ) ( ) s sb W1 ( sw s ) s 9 = ) 取最大值所对应的灰度级即为所求的最佳阈值 ( ) ( G ) s ( 当 G s ，即 s0 = arg max { ( G ) } s 。 求取最佳阈值时，若采用边缘概率 Qi = ∑ L －1 j = 0 L －1 ∑ k = 0 pijk 、Rj = L －1 L －1 L －1 L －1 j = 0 i = 0 i = 0 k = 0 pijk ∑ ∑ pijk 、Hk = ∑ 来计算耗时较多。因此，本文还提 ∑ ，采用下面的 出一种快速求取阈值的方法。对于最佳阈值 s0 办法来求取: 对原图像直接求取各个灰度级出现的概率 Pi ， 然后根据式( ，先对原灰度 图像进行预处理，由原图像得出邻域均值图像，然后再计算邻 ) 域均值图像各个灰度级出现的概率 Pi ，类似可求邻域中值图像的最佳阈值 q0 。 中计算出最佳阈值 t0 4 实验结果 ) 求取最佳阈值 s0 ; 而最佳阈值 t0 ，最后再代入到式( 9 9 ) ( 。 9 － 12 R2007b 为了验证本文算法的有效性和可行性，实验选取了 4 幅 ］的 算 法 进 行 了 比 较。实 验 环 境 为 3． 19 GHz 图片并 与 文 献［ Windows XP 操 作 系 统，系 统 配 置 1． 96 GB 内 存， CPU ， Matlab 7． 5． 0 一个图像分割算法的客观评判标准是计算复杂度小 、分 割速度快、分割效果佳，可以较好地将目标从背景中分离出 来，同时达到很好的去噪效果: 一方面，本文算法既利用图像 的灰度信息，也利用了像素点的邻域空间相关信息即像素点 的邻域均值和邻域中值，因而较二维 Otsu 算法对噪声有更好 的去噪分割效果，如轮船图片的分割; 另一方面，由于本文算 法的阈值判别函数结合了类间距离和类内距离，使得本文算 法充分考虑了背景类和目标类之间的离散测度信息以及背景 类和目标类类内的内聚性，如闹钟图的分割效果，闹钟旁边的 数字“8”只有本文算法分割出来了，这是其他算法都不能达 到的效果。表 1 是几个算法的时间比较，由于本文算法采用 

8251 计算机应用 第 32 卷 了基于分解的快速算法，将计算复杂度降为了 O 算时间上较文献［ 时间较文献［ ) ，故在计 ］还存在有明显的优势，计算 ］可提高 1 400 倍左右。 ］ 、文献［ 12 11 11 ( L 分割方法层出不穷，迄今也没有一种通用的分割算法是可行 的。本文针对现有的三维 Otsu 算法所存在的不足，提出并设 计了一种既能反映类间距离又能反映类内距离的阈值判别函 数，同时还利用了分解的思想，成功地将三维 Otsu 递推算法 ) ，大大提高了计算的速 的计算复杂度从 O 度，最后通过对多幅图像的实验验证了本文算法的可行性 。 但是对于不同的图像，由于三维 Otsu 方法每一维在图像分割 中所起的作用不同，如何改进阈值判别函数，使得分割的效果 更佳将是笔者继续研究的问题。 L3 ) 降到了 O L ( ( 图 1 rice 图像的分割效果 图 2 闹钟图像的分割效果 图 3 加入高斯噪声的 Cameraman 图像的分割效果 图 4 加入椒盐噪声的轮船图像的分割效果 参考文献: ［1］ SAHOO P K， SOLTANI S， WONG A K C， et al． A survey of thresholding techniques［J］． Computer Vision， Graphics and Image Processing，1988，41( 2) : 233 － 260． ［2］ PAL N R， PAL S K． A review on image segmentation techniques ［J］． Pattern Recognition， 1993， 26( 9) : 1277 － 1294． ［3］ WANG S T， CHUNG F L， XIONG F S． A novel image thresholding method based on Parzen window estimate ［J］． Pattern Recognition， 2008， 41( 1) : 117 － 129． ［4］ 范九伦，赵凤． 基于 Sugeno 补的广义模糊熵阈值分割方法［J］． 电子与信息学报， 2008，30( 8) : 1865 － 1868． ［5］ BAZI Y， BRUZZONE L， MELGANI F． Image thresholding based on the EM algorithm and the generalized Gaussian distribution［J］． Pattern Recognition， 2007， 40( 2) : 619 － 634． ［6］ NAKIB A， OULHADJ H， SIARRY P． Image histogram thresholding based on multiobjective optimization ［J］． Signal Processing， 2007， 87( 11) : 2516 － 2534． ［7］ OTSU N． A threshold selection method from gray-level histograms ［J］． IEEE Transactions on Systems， Man and Cybernetics， 1979， 9 ( 1) : 62 － 66． ［8］ 刘健庄， 栗文青． 灰度图像的二维 Otsu 自动阈值分割法［J］． 自 表 1 各算法的时间比较 s 动化学报，1993，19( 1) : 101 － 105． 文献［11］ 算法 文献［12］ 算法 本文算法 ［9］ 岳峰，左旺孟，王宽全． 基于分解的灰度图像二维阈值选取算法 ［J］． 自动化学报，2009， 35( 7) : 1022 － 1027． ［10］ 景晓军，李剑峰，刘郁林． 一种基于三维最大类间方差的图像分 割算法［J］． 电子学报，2003，31( 9) : 1281 － 1285． ［11］ 范九伦，赵凤，张雪峰． 三维 Otsu 阈值分割方法的递推算法［J］． 电子学报，2007，35( 7) : 1398 － 1402． ［12］ 吕燕，龚劬． 加权三维 Otsu 方法在图像分割中的应用［J］． 计算 机应用研究，2011，28( 4) : 1576 － 1579． 图例 rice 图像 闹钟图像 Cameraman 图像 轮船图像 5 结语 25． 274 5 26． 153 8 26． 111 8 26． 026 2 1． 520 1 1． 539 8 1． 542 1 1． 510 1 0． 017 6 0． 017 2 0． 019 2 0． 016 3 面对图像来源千差万别，其直方图具有多样性，导致图像