基于改进自适应降雪模型的随机游走图像分割

朱强

浙江传媒学院 教育技术中心，杭州 310018

基于改进自适应降雪模型的随机游走图像分割

朱强

浙江传媒学院 教育技术中心，杭州 310018

图像作为计算机视觉可视化处理对象之一，是近年来研究较多的课题，例如气象图，遥感监测图像，二维码等，这些图像中都包含丰富的内容，是信息的承载。图像作为信息的载体，它的前景与背景这些直观特征更为人所熟悉，有时为了对一块图像中的某一小块进行重点分析，需要将小块图像从原图像中无损失地提取出来，一般而言，小块图像并不是规则的，对于边缘不规则的图像提取，涉及到图像分割技术。图像分割作为图像分析的关键步骤，在图像处理中占据重要地位[1]。

图像分割并不是简单的图像裁剪，在图像分割过程中，对图像分割的边缘处理尤其需要注意，因为边缘裁剪过多，会引入噪声，而裁剪过少，会丢失图像信息[2]。因此，如何在图像分割过程中，既能保持原图像特征，又尽可能少地引入噪声，是图像分割需要重点解决的问题。当前也有很多学者在图像分割方面做了一些研究，基本都是算法优化，没有一个通用方法在抗噪性能上和保留细节上都达到最佳，比如采用模糊聚类思想实现图像的分割[3-5]，文献[3]用的是模糊C聚类均值算法，文献[4-5]采用FCM算法、模糊聚类算法在复杂图像分割上能够达到一定的效果，但效果一般；文献[6]是采用Meanshift在遥感图像中的应用；而文献[7]则是自适应的随机游走图像分割，该算法分割效果较好，但仍需改进。

基于上述分析，提出了一种基于自适应降雪模型的随机游走图像分割算法，核心是将图像模拟为地表起伏的地面，而且做类似于降雪过程的地标曲面变化模拟。因为降雪模型是根据地表情况形成的自适应模型，可以很好地应用到图像分割，有效降低边缘噪声和保证图像分割的自然和平滑度。降雪模型只是对图像分割的边缘进行优化处理，还需结合随机游走算法，完成图像分割，实验结果表明，采用该模型完成的图像分割更加精确。

1 相关工作

1.1 积雪表面效应

积雪表面效应直接影响了视觉，物体上的积雪会对物体本身的图像信息进行不同程度地改变，首先，积雪会掩盖物体表面部分细节，如果从整体来提取该物体的图像时，将会降低物体边缘提取的难度，更凸显了物体的整个轮廓；其次，积雪效应可有效弱化物体之间的映衬关系，消除不必要的阴影遮挡，可以有效去除噪声；最后，降雪在对细节进行模糊的同时，对大目标轮廓起凸显作用。

降雪模型的表面效应与降雪时间长短有一定关系，而在做图像分割处理时，也必须考虑这一点，降雪大小系数设置过程中，既要保证降雪时间，尽可能最大地抑制噪声，又要防止降雪时间过长，将有用信息覆盖，因此需要做一个权衡，降雪大小权重系数应设置合理。而这个降雪系数，在仿真过程中是由降雪的次数来限制的。

1.2 基本降雪模型

降雪效应可以改变地表轮廓，仿真自适应的地表曲面，如何采用数学的方法来将地表曲线进行量化，是降雪模型建模必须解决的问题，本文采用高斯核函数来对降雪地表变化进行量化。

下面，将对高斯核函数的基本算法进行相应改进，以便更好地满足实际图像分割处理，为了能够更直观地描述问题，采用简图来描述算法核心思想，如图1所示。标准图像经过拉伸、旋转、尺度变换处理可以实现此变换下的任何图像，任一图像特征可以由标准图像参数、拉伸参数Λi、旋转参数Uθi及尺度变换参数γi共同来表示[8]。正因为这样，任一图像特征均可以采用自适应高斯核来完成。

图1 传统核函数的改进

如图2，描述了不同核函数形状，其中（a）是传统高斯核，描述的是图像中平坦区域，（b）表示纹理区，图像变小后，丰富了图像；（c）表示弱边缘区，（d）表示强边缘区，（e）表示斜边缘区。为了更直观地表示这5个区的特征，采用经典图像分析图3作简要介绍。

图2 自适应的曲面进化核

根据上文描述的变换过程，提出了自适应高斯核函数：

其中σ表示全局平滑因子，C0是基于局部不同灰度值的协方差矩阵，为了简化计算，对C0进行特征值分解：

图3 曲面自适应示意图

2 改进的图像分割算法设计

随机游走是一种基于扩散策略的网络生成方法，随机游走过程是在整个原始网络中放置一个活跃标签，活跃标签的游走过程即为随机游走过程[9-11]。活跃标签经过的节点即为网络重建的节点，随机游走策略在选取行走路由的时候，不是简单地根据当前节点与之相连的节点中随机选取下一个节点，而是根据节点网络属性，比如节点的度，选择是继续下一跳还是退回原始节点，即跳出策略，有效避免局部陷入，同时也需要考虑原始网络遍历不全的问题，防止对整个网网络抽样不均匀。

