谱聚类算法及其在SAR图像分割中的应用研究

摘 要：谱聚类算法作为一种高效的智能聚类算法被广泛地研究与应用，它与传统的聚类算法相比，具有明显的优势。文章首先对谱聚类理论进行了概述，介绍了图划分准则、谱松弛及谱聚类算法，后介绍算法在SAR图像分割中的应用，并对分割时出现的一些问题加以分析和讨论，对研究谱聚类算法及其对SAR图像的分割具有一定得理论参考。

关键词：谱聚类；SAR图像；图像分割

中图分类号：TP391.41 文献标识码：A 文章编号：1006-8937（2015）29-0046-02

1 谱聚类算法

谱聚类算法基于谱图划分理论，它将聚类问题看成是图的划分问题，使用数据样本的相似度矩阵的特征向量进行聚类。该算法对凸型的球形空间或非凸的任意空间的聚类表现不敏感，易于得到全局最优解，较传统聚类算法（K-means和最大期望值EM算法）优势明显，是当前流行的一种高性能聚类算法。利用谱聚类算法实现图像的分割是人们较感兴趣的一个研究方向。

图的最优划分其实是一个NP难问题，有效的解决办法就是对原问题进行实数域松弛，进而可將图的划分转换为求解矩阵的特征值和特征向量问题。对于合成孔径雷达图像（简称SAR图像）的分割来讲，谱聚类算法除了要考虑图像的光谱特性、空间特征等因素，还要考虑算法的计算速度及内存消。

2 谱聚类理论及算法实现

2.1 谱聚类理论算法

得到图G的一个最优二分图即是对公式（1）最小化，但这种做法倾向于获得不均衡、歪斜的划分。基于2-way划分的规范割判据（Ncut）可以克服这种现象，其目标函数为：

将x松弛至连续实数域 ，求解minNcut（A，B）的问题可以转化为下式（4）的优化问题：

根据Rayleigh商原理的知识，我们可将对（4）式的优化问题转化为式（5）中特征值和特征向量的求解问题。

2.2 谱聚类的图像分割方法实现步骤

虽然第二最小特征值？姿2所对应的特征向量x2（也称Fiedler向量）包含了丰富的图划分信息。但仅仅根据x2对数据进行迭代性聚类，不仅计算效率低且聚类结果不稳定。研究发现，同时使用多个特征向量可以避免由于信息损失造成的不稳定性，并且直接进行k路分割可以得到更好的聚类效果。一种基于多路划分谱聚类的图像分割方法实现步骤。

2.2.1 预处理

2.2.2 谱映射

2.2.3 聚 类

将Y的每一行看成是k维空间Rk中的一个样本，通过K-Means算法将这些样本聚成k类，当且仅当Y的第i行被分配为j类时才将图像的像素点vi分配为j类。

3 关于SAR图像分割的两大问题

SAR图像不同于医学图像、纹理图像和彩色图像的分割，由于其图像本身的特点，如成像机理、对比度、一致性、信息熵、灰度共生矩阵、小波能量等特征，直接采用传统的分割方法往往不能够得不出较好的分割结果。针对SAR图像的分割问题值得讨论。

3.1 构造相似度问题

对于SAR图像的分割缺乏标准统一的相似度构造函数，目前针对这方面的研究，国内外许多研究、科研人员进行的大量工作。如：提取一窗口大小中像素点的小波能力、灰度共生矩阵等特征，并计算窗口内像素点的平均特征构造相似度矩阵；另一种方法是，首先对采用分水岭算法得出的特征块集合X聚成k 个子集合进行预处理，再使用高斯核函数构造相似度矩阵。3.2 时空复杂度问题

对于一个包含n个像素点的图像（如一副256×256的图像，n=28×28）来讲，算法的计算复杂度数量级为n3，往往致使计算机内存溢出和处理器计算时间过长。对内存的高消耗和处理器的计算速度优化问题显得尤为重要。典型的一种减少计算复杂度的方法是Fowlkes等人提出的Nystrom算法，该方法使用优化标准割准则对目标函数进行优化、逼近，并对矩阵特征矩阵进行稀疏，提取出典型特征方式来减少计算量。另一种是基于形态学分水岭的技术，并结合谱聚并结合谱聚类算法的聚类优势得出的一种多阶段聚类算法。该算法也能够大大降低构造相似性矩阵时的计算量。

4 结 语

本文介绍了谱聚类的理论基础及算法实现原理，并给出了基于谱聚类的SAR图像分割方法。最后，对SAR图像的分割问题加以分析，并对SAR图像的分割研究方向加以引导，对基于谱聚类算法的合成孔径雷达图像和航拍图像的目标定位和识别研究具有一定的理论参考和指导意义。

参考文献：

[1] Luxburg U V.A tutorial on spectral clustering [J].Statistics and Computing，2007，（4）.

[2] 葛洪伟，李志伟，杨金龙.基于局部密度估计和近邻关系关系传播的 谱聚类[J].模式识别与人工智能，2014，（9）.

[3] 李志伟，葛洪伟，杨金龙.基于邻里关系传播与模式合并的谱聚类[J].计算机工程，2014，（6）.

[4] 李志伟.基于近邻传播和密度信息的谱聚类算法研究与应用[D].无 锡：江南大学物联网工程学院，2014.

[5] Shi Jianbo，Malik J.Normalized cuts and image segmentation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，（8）.

[6] 贾建华，焦李成.空间一致性约束谱聚类算法用于图像分割[J].红外与毫米波学报，2010，（1）.

[7] Fowlkes C，Belongie S，Chung F，et al.Spectral grouping using the Nystrom method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，（2）.