基于锚点建图的半监督分类在遥感图像中的应用

童佳楠

摘 要： 针对基于图的半监督图像分类方法扩展性差的问题，结合了mean shift图像聚类算法和基于锚点建图的方法并将其应用于遥感图像的分类中。首先采用mean shift聚类算法对遥感图像聚类；其次根据基于锚点建图的半监督分类方法，选取聚类中心作为锚点，利用锚点集和标记样本集建图，达到缩小图规模的目的，并建立锚点与样本间的关联矩阵；然后通过分类器得到锚点的标记信息；最后由样本与锚点间的关联矩阵还原得到遥感图像的分类结果。实验结果表明，该方法对遥感图像分类时，能够有效地降低计算复杂度，同时获取较好的分类结果。

关键词： 遥感图像； 图像分类； mean shift； 锚点

中图分类号： TN957.52?34； TP79 文献标识码： A 文章编号： 1004?373X（2016）22?0092?0

0 引 言

遥感图像具有较高的光谱分辨率，在航天、地质勘探、农业等领域获得了越来越多的应用，遥感图像分类在遥感图像应用中具有重要的作用。但对遥感图像分类也面临以下难题：其一是如果采用传统的非监督方法对遥感图像直接分类，因遥感图像的复杂性和特殊性，很难获得比较满意的结果；其二采用监督方法，需要运用大量的训练样本才能获取较好的分类结果，而标记样本的获取代价高昂，也容易出现分类器过拟合与训练样本的问题。

半监督学习[1]可以很好地解决上述问题，首先大量的廉价的无标记样本也包含样本特征信息，其次遥感图像中标记样本的获取十分昂贵。半监督学习可以利用少量的已标记样本，结合大量的无标记样本建立分类器完成学习任务。基于图的半监督图像分类在近年来图像研究领域成为了一个研究热点，此方法结合图理论，能够充分利用图像中的无标记样本信息，分类性能较好，且目标函数优化简单，因此更加高效，目前也有许多基于图的半监督分类方法[2?6]。

基于图的半监督图像分类方法是建立在图理论的基础上，但算法计算速度依赖于所构建图的规模大小，当数据规模过大时，如果还是每一个图节点代表一个样本点，图规模就会很庞大，计算的时间复杂度会很高，例如线性近邻传递算法（Linear Neighborhood Propagation）、局部与全局一致性算法（Local and Global Consistency），其计算复杂度为[O（n3）]，[n]为样本个数。为了降低算法的复杂度，Blum 和Chawla提出了图的最小割（Mincut）算法，并将其时间复杂度降低到了[O（cn2）]，这里[c]为类别数。但最小割算法可能存在多个解，得到不同的分类结果。

2010年Liu等提出基于锚点建图的半监督分类方法[7]（Anchor Graph Regularization，AGR）。首先采用K?means算法对数据聚类，将聚类中心作为锚点得到锚点集，其次利用锚点与已标记样本建图，缩小了图规模，时间复杂度降为[Om2n，m?n]，[n]为样本总数，[m]为聚类个数。但K?means聚类算法消耗时间过长，且遥感图像混合像元问题使部分像元很难进行非此即彼的划分，部分区域地物类别边界是过渡性的，没有明显边界划分，因此K?means不适宜对遥感图像聚类。针对上述问题，本文采用mean shift聚类算法代替K?means算法对遥感图像聚类，缩短了聚类时间，mean shift算法对噪声也有一定的鲁棒性，可以解决噪声点带来的干扰，提高聚类的有效性。其次在每个聚类中随机选取一个点作为锚点，得到锚点集，并与标记样本集建立图。该方法不仅降低了算法复杂度，可以处理大规模图像分类问题，同时在遥感图像分类中具有较好的分类结果。

1 AGR图像分类方法

设样本数据集为[x=xini=l?Rd]，共有[n]个样本，[l]个是已标记样本，剩余的为未标记样本。为了解决大规模数据问题，将标记预测函数定义为一个对锚点的加权平均函数，当得到锚点的类别信息后，就可以通过映射关系得到与锚点密切相关的无标记样本的类别信息。将锚点加权平均函数表示为：[UA=ukmk=1?Rd]，其中[uk]代表锚点，标记预测函数为：

[f（xi）=k=1mZikf（uk）] （1）

在这里定义两个向量[f=[f（x1），f（x2），…，f（xn）]T]和[a=[f（u1），f（u2），…，f（um）]T]；[a]为锚点的软标签预测矩阵；[m]为锚点个数。式（1）可以写成：

