多尺度归一化割用于遥感图像分割

黄煌，肖鹏峰，王结臣

(1.江苏省地理信息技术重点实验室，南京 210023；2.南京大学 地理信息科学系，南京 210023)

多尺度归一化割用于遥感图像分割

黄煌1，2，肖鹏峰1，2，王结臣1，2

(1.江苏省地理信息技术重点实验室，南京 210023；2.南京大学 地理信息科学系，南京 210023)

针对高分辨率遥感图像数据量大、地物类型丰富、纹理结构复杂等特点，该文利用多尺度归一化割方法进行高分辨率遥感图像的分割。该方法是一种从全局出发的基于图论的分割方法，能够兼顾粗糙层和精细层的信息，适合复杂地物的分割。利用南京某区域Ikonos数据进行了实验，并与主流遥感图像分割软件eCognition中多尺度分割模块进行了效果对比和定量评价。结果表明，该方法在高分辨率遥感图像分割中可以取得较好的效果，具有较好的研究前景。

图像分割；遥感图像；多尺度；归一化割；精度评价

0 引 言

随着卫星及传感器技术的不断发展，卫星遥感呈现出高空间分辨率、高光谱分辨率和高时间分辨率的趋势，其中高空间分辨率是目前遥感应用领域普遍关注的指标。高空间分辨率遥感为经济建设、国防安全和社会公众信息服务等领域提供了重要的数据源。遥感图像分割是高空间分辨率遥感图像理解和地物识别的关键问题，也是有效利用地物信息的基础[1]，它可以将遥感图像的同质区域分离开，使后续的分析和应用可以针对同质区域进行，有效提高地物识别的精度和效率。高空间分辨率遥感图像空间分辨率高，不同地物分异明显，纹理信息丰富，有利于提高图像分割的精度，但图像数据量大、含多尺度信息等使得高空间分辨率遥感图像分割成为一个难题。

归一化割是一种基于图论的图像分割方法。图论是离散数学的一个分支，它是以图为研究单位，研究顶点和边组成的图形的数学理论和方法。图论在数据聚类和图像分割中的应用可以追溯到1971年Zahn的工作[2]，他提出的基于最小生成树的图像分割方法，使用固定阈值进行图像分割和点聚类。基于图论的图像分割方法具有广泛的数学基础，并具有能捕获全局特征的优点，从而在图像分割领域广泛应用。Wu和Leahy在1993年将最小割原理应用于图像分割[3]，该方法容易划分出孤立小区域。Shi和Malik克服了最小割准则中容易划分出孤立小区域的缺点，于1997提出的归一化割方法[4]，并很快得到广泛应用。

但是，归一化割方法存在明显的缺点：运算量巨大，是一个NP-hard问题。Shi和Malik在实数范围内将该问题转化为一个Rayleigh问题，得到了有效的近似解。后续出现了一些改进算法效率的方法，如Fowlkes首先提出采用Nystrom近似方法[5]，该方法通过采样估计相似度矩阵和特征向量，一定程度上提高了计算效率；Belongie等提出了改进后的Nystrom-Ncut方法[6]；Yu等提出了多类的思想重新定义了分割标准[7]，多类的概念是指把图分成多个不相交的集合，多类谱图求解的特点在于能够在一次循环中求出包含多个分割信息的特征向量。在此方法上，Tolliver等提出了更有效的计算图的Laplace矩阵特征向量的方法[8]；Cour等用多尺度方法改进了多类谱图方法[9]，使求解复杂度呈线性增长，从而使归一化割能处理大规模的数据。此后，研究重点主要在提高分割效果，如Cai等提出基于形状的归一化割方法[10]；Sun等结合纹理信息进行归一化割[11]；Zhang等提出彩色图像中最小化信息丢失的方法[12]；Mei等将K-means方法和归一化割结合[13]等。

针对高分辨率遥感图像数据量大，含多尺度信息等特点，本文采用多尺度归一化割的方法分割遥感图像。该方法可以实现大尺寸遥感图像的快速分割，同时兼顾精细层与粗糙层的信息，适用于高空间分辨率遥感图像的分割。

1 归一化割原理

