Otsu多阈值快速求解算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇Otsu多阈值快速求解算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

フ 要:最大类间方差(otsu)方法计算简单，分割效果良好，广泛应用于图像的单阈值分割。为了使Otsu方法能够适应于更加复杂的图像，很多学者对其进行了多阈值的推广，但存在计算量大、效率低的问题。针对此不足，对Otsu方法也进行了多阈值的推广，首先划分直方图区间，然后采用快速二分法求取区间中的阈值以实现Otsu方法的多阈值扩展，使其在保持良好分割效果的基础上大大节省了时间。实验说明了该算法的有效性。

ス丶词:图像分割；直方图区间；局部阈值；最大类间方差法；多阈值

ブ型挤掷嗪: TP391.41 文献标志码:A

Abstract: Otsu has been widely used because of its simplicity in calculation and good segmentation result. And many scholars have put forward multithreshold Otsu method to make it more useful in more complex pictures. But this multithreshold Otsu method is of low efficiency and time consuming. Concerning this shortage, this paper made histogram intervals first, and then the rapid dichotomy was used to seek for the threshold in the interval. The improvement in this paper can maintain good segmentation result and save lots of time. The experiments show that the algorithm is effective.

Key words:image segmentation；histogram interval；local threshold；Otsu method；multithreshold

0 引言

图像分割是将图像划分成若干个互不相交的小区域的过程，常见的图像分割方法有很多，比如：基于阈值的图像分割、模糊方法、边缘检测的方法、特征空间聚类的方法等［1］。其中基于阈值的方法计算简单，分割效果好［2］。在基于阈值的方法中，Otsu方法［3］是一种性能较好的方法，它以两个评价函数即最大类间方差和最小类内方差为基础，稳定性好，成功率高、使用率也很高［4］。但Otsu方法实质上是一个穷举法，因此计算量较大。另外，实际中的图像不仅仅是目标和背景的二值分割，更多情况下需要对图像进行多阈值分割，因此单阈值分割效果并不好［5］。鉴于这些问题，很多学者也尝试了多种扩展方法使Otsu方法能够应用于图像的多阈值分割。文献［5-6］运用了松弛余量的办法使得多阈值的求取范围进一步减小，同时也提高了算法的效率；文献［7-8］将Otsu单阈值方法进行了多阈值推广并将其应用到彩色图像的分割中；文献［9］引入了NelderMead单纯形法来优化多阈值算法，提高算法效率。本文也针对传统Otsu方法中的不足进行了推广与改进，先划分直方图区间，然后采用快速二分法求取区间中的阈值，实验证明本文方法在节省大量时间的同时保持了良好的分割效果。

1 单阈值Otsu算法分析

记f(i, j)为大小为M×N的图像在(i, j)点处的灰度值，灰度级数为L，因此可认为f(i, j)的灰度取值范围为[0，L-1]。设每一灰度级所占的比例为P(l)，P(l)的计算公式为：P(l)=1M×N∑f(i, j)=l1。如果以阈值t去分割图像的目标和背景两部分内容，则目标(本文以f(i, j)≤t为目标)所占的比例为Е鬲o(t)=∑l≤tP(l)，平均灰度为μo(t)=∑l≤tl*P(l)，背景所占的比例为ωb(t)=1-ωo(t)=∑t

Уャ兄氮Otsu方法就是找出使类间方差最大的t值即可，Х讲钤酱笏得髂勘旰捅尘暗那别越大，如果分错，方差就会变小［6］。

2 多阈值Otsu方法的推广与实现

2.1 多阈值Otsu算法分析

单阈值Otsu法基本思想是按阈值把直方图分割成两类：目标类和背景类，这里的多阈值分割其实就是指将图像分成多个类，使得多个类的类间的方差Е要2=∑n-1i=0∑n-1j=i+1ωi(t)*ωj(t)*(μi(t)-μj(t))2И［4］最大。单阈值Otsu方法本质上是一种穷举搜索算法，因此多阈值Otsu算法搜索运算的循环次数近似等于Lm，其中L为灰度级数，m为阈值的个数［4-5,9-10］，这样的计算过程十分耗时。オ

