快速递归多阈值分割算法
申铉京1,2, 张赫1,2, 陈海鹏1,2, 王玉1,2,3
1.吉林大学 计算机科学与技术学院,长春 130012
2.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012
3.吉林大学 应用技术学院,长春 130012
通讯作者:陈海鹏(1978),男,副教授,博士.研究方向:图像处理与模式识别,多媒体信息安全.E-mail:chenhp@jlu.edu.cn

作者简介:申铉京(1958-),男,教授,博士生导师.研究方向:图像处理与模式识别,多媒体信息安全,智能控制技术.E-mail:xjshen@jlu.edu.cn

摘要

针对强调波谷邻域算法在目标区域相对于背景区域较小且其之间的波谷特征并不十分明显的情况下,无法获得正确阈值的问题,提出了一种基于波谷邻域信息和波谷波峰相对特征的全局阈值分割算法.本算法在最大类间方差(OTSU)算法的基础上以直方图中波谷邻域灰度值和波谷波峰灰度值的相对关系为权值,改善最大类间方差算法定位阈值的准确性,使算法所确定的阈值在直方图中具有较小的波谷波峰比值,即使最优阈值定位到与临近波峰具有较大高度差的波谷灰度值.为提高分割效率,本文以前述算法为基础,采用递归单阈值方式进行图像的多阈值分割.实验证明,对强调波谷邻域算法存在的问题本算法有明显的改善,且在多阈值分割的效果及运行时间方面本文算法均具有十分良好的表现.

关键词: 计算机应用; 图像分割; 多阈值分割; 递归; 最大类间方差算法; 波谷
中图分类号:TP391 文献标志码:A 文章编号:1671-5497(2016)02-0528-07
Fast recursive multi-thresholding algorithm
SHEN Xuan-jing1,2, ZHANG He1,2, CHEN Hai-peng1,2, WANG Yu1,2,3
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China
2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
3.College of Applied Technology,Jilin University, Changchun 130012, China
Abstract

The Neighborhood Valley-emphasis method can not get the right threshold value in some cases, such as the valley feature between the target and background is not very distinct. In order to solve this problem, a global thresholding method is proposed. This method is based on the gray information around the valley-point neighborhood and the relative characteristics between the valley point and its adjacent crest-point. The proposed method weights the objective function with the gray information around the valley-point neighborhood and the relation between the valley-point and its adjacent crest-point. It improves the accuracy of the threshold obtained by OTSU. The optimal threshold got by the proposed method has less valley-to-crest ratio. In other word, the valley gray is taken as the optimal threshold, which has larger height difference with it adjacent crest-point. In order to improve the efficiency, a recursive single threshold method based on the aforesaid algorithm is used to achieve the image multi-threshold segmentation. Experiment results show that the proposed method has great segmentation performance and low time complexity.

Keyword: computer application; image segmentation; multilevel thresholding; recursion; OTSU method; valley point
0 引 言

图像分割技术在计算机视觉, 医学图像处理及模式识别等领域中都有着十分广泛的应用, 通过图像固有的纹理, 梯度和灰度值分布等信息, 将感兴趣的目标从背景中提取出来, 以便进行场景分析和目标识别.其中阈值分割算法以其简单性, 有效性等特点得到了广泛的研究与应用[1, 2].在众多的阈值分割算法[3, 4, 5, 6, 7]中, 最大类间方差(OTSU)算法[8]由于其简单的原理及良好的分割效果, 受到了众多的关注, 其通过在图像直方图中最大化所分得的各类的类间方差或最小化各类的类内方差来筛选最优阈值.OTSU算法所获取的最优阈值等于直方图中该阈值所分成的两部分各自的平均灰度值的均值[9], 这一特性就使得OTSU算法对于图像像素的直方图符合双峰或近似双峰分布等多种情况, 能够取得较为良好的分割效果, 而对于单峰及近似单峰分布的情况, 或者目标和背景的方差区别较大等一些情况, 则无法获得合适的阈值.因此, Morii[10], Hou[11], Ng[12]和龙建武等[13]提出了相应的改进算法.

