基于HAC的溢油SAR图像分割算法

苏腾飞，孟俊敏，张 晰

(国家海洋局 第一海洋研究所，山东 青岛 266061)

每年在世界范围内都会发生数起海上溢油污染事故，给海洋生态环境带来非常恶劣的影响。2010年发生在美国墨西哥湾的“深水地平线”事件是一次特大原油泄漏事故。据专家估计，这次事故对当地生态环境的危害会持续数十年之久。为了清理这次事故的溢油，美国政府被迫投入了巨大的人力和物力[1]。日益增加的海洋石油污染已成为全球最为严重的环境问题之一。

溢油监测可以提供溢油位置和面积信息，但是利用传统手段监测海上溢油，难以满足覆盖面积大和长时间连续监测的要求。卫星遥感技术的兴起，可以有效解决这一问题。目前可以被用来探测海上溢油的卫星传感器主要包括合成孔径雷达(SAR)、水色和可见光传感器、红外和紫外传感器以及微波辐射计等。其中SAR不受云雾遮挡和光照条件的限制，可全天时、全天候工作，现已成为业务化海上溢油监测的主要遥感传感器[2]。

Bragg共振散射机制是SAR海面成像的主要原理。当海面上有油膜存在时，海面上的短重力波会受到阻尼作用，从而减弱雷达的后向散射回波信号，因此油膜在SAR图像中呈现出暗区域[3]。Solberg等指出，SAR溢油检测包含3个步骤：1)暗斑识别；2)特征提取；3)溢油检测。其中，暗斑识别是利用图像分割来实现的[4]。图像分割的效果直接影响溢油位置、面积信息的提取和溢油检测的精度，因此图像分割在SAR溢油检测中非常关键。

图像分割算法主要分为3大类：基于边界的、基于区域的和结合前两者的。基于边界和基于区域的算法分别是通过边缘检测和区域合并实现的[5]。Canny算子是较为著名的基于边界的图像分割算法，Chang等利用该方法检测SAR图像中的溢油边界[6]。基于区域的方法主要有阈值分割、聚类分割。OTSU是应用广泛的阈值分割算法，刘鹏、杨永生等将该算法应用到了SAR溢油检测中[7-8]。张伟伟等发展了一种多特征-普聚类的溢油SAR图像分割算法[9]。Yu等讨论了模糊C均值聚类(Fuzzy C-Means, FCM)在溢油SAR图像分割上的应用[5]。水平集方法结合了基于边界和区域算法的特点。Karantzalos和Li等开展了水平集方法分割溢油SAR图像的研究[10-11]。然而，SAR图像中存在斑点噪声，以上方法均易受其影响而分割出很多细碎的斑块。鉴于此，拟发展一种基于HAC的溢油SAR图像分割算法，旨在减少细碎斑块的产生，将SAR影像中的暗斑以最佳的效果分割出来，以提高后续特征提取和溢油检测工作的精度。

1 算法原理

图像聚类分割的一般步骤：从象元开始，自底向上，根据一定的合并条件，将相似度大的象元或斑块合并，直到整个图像没有满足条件的合并为止。Baatz等指出，这样的图像分割算法应包含2部分[12]：

1)搜索适合合并斑块的方法，即斑块合并探索法；

2)判别2个斑块合并的合适程度。

以上是商业图像分析软件eCognition中多尺度分割算法的原始思想[12]。研究中，采用HAC实现斑块合并探索法，并使斑块异质性作为衡量斑块合并的合适程度的标准。

1.1 HAC方法介绍

层次聚类是数据挖掘的一种方法，最早由Johnson 于1967年提出。它具有凝聚和分裂两种方式，前者采用自底向上的策略，按照一定的规则，把集合中的各个元素逐步合并为一个有序的序列，后者采用了相反的流程[13]。HAC的这种特点使其适用于图像分割的斑块合并探索法。根据Johnson的描述，HAC主要包括4步：

1)对于含有N个元素的集合，首先将集合中的每一个元素视为一个类簇，并计算出它与其他类簇的距离(或相似度)；