[f=Za， Z∈Rn×m， m?n] （2）

其中Z是一个权值矩阵，表示了锚点与所有样本点的线性关系：

[Zik=Kh（xi，uk）k∈Kh（xi，uk）， ?k∈] （3）

这里使用的是高斯核函数[Kh（xi，uk）=][exp-xi-uk22h2]。[?[1：m]]是一个保存[xi]的[s]个最近邻锚点的索引，为了提高计算效率，规定每一个样本[xi]只与[s]个[Zik]中值最大的锚点具有连接关系，其他连接均为0。

由Z矩阵可以得到邻接矩阵：

[W=ZΛ-1ZT] （4）

式中，[Λ∈Rm×m]是一个对角矩阵：

[Λkk=i=1nZik] （5）

由[s]的取值可以知道，所有的样本点都只与部分近邻锚点存在连接关系，所以矩阵W是稀疏的。Zhu提出稀疏图对算法的性能的影响优于全连通图[1]。因为全连通图中，每个样本的邻接信息中含有大量重复的、干扰的信息，而稀疏图在连接不同样本时含有较少的错误信息，对算法结果有正确的指导。由式（4）定义的邻接矩阵所构造的图就是Anchor Graph。最后Anchor Graph的图拉普拉斯矩阵为：

[L=D-W=I-ZΛ-1ZT] （6）

式中：D为对角线矩阵，[Dii=j=1nWij]。

2 本文方法流程

假设已标记样本[xi（i=1，2，…，l）]，其标记信息为[yi∈{1，2，…，c}]，[c]为类别个数。用[Y=[y1，y2，…，yc]∈Rl×c]表示已标记样本的标记信息，如果[yi=j]，[Yij=1]，否则[Yij=0]。用mean shift聚类算法对遥感图像进行聚类，得到各个类别的聚类中心，把每个聚类中心作为一个锚点，得到AGR方法中的锚点集合。此时就需要求得锚点的标签预测矩阵[A=[a1，a2，…，ac]∈Rm×c]。选择被广泛应用的图拉普拉斯正则化项[ΩG（f）=12fTLf]，可得到半监督学习框架 ：

[minA=[a1，a2，…，ac]Γ（A）=12j=1cZlaj-yj2+γj=1cΩG（Zaj） =12ZlA-Y2F+γ2tr（ATZTLZA）] （7）

式中：[Zl∈Rl×m]是[Z]矩阵的子矩阵，只包含标记样本；[·F]是Frobenius范数；取[γ>0]，为正则化参数。那么缩小后的拉普拉斯矩阵为：

[L=ZTLZ=ZT（I-ZΛ-1ZT）Z =ZTZ-（ZTZ）Λ-1（ZTZ）] （8）

缩小后的拉普拉斯矩阵存储空间更小，易于计算，空间复杂度为[O（m2）]，时间复杂度为[O（m3+m2n）]。这时，目标函数[Γ（A）]进一步简化为：

[Γ（A）=12ZlA-Y2F+γ2tr（ATLA）] （9）

最后，就可以得到全局最优解：

[A*=（ZTlZl+γL）-1ZTlY] （10）

得到了锚点的标记信息，那么未标记样本的标记信息就可以通过下式得到：

[yi=argmaxj∈{1，2，…，c}Ziajλj， i=l+1，l+2，…，l+n] （11）

式中：[Zi∈Rl×m]表示Z矩阵的第i行。[λj=ITZaj]表示归一化因子，作用是平衡倾斜的类分布。

具体的算法步骤如下：

输入：已标记样本[xi（i=1，2，…，l）]，标记信息[yi∈{1，2，…，c}]

输出：图像分类结果

（1） 用mean shift算法对遥感图像进行聚类，得到m个类，从每一个聚类中选取一个点作为锚点；

（2） 选择合适的[γ]；近邻锚点个数s取3；

（3） 计算Z矩阵，根据式（4）计算邻接矩阵W；

（4） 根据式（6）计算图拉普拉斯矩阵L；

（5） 根据式（10）计算锚点标签预测矩阵[A*]；

（6） 根据式（11）计算未标记样本的标记。

3 算法复杂度分析

基于图的半监督分类方法，大多数方法中是每个样本作为一个图节点建立图，所以计算复杂度为[O（n3）]，其中[n]是样本个数。本文方法中，mean shift的计算复杂度是[O（dn2t）]，其中[d]是数据的空间维度，[t]是迭代次数；基于锚点的算法的计算复杂度[7]是[O（m2n）]，所以本文方法的计算复杂度是[O（dn2t）]+[O（m2n）]，且m是聚类后得到的聚类中心个数，[m?n]，所以本文方法的计算复杂度是远小于原始基于图的半监督分类方法的计算复杂度[O（n3）]。

