第5卷第6期 智能系统学报 Vol.5 No.6 2010年12月 CAAI Transactions on Intelligent Systems Dec.2010 doi:10.3969/i.issn.1673-4785.2010.06.014 多特征-谱聚类的SAR图像溢油分割 张伟伟，薄华，王晓峰 (上海海事大学信息工程学院，上海200315) 摘要：经典的K聚类算法，并不适合实现任意形状的聚类，而且有容易陷入局部最小值的不足.提出基于多个纹理 特征的谐聚类算法，该方法用灰度共生矩阵(GLCM)提取合成孔径雷达(SAR)图像的多个特征值，构建谱聚类的特 征矩阵，并依据规范切准则，用K均值聚类的方法对拉普拉斯矩阵的第二小的特征值对应的特征向量进行聚类，实 现基于SAR图像的溢油的分割.新方法与传统的K聚类方法比较，可以减少相干斑噪声对分割结果的影响，较好的 保持图像边缘.仿真结果显示，该算法对于相干斑噪声影响较大的图像具有较强的鲁棒性. 关键词：合成孔径雷达：灰度共生矩阵；谱聚类：溢油分割 中图分类号：TP751 文献标志码：A文章编号：16734785(2010)06055105 SAR oil spill image segmentation based on a multi-spectral clustering algorithm ZHANG Wei-wei,BO Hua,WANG Xiao-feng School of Information Engineering,Shanghai Maritime University,Shanghai 200135,China) Abstract:The classic K-mean clustering algorithm is not suitable for the circumstances of arbitrary shapes and is prone to use the local minimum.In order to fix these shortcomings,a spectral clustering algorithm based on multi- texture characteristics was proposed.The algorithm first used gray-level co-occurrence matrices (GLCM)to extract three features of the synthetic aperture radar (SAR)image and construct a characteristic matrix of spectral cluste- ring.Next using the N-cut(Normalized-cut)criterion,it clustered the eigenvector corresponding to the second small eigenvalue of the Laplacian matrix in order to carry out the SAR oil spill image segmentation.Compared with the classic K-mean algorithm,the proposed method reduces the influence of coherent scattering noise on the seg- mentation result and efficiently conserves the edge of the image.The simulation results also show that the new meth- od has a strong robustness for an image badly affected by the coherent scattering. Keywords:synthetic aperture radar;gray-level co-occurrence matrices;spectral clustering;spill oil segmentation 合成孔径雷达(SAR)具有全天候、全天时的观有大量的相干斑噪声，给后继的图像处理也造成很 测能力，因此在油污检测和舰船检测方面的应用受 大困难.快速、有效地实现对油污图像的分割，对后 到高度重视.海面溢油具有低雷达后向散射的特性， 面的油污检测等处理，有着重大的实际意义.在 在海平面上，浮油膜区域形成的Brag波抑制雷达 SAR图像的溢油检测方面，传统的算法是使用滤 的后向散射，浮油膜在海平面上显示为较暗的斑点 波、梯度和基于数学形态学等对溢油进行检测，当图 或条带，而周围波浪形成明暗混杂的背景数据.由于 像明暗对比明显时，这些算法是有效的，但是大多数 海洋波浪的干扰，造成雷达数据的高噪声和低对比 情况下，尤其是当溢油区域成像形状不规则或者和 度，严重影响了浮油膜特征的提取与解译.同时雨 海面区域的灰度对比不明显时，上述算法处理效果 区、低风速区、生物溢油和油脂冰等类油污现象也具 很不理想.根据SAR图像中含有丰富纹理信息[24] 有后向散射的特性，给图像分割带来很大困难， 的特点，文献[5]提出了利用SAR图像的纹理信息， SAR图像由于其自身的成像机理，获得的图像中含 结合支持向量机对海平面溢油进行分割的算法，得 到了满意的分割效果.文献[6]提出用分水岭谱聚 收稿日期：2009-11-12. 基金项目：上海市教育委员会科研创新资助项目(08Y2110). 类的方法对SAR图像目标进行Multiway分割，该方 通信作者：张伟伟.E-mail:zhangyuwei1983@126.com 法在一定程度上减少了运行时间，但是该算法并不
·552 智能系统学报 第5卷 能解决二分类图像数据量大的问题，而且此方法会 图的拉普拉斯矩阵的特征值和特征向量，只是有的 降低分割精度.文献[7]提出基于多参数核的谱聚 用规范的拉普拉斯矩阵，有的用的是未经规范化的 类算法，依据数据间的特征相似性和空间邻近相似 拉普拉斯矩阵. 性信息进行聚类，该算法需要依据实验设置2个不 表1各种谱方法的规范化形式 同的参数值分别调整特征相似性和空间相似性. Table 1 Normalized forms of various spectral clustering 谱聚类算法不局限于正态分布的聚类，具有坚 algorithms 实的理论基础.目前，许多新的算法相继提出并被成 算法 使用规范化状况 矩阵形式 功用于很多领域，如语音识别8)、视频分割和图像 MNcut 除规范化 L=D-W 分割]等.谱聚类是建立在谱图理论[]之上，利用 NJW 对称除规范化 L=D-12WD-12 数据点之间的相似性构造相似性矩阵，对得到的特 LSA 征向量进行聚类，从而实现图像的分割.但是当图像 没有规范化 L=W 很大时，数据点成指数增长，使得计算相似性矩阵、 尽管有实验表明使用规范的拉普拉斯矩阵可以 求解对应的特征值和特征向量的复杂度非常高，从 获得更好的聚类性能，但是当将规范切应用于SAR 而大大增加了对计算机内存和计算速度的要求。 溢油图像时，发现用规范化的拉普拉斯矩阵不仅增 本文提出基于多个纹理牲谱的聚类算法，用特 大了运算复杂度，而且增加了运行时间，分割效果也 征平均值度量数据点间的相似性，通一个核参数调 很不理想. 整，对获得的相似性矩阵，根据标准切准则选择 对于含有溢油的SAR图像，选用规范切，不仅 2小特征值对应的特征向量，最后用K-mean聚类的 简化了计算过程，节省了运算时间，后面的仿真也显 算法进行数据点间的分类， 示，可以得到了较好的分割效果 1.2GLCM特征提取处理 1算法简介 灰度共生矩阵(gray-levelco-occurrence matrix). 1.1谱聚类算法 由Haralick[]于1973年提出的，已被理论证明它在 谱聚类的思想来源于谱图划分.它将数据聚 纹理的特征提取上是个很好的方法.Haralick曾经 类问题看成是一个无向图的划分问题.由于图划分 提出14种由灰度共生矩阵计算出来的统计量.在 问题的组合本质，图的最优划分问题是一个NP难 SAR图像的溢油检测中，因为溢油在各种可能的方 问题.一个有效解决这个问题的方法是将问题放松 向上，在此认为方向因素并不重要.本文根据不同特 到实数值域，从而将原问题转换为求解矩阵的广义 点的溢油图像，手动选用GLCM的3个特征，组成特 特征值和特征向量的问题.在这里，将数据点看作是 征矩阵.常用的几个特征求取如下： 无向图G(V,E)的顶点V,边权重的集合E={W} 1)熵(ent). 表示基于某一相似性度量计算的2点间的相似性， ent =p(i,j)log p(ij). 其中W表示待聚类的数据点间的相似性矩阵，它包 当共生矩阵中所有元素有最大的随机性、空间 含了聚类所需的所有信息.然后定义一个划分准则， 共生矩阵中所有值几乎相等时，共生矩阵中元素分 最优化这一准则使同一类内的点具有较高的相似 散分布时，熵较大.它表示了图像中纹理的非均匀程 度，而不同类间的点则具有较低的相似度， 度或复杂程度， 目前用于二分情况的有3个性能较优的准则： 2)一致性(hom). 率切准则3]、规范切准则和最小最大切准则4.当 hom=p(i,j)/[1+(i-j)2]. 聚类间分的较开始时，这3个准则都能给出类似精 反映图像纹理的同质性，度量图像纹理局部变 确的结果；当聚类间分的不是很开时，规范切和最小 化的多少.其值大则说明图像纹理的不同区域间缺 最大切准则能给出较好的聚类结果；当聚类间严重 少变化，局部非常均匀 重叠时，最小最大切准则可以给出较紧凑和平衡的 3)对比度(con). 聚类.然而许多实验表明规范切准则相对于其他准 con =(i-j)'p(i,j). 则具有较好的性能 反映图像的清晰度和纹理沟纹深浅的程度.纹 在图划分准则的基础之上，出现了多种比较流 理沟纹越深，其对比度越大，视觉效果越清晰；反之， 行的谱聚类算法：l)有Shi和Mali提出的SDM算 对比度小，则沟纹浅、效果模糊.灰度差即对比度大 法；2)由Kannan、Vempala和Vetta提出的KVV派生 的像素对越多，这个值越大.灰度公生矩阵中远离对 算法；3)由Ng、Jordan和Weiss提出的NJW算法；4) 角线的元素值越大，con越大， 由Meila和Shi提出的MS算法.这些算法都是计算 仿真结果表明，当选用一个特征时，聚类效果很
第6期 张伟伟，等：多特征谱聚类的SAR图像溢油分割 ·553· 不理想，选用3个以上的特征时，不能提高算法的精 2)构造拉普拉斯矩阵L=W. 确度，但是却大大增加了计算量，过多地占用内存 3)计算L的特征值和特征向量，对特征值入：按 通常采用背景和目标的特征均值和方差，进行特征 降序排列，取其第2个特征值对应的特征向量u 量的筛选.asm、ent、hom3个特征值相比于另外的特 4)对特征向量进行归一化，最后对归一化的 征值有更小的方差.在本算法中，将图像归一化的灰 特征向量，用K-mean聚类的方法进行聚类. 度级为16，提取上述3个特征，求多个特征间的相 归一化的谱聚类具有更好的性能，因此先对特 似性，构造相似性矩阵 征向量归一化，然后再用多次迭代的方法用K均值 2本文算法 聚类进行分类.为了说明本文算法的有效性，后面将 本文算法与K聚类算法进行了比较. 由于小波变换在时、频域中有良好的局部化性 3 质和多分辨率分析的特点，可对图像进行多级分解， 实验结果与分析 每级分解都可以获得图像同一信息在不同方向、不 3.1与经典聚类的结果比较 同尺度和不同分辨率下的基本特征和细节，因此在 选用一副128×128的SAR溢油图像，其中颜 本文中用Har小波先对图像进行分解预处理，选取 色较黑的为油污.先对图像用Har小波做分解预处 它的低频部分图像，这部分图像几乎含有要分割图 理，选用其低频部分.针对图1的块状溢油，选用大 像的全部特征，对后继特征提取和分割不会造成太 小为9×9的滑窗，提取熵、一致性、能量3个特征， 大影响，低频图像大小为原始图像大小的1/4，诚少 σ=0.009.其中，图1(b)为本文提出算法的运行 了计算量，提高了运算效率. 结果.图1(c)为直接用灰度进行谱聚类的分割结 利用提取的特征，比直接利用图像的灰度的分 果，可以看出，由于相干斑噪声的影响，溢油部分的 割结果更不易受噪声影响.而利用多个特征比只用 连通性大受影响，有很多溢油的部分被误划分，无法 一个特征，又可以得到更好的分割结果.在此，利用 准确找出海面溢油.在不要求实时性的情况下，试验 前面提到的GLCM算法，提取图像的3个不同的特 证明多特征一谱聚类算法分类精度更高.分割结果 征.假设输人一副SAR图像经过一阶的Har小波 显示，基于灰度信息的聚类结果在细节上，特别对于 变化以后，其大小为n×m令L=n×m.则得到的 丝状溢油，分割误差很大.而提出的谱聚类算法，则 特征矩阵D的大小为L×3,采用Gaussian核函数， 具有相对更好的分割效果.图2为丝带状溢油，选用 度量数据间的相似度.其中，σ为核参数，依据经验 大小为3×3的滑动窗口，选取熵、一致性和对比度 值设置.本文提出的谱聚类的算法流程如下： 3个特征，高斯核函数的参数依经验选取σ=0.12. 1)分别计算单个特征向量间的欧式距离dm, 用提出的算法对其进行分割，得到如图2(b)的分割 m=1,2,3.dn=fm-fml,iJj=1,2,…,L.其中，f为 结果.只选用熵特征时，直接用k均值聚类得到的分 特征向量.然后求3个特征向量的平均距离平方和 割结果如图2(c).图2(a)的结果表明，多特征谱聚 d=三(d/3),根据W,=ep(-dno),计算相 类算法的分辨率较高，但受噪声影响比K-mean聚 类小 似性矩阵W∈R*m. (a)源图像 (b)本文算法 (c)直接用灰度聚类的结果 图1特征谱聚类与灰度谱聚类的结果比较 Fig.1 Comparison of segmentation results between spectral cluster and gray spectral cluster
·554. 智能系统学报 第5卷 (a)源图像 b)木文算法 (c)经典K聚类算法 图2与经典K聚类分割结果比较 Fig.2 Comparison of segmentation results the classic K-mean algorithm 3.2参数选取 很多的细节信息.图3为不同参数时的分割结果对 核参数依据经验设置，σ在0~0.15之间取值 比.当σ的取值过小时，分割结果只是几个点，无法 当参数值过大，会产生过分割，选的太小，则会丢失 对图像进行分割， (a)原始图像 (6)=0.12 (c)=0.012 图3参数取不同值时的分制结果对比 Fig.3 Comparison of segmentation with different parameters 4结束语 参考文献： 在本文中引入谱图分割理论先对图像进行压缩 [1]ARDHUIN F G,MERCIER G,GARELLO R.Oil slick de- 预处理，然后针对SAR图像中含有丰富的纹理特 tection by SAR imagery:potential and limitation.Digital Ob- 征，用灰度共生矩阵进行相应的特征提取，选取合适 ject Identifier10.1109/0 CEANS.2003.178539:164-169. 的特征矩阵，建立新的数据点间相似度公式，构造相 [2]FUMIAKI T,TSUJI S.Computer analysis of visual textures 似性矩阵，对其拉普拉斯矩阵的第2小特征值对应 [M].Boston:Kluwer Academic Publishers,1990:3-10. 的特征向量，用K-均值聚类的算法进行聚类.输入 [3]HARALICK M.Statistical and structural approaches to tex- 多幅图像，结果验证了该算法的稳健性，而且新算法 ture[C ]//Proceedings of the IEEE,1979,67(5):786- 804. 在减少运算时间的同时，保证了分割的精度和效果. [4]郭巍，张平，朱良，陈曦。基于AdaBoost.EC(0C的合成孔 但是由于谱聚类算法仍处于发展初期，算法本 径雷达图像目标识别研究[J].哈尔滨工程大学学报， 身还存在很多值得深入研究的问题.如何用有效的 2010,(2):232236. 算法减少运算量，如何自动地选取最佳核参数，还需 GUO Wei,ZHANG Ping,ZHU Liang,CHEN Xi.Research 要做进一步研究 on synthetic aperture radar image target recognition based on AdaBoost.ECOC[J].Journal of Harbin Engineering Uni-
第6期 张伟伟，等：多特征谱聚类的SAR图像溢油分割 ·555. versity,2010,(2):232-236 [15]HARALICK R M,SHANMUGAM K,DINSTEIN I.Tex- [5]ZHANG Fengli,SHAO Yun,TIAN Wei,et al.Oil spill i- ture features for image classification[J].IEEE Trans on dentification based on textural information of SAR Image Systerms,Man,and Cybernetics,1973,3(6):610-621. [C]//Proc of the IEEE International Geoscience and Re 作者简介： mote Sensing Symposium.Boston,USA,2008:1308-1311. 张伟伟，女，1983年生，硕士研究生， [6]马秀丽，焦李成.基于分水岭-谱聚类的SAR图像分割 主要研究方向为图像处理与视频分析. [J].红外与毫米波学报，2008,27(6)：452456. MA Xiuli,JIAO Licheng.SAR image segmentation based on watershed and spectral clustering[J].Journal of Infrared and Millimeter Waves,2008,27(6):452-456. [7]焦李成，张向荣，侯彪，等.智能SAR图像处理与解译 [M].北京：科学出版社，2008：409414. 薄华，女，1971年生，硕士生导 [8]BACH F R,JORDAN M I.Blind one microphone speech 师，主要研究方向为遥感图像处理、模 separation:a spectral learning approach[C]//Proc of Nine- 式识别、人工智能。先后主持上海市教 teenth Annual Conference Neural Information Processing 委项目1项，参加国家“863”计划和国 Systems(NIPS).Vancouver,Canada,2005:17. 家自然科学基金项目多项，其中作为第 [9]MALIK J,BELONGIE S,LEUNG T,et al.Contout and 二完成人获军队科技进步奖三等奖2 texture analysis for image segmentation[J].International 次.发表学术论文10余篇， Joumnal of Computer Vision,2001,43(1):7-27. [10]FIEDLER M.Algebraic connectivity of graphs[J].Czech- 王晓峰，男，1958年生，教授，博士 oslovak Mathematical Journal,1973,23:298-305. 生导师，上海海事大学信息工程学院院 [11]SHI J B,MALIK J.Normalized cuts and image segmenta- 长，上海海事大学学报编委，nternational tion[J].IEEE Trans on Patter Analysis and Machine In- Joural of Granular Computing,Rough telligence,2000,22(8):888-905. Sets and Intelligent Systems (IJGCRSIS) [12]DONATH W E,HOFFMAN A J.Lower bounds for parti- 编委：兼任中国人工智能学会机器学习 tioning of graphs[J].IBM Res Develop,1973,17:420- 专业委员会常务委员、智能交通专业委员会委员、粗糙集与粒 425. 度计算专业委员会委员：中国仪器仪表学会微机应用学会常 [13]HAGEN L,KAHNG A B.New spectral methods for ratio 务理事；上海海洋与湖沼学会海洋信息技术专业委员会副主 cut partitoning and clustering[J].IEEE Trans on Compu- 任等.任2006、2007EEE控制与机器学习国际会议程序委员 ted Aided Design,1992,11:1074-1085. 会委员.担任20O8 IEEE International Conference on Granular [14]DING C H Q,HE Xiaofeng,SIMON H D,ett al.A min- Computing程序委员会委员，2007 Interational Conference on max cut algorithom for graph partitioning and data cluste- Risk Analysis and Crisis Response会议副主席；国家科技部国 ring[C]//Proc of the 2001 IEEE Intemational Conference 际科技合作项目评审专家.主要研究方向为数据挖掘和机器 on Data Mining.Calofornia,USA,2001:107-114. 学习.发表学术论文多篇