基于三维指数灰度熵的快速图像分割算法

张书真，黄光亚

吉首大学信息科学与工程学院，湖南吉首 416000

基于三维指数灰度熵的快速图像分割算法

张书真，黄光亚

吉首大学信息科学与工程学院，湖南吉首 416000

1 引言

图像分割是数字图像处理中的一项关键技术，它是对图像进行视觉分析和模式识别的基本前提[1]。阈值分割因其实现简单、性能稳定而成为图像分割中最基本的分割技术[2-3]。其中，基于熵的阈值分割方法一直受到研究者的广泛关注，常见的有Shannon熵[4-5]、交叉熵[6-7]、Renyi熵[8]等，并且已有相应的二维算法[9-13]或三维算法[14-15]。上述的阈值分割法中普遍存在两个问题：一是阈值的选取仅利用到图像灰度直方图的统计信息，而未直接考虑图像类内灰度分布的均匀性；二是在推广的二维或三维算法中，由于阈值搜索范围扩大，最佳阈值的寻求过程耗时巨大。

针对上述问题，本文提出一种快速三维指数灰度熵图像分割算法。算法首先给出了指数灰度熵的定义，然后推导出三维指数灰度熵阈值分割的原理，并利用降维处理和优化搜索策略的方法快速获取最佳阈值，使得阈值搜索复杂度降为O(L1/2)。由于指数灰度熵同时考虑了直方图的统计信息和图像类内灰度分布的均匀性，图像分割亦取得了较好的效果。

2 三维指数灰度熵阈值分割算法

2.1 三维直方图

设一幅图像的灰度级为L，其三维直方图的三个坐标轴分别表示图像像素的灰度值i、邻域均值j和邻域中值k，直方图中任意一点的值表示三元组(i，j，k)发生的频数g(i，j，k)，其中0≤i，j，k≤L-1。以lena图为例，其三维直方图如图1（b）所示，由于图像目标和背景内像素的灰度值、邻域均值和邻域中值十分接近，图像大部分的像素点集中在直方图的对角线附近，而少量的边缘点和噪声点将分布于直方图中远离对角线的区域。

图1 lena图与其三维直方图

2.2 一维指数灰度熵阈值法

指数熵[16]的定义是PAL在1989年提出的，它能克服Shannon熵出现的无定义和零值问题，但是和现有的大部分阈值法一样，指数熵仅利用了直方图的统计信息，而忽略了图像类内分布的均匀性，为此考虑引入指数灰度熵的概念进行图像分割。

设一幅图像灰度级数目为L，图像中灰度为l的像素数目记为g(l)，阈值s将图像划分为目标类Co和背景类Cb，设低灰度区为目标类，高灰度区为背景类，令

2.3 三维指数灰度熵阈值法

在三维直方图中，若(s，t，q)为阈值分割点，忽略掉远离直方图对角线上的分布点，可得目标类指数灰度熵为：

3 降维处理和搜索策略的优化

3.1 三维指数灰度熵法的降维处理

三维阈值法能够有效提高一维阈值法的抗噪性能，但阈值搜索空间的扩展也使得计算复杂度以指数级方式大幅攀升。文献[17]针对二维Otsu方法，在忽略直方图中远离对角线的噪声点和边缘点的前提下，提出求解两个一维Otsu阈值来代替原始二维Otsu阈值的方法，使计算复杂度降低到O(L)。文献[18]通过对三维Otsu进行分解，使计算复杂度降低到O(L)。基于类似思想，推导出三维指数灰度熵的降维公式。

在三维直方图中，令像素灰度值、邻域均值、邻域中值的边缘频数为F(i)、V(j)、R(k)，则

F(i)、V(j)、R(k)也可以认为是原图像、邻域均值图像、邻域中值图像的灰度直方图。

设三维直方图中远离对角线分量近似为0，则有：

由式（20）和式（21）可知，通过降维处理，最佳三维阈值的计算复杂度降至O(L)。

3.2 搜索策略的优化

在降维处理的基础上，本文考虑一种阈值搜索的优化策略，使算法的计算复杂度进一步降低。优化搜索策略的流程框图如图2所示。

图2 优化搜索策略的流程框图

步骤1设图像总的灰度级为L，在三维直方图上将各

