一种结合超像素和图论的高空间分辨率遥感影像分割方法

姚丙秀， 黄亮,2， 许艳松

(1.昆明理工大学国土资源工程学院，昆明 650093； 2.云南省高校高原山区空间信息测绘技术应用工程研究中心，昆明 650093)

0 引言

随着对地观测卫星技术的不断发展，高空间分辨率遥感影像已经广泛应用于城市规划、作物分类、灾害监测、生态环境评价和土地资源调查等领域[1]。高空间分辨率遥感影像具有成像光谱波段多、地物纹理信息丰富、地物轮廓和形状信息更加清晰、重访时间短等优点，这些优点提高了地物信息利用的便利性和时效性，但同时也会增加遥感影像分割的难度。影像分割是高空间分辨率遥感影像信息挖掘与目标识别的智能化的必要前提和重要基础[2]，是指将影像划分为不重叠的相互独立的若干区域。传统影像分割技术是根据影像的灰度、几何形状、空间纹理等特征，获取目标以便于进行图像信息的获取与描述。目前对影像的处理大部分以像素为单位，较少考虑像素之间的空间组织关系，这导致算法处理的效率过低。传统基于像素的影像分割方法，容易形成过分割的问题，难以得到理想的分割结果，如K均值聚类方法[3]和层次聚类方法[4]等。

超像素由Ren等[5]首次提出，是对具有相似纹理、颜色、亮度等特征的相邻像素进行聚类，得到了形状不完全规则但有一定视觉意义的像素块。此方法仅用少量的超像素代替大量的原始像素来表达影像特征,在很大程度上提高了图像处理效率，一经提出便引起了广泛关注，目前已成功运用于计算机视觉、遥感影像处理等领域。超像素算法大致可分为基于图论的算法和基于梯度下降的算法2大类[6]。基于图论的代表算法有图割算法[7]、种子点超像素算法[8]、超像素网格算法[9]，熵率的超像素分割算法[10]、伪布尔超像素算法算法[11]、图片范围切割算法[12]以及基于懒惰随机游走在超像素分割算法[13]等； 基于梯度下降的算法有分水岭法[14]、均值漂移算法[15]、简单线性迭代聚类法(simple linear iterative clustering，SLIC)[16]、线性谱聚类算法[17]、归一化切算法[18]、涡轮像素算法[19]以及基于密度聚类算法的超像素分割[20]等。其中，SLIC算法思想简单，可以基于颜色和距离的相似性生成大小均匀、形状规则的超像素，分割结果的边界紧凑度较高，且是当前效率最高的超像素分割算法，因而受到社会的广泛关注和应用。

采用超像素分割方法可以提高高空间分辨率遥感影像处理的容易度和运算效率，且有效降低了高空间分辨率遥感影像局部信息的冗余度，但也会造成大量过分割的现象，仍会给后续信息提取带来一些问题。为此，本文提出一种结合超像素和图论的分割方法，首先采对高空间分辨率遥感影像用SLIC算法形成初始超像素，进行过分割影像处理； 然后采用图论在初始超像素的基础上，重新获取种子点进行对象合并，从而获取最终的分割结果。

1 结合超像素和图论的分割方法

本文先把超像素作为区域单元，根据区域间的邻接关系与属性差异建立连接，再用图论算法对超像素进行聚类合并，使得最终结果在同一簇中的区域具有最大的同质性和最小的异质性。首先根据设定初始分割数进行分割，生成连接所有超像素的区域单元，利用曼哈顿距离计算相似矩阵的相似性，设置一个n像素×n像素的移动窗口，计算窗口内像素的光谱属性标准差的平均值,即局部方差，涉及分割尺度问题。每次分割合并后求取局部方差，直至局部方差最小，以获取合适的分割数。方法主要分为4个步骤：

1)设定初始影像分割数，采用SLIC算法对遥感影像进行过分割生成超像素。

2)运行图论算法对超像素分割进行合并。

3)得到每次合并的分割数对应的局部方差，确定合适的影像分割数。