图G=(V，E)可以分割成两个不相交的集合A和B，A∪B=V，A∩B=Ø，只需移除连接两个集合的边。这两个部分的相似度可以通过移除的边的权重计算。在图像理论语言中，它被称为切割：

(1)

对于一个图像的最优分割是将切割值降到最低。但是这一最小切割准则有利于切割图形中的孤立结点。为了避免切割产生孤立结点，Shi和Malik提出了归一化方法解决这一问题，称为归一化割(normalized cut)：

(2)

2 多尺度归一化割

2.1 权值定义

首先确定图像上任意两点之间的相关性计算方法，考虑亮度、距离、图的边缘等信息，将权值计算方法定义如下：

WI(ij)=e-‖Xi-Xj‖2/σx-‖Ii-Ij‖2/σI

(3)

其中，Xi和Ii分别表示像元位置和亮度。在此基础上定义基于边缘的权值：

WC(ij)=e-maxx∈line(i,j)‖Edge(x)‖2/σC

(4)

结合上述两种权值定义得到如下的相似度计算方法：

(5)

2.2 关联半径

当两点之间的距离大于一定的关联半径r时，设定两点之间的权值为0，这样可以很大程度上提高计算效率。关联半径的设定对于分割结果和分割时间产生很大的影响。对于Ikonos的0.86m分辨率遥感图像(大小为100像素×80像元)设定不同关联半径进行归一化割分割实验，结果如下：

图1 不同关联半径的归一化割分割结果

对不同关联半径图像进行分割所用时间如表1所示。

表1 不同关联半径对应归一化割时间

可以看出随着关联半径的增加，分割时间也逐步增加，而对于图像分割效果，实验图像为单一建筑屋顶遥感图像，可以看出，该建筑屋顶较长。在关联半径为4的分割图像中，我们可以看出，建筑屋顶未被完整分割。在关联半径为8及16的分割图像图1(c)、图1(d)中，可以看到屋顶被完整分割出来。

同时可以看出，不同关联半径的分割效果和效率具有很大影响，因此，将图划分为不同的尺度，对不同尺度采用不同的关联半径进行分割，最后综合不同尺度的分割结果，就可以很大程度上提高分割效率。

2.3 多尺度归一化割算法流程

设有图像I，N为图像I中的总像元数，用I中的像素作为顶点构造赋权图G=(V，E)，构造相似度矩阵W=(wi,j)N×N，并将赋权图G=(V，E)表示为G=(V，E，W)。利用等间距采样的方法将图G分解成不同的尺度。图G的相似度矩阵可表示为：

W=W1+W2+…+WS

(6)

其中，WS表示距离固定空间距离的像元对的相似度：仅当Gr,s-1

图2 多尺度图分解在r=1时一维示意图

通过多尺度分割并行处理多个尺度图的方法，使信息可以在不同尺度图中传播。令Xs∈{0,1}Ns×K为尺度图s中的划分矩阵，如果结点i∈Is属于划分k，则Xs(i,k)=1。 构造多尺度划分矩阵和多尺度对角相似度矩阵如下：

(7)

对于多尺度分割，需要使分割代价在不同尺度间传递。在最精细尺度图上需要考虑所有较粗尺度图中的连接，以达到所有尺度图的一致性分割。为解决所有尺度图的一致性，将较粗尺度图结点的划分矩阵取为其在较细尺度图上投影所包含结点划分矩阵的均值，通过约束多尺度图划分矢量X来实现。对于图层Is+1中的所有结点i：

(8)

采样邻域Pi表示图层Is+1中点i在较精细尺度图Is上的投影，其绝对值简单定义为采样邻域中的结点数目。

定义矩阵Cs,s+1(尺寸为Ns+1×Ns)作为尺度图Is和Is+1之间的跨尺度插值矩阵：

(9)

定义跨尺度约束矩阵C以及跨尺度约束方程：

(10)

使用约束多尺度归一化分割标准：

(11)

并且满足CX=0，X∈{0,1}N*×K，X1K=1N*，其中N*=∑SNS。 上述问题的最优解即为分割结果。

3 实验和分析

3.1 Ikonos图像分割实验

