改进的三维Otsu图像分割快速算法

龚劬，倪麟，唐萍峰，叶剑英，廖武忠

重庆大学数学与统计学院，重庆 401331

改进的三维Otsu图像分割快速算法

龚劬，倪麟，唐萍峰，叶剑英，廖武忠

重庆大学数学与统计学院，重庆 401331

针对三维Otsu图像分割算法运算量大和图像细节分割不够准确的问题，提出一种改进的三维Otsu图像分割算法。该算法基于灰度-邻域平均灰度-梯度的新的三维特征模型，构建三维直方图；将三维Otsu分解为三个一维Otsu；在同时考虑类间距离和类内距离的基础上，提出一种新的最大散度差准则。实验结果表明，该算法不仅可以取得较好的分割效果，而且计算量较小，比三维Otsu阈值分割递推算法快900倍左右。

图像分割；Otsu；三维直方图；阈值

1 引言

图像分割是指将一幅图像分解为若干个互不交叠的、有意义的、具有相同性质的区域[1-2]。它是图像工程中的重点和热点，也是计算机视觉中的难题。至今，提出的分割算法已有上千种，其中最经典的方法就是基于灰度阈值的分割方法。阈值分割利用了图像中所要提取的目标和背景在灰度上的差异，把图像视为不同灰度级的目标和背景两类区域的组合，选择合适的阈值以确定图像中每个像素应属于目标还是背景的区域。Otsu法[3]因计算简单、实时性高等优点被广泛使用[4-6]。但是，Otsu法只使用了灰度信息，而没有考虑空间邻域信息，抗噪性较弱。为此，人们利用图像像素与其邻域之间存在一定相关性的这一空间信息，推导出了相应的二维算法[7-8]及三维算法[9-11]。相对于一维Otsu算法，二维算法和三维算法取得了较好的分割效果。但是，对于边缘细节的处理，以及一些强噪声的抑制上，二维算法的处理效果也不够好。而目前的三维Otsu算法[9-11]均是基于灰度-邻域平均灰度-邻域中值的三维直方图，但是中值会破坏掉图像中大量的高频边缘细节信息，使得图像变得模糊不清，特别对一些细节多，如点、线、尖顶细节较多的图像不宜使用中值方法[12]，否则会使得分割不够准确。因此，为了抑制噪声，又尽量凸显以及还原图像中的细节并减小算法的计算量，本文把像素的梯度作为第三维加入到三维Otsu算法中，提出一种改进的三维Otsu图像分割快速算法。经过多次实验表明，该算法不仅可以取得较好的分割效果，而且计算量较小，比三维Otsu阈值分割递推算法快900倍左右。

2 传统三维Otsu算法

在文献[9]中，景晓军等利用原始图像、邻域平均图像以及邻域中值图像联合直方图，提出了三维Otsu算法。该方法不仅充分利用了图像像素点的信息，而且还考虑到了邻域图像像素点以及邻域中值图像像素点的空间相关信息，具有很好的抗噪性。三维Otsu算法在文献[9]中有详细叙述，在此不再赘述。

3 本文算法

3.1 基于灰度-邻域平均灰度-梯度的三维直方图

目前传统三维Otsu算法中一般采用邻域中值作为第三维，虽然有利于噪声抑制，但是弱化了图像的边缘和细节等信息。因此，本文从考虑抑制噪声和增强图像的边缘和细节出发，将三维直方图的第三个分量改为像素点的梯度。梯度运算实际上是一种非线性锐化滤波器，能够使边缘和轮廓线模糊的图像变得清晰，并使其细节清晰[12]。这里梯度算法选择了对灰度渐变和噪声较多的图像处理较好的Sobel算子。该算子的计算公式如下：

式中，f(m，n)表示像素点(m，n)处的灰度，▽fm(m，n)、▽fn(m,n)分别表示横、纵坐标方向的一阶微分，G[f(m,n)]表示梯度。为了提高最佳阈值选取的速度以及后文处理的方便，将其范围压缩至[0，255]以内。

3.2 分解的灰度-邻域平均灰度-梯度三维Otsu算法

3.3 最大散度差准则

