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

周良芬，何建農

（福州大學 數學與計算機科學學院，福建 福州 350108）

0 引 言

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

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

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

1 隨機游走算法

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

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

圖1給出了L1、L2、L3這3個標記種子點的隨機游走算法的原理圖。例如某未標記點首次到達L1、L2、L3標記點的電勢值分別是0.24，0.47和0.29，此3者電勢值之和為1，則此未標記點屬于最大電勢值0.47所對應的標簽L2；其他節點類似地得到相應標簽，分割結果如圖1（a）所示。

圖1 隨機游走算法原理

傳統的隨機游走算法僅考慮圖像中像素的灰度信息，目標輪廓易受背景干擾，容易抑制隨機游走者沿著某些與標記點灰度接近的邊行走，造成錯分與漏分，因此圖像分割不夠精準。

2 基于隨機游走的水邊線提取改進算法

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

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

步驟1 改進權值，建立加權圖。

經典的高斯權值函數，其定義如下

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

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

其中

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

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

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

步驟2 得到加權圖后，根據遙感圖像的不同特點，把海域當作目標，陸地當作是背景，手動輸入目標和背景相應標記集合VM。

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

將無向圖G的頂點集分成互補的兩個子集VM、VU，則VM∪VU＝V，VM∩VU＝Φ，其中VM表示已標記的節點、VU表示未標記的節點。將L和x 中的點按照已經標記和未標記的順序分解為對角分塊陣形式，則式（7）分解為式（8）

式中：xM、xU——種子點（海陸上的標簽點）、非種子點的隨機游走概率值，即電勢值。

滿足式（9）的臨界條件時，D［xU］達到最小值

對于1個標記點s，組合Dirichlet問題可以通過求解式（11）得到

對于所有的標記點，則通過求解式（12）得到

式中：X的K 列即為各個xs，M的列即為各個ms。因此，有K－1個稀疏線性系統需要求解，K為標號類別總數。本文提取水邊線的關鍵，就是實現海陸分離，就是把相應的標記分成兩類，所以其標號類別總數為2。

步驟4 求解的結果就是每個節點Vi對應的電勢值，取電勢值最大的標記像素maxs（xsi）作為其所屬目標，最終實現海陸分離，提取到水邊線。

3 仿真實驗與結果分析

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

圖2（a）A海海域、陸地亮度、顏色變化較為均一，地形起伏小，坡度較緩，變化較大的出現在海陸交界處。陸地左上方出現較大面積的植被，海域右上方因為浮冰影響導致海陸顏色比較接近，邊緣較模糊，其右下方出現浪潮。

圖2 A 海水邊線提取結果

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

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

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

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

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

圖3 B海水邊線提取結果

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

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

4 結束語

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

［1］SHEN Jiashuang，ZHAI Jingsheng，GUO Haitao.Study on coastline extraction technology［J］.Hydrographic Surveying and Charting，2009，29（6）：74－77（in Chinese）.［申家雙，翟京生，郭海濤.海岸線提取技術研究［J］.海洋測繪，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）.［張鵬，李洪平.基于平穩小波變換的SAR 圖像海岸線提取［J］.電腦開發與應用，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］.青島：中國海洋大學，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）.［沈琦，汪承義，趙斌.幾何活動輪廓模型用于高分辨率遙感影像海岸線自動提取［J］.復旦學報，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－hat and bottom－hat［J］.Urban Geotechnical Investigation ＆Surveying，2009，24（1）：80－82（in Chinese）.［張玉方.基于形態學高低帽變換的遙感影像水域邊緣檢測算法［J］.城市勘測，2009，24（1）：80－82.］

［7］MA Xiaofeng.The means of withdrawing coastline by remote sensing［D］.Dalian：Dalian Maritime University，2007（in Chinese）.［馬小峰.海岸線衛星遙感提取方法研究［D］.大連：大連海事大學，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）.［韓震，郭永飛.基于小波多分辨率分析提取長江口淤泥質潮灘水邊線［J］.海洋科學，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）.［謝磊.基于云模型的遙感圖像邊緣檢測［D］.重慶：重慶郵電大學，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）.［張朝陽.遙感影像海岸線提取及其變化檢測技術研究［D］.鄭州：中國人民解放軍信息工程大學，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.數字圖像處理［M］.2版.阮秋琦，阮宇智，譯.北京：電子工業出版社，2007.］