联合狄利克雷问题与随机游走转移概率的解在边界条件固定时是有可以比拟之处，在此，借助联合狄利克雷问题对随机游走算法的求解过程进行详细描述[12-14]：

给定区域Z上的狄利克雷积分为：

随机游走活跃标签从非标记点出发第一次到达标记点的概率等于该标记点在边界 Γ条件下的狄利克雷问题的解，其中u(i，j)为调和函数，边界条件如式（3）所示：

整个问题的求解过程即为调和函数u(i，j)的最小值求解过程。

在映射图中定义联合拉普拉斯矩阵，如式（4）所示：

Lij的值由节点vi与vj共同决定，di为节点vi的度。顶点间的关联矩阵，即图G的m×n条边的定义：

由式（11）得，关联矩阵由边eij和节点vk共同决定，图中所有的eij可以是任意一个指定的方向。一般称 A为联合梯度算子，AT为联合散度算子。

定义一个m×m大小的对角构造矩阵C，它的对角线上的值对应映射图的边的权值大小，即

在连续的前提下，各向同性的联合拉普拉斯矩阵可以分解为联合散度算子和联合梯度算子的乘积，即L=ATA。这个构造矩阵C可以理解为在向量上一个加权内积大小的度量，从这个意义上来说，通过L=ATCA，即当C=I时，L=ATA。

在已经固定标记点的值的前提下，求解非标记点到达标记点的概率值。公式（7）可以改写为：

由K-1个线性方程求解出非标记点到K个标记点的概率值大小，由 ys可以得出X有K列，且由ms可以得出M的列数，由电路原理可知，每个节点的概率和为1。

在获得每个未标记点vi到标记点的K个概率后，逐个比较它们的大小，以最大转移概率()为准则来实现图像的分割[12]。

传统的随机游走使用了高斯函数来确定两个像素点组成的边的权值大小，即

在选择权值函数时候，对梯度信息进行了运用，即

式中，gi是经过降雪模型处理后的图像像素点i灰度值，hi是对应的梯度值，β1，β2是改进算法的自由参数。

通过以上可得，融合传统的随机游走图像分割算法与自适应降雪模型的特性，提出了新的图像分割算法，具体算法实现流程如图4所示。

图4 基于降雪模型的随机游走图像分割流程图

3 实例仿真

为了评估所提出的基于降雪模型的改进随机游走算法的性能，运用Matlab及所提算法对人工模拟图像和真实图像分别进行实例仿真，并与NCut和随机游走等分割算法进行性能比较。

3.1 虚拟图像仿真

首先，用Matlab模拟一条有缺口的直线图像，用自适应降雪模型的随机游走算法来实现图像分割，验证该算法对有缺失图像的分割情况。该模拟原始图像如图5（a）所示，（b）为经过降雪模型滤波后的图像的梯度图像，（c）是采用归一化分割后的图像，（d）为传统的随机游走图像，（e）为所提算法取得的分割图像。从图中，可以明显对比本文算法对缺失图像的还原弥补功能更强，（c）中的图像分割线与直线不能重合，（d）中的分割在缺失部分有一小部分突出，而（e）中的图像弥补了原始图像的缺口，并且分割线部分非常平滑，突起部分可忽略不计，所提算法融合了传统随机游走及自适应降雪模型，传统随机游走弥补了原始图像的缺口，降雪模型中采用自适应高斯核函数对降雪地表变化进行量化，从而使分割线保持平滑。

图5 虚拟图分割结果比较（（a）～（e）为未加噪声，（f）～（j）为加入高斯噪声）

为了对所提算法的抗噪性能进行分析对比，在虚拟图像图5（a）中加入高斯噪声，其中均值和方差分别为0和0.01，如图5（f）所示。相应的，图5（h）、（i）、（j）是加入噪声后的图像分别采用NCut、传统随机游走和所提算法取得的分割效果，从实验结果可以明显看出，基于自适应的降雪模型随机游走算法在抗噪声方面比其他两种方法表现出了更好的性能，而且经实验证明，噪声越强，所提算法的优越性更明显。

3.2 真实图像仿真

实验选用了飞机图像、人物图像和自行拍摄的水杯药瓶图像为实验对象，为了更好地说明所提算法的通用性，其中前两幅图像取自于公共数据库，第三幅是研究者自己拍摄的生活中的图像。如图6所示，一共分为三组，每一组有5个图像，分别为：原始图像、梯度图像、NCut分割图像、传统随机游走分割图像、所提改进方法生成图像。

图6中第1行和第2行的图像均来自于berkeley分割数据库，在Matlab仿真中，对原始图像加入了均值为0，方差为0.000 5的高斯噪声的图像，仿真结果可得，图6（c）NCut分割效果一般，图6（d）有一定的分割结果，但第1行图像出现了漏分割现象，所提分割算法对整体图像分割完好。

