基于随机游走策略改进的降雪模型图像分割方法*

陈杏环，闫海煜

(1.重庆电子工程职业学院计算机学院，重庆401331;2.重庆电子工程职业学院通信学院，重庆401331)

基于随机游走策略改进的降雪模型图像分割方法*

陈杏环1*，闫海煜2

(1.重庆电子工程职业学院计算机学院，重庆401331;2.重庆电子工程职业学院通信学院，重庆401331)

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

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

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

图像分割并不是简单的图像裁剪，在图像分割过程中，对图像分割的边缘处理尤其需要注意，因为边缘裁剪过多，会引入噪声，而裁剪过少，会丢失图像信息［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 自适应的曲面进化核

图3 曲面自适应示意图

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

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

其中Uθ0、B0、σ0分别表示旋转矩阵，拉伸矩形阵和调整核的大小。梯度矩阵如下定义:

其中U0N0VT0是M0的分解，N0是二阶对角矩阵，为起关键作用的方向值，V0，V0=［v1，v2］T是一个定义方向的正交矩阵，其中角度值为:

旋转参数σ0是根据起决定作用的梯度方向定义的:

其中η'为拉伸的调节因子。

选择因子φ0为:

其中η″选择调节因子。

1.3 改进算法设计

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

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

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

随机游走活跃标签从非标记点出发第1次到达标记点的概率等于该标记点在边界Γ条件下的狄利克雷问题的解，其中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)可以改写为:

对D［xU］求关于yU进行微分，可得式(10):

Q(vj)=s，∀vj∈VM，其中s∈Ζ，0＜s≤K，再为所有在vj∈VM的点定义一个|VM|×1大小的矩阵

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

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

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

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

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

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

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

2 实例仿真

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

2.1 虚拟图像仿真

首先，用MATLAB模拟一条有缺口的直线图像，用自适应降雪模型的随机游走算法来实现图像分割，验证该算法对有缺失图像的分割情况。该模拟图像如图5(a)所示，图5(b)为经过降雪模型滤波后的图像的梯度图像。图5(c)是采用归一化分割后的图像、图5(d)为传统随机游走图像、图5(e)是本文采用的自适应降雪模型的随机游走分割图像。从图5中，可以明显对比本文算法对缺失图像的还原弥补功能更强，图5(c)中的图像分割线与直线不能重合，图5(d)中的分割在缺失部分有一小部分突出。

图5 虚拟图分割结果比较

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

2.2 真实图像仿真

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

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

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

2.3 图像分割算法性能分析

采用研究者自己拍摄的生活中的图像为例，即第3组图。对本文所提的图像分割算法进行性能测试，作为横向比较，选择梯度图像算法、NCut算法和随机游走算法做了相似效果下的性能测试，其结果如表1所示。

表1 不同图像分割算法性能比较

从检测效果看，相比于传统的梯度图像算法，NCut算法，本文提出的改进算法复杂度明显降低，仅仅稍高于随机游走算法，有较为广泛的应用前景。

3 结语

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

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

［1］ 杨健鸷，刘霖，刘秀娟，等.基于FPGA的面阵CCD图像采集系统［J］.电子器件，2013，36(1):49-53.

［2］ Khan，Ahmad Ullah，Javid Jaffar，et al.Color Image Segmentation: A Novel Spatial Fuzzy Genetic Algorithm.Signal，Image and Video Processing，2012:1-11.

［3］ Liu Fang.The New Image Segmentation Algorithm Using Adaptive Evolutionary Programming and Fuzzy C-Means Clustering［C］// Proceedings of SPIE—The International Society for Optical Engineering，v 8056，2011，Visual Information Processing XX.

［4］ 李旭超，刘海宽，王飞，等.图像分割中的模糊聚类方法［J］.中国图象图形学报，2012(4):100-106.

［5］ 依玉峰，高立群，郭丽.改进FCM在交互式图像分割中的应用［J］.中国图象图形学报，2012(3):90-96.

［6］ 周家香，朱建军，梅小明，等.多维特征自适应MeanShift遥感图像分割方法［J］.武汉大学学报(信息科学版)，2012(4): 419-422，440.

［7］ 依玉峰，高立群，程伟，等.自适应随机游走图像分割算法［J］.东北大学学报(自然科学版)，2011(8):1092-1096.

［8］ 王成恩，黄章俊.基于高斯函数和信赖域更新策略的Kriging响应面法［J］.计算机集成制造系统，2011(4):740-746.

［9］ 钭斐玲，胡延庆，黎勇，等.空间网络上的随机游走［J］.物理学报，2012(17):571-577.

［10］王芳梅，范虹，王凤妮.水平集在图像分割中的应用研究［J］.计算机应用研究，2012(4):1207-1210.

陈杏环(1980- )，女，山东菏泽人，重庆大学硕士研究生，讲师，主要研究方向为图像处理，智能计算、数据挖掘，chenxinghuan1980@163.com;

闫海煜(1981- )，男，汉族，陕西勉县人，重庆电子工程职业学院通信工程学院，讲师，主要研究方向为电子技术、单片机技术、自动控制，yanhaiyu1981cq@ 163.com。

An Improved Model of Snowfall Image Segmentation Method Based on the Random Walk*

CHEN Xinghuan1*，YAN Haiyu2
(1.Computer College，Chongqing College of Electronic Engineering，Chongqing 401331，China; 2.College of Communication Engineering，Chongqing College of Electronic Engineering，Chongqing 401331，China)

In order to improve accuracy of image segmentation and 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 was proposed，Firstly，snowfall model and snow surface effect were analyzed in detail，the snow model was applied to image segmentation with strong adaptability，and then mixed the traditional random walk image segmentation algorithm with adaptive snow model characteristics to generate a new algorithm，finally made performance simulation using virtual and real images algorithm，the results showed the image segmentation performance is better than the common NCut and the traditional random walk algorithm for image segmentation，and it had certain research value.

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

10.3969/j.issn.1005－9490.2014.02.039

TN919.8

A

1005－9490(2014)02－0350－05

项目来源:重庆市教委科学技术研究项目(KJ110401)

2013-05-27修改日期:2013-06-24

EEACC:6140C