Ng[12]提出的强调波谷的阈值分割算法, 将阈值灰度值在图像中的出现概率(即阈值在图像直方图中的高度信息)作为权值加入到OTSU目标公式中, 使得选取的阈值更趋向于直方图中的波谷灰度值, 出色地解决了图像直方图单峰或近似单峰分布情况下的阈值分割问题.Fan等[14]在Ng的基础上, 引入了对直方图中阈值邻域内的灰度值分布情况的考虑, 提出了强调波谷邻域算法, 解决了强调波谷阈值分割算法针对图像直方图中目标方差与背景方差差异较大的情况所获取的阈值不准确的问题.但是, 强调波谷算法和强调波谷邻域算法都只是考虑了图像直方图中波谷灰度值在图像中的出现频率对阈值的影响, 并未考虑到波谷灰度值在直方图中与其左右临近的波峰之间的相对关系, 使得在一些情况下, 特别是目标灰度值相对于背景灰度值在图像中的出现频率较低, 即图像直方图中目标对应的整体高度相对于背景更趋近与零, 目标与背景间的波谷特征并不十分明显的情况下, 所获取的灰度值不够准确, 无法将目标从背景中分割出来.

本文算法在强调波谷邻域算法[14, 15]的基础上, 加入了与直方图中波谷和波峰相对关系有关的因子, 使得上述问题得以解决, 并采用递归方式进行多阈值分割, 在保证了阈值定位准确性的同时, 取得了较高的算法运行效率.本文采用伯克利图像库[16]及脑部MRI图像进行实验, 充分验证了算法的有效性与实用性.

1 相关研究基础

将一幅大小为M× N, 灰度级为L的数字图像I表示成其像素集合的形式, 即I={pixel1, pixel2, , et al., pixeli, , et al., pixelM× N}, pixeli 代表I中的第i个像素的灰度值, pixeli∈ [0, 1, 2, , et al., L-1], 则图像中灰度值为l的像素点的个数表示为n(l), 灰度值为l的像素点在图像中出现的频率可定义为:

hl=nl/M×N, l=0, 1, 2, , L-1(1)

图1所示的单阈值情况为例, 阈值t将图1中直方图所对应的图像像素点分成s1和s2两类, 则s1和s2两部分所对应的概率分别表示为:

p1t=l=0thl(2)

p2t=l=t+1L-1hl(3)

s1和s2两部分的均值就可以由如下公式求得:

u1t=l=0tl·hl/p1t(4)

u2t=l=t+1L-1l·hl/p2t(5)

同理, 整幅图像的均值为:

uht=l=0L-1l·hl(6)

由式(2)~(6)得:

uht=u1tp1t+u2tp2t(7)

因此, 可以将图像的最大类间方差(OTSU)公式做如下简化:

σB2t=p1tu1t-uht2+p2tu2t-uht2=p1tu12t+p2tu22t(8)

图1 单阈值示意图Fig.1 Legend of single thresholding

针对直方图单峰及近似单峰分布的情况, Ng[10]提出了强调波谷的OTSU改进算法, 认为图像分割的最优阈值应该是图像直方图中处于波谷位置的灰度值, 所以在原始OTSU的目标公式中添加了与图像中灰度值出现频率 h(l)(即直方图中相应灰度值的高度)有关的权值, 改进算法的目标公式如下:

σB2t=1-htp1tu12t+p2tu22t(9)

Fan等[12]在强调波谷算法的基础上, 加入了对直方图中阈值邻域的考虑, 增强了目标公式中权值部分对类间方差部分的影响程度, 使得目标方差和背景方差差异较大情况下的阈值定位更为准确.具体的公式表述如下:

σB2(t)=1-h-(t)p1(t)u12(t)+p2(t)u22t(10)

其中 h-(t)的定义如下:

h-(t)=[ht-m++ht-1+h(t)+ht+1++ht+m](11)

