二维直方图重建和降维的Otsu阈值分割算法

陈金位， 吴 冰

(河南理工大学电气工程与自动化学院，河南 焦作 454150)

二维直方图重建和降维的Otsu阈值分割算法

陈金位， 吴 冰

(河南理工大学电气工程与自动化学院，河南 焦作 454150)

指出二维直方图直分法中存在区域划分不合理和抗噪性差问题，提出一种新的阈值分割方法，导出有关计算公式。首先分析噪声点在二维直方图中分布情况，通过重建二维直方图减弱了噪声对阈值分割的干扰；然后将二维直方图区域划分由四分法改为二分法，使得阈值搜索的空间维度从二维降到一维；最后分别给出现有二维直方图分割算法和本文方法的仿真结果。理论分析和实验结果表明，该方法可以运用于几乎所有基于二维直方图的阈值分割，特别是对受噪声污染的图片进行阈值分割时，能使分割后的图片内部均匀、边界准确、抗噪性更稳健，所需运行时间大幅减少。

图像分割；直方图降维；阈值选取；最大类间方差法

图像分割是图像处理与分析应用中一项非常重要的前期工作，国内外学者已进行了大量地研究[1-3]。目前为止，人们提出了各种各样的图像分割方法[4-7]，其中阈值分割法因简单有效且易于理解而被广泛应用。由Otsu提出的该方法是根据图像一维灰度直方图，采用穷举搜索法使类间方差达到最大来确定最佳阈值[8]。1984年Reddi等针对Otsu方法，在不采用原始的穷举搜索法，而通过假定一维灰度直方图为连续的概率密度函数，提出了一种快速搜寻迭代法——最陡上升法[9]，该算法性能稳定且运行效率高，一般只需6～20次迭代即可收敛到最佳阈值。

1993年刘健庄和栗文青[10]将Otsu法从一维推广到二维，结合灰度和邻域平均灰度构成了二维直方图，鉴于二者有很强的相关性，在一定假设下(即目标区域和背景区域上的概率和近似为1)提出了二维最大类间方差法(二维 Otsu法)。其效果较一维方法有明显改善，因将一维信息搜索拓展为二维信息搜索，导致运算量呈指数增加，不宜处理实时问题。为此，人们提出了多种基于二维直方图阈值选取的快速算法[11-14]，以便提高运行速度。

然而，上述二维方法及其快速算法都将二维直方图分成四个矩形区域(区域直分)，仅考虑两个沿对角线的矩形区域，分割结果不够准确。郝颖明和朱枫[15]提出的快速算法虽然没有忽略主对角线附近区域内向量点的概率分布，但仍然存在近似，忽略了部分点，抗噪稳健性不理想。针对传统二维Otsu方法抗噪性弱、实时性差的问题，本文首先指出了二维直方图 Otsu法存在的区域误分，通过重建二维直方图减弱噪声干扰；然后通过降维来降低计算复杂度，使得阈值搜索空间维度从二维降到一维。仿真结果表明该方法较之传统二维Otus法分割效果更好，且大大提高了运算速度。

1 二维直方图区域直分

定义一个L×L大小的正方形区域，其横坐标表示图像像素的灰度级，纵坐标表示像素的邻域平均灰度级，直方图内任意一点的值定义为二者联合概率密度的图形为该图像的二维直方图。

目前，基于二维直方图选取阈值的方法几乎都采用直分法，即利用阈值向量(s,t)，采用分别与灰度级、邻域平均灰度级两坐标轴平行的互相垂直的十字线，将二维直方图分割成如图1所示的4个矩形区域。

图1 二维直方图直分法

图1中4个区域分别用C0、C1、C2和C3表示，假设图像的暗(亮)像素属于目标(背景)，则区域C0和目标对应，区域C1和背景对应，区域C2和C3则表示边缘和噪声，计算时仅考虑区域C0和C1内的概率，而假设区域C2和C3内的概率和近似为零。最后通过Otsu准则获取最佳阈值点。

2 二维直方图重建和降维

2.1 二维直方图直分法存在的不足

