, 黄友红2, 胡庆荣1, 李军1, 王冠勇11. 中国航天二院二十三所, 北京 100854;
2. 中国人民解放军驻航天二院二十三所军代表室, 北京 100854
2016年01月11日 收稿; 2016年04月05日 收修改稿
基金项目: 国家自然科学基金（61271417）和高分专项青年创新基金（GFZX04060103）资助
通信作者: 邢涛 E-mail: 1mingzongyue@163.com
摘要: 针对SAR图像的分割问题，对K均值聚类算法进行研究.分析动态K均值聚类算法，用聚类样本数的正比函数对该聚类适应度函数进行平均，改进适应度函数的计算.毫米波SAR图像分割实验结果表明，对于城区建筑及路、桥场景的分割，改进后的动态K均值聚类算法和自适应动态K均值聚类算法的分割质量与改进前相同，但是分割时间有一定的减少，改进适应度函数后分割效率得到了提高.
关键词: 合成孔径雷达图像分割聚类K均值
SAR image segmentation based on dynamical K-means clustering algorithm
XING Tao1
, HUANG Youhong2, HU Qingrong1, LI Jun1, WANG Guanyong1 1. No. 23 Institute of the Second Academy of China Aerospace, Beijing 100854, China;
2. The PLA Office in No. 23 Institute of the Second Academy of China Aerospace, Beijing 100854, China
Abstract: We present our study on SAR image segmentation based on K-means clustering. We analyze dynamical K-means clustering algorithms and improve the adaptation degree function computation method which divides the raw adaptation degree function by a direct ratio function of the sample number in clustering. Millimeter SAR image segmentation results verify that, for urban area, road, and bridge scenes segmentation, dynamical K-means clustering algorithm and adaptive dynamical K-means clustering algorithm with the improved adaptation degree function computation method have the same segmentation quality while the segmentation efficiency is higher than before.
Key words: synthetic aperture radar(SAR)image segmentationclusteringK-means
合成孔径雷达(synthetic aperture radar，SAR)经过多年的发展[1-3]，成像方面很多问题已经得到解决[4-5].目前的热点和难点主要集中在新体制雷达的信号处理[6-8]或SAR图像的解译与应用研究上[9-10].
图像分割能够从图像中提取感兴趣的信息，是从图像处理到图像分析的关键步骤.图像分割的方法有多种，主要有基于阈值、边缘、区域、特定理论的分割方法等[11-13].
聚类作为一种无监督的分类方法，在众多领域应用广泛[13]，例如生物学上的基因分类和动植物分类，图像处理中的分割、增强、压缩、检索等.K均值聚类算法[14-17]是一种典型的基于划分的聚类算法，该算法思想简单、计算速度快，已经成为最常用的聚类算法之一.
本文以毫米波高分辨SAR图像为研究对象，采用K均值聚类方法对SAR图像进行分割，并对文献中的动态K均值聚类算法进行分析与改进，具体改进了每个聚类适应度函数的计算方式，即用聚类中样本数的正比函数对原始的适应度进行平均.毫米波SAR图像城市区域、路和桥梁的分割结果验证了本文改进算法相对已有算法在分割效率上的提升.
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=\sum\limits_{j=1}^{K}{\sum\limits_{i,i\in {{c}_{j}}}{{{d}_{ij}}\left( {{x}_{i}},{{c}_{j}} \right).}}$ | (1) |
| $J=\sum\limits_{j=1}^{K}{{{J}_{i}}}=\sum\limits_{j=1}^{K}{\left[ \sum\limits_{i,i\in {{c}_{j}}}{\left\| x_{i}^{\left( j \right)} \right.-{{\left. {{c}_{j}} \right\|}^{2}}} \right].}$ | (2) |
| ${{c}_{j}}=\frac{1}{{{n}_{j}}}\sum\limits_{i=1}^{{{n}_{j}}}{x_{i}^{\left( j \right)}}.$ | (3) |
1)初始化，输入样本集X及聚类数K，并在X中随机选取K个样本作为初始聚类中心；
2)初始聚类；
3)按式(3)计算新的聚类中心；
4)重新聚类；
5)反复进行3)、4)直至迭代结束，得到聚类结果.
称上述K均值聚类算法为基本K均值聚类算法，记为KM_Basic.KM_Basic算法理论严密，计算简单.但是聚类结果对初始聚类中心有很强的依赖性，容易收敛于局部极值点.初始聚类中心选取不当会对聚类结果产生很大的负面影响.
文献[13]提出全局K均值聚类算法，文献[14]对全局K均值聚类算法进行研究.全局K均值聚类算法通过迭代的方式来产生初始聚类中心，处理效率不高.文献[12]提出动态K均值聚类算法，动态K均值聚类算法能减小对聚类中心初值的依赖，改善性能，并且运算效率也较高.动态K均值聚类算法的适应度函数为聚类中心与属于该中心区域内的所有像素之间的欧式距离之和：
| $f\left( {{c}_{j}} \right)=\sum\limits_{i}{\left\| {{x}_{i}} \right.-}{{\left. {{c}_{j}} \right\|}^{2}}.$ | (4) |
1)给定初始聚类中心cj和权值α0(α0为常数)，αa=αb=α0；
2)初始聚类；
3)根据式(4)计算每个聚类中心的适应度函数f(cj)；
4)设f(*)中，最大的f(*)对应的聚类中心为cl，最小的f(*)对应的聚类中心为cs.如果f(cs)<αa f(cl)，重新分配cl聚类中的数据样本，将其中xi<cl的数据样本分配给聚类cs；
5)根据式(3)计算新的聚类中心；
6)更新阈值αa=αa－αa/K，重复3)至5)，直至f(cs)≥αa f(cl)；
7)按最小距离原则聚类一次；
8)根据式(3)计算新的聚类中心；
9)更新权值αa=α0和αb=αb－αb/K，重复3)至8)，直至f(cs)≥αb f(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最小为准则迭代聚类，文献[14]的KM_MKM及文献[12]的KM_AMKM均把各Jj均衡作为准则进行迭代聚类.不考虑运算效率，仅针对分割质量指标F, F′, Q而言，在文献[12]中，KM_MKM、KM_AMKM均优于KM_Basic，表明“Jj均衡准则”大部分时候还是优于“J最小准则”的.本节仍然遵循“Jj均衡准则”的思路，但是对该准则进行相应的改进.
根据式(4)，Jj为
| ${{J}_{j}}=\sum\limits_{i}{\left\| {{x}_{i}} \right.-}{{\left. {{c}_{j}} \right\|}^{2}}.$ | (5) |
| ${{J}_{j}}=\frac{\sum\limits_{i}{\left\| {{x}_{i}} \right.-}{{\left. {{c}_{j}} \right\|}^{2}}}{g\left( {{c}_{j}} \right)},$ | (6) |
3 毫米波SAR图像分割实验3.1 图像分割结果评价指标除了目视判读，文献[12, 15]给出如下的评价指标：
| $F\left( I \right)=\sqrt{R}\sum\limits_{i=1}^{R}{\frac{e_{i}^{2}}{\sqrt{{{A}_{i}}}},}$ | (7) |
文献[16]对式(7)进行修正，给出如下评价指标：
| $\begin{align} & F'\left( I \right)=\frac{1}{10\ 000\left( M\times N \right)} \\ & \sqrt{\sum\limits_{A=1}^{\text{Max}}{|R\left( A \right){{|}^{1+1/A}}}}\times \sum\limits_{i=1}^{R}{\frac{e_{i}^{2}}{\sqrt{{{A}_{i}}}}}, \\ \end{align}$ | (8) |
在对过分割和分割不足充分考虑的基础上，文献[17]提出如下的分割质量评价指标：
| $\begin{align} & Q\left( I \right)=\frac{1}{10\ 000\left( M\times N \right)}\sqrt{R}\times \\ & {{\sum\limits_{i=1}^{R}{\left[ \frac{e_{i}^{2}}{1+\log {{A}_{i}}}+\frac{R\left( {{A}_{i}} \right)}{{{A}_{i}}} \right]}}^{2}}. \\ \end{align}$ | (9) |
分割采用Intel(R) Core(TM) i3 CPU 550 @ 3.20 GHz，3.19 GHz，2.99 GB的内存，Microsoft Windows XP Professional Service Pack3系统，软件采用MATLAB 7.5.0(R2007b)，分割效率用分割所用时间来衡量.
3.2 毫米波SAR图像分割分割图像为Ka波段SAR数据，分辨率0.3 m×0.3 m.图 1(a)为建筑物场景，图 1(b)为城区场景，图 1(c)为高架桥场景，图 1(d)为平地道路场景，图 1(a)和图 1(d)大小为600像素×600像素，图 1(b)和图 1(c)大小为2 000像素×2 000像素.表 1为4个场景对应的分割指标.
Fig. 1
 | Download: JPG larger image |
图 1 选取的分割场景 Fig. 1 Selected segmental scenes | |
Table 1
 表 1 中场景分割指标Table 1 Segmentation index of the scenes shown in Fig. 1
| 表 1 中场景分割指标Table 1 Segmentation index of the scenes shown in Fig. 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
表 1中，改进适应度函数计算方法后，4种场景下KM_MKM、KM_AMKM分割所用的时间均比改进前有一定的减少.改进前后算法分割质量指标没有变化，这是由于改进前后算法基于的准则没有变化，都是“适应度函数均衡”准则，随着迭代的进行，最终聚类的结果是一样的，指标也一样.
4 结论本文对几种K均值聚类算法进行分析，改进了动态K均值聚类算法中每个聚类适应度函数的计算方法，用样本数的正比函数对适应度函数进行一定的削弱与平均.毫米波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.DOI:10.1109/TIM.2014.2298618 |
| [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.DOI:10.1109/TGRS.2013.2258402 |
| [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.DOI:10.1109/TGRS.2013.2291573 |
| [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.DOI:10.1109/LGRS.2012.2195634 |
| [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] | 折小强, 仇晓兰, 韩冰, 等. 一种基于变换域的滑动聚束SAR调频率估计方法[J].雷达学报, 2014, 3(4):419–427. |
| [8] | 邢涛, 李军, 王冠勇, 等. 基于非均匀快速傅里叶变换的SAR方位向运动补偿算法[J].电子与信息学报, 2014, 36(5):1023–1029. |
| [9] | 赵冠雄, 沈汀. 高分辨率SAR图像桥梁自动提取算法[J].计算机工程与设计, 2014, 35(8):2793–2797. |
| [10] | 陈祥, 孙俊, 尹奎英, 等. 基于Otsu与海域统计特性的SAR图像海陆分割算法[J].数据采集与处理, 2014, 29(4):603–608. |
| [11] | 张新野. 基于聚类分析的图像分割方法研究[D].大连:大连海事大学,2012.http://cdmd.cnki.com.cn/article/cdmd-10151-1013109717.htm |
| [12] | 梁烨炜. K-均值聚类算法的改进及其应用[D].长沙:湖南大学,2012.http://cdmd.cnki.com.cn/article/cdmd-10532-1012481938.htm |
| [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.http://cdmd.cnki.com.cn/article/cdmd-10701-1013295615.htm |
| [15] | Likas, Vlassis M, Verbeek J. The global k-means clustering algorithm[J].Pattern Recognition, 2003, 36(2):451–461.DOI:10.1016/S0031-3203(02)00060-2 |
| [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.DOI:10.1016/S0167-8655(98)00052-X |
