改进的二维Otsu图像分割方法及其快速实现

第 32 卷第 5 期 电 子 与 信 息 学 报 Vol.32No.5 2010 年 5 月 Journal of Electronics & Information Technology May 2010 改进的二维 Otsu图像分割方法及其快速实现 陈 琪 熊博莅 陆 军 匡纲要 (国防科学技术大学电子科学与工程学院 长沙 410073) 摘 要：通过实验和理论验证 2 维直方图的副对角区域的概率和不一定很小而不能忽略，因而传统 2 维 Otsu 法中 关于主对角区域的概率和近似为 1 的假设不够合理。针对该问题，该文提出了一种改进的 2 维 Otsu 法及其快速实 现。新方法舍弃了不合理的假设，通过单独计算 2 维直方图主对角区域概率的方法，来准确估计主对角区域中目标 和背景的概率，并重新计算 2 维 Otsu。实验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，改进的 2 维 Otsu 法能够获得明显优于传统 2 维 Otsu 法的 分割效果，其快速算法的计算复杂度与传统 2 维 Otsu 法的快速算法相当。 关键词：图像分割；2 维 Otsu 法；阈值；快速递归 中图分类号：TP391 文献标识码：A 文章编号：1009-5896(2010)05-1100-05 DOI: 10.3724/SP.J.1146.2009.00627 Improved Two-Dimensional Otsu Image Segmentation Method and Fast Recursive Realization Chen Qi Xiong Bo-li Lu Jun Kuang Gang-yao (School of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China) Abstract: Traditional 2D Otsu’s method supposes that the sum of probabilities of main- diagonal distinct in 2D histogram is approximately one. This paper’s experiments and theory prove that the sum of probabilities of counter-diagonal distinct in 2D histogram is not always very small and this could not be neglected. Therefore, the assumption mentioned above in 2D Otsu’s method is inadequately reasonable. In this paper, an improved 2D Otsu’s segmentation method and recursive algorithm are proposed. By separately calculates probabilities of objects area and background area in 2D histogram main-diagonal distinct, modified method is acquired. Experimental results show that proposed method can obtain better segmentation effect than the traditional 2D Otsu’s method. The computation complexity of improved 2D Otsu’s method corresponds to traditional 2D Otsu’s method. Key words: Image segmentation; Two-dimensional Otsu’s method; Threshold; Fast recursive 1 引言 图像分割就是把目标从背景中分离出来。由于 二值化阈值分割的速度快，因此在图像分割中占据 了重要地位。常用的二值化阈值分割方法有基于最 大类间方差即 Otsu 的阈值选取[1]，基于最大熵的阈 值选取，模糊 C 均值聚类等。 Otsu 法基于图像的 1 维灰度直方图，以目标和 背景的类间方差最大为阈值选取准则。该法往往只 是针对目标和背景灰度特性区分明显的图像有较好 的效果。在实际应用中，由于噪声等干扰因素的存 在，灰度直方图不一定存在明显的波峰和波谷，此 时仅利用 1 维灰度直方图来确定阈值难以获得满意 的分割效果，甚至产生错误分割。对该问题的一个 改进就是将图像的空间信息引入进来。通过对原图 进行邻域平均得到另一“平滑图像”，由原图像和平 2009-04-28收到，2009-09-28改回 国家自然科学基金(60772045)资助课题 通信作者：陈琪 cq_afeu@163.com 滑图像构造出一个 2 维直方图。由于图像每个像素 点与其邻域像素的相关性是很大的，所以目标和背 景的分布在 2 维直方图中就会比在 1 维直方图中更 容易区分，充分利用图像的灰度信息和空间信息进 行分割会改善图像的分割效果[2]。 刘建庄等[3]提出了基于 2 维灰度直方图的 Otsu 法(以下简称 2 维 Otsu 法)。该方法不仅充分利用了 图像像素点的信息，而且考虑到了像素点与其邻域 的空间相关信息，具有较好的抗噪性。但基于 2 维 直方图的 Otsu 法所带来的计算量也是惊人的，由于 将 1 维搜索空间扩大为 2 维，导致运算量按指数增 长，难以用于实时处理。鉴于此，Jian 等人提出了 2 维 Otsu 法的快速递推算法[4]，大大提高了运算速 度。 如图 1 所示，2 维 Otsu 法通过一个阈值对(s,t) 对 2 维直方图进行分割，划分得到 4 块区域 A，B， C 和 D。该法假设目标区域和背景区域占据了 2 维 直方图的绝大部分区域，即假设目标区域和背景区 域的概率和近似为 1。主对角线上的两个区域 A 和 更多技术文章， 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 请登录www.srvee.com 内容版权归作者所有 第5期 陈 琪等：改进的二维Otsu图像分割方法及其快速实现 1101 C 分别对应于目标和背景，副对角线上的两个区域 B 和 D 对应于边缘和噪声。 在 2 维 Otsu 法中认为区域 B 和 D 的概率值近 似为 0，这种假设只在远离主对角线的部分成立。 图 2 是一幅图像的 2 维直方图分布，当阈值对(s,t) 处于图 2 中位置(即主对角线附近)时，区域 B 的右 下角和区域 D 的左上角均有非零的 2 维直方图分 布，这种情况下 B 和 D 的概率和近似为 0 的假设不 再成立，若仍按这种假设进行分割，会影响分割效 果。为此人们提出了各种后处理以加强分割效果， 对 2 维 Otsu 法做了许多改进，如 2 维直线阈值型 Otsu [5,6]，2 维曲线阈值型 Otsu[5]，2 维斜分阈值型 Otsu[7,8]等。 图 1 2 维直方图区域 图 2 一幅图像的 2 维直方图分布 通过实验发现，2 维 Otsu 法对测试图像的效果 并不好，并且与 1 维 Otsu 的效果一样并没有因为考 虑了图像的空间信息而得到改善。原因如下：实验 验证了 2 维直方图的副对角区域的概率和不一定很 小，不能忽略，因而近似得到的区域 C 概率也不准 确，也就是说按照主对角区域概率和为 1 的假设得 不到最佳阈值。由此本文尝试分别计算主对角区域 A 和 C 的概率，来重新计算 2 维 Otsu，检验是否能 改善分割效果，这也就是本文改进 2 维 Otsu 法的思 路。 2 二维 Otsu 设图像灰度级为1 L− ，2 维直方图任意一点的 值定义为 ijp ，它表示 2 元组( , )i j 发生的频率。假设 图像被阈值对( , )s t 划分为两类 oC 和 bC ，对应的先验 概率 ( , )o s tω 与 ( , )b s tω 分别为 1 1 1 1 ( , ) , ( , ) s t L L o ij b ij i j i s j t s t p s t pω ω = = = + = + = =∑∑ ∑ ∑ (1) 相应的类内均值矢量 om 和 bm 分别为 T T 0 0 1 1 1 1 T ( , ) , ( ( , )/ ( , ), ( , )/ ( , )) s t s t o oi oj ij ij i j i j i o j o m m ip jp m s t s t m s t s t ω ω ω ω = = = = ⎛ ⎞⎟⎜ ⎟⎜= = ⎟⎜ ⎟⎜ ⎟⎝ ⎠ = ∑∑ ∑∑m (2) T T 1 1 1 1 =( , ) = , L L L L b bi bj ij b ij b i s j t i s j t m m ip jpω ω = + = + = + = + ⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠∑ ∑ ∑ ∑m (3) 其中 1 1 ( , ) s t i ij i t m s t ip = = =∑∑ ， 1 1 ( , ) s t j ij i t m s t jp = = =∑∑ 。 2 维直方图的总均值矢量 Tm 为 T T 1 1 1 1 ( , ) , L L L L T Ti Tj ij ij i j i j m m ip jp = = = = ⎛ ⎞⎟⎜ ⎟⎜= = ⎟⎜ ⎟⎜ ⎟⎝ ⎠∑∑ ∑∑m (4) 假设 2 维直方图的副对角区域图像的概率忽略不 计，于是有 1, o b T o o b bω ω ω ω+ ≈ ≈ +m m m (5) 类间方差 Bσ 定义为 T T [( )( ) [( )( ) ] B o o T o T b b T b T ω ω = − − + − − m m m m m m m m σ (6) 使用 Bσ 的迹 tr Bσ 作为类间方差的测度 2 2 2 2 tr [( ) ( ) ] [( ) ( ) ] B o oi Ti oj Tj b bi Ti bj Tj m m m m m m m m ω ω = − + − + − + − σ (7) 将式(5)代入式(7)，有 2 2[ ( , )] [ ( , )] tr [1 ] Ti o i Tj o j B o o m m s t m m s tω ω ω ω − + −≈ −σ (8) 最佳阈值 * *( , )s t 则可由式(9)确定 * * 1 , ( , ) arg max {tr ( , )}Bs t L s t s t ≤ ≤ = σ (9) 每对 ( , )s t 计算两类先验概率和类内均值的计算 复杂度为 2( )O L ，且共有 2L 对( , )s t ，因而计算 2 维 Otsu 的总计算复杂度为 4( )O L ，运算量惊人。Jian 等人提出了 2 维 Otsu 法的快速递推算法[4]，给出了 ( , )o s tω ， ( , )im s t 和 ( , )jm s t 的快速递推公式，计算复 杂度从 4( )O L 减少为 2( )O L 。 按照 2 维 Otsu 法的假设，副对角区域的概率和 很小可以忽略，而从图 3(d)中可以明显看出副对角 区域的概率和并非一个取值很小的曲面。通过进一 步 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，我们发现图 3 (b)2 维直方图的有效范围在 主对角线附近的矩形区域内，并且在 2 维直方图有 效范围以外的取值几乎为 0，这就保证有效范围以 外区域的主对角区域概率和近似为 1。图 3(e)是 2 维直方图的等高线图，其中左下角的虚线矩形框所 围区域即为该图像 2 维直方图的有效范围，而该矩 形分别向横轴、纵轴方向扩展得到两个条带区域， 即图中阴影部分。当阈值对在 2 维直方图有效范围 内且主对角线附近移动时，可保证主对角区域概率 和近似为 1；而当阈值对在远离主对角线且在图 3 (e) 阴影区域内时，依据此时阈值对划分 2 维直方图得 到的主对角区域概率和就不近似为 1 了。 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 1102 电 子 与 信 息 学 报 第 32 卷 图 3 测试图像的 2 维直方图及其主对角区域概率和的分析 这从理论上说明了2维Otsu法中关于主对角区 域概率和近似为 1 的假设的不合理。由此本文尝试 分别计算主对角区域 A 和 C 的概率，并重新计算 2 维 Otsu，检验是否能改善分割效果。 3 改进的二维 Otsu 如图 4 所示，2 维直方图中 4 个区域的概率分 别记为 stPA ， stPB ， stPC 和 stPD 。其中 stPA = ( , )o s tω ， ( , )st bPC s tω= 。 1 1 1 1 , s L L t st ij st ij i j t i s j PB p PD p = = + = + = = =∑ ∑ ∑ ∑ (10) A，B，C，D 4 块依次为顺时针排列，4 块的概率 和等于 1。 实验发现并经理论证明，副对角区域 B 和 D 的 概率和不一定很小，不可忽略，因此主对角区域关 于 1st stPC PA≈ − 的近似假设不够合理。 图 4 2 维直方图区域中四个区域概率的位置关系 因此，下面分别计算对角区域 A 和 C 的概率， 得到改进的 2 维 Otsu。 改进的 2 维 Otsu 法的类间方差的迹为 2 2 2 2 2 2 2 2 tr [( ) ( ) ] [( ) ( ) ] B A oi Ti oj Tj C bi Ti bj Tj ji A Ti Tj A A CjCi C Ti Tj C C P m m m m P m m m m mm P m m P P mm P m m P P = − + − + − + − ⎡ ⎤⎛ ⎞ ⎛ ⎞⎟ ⎟⎢ ⎥⎜ ⎜⎟ ⎟= − + −⎜ ⎜⎢ ⎥⎟ ⎟⎜ ⎜⎟ ⎟⎜ ⎜⎝ ⎠ ⎝ ⎠⎢ ⎥⎣ ⎦ ⎡ ⎤⎛ ⎞ ⎛ ⎞⎟ ⎟⎢ ⎥⎜ ⎜⎟ ⎟+ − + −⎜ ⎜⎢ ⎥⎟ ⎟⎜ ⎜⎟ ⎟⎜ ⎜⎝ ⎠ ⎝ ⎠⎢ ⎥⎣ ⎦ σ (11) 其 中 1 1 ( , ) L L Ci ij i s j t m s t ip = + = + = ∑ ∑ ， ( , )Cjm s t = 1 1 L L ij i s j t jp = + = + ∑ ∑ 。 改进的 2 维 Otsu 法的计算复杂度很大，同 2 维 Otsu 一样为 4( )O L 。为了实际应用的需要，下面 给出对应的快速递推公式。 4 改进的二维 Otsu的快速算法 根据图 4 中各个区域的位置关系，可以得到计 算各个区域概率的快速递推公式。关于 ( , )im s t 和 ( , )jm s t 的快速递推公式见文献[4]，下面不再给出。 为了说明 A 区和 B，C，D 区的联系，下面首 先给出文献[4]中 A 区概率 stPA 的快速递推公式。 1 ( 1)1 1s s sPA PA p−= + (12) 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 第5期 陈 琪等：改进的二维Otsu图像分割方法及其快速实现 1103 1 1 1 1 1 ( 1) 1 ( 1) ( 1) ( 1)( 1) s t s st ij it i j i s s t it st i s t s t s t st PA p p PA p p PA PA PA p − = = = − − = − − − − = + = + + = + − + ∑∑ ∑ ∑ (13) 然后我们仿照 A 区 stPA 递推公式分别从 B，C， D 各区各自顶点出发向内辐射得到 stPB ， stPC ， stPD 的递推公式，并推导了 Cim 和 Cjm 的快速递推公 式。 ,256 0sPB = (14) ( 1) ( 1) ( 1)( 1) ( 1)( 1)+st s t s t s t s tPB PB PB PB p− + − + − += − + (15) 256, 256( 1) 256( 1)t t tPC PC p+ += + (16) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1)( 1) st s t s t s t s t s t s t PC PC PC PC p p p + + + + + + + + = + − + + − (17) 256, 0tPD = (18) ( 1) ( 1) ( 1)( 1) ( 1)( 1)st s t s t s t s tPD PD PD PD p− + + − + −= + − + (19) 256( 1)(256, ) (256, 1) 256Ci Ci tm t m t p += + + ⋅ (20) 1, , 1 1, 1 ( , ) ( 1, ) ( , 1) ( 1, 1) ( 1) ( 1) Ci Ci Ci Ci s t s t s t m s t m s t m s t m s t s p s p s p + + + + = + + + − + + + + ⋅ + ⋅ − + ⋅ (21) 256( 1)(256, ) (256, 1) ( 1)Cj Cj tm t m t t p += + + + ⋅ (22) 1, , 1 1, 1 ( , ) ( 1, ) ( , 1) ( 1, 1) ( 1) ( 1) Cj Cj Cj Cj s t s t s t m s t m s t m s t m s t s p s p s p + + + + = + + + − + + + + ⋅ + ⋅ − + ⋅ (23) 采用快速算法后，每对 ( , )s t 计算两类先验概率 和类内均值分别只需累加几个数，每对 ( , )s t 的计算 复杂度从 2( )O L 减少为 0( )O L ，对于 2L 对( , )s t ，计算 改进的 2 维 Otsu 的总计算复杂度从 4( )O L 减少为 2( )O L 。 5 实验结果及分析 仿真实验是在 VC6.0 环境下，在 AMD 3.6 GHz 微处理器上进行的。实验图像为一幅 SAR 图像，分 别从分割效果与算法效率两方面，比较 1 维 Otsu 法、2 维 Otsu 及其快速算法、本文改进的 2 维 Otsu 及其快速算法。 实验图像为一幅含有河流的 SAR 图像，尺寸为 988×1116。SAR 图像中河流和陆地的灰度分布有较 大差异，对这类图像进行分割的目标是区分河流和 陆地。实验结果如图 5 所示，从分割结果上看，Otsu 法的阈值为 69，2 维 Otsu 法的阈值对为(69,69)，都 没有得到有意义的分割结果即没有将河流从图像中 分离出来。图 5(d)中按照 2 维 Otsu 法中的假设得到 的主对角区域中 C 区的近似概率和图 5(e)中单独计 算主对角区域中 C 区的概率，发现两者差别很大， 再次说明主对角区域关于 1st stPC PA≈ − 的近似假 设不够合理。由图 5(f)可以明显看出，本文改进的 2 维 Otsu 法采用单独计算主对角区域概率后得到的 阈值对为(73,24)，将河流从图像中分离出来，取得 了较好的分割结果。对图 5(f)的结果可以进一步通 过形态学处理取得更好的效果。 对比表 1 中计算时间可知，使用快速算法后， 将花费时间从多于 3 h 减少到只需几秒，改进的 2 图 5 测试图像的几种方法的分割结果 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 1104 电 子 与 信 息 学 报 第 32 卷 表 1 几种方法的计算时间比较 方法 Otsu 2 维 Otsu 2 维 Otsu 的 快速算法 改进的 2 维 Otsu 改进的 2 维 Otsu 的 快速算法 时间 0.5 s >3 h 8 s >3 h 9 s 维 Otsu 的快速算法的花费时间和 2 维 Otsu 的快速 算法的时间相当。 6 结论 针对传统2维Otsu法中目标区域和背景区域的 概率和近似为 1 的假设不够合理的缺陷，本文提出 了一种改进的 2 维 Otsu 法，新方法通过单独计算 2 维直方图中 A 区和 C 区的概率，丢弃了不合理的假 设。为提高计算效率，本文还给出了改进方法的快 速递推算法，计算复杂度由从 4( )O L 减少为 2( )O L 。 实验表明，本文提出方法与 2 维 Otsu 法相比，在保 持计算复杂度相当的同时，分割效果有了较大的改 善。 参 考 文 献 [1] Otsu N. A threshold selection method from gray level histogram[J]. IEEE Transactions on System, Man and Cybernetics, 1979, 9(1): 62-66. [2] 李弼程，柳葆芳. 基于二维直方图的模糊门限分割方法[J]. 数 据采集与处理，2000, 15(3): 324-329. Li Bi-cheng and Liu Bao-fang. Fuzzy thresholding of segmentation based on two-dimensional histogram[J]. Journal of Data Acquisition & Processing, 2000, 15(3): 324-329. [3] 刘建庄, 粟文青. 灰度图像的二维 Otsu 自动阈值分割法[J]. 自动化学报，1993, 19(1): 101-105. Liu Jian-zhuang and Li Wen-qing. Automatic thresholding of gray-level pictures using two-dimension Otsu method[J]. Acta Automatica Sinica, 1993, 19(1): 101-105. [4] Gong Jian, Li Li-yuan, and Chen Wei-nan. Fast recursive algorithm for two-dimensional thresholding[J]. Pattern Recognition, 1998, 31(3): 295-300. [5] 范九伦，赵凤. 灰度图像的二维 Otsu 曲线阈值分割法[J]. 电 子学报，2007, 35(4): 751-755. Fan Jiu-lun and Zhao Feng. Two-dimensional Otsu’s curve thresholding segmentation method for gray-Level images[J]. Acta Electronica Sinica, 2007, 35(4): 751-755. [6] 郝颖明，朱枫. 2 维 Otsu 自适应阈值的快速算法[J]. 中国图象 图形学报，2005, 10(4): 484-488. Hao Ying-ming and Zhu Feng. Fast algorithm for two-dimensional Otsu adaptive threshold algorithm[J]. Journal of Image and Graphics, 2005, 10(4): 484-488. [7] 吴一全，潘喆，吴文怡. 二维直方图区域斜分阈值分割及快速 递推算法[J]. 通信学报，2008, 29(4): 77-84. Wu Yi-quan, Pan Zhe, and Wu Wen-yi. Image thresholding based on two-dimensional histogram oblique segmentation and its fast recurring algorithm[J]. Journal on Communications, 2008, 29(4): 77-84. [8] 吴一全，潘喆，吴文怡. 二维直方图斜分 Tsallis-Havrda- Charvát 熵图像阈值分割[J]. 光电工程， 2008, 35(7): 53-58. Wu Yi-quan, Pan Zhe, and Wu Wen-yi. Tsallis–Havrda– Charvát entropy image thresholding based on two-dimensional histogram oblique segmentation[J]. Opto- Electronic Engineering, 2008, 35(7): 53-58. 陈 琪： 男，1981年生，博士生，研究方向为SAR图像处理. 熊博莅： 男，1981年生，博士生，研究方向为SAR图像处理. 陆 军： 男，1970年生，副教授，研究方向为雷达信号处理. 匡纲要： 男，1966年生，教授，博士生导师，研究方向为雷达信 号处理、SAR 图像判读、多光谱图像目标识别、雷达目 标特性分析等. 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有