基于局部密度和偏移量的图像自动分割算法

刘娜　刘向阳

摘   要：图像分割是计算机视觉领域的传统问题，也是图像分析和模式识别的关键组成部分。提出了一种不依赖于图像分割数参数的图像自动分割算法。基于超像素间的测地距离，根据其定义的局部密度和偏移量，结合K-S假设检验来分析图像最佳分割数，并给出了图像自动分割算法。大量图像分割的实验结果表明：该方法可以准确地对图像进行自动分割，达到了较好的分割效果，相比其它方法，速度更快。

关键词：测地距离;图像分割数;图像自动分割;局部密度;偏移量

中图分类号：TP 391.41                                             文献标识码：A

Automatic Image Segmentation Algorithm Based

on Local Density and Offset Distance

LIU Na？覮，LIU Xiang-yang

（School of Science，Hohai University，Nanjing，Jiangsu 211100，China）

Abstract：Image segmentation is a traditional problem in the field of computer vision and a key component of image analysis and pattern recognition. This paper proposes an automatic image segmentation algorithm that does not depend on the number of image segmentation parameters. Based on the geodesic distance between superpixels，according to its defined local density and offset distance，we combine the K-S hypothesis test to analyze the optimal segmentation number of the image and automatically segment the image. The experimental results of a large number of image segmentation show that the method can accurately segment the image automatically and achieve better segmentation effect. Compared with other methods，the speed is faster.

Key words：geodesic distance;image segmentation number ;automatic image segmentation;local density;offset distance

图像分割是图像处理的重要组成部分，其实质就是按照像素的属性进行聚类的过程[1]。它将给定图像分解成内部特性相同、相互特征不同的区域并提取出感兴趣的目标的过程，在图像工程中占有非常重要的位置。基于聚类分析的图像分割算法在图像分割领域有着广泛的应用，在聚类分析中，最佳聚类数的确定问题一直是聚类有效性的关键问题。很多学者提出用聚类有效性指标来评价聚类效果，并以此确定最佳聚类数。近年来，很多学者提出评估最佳聚类数的有效性指标，比如，Calinski和Harabas提出了基于全部样本的类内离差矩阵和类间离差矩阵测度的CH指标[2];Dudoit和Fridlyand提出了基于全部样本的类内离差矩阵测度的KL指标[3];Kapp等人[4]基于概率统计思想，使用类内数据点的in-group比例来评价聚类结果，提出了IGP指标;还有组内平方误差和BWP指标[5]等。也有学者提出运用一些信息准则，如贝叶斯信息准则（BIC）和Akiake信息准则（AIC）[6]等確定分类数。Figueiredo和Jain[7]开发了一种估计K的新方法，使用最小信息长度（MML）标准和高斯混合模型（GMM），这种方法的新颖之处在于它将估计和模型选择集成在单个算法中，而不是使用模型选择标准从一组预先估计的候选模型中选择一个。2014年，Andr Fujita和Daniel[8]开发了一种名为斜率统计的新方法，它不需要使用剪影索引进行密集计算，由于严格的数据分布假设，这仅适用于狭窄的应用。虽然上述算法可以在一定程度上帮助找到适当的簇数，但时间成本相当高，并且只有在导出聚类结果后，才能通过迭代此算法确定适当的聚类数。 此外大多数方法假设数据符合高斯分布的混合，但是大多数数据集更复杂，导致这些方法的性能较弱。

针对不依赖于图像分割数参数的图像分割，提出了一种基于局部密度和偏移量的图像自动分割算法。首先给出了测地距离的定义及计算方法，然后定义了局部密度和偏移量这两个指标，通过K-S假设检验找到满足条件的划分中心点，最后基于确定的划分中心对图像进行分割。和传统方法相比，这种方法的优点在于：传统方法需要通过对不同分割结果进行比较才能得到图像最佳分割数，而本文算法可以直接得到图像最佳分割数，更好地减少了图像分割算法中人为选取参数的麻烦，大大的减少了计算量。

1   算法思路