2)找到距离最短(或相似度最接近)的一对类簇，将其合并；

3)重新计算出新类簇与其他类簇的距离(或相似度)；

4)重复步骤2和3，直到所有类簇被合并为一个类簇。

1.2 基于HAC方法的斑块合并探索法

Baatz等给出了制定斑块合并探索法的4个标准[12]：

1) 合适(Fitting)，在斑块A的邻域找到任意一个满足合并条件的斑块B，将其合并；

2)最合适(Best fitting)，在斑块A的邻域寻找与A最适合合并的斑块B，将其合并；

3)局部相互最合适(Local mutual best fitting)，在斑块A的邻域寻找与A最适合合并的斑块B，然后在B的邻域寻找与B最适合合并的斑块C；若A与C相同，则A与B合并；否则，则将B视为A，将C视为B，重新判断；

4)全局相互最合适(Global mutual best fitting)：在全图中，所有斑块合并均满足标准3。显然，要使图像分割的效果达到最佳，应满足标准4。

鉴于标准4，本研究利用HAC方法实现合并探索发现，它包含4步：

1)将每个像素视为一个斑块，并建立其邻接关系，我们采用四邻域的规则；

2)遍历所有斑块，设当前斑块为A，计算A与其邻近斑块的异质性，得到与A合并后异质性变化最小的邻域斑块B，即找到与A最适合合并的斑块B；

3)寻找与B最适合合并的斑块C，若A与C不同，则继续进行斑块遍历，否则将A和B合并，另外，在下回遍历时需要重新计算新斑块与其邻接斑块的异质性改变值；

4)重复2和3，直到满足条件的合并均进行完毕为止。

步骤2和步骤3满足了Local mutual best fitting准则；步骤4将步骤2和步骤3的操作推广到全图，因此Global mutual best fitting准则得以满足。在实际操作中，利用Baatz提出的分布式斑块合并方法[12]，可以使分割结果的斑块大小均匀，达到多尺度分割的效果。图1为利用计算机语言实现本文算法的流程。由于C++语言具有面向对象、泛型编程等优越特性，适宜于实现复杂的图形图像处理算法，因此本研究利用它实现基于HAC的溢油SAR图像分割算法。

图1 基于HAC的溢油SAR图像分割算法流程图Fig. 1 Flow chart for oil spill SAR image segmentation developed based on HAC

1.3 斑块异质性

在进行聚类分割时，需要一个标准来考察两个相邻斑块是否适合合并。图像斑块的异质性，描述了图像斑块形状和灰度的特征，非常适合用作图像斑块合并的标准。

图像斑块的异质性包含2个部分：灰度异质性和形状异质性。

灰度异质性的计算方法是图像斑块中各个波段像素标准差的加权和hgrey，其公式如下[12]

(1)

式中，wgrey为灰度分量权重；σc为斑块中第c个波段的像素标准差。由于本研究的算法主要针对的是单极化的溢油SAR影像，此处c为1。

仅仅利用灰度异质性难以得到满意的分割效果，在异质性中考虑斑块的形状特征可以使分割斑块的边界更平滑，并且减少破碎的斑块产生。形状异质性包含了2部分，紧凑异质性hcompact和平滑异质性hsmooth，其计算公式分别如下[12]

(2)

(3)

hshape=wcompact·hcompact+(1-wcompact)·hsmooth

(4)

式中，l为图像斑块的边界长度；n为图像斑块包含的像素数目；b为包围图像斑块的外接矩形的长度值；wcompact为紧凑性权重。

综合考虑了灰度和形状的异质性计算公式如下[12]

f=wgrey·hgrey+(1-wgrey)·hshape

(5)

在进行斑块合并时，可以在其邻接斑块中选择使其异质性改变最小的斑块，与其合并。异质性变化的公式如下[12]

f′=wgrey·hgrey′+(1-wgrey)·hshape′

(6)

hgrey′=nmerge·σmerge-(n1·σ1+n2·σ2)

(7)

hshape′=wcompact·hcompact′+(1-wcompact)·hsmooth′

(8)

(9)

(10)

