弱交互式水边线提取新算法

周良芬，何建农

（福州大学 数学与计算机科学学院，福建 福州 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.］