本算法是基于RGB彩色空间，对所有RGB图像都可进行分割。对RGB图像的分割不再基于像素，而是以超像素为基本单元。超像素其实就是将具有相似纹理、颜色、亮度等特征的相邻像素进行合并后的图像块。采用超像素的图像分割算法后，可以消除像素间的冗余，大大降低后续图像处理任务的成本，加快图像识别的速度。本文算法主要分为以下几个步骤进行，首先是对图像进行超像素预处理，生成近邻图，定义相邻超像素之间的距离，计算两两超像素之间的测地距离[9];然后求出每个超像素点的局部密度和偏移量，再选取局部密度和偏移量的下限来确定划分中心点，最后基于这些划分中心对图像进行分割。本文算法的步骤如下：

第一步：超像素预处理;

第二步：使用超像素构造近邻图，求出近邻图中任意两两超像素点之间的测地距离;

第三步：计算超像素点的局部密度和偏移量;

第四步：设置超像素局部密度下限，根据每个点的偏移量和K-S假设检验确定偏移量下限;

第五步：确定局部密度和偏移量都大于下限的点就是划分中心点;

第六步：将其余点归类到比它们局部密度更大、测地距离最近的超像素点所属的类别中，完成图像分割。

2   图像自动分割算法

2.1   生成超像素并计算超像素间的测地距离

2012年Achanta等人提出了简单的线性迭代聚类算法（SLIC）[10]，本算法利用SLIC算法将图像分割成超像素图像，将每个超像素看成图像处理的基本单元。认为相邻的超像素间有边相邻，所有超像素点就可以构成近邻图，在近邻图中相邻的两两超像素点之间的距离dij定义如下：

dij = （d1 + λd2） × g       （1）

其中d1，d2分别表示超像素Ci和Cj之间的颜色距离、纹理距离（采用Hausdorff距离），为纹理距离的权重，g为超像素Ci和Cj之间的方向梯度，本文算法是用RGB圖像函数的一阶差商近似代替方向梯度，方向梯度反映了相邻超像素间的边界。

针对图像分割定义中区域的连通性要求，以及更好的度量两两超像素间的相似性，引入了测地距离[9]。基于相邻超像素点之间的距离，对于不相邻的超像素点，是计算它们之间的测地距离。首先将相邻超像素间的距离作为它们之间边的权重，再使用Dijkstra算法[11]找出不相邻超像素点间的最短路径，最后将计算出这个最短路径的长度作为它们之间的测地距离。基于超像素间的测地距离，下一步就要计算每个超像素点的局部密度和偏移量。

2.2   局部密度和偏移量

2014年Alex Rodriguez在新聚类算法（DP算法）中提出了局部密度ρ和偏移量δ的概念[12]。对于局部密度和偏移量这两个指标的计算，首先要计算出超像素点集D = {x1，x2，…，xn}中任意两点间测地距离dij，再将超像素点的局部密度ρi定义为“数据集中到该点距离小于截断距离dc的数据点个数”，最后根据高斯核函数计算局部密度值。本文采用高斯核函数计算局部密度，这样计算不同数据点具有相同的局部密度值的概率会更小。具体计算公式为：

ρi = ■e■        （2）

其中dc为截断距离，是算法中的可变参数，实验中取数据集中所有两点间距离值的1%-2%。当局部密度ρi的值算出后，令{ρ1，ρ2，…，ρn}是按从大到小排序的结果，偏移量δi定义为：

δi = ■（dij），i = 1■（dij），i > 1        （3）

即当xi的局部密度最大时，δi表示D中与xi距离最大的超像素点到xi之间的距离;否则，δi表示在所有局部密度大于xi的超像素点中，与xi距离最小的那个超像素点到xi之间的距离。

因为划分中心具有“与同一个区域中的大部分点距离较近”和“距离其他划分中心较远”的特点[10]，而ρ和δ这两个指标恰好对应了这两个特点。因此可以确定，划分中心的ρ和δ指标的值均较大。本文算法先计算出每个超像素点的ρ，δ值，并从中选出ρ，δ值均明显大于ρmin，δmin的超像素点作为划分中心，确定了图像最佳分割数，最后基于得到的划分中心对图像进行分割。