利用2010年南京市栖霞区某地0.86m Ikonos

多光谱遥感图像进行多尺度归一化割实验，得到如下结果：

图3 建筑及农田区域遥感图像及多尺度归一化割结果

可以看出，该算法在建筑区域和农田区域的分割中都取得较好的效果。在建筑区域遥感图像中，所有建筑都被独立分割出来，且大部分建筑边界较好地贴合了实际边界。右侧存在少量房屋分割结果不贴合实际建筑边界的现象，而道路区域由于关联半径大小的原因，难以完整地分割出来，道路分割结果表现为多个断裂的部分，植被区域存在类似问题。对于农田遥感图像，由于一块农田的范围较大，受分割关联半径影响，分割结果存在一定破碎，但是不同块农田的边界都实现了较好的分割，农田周边的绿地区域也都和农田分割开，且分割结果贴合实际边界。中部和左下方的小湖也都较完整地分割出来了。从目视结果分析，可以看出该方法在遥感图像分割中的表现较好，保证了分割结果不同区域内的同质性和不同区域间的异质性，可以满足一般的分割精度要求。

3.2 精度评价

为了进一步评价分割结果，利用主流遥感图像分割软件eCognition中的多尺度分割工具与多尺度归一化割方法进行分割效果比对，原遥感图像采用图3(a)。在eCognition中不断调整参数，得到分割结果较优的几组参数；在多尺度归一化割中分别设定K值为250，300，350，得到如下结果：

从图4中可以看到对于建筑区域，两者都能够较好的区分。多尺度归一化割中，分割块数K值的设定过大或者过小会使分割结果呈现过分割或者欠分割，合理K值下，分割结果较为理想，建筑屋顶分割完整且贴合实际边界，分割结果各区域内同质性较高。eCognition分割结果中，从3幅图中的下方区域，都可以看出分割结果较细碎，部分建筑物边缘扭曲，不能很好体现建筑屋顶的形状，这是由于该方法主要基于局部像元灰度差异进行分割，而多尺度归一化割作为全局的分割方法，结果中建筑轮廓都较完整。此外，两者在单一对象长度较大的道路与植被的分割都存在破碎的现象，在多尺度归一化割中，这是由于关联半径不够大造成的。

为了定量评价分割精度，本文采用Weidner等提出的评价方法来衡量分割精度[14]：

(12)

其中，x，y分别表示训练对象区域和分割结果区域，x通过对实验遥感数据进行人工分割得到。过分割和欠分割定义如下[15]：

(13)

(14)

3个参数的值域都是[0，1]，越接近0表示分割结果越好。用该方法对上文中eCognition与多尺度归一化割实验进行分割精度评价，结果如表2所示。

图4 eCognition基于对象多尺度分割与多尺度归一化割对比

parameterOverSegmentationUnderSegmentationqrMulti-scaleNormalized-cutK=3500.15060.06710.1992K=3000.09340.11940.1936K=2500.07580.12570.2007eCognitionscale:350.15020.10320.2423scale:370.13460.12940.2306scale:390.11670.19860.2754

在两种方法参数的设定上，使实验结果最优，这从上表结果的过分割率和欠分割率中可以看出，得到的过分割率和欠分割率都在近似相等的区间。可以看到，在参数设定合适的情况下，多尺度归一化割方法能够得到较高的分割精度，qr值保持在0.2左右，欠分割率和过分割率都在0.1左右。和eCognition对比可以看出，参数设定合理的情况下，多尺度归一化割的总体分割精度略高于eCognition中的多尺度分割模块。

4 结束语

针对高空间分辨率遥感图像数据量大、地物信息丰富、纹理结构复杂、含多尺度信息的特点，本文利用多尺度归一化割的方法进行高空间分辨率遥感图像的分割，分析了该方法在遥感图像分割中的适用性，并定量评价了分割结果。

通过与eCognition的结果对比和定量评价，可以看出多尺度归一化割方法在遥感图像分割中取得了不错的效果，具有很大的应用前景。但是该方法也存在一些不足：算法的效率较慢，尽管该方法在归一化割的基础上，时间效率有显著提高，但是在分割大尺寸遥感图像仍然较慢；需要预先设定分割块数，要通过几次实验来确定合适的分割块数使分割结果最优。后续将着力研究解决上述问题。

