基于最小类内差和最大类间差的图像分割算法研究

吴 昊1，汪荣贵2，方 帅2，杨万挺2



基于最小类内差和最大类间差的图像分割算法研究

吴 昊，汪荣贵，方 帅，杨万挺

（1. 合肥师范学院计算机科学与技术系，安徽合肥 230061；2. 合肥工业大学计算机与信息学院，安徽合肥 230009）

针对现有二维Otsu图像分割算法未考虑到目标和背景这二类像素自身的内聚性，提出一种新的自适应二维Otsu算法。该算法通过待分割图像的二维直方图，分别统计类内的绝对差、类间总体离差以反映类内、类间的离散度，从而构造出新阈值判别函数。通过一种改进的遗传算法优化二维阈值判别函数，自动得到较理想的分割阈值。实验结果表明，与其它阈值判别函数相比，通过优化新的阈值判别函数得到的二维阈值，具有了较好的分割效果，能够更好地保留了目标物的轮廓，而且计算量小。

图像分割；二维Otsu法；阈值判别函数；类内最小差；类间最大差

图像分割是图像进一步分析和理解的基础，是实现图像按特性分成互不重叠的不同区域的过程，实现这一过程常使用阈值法。最大类间方差算法（Otsu算法）就是一种经典的基于阈值的图像分割方法，其基本思想是通过对图像的灰度直方图的统计，计算出目标和背景的最大类间方差值，由此确定图像的分割阈值。最初的Otsu算法基于一阶直方图，方法简单、实时性好，因而得到广泛的应用。然而，当图像中的目标和背景的灰度区别不明显时，应用此方法分割会使图像的信息丢失，出现比较严重的分割错误。为此，文献[4]提出了一种通过使用二维直方图的来确定阈值的算法，即二维Otsu图像分割算法。该方法既包含了像素的灰度信息，又包含了像素的邻域空间信息，相比一维Otsu算法具有更好的分割效果。然而，计算复杂程度较高，并且阈值选择标准仅单方面考虑类间方差，未考虑到目标和背景这二类像素的自身内聚性，因而常导致分割后目标轮廓的细节比较模糊，而且该算法运行时间长，自适应性差。

很多学者对文献[4]提出的算法进行了改进，如文献[5-6]针对二维直方图进行了修正，对目标区域和背景区域进行重新划分，文献[7]也对类内的离散测度进行了考虑，但是增加了公式的复杂性，使得计算量加大。文献[8]把二维Otsu算法推广到三维，阈值判别函数的推导过程较繁琐，算法时间代价也是较大的。

本文提出一种新的自适应二维Otsu算法。该算法设计了一种新的阈值识别函数，使得对像素的分类不但考虑到类间方差的最大性，而且考虑了类内像素的内聚性；并且计算大都基于绝对值，减少了运算的复杂度。通过提出并使用一种改进的遗传算法不断优化二维阈值识别函数，自动得到较理想的分割阈值，实现算法的自适应性。实验结果表明，应用本文提出阈值识别函数，其分割效果能够保留较清晰地目标物轮廓细节，而且计算量较小。

1 二维最大类间方差法

二维最大类间方差法是一种二维阈值分割方法，原理如下：假设原图像的灰度等级为，大小为，则图像中的每个像素点的值对应于一个灰度级，扫描整幅图像，计算图像中的每个像素点的邻域灰度值，得到一幅平滑图像，显然的灰度等级也为。设表示图像中像素点的灰度值为，其邻域平均灰度值为的像素点出现的次数，由此得到该图像点灰度值－邻域灰度值的二维直方图。那么二维联合概率密度

图1表示某一幅图像的二维直方图，图2中是其对应的平面投影图，轴表示每个像素点的灰度值，轴表示每个像素点的灰度邻域平均值。点灰度值和其邻域灰度均值差别不是很大，因而大都集中在对角线附近。远离对角线的灰度对可以看成是对应图像的噪声和边缘点。

图1 一幅图像的二维直方图

图2 二维灰度直方图的平面投影图

（4）

在绝大多数情况下，噪声和边缘点的概率非常的小，对应于图2中的区域II和IV。它们的概率可近似看成是0，这样就可以认为，此时和这两类对应的均值矢量为

（6）

