弱交互式水邊線提取新算法

周良芬，何建農(nóng)

（福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108）

0 引 言

海岸線是海岸和陸地的交界線。實(shí)現(xiàn)海岸線的動(dòng)態(tài)監(jiān)測(cè)，對(duì)于海域管理使用具有重大意義［1］。目前熱門的遙感圖像處理技術(shù)為檢測(cè)海岸線的動(dòng)態(tài)變化提供了方便而重要的途徑。從遙感影像上獲取的數(shù)據(jù)一般是水邊線，即某一時(shí)刻起伏不平的海面與陸地的瞬時(shí)交接線，必須對(duì)水邊線進(jìn)行修正，最終才能獲得真正的海岸線［1］。因此作為海岸線自動(dòng)提取的前提和必要步驟，水邊線提取算法的研究是十分重要的。

水邊線提取實(shí)質(zhì)上是遙感圖像邊緣的提取，關(guān)鍵技術(shù)是實(shí)現(xiàn)海陸分離。除目視解譯和多光譜分類外，國內(nèi)外學(xué)者相繼提出了多種方法，如閾值分割法［2］、水平集法［3］、主動(dòng)輪廓模型法［4－5］、數(shù)學(xué)形態(tài)學(xué)法［6］、小波變換［2，7－8］等方法，但這些方法具有局限性。傳統(tǒng)的閾值方法對(duì)噪聲影響敏感，對(duì)水邊線的陰影也缺乏足夠的辨識(shí)能力；水平集方法和主動(dòng)輪廓模型法往往陷入非全局最優(yōu)影響分割結(jié)果，而且時(shí)效性差；近年來發(fā)展起來的小波變換為水邊線的提取提供了新思路，但其缺陷是當(dāng)沿岸海域有干擾物時(shí)，小波變換會(huì)把非邊緣點(diǎn)提取出來，影響檢測(cè)結(jié)果［7］。

交互式分割算法因其充分利用先驗(yàn)知識(shí)而引起研究人員的廣泛關(guān)注。隨機(jī)游走算法［9－11］是近年來流行的一種弱交互式無監(jiān)督圖像分割方法，不僅交互少、抗噪聲能力強(qiáng)，而且可以很好地檢測(cè)出弱邊界。針對(duì)海陸遙感圖像存在噪聲、弱邊界、干擾物等局限性，本文融合色彩和梯度特征，利用l2－范數(shù)與高斯權(quán)函數(shù)相結(jié)合描述像素之間的相似性，并采用隨機(jī)游走算法實(shí)現(xiàn)了海陸的分離以及水邊線的提取。

1 隨機(jī)游走算法

隨機(jī)游走算法將輸入圖像看做由一些數(shù)量的邊和頂點(diǎn)構(gòu)成的離散無向圖。給定一個(gè)無向圖G＝（V，E，W），其中v∈V 是節(jié)點(diǎn)，e∈E?V×V 是邊，Wij∈W 是節(jié)點(diǎn)vi和vj之間的權(quán)值，反映相鄰像素之間的差異或相似度，表示隨機(jī)游走者沿著這條邊行走的可能性。如果兩點(diǎn)不相鄰，則權(quán)重Wij為0，表示隨機(jī)游走者將不沿這條邊行走。

平面上隨機(jī)游走求解概率問題與Dirichlet積分求解的解法一樣，在文獻(xiàn)［9，11］中已經(jīng)得到證明和應(yīng)用，其實(shí)質(zhì)是利用Dicichlet的邊界條件計(jì)算所有未標(biāo)號(hào)像素隨機(jī)游走到標(biāo)號(hào)像素的電勢(shì)值，并按最大概率原則對(duì)像素進(jìn)行分類，實(shí)現(xiàn)圖像的分割。

圖1給出了L1、L2、L3這3個(gè)標(biāo)記種子點(diǎn)的隨機(jī)游走算法的原理圖。例如某未標(biāo)記點(diǎn)首次到達(dá)L1、L2、L3標(biāo)記點(diǎn)的電勢(shì)值分別是0.24，0.47和0.29，此3者電勢(shì)值之和為1，則此未標(biāo)記點(diǎn)屬于最大電勢(shì)值0.47所對(duì)應(yīng)的標(biāo)簽L2；其他節(jié)點(diǎn)類似地得到相應(yīng)標(biāo)簽，分割結(jié)果如圖1（a）所示。

圖1 隨機(jī)游走算法原理

