基于马尔科夫判别谱聚类的极化SAR图像分类方法

张向荣 于心源 唐 旭 侯 彪 焦李成

(西安电子科技大学人工智能学院，智能感知与图像理解教育部重点实验室，国际智能感知与计算联合研究中心 西安 710071)

1 引言

极化SAR (PolSAR) 图像地物分类在地质勘探、地形分析以及灾害监测等方面具有广泛的应用[1]。随着理论水平的逐年提高，加上图像处理领域的巨大需求，极化SAR图像的分类问题成为了研究领域的热点。

根据算法是否依赖于数据的先验样本，极化SAR图像分类算法可以具体地分为有监督与无监督两大类。无监督分类方法主要是利用极化数据的统计特征对同类型像素进行分类，不需要进行训练，因此当训练样本严重不足的情况下，采用无监督分类方法的优势十分明显。且无监督方法的图像分类过程简单，充分利用了图像的有效信息，适用范围十分广泛。无监督的极化SAR分类主要分为两类：基于地物目标电磁散射特性和统计特性的分类法[2]以及基于聚类分析和图像处理技术的分类法[3]。然而目前基于无监督的方法大多从极化数据的统计特性和散射特性角度出发，很少从图像本身角度去考虑，不能充分利用极化数据的特征信息，无法全面地描述地面目标的物理属性。因此，如何深度挖掘极化SAR图像的特征信息，采用高效的处理方法提高分类精度，是当前极化SAR分类面临的挑战，同时也是本文重点关注的问题。

谱聚类在分析复杂的数据结构信息时，通过得到数据点的不同相似图来预测聚类标签，往往能够显示出其较强的聚类能力。将判别聚类方法应用到极化SAR图像的分类中有两个优点：首先，判别聚类可以将有监督的判别能力引入无监督分类问题中，现有的监督学习工具在弱监督任务和无监督任务中具有良好的重要性能；其次，判别聚类是一个通用框架，它允许将不同的判别损失函数或其他特定领域的约束合并到一个单一的损失函数中，适用于不同的应用程序，并且具有很强的灵活性[4]。

但是，现有的聚类方法只是简单地将数据中的信息组合在一起，产生的噪声会大大降低聚类的性能。为了解决上述问题，本文提出一种基于马尔科夫的判别谱聚类方法(Markov Discriminative Spectral Clustering，MDSC)，具有低秩和稀疏分解的特点。在应用本方法时，首先需要构造一个原始的概率转移矩阵，然后用其恢复一个真实的低秩概率转移矩阵作为标准马尔科夫谱聚类方法的关键输入。为了能够对极化SAR的数据信息进行多层次利用，本文在目标函数中引入了判别信息以提升聚类精度。

对于本方法中的目标函数的优化问题，在概率转移矩阵上有一个低秩约束，同时在该矩阵的每一行上有一个概率单纯形约束，本文提出了一种基于增广拉格朗日乘子法的优化方法来解决这个有难度的优化问题。本文后续在各种实际数据集上进行实验，结果表明，本方法具有较好的准确率，表现出了良好的分类性能。

2 基于马尔科夫的判别谱聚类

2.1 标准马尔科夫谱聚类框架

由随机游走理论分析，当随机游走到某个分类时，在该类中停留的概率较大，游走到其他类的概率较小。由此，Meila等人[5]提出，谱聚类可以用图结构上的马尔科夫随机游动框架来描述。马尔科夫链状态簇是根据每个状态到平稳态的距离进行聚类的，可以在拓扑图上的随机游走框架中连接，状态转移概率图可以看作是一个有向图。由此将谱聚类的图谱理论应用于马尔科夫链中，以达到聚类的目的。求解马尔科夫随机游动的转移概率矩阵的特征值问题可以用来确定图上的归一化分割。本文所用的标准马尔科夫谱聚类算法流程如下：

步骤1 计算所有数据点的相似度，构建相似度矩阵S；

步骤2 计算概率转移矩阵P=D-1S以及它的平稳分布π=Pπ；

步骤3 构造拉普拉斯矩阵L=∏-1/2(∏P+PT∏)，其中∏表示对角元素为π(i)的对角矩阵；