总体均值为

定义离散度矩阵

用离散度矩阵的迹作为背景和目标类的离散度的测度

当这个离散度矩阵的迹为最大值时取得的分割阈值就为最优的阈值，即

（10）

2 新的阈值识别函数构造方法

上述二维Otsu法所用的阈值识别函数（即离散度矩阵的迹）只考虑到目标类和背景类的方差大小，也就说类间的方差越大，分割的效果越好。然而，上述算法的通过离散度矩阵并计算其迹来反映背景类和目标类之间的离散度测度，可以看出式(8)、式(9)有多次平方的运算，复杂度较高，计算非常耗时；同时算法也没有考虑到其目标类和背景类的每类自身像素的分类信息，也就是说没有考虑类内的内聚性。为此本文在不增加计算量的基础上设计一种新的阈值识别函数来取代离散度矩阵的迹这种离散度测度。

绝对差和平均离差是各数值相对于平均数的离散程度的重要统计量，两者的统计过程都是以计算绝对值为基础的，其计算复杂程度相对较低，因而，本文将绝对差和平均离差引入到阈值判别函数的设计中。假定设为待分割图像的二维阈值，先统计图像目标类与背景类各自类内的绝对差，得到总体类内绝对差之和；再统计目标类和背景类两类之间的总体平均离差；然后把总体类内绝对差之和和类间总体离差的商作为阈值识别函数，流程如下（见图3）。

图3 本文阈值识别函数构造流程

类内绝对差和类间总体离差公式，都是根据绝对差和离差的定义，并将其推广到二维，应用于待分割的图像二维直方图中推导得到的。

两类的总体类内绝对差为

（12）

那么可得目标类和背景类总体的类内绝对差之和

（14）

对于二个类，定义其类间平均离差为

同样对此，可以推广到二维。根据第1节给出的二维直方图，设为待分割图像的二维阈值，式(7)已给出总体均值向量。则目标类和背景类的类间平均离差为

（16）

综合式(14)和式(16)得到式(17)如下

从式(17)中可以看出，分子反映的属性为类内的内聚性；分母反映属性的是类间的离散度。因而，当取最小值时，既保证了目标类和背景类的最大化离散度，且又能是得目标类和背景类各类的内聚性最好。本文将使用来作为阈值判别向量。

本文将在第3节中通过设计一种改进的遗传算法，以式(17)为适应度函数，自动得到合适的阈值向量。有了阈值向量，就可以实现对灰度图像的二值化分割，分类函数如下

3 自适应的阈值向量求解方法

通过上述分析，本文改进的二维Otsu算法选取最佳阈值向量的过程也就是选取使得目标函数即阈值识别函数取得最小值的过程，是一种寻最优解的过程，可以通过遗传算法自适应求出，具体算法的流程图如图4所示。

传统遗传算法对交叉和变异做统一的操作，对收敛性有很大影响，往往会陷入局部最优解，这是一个经典难题，目前有很多学者都针对这个问题进行研究，本文根据不同的适应度值对种群进行分类，对不同的种群采用不同的交叉方法和变异概率，即采用基于海明距离判别的交叉方式、基于动态变化的变异概率，一定程度上避免了陷入局部最优。下面介绍本文阈值向量的自适应求解过程，并且比较了与传统遗传算法在选择、交叉、变异算子上的差异。

图4 遗传算法优化阈值识别函数流程图

（1）编码

对于给定是实际问题，确立采用16位二进制编码。

（2）初始化

设初始化种群的大小为popsize，初始化可以通过随机数产生器随机生成一个popsize行，16列的矩阵。

（3）适应度函数

（4）选择

传统遗传算法中采用的是轮盘赌的选择方式，通常会导致种群失去多样性，遗传算法也就过早地丧失了其进化能力。

本文采取的选择方法是，首先将父代中部分适应度值最高的个体保留，直接进入子代；对于部分次优的个体经过一定的突变后得到的优秀个体同样也可进入子代，即通过不同的父代种群进化得到子代种群。这种种群构造方式不仅确保了优秀个体进入下一代，同时，又保证了种群的多样性，使得种群中相似个体出现的概率降低了，提高以下的交叉、变异操作的效率，也提高了整个算法的收敛性。

（5）交叉

