二维Otsu法的降维递推综合改进算法

张智丰，关 坤，金文标，刘庆民

(1.杭州电子科技大学理学院，浙江 杭州310018;2.杭州电子科技大学机械工程学院，浙江 杭州310018)

0 引 言

图像分割就是从一幅图像里面提取我们感兴趣的事物信息，是图像处理和机器视觉的基本问题之一[1]。根据不同图像分割算法的主要特征，大致可以把图像分割算法分为边缘检测、阈值分割[2-3]和区域分割3类。基于阈值分割算法的关键是阈值的选定，大津(Otsu)法(即最大类间方差法)是其中一种经典、成熟的算法[4]。算法利用图像的灰度直方图，计算对应于图像灰度最大类间方差的灰度级，以此作为分割算法的最佳阈值。Otsu法的自适应能力使其对于图像对比度与亮度变化不敏感，因而在一些实时图像处理系统中得到了广泛的应用。同时，Otsu法是在判决分析最小二乘法原理的基础上推导得出的，使得选取的阈值在不同分类之间的分离性最好，是一种具有客观评价标准的图像分割优化方法。文献[5]提出了二维的Otsu法，将原算法中一维的灰度直方图推广到原始像素和邻域平均像素的二维联合灰度直方图，分割的效果以及抗噪能力有了显著的提高。但算法的时间复杂度由一维Otsu法的O(L2)变为O(L4)，选取的统计区域也不够合理。在文献[5]的基础上，文献[6-7]提出了递推改进算法，算法复杂度降低到O(L2);文献[8]则改进了选取统计区域不合理的缺点。但两者都仅仅改善了文献[5]方法中两大缺点的一个，还有待改进之处。本文通过对原始二维Otsu法两个缺点内在关系的分析研究，结合文献[6-8]的算法优点，提出了一种降维递推综合改进算法，可使算法时间复杂度降为O(L2)，并且统计区域选择更为合理。

1 二维Otsu 及其递推、降维改进算法

1.1 二维Otsu 阈值选择法

设图像的灰度级为L，像素点总数为N，对每个像素点计算其像素值i 及邻域平均值j，由此形成二元组(i，j)，统计二元组(i，j)出现的概率pij。设阈值点为(s，t)，则可把像素点分两类:

1)背景类C0:灰度值在 {(i，j)|i≤s，j≤t}内的像素点;

2)目标类C1:灰度值在 {(i，j)|i ＞s，j ＞t}内的像素点。

背景类C0的类内概率和均值如下[9-10]:

同理可计算目标类C1的类内概率w1、均值u1和总像素点均值uT。

则两类的类间方差(也有学者称之为离散度测度)为:

使得S 最大的(s'，t')即为最佳阈值。

1.2 二维Otsu的递推改进算法

传统二维Otsu法在计算类间方差S时，对任意阈值(s，t)，均要从(0，0)逐步累加至(s，t)，使得大量冗余计算存在。为减少这种冗余计算，降低时间复杂度，文献[6-7]提出了一种快速递推改进算法，对式(3)中提到的6个变量(w0、w1、u0i、u0j、u1i、u1j)进行递推处理，下面给出两个递推公式，其余4个完全类似:

1.3 二维Otsu的降维改进

二维Otsu法中，假设左上和右下两类区域没有像素点分布，这是不确切的，而如果将所有点都计算在内，计算量又很大。对此，文献[8]提出了降维算法，作了两方面的改进。

图1 二维Otsu 降维算法的区域划分方式

1)在原始二维Otsu算法中，需要对每个(s，t)计算类间方差，然后取类间方差最大时的(s，t)为分割阈值，本降维算法中仅需依次遍历s+t 寻找最大类间方差，阈值形式由二维(s，t)降低为一维s+t，从而时间复杂度由O(L4)降到O(L3)。

2)区域划分由原来的过(s，t)划分的4 区域转换为以通过点(s，t)且与对角线垂直的直线、f =g-N和f =g+N来进行分割，直线f=s+t-g 左下方区域的点对应于C0，右上方区域的点对应于C1，其C0和C1表示背景类和目标类，如图1所示。图1中，f表示像素自身的灰度值，g表示像素的邻域平均灰度，仅将图中阴影部分参与运算，而将其余部分忽略不计，当N 取适当值时，即可以将大部分概率不为零的点包括进来。