4)根据合适影像分割数，再次采用图论算法对超像素重新聚类合并对象，得到最终分割影像。

1.1 SLIC算法

SLIC算法是Achanta等[16]在2010年的时候提出的一种简单且方便的算法，它用5维特征向量来构建像素的度量标准，首先将彩色影像转换为CIELAB颜色空间和XY坐标下的5维特征向量，然后对像素使用改进的K均值聚类算法进行聚类生成超像素。具体步骤如下：

2)种子点的判断。在3像素×3像素种子点的邻域内，将分割区域内的像素的梯度值全部计算出，并在固定的窗口中将其移到最小的梯度值上。这是为了使种子点不落在大的梯度值上，以免影响后续的聚类结果。

3)为每个种子点周围的每个像素点分配一个类标签。与标准K均值算法搜索整个影像不同，SLIC的搜索范围仅限于2S×2S(图1)，这样可以加快算法的收敛速度。

(a) 标准K均值搜索整个影像 (b) SLIC搜索有限区域

图1 像素搜索范围示意图

Fig.1Pixelsearchscope

4)距离测量。对于每个搜索像素，计算它与种子点之间的距离，包括颜色距离和空间距离，即

(1)

(2)

式中：j为种子点；i为影像中搜索像素点；Dc为影像中颜色距离；Ds为空间距离，随着聚类的改变而改变。则像素与种子点间的距离D′为

(3)

式中：D′为2个像素的相似程度，s为种子点的间距；m为平衡参数，通常选取一个不变的常数，将其取值范围设置为[1，40]，用来平衡颜色值与空间信息在相似度的比重。

5)迭代优化。对步骤1)—4)进行迭代。理论上，直到误差收敛才会停止迭代(每个像素簇中心几乎是不变化的)。

6)增强连通性。经步骤5)后可能出现多重连接条件、超像素的范围不够大等问题，这些都可以使用增强连通性来处理。主要思想是： 创建一个标签列表，将表元素设置为-1，根据自顶到底、从左往右的顺序，把间断的超像素按照一定的次序将其与其他邻域的像素相结合，然后将标签与其对应像素点进行匹配，按照此种操作将所有的点都操作一遍。

1.2 图论算法

图由顶点(vertex)的集和边(edge)的集组成[21]。在图中使用点或圆来表示顶点，连接2个顶点的线段的边代表2个对象的连接关系。图论算法首先将影像映射为带权无向图G=，V，E分别为影像中的顶点和边。影像中每个节点也就是图的顶点对应于的每个像素，每条边连接着一对相邻的像素，边的权值表示相邻像素之间特征的非负相似度，而对影像的每一个分割就是对图的一个剪切，被分割的每个区域对应着图中的一个子图。V为图的顶点集合，E为图的边集合。e(vi,vj)∈E定义为一对顶点的边，w(vi,vj)为e(vi,vj)∈E对应的2个像素之间的差异程度，是非负度量。在影像分割中，V被分割成独立的连通区域Ci，则有

(4)

使分割的子图在内部特征相似度最大，子图之间的差异性也最大。基于图论的分割方法的本质是不断移除特定的边，将图分割为若干子图，其优点在于可以充分利用各分割区域相似性与邻接关系进行区域划分。图论对SLIC算法获取的超像素进行合并方法的步骤如下：

1)设定初始影像分割数，采用SLIC算法初始化种子点(聚类中心)，对遥感影像进行过分割生成超像素。利用生成的每个超像素看作一个数据点，用一个无向图G=表示要分割的影像。

2)建立新的矩阵，输入期望的合并区域数量，图论算法检测到的所需合并的簇数，不断移除特定的边，构建多个连通子图，最终形成连通分量。

3)得到生成超像素的图论算法矩阵，2个相邻超像素的像素点i与j的距离为dij，根据训练数据使用曼哈顿距离定义超像素di和dj之间的相似性测度，其中di和dj表示相应的超像素的特征属性。以每次分割生成图论算法中包含的超像素区域作为每次分割情况求残留误差。