步骤4 对L进行特征分解，得到前k个最小的特征向量；

步骤5 将这前k个特征向量作为矩阵的列向量构建特征矩阵；

步骤6 将特征矩阵的每一行作为数据点，利用k-均值算法对其进行聚类。

2.2 构造概率转移矩阵

在马尔科夫判别谱聚类方法中，最为关键的一步是如何构造一个精确的概率转移矩阵。本文通过低秩和稀疏分解的方法，恢复真实的概率转移矩阵，并将其用作标准马尔科夫谱聚类方法的输入，以获得最终的聚类解决方案。

该方法的基本假设有两个:

(1) 无向加权图G的特征足以发现大部分聚类信息；

(2) 提取的特征可能会被噪声破坏，即这些噪声可能会导致一小部分数据点被分配到错误的类。

图1 真实的概率转移矩阵构造概图Fig. 1 Real probability transfer matrix construction profile

在现实的谱聚类问题中，可以假设同一簇内任意两点之间的转移概率较高，而不同簇内两点之间的转移概率较低且近似为0，从而导致概率转移矩阵的秩往往较低。综上所述，根据这些观察结果可以假设，反映潜在真实聚类信息的概率转移矩阵往往是低秩的。

误差矩阵E表示了P和之间的差异。根据假设，提取的特征足以识别大多数集群结构，所以P中的元素与中相应的元素只有一小部分显著不同，可以说误差矩阵E趋于稀疏。

综上所述，在低秩稀疏假设下，可以将真实的概率转移矩阵构造问题表示为，

由于原始概率转移矩阵P的构建中只考虑了数据点之间的相似度，为了对数据信息进行多层次的充分利用，在目标函数中引入表示判别信息的判别损失函数Ec

其中，Ec表示极化 SAR 图像分类的判别损失函数，1是全一向量，，表示非负平衡参数，迹范数是的秩在谱范数的单位球上的凸包络，在实际问题中，最小化迹范数能够得到理想的低秩结构[6]。表示的每一行都是一个概率分布，这强制保证了一定是一个概率转移矩阵。

2.3 引入判别信息

判别聚类是一个将不同的判别损失函数或其他特定约束合并到一个损失函数中的通用框架。在进行聚类的过程中，可以通过分析不同类别的样本信息，得到各自的特点与规律，进而构建出更加准确的判别准则对数据进行分类。本节将一种新的基于判别聚类的模型引入马尔科夫谱聚类算法中，提高算法的信息利用率，改善分类精度。

本节根据SR模型[7]重新设计了判别损失函数，它结合了判别聚类项和正则项。前一项负责利用判别信息构建softmax损失函数，后一项负责降低由噪声和异常值引起的过拟合。

综上所述，在判别聚类的基础上，将判别损失函数定义为

其中，W表示分类器矩阵，L(P，W|X)是softmax损失函数，R(W)表示正则项。引入softmax损失函数是为了解决由于不同类别的像素数不同而导致的样本不平衡问题，该函数度量了分类器W与原始的概率转移矩阵之间的一致性。用交叉熵来定义softmax损失函数L(P，W|X)

其中，e是自然常数，k表示类的个数。

引用正则项R(W)来降低由噪声和异常值引起的过拟合。R(W)定义如下

判别损失函数Ec(P，W|X)虽然遵循SR模型的式，但本质上是不同的。在softmax分类方法中，训练数据集中的ground-truth类标签为常量。而在判别方法中，类标是在无监督算法下需要通过聚类得到的变量。

3 模型优化求解

在本节中将利用增广拉格朗日乘子法[8]来解决上一节中低秩和概率单纯形约束下的目标函数优化问题。与朴素拉格朗日方法相比，该方法提高了算法的鲁棒性，并放宽了函数的强凸约束，使变换后的问题更易于求解。

下面根据 Xia 等人[9]提出的鲁棒多视角谱聚类(Robust Multi-view Spectral Clustering， RMSC)方法，对，E，Ec进行更新求解。

首先假设Ec是已知的，式(2)对应的增广拉格朗日函数为