4 实验结果与分析

本文在Matlab R2012a下计算机内存为2 GB，CPU为Intel Core i3，频率为2.53 GHz的机器上运行实验。实验采用的遥感图像是IKONOS卫星图像，IKONOS卫星图像包含一个全色波段，分辨率为1 m，四个多光谱波段，分辨率为4 m。图像大小为400×400，实验中对四个多光谱波段构成的遥感图像进行分类，3个RGB多光谱波段构成的真彩色图像如图1所示。根据实验区的特点，具体样本分类类别如表1所示。

图1中最左侧两片颜色灰白的区域是水泥建筑场地，右上侧灌木林中间的一个蓝色区域是一个房屋，这两片区域在本文实验中都归为“公路居民区”类别。因此本次实验样本类别个数为：“农田”像元点数32 433，“荒裸地”像元点数41 825，“植被”像元点数67 978，“公路居民区”像元点数17 764。

原文方法采用K?means聚类算法，不适应对遥感图像聚类，所以本文对遥感图像的分类结果并未与原文方法进行对比，而与遥感图像处理平台ENVI自带的监督支持向量机（SVM）方法进行对比。

本文实验SVM方法参数取值：核类型（Kernel Type）选择Polynomial，核心多项式的次数取4，Classification Probability Threshold取0，其他参数采用默认值。

本文实验中标记样本均为人工选取，实验分四次，四次实验中每类标记样本个数分别为5，20，50，100，每一次实验中所有实验方法均采用相同的标记样本，且每次实验都在上次已有标记样本的基础上添加新的标记样本。本文对实验结果的评价采用了Kappa系数和像元分类正确率（Pixel Classification Rate，PCR）：

[PCR=正确分类像元数图像总像元数] （12）

图2和图3分别为每类标记样本为50和100时，本文方法和监督SVM方法的实验结果。遥感图像中样本分为四类，红色代表“荒裸地”的样本点，绿色代表“植被”的样本点，蓝色代表“农田”的样本点，黄色代表“公路居民区”的样本点。对比图2和图3，可以发现，本文方法优于监督SVM方法，图4中区域标号图像为1的区域是农田和没有农作物荒裸地区域，没有灌木植被，本文方法明确地分为农田和荒裸地两类，而SVM方法中将一部分样本错分为植被；在标号为2的区域与右上角的空白区域一样均为裸地，本文方法分类效果很好，而SVM方法分类效果显然较差，部分样本错分为农田类别；标号为3的区域中，有一排灌木植被在农田中间，即右侧的很少一部分还属于农田，可以看到还有农作物存在，SVM方法中将此少部分农田错分为裸地，本文方法大部分样本分类正确；在标号4的区域，可以看到是农田和裸地的分界处，而可以明显看到此处属于农田，只不过左侧部分不存在农作物，所以归为裸地类别，在SVM方法分类结果中许多样本点被错分为植被，而本文方法只有极少量样本分错，这是因为半监督学习的流形假设，处于很小局部区域内的样本可能具有相似的标记，此处的样本明显与邻近的农田相似性更大。

对遥感图像的分类精度的评价指标是以分类结果的混淆矩阵为基础，总体分类精度和Kappa系数都要通过混淆矩阵计算得到，而为了更直观地评价两种方法的分类效果和优缺点，本文列出了每类标记样本数为100的分类结果的混淆矩阵：两种方法在每类标记样本为100时的分类结果见表2和表3。

混淆矩阵中每行的总和为每一类样本的真实样本数，每一列的总和为分类结果中每一类的总样本数，括号内的值为混淆矩阵对角线的和，即分类正确的样本总数。漏分误差即每类真实样本中没有被正确识别出来的样本比例；错分误差为分类结果中其他类别样本被错分为此类的样本占总和的比例。

通过混淆矩阵的数字可以直观地看到，本文方法的每一类样本的错分误差都小于SVM方法的错分误差；本文方法对“植被”类别的分类正确率不如SVM方法的分类结果，但本文方法对细节处的分类效果更优于SVM方法，例如在图4中右侧的灌木林，本文方法的分类结果中，琐碎的极少量的裸地都被分出来；“荒裸地”和“农田”类别的样本分类正确率都明显优于SVM方法；而“公路居民”类别正确率低于SVM方法，由混淆矩阵可以看到是错分为“荒裸地”的样本较多，这是因为图4中最左侧的居民区建筑因为曝光太强，错分为“荒裸地”； “公路居民区”类别和“农田”类别样本差别明显，本文方法把“公路居民区”错分为“农田”的样本数为零，而SVM方法的错分数是9，本文方法对类别“公路居民区”和“农田”之间的区分更优；本文方法总体精度和Kappa系数也明显高于监督SVM的。具体的分类结果统计如表4所示。

