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

蘇騰飛，孟俊敏，張 晰

(國家海洋局 第一海洋研究所，山東 青島 266061)

每年在世界范圍內(nèi)都會發(fā)生數(shù)起海上溢油污染事故，給海洋生態(tài)環(huán)境帶來非常惡劣的影響。2010年發(fā)生在美國墨西哥灣的“深水地平線”事件是一次特大原油泄漏事故。據(jù)專家估計(jì)，這次事故對當(dāng)?shù)厣鷳B(tài)環(huán)境的危害會持續(xù)數(shù)十年之久。為了清理這次事故的溢油，美國政府被迫投入了巨大的人力和物力[1]。日益增加的海洋石油污染已成為全球最為嚴(yán)重的環(huán)境問題之一。

溢油監(jiān)測可以提供溢油位置和面積信息，但是利用傳統(tǒng)手段監(jiān)測海上溢油，難以滿足覆蓋面積大和長時(shí)間連續(xù)監(jiān)測的要求。衛(wèi)星遙感技術(shù)的興起，可以有效解決這一問題。目前可以被用來探測海上溢油的衛(wèi)星傳感器主要包括合成孔徑雷達(dá)(SAR)、水色和可見光傳感器、紅外和紫外傳感器以及微波輻射計(jì)等。其中SAR不受云霧遮擋和光照條件的限制，可全天時(shí)、全天候工作，現(xiàn)已成為業(yè)務(wù)化海上溢油監(jiān)測的主要遙感傳感器[2]。

Bragg共振散射機(jī)制是SAR海面成像的主要原理。當(dāng)海面上有油膜存在時(shí)，海面上的短重力波會受到阻尼作用，從而減弱雷達(dá)的后向散射回波信號，因此油膜在SAR圖像中呈現(xiàn)出暗區(qū)域[3]。Solberg等指出，SAR溢油檢測包含3個(gè)步驟：1)暗斑識別；2)特征提?。?)溢油檢測。其中，暗斑識別是利用圖像分割來實(shí)現(xiàn)的[4]。圖像分割的效果直接影響溢油位置、面積信息的提取和溢油檢測的精度，因此圖像分割在SAR溢油檢測中非常關(guān)鍵。

圖像分割算法主要分為3大類：基于邊界的、基于區(qū)域的和結(jié)合前兩者的?；谶吔绾突趨^(qū)域的算法分別是通過邊緣檢測和區(qū)域合并實(shí)現(xiàn)的[5]。Canny算子是較為著名的基于邊界的圖像分割算法，Chang等利用該方法檢測SAR圖像中的溢油邊界[6]?；趨^(qū)域的方法主要有閾值分割、聚類分割。OTSU是應(yīng)用廣泛的閾值分割算法，劉鵬、楊永生等將該算法應(yīng)用到了SAR溢油檢測中[7-8]。張偉偉等發(fā)展了一種多特征-普聚類的溢油SAR圖像分割算法[9]。Yu等討論了模糊C均值聚類(Fuzzy C-Means, FCM)在溢油SAR圖像分割上的應(yīng)用[5]。水平集方法結(jié)合了基于邊界和區(qū)域算法的特點(diǎn)。Karantzalos和Li等開展了水平集方法分割溢油SAR圖像的研究[10-11]。然而，SAR圖像中存在斑點(diǎn)噪聲，以上方法均易受其影響而分割出很多細(xì)碎的斑塊。鑒于此，擬發(fā)展一種基于HAC的溢油SAR圖像分割算法，旨在減少細(xì)碎斑塊的產(chǎn)生，將SAR影像中的暗斑以最佳的效果分割出來，以提高后續(xù)特征提取和溢油檢測工作的精度。

1 算法原理

圖像聚類分割的一般步驟：從象元開始，自底向上，根據(jù)一定的合并條件，將相似度大的象元或斑塊合并，直到整個(gè)圖像沒有滿足條件的合并為止。Baatz等指出，這樣的圖像分割算法應(yīng)包含2部分[12]：

1)搜索適合合并斑塊的方法，即斑塊合并探索法；

2)判別2個(gè)斑塊合并的合適程度。