交叉操作是进化算法中遗传算法具备的原始性的独有特征。传统的交叉算子存在一个问题，就是当进化到局部最优时，种群中很多个体都非常相似，这就是“近亲”。也就是说很大程度上作交叉的个体交换的串是相同的，交叉操作也就失去了作用。

本文为了避免“近亲”交叉，对交配池中随机选择的交叉个体对进行海明距离（两个个体串的对应比特取值不同的比特数）的判断。若选择的个体对海明距离，则按照原定的交叉概率进行交叉操作；反之若，则判定这对个体是“近亲”，替换掉其中的一个个体，进行重新判定，直到满足条件或者群体中的所有个体都被尝试替换为止。

（6）变异

本文中采用一种动态的变异概率，以此来增加种群的多样性。基本思路是判断当前种群是不是“早熟”，若是则以一个较大的概率进行变异操作；反之则按常规概率进行变异操作。定义是当前种群中最优的适应度，是当前种群的平均适应度，若，其中，称为密集因子，则判定种群没有“早熟”，以常规概率进行变异操作；反之认为种群“早熟”，以远大于常规概率对种群中所有个体进行变异操作，产生多个个体进入下一代，以此保证种群摆脱局部收敛。

4 实验分析

实验选取一幅医学CT图像、一幅脑核磁共振图像(MRI图像)等六幅图像通过与一维Otsu算法、文献[4]提出算法进行比较以验证本文算法性能。实验平台是Pentium 4，内存为512MB，运行环境为Matlab7.0。

实验中的参数设定如下：

窗口邻域：3；种群大小：10；迭代次数：150；编码长度：16；交叉概率：0.7；海明判别距离：2；较大变异概率：0.2；较小变异概率：0.01；密集因子：0.8。

表1给出了对每幅图像各种算法的分割阈值。

表1 三种算法的阈值统计

主观上从图5~图10可以看出用本文算法得到阈值化图像与文献[4]算法和一维Otsu算法相比背景和目标物能够更好区分出来。图5(b)中，CT图像四个部分的目标物几乎都连在一起，失去了轮廓信息；图5(c)其分割效果更差，目标物没有能够分割出来；应用本文算法的结果，图5(d)，其脑CT图像的四个部分有着清晰地轮廓，分割效果比较理想；图6(d)相对于图6(b)和图6(c)显然有着更多的轮廓；图7(b)中，帆船底部与水面没有分开，文献[4]算法的分割结果图7(c)相对于一维Otsu有所改善，但与本文算法分割结果图7(d)相比仍然有很多错误分割的地方。图8红外图像的分割也是本文算法相对于一维Otsu和文献[4]算法最大限度地将目标物与背景分开，目标物保留了较好的轮廓细节；对图9，三种算法都取得了较好的效果，但是本文算法能够很好地保留了坦克车轮的轮廓；图10对米粒图像的分割，一维Otsu算法和文献[4]算法的分割结果含有很多的噪声，本文算法分割后的结果米粒清晰可见。

通常人们对图像分割的结果是以人的主观判决为评价准则，但对不同分割方法的处理结果作定量的评价也是必需的。本文中，作者采用两个常用的图像分割质量评价指标区域一致性和区域对比度来定量评价实验中的三种算法性能。

区域一致性是指分割区域内部元素具有相似性（一致性）的分割结果，这种特征一致性可以通过计算区域内的特征方差而得到，即，其中，。1或2，分别代表目标区域和背景区域，为区域内像素点的个数，为区域内像素点的方差，为整幅图像的像素点数。

从表2可以看出，对六幅图像的处理，本文算法对区域一致性、区域对比度参数都具有更好的指标，与人的视觉基本一致。

表2 三种算法分割结果定量评价

本文算法中采用自适应的改进遗传算法来寻优最佳阈值向量，对于的计算次数为算法设置的循环代次，同样，每计算一次都要累加计算、个点，所以本文算法的时间复杂度为。本文通过改进的GA算法加速收敛进程，平均收敛代数基本上保证在50代以内，为了验证改进的GA具有更好的收敛性，本文也做了改进GA寻优和传统GA寻优的性能比较实验。图11~图16分别对应实验中的六幅图像应用GA和IGA进行寻优的进化曲线。