[1] 肖鹏峰，冯学智.高分辨率遥感图像分割与信息提取[M].北京：科学出版社，2012.

[2] ZAHN C T.Graph theoretical methods for detecting and describing Gestalt clusters[J].IEEE Trans.On Computation，1971，20(1)：68-86.

[3] WU Z，LEAHY R.An optimal graph theoretic approach to data clustering：Theory and its application to image segmentation[J].IEEE Trans on PAM I，1993，15(11)：1101-1113.

[4] SHI J，MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(11)：1768-1783.

[5] FOWLKES C，BELONGIE S，MALIK J.Efficient spatiotemporal grouping using the Nystrom method[J].Computer Vision and Pattern Recognition，2001，1：231-238.

[6] FOWLKES C，BELONGIE S，FAN C，et al.Spectral grouping using the nystrom method[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2004，26(2)：214-225.

[7] YU S X，SHI J.Multiclass spectral clustering[J].Computer Vision，Ninth IEEE International Conference on，2003，1：313-319.

[8] TOLLIVER D，COLLINS R T，BAKER S.Multilevel spectral partitioning for efficient image segmentation and tracking[J].Application of Computer Vision，2005，1：414-420.

[9] COUR T，BENEZIT F，SHI J.Spectral segmentation with multiscale graph decomposition[J].IEEE International Conference on Computer Vision and Pattern Recognition (CVPR)，2005，2：1124-1131.

[10] CAI W，WU J，CHUNG A C S.Shape-based image segmentation using normalized cuts，image processing[J].IEEE International Conference on，2006：1101-1104.

[11] SUN F，HE J.The remote-sensing image segmentation using textons in the normalized cuts framework[J].Mechatronics and Automation International Conference on，2009，1877-1881.

[12] ZHANG J，SONG Y，ZHANG Y，et al.A new approach of color image quantization based on Normalized Cut algorithm[J].Pattern Recognition (ACPR)，First Asian Conference on，2011，451-455.

[13] MEI Y C，WEI L K，WEI Y K，et al.Graph-based image segmentation using k-means clustering and normalized cuts，computational intelligence[J].Communication Systems and Networks (CICS&N)，Fourth International Conference on，2012，307-312.

[14] WEIDER U.Contribution to the assessment of segmentation quality for remote sensing applications[J].Proceedings of the 21stCongress for the International Society for Photogrammetry and Remote Sensing，2008.

[15] CLINTON N，HOLT A，SCARBOROUGH J，et al.Accuracy assessment measures for object-based image segmentation goodness[J].Photogrammetric Engineer & Remote Sensing，2010，76(3)：289-299.

Remote Sensing Image Segmentation Based on Multi-scale Normalized Cut

HUANG Huang1，2，XIAO Peng-feng1，2，WANG Jie-chen1，2

(1.JiangSuProvinceKeyLaboratoryofGeographicInformationScienceandTechnology，
NanjingUniversity，Nanjing210023；
2.GeographicInformationScienceDepartment，NanjingUniversity，Nanjing210023)

Due to high-resolution remote sensing images have characteristics of large size，rich feature types，and complex texture，we use multi-scale normalized cut method for high resolution remote sensing image segmentation.The method is a global segmentation method based on graph theory.The method is able to take into account information of coarse and fine layers，thus it is suitable for complex feature segmentation.We use Ikonos image of a region of Nanjing to conduct experiments，and to compare it with multi-scale segmentation module in mainstream segmentation software eCognition.The evaluation results show that the method can achieve sound results for high-resolution remote sensing image segmentation，which has good research prospects.

image segmentation；remote sensing image；multi-scale；normalized cut；accuracy assessment

2014-08-22

2014-10-06

全球变化研究国家重大科学研究计划课题(2011CB952001)；江苏高校优势学科建设工程项目(PAPD)。

黄煌(1992—)，男，本科，研究方向为遥感图像处理。

E-mail：huangyymail@163.com

10.3969/j.issn.1000-3177.2015.05.003

TP751

A

1000-3177(2015)141-0020-06