以上是商業(yè)圖像分析軟件eCognition中多尺度分割算法的原始思想[12]。研究中，采用HAC實(shí)現(xiàn)斑塊合并探索法，并使斑塊異質(zhì)性作為衡量斑塊合并的合適程度的標(biāo)準(zhǔn)。

1.1 HAC方法介紹

層次聚類是數(shù)據(jù)挖掘的一種方法，最早由Johnson 于1967年提出。它具有凝聚和分裂兩種方式，前者采用自底向上的策略，按照一定的規(guī)則，把集合中的各個(gè)元素逐步合并為一個(gè)有序的序列，后者采用了相反的流程[13]。HAC的這種特點(diǎn)使其適用于圖像分割的斑塊合并探索法。根據(jù)Johnson的描述，HAC主要包括4步：

1)對于含有N個(gè)元素的集合，首先將集合中的每一個(gè)元素視為一個(gè)類簇，并計(jì)算出它與其他類簇的距離(或相似度)；

2)找到距離最短(或相似度最接近)的一對類簇，將其合并；

3)重新計(jì)算出新類簇與其他類簇的距離(或相似度)；

4)重復(fù)步驟2和3，直到所有類簇被合并為一個(gè)類簇。

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

Baatz等給出了制定斑塊合并探索法的4個(gè)標(biāo)準(zhǔn)[12]：

1) 合適(Fitting)，在斑塊A的鄰域找到任意一個(gè)滿足合并條件的斑塊B，將其合并；

2)最合適(Best fitting)，在斑塊A的鄰域?qū)ふ遗cA最適合合并的斑塊B，將其合并；

3)局部相互最合適(Local mutual best fitting)，在斑塊A的鄰域?qū)ふ遗cA最適合合并的斑塊B，然后在B的鄰域?qū)ふ遗cB最適合合并的斑塊C；若A與C相同，則A與B合并；否則，則將B視為A，將C視為B，重新判斷；

4)全局相互最合適(Global mutual best fitting)：在全圖中，所有斑塊合并均滿足標(biāo)準(zhǔn)3。顯然，要使圖像分割的效果達(dá)到最佳，應(yīng)滿足標(biāo)準(zhǔn)4。

鑒于標(biāo)準(zhǔn)4，本研究利用HAC方法實(shí)現(xiàn)合并探索發(fā)現(xiàn)，它包含4步：

1)將每個(gè)像素視為一個(gè)斑塊，并建立其鄰接關(guān)系，我們采用四鄰域的規(guī)則；

2)遍歷所有斑塊，設(shè)當(dāng)前斑塊為A，計(jì)算A與其鄰近斑塊的異質(zhì)性，得到與A合并后異質(zhì)性變化最小的鄰域斑塊B，即找到與A最適合合并的斑塊B；

3)尋找與B最適合合并的斑塊C，若A與C不同，則繼續(xù)進(jìn)行斑塊遍歷，否則將A和B合并，另外，在下回遍歷時(shí)需要重新計(jì)算新斑塊與其鄰接斑塊的異質(zhì)性改變值；

4)重復(fù)2和3，直到滿足條件的合并均進(jìn)行完畢為止。

步驟2和步驟3滿足了Local mutual best fitting準(zhǔn)則；步驟4將步驟2和步驟3的操作推廣到全圖，因此Global mutual best fitting準(zhǔn)則得以滿足。在實(shí)際操作中，利用Baatz提出的分布式斑塊合并方法[12]，可以使分割結(jié)果的斑塊大小均勻，達(dá)到多尺度分割的效果。圖1為利用計(jì)算機(jī)語言實(shí)現(xiàn)本文算法的流程。由于C++語言具有面向?qū)ο?、泛型編程等?yōu)越特性，適宜于實(shí)現(xiàn)復(fù)雜的圖形圖像處理算法，因此本研究利用它實(shí)現(xiàn)基于HAC的溢油SAR圖像分割算法。

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

1.3 斑塊異質(zhì)性

在進(jìn)行聚類分割時(shí)，需要一個(gè)標(biāo)準(zhǔn)來考察兩個(gè)相鄰斑塊是否適合合并。圖像斑塊的異質(zhì)性，描述了圖像斑塊形狀和灰度的特征，非常適合用作圖像斑塊合并的標(biāo)準(zhǔn)。