图11 脑CT图GA和IGA进化曲线比较

图12 MRI图GA和IGA进化曲线比较

图13 ship图GA和IGA进化曲线比较

图14 红外图GA和IGA进化曲线比较

图15 tank图GA和IGA进化曲线比较

图16 rice图GA和IGA进化曲线比较

图11~图16中，横坐标表示进化的代数，纵坐标表示适应度值，这里寻优得到得是1/的最大值。黑线是传统GA的进化曲线，加星号线是应用改进的GA(IGA)所得到的进化曲线。显然，应用IGA算法所得到的最优阈值显然要好于传统遗传算法能够更早的得到最优解，也更加接近全局最优解，一定程度上克服了传统GA算法的“早熟”问题。

5 结 论

本文指出了传统的二维Otsu算法的计算复杂程度较大，并且也只仅仅考虑类间最大方差，为此，本文在不增加计算复杂度的前提下，提出了并设计了一种既能反映类间方差又能反映类内方差的阈值判别函数，得出了比传统二维Otsu算法更好的分割效果，同时用来改进的遗传算法具有更好的群体多样性和全局搜索能力。实验的结果验证了本文提出的方法具有更好、更快的分割效果，具有一定的实用价值。

[1] [美]冈萨雷斯. 数字图像处理(第2版)[M]. 阮秋琦等译. 北京: 电子工业出版社, 2003. 460-521.

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

[3] Otsu N. A threshold selection method from gray level histograms [J]. IEEE Trans on SMC, 1979, 9(1): 62-69.

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

[5] 范九伦, 赵 凤. 灰度图像的二维Otsu曲线阈值分割法[J]. 电子学报, 2007, 35(4): 751-755.

[6] 杨金龙, 张光南, 历树忠, 等. 基于二维直方图的图像分割算法研究[J]. 激光与红外, 2008, (4): 400-403.

[7] 周云燕, 杨坤涛, 黄 鹰. 基于最小类内离散度的改进Otsu分割方法的研究[J]. 华中科技大学学报, 2007, 35(2): 101-103.

[8] 范九伦, 赵 凤, 张雪峰. 三维Otsu阈值分割方法的递推算法[J]. 电子学报, 2007, 35(7): 1398-1402.

[9] 丁明跃, 彭嘉雄, 万发贯. 平均绝对差算法捕获概率的估计[J]. 华中理工大学学报, 1989, 17(5): 71-76.

[10] 郭福华, 邓飞其. 推广的半绝对离差和动态投资组合选择[J]. 应用数学, 2007, 20(3): 446-451.

[11] 李敏强, 寇纪淞, 林 丹, 等. 遗传算法的基本理论与应用[M]. 北京: 科学出版社, 2002. 163-208.

[12] 侯格贤, 毕笃彦. 图像分割质量评价方法研究[J]. 中国图象图形学报, 2000, 5(1): 39-43.

Image Segmentation Algorithm Research Based on Minimum Within-cluster Difference and Maximum Between-cluster Difference

WU Hao, WANG Rong-gui, FANG Shuai, YANG Wan-ting

( 1. Department of Computer Science and Technology, Hefei Normal College, Hefei Anhui 230061, China;2. Faculty of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China )

The present two-dimensional Otsu image segmentation algorithm ignores the cohesiveness of foreground and background pixels. A novel method of threshold recognition algorithm is proposed, which, by using two-dimensional histogram of the target image, counts the absolute difference within the cluster and the average total deviation between the cluster to reflect the scattered difference, and then constructs a new threshold recognition function. An improved genetic algorithm is adopted to optimize the new threshold recognition function so as to obtain the ideal threshold value automatically. Experimental results show that the two-dimensional threshold value obtained through the optimized threshold recognition function is of good segmentation efficiency, of good retaining of the object outline and of low work amount of calculation.

image segmentation; two-dimensional Otsu algorithm; threshold recognition function; minimum within-cluster difference; maximum between-cluster difference

TP 391.41

A

1003-0158(2011)01-0067-09

2009-04-15

国家自然科学基金资助项目（60705015）；安徽省自然科学基金资助项目（070412054）

吴 昊（1983-），男，安徽舒城人，硕士，主要研究方向为图像处理、人工智能等。