层次聚类算法和基于图的分割算法相融合的图像分割算法

郭昕刚，王 佳，程 超

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

图像分割是图像中最底层和最重要的预处理手段之一，它根据图像的语义信息将一张图像分成各具特性、互不交合的独立区域，并使同一区域内的像素点呈现相似性，不同区域间的像素点呈现明显的差异性。它是目前AI和自动驾驶中最重要的技术分支之一，图像分割的准确度将会直接决定下一步结果的好坏。图像分割通常分为两种：一种是无监督的传统图像分割；一种是有监督的语义分割[1]。

常用的传统图像分割方法有：基于阈值的分割方法、基于聚类的分割方法、基于边缘的分割方法和基于图论的分割方法等。基于阈值的分割方法计算简单、运算速度快，其常用方法包括固定阈值分割和自适应阈值分割，前者是固定某个像素值作为分割点来进行分割，此方法要不断尝试手动选取分割点，故不适用于批量图片操作；而后者是根据图像内的局部特征，动态地在一定范围内选取每点的阈值进行分割，但其易受噪声和亮度干扰。基于聚类的分割方法中最常使用的是超像素分割方法，它是由Ren和Malik等在2003年首次提出的[2]，是指将一张图像中具有相似轮廓、颜色和纹理的像素点划分为一类[3]，进而把图像中的点集问题转换为区域集问题[4]，为后续的处理技术降低了计算量，提高了运算速度。其中最为经典的超像素分割算法是Achanta等提出的简单线性迭代聚类(simple linear iterative clustering, SLIC)算法[5]， 它的提出有效地解决了传统算法分割效率低和复杂度高等问题，并帮助人们在SLIC算法基础上研究出了一系列新的超像素分割算法，如文献[6]在SLIC算法的基础上，提出了一种改进的本质流形的超像素分割方法。

文献[7]通过对SLIC算法迭代更新阶段的改进，提出了一种快速的线性迭代聚类(fast linear iterative clustering, FLIC)算法，FLIC算法比SLIC算法可靠性更高、算法性能更优，是目前最先进的超像素分割算法之一。然而超像素分割算法较突出的缺陷是对图像中内容敏感的弱边缘和纹理区域分割精度较差[8]，会导致后续工作中所获取的像素分割点类别标签存在误差。为了解决超像素分割中的这一问题，文献[9]中所提出的K-means-SLIC算法将SLIC分割出的每一个超像素块利用K-means进行重新聚类，并通过预先设定的阈值来判断超像素块是否欠分割，进而解决了SLIC欠分割问题。但是K-means算法需要预先给定每个簇中的簇数，而每个超像素块中的簇数是不固定的，所以使用K-means算法并不能完美地对簇中的每一个像素进行正确分类。

文献[10]中所提出的Canny SLIC算法利用Canny算子检测出来的边缘信息来进行SLIC超像素分割，从中可以看出Canny算子检测出来的边缘信息能够决定超像素与图像中的弱边缘和纹理区域之间的黏附性。除此之外，超像素分割算法与其他算法相结合，也取得了较好的分割效果，如：文献[11]提出了一种使用超像素生成目标的图像分割算法，可以实现基于目标的图像分割，但其算法时间复杂度较高；文献[12]将SLIC算法应用在特定领域的图像上，取得了较高的分割精度和鲁棒性；文献[13]在超像素的基础上，结合图的理论知识重新定义了图像局部特征中的光谱聚类，实现了图像分割；文献[14]根据超像素算法与其他方法相结合的思路，在彩色图像上实现了良好的分割效果。基于边缘的分割方法，如Canny、Sobel等[15]，其分割速度快、分割边缘轮廓完整，但它们易把噪声点误判为边界，故抗噪能力较差。基于图论的分割方法如NCuts(normalized cuts)、GBS算法等[16]，其中效果较好的是GBS算法。GBS算法是在RGB颜色空间中进行图像分割的，它将图像分割问题转换成图的顶点分类问题，降低了问题的复杂度，但其易忽略RGB颜色空间中的色彩分布不均匀问题，进而导致其分割结果产生欠分割。

自2012年以来，由于卷积神经网络(convolutional neural network, CNN)的提出和应用，图像分割的准确度再次提升，大批研究人员规避了传统图像分割算法，将大量的时间和精力投入深度学习之中。而在深度学习的图像分割算法中，全卷积网络(fully convolutional networks, FCN)无疑是最典型的深度学习算法之一[17]。它将CNN中所有全连接层全部转换成卷积层[18]，进而把结果由原本表示的类别标签转换成one-hot特征图，即一个有监督的语义分割图[19]。此外很多研究学者还将现阶段训练好的语义分割模型与传统分割算法相结合来提高分割精度，如文献[20]提出的将FCN与SLIC算法结合在一起，构造出一个超像素级别的语义分割图就取得较好的分割效果。目前，随着研究人员的不断创新和努力，语义分割技术得到了大幅度的提升和改善，并且此技术也已经被应用到了人们的日常生活中。但是对于语义分割，它最大的问题就是需要较好的硬件设备支持，所以经济成本较高。为此，为了降低开发成本，本文选取GBS算法进行研究。