圖像斑塊的異質(zhì)性包含2個(gè)部分：灰度異質(zhì)性和形狀異質(zhì)性。

灰度異質(zhì)性的計(jì)算方法是圖像斑塊中各個(gè)波段像素標(biāo)準(zhǔn)差的加權(quán)和hgrey，其公式如下[12]

(1)

式中，wgrey為灰度分量權(quán)重；σc為斑塊中第c個(gè)波段的像素標(biāo)準(zhǔn)差。由于本研究的算法主要針對的是單極化的溢油SAR影像，此處c為1。

僅僅利用灰度異質(zhì)性難以得到滿意的分割效果，在異質(zhì)性中考慮斑塊的形狀特征可以使分割斑塊的邊界更平滑，并且減少破碎的斑塊產(chǎn)生。形狀異質(zhì)性包含了2部分，緊湊異質(zhì)性hcompact和平滑異質(zhì)性hsmooth，其計(jì)算公式分別如下[12]

(2)

(3)

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

(4)

式中，l為圖像斑塊的邊界長度；n為圖像斑塊包含的像素?cái)?shù)目；b為包圍圖像斑塊的外接矩形的長度值；wcompact為緊湊性權(quán)重。

綜合考慮了灰度和形狀的異質(zhì)性計(jì)算公式如下[12]

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

(5)

在進(jìn)行斑塊合并時(shí)，可以在其鄰接斑塊中選擇使其異質(zhì)性改變最小的斑塊，與其合并。異質(zhì)性變化的公式如下[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)

式中，腳標(biāo)1、2和merge分別為當(dāng)前斑塊、當(dāng)前斑塊的鄰接斑塊以及2個(gè)斑塊合并后的斑塊；hgrey′，hshape′，hcompact′，hsmooth′，f′分別為灰度異質(zhì)性變化、形狀異質(zhì)性變化、緊湊性異質(zhì)性變化、平滑性異質(zhì)性變化以及總異質(zhì)性變化。

2 數(shù)據(jù)介紹

采用了3景Envisat ASAR WSM模式影像，C波段，VV極化，分辨率150 m，均是2010年美國墨西哥灣溢油事故的影像。利用ESA提供的開源軟件NEST，對SAR影像進(jìn)行輻射標(biāo)定、斑點(diǎn)噪聲濾除、幾何校正等預(yù)處理。圖2顯示了所采用的SAR影像。

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

美國國家海洋大氣管理局(NOAA)對2010年墨西哥灣溢油事故進(jìn)行了全方位的監(jiān)測和治理，其官方網(wǎng)站(www.noaa.gov/deepwaterhorizon/maps/traj_maps.html)提供了經(jīng)多源數(shù)據(jù)驗(yàn)證的溢油位置信息。我們分割實(shí)驗(yàn)采用的SAR影像油膜，就是根據(jù)該網(wǎng)站提供的信息選取的(圖2黑色方框所示)。為了便于分割算法的對比分析，從3景影像中選取了大小相當(dāng)?shù)挠湍ぃ渥訄D像的尺寸均為500×500。

3 對比分析

為了驗(yàn)證HAC溢油SAR圖像分割算法的有效性，分別在基于邊界、基于區(qū)域以及結(jié)合邊界和區(qū)域的圖像分割算法中，選取了最具代表性的算法與其進(jìn)行對比。第一類分割算法選取了Canny算子；第二類算法中選用了OTSU、FCM算法；第三類算法中，選取了C-V水平集算法。

3.1 與Canny算子的對比

Canny算子包含3個(gè)步驟：1)將原始圖像與高斯函數(shù)進(jìn)行卷積運(yùn)算，抑制高斯加性噪聲的影響；2)進(jìn)行微分運(yùn)算，分別求出水平、垂直方向的差分；3)檢測邊緣像素點(diǎn)。Canny算子的高斯濾波器的方差一般設(shè)定為1.4[14]。

圖3 Canny算子與HAC算法的對比Fig. 3 Contrast between the Canny operator and the HAC algorithm