其中，H是拉格朗日算子，μ>0是自适应惩罚参数。

(1) 求解E固定时，优化问题可以简化为

利用奇异值阈值法[10]可以得到E的近似解

(3) 求解Ec：根据式(10)，由于可以通过迭代原始的概率转移矩阵P得到，因此可以通过固定的P来最小化分类器W，并使用迭代优化算法来解决这个问题。

对Ec进行求导，梯度可计算为

根据这个求导式，使用L-BFGS优化算法[10]来最小化式。

综上所述，真实的概率转移矩阵构建算法框架如下：

步骤2 根据式(8)更新E；

步骤5 使用L-BFGS优化算法更新Ec;

得到真实的概率转移矩阵后，即可按照表标准马尔科夫谱聚类的算法流程，得到极化SAR图像的最终分类结果，如图2所示。

图2 本文算法框架图Fig. 2 Algorithm frame diagram

4 实验结果与分析

4.1 实验数据与环境说明

由于本文算法是在马尔科夫谱聚类算法基础上的改进模型，对目标函数的不足进行优化，并引入了判别信息。因此在实验中选取3个对比算法如下：

(1) 联合正则谱聚类(Co-Regularized spectral clustering， Co-Reg)[11]：谱聚类的共正则化方法，Kumar于2011年提出；

(2) 混合马尔科夫链(Mixture of Markov Chains， MMC)[12]：Zhou和Burges于 2007年提出的混合马尔科夫链方法，这是与本文所提基于马尔科夫链的判别谱聚类算法最相关的方法；

(3) SR-MO算法[13]：Haixia Bi提出的无监督判别聚类方法，利用监督Softmax 逻辑回归 (Softmax logistic Regression， SR)模型和大量特征进行无监督分类并在分类过程中采用了马尔可夫随机场优化算法(Markov random field Optimization， MO)，且考虑了空间关系。

本节在荷兰Flevoland地区小农田和大农田、德国Oberpfaffenhofen地区和西安地区这4幅真实的极化SAR数据上进行实验，以上4种数据分别来自不同的成像系统，包含不同的波段与数据类型，通过以上数据证明本文算法的有效性。仿真实验均是在主频2.50 GHz的Intel(R) Core(TM) i5-7300HQ CPU， 8 G的内存环境和Windows10操作系统中编程实现的。实验结果均为MATLAB R2017a的软件环境中进行10次实验的平均值。

本文实验主要用总体分类精度OA、平均分类精度AA以及Kappa系数作为分类的评价指标。

4.2 荷兰Flevoland地区农田小图实验结果

本实验数据为NASA在1989年使用AIRSAR系统获得的荷兰Flevoland地区L波段的农田小图数据，该组图像的大小为300×270。图像主要包含裸土、马铃薯、甜菜、大麦、豌豆、小麦6种农作物。

Co-Reg， MMC以及SR-MO 3种不同对比算法和本文算法对Flevoland地区小农田图的总体分类精度OA、平均分类精度AA以及Kappa系数如表1所示；分类结果图如图3所示。

在图3中，图3(a)是荷兰Flevoland地区农田小图的Pauli分解伪彩图，图3(b)是地物类标图，图3(c)-图3(e)分别是Co-Reg， MMC以及SR-MO算法的分类结果图，图3(f)是本文算法的分类结果图。

从总体分类精度和平均分类精度来看，本文方法均为最高且总体分类精度达92.43%，分别比Co-Reg，MMC和SR-MO算法高出8.43%， 5.35%和1.13%。虽然MMC在马铃薯这一类的分类效果最好，对豌豆、小麦等大多数地物类别也更加准确，但这也导致了将部分甜菜等地物错分为马铃薯，影响分类精度。这也说明了与单纯马尔科夫谱聚类算法相比，本文提出的引入判别信息的马尔科夫谱聚类算法更有优势。并且在分类结果图中，可以看出本文算法对不同的地物分类比较均衡，边缘更清晰，孤立像素更少，显示出算法的平滑效果，Kappa系数也是最高的，验证了本文方法的有效性。