傳統(tǒng)的隨機(jī)游走算法僅考慮圖像中像素的灰度信息，目標(biāo)輪廓易受背景干擾，容易抑制隨機(jī)游走者沿著某些與標(biāo)記點(diǎn)灰度接近的邊行走，造成錯(cuò)分與漏分，因此圖像分割不夠精準(zhǔn)。

2 基于隨機(jī)游走的水邊線提取改進(jìn)算法

圖像的邊緣是圖像局部特征的不連續(xù)，表現(xiàn)為圖像灰度級(jí)的突變，紋理結(jié)構(gòu)的突變或者彩色的變換等［12］。在水邊線附近，垂直于水邊線走向的像元顏色變化較大，而沿著水邊線走向的像元顏色變化較為平緩，表現(xiàn)出邊緣的特性。色彩特征變化大的處于海域與陸地的交界處的可能性也大。海陸的交界處就是水邊線所在之處，因此，可以利用海陸圖像色彩及顏色突變處的信息來提取水邊線。改進(jìn)算法的基本思想：融合顏色和梯度信息對(duì)海陸的色彩特征進(jìn)行充分描述。由于梯度信息在不同光照下具有不錯(cuò)的穩(wěn)定性，同時(shí)可以很好地反映鄰域像素間顏色的突變情況，因此采用色彩和梯度特征進(jìn)行圖像分割是一種有效的分割方法。

改進(jìn)的水邊線弱交互式提取算法的具體步驟如下：

步驟1 改進(jìn)權(quán)值，建立加權(quán)圖。

經(jīng)典的高斯權(quán)值函數(shù)，其定義如下

式中：gi——像素點(diǎn)i的灰度值，β——自由參數(shù)。在使用式（1）之前，需要先歸一化（gi－gj）2。

本文使用的是l2－范數(shù)的高斯權(quán)重函數(shù)，將色彩和梯度特征引入隨機(jī)游走算法中，其定義如下

其中

Sobel濾波器對(duì)于噪聲具有平滑作用，能夠提供較為精確的邊界信息，是一種較為常用的邊緣提取算法［13］。所以ei、ej是采用Sobel算子計(jì)算的彩色圖像的梯度幅值。Sobel算子也是一種梯度幅值［14］，對(duì)應(yīng)輸入圖像I，其梯度計(jì)算公式為

式中：Ex、Ey——像素的水平、垂直方向的梯度值。

式中：Hx、Hy——水平方向和垂直方向的Sobel濾波器。本文將海陸彩色圖像的像素分解為R、G、B這3個(gè)基本顏色分量，然后通過對(duì)3個(gè)分量分別進(jìn)行邊緣檢測(cè)的模板運(yùn)算得到：ei＝（eRi，eGi，eBi），ej＝（eRj，eGj，eBj）。

步驟2 得到加權(quán)圖后，根據(jù)遙感圖像的不同特點(diǎn)，把海域當(dāng)作目標(biāo)，陸地當(dāng)作是背景，手動(dòng)輸入目標(biāo)和背景相應(yīng)標(biāo)記集合VM。

步驟3 求解組合Dirichlet問題。根據(jù)文獻(xiàn)［9］給出組合拉普拉斯矩陣的定義式中：Lij——矩 陣L的 第（i，j）個(gè) 元 素，且 組 合Dirichlet積分公式為

將無向圖G的頂點(diǎn)集分成互補(bǔ)的兩個(gè)子集VM、VU，則VM∪VU＝V，VM∩VU＝Φ，其中VM表示已標(biāo)記的節(jié)點(diǎn)、VU表示未標(biāo)記的節(jié)點(diǎn)。將L和x 中的點(diǎn)按照已經(jīng)標(biāo)記和未標(biāo)記的順序分解為對(duì)角分塊陣形式，則式（7）分解為式（8）

式中：xM、xU——種子點(diǎn)（海陸上的標(biāo)簽點(diǎn)）、非種子點(diǎn)的隨機(jī)游走概率值，即電勢(shì)值。

滿足式（9）的臨界條件時(shí)，D［xU］達(dá)到最小值

對(duì)于1個(gè)標(biāo)記點(diǎn)s，組合Dirichlet問題可以通過求解式（11）得到

對(duì)于所有的標(biāo)記點(diǎn)，則通過求解式（12）得到

式中：X的K 列即為各個(gè)xs，M的列即為各個(gè)ms。因此，有K－1個(gè)稀疏線性系統(tǒng)需要求解，K為標(biāo)號(hào)類別總數(shù)。本文提取水邊線的關(guān)鍵，就是實(shí)現(xiàn)海陸分離，就是把相應(yīng)的標(biāo)記分成兩類，所以其標(biāo)號(hào)類別總數(shù)為2。

