一种改进的一维Otsu快速算法
郭瑞峰+杨柳+彭光宇+袁超峰
摘 要： 阈值分割是众多图像分割方法中使用最普遍的一种方法，阈值的求解也是图像处理的重心。传统Otsu算法属于穷举式的阈值求解方法，需遍历每个灰度值并计算以其为阈值的类间方差，在此进行了大量不必要的计算，可能无法应用于某些实时性要求较高的环境中。对此提出一种快速的Otsu改进算法，在引入图像复杂度及其相关性质缩小了灰度的搜索范围，同时在搜索范围内使用了一种快速计算方法，较传统Otsu算法进行了二次加速。实验结果证明，该算法较传统Otsu算法提高了计算速度，且两种算法的图像分割结果相同。
关键词： 图像分割； 图像复杂度； Otsu算法； 快速计算
中图分类号： TN911.73?34； TP391.41 文献标识码： A 文章编号： 1004?373X（2017）20?0042?04
Abstract： Threshold segmentation is one of the most commonly used image segmentation methods， and the solution of threshold is also the focus of image processing. The traditional Otsu algorithm is an exhaustive threshold solution method， which needs to traverse each gray value， calculate the interclass variance taking the gray value as the threshold value， and make a large number of unnecessary calculations. As a result， the traditional Otsu algorithm may not be appropriate to be applied in some environments with high real?time performance requirements. Therefore， an improved fast Otsu algorithm is proposed. The hunting scope of the traversed gray was reduced after importing the image complexity and its related properties. A fast calculation method is used in the scope of the traversed gray， which executes secondary acceleration in comparison with the traditional Otsu algorithm. The experimental results show that this algorithm improves the calculation speed in comparison with the traditional Otsu algorithm， and the image segmentation results of the two algorithms are the same.
Keywords： image segmentation； image complexity； Otsu algorithm； fast calculation
0 引 言
图像分割是图像分析中的难点和重点，其目的是要将图像中感兴趣区域提取出来，以便对分割出的目标区域进行分析处理。所以图像分割也起到了桥梁的作用，一直受到众学者极大的关注。目前传统分割方法主要分为基于区域的、基于边缘的和两者结合的图像分割方法[1]。而阈值分割是图像分割中一类最早被研究和使用的方法，其具有物理意义明确、效果明显、易于实现、实时性良好等特点[2]。其中最大類间方差法（Otsu算法）作为一种经典阈值法，也被广泛运用和发展。且在原算法上又提出基于二维直方图的二维阈值分割法（二维Otsu）[3?4]和相应的三维Otsu[5]算法，虽然比起一维算法，二维算法和三维算法抗噪性更强，不过其计算较一维Otsu算法复杂，需要消耗更多的时间，可能无法满足某些对实时性要求较高的工作。文献[6]所述的快速算法属于一种迭代算法，虽然计算速度有所提高，但其求得的阈值在某些时候与Otsu算法所求结果不相同。而文献[7]的计算结果和Otsu计算出的阈值也有所不同。
本文在一维Otsu算法基础上进行了改进， 基于文献[8?9]所证明关于图像复杂度和Otsu算法的性质，对一维Otsu算法进行了简化，在保证计算精度的同时，提高了阈值计算速度，这可以满足机器视觉对于实时性的要求。
1 传统Otsu算法
Otsu算法是由大津展之[3]在1979年提出的经典算法。它是按图像的灰度特性，将图像分成了两部分，可理解为目标和背景两部分，再计算二者的类间方差。若分割后两部分类间方差越大，则表示构成图像的两部分的差别越大。因此，使类间方差最大的分割意味着错分概率最小。
设一幅图像有L个灰度级别，以灰度阈值t将图像分为两部分，将两部分分别设为B0=[0，1，2，…，t]，B1=[t+1，t+2，…，L-1]。设任意灰度为k的像素出现的概率为[pk]，[pk]=[nkN，]其中N为图像像素总数，[nk]为灰度值为k的像素点个数。图像总像素均值为[μk=k=0L-1kpk]。目标像素（B0）出现的概率记为[ω0（t）]，背景像素（B1）出现的概率记为[ω1（t）]。设[μ（t）=k=0tkpk]，则目标像素灰度均值记为[μ0（t）]，背景像素灰度均值记为[μ1（t）]。
2 改进Otsu快速算法
对于传统的Otsu算法，对所有灰度值进行穷举计算将消耗大量冗余时间，是拉低计算速度的主要原因。因此本文从减少冗余运算为出发点，在传统Otsu计算的基础上，对目标图像的灰度级遍历范围进行缩减，同时在对缩减后的灰度级范围内使用一种改进的Otsu快速算法，在传统的Otsu算法基础上进行了两次提速，可以满足机器视觉实时性的要求。
2.1 灰度级遍历范围的缩小
传统Otsu算法需要遍历256个灰度级，本文引用图像复杂度的性质对所遍历灰度级范围进行缩减。选用图像复杂度作为信息隐藏研究中图像的度量尺度。首先是因为图像复杂度是图像的客观属性；其次，基于图像的信息隐藏对图像的纹理、颜色变化等因素敏感，信息隐藏能力和效果随着图像纹理的复杂程度的变化而不同[10]。图像复杂度的计算公式为：
[C=-k=1tnklog（nkN）] （7）
式中：C代表图像复杂度；t为划分目标和背景区域的分割阈值；[nk]是灰度值为k的像素点个数；N为整幅图像内像素点个数[11]。
由图像复杂度的性质[12]可知，图像的整体复杂度不小于其任意子集的复杂度，且随着待分割区域的减小，图像灰度值差异的减少，图像复杂度会减小；相反的，随着待分割区域的增大，图像灰度值差异的增大，图像复杂度会增大。而且在一般的图像处理经验中，待分割区域在整图中所占比例越大，图像的平均灰度也会越接近最优分割阈值。所以由图像复杂度，待分割区域大小的关系即可对Otsu算法中灰度的遍历范围进行缩减。即图像复杂度越高，待分割区域所占比例越大，最佳阈值就离平均灰度越接近。设Tm为图像平均阈值，[nT]是灰度为Tm的像素数，[NT]是以阈值为Tm分割区域内像素数，待分割区域图像复杂度公式为[11]：
式中：L是图像灰度级数；q为比例系数，[0.05≤q≤0.15]。最终灰度级遍历范围会在（Tm-[α]，Tm+[α]）之内，可见图像复杂度越高，[α]越小，传统Otsu方法的灰度遍历范围越小。这样就从缩小灰度级遍历范围的角度出发，实现了本文快速算法的第一次加速。
2.2 遍历范围内快速计算
相比于传统的Otsu算法，本文使用的快速算法大大减少了穷举次数，若在相同的灰度级范围内搜索最佳阈值会大大减少计算时间。根据Otsu准则的性质[8]，在传统Otsu算法下得到的最佳阈值[t*]满足如下公式：
利用这三条性质即可进行最佳阈值t*的快速搜索。概括地说，这种快速搜索就是要分别从所要遍历的灰度范围的两端，即范围内的首个灰度和末尾灰度值分别开始搜索使得[f1（t）]=[f2（t）]的所有t值。在此过程中，把所要遍历的范围分成了若干个小区间，利用性质，直接就能判断出每个小区间是否有满足式（10）的t值，并且记录这个t值，若有惟一t值使得式（10）成立，此t值即为所求的最佳阈值；若有两值t1，t2分别满足式（10），则在（t1，t2）范围内继续重复之前步骤搜索出满足[f1（t）]=[f2（t）]的t值，最后将所有满足式（10）的t值分别代入[σ2b（t）]，使得其最大的t值即为所求。这种快速算法减少了待搜索灰度范围内的冗余计算次数，避免了逐一搜索，进而实现了本文快速算法的第二次加速。
2.3 改进算法计算流程
運用本文算法进行最佳阈值求解计算过程如下：
（1） 计算图像的平均阈值Tm，计算以Tm为阈值分割的目标区域的图像复杂度[CTm]，结合式（8）、式（9）计算出[α]，得出所要搜索的灰度范围（Tm-[α]，Tm+[α）]。并依照定义计算[μk]，[μ（t）]和[ω0（t）]。
（2） 从Tm-[α]开始搜索满足[f1（t）]=[f2（t）]的t值。若[f1（t）]>[f2（t）]，令[d=f1（t）-f2（t）]，当[ω0（t+d）<1]，则t=t+d，否则t=t+1。将新得出的t值再重新返回进行比较计算，直到搜索出满足[f1（t）]=[f2（t）]的t值，使t1=t，结束搜索。
（3） 从Tm+[α]开始搜索满足[f1（t）]=[f2（t）]的t值，若[ω0（t）]=1，则使t=t-1。当[ω0（t）]<1并有[f1（t）]<[f2（t）]时，使[d=f1（t）-f2（t）]，t=t-d。将新得到的t值再重新计算比较，直至搜索出使[f1（t）]=[f2（t）]成立的t值，使t2=t，结束搜索。
（4） 比较t1与t2，若t1和t2相等，此时交点惟一，则t1（t2）即为所求最佳阈值，求解结束；否则继续步骤（5）和步骤（6）。
（5） 若t1[≠]t2，则继续以（t1，t2）为区间返回步骤（2）重新搜索，并记录所有使得[f1（t）]=[f2（t）]成立的t值。
（6） 将不同t值代入[σ2b（t）]计算，则使其最大的t值即为最佳阈值。
2.4 算法耗时分析
运算量越大会导致计算耗时越长，降低图像处理速度，影响机器视觉的实时性。运用传统Otsu方法计算图像最佳阈值，需要计算[ω0（t）]，[μk]，[μ（t）]和[σ2b（t）]，其中[μk]=[μ（L-1）]。记计算一次[μ（t）]所耗时为y0，计算一次[ω0（t）]耗时为y1，且[ω0（t）]和[μ（t）]均可递推得到结果，故计算时间远小于[σ2b（t）]计算时间。记计算一次[σ2b（t）]的时间记为y2，由式（6）可知需要计算4次乘法和2次加法。传统Otsu的总计算时间可记为L（y0+y1）+Ly2。
运用本文算法同样需先计算[ω0（t）]，[μk]，[μ（t）]，可知每算一次消耗时间y0+y1。记减小灰度搜索范围后灰度数为l，则此部分耗时为l（y0+y1）。由式（8）和式（9）可知，计算图像复杂度[CTm]需2次乘法运算，计算[α]需要4次乘法1次减法运算，总共需进行6次乘法和1次减法运算，总耗时记为y3，则y3<2y2。记每次计算[f1（t）]耗时为y4，由式（11）可知计算[f1（t）]时需要3次乘法3次减法，因为乘法计算耗时通常大于加法计算耗时，故y4<y2。记m为[f1（t）]，[f2（t）]交点搜索次数，m为交点个数。当[f1（t）]，[f2（t）]交点数惟一时，算法总耗时为l（y0+y1）+y3+my4，因为l（y0+y1）<l（y0+y1），m远小于l，故y3+my4<（2+m）y2<ly2，所以此时改进算法耗时远小于传统otsu。当[f1（t）]和[f2（t）]的交点数不惟一时，算法总耗时为l（y1+y2）+y3+my4+my2。因为m小于m，y3+my4+my2<（2+m+n）y2<ly2。故本文快速算法耗时总小于传统otsu算法。
摘 要： 阈值分割是众多图像分割方法中使用最普遍的一种方法，阈值的求解也是图像处理的重心。传统Otsu算法属于穷举式的阈值求解方法，需遍历每个灰度值并计算以其为阈值的类间方差，在此进行了大量不必要的计算，可能无法应用于某些实时性要求较高的环境中。对此提出一种快速的Otsu改进算法，在引入图像复杂度及其相关性质缩小了灰度的搜索范围，同时在搜索范围内使用了一种快速计算方法，较传统Otsu算法进行了二次加速。实验结果证明，该算法较传统Otsu算法提高了计算速度，且两种算法的图像分割结果相同。
关键词： 图像分割； 图像复杂度； Otsu算法； 快速计算
中图分类号： TN911.73?34； TP391.41 文献标识码： A 文章编号： 1004?373X（2017）20?0042?04
Abstract： Threshold segmentation is one of the most commonly used image segmentation methods， and the solution of threshold is also the focus of image processing. The traditional Otsu algorithm is an exhaustive threshold solution method， which needs to traverse each gray value， calculate the interclass variance taking the gray value as the threshold value， and make a large number of unnecessary calculations. As a result， the traditional Otsu algorithm may not be appropriate to be applied in some environments with high real?time performance requirements. Therefore， an improved fast Otsu algorithm is proposed. The hunting scope of the traversed gray was reduced after importing the image complexity and its related properties. A fast calculation method is used in the scope of the traversed gray， which executes secondary acceleration in comparison with the traditional Otsu algorithm. The experimental results show that this algorithm improves the calculation speed in comparison with the traditional Otsu algorithm， and the image segmentation results of the two algorithms are the same.
Keywords： image segmentation； image complexity； Otsu algorithm； fast calculation
0 引 言
图像分割是图像分析中的难点和重点，其目的是要将图像中感兴趣区域提取出来，以便对分割出的目标区域进行分析处理。所以图像分割也起到了桥梁的作用，一直受到众学者极大的关注。目前传统分割方法主要分为基于区域的、基于边缘的和两者结合的图像分割方法[1]。而阈值分割是图像分割中一类最早被研究和使用的方法，其具有物理意义明确、效果明显、易于实现、实时性良好等特点[2]。其中最大類间方差法（Otsu算法）作为一种经典阈值法，也被广泛运用和发展。且在原算法上又提出基于二维直方图的二维阈值分割法（二维Otsu）[3?4]和相应的三维Otsu[5]算法，虽然比起一维算法，二维算法和三维算法抗噪性更强，不过其计算较一维Otsu算法复杂，需要消耗更多的时间，可能无法满足某些对实时性要求较高的工作。文献[6]所述的快速算法属于一种迭代算法，虽然计算速度有所提高，但其求得的阈值在某些时候与Otsu算法所求结果不相同。而文献[7]的计算结果和Otsu计算出的阈值也有所不同。
本文在一维Otsu算法基础上进行了改进， 基于文献[8?9]所证明关于图像复杂度和Otsu算法的性质，对一维Otsu算法进行了简化，在保证计算精度的同时，提高了阈值计算速度，这可以满足机器视觉对于实时性的要求。
1 传统Otsu算法
Otsu算法是由大津展之[3]在1979年提出的经典算法。它是按图像的灰度特性，将图像分成了两部分，可理解为目标和背景两部分，再计算二者的类间方差。若分割后两部分类间方差越大，则表示构成图像的两部分的差别越大。因此，使类间方差最大的分割意味着错分概率最小。
设一幅图像有L个灰度级别，以灰度阈值t将图像分为两部分，将两部分分别设为B0=[0，1，2，…，t]，B1=[t+1，t+2，…，L-1]。设任意灰度为k的像素出现的概率为[pk]，[pk]=[nkN，]其中N为图像像素总数，[nk]为灰度值为k的像素点个数。图像总像素均值为[μk=k=0L-1kpk]。目标像素（B0）出现的概率记为[ω0（t）]，背景像素（B1）出现的概率记为[ω1（t）]。设[μ（t）=k=0tkpk]，则目标像素灰度均值记为[μ0（t）]，背景像素灰度均值记为[μ1（t）]。
2 改进Otsu快速算法
对于传统的Otsu算法，对所有灰度值进行穷举计算将消耗大量冗余时间，是拉低计算速度的主要原因。因此本文从减少冗余运算为出发点，在传统Otsu计算的基础上，对目标图像的灰度级遍历范围进行缩减，同时在对缩减后的灰度级范围内使用一种改进的Otsu快速算法，在传统的Otsu算法基础上进行了两次提速，可以满足机器视觉实时性的要求。
2.1 灰度级遍历范围的缩小
传统Otsu算法需要遍历256个灰度级，本文引用图像复杂度的性质对所遍历灰度级范围进行缩减。选用图像复杂度作为信息隐藏研究中图像的度量尺度。首先是因为图像复杂度是图像的客观属性；其次，基于图像的信息隐藏对图像的纹理、颜色变化等因素敏感，信息隐藏能力和效果随着图像纹理的复杂程度的变化而不同[10]。图像复杂度的计算公式为：
[C=-k=1tnklog（nkN）] （7）
式中：C代表图像复杂度；t为划分目标和背景区域的分割阈值；[nk]是灰度值为k的像素点个数；N为整幅图像内像素点个数[11]。
由图像复杂度的性质[12]可知，图像的整体复杂度不小于其任意子集的复杂度，且随着待分割区域的减小，图像灰度值差异的减少，图像复杂度会减小；相反的，随着待分割区域的增大，图像灰度值差异的增大，图像复杂度会增大。而且在一般的图像处理经验中，待分割区域在整图中所占比例越大，图像的平均灰度也会越接近最优分割阈值。所以由图像复杂度，待分割区域大小的关系即可对Otsu算法中灰度的遍历范围进行缩减。即图像复杂度越高，待分割区域所占比例越大，最佳阈值就离平均灰度越接近。设Tm为图像平均阈值，[nT]是灰度为Tm的像素数，[NT]是以阈值为Tm分割区域内像素数，待分割区域图像复杂度公式为[11]：
式中：L是图像灰度级数；q为比例系数，[0.05≤q≤0.15]。最终灰度级遍历范围会在（Tm-[α]，Tm+[α]）之内，可见图像复杂度越高，[α]越小，传统Otsu方法的灰度遍历范围越小。这样就从缩小灰度级遍历范围的角度出发，实现了本文快速算法的第一次加速。
2.2 遍历范围内快速计算
相比于传统的Otsu算法，本文使用的快速算法大大减少了穷举次数，若在相同的灰度级范围内搜索最佳阈值会大大减少计算时间。根据Otsu准则的性质[8]，在传统Otsu算法下得到的最佳阈值[t*]满足如下公式：
利用这三条性质即可进行最佳阈值t*的快速搜索。概括地说，这种快速搜索就是要分别从所要遍历的灰度范围的两端，即范围内的首个灰度和末尾灰度值分别开始搜索使得[f1（t）]=[f2（t）]的所有t值。在此过程中，把所要遍历的范围分成了若干个小区间，利用性质，直接就能判断出每个小区间是否有满足式（10）的t值，并且记录这个t值，若有惟一t值使得式（10）成立，此t值即为所求的最佳阈值；若有两值t1，t2分别满足式（10），则在（t1，t2）范围内继续重复之前步骤搜索出满足[f1（t）]=[f2（t）]的t值，最后将所有满足式（10）的t值分别代入[σ2b（t）]，使得其最大的t值即为所求。这种快速算法减少了待搜索灰度范围内的冗余计算次数，避免了逐一搜索，进而实现了本文快速算法的第二次加速。
2.3 改进算法计算流程
運用本文算法进行最佳阈值求解计算过程如下：
（1） 计算图像的平均阈值Tm，计算以Tm为阈值分割的目标区域的图像复杂度[CTm]，结合式（8）、式（9）计算出[α]，得出所要搜索的灰度范围（Tm-[α]，Tm+[α）]。并依照定义计算[μk]，[μ（t）]和[ω0（t）]。
（2） 从Tm-[α]开始搜索满足[f1（t）]=[f2（t）]的t值。若[f1（t）]>[f2（t）]，令[d=f1（t）-f2（t）]，当[ω0（t+d）<1]，则t=t+d，否则t=t+1。将新得出的t值再重新返回进行比较计算，直到搜索出满足[f1（t）]=[f2（t）]的t值，使t1=t，结束搜索。
（3） 从Tm+[α]开始搜索满足[f1（t）]=[f2（t）]的t值，若[ω0（t）]=1，则使t=t-1。当[ω0（t）]<1并有[f1（t）]<[f2（t）]时，使[d=f1（t）-f2（t）]，t=t-d。将新得到的t值再重新计算比较，直至搜索出使[f1（t）]=[f2（t）]成立的t值，使t2=t，结束搜索。
（4） 比较t1与t2，若t1和t2相等，此时交点惟一，则t1（t2）即为所求最佳阈值，求解结束；否则继续步骤（5）和步骤（6）。
（5） 若t1[≠]t2，则继续以（t1，t2）为区间返回步骤（2）重新搜索，并记录所有使得[f1（t）]=[f2（t）]成立的t值。
（6） 将不同t值代入[σ2b（t）]计算，则使其最大的t值即为最佳阈值。
2.4 算法耗时分析
运算量越大会导致计算耗时越长，降低图像处理速度，影响机器视觉的实时性。运用传统Otsu方法计算图像最佳阈值，需要计算[ω0（t）]，[μk]，[μ（t）]和[σ2b（t）]，其中[μk]=[μ（L-1）]。记计算一次[μ（t）]所耗时为y0，计算一次[ω0（t）]耗时为y1，且[ω0（t）]和[μ（t）]均可递推得到结果，故计算时间远小于[σ2b（t）]计算时间。记计算一次[σ2b（t）]的时间记为y2，由式（6）可知需要计算4次乘法和2次加法。传统Otsu的总计算时间可记为L（y0+y1）+Ly2。
运用本文算法同样需先计算[ω0（t）]，[μk]，[μ（t）]，可知每算一次消耗时间y0+y1。记减小灰度搜索范围后灰度数为l，则此部分耗时为l（y0+y1）。由式（8）和式（9）可知，计算图像复杂度[CTm]需2次乘法运算，计算[α]需要4次乘法1次减法运算，总共需进行6次乘法和1次减法运算，总耗时记为y3，则y3<2y2。记每次计算[f1（t）]耗时为y4，由式（11）可知计算[f1（t）]时需要3次乘法3次减法，因为乘法计算耗时通常大于加法计算耗时，故y4<y2。记m为[f1（t）]，[f2（t）]交点搜索次数，m为交点个数。当[f1（t）]，[f2（t）]交点数惟一时，算法总耗时为l（y0+y1）+y3+my4，因为l（y0+y1）<l（y0+y1），m远小于l，故y3+my4<（2+m）y2<ly2，所以此时改进算法耗时远小于传统otsu。当[f1（t）]和[f2（t）]的交点数不惟一时，算法总耗时为l（y1+y2）+y3+my4+my2。因为m小于m，y3+my4+my2<（2+m+n）y2<ly2。故本文快速算法耗时总小于传统otsu算法。