式中，脚标1、2和merge分别为当前斑块、当前斑块的邻接斑块以及2个斑块合并后的斑块；hgrey′，hshape′，hcompact′，hsmooth′，f′分别为灰度异质性变化、形状异质性变化、紧凑性异质性变化、平滑性异质性变化以及总异质性变化。

2 数据介绍

采用了3景Envisat ASAR WSM模式影像，C波段，VV极化，分辨率150 m，均是2010年美国墨西哥湾溢油事故的影像。利用ESA提供的开源软件NEST，对SAR影像进行辐射标定、斑点噪声滤除、几何校正等预处理。图2显示了所采用的SAR影像。

图2 Envisat ASAR墨西哥湾溢油影像Fig. 2 Envisat ASAR images of the Gulf of Mexico used in the present paper

美国国家海洋大气管理局(NOAA)对2010年墨西哥湾溢油事故进行了全方位的监测和治理，其官方网站(www.noaa.gov/deepwaterhorizon/maps/traj_maps.html)提供了经多源数据验证的溢油位置信息。我们分割实验采用的SAR影像油膜，就是根据该网站提供的信息选取的(图2黑色方框所示)。为了便于分割算法的对比分析，从3景影像中选取了大小相当的油膜，其子图像的尺寸均为500×500。

3 对比分析

为了验证HAC溢油SAR图像分割算法的有效性，分别在基于边界、基于区域以及结合边界和区域的图像分割算法中，选取了最具代表性的算法与其进行对比。第一类分割算法选取了Canny算子；第二类算法中选用了OTSU、FCM算法；第三类算法中，选取了C-V水平集算法。

3.1 与Canny算子的对比

Canny算子包含3个步骤：1)将原始图像与高斯函数进行卷积运算，抑制高斯加性噪声的影响；2)进行微分运算，分别求出水平、垂直方向的差分；3)检测边缘像素点。Canny算子的高斯滤波器的方差一般设定为1.4[14]。

图3 Canny算子与HAC算法的对比Fig. 3 Contrast between the Canny operator and the HAC algorithm

图3为Canny算子与本研究提出的算法检测SAR图像中溢油区域边界的结果。本研究的算法碎块合并阈值均为100，以适合图像中溢油斑块的实际尺寸。HAC算法可以有效分割出暗斑，但Canny算子分割效果较差：1)它难以分割出闭合的边界，这也是基于边界的图像分割算法普遍存在的弊端；2)它易检测出错误的边界(图3)。这主要是因为SAR图像中存在乘性的斑点噪声，虽然Canny算子对加性噪声有一定的抑制作用，但它难以抑制乘性噪声而产生很差的分割效果。鉴于以上弊端，我们对Canny算子的研究仅止于此。

相比之下，HAC算法可以产生闭合的斑块曲线，这对暗斑的特征提取和后续的溢油检测具有重要意义。

3.2 与OTSU和FCM算法的对比

OTSU与FCM分割算法分别是阈值分割和聚类分割中具有代表性的算法，均属于基于区域的方法，因此将本文算法与这两种算法一起进行对比。

OTSU算法由Otsu于1979年提出，又称为最大类间方差法，它是一种经典的非参数图像分割方法。它首先将图像的直方图分为两类，通过最小化类间直方图和最大化类外直方图的方差，来确定分割阈值[7]。

FCM图像分割算法应用广泛，它本质上是一种基于目标函数的非线性迭代最优化方法。该方法首先确定聚类中心，然后通过迭代，确定使目标函数最小的聚类中心，以达到最佳分割效果[15]。

图4为3种算法的分割结果对比。3种算法均能将溢油暗斑的主题部分分割出来，其中HAC效果最佳，FCM次之，OTSU最差。受SAR图像斑点噪声的影响，OTSU与FCM的分割结果中存在许多细碎的暗斑,而HAC分割结果无细碎暗斑。这是因为，HAC算法将较小的斑块合并在一起，组成更大的均一致的斑块。

图4 OTSU,FCM方法与HAC的对比Fig. 4 Contrast between the OTSU and FCM methods and the HAC algorithm

3.3 与C-V水平集算法的对比