(1) 对区域C2和C3的忽略不计与实际不符。因大部分边缘像素点和噪声点分布在远离对角线的区域，所以对C2和C3区域的忽略不计直接导致大量边缘信息丢失。尽管该区域内像素点数远少于背景和目标区域内的像素点数，但仍会影响对图像的分割准度。

(2) 对噪声的处理不统一，抗噪性能弱。虽然忽略了区域C2和C3内的噪声，但区域C0和C1中仍可能存在大量噪声，二维直分法并没有对其进行处理。尤其当图片受噪声干扰后，噪声点的分布随机性较大，导致目标区域内的噪声点分布于二维直方图中的背景区域内，而处于背景区域内的噪声点则分布在二维直方图中的目标区域内，这种分布的随机性随着噪声干扰程度的增强而加大，直接造成二维直方图的分布与正常分布存在较大偏差，影响处理结果。另外，在获取最佳阈值后，二值化图像是对整个区域(包括 C2和C3)进行分割，由于噪声分布的随机性，致使二值

化后的图像中出现了“黑点”或“白点”现象。也就是说，目标区域内的一些噪声点被误认为是背景，二值化成背景点，导致在黑色目标区域中形成“白点”；同样，背景区域内分布的一些噪声点被误认为是目标，将其二值化成目标点，导致在白色背景区域中形成“黑点”。

可以看出，二维Otsu法考虑了空间邻域均值信息，但并未从根本上达到去噪目的。在实际应用中，如果图像受噪声影响小且背景和目标像素变化均匀时，该方法尚能达到预期分割效果，但当图像受噪声影响较大时，用该方法得到的分割效果就不够理想，所以有必要对二维直方图中的一些信息点进行矫正，即二维直方图重建，使其分布尽量恢复到正常状态，以减弱噪声对阈值分割的影响。

(3) 时间和空间复杂度较大。由于该方法在求得最佳阈值时，遍历了整个二维空间，使得计算时间较长，无法满足实时性要求，加之其所需存储空间较大，在实际项目中很难得到应用，对其进行改进势在必然。

2.2 二维直方图重建

由上述分析可知，传统的二维直方图直分法存在错分情况，特别当图片受噪声污染严重时，其缺点更加明显，不能满足分割要求。为此，本文将二维直方图重建，做两条平行直方图主对角线的直线f=g+n和f=g–n分别交坐标轴于点(n,0)和(0,n)，过阈值点(s,t)做直线T=f+g垂直于主对角线。将原直方图的4个区域划分成如图2所示的14个区域。

图2 二维直方图重建

对重新划分的区域进行分析：

(1) C0区域。这个区域中的灰度值和邻域平均灰度值都较小，分布在主对角线附近，二者大小十分接近，为图像的目标区。

(2) C1区域。这个区域中的灰度值和邻域平均灰度值都较大，分布在主对角线附近，二者大小十分接近，为图像的背景区。

(3) (C2、C10、C11、C4)区域。这4个区域内像素的邻域平均灰度值远大于该像素的灰度值，为背景区域内的噪声。

(4) (C3、C7、C8、C5)区域。这4个区域内像素的邻域平均灰度值远小于该像素的灰度值，为目标区域内的噪声。

(5) (C13、C9)区域。此区域因像素点灰度级和邻域平均灰度级有一定差别，视为目标和背景之间过渡的边界点且是靠近目标区域部分的边缘像素点。

(6) (C12、C6)区域。此区域因像素点灰度级和邻域平均灰度级有一定差别，视为目标和背景之间过渡的边界点且是靠近背景区域部分的边缘像素点。

通过上述分析，其矫正方法如下：

对于情况(1)和(2)，属于正常分布，不需要矫正。对于情况(3)，据分析可知，该区域内的点为背景区域内的噪声点，需要矫正，令f*(x,y)=g(x,y)，f*(x,y)为矫正后的像素灰度值。同理，对于情况(4)，该区域内的点为目标区域内的噪声点，需要矫正，令f*(x,y)=g(x,y)。由图2可知被矫正区域的大小与两条直线f=g-n和f=g+n的选取有关，两直线与两坐标轴的交点都为n，对于图像受噪声影响情况的不同，合理地选取 n值，能较理想地重建二维直方图。