由于本文已经成功地将三维分解为三个一维即将三维Otsu递推算法的计算复杂度从O(L3)降到了O(L)，所以在求取最佳阈值时，就放在一维的Otsu中求取最佳阈值，这样算法的计算复杂度就为O(L)，可大幅度地提高计算速度，提高算法的实用性。

传统三维Otsu算法和加权的三维Otsu算法的类间散度函数都只考虑目标类和背景类的类间距离，也就是说类间距离越大，分割的效果越好。然而，上述的两个算法都没有考虑到目标类和背景类的每个类自身像素的分类信息，也就是说没有考虑类内距离。因此，本文同时考虑类间距离和类内距离，最大散度差准则以广义散度差[13-14]即类间距离减去C倍的类内距离作为数据的可分离性度量，并且可以通过调节参数C来改变类内距离在分离性中的作用。

定义3.1设用值s将一组离散的数据分为了两类，对于这两个类，定义其类间距离为：

其中μ1(s)，μ0(s)是对应各自类别元素均值。可以看出，sb(s)越大，类间距离就越大，目标和背景就分得越开，分割效果就越好。

定义3.2设用值s将一组离散的数据分为了两类，Pi是数据i出现的概率，W0(s)和W1(s)分别是两类所占的概率，μ0(s)和μ1(s)是对应的两类的均值，那么这两类的类内距离分别为：

两类的总体类内距离为：

那么最大散度差准则的数学形式就定义为：

当G(s)取最大值所对应的灰度级即为所求的最佳阈值s0，即s0=argmax{} G(s)。

3.4 快速实现方法

4 实验结果

为了验证本文算法的有效性和可行性，实验选取了一幅普通图像、两幅Berkeley segmentation dataset[15]里的人物图像、一幅VOC dataset里的摩托车图像，并与文献[3，8，10-11]的算法进行了比较。实验环境为Windows XP操作系统，系统配置1.96 GB内存，3.19 GHz，Matlab 7.5.0（R2007b）。这里的VOC数据库是来自于名叫Mark Everingham，University of Oxford的一位学者。

参数的选取是本文关键的步骤，对分割的结果有着重要影响。在本文中，参数的选取是根据具体的图像，通过实验数据，分析不同图像的类间距离和类内距离而得到的。本文通过大量的实验观察发现，参数取值为10或者在10的左右分割较好。从以上实验结果可以看出，本文提出的基于灰度-邻域平均灰度-梯度直方图的三维Otsu算法分割效果可以达到甚至优于递推的三维Otsu图像分割算法[10]和加权的三维Otsu算法[11]。在图1中，它是对轮胎图像的分割。文献[3，8，10-11]算法的分割效果都不是很理想，提取出来的轮胎都包括了部分背景；而本文算法巧妙地将轮胎从背景中分离出来，并且轮胎内部细节和轮廓较为清晰，这是其他几个算法都不能达到的效果。图2中的摩托车图像选自于VOC dataset图像分割测试集，本文算法的优势在于将前轮的影子给正确地分割成了背景，且摩托车的轮廓更为清晰。图3是Berkeley segmentation dataset里的一幅人物图像，可以看出，其他的几个算法效果都相当，都未能较好提取出人物目标，大部分背景都错分成了目标；而本文算法却将人物目标大致从背景中分割出来。图4是Berkeley segmentation dataset里的一幅女孩图像，本文算法成功地将女孩头部和背景分割开来，图像右侧的背景分割也更为理想，这是其他几个算法都不具有的分割效果。表1给出了各个算法的运算时间比较。

图1 轮胎图像的分割效果（参数：C1=6，C2=6，C3=6）

图2 摩托车图像的分割效果（参数：C1=6，C2=6，C3=8）

图3 人物运动图像的分割效果（参数：C1=10，C2=10，C3=10）

图4 女孩图像的分割效果（参数：C1=10，C2=6，C3=10）

表1 各个算法的运算时间比较s

5 结语

从分割图像自身的特点出发，本文提出一种基于灰度-邻域平均灰度-梯度直方图的三维Otsu图像分割快速算法。该算法不仅能较好地保留图像边缘和细节信息，而且还更能准确地将图像目标和背景分割开来，大大提高了分割的准确性。需要指出的是，对于不同的图像，由于三维Otsu方法每一维在图像分割中所起的作用不同，如何自适应地确定三个参数，使得分割的效果更佳将是继续研究的问题。