步驟4 求解的結(jié)果就是每個(gè)節(jié)點(diǎn)Vi對(duì)應(yīng)的電勢(shì)值，取電勢(shì)值最大的標(biāo)記像素maxs（xsi）作為其所屬目標(biāo)，最終實(shí)現(xiàn)海陸分離，提取到水邊線。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本文選取了兩幅海陸遙感圖像，將所提算法（random walks algorithm based on color and gradient feature，CGRW）的仿真結(jié)果與基于小波多分辨率算法（based on wavelet multi－resolution algorithm，WMR）［8］和傳統(tǒng)隨機(jī)游走算法（random walks for image segmentation，RW）［9］的水邊線提取結(jié)果進(jìn)行比較，其中參數(shù)β的值選取為90。

圖2（a）A海海域、陸地亮度、顏色變化較為均一，地形起伏小，坡度較緩，變化較大的出現(xiàn)在海陸交界處。陸地左上方出現(xiàn)較大面積的植被，海域右上方因?yàn)楦”绊憣?dǎo)致海陸顏色比較接近，邊緣較模糊，其右下方出現(xiàn)浪潮。

圖2 A 海水邊線提取結(jié)果

由圖2（b）、圖2（c）、圖2（d）可以看出WMR 算法雖然可以提取出水邊線的大致輪廓，但是邊緣出現(xiàn)了較嚴(yán)重的誤檢或漏檢情況。由尺度1、2、3 對(duì)比可以知，小尺度，描繪了豐富的細(xì)節(jié)，但增加了噪聲；大尺度抑制了部分細(xì)節(jié)，突出了水邊線信息，但水邊線也出現(xiàn)不連續(xù)現(xiàn)象。

由圖2（e）、圖2（g）可以看出RW 算法提取的瞬時(shí)水邊線很準(zhǔn)確，CGRW 算法提取到的水邊線也很好地停留在弱邊緣上。RW 算法、CGRW 算法對(duì)于排污物、植被、海浪等干擾物體現(xiàn)了很好的魯棒性。

圖3（a）B 海海域、陸地亮度、顏色層次較豐富，地形起伏較大，坡度較陡。而且沿岸的陸地被大量的植被覆蓋著，左側(cè)水邊線的出口處出現(xiàn)懸浮泥沙現(xiàn)象。

圖3（b）、圖3（c）、圖3（d）可以看出受植被、懸浮泥沙的影響，WMR 算法提取了過多的干擾信息，水邊線出現(xiàn)過分誤提取或漏提取情況。

圖3（e）中RW 算法對(duì)于B海左側(cè)的水邊線出現(xiàn)部分誤提取和漏提取，對(duì)于B 海的右下方出現(xiàn)過分提取現(xiàn)象，原因在于它只采用單一灰度信息來描述節(jié)點(diǎn)間的相似性。

圖3 B海水邊線提取結(jié)果

如圖3（g）所示，與WMR 算法、傳統(tǒng)RW 算法相比較，對(duì)于背景比較復(fù)雜的、顏色較豐富的水邊線，CGRW算法充分考慮到圖像的色彩和梯度信息，而且新權(quán)重更準(zhǔn)確地描述了色彩的相對(duì)變化，提取到的水邊線更加平滑、完整，跟現(xiàn)實(shí)輪廓擬合得更好。

由圖2A 海和圖3B 海的水邊線提取結(jié)果可以看出，WMR 算法提供了過于豐富的細(xì)節(jié)信息，而隨機(jī)游走算法對(duì)于斑點(diǎn)噪聲、波浪泡沫、植被、懸浮泥沙等干擾物具有較強(qiáng)的免疫力。特別對(duì)于陸地地形比較復(fù)雜，亮度變化層次比較豐富的遙感圖像，本文改進(jìn)的隨機(jī)游走比基于小波多分辨率算法和傳統(tǒng)隨機(jī)游走算法刻畫的細(xì)節(jié)信息更準(zhǔn)確，提取的水邊線更精準(zhǔn)。

4 結(jié)束語

本文算法利用色彩和梯度特征向量建立了節(jié)點(diǎn)間的連接權(quán)，不僅刻畫海陸圖像像素間的色彩相似性，而且反映了色彩的突變情況，更加全面地描述了圖像的細(xì)節(jié)信息，從而提取到準(zhǔn)確、清晰的水邊線，對(duì)水邊線進(jìn)行潮位校正，便可以提取出真正意義上的海岸線。實(shí)驗(yàn)表明：本文算法對(duì)噪聲、外來干擾物具有一定的魯棒性，而且可以很好地識(shí)別出水邊線的弱邊緣。