二维直方图重建将直方图内边界点区和噪声点区进一步划分成对应于目标和背景的两个子区。上述讨论的都是 L-1＜T≤2L-2的情况，而0≤T≤L-1的情况类似，在此不再赘述。

对于正常分布的非噪声像素点可能也会满足(3)和(4)中某种情况，但因其灰度值和均值十分接近，故使用上述矫正方法矫正后，其分布基本不受影响。

2.3 降维的Otsu阈值分割法

斜线 T=f+g将二维直方图分成两类，表示目标和背景。

(1) 当0≤T≤L-1时，斜线左下角部分对应目标，可以从(0,0)点开始逐点累加算出目标的概率W0(T)及u0i(T)与u0j(T)：

(2) 当L-1＜T≤2L-2时，斜线右上三角部分对应背景，从(L-1,L-1)点开始逐点累加，先求出背景的概率W1(T)及u1i(T)与u1j(T)：

因斜线将直方图分成的两部分包含了直方图内所有信息点，所以容易得到：

将其推导后得：

选择测度函数SB的迹的最大值作为二维最大类间方差门限法的最佳门限向量(T0)：

从上述分析可知，每次计算类间离散度 trSB都需从i=0，j=0开始累加计算，且T的取值越接近 L-1， trSB的计算时间越长，为了提高运算速度，可采用以下递推公式。

当0≤T≤L-1时：

当L-1＜T≤2L-2时可推出：

由上式可知，每次计算 trSB时，只要分别利用前面得到的和再加上直线T=f+g上各点对应的值即可。这样将计算的复杂度从O(L3) 降到O(L)，大大提高了运算效率。

3 实验结果与分析

本实验是在Intel(R) Core(TM) i5-3230M CPU 2.6 GHz、内存为4.00 G(3.82 GB可用)、64位操作系统下运行的，编程环境为MATLAB R2013(b)。其对大量的图片进行了仿真，并将仿真结果与若干种方法对比，发现本文算法分割结果准确，抗噪性相当稳健，取经典图像moon.tif(255×255)、spin.tif(490×367)和coins.png(300×240)作为实验目标，与文献[10]算法及文献[11]算法的图像处理效果和运行时间进行比较。图3为原始图像，图4～6为加入服从N(0,0.2)分布的随机噪声后处理的结果，表1为其仿真阈值和所需时间对比表。

图3 无噪moon.tif分割结果

图4 含噪moon.tif分割结果

图5 含噪spin.tif图片的分割结果

图6 含噪coins.png分割结果

表1 算法的分割阈值及运行时间

图3中无噪moon.tif图片在文献[10]、文献[11]和本文算法下的仿真结果相似，这是因为无噪时图像背景与目标变化均匀，大部分像素点的灰度值与邻域平均灰度相近，分布在直方图主对角线附近，二维灰度直方图C2、C10、C11、C4、C3、C7、C5、C8区域内的分布概率较小。

图 4～6为含噪图片，本文的分割效果比文献[10]、文献[11]更好，抗噪性更稳健，在取不同 n值时发现，当含噪图片在n=40以后，分割阈值几乎不随n的增大而变化，因此将n=40时的阈值作为最佳阈值。文献[10]中的快速算法虽然在时间上比传统分割算法有很大提高且错分的噪声点区域比原始直分算法少，但是忽略了远离对角线的两个区域内的噪声点，通常表现为像素点较少，当对图像处理结果要求较高时，效果不很理想。表1可见，本文将阈值搜索空间维度从二维降到一维，运用给出的递推算法比文献[11]的运行时间少了一个数量级，比文献[10]少了约两个数量级。根据图像含噪的不同程度，合理选取 n值，可获得最佳分割阈值。

4 结 论

本文提出的二维直方图重建及降维的Otsu算法有两个明显优势：其一，当图片受噪声污染时，根据选定的 n值将图片的像素灰度值矫正，重建二维直方图，从而使分割后图像区域内部更均匀，抗噪性更稳健；其二，用斜分法代替传统二维Otsu法中的穷举搜索法，把计算的复杂度从二维降到一维，计算速度可大大提高。本文算法使基于二维直方图的阈值分割方法在工程中更为实用。