4)在此基础上不断迭代，原始聚类中心在3像素×3像素种子点的邻域内，并在固定的窗口中将其移动，重新搜索标记，聚类中心终止的条件是残留误差在新聚类中心和原始聚类中心小于阈值范围，此数据点为聚类中心，直至残留误差最小。聚类中心重新建立，得到分割结果。

2 实验与分析

2.1 实验设计

本文选取了4幅不同空间分辨率、不同场景的高空间分辨率遥感影像来验证本文方法的有效性。为了更好地进行精度评价，实验设计了2种方法与本文方法进行对比，一是传统的SLIC方法，二是eCognition软件中的多尺度分割方法(即分形网络演化方法(fractal net evolution approach，FNEA))，其中FNEA算法使用2组不同尺度参数。SLIC方法的参数K设置为500； 2组FNEA方法的形状异质度和紧致度参数分别固定为0.4和0.5，尺度参数分别设置为50和100，下文记作FNEA(50)和FNEA(100)； 本文方法合并参数设置为分别为68，26，25，108。

实验采用定性和定量2种方法进行精度评价。定性采用视觉比较的方法； 定量采用P-R方法[22]，具体计算公式为

Presicion=TP/(TP+FP)，

(5)

Recall=TP/(TP+FN)，

(6)

式中：Precision为分割精度；Recall为边界召回率；TP为地物被正确分割的样本个数；FP为背景像素被分为地物的样本个数；FN为地物像素被分为背景的样本个数。

实验环境为Inter(R)Pentium(R)四核CPU，4GB内存，Windows10操作系统，实验平台为MATLAB2018a和eCognition Developer。

2.2 实验结果

2.2.1 实验1结果与分析

实验1使用的数据为经Pansharpen融合后的QuickBird影像，包含红、绿、蓝和近红外4个波段，大小为2 480像素×975像素，空间分辨率为0.61 m。该影像主要包括道路、水体、植被等地物，如图2(a)所示； 图2(b)为遥感影像对应的参考分割结果； 影像SLIC方法生成的超像素结果如图2(c)所示，可以看出整体过分割严重，特别是水体分割破碎。为了更好地进行视觉比较，分别在图2(d)—(f)影像中的水体区域标注了红色矩形框。可以看出在内部光谱特征变化较大的水体区域内FNEA(50)产生了大量的过分割现象； 而采用FNEA(100)虽然提高尺度参数减少了过分割，但过分割的问题还是未得到很好地解决； 并且随着尺度参数的增加整个影像的过分割仍比较严重； 本文方法可以较好地区分植被与水体，水体有了很好的合并效果，分割完整，且解决了与水体光谱相近的非水体区域被错误合并的问题； 虽然由于影像空间分辨率相对较低造成了较多细小斑块的错误合并，但依然获得了较好的分割结果，对地物的总体分割结果与参考分割结果基本一致。

(a) 原始影像 (b) 参考分割结果 (c) SLIC分割结果

(d) FNEA(50)分割结果 (e) FNEA(100)分割结果 (f) 本文方法分割结果

图2 实验1影像数据及实验结果

Fig.2Imagedataandexperimentalresultsoftest1

根据图2，SLIC方法分割结果过分割明显，分割精度过低，因此不对其进行定量评价。表1列出了FNEA算法和本文方法对图2(a)分割结果的评价结果。从表1可以看出，本文方法分割结果的Precision大于0.8，而2个参数的FNEA算法均低于0.75，分割精度均低于本文方法。虽然空间分辨率对其结果造成一定影响，但本文方法的Recall指标(0.919 6)仍旧显著高于FNEA(50)的0.802 6和FNEA(100)的0.824 8，说明本文方法的实验分割结果与实际地物结果较为一致。

表1 实验1分割结果评价Tab.1 Segmentation results evaluation of test1

2.2.2 实验2结果与分析