4.3 德国Oberpfaffenhofen地区实验结果

本实验数据为德国国家宇航中心DLR使用ESAR系统拍摄的德国Oberpfaffenhofen地区L波段极化SAR数据的局部，400×450，分辨率为3×2.2 m。该区域主要分为农田、居民区、林地、道路和其它地物5类。

Co-Reg， MMC和SR-MO 3种不同对比算法和本文算法对德国Oberpfaffenhofen地区的总体分类精度OA、平均分类精度AA以及Kappa系数如表2所示，分类的结果图如图4 所示。

在图4中，图4(a)是德国Oberpfaffenhofen地区的Pauli分解伪彩图，图4(b)是地物类标图，图4(c)-图4(e)分别是Co-Reg， MMC以及SR-MO算法的分类结果图，图4(f)是本文算法的分类结果图。

从图4中能够看出，图4(c)的杂点最多，区域一致性最差。图4(d)整体分类效果较好，但和本文算法相比，对边缘像素点的分类效果不太理想。图4(e)和图4(f)相比，图4(e)将林地和开放型区域错分的像素点较多。图4(d)错分的杂点较多，将大部分林地区域错分为开放型区域。对比算法的实验结果图中，图4(e)分类效果最好。

由实验结果表2可以得到本文算法的总体分类精度为79.74%，分别比Co-Reg， MMC和SR-MO方法高出6.11%， 5.03%和1.52%。Kappa系数和平均分类正确率也优于对比方法。这说明了本文算法对德国Oberpfaffenhofen地区的分类效果较好，地物之间的分界较为清晰，能够识别出农田和道路，以及大部分的林地区域。同时，可以看到本文算法在处理除过道路之外的区域时，分类效果很好，且更加稳定，尤其在图中间的农场区域，分类更为连贯平整，视觉效果好，杂点较少。Co-Reg方法对于道路的误分现象较为严重，大部分道路没有被识别。SR-MO方法能够有效识别大部分的道路、郊区、林地，以及农田，却将大部分的农田误分为郊区，分类效果也不够理想，这是由于仅仅基于判别信息进行分类，没有反映极化数据的统计特征。不过这4类算法对中间道路的分类效果都不是很好，还有很大的改进完善空间，但相对来说本文算法的道路边界更为清晰平滑，视觉效果更好。

表1 4种算法对Flevoland小农田图的分类结果Tab. 1 Classification results of four algorithms for Flevoland small farmland map

图3 荷兰Flevoland地区农田小图的伪彩图、类标图以及不同算法的分类结果图Fig. 3 Pseudo-color map， class diagram and classification results of different algorithms for farmland maps in the Flevoland region of the Netherlands

表2 4种算法对德国Oberpfaffenhofen地区的分类结果Tab. 2 Classification results of four algorithms for the Oberpfaffenhofen region of Germany

4.4 西安地区实验结果

本实验数据为由加拿大太空署RADARSAT-2系统获取的西安地区极化SAR图像，该图像大小为512×512，主要有河流、城区、植被3种地物分类。

Co-Reg， MMC以及SR-MO 3种不同对比算法和本文算法对西安地区的总体分类精度OA、平均分类精度AA以及Kappa系数如表3所示；分类的结果图如图5所示。

在图5中，图5(a)是西安地区的Pauli分解伪彩图，图5(b)是地物类标图，图5(c)-图5(e)分别是Co-Reg， MMC以及SR-MO算法的分类结果图，图5(f)是本文算法的分类结果图。

由表3可以看出本文算法的总体分类精度为85.03%，分别比Co-Reg， MMC和SR-MO高出11.03%， 8.33%和2.76%，尤其在城区和植被的分类中，本文算法均表现出了良好的性能。从图5的视觉效果上分析，Co-Reg和MMC算法的分类效果较差，通常情况下某一区域内的样本点应属于同一类地物，但这两幅结果图的整个图像充满斑点点，区域内杂点过多。相比之下，SR-MO和本文算法的两幅图视觉效果很好，杂点较少，河流区域分类较好。相比与SR-MO算法，本文算法的城区部分分类较好，能较好地保持区域一致性。