[1] 吴一全, 朱兆达. 图像处理中阈值选取方法30年(1962－1992)的进展(一)[J]. 数据采集与处理, 1993, 8(3)： 193-201.

[2] 吴一全, 朱兆达. 图像处理中阈值选取方法30年(1962－1992)的进展(二)[J]. 数据采集与处理, 1993, 8(4)： 268-282.

[3] Reddi S S, Rudin S F, Keshavan H R. An optimal multiple threshold scheme for image segmentation [J]. IEEE Transactions on Systems, Man, and Cybernetics, 1984, 14(4)： 661-665.

[4] 陈 果. 图像阈值分割的Fisher准则函数法[J]. 仪器仪表学报, 2003, 24(6)： 564-567.

[5] 朱晓临, 邓祥龙, 胡德敏. 多阈值选取与边缘连接的边缘检测算法[J]. 图学学报, 2012, 33(2)： 72-76.

[6] Sahoo P K, Soltani S, Wong A K C, et al. A survey of thresholding techniques [J]. Computer Vision, Graphics and Image Processing, 1988, 41： 233-260.

[7] 龚军辉, 陈爱萍, 唐勇奇, 等. 一种快速有效的虹膜图像预处理方法[J]. 图学学报, 2012, 33(4)： 93-97.

[8] Nikhil R P, Sankar K P. A review on image segmentation techniques [J]. Pattern Recognition, 1993, 26(9)： 1277-1294.

[9] Nobuyuki O. A threshold selection method from gray-level histograms [J]. IEEE Transactions on Systems, Man, and Cybernetics, 1979, 9(1)： 62-66.

[10] 刘健庄, 粟文青. 灰度图像的二维 Otsu自动阈值分割法[J]. 自动化学报, 1993, 19(1)： 101-105.

[11] Gong Jian, Li Liyuan, Chen Weinan. A fast recursive algorithm for two-dimensional thresholding [J]. Signal Processing, 1996, 2： 1155-1158.

[12] 景晓军, 蔡安妮, 孙景鳌. 一种基于二维最大类间方差的图像分割算法[J]. 通信学报, 2001, 22(4)： 71-76.

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

[14] 吴一全, 潘 喆. 2维最大类间平均离差阈值选取快速递推算法[J]. 中国图象图形学报, 2009, 14(3)：471-476.

[15] 郝颖明, 朱 枫. 2维Otsu自适应阈值的快速算法[J].中国图象图形学报, 2005, 10(4)： 484-488.

A Otsu Threshold Segmentation Method Based on Rebuilding and Dimension Reduction of the Two-Dimensional Histogram

Chen Jinwei, Wu Bing
(School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo Henan 454150, China)

The issue of poor resistance to noise and unreasonable is pointed out based on two-dimensional histogram regional straight points method. A new threshold segmentation method is proposed, and the calculation formula of the method is deduced. Firstly, in this method, noise interference weakened for threshold′s segmentation through the reconstruction of two-dimensional histogram based on detailed analysis of noise distribution in the two-dimensional histogram, and then, the region division is transfered from eight partitions into two partitions in two-dimensional histogram. Thus the two-dimension search space of threshold is reduced to one-dimension. Finally, simulation results of existing two-dimensional histogram segmentation algorithm and our method are given respectively. Theoretical analysis and experimental results show that our method could be used in nearly all the two-dimensional histogram threshold segmentation, especially in threshold segmentation with the contaminated image. It makes the inner part uniform, the edge accurate in the threshold image and has better tolerance capability to noise. The running time is significantly reduced.

image segmentation; histogram dimensionality reduction; threshold selection; Otsu algorithm

TP 317.4

A

2095-302X(2015)04-0570-06

2014-08-27；定稿日期：2014-12-19

陈金位(1990–)，男，河南安阳人，硕士研究生。主要研究方向为图像处理。E-mail：chenjwhpu@163.com

吴 冰(1964–)，男，江西萍乡人，教授，博士。主要研究方向为通信与信息系统研究。E-mail：wubing@hpu.edu.cn