2 二维Otsu法的降维递推综合改进算法

由本文第1 节容易看出，无论原始二维Otsu法，还是其递推、降维改进算法，都存在明显的缺陷。原始二维Otsu法时间复杂度较高的同时统计区域的选择也不尽合理;递推算法虽然时间复杂度有明显降低，但是区域选择仍与原始法相同;而降维改进虽然改进了区域选择，但还有较多的冗余计算。

基于以上分析，本文对降维算法进行递归改进，提出降维递推综合改进算法。算法主要做了如下改进:1)采用一维阈值s+t 取代二维阈值(s，t)，使得之后的类划分标准产生变化，区域选择更加合理。由阈值左下和右上的两区域改为对角线两侧的带型区域，时间复杂度由O(L4)降为了O(L3);2)对任意阈值s+t，计算类内概率和均值时，前述算法均要从0 逐步累加至s+t，而本文算法利用了阈值点间的递推关系，阈值点s+t的概率和均值可由s+t-1 处的计算结果递推得到，使得算法时间复杂度进一步降为O(L2)。改进算法框图如图2所示。

图2 二维Otsu 综合改进算法框图

二维Otsu法中，假定二维点(s，t)的左下方块区域和右上方块区域分别为C0类和C1类，对每个(s，t)(s，t =0...L-1)计算两类间的类间方差，然后取类间方差最大时的(s，t)为分割阈值，这必然导致靠近(s，t)的左上和右下点都未考虑，根据像素值同邻域像素值相近的特点我们可知对角线两侧的点为较大概率出现的点，故需重点考虑，而远离对角区域的点可以不予考虑从而降低运算时间，据此，本文选择考虑区域同降维算法中考虑的区域，而阈值形式的选择上也由二维(s，t)降低为一维s+t[8]，从而将算法的时间复杂度由O(L4)降到O(L3)。

通过降维改进使得区域选择更加合理，但是时间复杂度为O(L3)，仍然较高。分析其中的冗余计算:在计算矩阵的迹S时，对任意阈值s+t，仍要从0 逐步累加至s+t，计算复杂度仍然较高。针对此问题本文提出了一种降维基础上的递推改进算法，对式(3)提到的6个变量进行递推处理:

上述递推式中num 取值范围均为{0，1，…，2L-2}，若存在pij，wi，uij中的系数溢出(指小于0 或大于2L-2)，则取0，从而仅需做如下初始化p(L-1)L=pL(L-1)=0，w0(-1)=0，w1(2L-1)=0，u0i(-1)=0，u0j(-1)=0，u1i(2L-1)=0，u1j(2L-1)=0。

根据上述递推公式，每次计算类间方差S(num)时，都只需要分别利用前面得到的w0(num-1)，w1(num+1)，u0i(num-1)，u1i(num+1)和u0j(num-1)，u1j(num+1)。

另外，本综合改进算法在计算类间方差时，考虑到s和t 分别代表本身像素值和邻域像素值，其权重可能不同，故增加权重系数pro，对式(3)改进如下:

在原始降维算法中，由于是遍历阈值所有情况的同时更新最小类间方差，故2个类内概率和4个类内均值只需分别用1 浮点数变量存储即可，而本改进算法使用递推公式需要保存阈值各情况数据，故需要开辟6个数组空间存储，故增加了运行内存，这是本改进算法需付出的代价。

综上，本算法进行了改善区域选择、降低时间复杂度、考虑阈值权重等方面的改进，以空间复杂度换取时间复杂度，既提高了算法效率，又改进了所选阈值。

3 算法结果展示与分析

3.1 算法时间复杂度分析

本文算法只需对s+t 进行2L次遍历，且计算s+t时使用s+t-1的结果，故时间复杂度降低为O(L2)，在减少大量统计区域的降维算法基础上进一步降低了时间复杂度，各算法复杂度如表1所示。