2.3   划分中心的定义

DP算法[12]中提到了用γ = ρ × δ的值来确定划分中心，因为划分中心的ρ和δ指标的值均较大，所以DP算法中认为γ值异常大的点为划分中心。图1（g）为超像素点的γ值从大到小的排序图，显然从图1（g）中只能看到一个γ值异常大的点，但是图1（a）明显分为前景和背景两个部分。图1（c）中红星为原图基于γ值确定的两个划分中心，而这两个划分中心都在背景上。这是因为原图前景中超像素点的局部密度值小，导致它们的γ值较小，所以识别不出来前景中的划分中心。本文算法单独分析了ρ和δ指标，判断超像素点是否为划分中心。图1（f）为δ分布图，可以看出很多局部密度大的点偏移量却很小，一些局部密度小的点偏移量却很大。本文算法通过单独分析ρ和δ指标之后，确定了原图的划分中心并进行图像分割，如图1（d）所示，可以看出能准确找到划分中心点并且图像的分割效果也很好。

（a）原图;（b）超像素预处理（其中白色纹理是超像素边界）;

（c）基于γ值确定的划分中心点（其中红星表示中心点）;

（d）本文算法确定的划分中心（其中白色线条为图像分割边界）;

（e）原图的ρ值（从大到小排序）;（f）原图的δ值（按ρ值大小排序）;

（g）原图的γ值（从大到小排序）;（h）原图的δ值（从大到小排序）

图1   基于不同方法的划分中心定义

对于ρmin的选取，应该比大部分超像素点的ρ值大。因为图像中有些区域比较小，超像素点局部密度也较小，如图1（a）中的飞机区域。但ρ值特别小的超像素点可能是噪声点，不能作为划分中心。本文算法取数据集中所有点的局部密度值的a%作为ρmin，通过实验得出a%的取值大约在50%-75%。对于δmin的选取，首先经过大量数据分析可得，数据点的δ值大致服从指数分布。我们将δ值从大到小排序，再使用柯尔莫哥洛夫假设检验（K-S假设检验）做统计量分析选取δmin。即：选取δmin使得在区间[0，δmin]上所有数据点的δ值都满足指数分布，大于δmin的数据点的性质显然与其他数据点不同，因此这些点可以作为划分中心。

2.4   K-S假设检验

将K-S假设检验应用在δmin的选取上，通过假设检验找到不符合指数分布的数据点，确定临界点δmin。设δn（x）是随机样本观察值经验分布函数，样本量为n;F0（x）是一个特定的理论分布函数。定义D = δn（x） - F0（x），如果对于每一个x值，δn（x）与F0（x）都十分接近，则表明经验分布函数的拟合程度很高，认为样本数据来自服从该理论分布的总体。

δn（x）的经验分布函数为：

δn（x） = ■■I{xi ≤x}        （4）

其中I{xi ≤x} = 1，xi≤x0，otherwise。

δn（x）的理论分布函数为：

F0（x） = F（x;λ）n = （1 - eλx）n       （5）

其中λ = [E（δ）]-1。

再计算统计量Dmax = maxδn（x） - F0（x），根据给定的显著性水平α和样本数据个数n确定样本的临界值Dα，最后确定符合条件的δmin。

2.5   确定划分中心及图像分割

计算出数据集D当中每一个样本点xi的局部

密度ρi和偏移量δi。根据分布图，我们可以直观地了解每个数据点符合划分中心性质的程度，ρ和δ均较大的点则是符合划分中心性质的点。因此选取ρmin和δmin后，就可以确定划分中心集为C = {xj | ρj > ρmin，δj > δmin}，该集合中的点被称为划分中心。

假设划分中心有k个，定义每个划分中心的标签为L（xj），j = 1，…，k先将其余点按局部密度值大小排序，再依次将它们的标签定义为：

L（xi ） = ■

将其余点按照局部密度大小依次归类到比它们局部密度更大、测地距离最短的超像素点所属的类别中，即可完成图像的分割。

3   试验结果及分析

为了验证本文图像自动分割算法的性能，针对纹理图像和自然图像（如图2）进行了图像分割。