为了解决GBS算法在彩色空间中忽略色彩分配不均匀所导致的欠分割问题，本文在GBS算法分割结果的基础上，提出了结合层次聚类算法进行再次聚类分割的改进图像分割算法，记为HCGBS(hierarchical clustering and GBS)。

1 相关算法介绍

1.1 GBS算法

GBS算法是由Felzenszwalb和Huttenlocher在2004年所提出的经典算法之一[21]，它是在图像最小生成树的基础上构建的，它分割的实质是对图像中的像素进行聚类。GBS算法会将待分割的图像转换成一个带权无向图G=(V,E)，其中V是顶点构成的集合，记作V={v1,…,vn}，E是连接顶点间的边所构成的集合。图1表明了原始图像与无向图G之间的对应关系。

图1 原始图像转换成带权无向图Fig.1 Conversion of original image into weighted undirected graph

在图1中，原始图像中的像素点被映射成为G中的顶点，像素之间的邻近关系由G中顶点间的边来反应，而连接顶点间的边都有一个重要的参数——权重w(vi,vj)，此参数是用来测量两个像素点(顶点)间的相似性与非相似性的非负值，其定义如式(1):

(1)

式中：vi和vj是图像中的两个像素点，R、G、B分别是两个像素点对应的颜色值。

如图1所示，分割面S将无向图中的V划分成不同的区域C，定义一个区域的内部差异为：

(2)

式中：I(C)表示区域C的生成树中边的最大权值。定义两个区域的类间差异为：

(3)

式中：d(C1,C2)表示连接两个区域的所有边中权值最小的边的权值。

另外，在GBS算法中，合并两个区域的标准条件为：

(4)

GBS算法首先计算所有像素点边的权重值，将边按照其权重值从小到大排序得到{e1,…,en}。然后选择ei来对当前选择的边ej(假设ej是连接顶点vi和vj的边)进行合并判断。如果vi和vj不在同一个区域或者其不相似度比二者内部不相似度小，则更新阈值和类别标签；如果i

1.2 层次聚类算法

层次聚类算法是无监督聚类算法中最典型的算法之一，它的主要任务是把一个数据集分成若干个类或簇，它分为从下向上(凝聚法)和从上向下(分裂法)两种算法[22]。它们的基本定义如下：

1)从上向下(分裂法)：初始化时把所有的样本看成一类，然后根据最小距离准则进行逐渐分裂，重复此操作直到达到停止条件。

2)从下向上(凝聚法)：初始化时将每个样本点自成一类(即原始类别的大小等于样本点的个数)，然后依据最小距离准则合并这些初始的类簇，重复此操作直到达到停止条件。

在这两种算法中，最常使用的是凝聚法,而凝聚法中最经典的是AGNES算法，其具体步骤描述如下：

1)输入样本集合D={X1,…,Xn}，样本之间的距离T；

2)把样本集D中的所有样本点都单独地归为一类；

4)根据设定的样本间距离阈值T来判断两个类簇的差异，判决是否合并类簇Ci和Cj为一个类簇；

5)当达到聚类的数目或者达到设定的条件时结束聚类；

6)输出聚类结果。

2 关键技术

2.1 HCGBS算法

在机器学习中，常用的聚类算法有K-means聚类算法、K-medoid聚类算法和层次聚类算法等。其中K-means和K-medoid都是属于分类式的聚类算法，用户需要预先指定聚类的簇数，且容易陷入局部最优解，会使聚类的结果出现较大误差；层次聚类算法是一种自底向上聚类的算法，不需要预先指定聚类的簇数且其相似度规则容易定义，能够实现很好的类别分类。

本文HCGBS算法是将GBS算法与层次聚类算法融合在一起，构造出一个更加精细的超像素分割图。其实验方案如图2所示。

图2 实验方案Fig.2 Experimental scheme

本文算法具体实现步骤如下：

1)输入待分割的原始图像，设置GBS算法所需的分割区域数目值s、高斯滤波标准差σ和区域块中像素点数目m。

2)使用GBS算法对待分割图像进行分割，获取初始的分割类别标签。

3)将GBS算法得到的每一个区域块中的像素pi进行归一化，并计算出每一个区域块中像素pi的均值T：

(5)

其中：N为每一个区域块中像素的个数；T∈(0,1)，T越趋于1，两个样本相似度越高，T越趋于0，两个样本相似度越小。

4)对分割后的每一类区域块依次使用层次聚类算法来获取每一类区域块内部的类别标签。