水平集方法最早由美国数学家Osher与Sethian联合提出，其主要思想是将曲线演化表示为更高维度的超平面水平集演化。Chan和Vese于2001年提出了一种简化的水平集方法，称为C-V模型，该方法在模糊边缘的检测方面具有更好的效果[16]。

图5 C-V水平集方法与HAC方法的对比Fig. 5 Contrast between the C-V level set and the HAC algorithm

图5为C-V水平集与HAC算法的结果对比。水平集方法的初始状态设置为圆形，其圆心为图像中心，半径为150，迭代次数为2 000。迭代次数越高，该算法运算时间越长，2 000次迭代需要的计算时间在3 min以上。但该方法分割效果很差：1)结果中存在过多的细碎斑块;2)部分溢油斑块的边界未能检测到。其主要原因分别为：1)SAR图像中存在斑点噪声，它使曲线在演化过程中发生了拓补关系的改变，即产生了曲线的分裂现象；2)过多的曲线分裂增加了计算复杂度，使得在一定的迭代次数内难以达到最佳分割效果，致使有些暗斑边界未能检测到。鉴于以上因素，本研究对C-V水平集算法的探究仅止于此。

为了进一步验证HAC算法的精度，本研究将以上各个算法的分割结果与专家解译结果进行了比较。根据3.1和3.3的结论，本节仅考虑OTSU，FCM和HAC算法。图6为专家手动提取的溢油斑块。

图6 专家解译溢油斑块Fig. 6 Oil spill patches interpreted by experts

由图3～6可见，专家手动提取的溢油斑块，具有更加平滑的边界，其溢油斑块面积从左至右分别为：52.88 km2，134.26 km2，140.98 km2。表1为3种算法的溢油斑块面积与专家解译结果对比，并提供了3种算法的运算时间。

表1 OTSU，FCM与HAC算法溢油斑块面积和运算时间Table 1 The area of oil spill patches and operating time obtained respectively by using OTSU, FCM and HAC

这3种算法的运行环境：Windows 7(32位)操作系统；Intel酷睿2处理器(2.13GHz)；编译环境为Microsoft Visual Studio 2010；4Gb内存。由表1可以看出，OTSU算法的分割暗斑面积与专家解译结果严重不符，但其运算时间最短，不到1 s；FCM算法的分割结果也出现了专家解译结果严重不符的情况，其运算时间居中，基本在3 s以内；HAC算法的分割结果最佳，与专家解译结果的差值不超过16.3%，但其运算时间最长，为5 s左右，在可接受的范围内。由此推论：算法的计算时间越长，其运算复杂度越高，分割效果越佳。

表2 OTSU分割结果的混淆矩阵Table 2 The confusion matrix of segmentation results by using OTSU

表3 FCM分割结果的混淆矩阵Table 3 The confusion matrix of segmentation results by using FCM

表4 HAC分割结果的混淆矩阵Table 4 The confusion matrix of segmentation results by using HAC

以2010-07-21的实验油膜暗斑为例，计算出了3种算法暗斑分割的混淆矩阵(表2～4)。OTSU，FCM，HAC算法的暗斑分割总精度分别为76.6%，95.2%，98.6%。OTSU的精度最差，其暗斑分割的用户精度仅为15.4%；FCM的精度居中，但其暗斑用户精度也不高，为48.3%；HAC的精度最高，其暗斑用户精度也达到了82.8%。其中，FCM和HAC的分割总精度较为接近，但HAC略高，前者的过程精度均低于后者。细碎暗斑过多，是OTSU与FCM算法精度低于HAC的主要原因。

5 结 论

本研究发展了一种基于HAC的溢油SAR图像分割算法，该方法能够有效减少细碎暗斑的产生，分割出SAR影像中的暗斑；经过与其他分割算法的对比，显示了不错的分割效果。主要结论如下：

1)发展的方法能够得到闭合的暗斑区域边缘曲线，且可以有效减少细碎暗斑的产生；

2)Canny算子边缘检测方法难以得到闭合的暗斑区域边缘，且易受斑点噪声的影响而产生错误的边缘检测结果；