图4 德国Oberpfaffenhofen地区数据的伪彩图、类标图以及不同算法的分类结果图Fig. 4 Pseudo-color map， class diagram and data classification results of different algorithms in the Oberpfaffenhofen region of Germany

表3 4种算法对西安地区的分类结果Tab. 3 Classification results of four algorithms for Xi'an area

4.5 荷兰 Flevoland 地区大农田地区实验结果

本节实验美国NASA/JPL AIRSAR系统于1989获得的Flevoland地区四视L波段的大图数据，图像大小为750×1024，分辨率为12.1×6.7 m。包含15类地物：蚕豆、油菜籽、裸地、土豆、甜菜、小麦2、豌豆、小麦3、苜蓿、大麦、小麦、草地、森林、水域和建筑物。设置Ns=15，K=9， 4种不同算法的总体分类精度OA、平均分类精度AA以及Kappa系数如表4所示，不同算法的结果图如图6所示。

从图6中能够看出，图6(c)的杂点最多，区域一致性最差，油菜籽、甜菜和小麦等区域被大量误分为水域，区域之间没有明显区分，分类效果较差。图6(e)整体分类效果较好，但和本算法相比，对边缘像素点的分类效果不太理想。和图6(f)相比，图6(d)与图6(e)区域错分的像素点较多，小麦、草地和建筑物等区域均有较多杂点。对比算法的实验结果图中，图6(e)分类效果最好。

与对比算法相比，本文算法对Flevoland地区大农田的农作物分类的正确率都很高，稳定性很好，没有偏差，尤其在油菜籽、土豆、苜蓿、森林这几类上，分类正确率明显优于其它3种算法。但是本章算法在处理草地和小麦区域时，最终结果并没有达到理想状态，还有进一步提升的空间。但是整体来说，本文算法对比于其他对比算法的分类效果最好，区域一致性较好，边界更清晰，错分点更少。

图5 西安地区数据的伪彩图、类标图以及不同算法的分类结果图Fig. 5 Pseudo-color map， class diagram and data classification results of different algorithms in Xi'an area

表4 4种算法对荷兰 Flevoland 地区大农田图的分类结果Tab. 4 Classification results of four algorithms for large farmland maps in the Flevoland region of the Netherlands

4.6 参数敏感性分析

在本文方法中有两个权衡参数λ，β和正则项参数ξ。通常的做法是在无监督聚类中根据经验设置参数。下面本节对荷兰Flevoland小农田、德国Oberpfaffenhofen和西安地区数据集进行实验，观察不同值和对总体分类精度的影响，如图7-图10所示。可以观察到：

综上所述，本文算法在合适的区间内对其参数相对不敏感，区间内参数的变化对分类总精度影响较小，且参数的可调节的范围较大。因此，本文所提方法有较好的参数稳定性。这使得本文算法易于使用，无需进行太多的权衡参数调优。

5 结束语

本文提出一种基于马尔科夫的低秩稀疏的判别谱聚类方法。首先构造一个概率转移矩阵用于恢复一个真实的低秩转移概率矩阵作为标准马尔科夫聚类方法的关键输入。然后在目标函数中引入判别信息，达到对数据信息的充分利用。本文采用基于增广拉格朗日乘子法的优化方法来求解低秩和概率单纯形约束下的目标函数。通过应用4种典型的实验数据，证明了本文算法在分类精度、参数敏感性等方面具有优势，最终的分类效果也更好。

图6 荷兰 Flevoland 地区大农田数据的伪彩图、类标图以及不同算法的分类结果图Fig. 6 Pseudo-color map， class diagram and classification results of different algorithms for large farmland data in the Flevoland region of the Netherlands

图7 荷兰小农田中不同和下的分类结果图Fig. 7 Classification results of different and below in small Dutch farmland

图8 德国地区中不同和下的分类结果Fig. 8 Classification results for different and below in the German region

图9 西安地区中不同和下的分类结果图Fig. 9 Classification results of different and subordinates in Xi'an area

图10 不同正则项参数的分类结果图Fig. 10 Classification results of different regular item parameter