打印本文 
关闭窗口 【摘要】 传统的二维Otsu阈值分割算法采用穷举搜索法搜寻最佳阈值向量。与此不同，本文提出了一种二维最大类间方差阈值分割的快速迭代算法，用迭代的思想解决原始二维Otsu方法计算复杂、实时性差的问题。文中导出了迭代算法的公式，给出了算法流程。实验结果表明，与二维Otsu原始算法及其他两种快速算法相比较，本文提出的二维Otsu快速迭代算法分割结果准确，实现简单，其运行时间仅为原始算法的0.4%左右，大大减少了计算量和存储空间，是一种快速有效且实时性好的图像阈值分割算法。
【关键词】 图像分割； 二维最大类间方差； Otsu阈值； 快速迭代考试大http:/
A fast iterative algorithm for image segmentation based on 2D
maximum betweencluster varianceWU Yiquan, WU Wenyi, PAN Zhe
（College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics,Jiangsu Nanjing 210016, China）
Abstract: The traditional twodimensional (2D) Otsu threshold algorithms for image segmentation always use exhaustive searching method for the best thresholds. In this paper, a fast iterative algorithm based on 2D maximum betweencluster variance is proposed in order to improve the performance and efficiency of the original 2D Otsu threshold algorithms. The iterative formula is deduced and the algorithm flow chart is given in the paper. Experimental results show that the proposed algorithm has a good segmentation result compared to the original 2D Otsu algorithm and the other two fast methods. It can well reduce the storage space and the running time which is only 0.4% of that of the original method. Therefore, it is a fast and effective image segmentation algorithm with a good realtime quality.
Key words: image segmentation; 2D maximum betweencluster variance; Otsu threshold; fast iterative
引言来源：考试大
图像分割是图像处理和前期视觉中的基本技术，也是大多数图像分析及视觉系统的重要组成部分，分割质量直接影响着后续处理的结果。阈值分割是普遍使用的最为有效的图像分割方法，它实质上归结为阈值的选取。针对这一问题国内外学者进行了大量的研究，提出了多种阈值选取方法［1,2］。在诸多阈值选取方法中，由Otsu（即大津展之）于1978年提出的一维最大类间方差法，以其分割效果较好、适用范围较广、简单有效而引起人们普遍关注，且应用最为广泛。该方法基于类别可分离性，根据图像的一维灰度直方图，用穷举搜索法选取一个阈值使得类间方差最大。1984年Reddi等［3］针对Otsu的方法，不采用原始的穷举搜索法，通过假定一维灰度直方图为连续的概率密度函数，提出了一种快速搜寻迭代法——最陡上升法。这种算法速度非常快，性能好，一般只需6～20次迭代即可收敛到最佳阈值。一维Otsu算法虽然处理速度快，在图像质量较好和背景稳定变化的情况下，可以取得令人满意的效果，但是，由于图像的一维灰度直方图仅反映了图像的灰度分布，并不能反映图像像素之间的空间相关信息，当图像的信噪比较低或受到光照不均匀等因素影响时，该方法的分割效果就不太令人满意，甚至产生分割错误。
为此，1993年刘建庄［4］借助Abutaleb等［5］的二维直方图的思想，利用像素的灰度级分布和邻域的平均灰度级分布所构成的直方图来进行阈值分割。由于二维灰度直方图同时考虑了图像的灰度级信息和空间邻域信息，因此二维最大类间方差阈值分割方法的分割效果比相应的一维方法有明显改善。但同时由于将一维搜索空间扩大到二维，加上变成二维算法后本身的复杂性，导致运算量按指数增加，运行时间长，所需存储空间大，实时性较差，从而限制了二维最大类间方差阈值分割方法的适用范围。
为了降低计算量，1998年龚坚等［6］从减少重复计算的观点出发，提出二维Otsu的一种快速递推算法［7］。2005年郝颖明等［8］在改变二维直方图区域划分的基础上，提出通过将二维阈值转换成一维阈值的快速算法。这两种快速算法都能不同程度地节省计算时间，提高运行速度，但搜寻最佳阈值实质上仍然采用的是穷举搜索法。与此不同，本文将Reddi的一维最大类间方差阈值分割的快速迭代法推广到二维，提出了一种二维最大类间方差阈值选取的快速迭代算法，用迭代的思想解决了原始二维方法计算复杂、实时性差的问题。文中导出了二维最大类间方差阈值分割迭代算法的公式，给出了分割结果和运行时间，并与二维Otsu原始算法及其他两种快速算法的运行时间进行了比较。
1 二维直方图
设图像的尺寸为M×N，图像灰度级取为0,1,…,L－1。如果用集合Z表示这L个灰度级，则Z={z0|z0∈(0,L－1)}。显然，图像中坐标(m,n)的像素点的灰度级f(m,n)为集合中的某一值，即f(m,n)∈Z。定义坐标(m,n)的像素点的邻域平均灰度级g(m,n)如下g(m,n)
=1W×W(W－1)/2i=－(W－1)/2(W－1)/2j=－(W－1)/2f(m+i,n+j)，
(1)这里W为像素点f(m,n)的正方形邻域窗口的宽度，一般取奇数。对于g(m,n)，显然有0≤g(m,n)≤L－1。因此邻域平均灰度级g(m,n)与图像f(m,n)具有同样的灰度变化范围。
对于一幅M×N的图像f(m,n)，当采用［f(m,n),g(m,n)］的向量表示方式时，我们定义并计算其二维直方图。该二维直方图定义在一个L×L大小的正方形区域，其横坐标表示图像像素的灰度级，纵坐标表示像素的邻域平均灰度级。直方图任意一点的值定义为pij，它表示向量(i,j)发生的频率，这里向量(i,j)表示［f(m,n),g(m,n)］，且0≤i,j≤L－1。若用cij表示向量(i,j)发生的频数，那么向量(i,j)发生的频率pij由下式确定pij=cijM×N，(2)其中0≤i,j≤L－1，并且L－1i=0 L－1j=0pij=1。
若以二维向量(t,s)作为阈值来分割图像，t为像素灰度级阈值，s代表邻域平均灰度级阈值，则图像的二维直方图的定义域可被分为四个区域，如图1所示。假设图像的背景灰度级高于目标灰度级，则区域0和区域1中像素的灰度级与邻域平均灰度级基本接近，其分别对应于目标内部和背景内部，而区域2和区域3处像素的灰度级与邻域平均灰度级相差较大，对应目标和背景之间的边界像素和图像的噪声点分布。多数情况下，区域边界附近的像素数与整幅图像的像素数比较，数量很少，因此按照惯例可以假设区域2和区域3上的pij≈0。一般情况下pij≠0的统计值为：0.98～0.95。
2 二维最大类间方差阈值选取的快速迭代算法 由于图像中像素灰度级和邻域平均灰度级二元组共有L2种可能的组合，从而使二维Otsu算法计算复杂度提高，实时性降低。本文提出的方法不采用原始的穷举搜寻法，而是将Reddi的一维最大类间方差阈值分割的快速迭代法推广到二维，即采用一种快速搜寻法来迭代得到可收敛的最佳阈值。假定二维灰度直方图为连续的概率密度函数p(x,y)。现把图像的像素按灰度用阈值t划分成目标类C0和背景类C1，即C0=［0,t］,C1=［t+1,L－1］，若用ω0，ω1分别表示目标类和背景类区域发生的概率分布，则ω0=Pr(C0)=∫t0∫L－10p(x,y)dxdy，(3)
ω1=Pr(C1)=∫L－1t∫L－10p(x,y)dxdy.(4) 考虑到区域2和区域3上p(x,y)≈0，则各区域上概率分布和均值向量都有下列关系：(0区＋2区)≈(0区)≈(0区＋3区),(5)
(1区＋3区)≈(1区)≈(1区＋2区).(6)根据上述关系，式(3)的ω0和式(4)的ω1也可写为ω0≈∫t0∫s0p(x,y)dxdy≈∫L－10∫s0p(x,y)dxdy，(7)
ω1≈∫L－1t∫L－1sp(x,y)dxdy≈∫L－10∫L－1sp(x,y)dxdy.(8) 目标类和背景类相应的均值向量为μ0=(μ0i,μ0j)T
=1ω0∫t0∫L－10xp(x,y)dxdy,
1ω0∫L－10∫s0yp(x,y)dxdyT, (9)
μ1=(μ1i,μ1j)T
=1ω1∫L－1t∫L－10xp(x,y)dxdy,
1ω1∫L－10∫L－1syp(x,y)dxdyT，(10) 这里μ0和μ1分别为(0区＋2区)和(1区＋3区)的均值向量。式(9)中μ0i仍然为(0区＋2区)均值向量的i分量，μ0j则改写为用(0区+3区)均值向量的j分量表达。同理，式(10)中μ1i仍然为(1区＋3区)均值向量的i分量，μ1j则改写为用(1区＋2区)均值向量的j分量表达。
总体均值μZ可表示为μZ=(μZi,μZj)T
=∫L－10∫L－10xp(x,y)dxdy,
∫L－10∫L－10yp(x,y)dxdyT.(11) 在二维直方图的基础上，定义一个目标类和背景类间的离散测度矩阵σb=ω0［(μ0－μZ)(μ0－μZ)T］
+ω1［(μ1－μZ)(μ1－μZ)T］. (12) 在二维最大类间方差法中，采用矩阵σb的迹trσb作为目标类和背景类间的距离测度函数，于是trσb(t,s)=ω0［(μ0i－μZi)2+(μ0j－μZj)2］
+ω1［(μ1i－μZi)2+(μ1j－μZj)2］
=［ω0(μ0i－μZi)2+ω1(μ1i－μZi)2］A
+［ω0(μ0j－μZj)2+ω1(μ1j－μZj)2］B.
13) 上式中等号右边A项中的ω0和ω1分别用式(3)和式(4)代入，μ0i和μ1i分别用式(9)和式(10)的i分量代入；B项中的ω0和ω1分别用式(7)和式(8)代入，μ0j和μ1j分别用式(9)和式(10)的j分量代入，则A项仅含待定参数t，与s无关；而B项仅含待定参数s，与t无关。
选择距离测度函数trσb(t,s)的最大值所对应的阈值向量作为二维最大类间方差法的最佳阈值向量(t*,s*)。为此对式(13)分别求t和s的偏导数并令其为零，即trσb(t,s)t=0，
trσb(t,s)s=0. (14)具体步骤如下，首先求：trσb(t,s)t=［ω0(μ0i－μZi)2+ω1(μ1i－μZi)2+ω0(μ0j－μZj)2+ω1(μ1j－μZj)2］t=0. (15) 前面已说明式(13)等号右边B项中ω0(μ0j－μZj)2和ω1(μ1j－μZj)2均与t无关，故式(15)可写为
trσb(t,s)t=［ω0(μ0i－μZi)2+ω1(μ1i－μZi)2］t=0
［ω0μ20i-2ω0μ0iμZi+ω0μ2Zi+ω1μ21i-2ω1μ1iμZi+ω1μ2Zi］t
=0
［ω0μ20i+ω1μ21i-2μZi(ω0μ0i+ω1μ1i）+μ2Zi］t
=0
［ω0μ20i+ω1μ21i-μ2Zi］t=0.(16)
此时，即可对上式求得t*，即 t*=12(μ0i+μ1i)。
同理，由trσb(t,s)s=0，得到trσb(t,s)s
=［ω0(μ0j－μZj)2+ω1(μ1j－μZj)2］s=0,(17)此时可以求得s*=12(μ0j+μ1j)，即最佳阈值向量(t*,s*)=12(μ0i+μ1i),12(μ0j+μ1j).(18) 由此可采用迭代方式实现，寻找出最优阈值向量(t*,s*)。迭代时，t和s的初始值t0和s0可分别取为图像灰度级均值和邻域平均灰度级的均值，亦可分别取非零灰度区间灰度级的中值和邻域平均灰度级的中值。具体的算法流程框图如图2所示。该方法大大节省了计算时间，降低了计算复杂度，并大幅减少了计算所需要的存储空间。
3 实验结果与分析
针对上述提出的二维最大类间方差阈值分割的快速迭代算法，我们对大量不同类型的灰度图像进行阈值分割，并与采用原始的二维最大类间方差法的分割结果进行比较，发现两种算法所得的分割结果非常接近，分割效果理想，而本文所提出的算法使运行时间大幅度减少。现选取其中的四幅图像，分别为Girl、Baboon、车牌和指纹图像。图3至图6分别为四幅图像的原始灰度级图像(a)、原始二维Otsu法分割后的二值图像(b)及本文提出的快速迭代法分割后的二值图像(c)。它们的最佳分割阈值分别列于表1。二维Otsu原始算法、二维Otsu快速递推算法、文献［8］中的快速算法和本文提出的快速迭代算法在P4 1.60GHz CPU，512M内存条件下的运行时间分别列于表2。表1 利用2种算法对4种图像所得分割阈值表2 图像分割的运行时间 从表1列出的用两种不同方法得到的最佳分割阈值来看，原始二维Otsu阈值算法得到的阈值和本文提出的方法得到的分割阈值十分接近。尽管本文提出的算法是针对二维连续直方图导出的，但同Reddi等针对一维连续直方图导出的一维最大类间方差阈值分割快速迭代法同样的道理，对于二维离散直方图情况，本文提出的算法通常能达到类内误差的最小值或其邻近值，由此保证了二维阈值分割的质量。
从表2的数据可以看出，上述四幅图像的原始二维Otsu算法运行时间都要在80 s左右，而本文提出的二维Otsu快速迭代算法一般迭代8～20次即可收敛到最佳阈值，与二维Otsu原始算法相比，运行时间大大减少，仅为原始算法的0.4%左右，不到二维Otsu快速递推算法运行时间的1/3，约为文献［8］中的快速算法的4%左右。因此这种新的方法可以有效地降低原始二维Otsu算法的计算复杂度，从而提高了图像分割的运行速度，很好地满足了实时应用系统的要求。
4 结论
本文提出了一种二维最大类间方差阈值分割的
快速迭代算法， 这种分割快速算法既保证了图像的分割质量，又提高了原始二维Otsu分割算法的运行效率。通过大量实验可以看出，本文提出的算法分割效果理想，运行速度大大加快，其运行时间仅为二维Otsu原始算法的0.4%左右，不到二维Otsu快速递推算法的1/3，约为文献［8］中的快速算法的4%左右，满足了实际应用系统对阈值分割实时性的要求，是一种行之有效的图像阈值分割算法。
【参考文献】
［1］吴一全,朱兆达.图像处理中阈值选取方法30年(1962—1992)的进展(一) ［J］.数据采集与处理,1993,8 (3):193-200.
［2］吴一全,朱兆达.图像处理中阈值选取方法 30年(1962—1992)的进展(二) ［J］.数据采集与处理,1993,8(4):268-277.
［3］Reddi S S, Rudin S F, Keshavan H R. An Optimal Multiple Threshold Scheme for Image Segmentation ［J］. IEEE Trans Systems, Man, Cybernetics, 1984, 14(4):661-665.
［4］刘健庄,栗文青.灰度图像的二维Otsu自动阈值分割法 ［J］.自动化学报, 1993,19(1):101-105.
［5］Abutaleb A. S. Automatic Thresholding of Graylevel Picture Using Twodimensional Entropies ［J］. Pattern Recognition,1989,47(1):22-32.
［6］Jian Gong, Liyuan Li, Wsinan Chen. Fast Recursive Algorithms for Twodimensional Thresholding ［J］. Pattern Recognition,1998,31(3):295-300.
［7］景晓军,蔡安妮,孙景鳌.一种基于二维最大类间方差的图像分割算法 ［J］.通信学报,2001,22 (4):71-76.
［8］郝颖明,朱枫.2维Otsu自适应阈值的快速算法 ［J］.中国图象图形学报,2005,10(4):484-488.
打印本文 关闭窗口