从表4可以看出，本文方法分类结果明显优于监督SVM方法，而监督SVM方法是ENVI软件的监督分类方法中效果最优的方法[8]，且监督SVM方法在小样本时具有良好的分类效果。但半监督的学习方法，结合无标记样本，优于监督学习方法，提高了分类性能。如标记样本数较少，为5和20时，无标记样本作用明显，分类精度和Kappa系数提高较大。通过观察图像和实验发现，本此实验的遥感图像中样本比较复杂，地物交错比较严重，边界过度不明显，不同于城市居民区边界清晰，这就给分类增加了难度，这也是分类精度不是很高的原因之一。实验结果验证了本文方法在遥感图像分类中的有效性，相比监督SVM方法获得了更好的分类效果。

本文方法在图像聚类选取锚点时采用mean shift聚类算法，聚类样本数160 000，平均用时9.4 s。原文[9]方法采用K?means聚类算法选取锚点，文中给出了两次实验结果中的聚类时间，7 291个样本聚类时间是7.65 s；630 000个样本聚类时间是195.16 s。因此mean shift聚类算法相比K?means算法缩短了聚类时间。

5 结 语

基于图的半监督图像分类方法通常因为数据规模大而导致内存空间不足和分类时间过长，而遥感图像通常规模较大且地物复杂、信息量大，所以影响了其在遥感图像分类中的应用。本文首先采用mean shift算法对遥感图像聚类得到锚点集，利用锚点集和标记样本集建图，缩小了图规模，降低了计算复杂度，其次通过分类方法得到锚点的类别信息，最后映射还原到整个样本集，得到遥感图像分类结果。AGR方法解决了大规模图像分类，本文采用mean shift算法缩短了锚点选取时间。实验结果表明，本文方法在遥感图像分类中获得了较好的分类结果，验证了其对遥感图像分类的有效性。

参考文献

[1] HUANG G， SONG S， GUPTA J， et al. A second order cone programming approach for semi-supervised learning[J]. Pattern recognition， 2013， 46（12）： 3548-3558.

[2] XIE W， LU Z， PENG Y， et al. Graph?based multimodal semi?supervised image classification [J]. Neuro computing， 2014， 138： 167?179.

[3] BLUM A， CHAWLA S. Learning from labeled and unlabeled data using graph mincuts [C]// Proceedings of 2001 International Conference on Machine Learning. San Francisco： ACM， 2001： 19?26.

[4] WANG F， ZHANG C. Label propagation through linear neighborhoods [J]. IEEE transactions on knowledge and data engineering， 2008， 20（1）： 55?67.

[5] ZHOU D， BOUSQUET O， LAL T N， et al. Learning with local and global consistency [J]. Advances in neural information processing systems， 2004， 16（4）： 321?328.

[6] ZHU X J， GHAHARMANI Z， LAFFERTY J. Semi?supervised learning using Gaussian fields and harmonic functions [C]// Proceedings of 20th International Conference on Machine Learning. Menlo Park： AAAI， 2003： 912?919.

[7] LIU W， HE J， CHANG S F. Large graph construction for scalable semi?supervised learning [C]// Proceedings of the 27th International Conference on Machine Learning. Haifa： ACM， 2010： 679?686.

[8] 闫琰，董秀兰，李燕.基于ENVI的遥感图像监督分类方法比较研究[J].北京测绘，2011（3）：14?16.

[9] YU G， ZHANG G， DOMENICONI C， et al. Semi?supervised classification based on random subspace dimensionality reduction [J]. Pattern recognition， 2012， 45（3）： 1119?1135.

[10] CHENG Y. Mean shift， mode seeking， and clustering [J]. IEEE transactions on pattern analysis and machine intelligence， 1995， 17（8）： 790?799.

[11] WANG Y， CHEN S， ZHOU Z H. New semi?supervised classification method based on modified cluster assumption [J]. IEEE transactions on neural networks and learning systems， 2012， 23（5）： 689?702.

[12] D?PIDO I， LI J， MARPU P R， et al. Semi?supervised self?learning for hyperspectral image classification [J]. IEEE transactions on geoscience and remote sensing， 2013， 51（7）： 4032?4044.