3.1   算法分析

实验中将图2（a）超像素个数设为K=800，图2（b）超像素个数设为K=3000，选取原始图像中局部密度值前65%的超像素点，将它们的 值从大到小排列得到散点图，如图3所示。然后通过K-S假设检验对δ值做统计量分析。将δ值在bins（实验中取值为8至100 ）个区间中计算直方图分布，确定偏移量下限δmin。图4显示了图像的划分中心。图5显示了图像分割结果，可以看出本文算法可以准确地得到划分中心，并且分割效果较好。

图2   原始图像

图3   偏移量 分布图

图4   超像素处理及划分中心结果

图5   图像分割结果（其中白色线条为图像分割边界，红星的编号是划分中心点次序）

3.2   实验结果及分析

為了验证本文算法的可行性和有效性，选取了大量的图像进行了分割实验，同时还利用了评价性指标来确定图像最佳分割数，实验中采用CH指标[2]和Dunn指标[13]，最后再与本算法结果进行比较。图6为本算法部分实验图像及分割结果，从图6中可以看出本算法能比较准确的找到划分中心，分割效果也比较好，分割边界也比较清楚。从表1中可以看出，本算法的实验结果与评价性指标的实验结果相比较，确定的最佳分割数更准确，计算时间比用评价性指标算法也少很多。

图6   部分实验图像及分割结果

表2   本文利用评价性指标确定图像最佳分割数所得结果

4   结 论

提出了一种基于局部密度和偏移量图像分割算法。实验仿真结果表明，提出的方法有较好的分割效果。综合来看，本算法比传统方法计算量小，偶然性小，且省去了使用多种算法、多种指标和必须分析一些分割结果的麻烦。但也存在许多难以解决的异常结果，例如纹理差别特别大的图像无法准确确定分割数。下一步需改进该算法，使算法所得的图像分割更准确。

参考文献

[1]    何俊，葛红，王玉峰. 图像分割算法研究综述[J]. 计算机工程与科学，2009，31（12）：58—61.

[2]   CALINSKI R B，HARABASZ J. A dendrite method for cluster analysis[J]. Communications in Statistics，1974，3（1）：1—27.

[3]   DUDOIT S，FRIDLYAND J. A prediction-based resampling method for estimating the number of clusters in a dataset[J]. Genome Biology，2002，3（7）：1—21.

[4]    KAPP A V，TIBSHIRANI R. Are clusters found in one dataset present in another dataset[J].Biostatistics，2007，8（ 1）：9—31.

[5]    ZHOU S B，ZHEN X U. New method for determining optimal number of clusters in K-means clustering algorithm [J]. Journal of Computer Applications，2010，30（8），1995—1998.

[6]    XIE C H，CHANG J Y，LIU Y J. Estimating the number of components in gaussian mixture models adaptively for medical image[J].Optik-International Journal for Light and Electron Optics，2013，124（ 23）：6216—6221.

[7]    FIGUEIREDO M A，JAIN A K.Unsupervised learning of finite mixture models[J]. Pattern Analysis and Machine Intelligence，2002，24（3）：381—396.

[8]    FUJITA A，TAKAHASHI D Y，Patriota A G.. A non-parametric method to estimate the number of clusters[J]. Computational Statistics & Data Analysis，2014（73）：27—39.

[9]    CRIMINISI A，SHARP T，ROTHER C，et al. Geodesic image and video editing[J].ACM Transactions on Graphics，2010，29（5）：1—5.

[10]  ACHANTA R，SHAJI A，SMITH K，et al. SLIC  superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2012，34（11）：2274—2282.

[11]  DIJKSTRA E W . A note on two problems in connexion with graphs[J]. Numerische Math，1959，（1）：269—271.

[12]  RODRIGUEZ A，Alessandro. Supplementary materials for clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492—1498.

[13]  DEXNER H，HORN M，STREEK A，et al. Laser micro sintering：a new method to generate metal and ceramic parts of high resolution with sub-micrometer powder[J]. Virtual and Physical Prototyping，2008，3（1）：3—11.