表1 4种算法的时间复杂度

3.2 实验结果

测试实验的软件环境是VS2008，硬件条件如下:处理器为Intel(R)Core(TM)2 Duo CPU E7500 @2.93 GHz，内存为2.00 GB，显卡为NVIDIA GeForce G100。实验运行时间如表2所示，效果图如图3、图4所示。

表2 4种分割方式的计算时间 s

图3 Lena 灰度图实验效果图

图4 Rice 灰度图实验效果图

通过遍历pro的21种取值(0，0.1，0.2，…，1.9，2)，得到pro 取1.4时效果较好，故文中选取pro =1.4的结果。本文算法和递推算法时间复杂度都是O(L2)，但运行时间却降低较大，主要原因有两点:1)统计区域由全部像素值改进为对角线两侧的带型区域，减少计算约70%;2)递推算法在计算(s，t)时需要阈值为(s，t-1)(s-1，t)(s-1，t-1)时的计算结果，而本文算法计算s+t时只需s+t-1的结果，乘除运算减少数倍。从分割效果看，二维Otsu法及其递推改进算法虽然也得到了较完整的目标，但对一些弱边缘区域分割较差且参杂少量噪声点。降维算法的分割效果较好地改进了上述缺点，但是计算时间却是递推算法的十倍以上。本文提出的算法既保证降维算法分割效果，又很好地降低了运行时间。从分割效果和算法效率两方面来评价二维Otsu法、递推改进、降维改进和二维Otsu的降维递推综合改进算法，可以看出本文算法具有较大的实用价值。

4 结束语

本文在二维Otsu 降维算法的基础上进行递推改进，得到基于Otsu的降维递推综合改进算法，在保证分割效果不变的同时，算法时间复杂度由降维算法的O(L3)降低为O(L2)，实验结果表明本算法在保证良好分割效果的同时缩短运算时间数十倍，具有较好的工业应用价值。通过查阅文献可知Otsu算法同其它算法结合[11]以及三维Otsu算法[12]的研究还具有很好的发展空间[13]，下一步将对此方向深入研究探讨。

[1]许录平.数字图像处理[M].北京:科学出版社，2007:10.

[2]Yilmaz A，Javed O，Shah M.Object tracking:A survey[J].Acm computing surveys (CSUR)，2006，38(4):13.

[3]Yang W Z，Li D L，Zhu L，et al.A new approach for image processing in foreign fiber detection[J].Computers and Electronics in Agriculture，2009，68(1):68-77.

[4]Otsu N.A threshold seletion method from gray-level histograms[J].IEEE Transactions on Systems.Man and Cybernetics，1979，9(1):62-66.

[5]刘健庄，栗文清.灰度图像的二维Otsu 自动阈值分割法[J].自动化学报，1993，19(l):101-105.

[6]汪海洋，潘德炉，夏德深.二维Otsu 自适应阈值选取算法的快速实现[J].自动化学报，2007，33(9):968-971.

[7]徐长新，彭国华.二维Otsu 阈值法的快速算法[J].计算机应用，2012，32(5):1 258-1 260.

[8]马胜前，张光南，杨金龙，等.基于二维直方图的Otsu 图像分割算法改进[J].西北师范大学学报(自然科学版)，2009，45(1):57-61.

[9]龙建武.基于Otsu的图像阈值分割算法的研究[D].吉林:吉林大学，2011.

[10]王菡.基于中值的Otsu算法在图像处理中的研究与应用[D].吉林:吉林大学，2013.

[11]梁光明，孙即祥，马琦，等.Otsu算法在Canny 算子中的应用[J].国防科技大学学报，2003，25(5):36-39.

[12]龚劬，倪麟，唐萍峰，等.基于分解的三维Otsu 图像分割快速算法[J].计算机应用，2012，32(6):1526-1528.

[13]Shao G F，Yang F，Zhang Q，et al.Using the Maximum Between-Class Variance for Automatic Gridding of cDNA Microarray Images[J].Computational Biology and Bioinformatics，IEEE/ACM Transactions on，2013，10(1):181-192.