h-(t)代表灰度值t的出现频率h(t), 以及图像直方图中灰度值t的大小为2m+1的邻域内所有灰度值的出现频率之和.最优阈值即为使目标公式(10)取得最大值的灰度值:

to=Argmax0t255σB2t=Argmax0tL-1{[1-h-(t)][p1(t)u12(t)+p2(t)u22(t)]}(12)

由以上的描述中能看出, 强调波谷邻域算法可以很容易扩展成多阈值分割算法.

to1, to2, , toM=Argmax0< to1< to2< < toM< L-11-s=1Mh-sk=1M+1pkuk2(13)

强调波谷邻域算法所引入的权重只考虑了直方图中波谷灰度值在图像中的出现概率, 即波谷灰度值在直方图中的高度, 使得算法所选取的最优阈值不够准确, 导致图像分割结果在边缘细节上有瑕疵.此外, 如图2所示, 当目标灰度值相对于背景灰度值在图像中的出现频率较低, 即图像直方图中目标对应的整体高度相对于背景更趋近于零, 目标与背景间的波谷信息并不十分明显时, 前述算法所选取的阈值无法将目标与背景分割.

图2 伯克利图像库[13]中图片分割结果Fig.2 Segmentation results of the picture in [13]

2 本文算法

针对上述问题, 本文在强调波谷邻域算法[12]的基础上, 进一步发掘直方图中波谷点的特征, 最优阈值所对应的波谷点不单纯是图像中具有较低出现频率的灰度值.因为图像中目标与背景的边界灰度值的出现频率可能受环境, 光照, 目标或背景形状的影响, 使得边界灰度值相比于图像中的噪声, 目标或背景的纹理等灰度值具有更高的出现频率.所以, 本文所要寻找的最优阈值, 应当是图像中与目标和背景整体灰度值相比具有相对较低出现频率的灰度值.为此, 本文引入了表示直方图中波谷灰度值同其左右邻近波峰灰度值关系的变量, 以提高波谷定位的准确性.

2.1 预处理

全局阈值分割的目的就是在图像对应的灰度直方图中找到合适的波谷阈值, 将目标像素同背景像素区分开来.由此可见, 本文所要寻找的最优分割阈值就是直方图中所有波谷点中的一个或多个.因此, 本文算法在进行递归多阈值分割前首先对候选阈值(波谷灰度值) i进行简单筛选:

{i, hihi-1hi< hi+1hi< hi-1hihi+1, i0, L-1}(14)

h(i)表示灰度值i在图像中的出现频率, 这样在后续的处理中就可以避免对非候选灰度值的冗余处理, 从而提高处理效率和质量.同时, 为方便后续算法对于波谷和邻近波峰关系的计算, 同样通过预处理筛选出直方图中的波峰灰度值 j:

{j, hjhj-1hj> hj+1hj> hj-1hjhj+1, j0, L-1}(15)

2.2 强调相对波谷算法

通过进一步发掘图像直方图的分布特点, 将波谷灰度值的出现频率以及波谷与其邻近波峰灰度值的相对出现频率一同构成阈值选取的权值项, 作用于直方图的类间方差, 使目标公式的最优解趋向于相对于邻近波峰具有更小出现频率的波谷灰度值, 即那些相对高度更低的波谷灰度值, 使分割结果更为准确.

强调相对波谷算法的目标公式如下:

σB2(t)=1-v(t)[p1(t)u12(t)+p2(t)u22(t)](16)

vt=h-t×2hthcrestLt+hcrestRt(17)

式中:h(crestL (t))和h(crestR(t))分别为灰度值t在直方图中左, 右相邻的波峰灰度值对应的出现频率; 2h(t )⁄[ h(crestL(t))+h(crestR(t))]表示波谷灰度值t在直方图中相对其左右相邻波峰的均值的比值, 若灰度值t不具有相邻的左波峰或右波峰, 则将其不具有的波峰灰度值取值为t本身.

最优阈值即为使式(16)取得最大值的灰度值to:

