二维最大类间方差阈值分割的快速迭代算法

二维最大类间方差阈值分割的快速迭代算法 ( ) ?论著 ?文章编号 : 100 7 - 148 2 20 07 0 3 - 0216 - 05 二维最大类间方差阈值分割的快速迭代算法 吴一全 ,吴文怡 ,潘喆 ()南京航空航天大学 信息科学与技术学院 , 江苏省 210016 摘 要 : 传统的二维 O tsu阈值分割算法采用穷举搜索法搜寻最佳阈值向量 。与此不同 ,本文提出 了一种二维最大类间方差阈值分割的快速迭代算法 ,用迭代的思想解决原始二维 O tsu 方法计算复 杂 、实时性差的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。文中导出了迭代算法的公式 ,给出了算法流程 。实验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明 ,与二维 O tsu 原始算法及其他两种快速算法相比较 ,本文提出的二维 O tsu 快速迭代算法分割结果准确 ,实现简 单 ,其运行时间仅为原始算法的 0. 4 %左右 ,大大减少了计算量和存储空间 ,是一种快速有效且实时 性好的图像阈值分割算法 。 关键词 : 图像分割 ; 二维最大类间方差 ; O tsu阈值 ; 快速迭代 中图分类号 : TN911. 73文献标识码 : A A fa st itera t ive a lgor ithm for im a ge segm en ta t ion ba sed on 2D m a x im um be tween 2c lu ster va r ian ce WU Yiquan, WU W enyi, PAN Zhe ( Co llege of Info rm a tion Sc ience and Techno logy, N an jing U n ive rsity of A e ronau tic s and A stronau tic s, )J iangsu N an jing 210016 , Ch ina ( ) A b stra c t: The trad itiona l two2d im en siona l 2D O tsu th re sho ld a lgo rithm s fo r im age segm en ta tion a lways u se exhau stive sea rch ing m e thod fo r the be st th re sho ld s. In th is p ap e r, a fa st ite ra tive a lgo rithm ba sed on 2D m axim um be tween2c lu ste r va riance is p ropo sed in o rde r to imp rove the p e rfo rm ance and effic iency of the o rigina l 2D O tsu th re sho ld a lgo rithm s. The ite ra tive fo rm u la is deduced and the a lgo rithm flow cha rt is given in the p ap e r. Exp e rim en ta l re su lts show tha t the p ropo sed a lgo rithm ha s a good segm en ta tion re su lt comp a red to the o rigina l 2D O tsu a lgo rithm and the o the r two fa st m e thod s. It can we ll reduce the sto rage sp ace and the runn ing tim e wh ich is on ly 0. 4 % of tha t of the o rigina l m e thod. The refo re, it is a fa st and effec tive im age segm en ta tion a lgo rithm w ith a good rea l2tim e qua lity. Key word s: im age segm en ta tion; 2D m axim um be tween2c lu ste r va riance; O tsu th re sho ld; fa st ite ra tive ) (在诸多阈 值 选 取 方 法 中 , 由 O tsu 即 大 津 展 之 于 引言 1978 年提出的一维最大类间方差法 ,以其分割效果 较好 、适用范 围较 广 、简单 有 效 而 引 起 人 们 普 遍 关 图像分割是 图 像 处 理 和 前 期 视 觉 中 的 基 本 技 注 ,且应用最为广泛 。该方法基于类别可分离性 ,根 术 ,也是大多数图像 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 及视觉系统的重要组成部 据图像的一维灰度直方图 ,用穷举搜索法选取一个 分 ,分割质量直接影响着后续处理的结果 。阈值分 [ 3 ] 阈值使 得类 间方 差 最大 。 1984 年 R edd i等 针 对 割是普遍使用的最为有效的图像分割方法 ,它实质 O tsu的方法 ,不采用原始的穷举搜索法 ,通过假定一 上归结为阈值的选取 。针对这一问题国内外学者进 [ 1 , 2 ] 维灰度直方图为连续的概率密度函数 , 提出了一种 行了大 量 的 研 究 , 提 出 了 多 种 阈 值 选 取 方 法 。 收稿日期 : 2007 - 06 - 08 作者简介 : 吴一全 ,男 ,博士 ,副教授 ,研究方向为图像处理与分析 、视频通信 。 E2am il: gump tion_ s@ yahoo. com. cn ( ) W 为像 素 点 f m , n 的正 方 形邻 域窗 口 的宽这里 快速搜寻迭代法 ———最陡上升法 。这种算法速度非 () () 常快 ,性能好 ,一般只需 6,20次迭代即可收敛到最 度 , 一般取奇数 。对于 g m , n , 显然有 0 ?g m , n ()(佳阈值 。一维 O tsu算法虽然处理速度快 ,在图像质 ?L - 1。因此邻域平均灰度级 g m , n 与图像 f m , )量较好和背景稳定变化的情况下 ,可以取得令人满 n 具有同样的灰度变化范围 。 () (意的效果 ,但是 ,由于图像的一维灰度直方图仅反映 对于一幅 M ×N 的图像 f m , n , 当采用 [ f m , ) ( ) 了图像的灰度分布 ,并不能反映图像像素之间的空 n , g m , n ]的向量表示方式时 , 我们定义并计算 间相关信息 ,当图像的信噪比较低或受到光照不均 其二维直方图 。该二维直方图定义在一个 L ×L 大 匀等因素影响时 ,该方法的分割效果就不太令人满 小的正方形区域 , 其横坐标表示图像像素的灰度级 , 意 ,甚至产生分割错误 。 纵坐标表示像素的邻域平均灰度级 。直方图任意一 [ 4 ] [ 5 ] ( ) 为此 , 1993 年刘建庄 借助 A bu ta leb等 的二 点的值定义为 p , 它表示向量 i, j发生的频率 , 这 ij ( ) () () 里向量 i, j表示 [ f m , n , g m , n ], 且 0 ? i, j?L维直方图的思想 ,利用像素的灰度级分布和邻域的 ( ) 平均灰度级分布所构成的直方图来进行阈值分割 。 - 1。若用 c表示向量 i, j发生的频数 , 那么向量ij ( )i, j发生的频率由于二维灰度直方图同时考虑了图像的灰度级信息 p由下式确定 ij 和空间邻域信息 ,因此二维最大类间方差阈值分割 cij ( )p= , 2 ijM ×N 方法的分割效果比相应的一维方法有明显改善 。但 L - 1 L - 1 同时由于将一维搜索空间扩大到二维 ,加上变成二 其中 0 ? i, j?L - 1, 并且= 1。 p ij 6 6 i = 0 j = 0 维算法后本身的复杂性 ,导致运算量按指数增加 ,运 ( ) 若以二维向量 t, s作为阈值来分割图像 , t为 行时间长 ,所需存储空间大 ,实时性较差 ,从而限制 像素灰度级阈值 , s代表邻域平均灰度级阈值 , 则图 了二维最大类间方差阈值分割方法的适用范围 。 [ 6 ] 像的二维直方图的定义域可被分为四个区域 , 如图 为了降低计算量 , 1998 年龚坚等 从减少重复 1所示 。假设图像的背景灰度级高于目标灰度 级 , 计算的观点出发 ,提出二维 O tsu 的一种快速递推算 [ 7 ] [ 8 ] 则区域 0和区域 1中像素的灰度级与邻域平均灰度 法 。 2005年郝颖明等 在改变二维直 方图 区域 级基本接近 , 其分别对应于目标内部和背景内部 , 而 划分的基础上 ,提出通过将二维阈值转换成一维阈 区域 2和区域 3处像素的灰度级与邻域平均灰度级 值的快速算法 。这两种快速算法都能不同程度地节 相差较大 , 对应目标和背景之间的边界像素和图像 省计算时间 ,提高运行速度 ,但搜寻最佳阈值实质上 的噪声点分布 。多数情况下 , 区域边界附近的像素 仍然采用的是穷举搜索法 。与此不同 ,本文将 R edd i 数与整幅图像的像素数比较 , 数量很少 , 因此按照惯 的一维最大类间方差阈值分割的快速迭代法推广到 例可以假设区域 2 和区域 3 上的 p? 0。一般情况 ij二维 ,提出了一种二维最大类间方差阈值选取的快 下p?0的统计值为 : 0. 98 ,0. 95。 ij 速迭代算法 ,用迭代的思想解决了原始二维方法计 算复杂 、实时性差的问题 。文中导出了二维最大类 间方差阈值分割迭代算法的公式 ,给出了分割结果 和运行时间 ,并与二维 O tsu 原始算法及其他两种快 速算法的运行时间进行了比较 。 1 二维直方图 设图像的尺寸为 M ×N , 图像灰度级取为 0, 1, , L - 1。如果用集合 Z 表示这 L 个灰度级 , 则 Z = ( ) ( ) { z| z? 0, L - 1 } 。显然 , 图像中坐标 m , n 的像 0 0 图 1 二维直方图的定义域( ) ( 素点的灰度级 f m , n 为集合中的某一值 , 即 f m , () )n ?Z。定义坐标 m , n 的像素点的邻域平均灰度 ()2 二维最大类间方差阈值选取的快速迭 代级 g m , n 如下 ()g m , n 算法 () () W - 1 / 2 W - 1 / 2 1 () f m + i, n + j, = 6 6 由于图像中像素灰度级和邻域平均灰度级二元 W ×W i = - (W - 1 ) / 2 j = - (W - 1 ) / 22 ( )组共有 L种可能的组合 , 从而使二维 O tsu算法计算1 )μ( ,实时性降低 。本文提出的方法不采用3区 均值 向 量 的 i 分 量 , 则 改 写 为 用 1 区 + 2 复杂度提高 1 j )原始的穷举搜寻法 ,而是将 R edd i的一维最大类间 区 均值向量的 j分量表达。 μ总体均值 可表示为 方差阈值分割的快速迭代法推广到二维 , 即采用一 Z T 种快速搜寻法来迭代得到可收敛的最佳阈值 。假定 μ= (μμ ) , ZZ i Z j ( ) 二维灰度 直 方图 为 连 续 的 概 率 密 度 函 数 p x, y 。 L - 1 L - 1 x p( x, y ) dx dy, = 现把图像的像素 按 灰度 用阈 值 t划分 成目 标 类 C ??000 L - 1 L - 1 T 和背景类 C, 即 C= [ 0, t ], C= [ t + 1, L - 1 ], 若用 1 0 1 ( ) ( )y p x, y dx dy 11 . 0?0? ωω,分别表示目标类和背景类区域发生的概率分 0 1 在二维直方图的基础上 , 定义一个目标类和背 布 , 则 t L - 1 景类间的离散测度矩阵 ( ) ( ) ω( )3 = P r C= p x, y dx dy,0T 0 0?0?σω (μμ ) (μμ ) - ]= [- b 0 0 Z 0 Z L - 1 L - 1T ω μ μ ) (μ μ ) ( [ - - ].( )+12 ( ) ( ( )1 1 Z 1 Z ) ω= P r C= p x, y dx dy.4 1 1t?0?σ在二维最大类间方差法中 , 采用 矩阵 的迹 b ( ) 2 和区域 3 上 p x, y ? 0, 则各区考虑到区域 σ tr 作为目标类和背景类间的距离测度函数 , 于是b 域上概率分布和均值向量都有下列关系 :2 2 σ( ω(μμ)(μμ) )tr t, s = [ - + - ] b 0 0 i Z i 0 j Z j ( ) ( ) ( ) ( )0 区 + 2区 ? 0区 ? 0 区 + 3区 ,5 2 2 ω(μμ)(μμ) +[ - + - ] 1 1 i Z i 1 j Z j ( ) ( ) ( ) ( )1 区 + 3区 ? 1区 ? 1 区 + 2区 .6 2 2 ω(μμ) ω(μμ)( )( )+- ] ωω= [- 根据上述关系 , 式 3 的 和式 4 的 也可写为 1 1 i Z i 0 0 i Z i 0 1 A t s L - 1 s 2 2 ω( ) ( ) ( )7 ? p x, y dx dy ? p x, y dx dy,0 ω(μμ) ω(μμ)+- ]. + [- 0?0? 0?0?1 1 j Z j 0 0 jZ j B L - 1 L - 1 L - 1 L - 1 ω( ) ( ) ? p x, y dx dy? p x, y dx dy.( )1 13 t?s? 0?s? ωω上式中等号右边 A 项中的 和 分别用式 0 1 ( )8 ( )( )μ( )( )μ3 和式 4 代入 ,和 分别用式 9 和式 10 的 0 i1 i 目标类和背景类相应的均值向量为( ) ωωi分量代入; B 项 中 的 和 分 别 用 式 7 和 式 0 1 T (μ μ )μ= , 0( )μ( )( )μ8 代入 ,和 分别用式 9 和式 10 的 j分量代 0 i 0 j 0 j1 j t L - 1 1 入 , 则 A 项仅含待定参数 t, 与 s无关 ; 而 B 项仅含待 ( ) x, y dx dy, x p = ??00ω 0 定参数 s, 与 t无关 。 L - 1 s T 1 σ( ) 选择距离测度函数 tr t, s的最大值所对应b ( ) ( )y p x, y dx dy 9 , ??00ω 0 的阈值向量作为二维最大类间方差法的最佳阈值向T μ(μμ) = ,11 i 1 j 3 3 ( ) ( ) 量 t , s 。为此对式 13 分别求 t和 s的偏导数 L - 1 L - 1 1 ( ) 并令其为零 , 即= x p x, y dx dy, ??t0 ω1 σ( ) 9tr t, s b L - 1 L - 1 T = 0, 1 9t )( ) ( y p x, y dx dy 10 , ??0s( )ω 14 1 ( )σ 9 r t, s t b ( ) ( )μμ这里 和 分别为 0 区 + 2 区 和 1 区 + 3 区 = 0. 0 1 9s ( ) ( ) μ的均值向量 。式 9 中 仍然为 0 区 + 2 区 均值 0 i 具体步骤如下 , 首先求 :μ( )向量的 i分量 ,则改写为用 0区 + 3 区 均值向量 0 j ( ) ( μ 的 j分量表达。 同理 , 式 10 中 仍然 为 1 区 +1 i2 2 2 2 σ( )ω(μμ) ω(μμ) ω(μμ) ω(μμ) 9tr t, s 9[- +- +- +- ] b 0 0 i Z i 1 1 i Z i 0 0 j Z j 1 1 j Z j ( )15 = 0. = 9t 9t = 0 ( ) (μω前面已说明式 13 等号右边 B 项中 - 0 0 j 2 2 2 2 2 ωμ ) μ (ωμ++]ωμωμμ 9[+- 2 0 0 i 1 1 i Z i (μμ) ( )00 i 11 i Z iωμ) 和 - 均与 t无关 , 故式 15 可写为 Z j 1 1 j Z j ] 9t 2 2 σ( ) ω(μμ) ω(μμ) 9tr t, s 9[- +- ] b 0 0 i Z i 1 1 i Z i = = 0 = 0 9t 9t 2 2 2 2 2 2 2 ωμωμμ9[+- ] ωμ ωμ ωμ μ ωμ ωμωμμ ++- 2+]9[- 2 00 i 11 i Z i Z i 0 Z i 1 1 i 1 1 i Z i 1 Z i 00 i 00 i] = 0. ( )16 ] 9t 9t 1 3 行阈值分割 ,并与采用原始的二维最大类间方差法 3 (μμ) 此时 , 即可对上式求得 t , 即 t = +。0 i 1 i 2 的分割结果进行比较 ,发现两种算法所得的分割结 σ( ) 9tr t, s b 果非常接近 ,分割效果理想 ,而本文所提出的算法使 同理 , 由= 0, 得到 9s 运行时间大幅度减少 。现选取其中的四幅图像 ,分 σ( )9tr t, s b 别为 Girl、B aboon、车牌和指纹图像 。图 3 至图 6 分 9s ( ) 别为四幅图像的原始灰度级图像 a 、原始二维 O t2 2 2 ω(μμ) ω(μμ) ( ) 9[- +- ] su法分割后的二值图像 b及本文提出的快速迭代 0 0 j Z j 1 1 j Z j 0, = = 9s ( ) 法分割后的二值图像 c。它们的最佳分割阈值分 别列于表 1。二维 O tsu原始算法 、二维 O tsu 快速递 ( )17 推算法 、文献 [ 8 ]中的快速算法和本文提出的快速 1 3(μ μ ) 此时可以求得 = +, 即最佳阈值向量 s 0 j 1 j 迭代算法在 P4 1. 60 GH z CPU , 512M 内存条件下的 2 运行时间分别列于表 2。3 3 1 1 ( ) (μ . t, s= (μμ ) μ )+, + 0 i 1 i 0 j 1 j 2 2 表 1 利用 2种算法对 4种图像所得分割阈值 ( )18 Girl B aboon 图像 车牌 指纹 由此可采用迭代方式实现 , 寻找出最优阈值向 ( )( )( )( )95 , 72 156 , 112 116 , 101 141 , 121 原始二维 O tsu算法 3 3 本文快速迭代算法 ( )( )( )( )92 , 69 176 , 97 120 , 84 137 , 94 ( ) 量 t , s 。迭代时 , t和 s的初始值 t和 s可分别 0 0 取为图像灰度级均值和邻域平均灰度级的均值 , 亦 表 2 图像分割的运行时间 ( s) 可分别取非零灰度区间灰度级的中值和邻域平均灰 Girl B aboon 图像 车牌 指纹 度级的中值 。具体的算法流程框图如图 2 所示 。该 [ 4 ]80. 251 81. 467 79. 515 79. 587 原始二维 O tsu算法 [ 6, 7 ] 方法大大节省了计算时间 , 降低了计算复杂度 , 并大 二维 O tsu快速递推算法 0. 0863 0. 1069 0. 0799 0. 0916 文献 [ 8 ]中的快速算法 本文幅减少了计算所需要的存储空间 。 0. 6531 0. 6721 0. 5628 0. 6639 提出的快速迭代算法 0. 0188 0. 0346 0. 0209 0. 0215 ( )图 3 Girl 256 ×256 的原始图像和分割后的二值图像 ( )图 4 B aboon 512 ×512 的原始图像和分割后的二值图像 图 2 算法流程框图 3 实验结果与分析 针对上述提出的二维最大类间方差阈值分割的 ( )图 5 车牌 162 ×34 的原始图像和分割后的二值图像 快速迭代算法 ,我们对大量不同类型的灰度图像进 分割质量 ,又提高了原始二维 O tsu 分割算法的运行 效率 。通过大量实验可以看出 ,本文提出的算法分 割效果理想 ,运行速度大大加快 ,其运行时间仅为二 维 O tsu原始算法的 0. 4 %左右 ,不到二维 O tsu 快速 递推算法的 1 /3 ,约为文献 [ 8 ]中的快速算法的 4 % 左右 ,满足了实际应用系统对阈值分割实时性的要 求 ,是一种行之有效的图像阈值分割算法 。( )图 6 指纹 256 ×256的原始图像和分割后的二值图像 从表 1列出的用两种不同方法得到的最佳分割 参考文献 : 阈值来看 ,原始二维 O tsu 阈值算法得到的阈值和本 [ 1 ] 吴一 全 , 朱 兆 达 . 图 像 处 理 中 阈 值 选 取 方 法 30 年 文提出的方法得到的分割阈值十分接近 。尽管本文 ( () ) 1962—1992 的 进 展 一 [ J ]. 数 据 采 集 与 处 理 ,提出的 算 法 是 针 对 二 维 连 续 直 方 图 导 出 的 , 但 同 ( ) 1993 , 8 3: 193 - 200. R edd i等针对一维连续直方图导出的一维最大类间 吴一全 , 朱 兆 达 . 图 像 处 理 中 阈 值 选 取 方 法 30 年[ 2 ] 方差阈值分割快速迭代法同样的道理 ,对于二维离 ( () ) 1962—1992 的 进 展 二 [ J ]. 数 据 采 集 与 处 理 ,散直方图情况 ,本文提出的算法通常能达到类内误 ( ) 1993 , 8 4: 268 - 277. 差的最小值或其邻近值 ,由此保证了二维阈值分割 R edd i S S, R ud in S F, Ke shavan H R. A n Op tim a lM u l2 [ 3 ] 的质量 。 tip le Th re sho ld Schem e fo r Im age Segm en ta tion [ J ]. ( ) 从表 2的数据可以看出 ,上述四幅图像的原始IEEE Tran s System s, M an, Cybe rne tic s, 1984, 14 4 : 661 - 665. 二维 O tsu算法运行时间都要在 80 s左右 ,而本文提 刘健庄 ,栗文青 . 灰度图像的二维 O tsu自动阈值分割 [ 4 ] 出的二维 O tsu 快速迭代算法一般迭代 8 ,20 次即 ( ) 法 [ J ]. 自动化学报 , 1993, 19 1: 101 - 105. 可收敛到最佳阈值 , 与二维 O tsu 原始算法相比 , 运 A bu ta leb A. S. A u tom a tic Th re sho ld ing of Gray2leve l [ 5 ] 行时间大大减少 ,仅为原始算法的 0. 4 %左右 ,不到 P ic tu re U sing Two2d im en siona l En trop ie s [ J ]. Pa tte rn 二维 O tsu快速递推算法运行时间的 1 /3 ,约为文献 ( ) R ecogn ition, 1989 , 47 1 : 22 - 32. [ 8 ]中的快速算法的 4 %左右 。因此这种新的方法 J ian Gong, L iyuan L i, W sinan Chen. Fa st R ecu rsive A l2 [ 6 ] 可以有效地降低原始二维 O tsu 算法的计算复杂度 , go rithm s fo r Two2d im en siona l Th re sho ld ing [ J ]. Pa tte rn 从而提高了图像分割的运行速度 ,很好地满足了实 ( ) R ecogn ition, 1998 , 31 3 : 295 - 300. 时应用系统的要求 。 景晓军 ,蔡安妮 ,孙景鳌 . 一种基于二维最大类间方差 [ 7 ] ( ) 的图像 分 割 算 法 [ J ]. 通 信 学 报 , 2001 , 22 4 : 714 结论 - 76. 郝颖明 ,朱枫 . 2维 O tsu自适应阈值的快速算法 [ J ].[ 8 ] 本文提出了一种二维最大类间方差阈值分割的 ( ) 中国图象图形学报 , 2005, 10 4: 484 - 488. 快 速迭代算法 ,这种分割快速算法既保证了图像的