步骤3利用降维方式先在缩小的三维直方图上寻找到初始阈值(s1，t1，q1)，并由该点求得对应的原三维直方图小区域为ψs1t1q1，其坐标轴取值范围为s1m≤i≤(s1+1)m-1，t1m≤j≤(t1+1)m-1，q1m≤k≤(q1+1)m-1。

步骤4利用降维方式在ψs1t1q1区域上搜索，得到最终阈值(s2，t2，q2)。

利用上述优化搜索策略，可知计算复杂度满足：坐标取值范围均分为n段，每段有m=L/n个灰度级，则三维直方图空间被分成n×n×n的多个小区域，设小区域记为ψxyz，其中0≤x，y，z≤n-1。

步骤2将每个小区域由一个点来代替，则原三维直方图缩小为n×n×n的三维直方图，该直方图中每一点的值表示三元组(x，y，z)发生的频数，即有：

当n=L1/2时，计算复杂度最小，为O(L1/2)，可见采用优化搜索策略可进一步减少运算时间。

4 实验结果及分析

仿真实验是在AMD Athlon II X4 640，3.01 GHz CPU和内存3.25 GB的微处理器上进行的，编程环境为Matlab7.9。实验分别采用文献[9]中二维Shannon熵斜分法、文献[10]中二维交叉熵递推法、文献[18]中三维Otsu分解法以及本文提出的算法对多幅图像进行阈值分割。现选取其中三幅图像加以说明，如图3所示，原图像分别是混有高斯噪声和椒盐噪声的lena图、月亮图以及怀表图，各算法分割效果如图4～图7所示。

图3 原图像

图4 文献[9]算法结果

图5 文献[10]算法结果

图6 文献[18]算法结果

图7 本文算法结果

从lena图分割效果来看，本文算法得到的lena的脸部和肩部噪声干扰是最少的，说明本文算法在抗噪性能上要优于其他三种阈值分割算法。从月亮图和怀表图的分割结果来看，由于本文算法兼顾了图像直方图的统计信息和图像类内灰度分布的均匀性，图像分割效果也是最优的。例如在月亮图的分割中，文献[9]的算法不能很好地分割出图像中月亮的总体轮廓，而文献[10]的算法和文献[18]的算法则不能很好地分割出月亮上的灰度变化区域，综合来看，本文算法兼顾了月亮轮廓和月亮内部灰度变化区域，总体上分割的视觉效果是最优的。对于怀表图的分割，本文的算法和文献[10]的算法都取得了比较好的分割效果，在分割出怀表的同时，图像右下方的标尺上的细节也能清楚地分割得到，但本文算法在运算速度上又具有明显的优势。

表1和表2给出了各种算法得到的阈值和运行时间的比较，从表中可以看出，与上述文献所提出的各种算法相比，本文算法的运算速度提升明显，由于将降维处理和优化搜索策略相结合，相对于其他算法中所需时间最少的三维Otsu分解法，本文算法运算时间也至少减少了20%以上。

表1 不同算法获得的阈值比较

表2 不同算法获得的运行时间比较s

5 结束语

本文提出的指数灰度熵阈值分割法，既考虑了图像直方图的统计信息，也反映出图像中目标和背景类内的灰度分布的均匀性。为了提高抗噪能力，将该算法推广运用到三维直方图上。由于三维直方图的搜索空间复杂度提高到O(L3)，论文采用降维处理与优化阈值搜索策略相结合的方法，将搜索复杂度降为O(L1/2)。通过对多幅图像进行分割的实验表明，本文提出的算法抗噪性能更好，分割效果更优，且运行时间大为减少。

[1]王爱民，沈兰荪.图像分割研究综述[J].测试技术，2000，19（5）：1-6.

[2]Sezgin M，Sankur B.Survey over image thresholding techniques and quantitative performance evaluation[J].Journal of Electronic Imaging，2004，13（1）：146-168.

[3]曹建农.图像分割的熵方法综述[J].模式识别与人工智能，2012，25（6）：958-971.

[4]唐新亭，张小峰，邹海林.图像分割的最大熵方法的改进[J].计算机工程与应用，2012，48（1）：212-215.

[5]张俊娜，冯云芝.基于量子最大熵多阈值算法的图像分割研究[J].激光与红外，2013，43（5）：578-582.