2.2 改进的多阈值Otsu算法

单阈值Otsu方法的实质是在两个波峰之间找到一个统计意义上的最佳阈值，划分开两个独立的波峰［8］。复杂图像的直方图也多呈多峰值形状，这也使得多阈值的分割是必要的。因此，本文首先对直方图进行小区间划分，使得每个小区间内尽量保持只有一个谷底，如图1所示，这样再在小区间内反复使用单阈值Otsu方法可以得到良好的分割效果。经过上述做法可以使得运算量降为O(L)。为了更近一步降低算法的时间复杂度，本文采取了快速二分法［11］去求解直方图小区间中的分割阈值。

2.3 改进的多阈值算法的具体实现过程

2.3.1 直方图区间划分

1)对直方图进行多尺度滤波［12-13］可得到更为精确的直方图逼近图像，但是这种算法耗时大，需要进行多次循环运算。为了得到平滑的直方图并节省时间，本文对直方图进行两次均值滤波，以得到平滑的直方图，这样的处理既能保持原始直方图的良好性状，还有利于后期的进一步处理。

2)在平滑后的直方图中找出峰值集合：P0={Pl,P(l)≥P(l-1) & Pl≥P(l+1) & h(l)>(1/L)*θ}，其中h(l)为直方图原始值，L为灰度级数，θ为比例系数，可凭经验设置，即如果此灰度是个波峰且原直方图中的值占有一定比例时,峰值被保留下来。

3)去除距离相近的峰值：在峰值集合P0中进行筛选，如果两个峰值的距离小于δ(本文取15)时，将小的峰值从P0中去除［14］。オ

4)去除波谷不明显的峰值，假设两个峰值的灰度为i和j，其波谷计算方式为valley=h(i)+h(j)j-i+1h(i)+h(j)2，У辈ü嚷足一定值Е联时就认为这两个峰值是相似的[14]，可以合并。

5)经过筛选当峰值数仍然大于一定的数目m时，可适当调整参数，重复步骤3)、4)进行二次筛选；否则，结束筛选。利用最后留下来的峰值进行对直方图进行区间划分，假设筛选后的峰值为t0,t1,t2,…,tm，则划分后的区间为[0,t0),[t0,t1),…,[tm,L)。オ

2.3.2 快速二分法求解阈值

在划分好的区间中反复利用快速二分法求取最佳局部阈值，具体步骤如下：

1)对单阈值Otsu的目标函数Е要2=ωo(t)*ωb(t)*(μo(t)-μb(t))2进行连续域上的扩展，即认为t在连续域上取值，对其求一阶导数，得到满足μo(t)+μb(t)-2t=0的阈值可使得类间方差σ最大。オ

2)在划分好的小区间[t┆low,t┆high)中，定义函数f(k)=μo(k)+μb(k)-2k，令t=(t┆low+t┆high)/2，计算f(t)。如果f(t)足够小，且f(t-1)与f(t+1)异号，那么t即为该区间的分割阈值；如果f(t)>0，则令t=t┆low，继续求f(t)的值并进行判断；如果f(t)

3 实验结果比对

文献［5-8］虽然对多阈值分割方法进行了改进，使得迭代次数比Lm有明显下降，У它们的本质还是穷举法，只是缩小了搜索的范围。而本文所采用的图像分割方法是在区间内利用快速二分法求解得到阈值，其迭代次数可以更进一步减少，并保持良好的分割效果。为了加以比较，本文采用了文献［8］中的测试图像进行结果比对，图像来自网络，与文献［8］中的测试图像并不完全一样，大小为425×318，如图2所示，图3是图2的灰度直方图，图4和图5是多阈值分割和单阈值分割的结果。

