基于聚类的合成孔径雷达图像分割算法研究

邢 涛 赵海宾 胡庆荣 李 军 王冠勇

(1.中国航天二院二十三所北京100854;2.中国人民解放军驻航天二院二十三所军代表室北京100854)

总体工程

基于聚类的合成孔径雷达图像分割算法研究

邢 涛1赵海宾2胡庆荣1李 军1王冠勇1

(1.中国航天二院二十三所北京100854;2.中国人民解放军驻航天二院二十三所军代表室北京100854)

针对SAR图像的分割问题，对K均值聚类算法进行了研究，分析了自适应动态K均值聚类算法，改进了最大适应度函数聚类的样本分离准则。毫米波SAR图像分割表明，对于城区建筑及路、桥场景的分割，改进算法比基本的K均值聚类算法、动态K均值聚类算法及自适应动态K均值聚类算法性能要好，指标更优。在运算效率上，改进算法与自适应动态K均值聚类算法效率相当。

合成孔径雷达;图像分割;聚类;K均值

0 引 言

合成孔径雷达(synthetic aperture radar，SAR)经过多年的发展［1－3］，成像方面很多问题已经得到解决［4，5］。目前的热点和难点主要集中在新体制雷达的信号处理［6－8］或SAR图像的解译与应用研究上［9－10］。

图像分割能够从图像中提取感兴趣的信息，图像分割是从图像处理到图像分析的关键步骤。图像分割的方法有多种，主要有基于阈值、基于边缘、基于区域、基于特定理论的图像分割方法等［11－13］。

聚类作为一种无监督的分类方法，在众多领域应用广泛［13］，例如生物学上的基因分类和动植物分类，图像处理中的图像分割、图像增强、图像压缩、图像检索等。K均值聚类算法［14－17］是一种典型的基于划分的聚类算法，该算法思想简单，计算速度快，已经成为最常用的聚类算法之一。

本文以毫米波高分辨SAR图像为研究对象，采用K均值聚类方法对SAR图像进行分割，并对文献中的自适应动态K均值聚类算法进行了分析与改进。城市区域、路和桥梁的分割结果验证了本文改进算法相对已有算法在分割质量上的提升。

1 当前的K均值聚类算法

K均值聚类算法的基本思路是在最小化误差函数的基础上将数据划分成K类。算法的处理过程［11，12］为:先指定聚类数目K及K个初始聚类中心，然后根据一定的准则将每个数据分配给最近的聚类中心。

将样本空间X={x1，x2，…，xi，…，xn}的样本分成K类，聚类中心为C={c1，c2，…，cj，…，cK}，用dij(xi，cj)表示样本xi与其对应的中心cj间的距离，样本空间内所有数据点与所属聚类质心距离的总和用目标函数J来表示，为:

目标函数J越小，表明聚类越紧凑，聚类越优。当选择欧式距离作为样本xi与其对应的中心cj间的距离时为属于聚类j的数据样本，nj为聚类j的样本个数，式为:

为使目标函数最小，各聚类中心为:

K均值聚类算法流程如下:

(1)初始化，输入样本集及聚类数K，并在中随机选取K个样本作为初始聚类中心;

(2)初始聚类;

(3)按式计算新的聚类中心;

(4)重新聚类;

(5)反复进行(3)、(4)直至迭代结束，得到聚类结果。

称上述K均值聚类算法为基本K均值聚类算法，记为KM_Basic。KM_Basic算法理论严密，计算简单。但是聚类结果对初始聚类中心有很强的依赖性，容易收敛于局部极值点。初始聚类中心选取不当会对聚类结果产生很大的负面影响。

文献［13］提出了全局K均值聚类算法，文献［14］对全局K均值聚类算法进行了研究。全局K均值聚类算法通过迭代的方式来产生初始聚类中心。全局K均值聚类算法处理效率不高。文献［12］提出了动态K均值聚类算法，动态K均值聚类算法能减小对聚类中心初值的依赖，改善性能，并且运算效率也较高。动态K均值聚类算法的适应度函数为聚类中心与属于该中心区域内的所有像素之间的欧式距离之和:

若f(cj)越小，则中心的适应度越小，聚类越紧凑。动态K均值算法通过调整聚类来使各中心的适应度函数均衡，当适应度均衡时，认为聚类最优。动态K均值聚类算法流程如下:

(1)给定初始聚类中心cj和权值α0(α0为常数)，αa=αb=α0;

(2)初始聚类;

(3)根据式计算每个聚类中心的适应度函数f (cj);