实验2使用的数据为无人机高空间分辨率遥感影像，包含红、绿、蓝3个波段，大小为726像素×468像素； 空间分辨率为0.05 m。该影像主要包括房屋、道路、植被等地物(图3(a)); 图3(b)为高空间分辨率遥感影像对应的参考分割结果； 影像过分割生成的超像素结果如图3(c)所示。从分割的区域可以看出，采用SLIC方法过分割情况明显。为了便于视觉比较分别在图3(d)—(f)的影像中标注了红色矩形框。红色矩形框所标定的是道路区域，在内部光谱特征变化较大的道路区域内FNEA(50)和FNEA(100)都产生了大量的过分割现象，FNEA(100)在50到100尺度参数不断变化的时候，过分割得到优化，但是小尺度地物依然存在过分割现象; 从图3(f)可以看出采用本文提出的方法道路被完整分割。裸地也得到了很好的合并； 植被由于光谱异质性较大，虽然也有了较好的合并但还存在过分割现象。这进一步说明了本文方法的优越性。

(a) 原始影像 (b) 参考分割结果 (c) SLIC分割结果

(d) FNEA(50)分割结果 (e) FNEA(100)分割结果 (f) 本文方法分割结果图

图3 实验2影像数据及实验结果

Fig.3Imagedataandexperimentalresultsoftest2

同样由于SLIC方法分割结果过分割明显，分割精度过低，仅对FNEA算法和本文方法对图3(a)的分割结果进行评价，如表2所示。从表2中可以看出，本文方法分割结果的Precision为 0.856 3，大于0.85，与FNEA相比分割精度得到了显著的提高，能够将建筑物、道路、绿地等地物很好地区分开。虽然FNEA(50)和FNEA(100)的Recall指标分别达到0.823 6和0.896 3，都得到了不错的分割效果，但本文方法的Recall为0.956 8，高于0.95，分割效果更佳。

表2 实验2分割结果评价Tab.2 Segmentation results evaluation of test2

2.2.3 实验3结果与分析

实验3使用的数据为无人机高空间分辨率遥感影像，包含红、绿、蓝3个波段，大小为979像素×586像素； 空间分辨率为0.05 m。该影像主要包括房屋、道路、植被等地物(图4(a)); 图4(b)为影像对应的参考分割结果； 影像过分割生成的超像素结果如图4(c)所示。从分割的区域可以看出，采用SLIC方法依然存在严重的过分割情况。同样分别在图4(d)—(f)的影像中标注了红色矩形框。红色矩形框所标定的是房屋区域，FNEA(50)和FNEA(100)都产生了大量的过分割现象，由于分割区域的建筑光谱异质性特别大，FNEA方法则难以区分出光谱相似的房屋对象，出现过分割现象。本文方法较好地区分了房屋与道路，较为完整地保留了房屋、植被等细小区域，可以较好地平衡影像过分割的情况。

(a) 原始影像 (b) 参考分割结果 (c) SLIC分割结果

(d) FNEA(50)分割结果 (e) FNEA(100)分割结果 (f) 本文方法分割结果

图4 实验3影像数据及实验结果

Fig.4Imagedataandexperimentalresultsoftest3

表3列出了2种方法对图4(a)分割结果的评价结果。从表3可以看出，本文方法分割结果的Precision为0.841 2，均高于于2种不同分割尺度FNEA方法(0.756 9和0.768 9)，说明本文方法对地物分割结果优于FNEA方法； 此外本文方法的Precision高于0.84，说明它对地物的分割结果与实际地物较为一致。本文方法的Recall指标为 0.940 5，分割结果与对应参考对象的边界吻合程度都最高(但彼此间仍存在一定差异)，均高于FNEA(50)的0.819 6和FNEA(100)的0.879 2，说明其分割结果更加合理有效。

表3 实验3分割结果评价Tab.3 Segmentation results evaluation of test3

2.2.4 实验4结果与分析