多阈值分割时先在灰度直方图中筛选，剩下三个峰值122和160和229，因此直方图划分的区间有四个：［0~122)，［122~160)，［160~229)，［229~256)，在这四个区间中应用快速二分法进行求解即可得出分割图像的四个阈值;当然也可不加入0和256级灰度值，只在［122~160)，［160~229)，区间中求取阈值，本文采用第一种形式。结果如表1所示。

从分割结果来看，多阈值的分割结果比单阈值分割结果保留了更多细节信息。其中，松弛余量法是在分好的直方图区间中又另外以一定参数确定一个小范围进行阈值的搜索，文献［5-6,8］等都采用了这种方式，本文采用的松弛余量为直方图小区间的1/4。经过比较，本文方法在迭代次数上远优于其他方法，同时又没有降低图像分割的效果。

另外，文献［8］是按颜色直方图对图像分割，为了进一步对比，本文也按图像的颜色直方图对图像进行分割，结果如图7所示，分割阈值为16.0, 53.0, 137.0，迭代次数为10，比文献［8］中40次要少很多，同样说明了本算法的有效性。

为了更进一步验证本文算法的有效性，本文在SIMPLicity系统测试集中的1B000张图像上进行了分割实验，并统计了它们的迭代次数，结果如表2所示。

在表2中，每一列分别记录了三种分割方法的平均迭代次数和平均阈值数，通过对比，本文的方法在效率上优于其他两种方法，同时又保持了良好的分割效果。

4 结语

传统的多阈值Otsu分割是一个比较耗时的工作，本文利用直方图分段与改进的单阈值Otsu方法结合的方式实现了图像的快速分割。与传统的方法相比,本文的改进方法既能保持好的分割效果又能提高分割运算的效率。

げ慰嘉南:

[1] 林开颜，吴军辉，徐立鸿.彩色图像分割方法综述［J］.中国图象图形学报，2005，10(1)：1-10.

[2] SEZGIN M, SANKUR B.Survey over image thresholding techniques and quantitative performance evaluation［J］.Journal of Electronic Imaging, 2004, 13(1):146-165.

[3] OTSU N.A threshold selection method from graylevel histogram［J］.IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(1):62-66.

[4] 殷蔚明,王典洪.Otsu法的多阈值推广及其快速实现［J］.中国体视学与图像分析，2004，9(4)：219-223.

[5] ARORA S, ACHARYA J, PRASANTA V A, et al. Multilevel thresholding for image segmentation through a fast statistical recursive algorithm［J］.Pattern Recognition Letters, 2008,29(2):119-125.

[6] 王磊，段会川.Otsu方法在多阈值图像分割中的应用［J］.计算机工程与设计，2008，29(11)：2844-2845.

[7] 李中健，杜鹃，郭璐.将Otsu用于多阈值彩色图像分割的方法及优化［J］.计算机工程与应用，2010，46(11)：176-178.

[8] 王祥科,郑志强.Otsu多阈值快速分割算法及其在彩色图像中的应用［J］.计算机应用，2006，26(z1)：14-15.

[9] 刘立，焦斌亮，刘钦龙.Otsu多阈值算法推广实现［J］.测绘科学，2009，34(6)：240-241.

[10] 李哲学，陈树越.快速多阈值图像分割法［J］.计算机应用，2010，30(5)：1335-1337.

[11] 李大卫，姜鹏远,王华强,等.一种基于改进OTSU评价函数的图像分割方法［J］. 测绘科学，2010，35(1)：26-27.

[12] CARLOTTO M J.Histogram analysis using a scalespace approach［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(1):121-129.

[13] 邹丹平，冯涛，李咸伟，等.基于EM的直方图逼近及其应用［J］.中国图象图形学报，2005，10(11)：1458-1461.

[14] CHENG HENGDA, SUN YING.A hierarchical approach to color image segmentation using homogeneity［J］.IEEE Transactions on Image Processing, 2000, 9(12):2071-2082.