(4)设f(*)中，最大的f(*)对应的聚类中心为ci，最小的f(*)对应的聚类中心为cs。如果f (cs＜αaf(cl)，重新分配 cl聚类中的数据样本，将其中xi＜cl的数据样本分配给聚类cs;

(5)根据式计算新的聚类中心;

(6)更新阈值αa=αa－αa/K，重复(3)～(5)，直至f(cs)≥αaf(cl);

(7)按最小距离原则聚类一次;

(8)根据式计算新的聚类中心;

(9)更新权值αa=α0和 αb=αb－αb/K，重复(3)～(8)，直至f(cs)≥αbf(cl)。

记上述动态K均值聚类算法为KM_MKM。KM_MKM通过调整具有最大适应度函数值和最小适应度函数值的聚类区域的样本，最终达到各区域适应度函数的均衡。KM_MKM能减少对初始聚类中心的依赖，改善并减少陷入局部极值引起的死区中心和中心冗余问题，但该算法对孤立数据和噪声敏感的问题依然存在［12］。

KM_MKM将最大适应度函数聚类里面的部分样本强制分配给最小适应度函数聚类区域，如果这些样本是噪声，那么具有最小适应度的聚类就将代表噪声数据，这将导致错误的分类［12］。基于此，文献［12］提出了一种自适应动态K均值聚类算法，改变了KM_MKM算法强制分配样本给具有最小适应度聚类的做法，引入最小距离原则来分配这些样本，即将待分配样本配给与这些样本最近距离的聚类区域，以此来减少噪声数据的错误分类。自适应动态K均值算法记为KM_AMKM，KM_AMKM与KM_MKM流程类似，只是在(4)中将其中xi＜cl的数据样本按照最小距离原则分配给最近的聚类中心，而非统一分配给聚类cs。

2 当前算法分析与改进

KM_Basic给定聚类中心，然后以J最小为准则迭代聚类;KM_MKM以各Ji均衡为准则迭代聚类;KM_AMKM改进了KM_MKM中样本的分配方式，在KM_MKM中样本直接分配给最小适应度的聚类，在KM_AMKM中样本根据最小距离原则分配给其他聚类。根据文献［12］的研究结果，在以文献中的灰度图像为研究对象时，从KM_Basic、KM_MKM到KM_AMKM，分割结果依次更好。

本文沿用文献［12］的思路，即认为“Ji均衡准则”优于“J最小准则”，对KM_AMKM进行分析与改进。在样本分配方式上，KM_AMKM对KM_ MKM进行了改进，但是在样本的选取上，KM_ AMKM并未做到尽善尽美。

在KM_MKM、KM_AMKM中，将cl聚类中满足xi＜cl的数据样本剥离出cl聚类，重新进行分配。虽然从cl聚类中分离出一部分样本能减小f(cl)，使得f(cs)≥αaf(cl)、f(cs)≥αbf(cl)，但是满足xi＜cl的样本可能也有一部分处在cl的邻域内，这部分处在cl左邻域内的样本按照最小距离原则应当是分配给cl聚类的，一刀切式地把这部分样本分离出cl聚类并不科学，也许会影响最终的聚类效率及聚类质量。定义一个常数ε，修改KM_MKM、KM_AMKM处理流程的(4)为:

(4)设f(*)中，最大的f(*)对应的聚类中心为cl，最小的f(*)对应的聚类中心为cs。如果f(cs)＜αaf(cl)，重新分配cl聚类中的数据样本，将其中‖xi－cl‖≥ε的数据样本按照最小距离原则分配给其余聚类;

称上述改进后的聚类算法为修正的自适应动态K均值聚类算法，记为KM_RAMKM。

3 毫米波SAR图像分割实验

3.1 图像分割结果评价指标

除了目视判读，文献［12，15］给出了如下的评价指标:

其中，I表示原始图像，R表示分割的区域个数，Ai表示第i个区域的尺寸，ei表示原始图像与分割图像在第i个区域内每个对应像素的欧几里德距离之和。

文献［16］对式进行了修正，给出了如下评价指标:

其中，M×N表示图像I的尺寸，R(A)表示尺寸为A的区域数，Max为最大尺寸的区域，1+1/A为加大了的小区域权值。

在对过分割和分割不足充分考虑的基础上，文献［17］提出了如下的分割质量评价指标:

本文对分割结果的评价将采用以上三个指标，指标数据越小，分割效果越好。

分割采用Intel(R)Core(TM)i3 CPU 550@ 3.20GHz，3.19GHz，2.99GB的内存，Microsoft Windows XP Professional Service Pack3系统，软件采用MATLAB 7.5.0(R2007b)，分割效率用分割所用时间来衡量。

3.2 毫米波SAR图像分割

分割图像为Ka波段SAR数据，分辨率0.3m ×0.3m。图1(a)为建筑物场景，图1(b)为城区场景，图1(c)为高架桥场景，图1(d)为平地道路场景，图1(a)和图1(d)大小为600×600像素，图1 (b)和图1(c)大小为2000×2000像素。表1、表2、表3、表4分别为四个场景对应的分割时间及评价指标。

图1 选取分割的场景

图2 图1(a)分割后的结果

图3 图1(b)分割后的结果

图4 图1(c)分割后的结果

图5 图1(d)分割后的结果

表1 图1(a)场景分割时间及评价指标

表2 图1(b)场景分割时间及评价指标

表3 图1(c)场景分割时间及评价指标

表4 图1(d)场景分割时间及评价指标

表2中，KM_RAMKM的时间比KM_AMKM的时间略长，表1、表3、表4中，KM_RAMKM的时间比KM_AMKM的时间略短。在每一个场景中，KM _RAMKM与KM_AMKM分割所用时间基本相当，可以认为两种分割算法运算效率相同。

表1～表4对应的四种场景分割指标中，KM_ Basic评价指标最大，分割质量最差;KM_MKM和KM_AMKM评价指标小于KM_Basic评价指标; KM_RAMKM的评价指标最小，分割质量最好。图2～图5的分割结果中KM_RAMKM分割结果拥有最多的边缘和细节信息，轮廓特征最明显。

4 结 论

本文对几种K均值聚类算法进行了分析，改进了自适应动态K均值聚类算法中最大适应度函数聚类样本的选择准则。改进算法与自适应动态K均值聚类算法运算效率相当，分割质量有明显改善。毫米波SAR图像分割实验表明，在SAR图像城区建筑及路桥的分割应用中，改进算法比已有算法分割效果更好。

［1］Ghasr M T，Case J T，Zoughi R.Novel reflectometer for millimeter－wave 3－D holographic imaging［J］.IEEE Instrumentation and Measurement Society，2014，63(5): 1328 －1336.

［2］Fjortoft R，Gaudin J，Pourthie N，et al.KaRIn on SWOT:Characteristics of near－nadir Ka－band interferometric SAR imagery［J］.IEEE Transactions on Geoscience and Remote Sensing，2014，52(4):2172－2185.

［3］Anghel A，Vasile G，Cacoveanu R，et al.Short－range wideband FMCW radar for millimetric displacement measurements［J］.IEEE Transactions on Geoscience and Remote Sensing，2014，52(9):5633－5642.

［4］Zhang S X，Xing M D，Xia X G，et al.Focus improvement of high－squint SAR based on azimuth dependence of quadratic range cell migration correction［J］.IEEE Geoscience and Remote Sensing Letters，2013，10(1): 150－154.

［5］Fiss J，Curless B，Szeliski R.Refocusing plenoptic images using depth－adaptive splatting［C］∥Proc.of IEEE International Conference on Computational Photography，2014:1－9.

［6］Garren D A.Smear signature morphology of surface targets with arbitrary motion in spotlight synthetic aperture radar imagery［J］.IET Radar，Sonar＆Navigation，2014，8(5):435－448.

［7］Spencer M F，Thornton D E，Hyde M W，et al.Piston phase compensation of tiled apertures in the presence of turbulence and thermal blooming［C］∥Proc.of the IEEE Aerospace Conference，2014:1－20.

［8］邢涛，胡庆荣，李军等.基于非均匀FFT的超宽带合成孔径雷达高效成像算法［J］.系统工程与电子技术，2015，37(2):291－296.

［9］李小平，王卫卫，罗亮等.图像分割的改进稀疏子空间聚类方法［J］.系统工程与电子技术，2015，37 (10):2418－2424.

［10］陈祥，孙俊，尹奎英等.基于Otsu与海域统计特性的SAR图像海陆分割算法［J］.数据采集与处理，2014，29(4):603－608.

［11］张新野.基于聚类分析的图像分割方法研究［D］.大连:大连海事大学，2012.

［12］梁烨炜.K－均值聚类算法的改进及其应用［D］.长沙:湖南大学，2012.

［13］Sulaiman S N，Isa N A M.Adaptive fuzzy－K－means clustering algorithm for image segmentation［J］.IEEE Transactions on Consumer Electronics，2010，56(14): 2661－2668.

［14］赵丽.全局K－均值聚类算法研究与改进［D］.西安:西安电子科技大学，2013.

［15］Likas，Vlassis M，Verbeek J.The global k－means clustering algorithm［J］.Pattern Recognition，2003，36(2):451－461.

［16］Mashor M Y.Hybrid Training Algorithm for RBF Network［J］.International Journal of the Computer，2000，8(2):50－65.

［17］Borsotti M，Campadelli P，Schettini R.Quantitative evaluation of color image segmentation results［J］.Pattern Recognition Letters，1998，19(8):741－747.

Study on Synthetic Aperture Radar Image Segmentation Algorithm Based on Clustering

Xing Tao1，Zhao Haibin2，Hu Qingrong1，Li Jun1，Wang Guanyong1
(1.No.23 Research Institute of the Second Research Academy，CASIC，Beijing 100854; 2.Military Representative Office of PLA positioned in No.23 Research Institute of the Second Research Academy，CASIC，Beijing 100854)

Aiming at SAR image segmentation issue，K mean value clustering algorithm is studied;adaptive dynamic K mean value clustering algorithm is analyzed，and sample separation criteria of maximum fitness function clustering is improved.MMW SAR image segmentation shows that the improved algorithm has better performance and more excellent index than that of basic K mean value clustering algorithm，dynamic K mean value clustering algorithm and adaptive dynamic K mean value clustering algorithm for segmentation of urban area building，road，bridge scenes.The improved algorithm has correspondent efficiency with adaptive dynamic K mean value clustering algorithm in operation efficiency.

synthetic aperture radar;image segmentation;clustering;K mean value

TN957

A

1008-8652(2016)04-001-05

2016-10-23

国家自然科学基金(61271417)

邢 涛(1986－)，男，博士研究生。研究方向为雷达成像技术。