to=Argmax0tL-1σB2(t)=Argmax0tL-11-v(t)p1(t)u12(t)+p2(t)u22(t)(18)

多阈值分割的目标公式为:

to1, to2, , toM=Argmax0< to1< to2< < toM< L-11-s=1Mvsk=1M+1pkuk2(19)

2.3 递归多阈值分割算法

以OTSU为基础的多阈值分割算法通常都是预先给出目标图像的阈值数, 然后采用遍历枚举的方式筛选出目标公式的一组最优解, 这样就会使得算法的运行时间随着阈值数的增加呈指数增长, 即使采取一定的预处理, 算法整体的运行时间依然很长.因此, 本文以式(18)为目标公式, 使用递归单阈值方式进行阈值选取, 在保证阈值定位准确性的同时, 提高了算法效率, 且无需预先给出阈值数目.

下面给出递归多阈值分割算法流程:

Step1 采用2.1节中所述的预处理方法, 筛选出波谷值t, 及其左右相邻的波峰值crestL(t)和crestR(t), 确定阈值的值域[start, end], 初始为[0, L-1].

Step2 在值域[start, end]内, 利用式(18)选取最优阈值 to, to等于取值域的边界灰度值, 即start或者end, 则取值域内的灰度值属于同一类, 无需分割, 退出递归.若 to为取值域内的其他灰度值, 则 to将取值域分为[start, to]和[to, end]左右两部分, 再在左右两部分中分别进行分割.

Step3 在值域[start, to]和[to, end]内取得子阈值分别为toltor, 比较值域[start, end]内3个阈值to, toltor的下列组合, 即{to}, {to, tol}, {to, tor}, {to, tol, tor}, 从中选取满足式(19)的组合, 即最优的阈值集合.

3 实验结果及分析

本文实验平台为Intel Celeron 2.60 GHz CPU, 3G memory以及Matlab 2010b.为了准确验证本文算法的效果, 实验分为两部分.第一部分为单阈值实验, 使用Fan等[12]论文中的图片以及伯克利图像库[13]中200幅图像进行试验, 对本文算法和强调波谷邻域算法[12]的分割效果进行对比; 第二部分为多阈值实验, 采用脑部MRI图像进行对比分析.

由于本文算法所引入的权值项中含有波谷灰度值邻域内灰度值的出现频率信息, 所选取的邻域大小将会对分割结果产生影响, 因此, 对于实验中的所有图像, 在不同邻域大小下分别进行实验对比, 表2中仅列出了部分图像在不同邻域大小下的分割结果.3.3节中将会给出具体的实验分析, 结果表明, 邻域大小为7时, 实验中的所有图像均能取得理想的分割结果.

3.1 单阈值分割实验

本文对图3(a)所示的Fan等论文中图片以及伯克利图像库中的200幅图像进行实验对比.实验结果表明, 本文对图3(a)中图像的分割效果与原文结果基本一致; 而对伯克利图像库中200幅图像分割效果相比于强调波谷邻域算法有一定提高:其中62幅图像本文算法与文献[12]算法所确定的阈值相同; 其中102幅图像本文算法相比于文献[12]算法所确定的阈值更为准确; 其中36幅图像本文算法准确分割而文献[12]算法分割失败.图4(a)为伯克利图像库中200幅图像中的一幅, 可以看出, 本文算法针对目标灰度值整体的出现频率远远小于背景灰度值, 且目标与背景之间的波谷灰度值并不十分明显的情况, 依然能够取得较为满意的阈值结果.

图3 文献[12]中图片的分割结果Fig.3 Segmentation result of the picture in the algorithm[12]

图4 伯克利图像库[13]中图像的分割结果Fig.4 Segmentation result of the picture in [13]

图5 脑部MRI图像三阈值分割结果Fig.5 Segmentation results of MRI brain image with three threshold values

3.2 多阈值分割实验

