09月22日, 2014 186次
摘要：Otsu算法，也被称之为最大类间方差算法，是实现阈值分割的经典算法之一。二维Otsu算法是一维Otsu算法的推广，它充分考虑了图像的灰度信息和空间邻域信息，可以有效滤除噪声影响，但是同样存在着运算量大、时效性差的问题。对此提出了一种改进的二维Otsu快速阈值分割算法，先将二维Otsu算法分解为两个一维Otsu算法，并集成类间和类内方差信息构造了一种新的阈值判别函数，同时通过降维，进一步降低计算量。实验结果表明，该算法在时间效率与分割效果两方面明显优于传统的二维Otsu算法与快速二维Otsu算法。
中文引用格式：徐超，黄风华，毛政元. 一种改进的二维Otsu阈值分割算法[J].电子技术应用，2016，42(12)：108-111.
英文引用格式：Xu Chao，Huang Fenghua，Mao Zhengyuan. An improved two-dimensional Otsu thresholding segmentation method[J].Application of Electronic Technique，2016，42(12)：108-111.
0 引言
图像分割是将图像划分为一组子区，使得每个子区的内部都具有某种同质性、而任意两个相邻的子区间则不具备此种同质性的过程。它是涉及计算机视觉、图像分析和模式识别等领域的重要研究内容[1]，历经数十年的发展，各类文献中提出的图像分割方法已经形成了复杂的谱系[2-3]，阈值分割法是其中的一个分支，因其实现简单、执行效率高而被广泛运用。日本学者OTSU N于1978年提出的Otsu算法被称之为最大类间方差法[4]，是目前阈值分割法的主流算法之一，分割效果良好[5]。但传统的一维Otsu法仅仅考虑了图像的灰度信息，而未充分考虑图像的空间信息，因此当图像直方图没有出现明显的双峰时，利用该方法进行分割会出现信息丢失现象。
为此，刘健庄等人提出了二维Otsu法，利用图像灰度值和邻域平均灰度值作为两个维度进行阈值分割，使其抗噪性得到了提升，但是同样提高了计算的复杂度[6]；在此基础上，Gong Jian等人提出了二维Otsu的快速分割算法，将原算法时间复杂度从O(L4)降低到O(L2)[7]；范九伦等人提出二维Otsu曲线算法，将阈值范围限制在主对角线与次对角线之间，有效地降低了算法的时间复杂度[8]；汪海洋等人提出了改进的二维Otsu阈值分割算法，通过递归的方式创建查找表，减少大量冗余的计算过程，降低计算量[9]；Wu Chengmao等人通过求取多元函数极值的方法构建迭代算法，降低了时间开销和存储空间开销[10]；江禹生等人利用遗传算法来快速获取二维Otsu阈值算法的近似最优阈值，唐英干等人则利用粒子群算法来优化二维Otsu法的分割阈值，但是这种优化算法容易过早地收敛而陷入到局部最优的结果中，并且算法的代码量过大[11-12]。
为了进一步降低二维Otsu阈值分割算法的计算量同时提高其分割效果，本文利用分解的思想，将二维Otsu最佳阈值(s，t)分解为两个一维Otsu最佳阈值s和t。同时，在获取一维Otsu最佳阈值过程中，引入了类内方差概念，并提出一种改进的最佳阈值判别函数，从而得到最佳阈值s和t。
1 二维Otsu阈值分割算法
传统的二维Otsu算法主要是利用图像邻域中心灰度值与其邻域均值构成的二维直方图来进行分割，因此具有良好的抗噪性，其原理如下：
设一幅图像f(x，y)的大小为M×M，其灰度级为L(0，1，2，…，L-1)，它的邻域均值图像g(x，y)(以3×3邻域均值作为该像素灰度值)灰度级也为L(0，1，2，…，L-1)，由此形成一个二元组：像素的灰度值i和其邻域灰度均值j。设灰度值为i且邻域灰度均值为j的像素数为fij，图像像素总数为N，则对应的联合概率密度pij可定义为：
假设给定一个门限向量(s，t)，s为灰度阈值，t为邻域灰度均值阈值，可以将图1所示的正方形分割为I、II、III、IV 4个区域。由于图像目标或者背景内部像素点之间的相关性很强，像素点的灰度值和其邻域灰度均值十分接近；而在目标和背景边缘处或者噪声部分，它的灰度值与其邻域灰度均值差异明显。因此，图1中I代表的是背景部分，III代表的是目标部分，II和IV分别代表边缘和噪声部分。假设图像目标和背景分别用C0和C1表示，则它们出现的概率分别为：
大多数情况下，远离对角线的概率较小，即边缘点和噪声点的概率很小，可忽略不计。因此可以假设：w0+w1=1；uT=w0u0+w1u1。
定义图像类间离散度矩阵为：
最佳阈值为tr(Sb)取得最大时的(s，t)。
2 改进的快速二维Otsu算法
为了降低二维Otsu算法复杂度以及提高分割效果，本文提出一种改进的快速二维Otsu算法。该算法将传统的二维Otsu算法分解为两个一维Otsu算法，即原图像f(x，y)获取一个阈值s，它的邻域均值图像g(x，y)获取一个阈值t。从计算机的角度上看，分别求解两个阈值以代替原来二维Otsu算法的阈值，这种方法不但降低了算法时间复杂度，而且降低了计算机的存储空间。另外，传统的二维Otsu算法以及一些改进的二维Otsu算法的阈值判别函数只考虑目标与背景之间的方差大小，即类间方差越大，分割效果越好。然而，这些算法并未考虑目标或背景内的内聚性，即目标类和背景类内部像素具有较强的相关性。因此，本文综合考虑类间方差和类内方差的概念，提出一个新的阈值判别函数。
定义1 设阈值s将一组离散的数据分成了两类，定义其类间方差为：
式中，u0、u1分别代表目标类和背景类的均值，w0、w1分别代表目标类和背景类的概率。因此，sp值越大，即类间方差越大，目标类和背景类区分就越明显，分割效果越好。
定义2 设阈值s将一组离散的数据分成了两类，pi表示i出现的概率，u0、u1分别表示两类的均值，w0、w1分别表示两类的概率，则这组数据两类的类内方差分别表示：
显然，sw表示这组数据两类类内的内聚性，其值越小，分割效果越好。
为了进一步考虑类间方差和类内方差这两个因素，即类间方差越大，类内方差越小，所得到的分割效果越好。因此，本文提出一个新的判别函数，即类间类内方差比值法：
S=sp/sw (13)
则最优阈值满足S*=argmax{S}，其对应的灰度值则为最佳阈值。类似可求得邻域均值图像g(x，y)的最佳阈值t，该方法避免了在L×L维进行穷举遍历，只需要在两个长度为L的空间内寻找最佳阈值即可，从而降低了计算量，减少计算机所需存储空间。算法步骤如下：
(1)初始阈值范围计算
由于图像目标灰度必然高于大量背景的均值，因此将初始阈值的下限设定为图像灰度均值m，实验也证实了该结论。另外由于图像目标灰度必然不高于图像最大灰度值，因此将初始阈值的上限设定为图像最大灰度值n。
(2)最佳阈值求取
为了进一步降低运算时间，本文将二维图像灰度矩阵转换为一维矩阵(1，L)，并根据式(9)、式(12)分别求取图像类间方差sp、类内方差sw，进而根据式(13)得到最佳阈值s，同样可以求得邻域均值图像g(x，y)的最佳阈值t。
(3)分割图像
利用上一步得到的阈值(s，t)分割图像，并将其二值化。
3 实验结果
为了验证本文算法的可行性和有效性，将它与传统二维Otsu算法、快速二维Otsu算法进行比较。实验环境为：Win8.1专业版，IntelCore(TM) i5-3570 CPU @ 3.40 GHz，RAM 4.00 GB，MATLAB R2012b。
在实际应用环境中，获取到的图像背景一般较为复杂并且信噪比较低。为了验证本文算法的分割效果，以rice图像、lena图像、学生合照作为样本数据，选择目前阈值法中效果较好的传统二维Otsu算法、快速二维Otsu算法与本文算法进行实验对比，结果如图2～图4所示。表1为本文算法与传统二维Otsu法、快速二维Otsu法针对各样本数据的运算时间。
上述实验所用的lena图像大小为512×512，rice图像大小为256×256,学生合照大小为768×1 024。从表1可知，在上述实验环境下，本文算法时间复杂度远低于文献[6]和文献[9]的算法，处理时间大为降低。就分割效果而言，本文综合考虑类间方差和类内方差(即类间的离散测度信息和类内的内聚性)得到的分割结果抗噪性和目标内聚性均优于传统二维Otsu算法与快速二维Otsu算法。图2(d)的上半部分没有出现图2(b)与图2(c)中的细微噪声颗粒，而下半部分米粒的完整性也更好；图3(d)中分割出来的头发和柱子内部更具饱和性；图4(d)中汉字和学生眼睛、鼻子、嘴巴等目标更能清晰地识别出来。
4 结论
为了进一步降低二维Otsu算法复杂度、提高分割质量，本文提出了改进的二维Otsu算法。根据本文算法与其他同类算法处理相同样本图像的实验结果表明，本文提出的算法在分割效果和算法复杂度两个方面都具有明显提高。另外，将本文的算法思想扩展到三维甚至高维Otsu算法时，算法复杂度不会明显提高。如何集成Otsu与其他同类算法得到更佳的分割效果，是后续研究要解决的问题。
参考文献
[1] 冈萨雷斯.数字图像处理[M].第三版.北京：电子工业出版社，2011.
[2] BHARGAVI K，JYOTHI S.A survey on threshold based segmentation technique in image processing[J].International Journal of Innovative Research and Development，2014，3(12)：234-238.
[3] TANEJA A，RANJAN P，UJJLAYAN A.A performance study of image segmentation techniques[C].Reliability，Infocom Technologies and Optimization(ICRITO)(Trends and Future Directions)，2015 4th International Conference on.IEEE，2015：1-6.
[4] OTSU N.A threshold selection method from gray-level histograms[J].Automatica，1975，11(285-296)：23-27.
[5] SEZGIN M.Survey over image thresholding techniques and quantitative performance evaluation[J].Journal of Electronic Imaging，2004，13(1)：146-168.
[6] 刘健庄，栗文青.灰度图像的二维Otsu自动阈值分割法[J].自动化学报，1993，19(1)：101-105.
[7] Gong Jian，Li Liyuan，Chen Weinan.A fast recursive algorithm for two-dimensional thresholding[C].Signal Processing，1996，3rd International Conference on.IEEE，1996，2：1155-1158.
[8] 范九伦，赵凤.灰度图像的二维Otsu曲线阈值分割法[J].电子学报，2007，35(4)：751-755.
[9] 汪海洋，潘德炉，夏德深.二维Otsu自适应阈值选取算法的快速实现[J].自动化学报，2007，33(9)：968-971.
[10] Wu Chengmao，Tian Xiaoping，Tan Tieniu.Fast iterative algorithm for 2D Otsu thresholding method[J].PR&AI，2008，21(6)：746-757.
[11] 江禹生，宋香丽，任晶晶.基于遗传算法的二维Otsu算法改进[J].计算机应用研究，2010，27(3)：1189-1191.
[12] 唐英干，刘冬，关新平.基于粒子群和二维Otsu方法的快速图像分割[J].控制与决策，2007，22(2)：202-205.
作者信息
徐 超1，2，3，黄风华1，4，毛政元1，2，3
1.福州大学 福建省空间信息工程研究中心，福建 福州350002；
2.福州大学 空间数据挖掘与信息共享教育部重点实验室，福建 福州350002；
3.福州大学 地理空间信息技术国家地方联合工程研究中心，福建 福州350002；
4.福州大学 阳光学院，福建 福州350015；
