基于空间聚类和边缘梯度的图像分割算法

雍玉洁，顾 华

(河海大学理学院，江苏 南京 211100)

0 引 言

图像分割的实质是将图像按某种特质对像素进行聚类的过程，是图像处理[1-2]的重要组成部分，其目的是从图像中提取出人们感兴趣的部分以便于进行下一步处理。图像分割技术[3]也是当前图像工程中需要研究的热门项目。目前比较经典的图像分割技术大多分为2种:

1)根据颜色、纹理等区域因素进行聚类，即在整个图像中将具有相似颜色或纹理的区域分为一类,完成分割。传统的区域分割方法主要有区域生长法[4]、区域分裂与合并方法[5]和阈值分割[6]方法等。区域分割方法的优点在于可以得到连续的区域，区域间的边缘也比较完整，但是也可能由于图像的颜色纹理的变化较多，造成过度分割。

2)基于边界因素的分割方法，即通过提取各种边缘特征信息来搜索不同区域之间的边界，从而完成图像分割[7-8]。传统的方法是利用边缘检测算子来搜索边界，这类方法由于检测速度比较快而被广泛利用。经典的边缘检测算子主要有Sobel算子[9]、Prewitt算子[10]、Robert算子[11]、LoG算法[12]、Canny算子[13-14]等。近年来边界模型[15-16]的方法也比较流行，这种方法一般通过将梯度作为边缘停止函数引入能量函数来分割图像。其优点是对高对比度的目标计算成本低，结果精度高，缺点是对噪声过于敏感。边界方法的主要优点在于它可以更好地刻画图像边界，将图像的不同区域清晰地分割出来，但是这类方法无法得到较好的区域结构，致使分割后无法得到连续的区域。

近年来一些基于深度学习的方法比较流行，例如DeepLab、Mask R-CNN等。深度学习的方法要输入许多图像，先有一个学习的过程，然后再进行图像分割。这一类方法与上述方法有着本质的不同，上述方法不需要进行学习，直接基于图像的区域和边界特征，并且可以对任意图像进行分割，不拘泥于图像的类型。基于这2种方法的不同，无法进行比较，因此本文不讨论这一类方法。

针对图像区域相似性和边缘不连续性的特点，本文提出一种将区域和边缘因素结合的分割方法。先将图像划分为超像素，使用分段梯度计算方法来表示边缘信息，然后使用超像素之间的测地距离对超像素进行空间聚类。本文算法不仅利用颜色和纹理这些区域特征信息对图像进行相似度分析，还加入了边缘检测的思想方法，利用超像素之间的边缘梯度对图像进行分割，并且在计算边缘梯度的过程中，本文利用分段函数对边缘进行拟合，使得边缘梯度的计算结果更加精确，从而使得分割结果贴合真实边界，更加准确。与传统的方法相比，这种方法结合了区域内部相似性和边缘不连续性，其分割结果既可以拥有连续的区域，也不至于过度分割，对边界的刻画也更加精确。

1 算法思路

在本文方法中首先对图像进行超像素的预处理，将具有相似颜色、纹理等特征的相邻像素聚类成同一个超像素块。将超像素作为基本单元可以加快图像识别的速度、降低计算复杂度。将图像划分为超像素后，在边缘因素中引入梯度，计算超像素之间的测地距离，最后选取划分中心对图像进行分割。本文的具体算法步骤如下：1)超像素预处理；2)求出相邻超像素之间基于区域因素的距离；3)在边缘因素中引入梯度，求出相邻超像素边缘上梯度；4)将区域因素和边缘因素相结合，构造超像素距离的近邻图，求出任意2个超像素之间的测地距离；5)确定划分中心点，将其余点进行聚类，完成图像分割。

2 图像分割算法

本文算法首先计算任意2个超像素之间的测地距离，然后计算所有超像素点的局部密度和偏移量选出划分中心，完成分割。

2.1 相邻超像素的相似性

本文利用SLIC算法[17]将图像分割为超像素图像，再在超像素上进行图像处理。本文算法将相邻超像素的颜色距离和纹理距离相结合，作为超像素之间基于区域因素的距离定义如下：

d1=dc+λdt

(1)

其中，dc表示超像素之间的颜色距离，dt表示超像素之间的纹理距离。纹理距离采用Hausdorff[18]距离，λ是纹理距离的权重，用于调整区域因素中颜色和纹理的比重。这种计算方式更多考虑了图像的多样性。

2.2 边界梯度的计算