［1］SHEN Jiashuang，ZHAI Jingsheng，GUO Haitao.Study on coastline extraction technology［J］.Hydrographic Surveying and Charting，2009，29（6）：74－77（in Chinese）.［申家雙，翟京生，郭海濤.海岸線提取技術(shù)研究［J］.海洋測(cè)繪，2009，29（6）：74－77.］

［2］ZHANG Peng，LI Hongping.Sea boundary extraction in SAR satellite images based on stationary wavelet transform［J］.Computer Development ＆Applications，2010，23（5）：30－32（in Chinese）.［張鵬，李洪平.基于平穩(wěn)小波變換的SAR 圖像海岸線提?。跩］.電腦開發(fā)與應(yīng)用，2010，23（5）：30－32.］

［3］GUO Zhenbo.Multiphase image segmentation based on variational level set methods［D］.Qingdao：Ocean University of China，2008（in Chinese）.［郭振波.基于變分水平集方法的多相圖像分割研究［D］.青島：中國海洋大學(xué)，2008.］

［4］SHEN Qi，WANG Chengyi，ZHAO Bin.Automatic waterline extraction in VHR imagery using geometric active contour model［J］.Journal of Fudan University，2012，51（1）：77－82（in Chinese）.［沈琦，汪承義，趙斌.幾何活動(dòng)輪廓模型用于高分辨率遙感影像海岸線自動(dòng)提取［J］.復(fù)旦學(xué)報(bào)，2012，51（1）：77－82.］

［5］Huang K H，Zhang J.A costline detection using SAR images based on the local statistical active contour model［J］.Journal of Remote Sensing，2011，15（4）：737－749.

［6］ZHANG Yufang.Water area of remote sensing image edge detection method based on morphology top－h(huán)at and bottom－h(huán)at［J］.Urban Geotechnical Investigation ＆Surveying，2009，24（1）：80－82（in Chinese）.［張玉方.基于形態(tài)學(xué)高低帽變換的遙感影像水域邊緣檢測(cè)算法［J］.城市勘測(cè)，2009，24（1）：80－82.］

［7］MA Xiaofeng.The means of withdrawing coastline by remote sensing［D］.Dalian：Dalian Maritime University，2007（in Chinese）.［馬小峰.海岸線衛(wèi)星遙感提取方法研究［D］.大連：大連海事大學(xué)，2007.］

［8］HAN Zhen，GUO Yongfei.Waterside line information extraction of tidalflat at the yangtze river estuary by wavelet multi－resolution analysis［J］.Marine Sciences，2011，35（7）：67－70（in Chinese）.［韓震，郭永飛.基于小波多分辨率分析提取長(zhǎng)江口淤泥質(zhì)潮灘水邊線［J］.海洋科學(xué)，2011，35（7）：67－70.］

［9］Grady L.Random walks for image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（11）：1768－1783.

［10］Sinop A K，Grady L.A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm［C］／／Proceeding of the 11th IEEE International Conference on Computer Vision，Rio de Janciro，2007：1－8.

［11］Couprie C，Grady L，Najman L，et al.Power watersheds：A new image segmentation framework extending graph cuts，random walker and optimal spanning forest［C］／／France：Proceeding of the 12th IEEE International Conference on Computer Vision，2009：731－738.

［12］XIE Lei.Edge detection of remote sense image based on the cloud models［D］.Chongqing：Chongqing University of Posts and Telecommunications，2007（in Chinese）.［謝磊.基于云模型的遙感圖像邊緣檢測(cè)［D］.重慶：重慶郵電大學(xué)，2007.］

［13］ZHANG Chaoyang.A study of coastline extraction in RS image and its change detection technology［D］.Zhengzhou：PLA Information Engineering University，2006（in Chinese）.［張朝陽.遙感影像海岸線提取及其變化檢測(cè)技術(shù)研究［D］.鄭州：中國人民解放軍信息工程大學(xué)，2006.］

［14］Rafael C Gonzalez，Richard E Woods.Digital image processing［M］.2nd ed.RUAN Qiuqi，RUAN Yuzhi，transl.Beijing：Publishing House of Electronics Industry，2007（in Chinese）.［Gonzalez R C，woods R E.數(shù)字圖像處理［M］.2版.阮秋琦，阮宇智，譯.北京：電子工業(yè)出版社，2007.］