圖3為Canny算子與本研究提出的算法檢測SAR圖像中溢油區(qū)域邊界的結(jié)果。本研究的算法碎塊合并閾值均為100，以適合圖像中溢油斑塊的實(shí)際尺寸。HAC算法可以有效分割出暗斑，但Canny算子分割效果較差：1)它難以分割出閉合的邊界，這也是基于邊界的圖像分割算法普遍存在的弊端；2)它易檢測出錯(cuò)誤的邊界(圖3)。這主要是因?yàn)镾AR圖像中存在乘性的斑點(diǎn)噪聲，雖然Canny算子對加性噪聲有一定的抑制作用，但它難以抑制乘性噪聲而產(chǎn)生很差的分割效果。鑒于以上弊端，我們對Canny算子的研究僅止于此。

相比之下，HAC算法可以產(chǎn)生閉合的斑塊曲線，這對暗斑的特征提取和后續(xù)的溢油檢測具有重要意義。

3.2 與OTSU和FCM算法的對比

OTSU與FCM分割算法分別是閾值分割和聚類分割中具有代表性的算法，均屬于基于區(qū)域的方法，因此將本文算法與這兩種算法一起進(jìn)行對比。

OTSU算法由Otsu于1979年提出，又稱為最大類間方差法，它是一種經(jīng)典的非參數(shù)圖像分割方法。它首先將圖像的直方圖分為兩類，通過最小化類間直方圖和最大化類外直方圖的方差，來確定分割閾值[7]。

FCM圖像分割算法應(yīng)用廣泛，它本質(zhì)上是一種基于目標(biāo)函數(shù)的非線性迭代最優(yōu)化方法。該方法首先確定聚類中心，然后通過迭代，確定使目標(biāo)函數(shù)最小的聚類中心，以達(dá)到最佳分割效果[15]。

圖4為3種算法的分割結(jié)果對比。3種算法均能將溢油暗斑的主題部分分割出來，其中HAC效果最佳，F(xiàn)CM次之，OTSU最差。受SAR圖像斑點(diǎn)噪聲的影響，OTSU與FCM的分割結(jié)果中存在許多細(xì)碎的暗斑,而HAC分割結(jié)果無細(xì)碎暗斑。這是因?yàn)?，HAC算法將較小的斑塊合并在一起，組成更大的均一致的斑塊。

圖4 OTSU,FCM方法與HAC的對比Fig. 4 Contrast between the OTSU and FCM methods and the HAC algorithm

3.3 與C-V水平集算法的對比

水平集方法最早由美國數(shù)學(xué)家Osher與Sethian聯(lián)合提出，其主要思想是將曲線演化表示為更高維度的超平面水平集演化。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算法的結(jié)果對比。水平集方法的初始狀態(tài)設(shè)置為圓形，其圓心為圖像中心，半徑為150，迭代次數(shù)為2 000。迭代次數(shù)越高，該算法運(yùn)算時(shí)間越長，2 000次迭代需要的計(jì)算時(shí)間在3 min以上。但該方法分割效果很差：1)結(jié)果中存在過多的細(xì)碎斑塊;2)部分溢油斑塊的邊界未能檢測到。其主要原因分別為：1)SAR圖像中存在斑點(diǎn)噪聲，它使曲線在演化過程中發(fā)生了拓補(bǔ)關(guān)系的改變，即產(chǎn)生了曲線的分裂現(xiàn)象；2)過多的曲線分裂增加了計(jì)算復(fù)雜度，使得在一定的迭代次數(shù)內(nèi)難以達(dá)到最佳分割效果，致使有些暗斑邊界未能檢測到。鑒于以上因素，本研究對C-V水平集算法的探究僅止于此。

為了進(jìn)一步驗(yàn)證HAC算法的精度，本研究將以上各個(gè)算法的分割結(jié)果與專家解譯結(jié)果進(jìn)行了比較。根據(jù)3.1和3.3的結(jié)論，本節(jié)僅考慮OTSU，F(xiàn)CM和HAC算法。圖6為專家手動提取的溢油斑塊。

圖6 專家解譯溢油斑塊Fig. 6 Oil spill patches interpreted by experts

由圖3～6可見，專家手動提取的溢油斑塊，具有更加平滑的邊界，其溢油斑塊面積從左至右分別為：52.88 km2，134.26 km2，140.98 km2。表1為3種算法的溢油斑塊面積與專家解譯結(jié)果對比，并提供了3種算法的運(yùn)算時(shí)間。