Ren等人[19]提出通过计算超像素边界上像素的方向能量来计算轮廓线的方法，相邻超像素之间若存在分割边界，那么边缘上像素将会有明显变化，这一特征可以用于判断相邻的2个超像素之间是否存在边界。处在边界上的像素一般颜色会发生突变，梯度值相对较大。本文算法计算相邻超像素边缘的梯度并将其作为边缘因素加入超像素之间的距离计算。超像素之间边缘上梯度越大，则这2个超像素之间存在边界的可能性越大，反之亦然。

为了更加准确地计算超像素边缘梯度，本文采用分段的方法去刻画边缘。将边缘等分为n段并连接每一段的端点，以该连线的法向量作为这一段边缘中点的法向量。法向量上像素梯度变化最大值作为该段边缘的梯度，并将这n段边缘的梯度取平均值作为整个边缘的梯度。如图1所示，其中超像素Ci和Cj中间的实现曲线是2个超像素边缘，虚线是分成n段后每段端点连线，带箭头连线为该段边界的法向量，圆点是这段边界的中点。

(a) n=1 (b) n=3图1 超像素边缘梯度的计算

相邻超像素之间的梯度信息定义如下：

(2)

Mk=‖rk-rk+1‖+‖gk-gk+1‖+‖bk-bk+1‖

其中，rk、gk、bk表示相邻的超像素Ci和Cj之间边缘的第s(s≤n)段中点法向量上第k个像素在RGB颜色空间中的3个颜色值，ls表示该法向量上所取像素的数目。针对不同的图像，超像素边缘上像素数目不同，所以计算时要先根据像素数目确定n的大小。当n=1时，直接以边缘2个端点之间连线的法向量上梯度作为边缘梯度。但是由于相邻超像素的边缘并不总是一条直线，若取n=1，如图1(a)所示，并不能很好地贴合边缘，未体现出超像素边缘的变化。若此时同一区域的边缘法向量上恰好有变化较大的噪点，分割结果也会不准确。因此一般选取n≥2(见图1(a))，将每一条边缘分成2段以上。在这里选取的n越大，对于边缘的刻画就越准确，算法所得的梯度值也越接近边缘的真实梯度值。图2展示了n=1和n=3时，相邻超像素C1、C2属于同一区域和不同区域2种情况下的边缘梯度对比,显然n=3时的结果更加准确。图2中，g1表示n=1时相邻超像素的边缘梯度，g2表示n=3时相邻超像素的边缘梯度。

(a) 原始图像 (b) C1、C2非同一区域 (c) C1、C2同一区域

2.3 任意超像素之间距离的计算

本文算法将区域因素和边缘因素相结合，综合考虑颜色、纹理和梯度特征对于超像素之间相似性的影响，将相邻的超像素Ci和Cj之间的距离dij定义如下：

dij=d1×gijα

(3)

其中，gij=grad(Ci,Cj)，是超像素Ci和Cj之间的梯度；α是梯度的权重，用于衡量区域因素和边缘因素在相邻超像素距离上的比重。由于梯度值是RGB颜色空间中的颜色值之差，必然小于1，因此α≠0时，α的值越小，gijα越大。若图像各个区域的颜色相近，可将α的值减小，使得梯度比重增大；若各个区域之间颜色差异较大，可以将梯度权重α增大，从而增加颜色纹理距离的比重。本文将区域距离与边缘距离相乘是考虑到即使d1和gijα中某一项的值很小，也可以在结果dij的值中得到体现，避免由于区域和边缘中某一种因素的值远远大于另一种而导致的误差。

由于预处理时所得到的任意2个超像素都有连通性，相邻的超像素间有边相邻，所有超像素点就可以构成近邻图。本文算法使用测地距离[20]计算不相邻的超像素之间的距离。首先用Dijkstra算法[21]找到不相邻超像素之间的最短路径，将相邻超像素的距离作为边的权重，计算最短路径的长度，即为不相邻超像素的测地距离。

2.4 确定划分中心并完成图像分割

本文算法采用局部密度和偏移量[22]来进一步确定分割中心并完成分割。分割中心具有“与同一个区域中的大部分点距离较近”即局部密度大和“距离其他划分中心较远”[17]即偏移量大的特点。局部密度ρ和偏移量δ的定义如下：

其中，Dij是任意2个超像素Ci和Cj之间的测地距离，Dc是截断距离。DP算法中将γ=ρ×δ的值较大的点确定为划分中心，然而有些超像素点会出现偏移量很大、局部密度很小或者偏移量很小、局部密度很大的情况。若只看γ值的大小并不能完全准确判断划分中心，容易出现噪点，因此，本文算法不采用γ来选取划分中心。首先将局部密度ρ的值从大到小排序并选取ρmin，去除小于ρmin的点，再将剩下的点按照偏移量δ的值从大到小排序，选取偏移量大的点作为划分中心。采用这种方法，可以直接将局部密度小的点去除，即去除了一些分割区域小的中心点避免出现偏移量很大、局部密度很小的噪点。在剩下的超像素点中选取偏移量最大的几个点，即优先选择距离其他划分中心远的超像素点，避免出现选择同一区域密度很大的几个点成为划分中心的情况。采用这种选取方法有效避免了原本采用DP算法选择划分中心时所出现的误差。