实验4使用的数据为无人机高空间分辨率遥感影像，包含红、绿、蓝3个波段，大小为1 706像素×1 546像素。空间分辨率为0.05 m。该影像主要包括房屋、道路、裸地等地物(图5(a)); 图5(b)为影像对应的参考分割结果； 影像过分割生成的超像素结果见图5(c)。分别在图5(d)—(f)的影像中部分房屋区域标注了红色矩形框。从分割的区域可以看出，采用SLIC依然存在严重的过分割情况。红色矩形框中FNEA(50)和FNEA(100)依旧产生了大量的过分割现象。FNEA方法由于分割区域范围增大，相比小尺寸影像错误分割要多一些。该方法也难以区分光谱相似的房屋及裸地对象，出现了大量的过分割和欠分割现象。本文方法较好地区分了房屋与裸地，较为完整地保留了房屋、裸地的边界分割线； 绝大部分地物也被完整地分割出来。说明本文方法也适用于区域范围较大影像的分割。

(a) 原始影像 (b) 参考分割结果 (c) SLIC分割结果

(d) FNEA(50)分割结果 (e) FNEA(100)分割结果 (f) 本文方法分割结果

图5 实验4影像数据及实验结果

Fig.5Imagedataandexperimentalresultsoftest4

表4列出了2种方法对图5(a)分割结果的评价结果。从表4可以看出，本文方法分割结果的Precision均高于2种不同分割尺度FNEA方法，说明本文方法对尺寸较大影像的地物分割结果也同样优于FNEA方法。此外本文方法的Precision为0.801 3，精度高于0.8，说明其分割结果获得了良好效果。本文方法的Recall指标为0.855 6，分割结果与之对应参考对象的边界吻合是最高的，但是彼此之间仍然存在一定差异，精度受到了影响，但均高于FNEA(50)的0.752 6和FNEA(100)的0.798 6，虽然算法精度比尺寸较小影像的分割精度要低一些，但是2个评价指标都显著优于FNEA方法。说明本文方法对尺寸较大的高分遥感影像的分割结果也有一定的应用价值，是合理有效的。

表4 实验4分割结果评价Tab.4 Segmentation results evaluation of test4

综上可知，本文方法对地物的分割结果与分割参考图较为一致。FNEA方法在实验的尺度下都存在明显的过分割现象。在较小分割尺度中，实验影像存在明显的过分割现象，如图3(a)中影像区域内的房屋。随着尺度参数的数值加大，房屋的分割效果显著变好，但是较小尺度地物如图3(f)中影像区域内却没有分割出来，即存在欠分割现象。本文方法很好地解决了消除过分割现象问题，而且较好地保持了分割对象边界的贴合度信息，分割的精度得到了明显提高。总而言之，对于影像内光谱特征变化较大的同种地物，FNEA易产生过分割现象，而本文方法可以较好地消除影像的过分割现象。总之，本文方法在超像素过分割结果的基础上，可进行对象合并和小尺度分割。实验表明，尺寸很小的建筑物细节能得到很好的保留； 较大尺度的地物，如水体、植被等，也可以得到完整、规则的分割。

3 结论

本文提出了一种结合SLIC超像素和图论的高分辨率遥感影像分割方法，解决了易形成过分割的问题，提升了高空间分辨率遥感图像的分割精度。本文算法将图论算法结合到超像素影像分割中，通过实验验证，得出如下结论：

1)将SLIC分割方法引入高空间分辨率影像分割算法中，产生的超像素对象边缘贴合度以及紧密度较好、超像素内部的同质性较高，避免了地物细节信息丢失的问题； 使影像更充分地利用空间背景信息，而且同时提高了分割效率。

2)将图论算法结合超像素，相比于SLIC分割方法，可以抑制超像素与实际地物过分割不完全符合造成的误差，该方法能够更为精确地完整分割地物，很好地解决了影像过分割的问题，获得了良好的合并结果，有利于提高分割精度。

3) 在结合SLIC超像素和图论的高分辨率遥感影像分割方法中，高空间分辨率影像的分辨率越高，分割效果越好，精度也越高； 地物类型越复杂，分割难度随之增加，分割精度会随之下降。

对实验结果的分析表明，不同影像的最佳参数选择可能存在差异； 不同空间分辨率影像的分割精度也会有差异。针对某些特殊目标和地物类型复杂的分割问题，以及如何合理选择初始样本以及初始样本中各类别样本数目提高算法的泛化能力和效率是后续研究的目标。