图6中第3行为自定义图像，虽然图像背景简单，但是两个物体之间有一定的阴影，为两个物体的图像分割增加了一定量难度。如图6（c）所示，NCut分割效果差，左边的杯子分割效果不明显，而且将药瓶子当成了背景而没有识别出来，图6（d）分割算法右边物体分割效果较差，有毛刺出现。所提算法分割效果优势较明显。

4 结语

为了降低分割边缘噪声对图像分割的影响，提出了一种自适应降雪模型的随机游走图像分割算法，经过实验证明，通过对传统随机游走与降雪模型相结合，很好地提高了图像分割性能，特别是在图像分割的边缘处理上，既很好地保持了图像原来的特性，又很好地抑制噪声，具有一定的应用前景。

后续研究主要是对算法性能进行优化，进一步提高降雪模型自适应参数控制的精确性，增加对复杂图像的分割完整性。

图6 真实图分割结果比较

[1]吴一全，郝亚冰，吴诗婚，等.基于KFCM和改进CV模型的海面溢油SAR图像分割[J].仪器仪表学报，2012，33（12）：2812-2818.

[2]Khan A，Ullah J，Jaffar M A，et al.Color image segmentation：a novel spatial fuzzy genetic algorithm[J].Signal，Image and Video Processing，2012：1-11.

[3]Liu F.The new image segmentation algorithm using adaptive evolutionary programming and fuzzy c-means clustering[C]// SPIE，2011，8056.

[4]李旭超，刘海宽，王飞，等.图像分割中的模糊聚类方法[J].中国图象图形学报，2012，17（4）：447-458.

[5]依玉峰，高立群，郭丽.改进FCM在交互式图像分割中的应用[J].中国图象图形学报，2012，17（3）：342-348.

[6]周家香，朱建军，梅小明，等.多维特征自适应MeanShift遥感图像分割方法[J].武汉大学学报：信息科学版，2012，37（4）：419-422.

[7]依玉峰，高立群，程伟，等.自适应随机游走图像分割算法[J].东北大学学报：自然科学版，2011，32（8）：1092-1096.

[8]王成恩，黄章俊.基于高斯函数和信赖域更新策略的Kriging响应面法[J].计算机集成制造系统，2011，17（4）：740-746.

[9]钭斐玲，胡延庆，黎勇.空间网络上的随机游走[J].物理学报，2012，61（17）.

[10]王丽莎，张绍武，林鸿飞.基于项目和标签的随机游走个性化信息推荐模型[J].情报学报，2012，31（3）：289-296.

[11]依玉峰，高立群，郭丽.基于Mean Shift随机游走图像分割算法[J].计算机辅助设计与图形学学报，2011，23（11）：1875-1881.

[12]王芳梅，范虹，王凤妮.水平集在图像分割中的应用研究[J].计算机应用研究，2012，29（4）.

[13]袁和金，王翠茹.人体行为识别的Markov随机游走半监督学习方法[J].计算机辅助设计与图形学学报，2011，23（10）：1749-1757.

[14]郑伟，王朝坤，刘璋，等.一种基于随机游走模型的多标签分类算法[J].计算机学报，2010，33（8）：1418-1426.

ZHU Qiang

Educational Technology Center,Zhejiang University of Media and Communications,Hangzhou 310018,China

In order to improve accuracy of image segmentation,reduce the effect of noise on the cutting edge of image segmentation as much as possible,a new image segmentation method based on the model of the snowfall is proposed.Snowfall model and snow surface effect are analyzed in detail,the snow model is applied to image segmentation with strong adaptability,and it mixs the traditional random walk image segmentation algorithm with adaptive snow model characteristics,generates a new algorithm,makes performance simulation using virtual and real images algorithm,the results show that the image segmentation performance is better than the common NCut and the traditional random walk algorithm for image segmentation,and it has certain research value.

image segmentation;snowfall model;random walk;Gauss kernel function

为了提高图像分割的准确度，尽可能降低分割边缘噪声对图像分割的影响，提出了一种基于降雪模型的图像分割方法。对降雪模型及积雪表面效应做了详细分析，得出降雪模型运用于图像分割具有较强的适应性；接着在传统的随机游走图像分割算法中加入了自适应降雪模型的特性，生成新的算法；运用虚拟图像和真实图像进行算法性能实例仿真，结果表明，该算法的图像分割性能优于常见的NCut和传统随机游走图像分割算法，具有一定的研究价值。

图像分割；降雪模型；随机游走；高斯核函数

A

TP399

10.3778/j.issn.1002-8331.1307-0108

ZHU Qiang.Random walking image segmentation based on improved adaptive snowfall model.Computer Engineering and Applications,2013,49（23）：127-131.

浙江省自然科学基金项目（No.Y1100314）。

朱强（1964—），男，副教授，主要研究领域为图形图像处理、并行语法分析。E-mail：zhuqiang_2013@126.com

2013-07-09

2013-08-30

1002-8331（2013）23-0127-05

book=131,ebook=136