[6]曹建农.基于直方图重构的极大交叉熵图像分割方法[J].计算机应用，2008，44（18）：177-180.

[7]周理，高山，毕笃彦，等.基于视觉侧抑制机理的强鲁棒性图像分割方法[J].中南大学学报：自然科学版，2013，44（5）：1910-1917.

[8]聂方彦，屠添翼，潘梅森，等.红外人体图像模糊Renyi熵快速分割[J].计算机工程与应用，2013，49（7）：183-186.

[9]吴一全，潘喆，吴文怡.二维直方图区域斜分的最大熵阈值分割算法[J].模式识别与人工智能，2009，22（1）：162-168.

[10]雷博，范九伦.灰度图像的二维交叉熵阈值分割法[J].光子学报，2009，38（6）：1572-1576.

[11]Sahoo P K.A thresholding method based on two-dimensional Renyi’s entropy[J].Pattern Recognition，2004，37（6）：1149-1161.

[12]Sahoo P K，Arora G.Image thresholding using two-dimensional Τsallis-Havrda-Charvat entropy[J].Pattern Recognition Letters，2006，27（6）：520-528.

[13]张晓杰，吴一全，吴诗婳.基于分解的二维指数交叉熵图像阈值分割[J].信号处理，2011，27（4）：546-551.

[14]龙建武，申铉京，魏巍，等.一种结合纹理信息的三维Renyi熵阈值分割算法[J].小型微型计算机系统，2011，32（5）：947-952.

[15]王菲菲，龚劬，倪麟，等.基于三维直方图重建和降维的Renyi熵阈值分割算法[J].计算机应用研究，2013，30（4）：1223-1225.

[16]Pal S K，Pal N R.Entropic thresholding[J].Signal Processing，1989，16（2）：97-108.

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

[18]龚劬，倪麟，唐萍峰.基于分解的三维Otsu图像分割快速算法[J].计算机应用，2012，32（6）：1526-1528.

ZHANG Shuzhen,HUANG Guangya

School of Information Science and Engineering,Jishou University,Jishou,Hunan 416000,China

In view of the existing threshold segmentation methods which usually only consider the statistical information from image histogram,while ignoring the gray distribution uniformity of the image target class and the background class,one-dimensional exponential gray entropy segmentation algorithm is put forward and three-dimensional exponential gray entropy segmentation algorithm is deduced.Τhe principles of one-dimensional exponential gray entropy algorithm and three-dimensional exponential gray entropy algorithm are presented.Τhe optimum segmentation threshold is got by combining dimension reduction and optimal search strategy on the three-dimensional histogram.Τhe search complexity is reduced fromO(L3)toO(L1/2)in theory.Experimental results show that,compared with other existing threshold algorithms,the proposed algorithm has better anti-noise performance, segmentation effect and its operation time is reduced greatly.

threshold segmentation;three-dimensional histogram;exponential gray entropy;dimension reduction method; search strategy

针对现有阈值分割法通常只考虑图像直方图的统计信息，而忽略了图像目标和背景类内灰度分布的均匀性，提出指数灰度熵分割算法，并推广得到三维指数灰度熵分割算法。给出了一维指数灰度熵阈值法及三维指数灰度熵阈值法的原理，在三维直方图上，将降维处理和优化搜索策略相结合，得到最优分割阈值。理论证明，阈值搜索复杂度由原来的O(L3)降至O(L1 2)。实验结果表明，与现有的多种阈值法相比，所提算法抗噪性能更强、分割效果更优，且运算时间大为减少。

阈值分割；三维直方图；指数灰度熵；降维处理；搜索策略

A

ΤP391.41

10.3778/j.issn.1002-8331.1307-0052

ZHANG Shuzhen,HUANG Guangya.Fast image segmentation algorithm based on three-dimensional exponential gray entropy.Computer Engineering and Applications,2013,49（21）：119-122.

国家自然科学基金（No.61262032）；湖南省教育厅科学研究项目（No.12C0314）。

张书真（1977—），女，讲师，研究领域为图像处理、模式识别、网络编码；黄光亚（1981—），女，讲师，研究领域为信号处理、模式识别。E-mail：sunny_zsz@126.com

2013-07-04

2013-08-09

1002-8331（2013）21-0119-04