[1]冈萨雷斯.数字图像处理[M].2版.北京：电子工业出版社，2003：460-521.

[2]姚敏.数字图像处理[M].北京：机械工业出版社，2006：243-253.

[3]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on Systems，Man and Cybernetics，1979，9（1）：62-66.

[4]Farrahi M R，Cheriet M.A multi-scale framework for adaptive binarization of degraded document images[J].Pattern Recognition，2010，43（6）：2186-2198.

[5]Yang Wenzhu，Li Daoliang，Zhu Liang，et al.A new approach for image processing in foreign fiber detection[J].Computers and Electronics in Agriculture，2009，68（1）：68-77.

[6]Chung Kuo-liang，Tsai Chia-lun.Fast incremental algorithm for speeding up the computation of binarization[J].Applied Mathematics and Computation，2009，212（2）：396-408.

[7]刘健庄，栗文青.灰度图像的二维Otsu自动阈值分割法[J].自动化学报，1993，19（1）：101-105.

[8]岳峰，左旺孟，王宽全.基于分解的灰度图像二维阈值选取算法[J].自动化学报，2009，359（7）：1022-1027.

[9]景晓军，李剑峰，刘郁林.一种基于三维最大类间方差的图像分割算法[J].电子学报，2003，31（9）：1281-1285.

[10]范九伦，赵凤，张雪峰.三维Otsu阈值分割方法的递推算法[J].电子学报，2007，35（7）：1398-1402.

[11]吕燕，龚劬.加权三维Otsu方法在图像分割中的应用[J].计算机应用研究，2011，28（4）：1576-1579.

[12]刘直芳.数字图像处理与分析[M].北京：清华大学出版社，2006：79-85.

[13]宋枫溪，张大鹏，杨静宇，等.基于最大散度差鉴别准则的自适应分类算法[J].自动化学报，2006，32（4）：541-549.

[14]宋枫溪，程科，杨静宇，等.最大散度差和大间距线性投影与支持向量机[J].自动化学报，2004，30（6）：890-896.

[15]Arbelaez P，Maire M，Fowlkes C，et al.Contour detection and hierarchical image segmentation[J].IEEE TPAMI，2011，33（5）：898-916.

GONG Qu,NI Lin,TANG Pingfeng,YE Jianying,LIAO Wuzhong

College of Mathematics&Statistics,Chongqing University,Chongqing 401331,China

Aiming at the weakness of image detail and the huge calculation of the three-dimensional Otsu,an improved three-dimensional Otsu image segmentation algorithm is presented.A three-dimensional histogram based on gray level-average gray level-gradient is built.The original three-dimensional Otsu algorithm is decomposed into three one-dimensional Otsu algorithms.Based on the one-dimensional Otsu algorithm,a novel maximum scatter difference discriminant criterion is proposed.The criterion considers simultaneously both between-class distance and within-class distance.The experimental results show that the proposed algorithm does not only get satisfactory segmentation result,but also improves the calculation speed,which spends 900 times less than the recursive algorithm for the three-dimensional Otsu method.

image segmentation;Otsu;three-dimensional histogram;threshold

A

TP391.41

10.3778/j.issn.1002-8331.1204-0563

GONG Qu,NI Lin,TANG Pingfeng,et al.Improved fast three-dimensional Otsu image segmentation algorithm. Computer Engineering and Applications,2014,50（6）：171-174.

中央高校基本科研业务费基金资助项目（No.CDJXS11100032）。

龚劬（1963—），女，博士，教授，主要研究方向：图像处理和小波分析；倪麟（1987—），男，硕士研究生，主要研究方向：图像处理；唐萍峰（1987—），男，硕士研究生，主要研究方向：模式识别和图像处理；叶剑英（1987—），女，硕士研究生，主要研究方向：图像处理；廖武忠（1986—），男，硕士研究生，主要研究方向：图像处理。E-mail：nilin871124@163.com

2012-05-02

2012-08-03

1002-8331（2014）06-0171-04

CNKI网络优先出版：2012-09-06，http://www.cnki.net/kcms/detail/11.2127.TP.20120906.0855.007.html