选取好划分中心后，将其他的超像素点按照局部密度依次归类到各个划分中心所属的类别中，即可完成图像分割。

3 实验结果及分析

3.1 实验参数及评估方法

算法中的参数包括：梯度的权重α，区域因素中纹理距离的权重λ和超像素的数目K。为了评估参数α的变化对于结果的改变，选取伯克利数据集中的图像，对分割结果进行定量估计，本文将采用SC(Segmentation Covering Metric)[23]评价方法来对比分割结果。该方法将计算人工分割结果被算法分割覆盖的重叠率，定义如下：

其中，N表示图像像素的总数目，S是算法分割的结果，G是人工分割的结果，R和R′分别是S和G分割的区域，O(R,R′)=|R∩R′|/|R∪R′|代表区域R和R′的重叠率。

3.2 算法以及结果分析

在本文算法的实验过程中，对伯克利数据集中的图像进行了大量实验，结果表明，根据图像类型的不同，选取合适的α值引入梯度可以使得图像的分割结果更加准确。图3～图6为实验图像和不同的α值下采用本文算法得到的分割结果。当α=0时，未引入梯度，从图4中可以看出，由于只采用区域因素，过于重视颜色纹理，导致2个区域颜色相近时边界不易被识别出。图像中没有分割边界却有颜色变化的狭长区域容易被分割成2个区域。另外，相比于只采用边缘因素的分割结果，其分割边界没有那么贴合真实边界。加入梯度后，当α≠0时，α越小边缘因素的值越大。图5中α=1，其分割结果开始受到边缘梯度的影响，颜色纹理变化的影响减小，分割边界也更加精确，但此时还未将该算法的优越性完全体现。当α=0.5时(见图6)，边缘因素与区域因素正确结合，根据颜色纹理以及边缘梯度，对图像进行分割，得到精确的分割结果。从表1中也可以看出，引入梯度因素并根据图像特点选择合适的梯度权重，可以使图像分割结果更加准确，也更加体现出本文算法的优点。

(a) (b) (c)图3 原始图像

(a) (b) (c)图4 α=0时的分割结果

(a) (b) (c)图5 α=1时的分割结果

(a) (b) (c)图6 α=0.5时的分割结果

表1 分割结果的SC值

3.3 实验结果及分析

为了验证本文提出的图像分割算法性能的优越性，调整各个参数，对图像进行了实验。图7～图9选取了具有代表性的自然图像与纹理图像对实验结果进行分析与说明。图7(a)是原始图像，实验中先将超像素个数设为K=2000，如图7(b)所示。再将纹理距离的权重设为λ=0.1，梯度的权重α=0.05。由于图像中前景与背景颜色相近，但区域间有明显边界，所以将α的值设置得很小，增加梯度在距离中的比重，图7(c)是其分割结果。在分割图8的图像时，将超像素的个数设为K=1000，由于图像中区域间颜色差距较大，需要将α的值增大，纹理距离的权重λ的值减小，加大颜色对距离大小的影响。因此设置纹理距离权重λ=0.01，梯度权重α=1，图8(c)显示了该权重下的图像分割结果。图9是较为简单的纹理图像，各个区域颜色差异较小，纹理差异较大且边界比较清晰，又由于图像的各区域之间的边界较为平直，因此不需要在预处理阶段利用超像素先将边界清晰地刻画出来。在图9(b)中，设置超像素个数K=100，将超像素数量设置得较小。纹理距离的权重λ=0.1，梯度权重α=0.4，同时增加纹理距离权重和梯度权重，使得纹理和边缘梯度共同影响图像分割结果，图9(c)显示了该图像的分割结果。从图7～图9的各个分割结果来看，本文算法分割效果较好，且适用于多种类型图像。

(a) 原始图像

(a) 原始图像

(a) 原始图像

4 结束语

本文提出了一种将区域内部相似性和边缘不连续性相结合的图像分割算法，在特征信息中加入超像素边缘梯度信息对图像进行分割，为了得到更加精确的分割边界，在边缘因素中引入了分段梯度计算方法。实验结果表明，本文提出的算法能比较准确地将图像进行分割，使得分割区域不仅连续性好，区域之间有连通性，边界的刻画也较为精确。但是该算法也存在计算时间增加等缺点。接下来笔者将进一步改进算法，使算法更加快速和准确。