表1 OTSU，F(xiàn)CM與HAC算法溢油斑塊面積和運(yùn)算時(shí)間Table 1 The area of oil spill patches and operating time obtained respectively by using OTSU, FCM and HAC

這3種算法的運(yùn)行環(huán)境：Windows 7(32位)操作系統(tǒng)；Intel酷睿2處理器(2.13GHz)；編譯環(huán)境為Microsoft Visual Studio 2010；4Gb內(nèi)存。由表1可以看出，OTSU算法的分割暗斑面積與專家解譯結(jié)果嚴(yán)重不符，但其運(yùn)算時(shí)間最短，不到1 s；FCM算法的分割結(jié)果也出現(xiàn)了專家解譯結(jié)果嚴(yán)重不符的情況，其運(yùn)算時(shí)間居中，基本在3 s以內(nèi)；HAC算法的分割結(jié)果最佳，與專家解譯結(jié)果的差值不超過16.3%，但其運(yùn)算時(shí)間最長，為5 s左右，在可接受的范圍內(nèi)。由此推論：算法的計(jì)算時(shí)間越長，其運(yùn)算復(fù)雜度越高，分割效果越佳。

表2 OTSU分割結(jié)果的混淆矩陣Table 2 The confusion matrix of segmentation results by using OTSU

表3 FCM分割結(jié)果的混淆矩陣Table 3 The confusion matrix of segmentation results by using FCM

表4 HAC分割結(jié)果的混淆矩陣Table 4 The confusion matrix of segmentation results by using HAC

以2010-07-21的實(shí)驗(yàn)油膜暗斑為例，計(jì)算出了3種算法暗斑分割的混淆矩陣(表2～4)。OTSU，F(xiàn)CM，HAC算法的暗斑分割總精度分別為76.6%，95.2%，98.6%。OTSU的精度最差，其暗斑分割的用戶精度僅為15.4%；FCM的精度居中，但其暗斑用戶精度也不高，為48.3%；HAC的精度最高，其暗斑用戶精度也達(dá)到了82.8%。其中，F(xiàn)CM和HAC的分割總精度較為接近，但HAC略高，前者的過程精度均低于后者。細(xì)碎暗斑過多，是OTSU與FCM算法精度低于HAC的主要原因。

5 結(jié) 論

本研究發(fā)展了一種基于HAC的溢油SAR圖像分割算法，該方法能夠有效減少細(xì)碎暗斑的產(chǎn)生，分割出SAR影像中的暗斑；經(jīng)過與其他分割算法的對比，顯示了不錯(cuò)的分割效果。主要結(jié)論如下：

1)發(fā)展的方法能夠得到閉合的暗斑區(qū)域邊緣曲線，且可以有效減少細(xì)碎暗斑的產(chǎn)生；

2)Canny算子邊緣檢測方法難以得到閉合的暗斑區(qū)域邊緣，且易受斑點(diǎn)噪聲的影響而產(chǎn)生錯(cuò)誤的邊緣檢測結(jié)果；

3)OTSU和FCM方法容易受斑點(diǎn)噪聲的影響而產(chǎn)生細(xì)碎的暗斑，F(xiàn)CM的效果優(yōu)于OTSU，但也需要更多的運(yùn)算時(shí)間；

4)C-V水平集算法易受斑點(diǎn)噪聲的影響而產(chǎn)生細(xì)碎斑塊，且運(yùn)算時(shí)間較長。

參考文獻(xiàn)(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]. 海洋環(huán)境科學(xué), 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]. 智能系統(tǒng)學(xué)報(bào), 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. 李衛(wèi)斌, 田俊華, 李宗領(lǐng). 基于改進(jìn)Canny算子的SAR圖像邊緣檢測[J]. 咸陽師范學(xué)院學(xué)報(bào), 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. 湖廣, 李娟, 黃本雄. 結(jié)合空間信息的模糊C均值聚類圖像分割算法[J]. 計(jì)算機(jī)與數(shù)字工程, 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. 石立堅(jiān). SAR及MODIS數(shù)據(jù)海面溢油監(jiān)測方法研究[D]. 青島: 中國海洋大學(xué), 2008.