5)设定区域块中所存在的类别数目的范围来更新初始的分割结果。

6)最后寻找出边缘像素点并利用区域合并准则进行区域合并，获取新的分割图。

2.2 算法处理速度的改进

传统的层次聚类算法复杂度较高，处理大规模数据时计算速度缓慢。因此，本文先把获取的每个像素值数组进行降维和剪切，然后再采用多线程并行处理数据的方式，将待分类的数据集同时进行聚类，有效地改善了传统层次聚类算法的处理速度。传统层次聚类算法与本文使用的层次聚类算法处理速度随数据量变化的关系如图3所示。

图3 两种算法处理速度对比Fig.3 Comparison of processing speed of two algorithms

从图3中可以看出，本文改进的层次聚类算法使用多线程提高了系统的并行性，能够一次性处理多个数据集，从而很好地实现了算法处理速度的优化，减少了时间消耗。

3 实验结果分析

实验是在win7系统和pycharm平台上实现的，所采用的数据集为公开数据集BSDS500，本节将从分割结果图和评价指标来分析本文所提算法。

3.1 分割结果图分析

图4展示了本文HCGBS算法在不同的区域块数量k和区域内像素点数量m下的分割结果。图像结果表明，m越大，区域块之间就越规整；m越小，k值越大，区域块之间就越紧凑，对图像边界的分割性就越好。

图4 HCGBS在不同k和m下的分割结果Fig.4 Segmentation results of HCGBS under different k and m

将本文HCGBS算法与传统的K-means-SLIC算法在BSD数据集上进行了比较，其结果如图5所示。

(a) HCGBS算法(a) HCGBS algorithm

(b) K-means-SLIC算法(b) K-means-SLIC algorithm

(c) 两种算法比较部分的放大图(c) Enlarged image of comparison part between two algorithms图5 HCGBS算法与传统K-means-SLIC算法的比较(k=300,m=60)Fig.5 Comparison of HCGBS algorithm and traditional K-means-SLIC algorithm(k=300,m=60)

图5(b)中，矩形框出了K-means-SLIC算法的欠分割区域，图5(a)中是本文HCGBS算法对其欠分割区域再分割后的图像。从图5(c)可以看出，本文HCGBS算法对图中的所有欠分割区域进行了聚类再分割，分割精度高，且完整地将欠分割区域中的背景和前景分割出来，其分割效果更加精准。

图6是本文HCGBS算法与传统的GBS算法、K-means-SLIC算法、SLIC算法在BSDS500数据集的500幅图像进行的部分比较图。为了保证比较结果的鲁棒性和真实性，固定四种算法生成的超像素数均为400，紧凑度均为60，阈值T均为每个算法生成的每个超像素块中的像素均值，而本文HCGBS算法与GBS算法的标准差均为0.716 5。从图6中可以看出：本文算法与其他传统算法相比能够在分割出较少区域的情况下，分割出更多的正确边界，使分割精度更加贴合真值(GT)。

(a) HCGBS (b) GBS (c) K-means-SLIC (d) SLIC图6 四种算法的分割图(k=400,m=60)Fig.6 Segmentation graph of four algorithms(k=400, m=60)

3.2 评价指标

图像分割图是从人的视觉感官上来反映分割结果的优劣程度，故而不能精细地反应分割结果的好坏。为了检验本文算法的分割有效性，采用常用的性能评价指标边缘召回率BR和欠分割错误率UE[23]。BR表示图像分割边界在一个小邻域内检测到的边界真值的分数，其数学定义如下：

(6)

其中：b(s)表示所用算法产生的边缘分割结果；b(g)表示手工分割的边缘真值；函数I(·)是用来判断算法产生的分割边界点是否在b(g)中像素θ的区域内，A(·)表示每块分割区域的面积。

UE是用来衡量算法生成的类别区域超出图像真值范围区域的程度，其数学表示为：

(7)

其中，sn为生成的分割区域块。本文算法的两种分割性能的评价标准如图7所示，通过图可以看出，本文算法对测试库中的数据集分割结果是准确的，且BR越高、UE越小，分割结果越精细。

(a) BR

(b) UE图7 边缘召回率BR和欠分割错误率UE的趋势Fig.7 Trend chart of edge recall rate BR and under segmentation error rate UE

4 结论

本文将层次聚类算法与GBS算法融合在一起构成HCGBS算法，该方法通过设置层次聚类算法的距离阈值T为像素的均值，同时采用多线程并行处理数据的方式改善传统层次聚类算法的处理速度，实现了自适应地对GBS算法分割后的图像区域进行再次分割，有效地解决了K-means-SLIC算法存在的欠分割问题，并且它不会改变GBS算法的原始分割结果。经过多次对比实验表明，本文算法产生的图像分割结果更加精细，精确度更高，为图像预处理技术的发展奠定了更好的基础。