多阈值实验中, 选取了50幅脑部MRI图像进行分割效果对比, 图5(a), 图6(a)为其中两幅脑部MRI图像.对于图5(a)的脑部MRI图像, 本文算法自动确定的最优阈值数为3, 分割后的效果及相应的阈值如图5(c), 图5(e)所示, 将强调波谷邻域算法的分割阈值数设置为3, 其分割结果及阈值如图5(b), 图5(d)所示.由分割结果可以看出, 本文算法所确定的阈值能够更好地区分脑部MRI图像的各个部分.对于图6(a)中的脑部MRI图像, 本文算法自动确定的最优阈值数为4, 将强调波谷邻域算法的阈值数设置为4, 其分割效果分别如图6(c)和图6(b)所示, 相应的阈值结果如图6(e), 图6(d)所示.其结果表明, 对于图像中的异常区域, 强调波谷邻域算法分割失败, 而本文算法所获得的阈值取得了较为良好的分割效果, 且在多阈值分割效率方面, 本文算法具有明显提升.表1为多阈值分割实验的阈值结果及运行时间的统计结果, 可以看出本文算法在阈值定位准确性和效率方面均有十分优秀的表现.

图6 脑部MRI图像四阈值分割结果Fig.6 Segmentation results of MRI brain image with four threshold values

表1 多阈值实验中所获得的阈值及运行时间统计 Table 1 Statistics of threshold values and time-consumings in the multi-threshold experiments
3.3 邻域大小对分割结果的影响

本文算法以 1-v(t)为权值项作用于直方图中阈值所分得各类的类间方差, 通过最大化目标公式的值选取最优阈值, 其中, 由式(11)(17)可以看出, 权值项的值与波谷灰度值的邻域大小有关.为此, 本文对实验中的所有图片进行了不同邻域大小下的分割比较, 以选取使算法取得最优阈值的邻域大小.这部分实验中, 分别在3, 5, 7, 9, 11, 35, 105的邻域大小下进行分割比较.结果表明, 当邻域大小为3时, 算法所获得的阈值并不十分准确, 随着邻域的增大, 所获得的结果趋近于理想阈值, 但当邻域大小过大时, 所获得的结果无法将图片正确分割.例如, 在单阈值实验中, 图4在邻域大小为5时, 取得理想阈值47, 在邻域为35时, 获得的阈值159无法将目标正确分割; 在多阈值实验中, 随着邻域增大, 算法所确定的最优阈值数会相应减少, 且当邻域过大时, 所得出的阈值也并不准确, 对图7而言, 当邻域大小为7时, 算法获得理想阈值结果, 而当邻域为105时, 所得阈值只有一个.这表明对于不同图像而言, 使算法取得最优阈值结果的邻域大小也并不相同, 但是, 当邻域大小在一定范围内时, 不同图像各自获得的阈值十分近似, 例如, 对表2中所示的4幅图像, 其各自在邻域大小为7至11之间取得稳定结果.根据实验中所有图像的分割效果, 邻域大小为7时, 算法对各图像的分割结果最为理想.

表2 不同邻域大小下本文算法的阈值结果 Table 2 Different threshold results of the proposed method using different neighborhood lengths
4 结束语

提出了一种改进的OTSU分割算法, 在强调波谷邻域算法的基础上, 引入了直方图中波谷灰度值同其左右邻近的波峰灰度值之间的相对关系, 有效地改善了分割结果的边界细节, 以及某些目标与背景灰度值在直方图中的波谷界限比较模糊的图像的分割结果.采用递归方式进行多阈值分割, 在保证了阈值定位准确性的同时, 有效地提高了算法效率, 但本文算法对非均匀光照图像以及噪声较大图像的分割效果还有待提升, 因此, 针对非均匀光照和噪声等因素的优化将会是后续研究工作的重点.本文通过大量的实验对比, 验证了算法的合理性及有效性.

The authors have declared that no competing interests exist.