3)OTSU和FCM方法容易受斑点噪声的影响而产生细碎的暗斑，FCM的效果优于OTSU，但也需要更多的运算时间；

4)C-V水平集算法易受斑点噪声的影响而产生细碎斑块，且运算时间较长。

参考文献(References)：

[1] WIKIPEDIA. Deepwater horizon oil spill [EB/OL].[2011-03-20]. http:∥en.wikipedia.org/wiki/Deepwater_Horizon_oil_spill.

[2] BREKKE C, SOLBERG A H S. Oil spill detection by satellite remote sensing[J].Remote Sensing of Environment, 2005, 95(1):1-13.

[3] WERNER A, HEINRICH H. The damping of ocean waves by surface films: a new look at an old problem[J].Journal of Geophysical Research, 1989, 94(C5): 6251-6265.

[4] SOLBERG A H S, BREKKE C, HUSOY P. Oil spill detection in radarsat and Envisat SAR images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(3):746-755.

[5] YU J, AN J, LIU Z. A novel edge detection algorithm based on global minimization active contour model for oil slick infrared aerial image[J]. IEEE Transactions on Geoscience and Remote Sensing, 2011, 49(6): 2005-2013.

[6] CHANG L, TANG Z S, CHANG S H, et al. A region-based GLRT detection of oil spills in SAR images[J]. Pattern Recognition Letters, 2008, 29: 1915-1923.

[7] LIU P, ZHAO C, LI X, et al. Identification of ocean oil spills in SAR imagery based on fuzzy logic algorithm[J]. International Journal of Remote Sensing, 2010, 31(17): 4819-4833.

[8] YANG Y S, ZHANG Z J. An image segment method for large SAR oil spilled at sea[J].Marine Environmental Science, 2010, 29(6): 914-916. 杨永生, 张宗杰. 一种适合于大面积的 SAR海面溢油图像分割方法[J]. 海洋环境科学, 2010, 29(6): 914-916.

[9] ZHANG W W, BO H, WANG X F. SAR oil spill image segmentation based on a multi-spectral clustering algorithm[J]. CAAI Transactions on Intelligent System, 2010, 5(6): 551-555. 张伟伟, 薄华, 王晓峰. 多特征-普聚类的SAR图像溢油分割[J]. 智能系统学报, 2010, 5(6): 551-555.

[10] KARANTZALOS K, ARGIALAS D. Automatic detection and tracking of oil spills in SAR imagery with level set segmentation[J]. Remote Sensing of Environment, 2008, 29(21): 6281-6296.

[11] LI F, SHEN C. A two-stage mMethod for oil slick segmentation[J]. International Journal of Remote Sensing, 2008, 31(15): 4217-4226.

[12] BAATA M, SCHPE A. Multiresolution segmentation: an optimization approach for high quality multi-scale image segmentation[J]. Angewandte Geographische Informationsverarbeitung, 2000, 10: 12-23.

[13] MATTEUCC. A tutorial on custering algorithms[EB/OL]. [2012-08-10]. http:∥home.dei.polimi.it/matteucc/Clustering/tutorial_html.

[14] LI W B, TIAN J H, LI Z L. Edge detection for SAR image based on improved canny operator[J]. Journal of Xianyang Normal University, 2006, 21(2): 40-42. 李卫斌, 田俊华, 李宗领. 基于改进Canny算子的SAR图像边缘检测[J]. 咸阳师范学院学报, 2006, 21(2): 40-42.

[15] HU G, LI J, HUANG B X. Image segmentation via Fuzzy C-Means clustering with spatial information[J]. Computer & Digital Engineering. 2008, 36(4):122-124. 湖广, 李娟, 黄本雄. 结合空间信息的模糊C均值聚类图像分割算法[J]. 计算机与数字工程, 2008, 36(4):122-124.

[16] SHI L J. Research on sea surface oil spill detection by SAR and MODIS data[D]. Qingdao: Ocean University of China. 2008. 石立坚. SAR及MODIS数据海面溢油监测方法研究[D]. 青岛: 中国海洋大学, 2008.