参考文献
[1] Sahoo P K, Soltani S, Wong A K C. A survey of thresholding techniques[J]. Computer Vision, Graphics, and Image Processing, 1988, 41(2): 233-260. [本文引用:1]
[2] Sezgin M. Survey over image thresholding techniques and quantitative performance evaluation[J]. Journal of Electronic Imaging, 2004, 13(1): 146-168. [本文引用:1]
[3] Xue J H, Zhang Y J. Ridler and Calvard's, Kittler and Illingworth's and Otsu's methods for image thresholding[J]. Pattern Recognition Letters, 2012, 33(6): 793-797. [本文引用:1]
[4] Yimit A, Hagihara Y, Miyoshi T, et al. 2-D direction histogram based entropic thresholding[J]. Neurocomputing, 2013, 120: 287-297. [本文引用:1]
[5] 魏巍, 申铉京, 千庆姬, . 三维最大Renyi熵的灰度图像阈值分割算法[J]. 吉林大学学报: 工学版, 2011, 41(4): 1083-1088.
Wei Wei, Shen Xuan-jing, Qian Qing-ji, et al. Thresholding algorithm based on threedimensional Renyi's entropy[J]. Journal of Jilin University(Engineering and Technology Edition), 2011, 41(4): 1083-1088. [本文引用:1]
[6] 巢渊, 戴敏, 陈恺, . 基于广义反向粒子群与引力搜索混合算法的多阈值图像分割[J]. 光学精密工程, 2015, 23(3): 879-886.
He Zhi-yong, Sun Li-ning, Huang Wei-guo, et al. Thresholding segmentation algorithm based on Otsu criterion and line intercept histogram[J]. Optics and Precision Engineering, 2012, 20(10): 2315-2323. [本文引用:1]
[7] 陈恺, 陈芳, 戴敏, . 基于萤火虫算法的二维熵多阈值快速图像分割[J]. 光学精密工程, 2014, 22(2): 517-523.
Chao Yuan, Dai Min, Chen Kai, et al. Image segmentation of multilevel threshold using hybrid PSOGSA with generalized opposition-based learning[J]. Optics and Precision Engineering, 2014, 22(2): 517-523. [本文引用:1]
[8] Otsu N. A threshold selection method from gray-level histograms[J]. Automatica, 1975, 11(285-296): 23-27. [本文引用:1]
[9] Xu X, Xu S, Jin L, et al. Characteristic analysis of Otsu threshold and its applications[J]. Pattern Recognition Letters, 2011, 32(7): 956-961. [本文引用:1]
[10] Morii F. An image thresholding method using a minimum weighted squareddistortion criterion[J]. Pattern Recognition, 1994, 28(7): 1063-1071. [本文引用:2]
[11] Hou Z, Hu Q, Nowinski W L. On minimum variance thresholding[J]. Pattern Recognition Letters, 2006, 27(14): 1732-1743. [本文引用:1]
[12] Ng H F. Automatic thresholding for defect detection[J]. Pattern Recognition Letters, 2006, 27(14): 1644-1649. [本文引用:9]
[13] 申铉京, 龙建武, 陈海鹏, . 三维直方图重建和降维的Otsu阈值分割算法[J]. 电子学报, 2011, 39(5): 1108-1114.
Shen Xuan-jing, Long Jian-wu, Chen Hai-peng, et al. Otsu thresholding algorithm based on rebuilding and dimension reduction of the 3-dimensional histogram[J]. Acta Electronica Sinica, 2011, 39(5): 1108-1114. [本文引用:2]
[14] Fan J L, Lei B. A modified valley-emphasis method for automatic thresholding[J]. Pattern Recognition Letters, 2012, 33(6): 703-708. [本文引用:2]
[15] 张健, 李宏升. 基于图论阈值算法的图像分割研究[J]. 液晶与显示, 2014, 29(4): 592-597.
Zhang Jian, Li Hong-shengl. Image mosaic research based on wavelet and rough set algorithm[J]. Chinese Journal of Liquid Crystal and Displays , 2014, 29(4): 592-597. [本文引用:1]
[16] Berkley Image Database[EB/OL]. [2013-11-12]. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/. [本文引用:1]