摘要

人类对于信息的获取，大部分都来源于视觉，对于周围环境的认知，也主要是通过视觉的方式来获取。可以说人类的视觉是人类走向新的世界，不断进步的源泉。人脑结构复杂，人类对于人脑的利用不过是总脑容量的风毛菱角。但是人脑对于图像的处理是非常灵活的，不管是什么实物，都可准确的进行判断。而机器却不行，一个机器要判断一样事物，必须要大量学习。计算机虽然处理速度非常快，但是计算机对事物的识别的准确率还有待提高。机器人对抗人脑，还有一个非常有挑战的问题。而在计算机对图像结构数据的处理过程中，图像分割位计算机对图像的高层理解与应用提供了必要的条件。没有准确的分割结果作为基础条件，计算机处理系统后续的分析机应用是无法顺利进行的。因此，本文对计算机图像分割进行研究，研究基于随机游走得图像分割技术，主要做了以下几方面工作：

（1）对本课题得研究意义与背景进行分析阐述，对图像分割得概念进行介绍，包括图像分割得定义，图像分割分类及特点。

（2）对图像进行预处理，图像在采集得过程中，会有噪声污染，所以为了提高分割效率，我们需要对图像进行预处理，包括图像灰度化、直方图均衡化、中值滤波、边缘检测；

（3）对随机游走得图像分割算法进行研究，首先对传统得随机游走算法进行研究，包括分割模型和算法步骤，在此基础上，结合分水岭算法得思想，提出基于区域的随机游走图像分割模型。

通过实验结果证明，本文所设计的算法不管是面对复杂度低还是复杂度高得图片，或者是彩色图像，都由较好得分割效果。从不同分割算法对同一图像的分割评价指标数据我们可以看，基于区域得随机游走分割算法效果最好，因此，本文设计得基于区域得随机游走算法是一种非常可取得图像分割算法。

关键词：图像分割；随机游走；分割评价

基于随机游走的图像分割技术

3.1传统的随机游走分割模型

3.1.1随机游走分割模型

随机游走模型是指定一个起始点和一个网络图，随机游走者以不同的概率从

起点游走到相邻的节点上，然后以当前节点为起始点，重复上述随机移动的过程。

那些被随机选出的节点序列就构成了一个随机游走过程。

    使用随机游走算法进行图像分割最早由Grady提出，它的分割思想是，以图

像的像素为图的顶点，相邻像素之间的四邻域或八邻域关系为图的边，并根据像

素属性及相邻像素之间特征的相似性定义图中各边的权值，以此构建网络图，然

后由通过用户手工指定前景和背景标记，即前景物体和背景物体的种子像素，以

边上的权重为转移概率，未标记像素节点为初始点，计算每个未标记节点到首次

到达各种子像素的概率，根据概率大小，划分未标记节点，得到最终分割结果。

3.3.1随机游走图像分割步骤

随机游走算法是一种基于图论的半自动图像分割方法，其本质同归一化分割，只是将分割准则转化为求网络图中结点间跳跃的概率，依据最大概率准则完

成图像的分割。随机游走从每个为标记节点游走到各个种子像素的概率可通过求

解一个关于图Laplace矩阵的稀疏的正定的线性方程得到，可以用L表示图的Laplace矩阵，该算法可用于任意数目的标记像素类别。假设图像用序列对G(V,E)来表示，其中每一个顶点 的邻接关系。边上的权值可解释为像素之间的相似度，根据采用的度量特征不同而有所不同，这里用W表示权重矩阵，边 的权重 或者w(i,j)表示随机游走从顶点 的转移概率，因此必须有 表示顶点 的度，它是连接顶点 的所有边的权重之和。然后，图上顶点、边以及边上的权重可用于构造图的Laplace矩阵。

随机游走算法首先将图像映射为带权的无向图，并对其中的每条边赋予一定的权值，代表相邻像素或者区域之间的相关性。随机游走分割算法的主要步骤是:

(1)   对图像进行相关的去噪、平滑等预处理，然后由用户手工标定K个种子像素，分别指定用户感兴趣的目标区域或背景区域，从而获得一个标记点集合 ,在两类分割的情况下只需要标记目标与背景两类种子点，即K=2。若多类目标分割，则标记多种类别的种子点；

(2)   将图像转换为图的形式，可以使用图像的灰度或者纹理信息，滤波系数

等特征值定义图中结点间的权值。

(3)   将图的顶点分为 两个集合， 是各类标记点的集合， 为标记点的集合；

(4)   根据公式构建Laplace矩阵，将图像分割问题转化为Dirichlet问题进行求解，获得各未标记节点对各类标记的隶属度。对于K类标记， ，因此只需要计算K-1次即可；

(5)   每一个未标记点，根据获得的对K类标记的隶属度值进行判断，将未标记节点 判别位属于类别k,若

3.2基于区域的随机游走图像分割模型

3.2.1分水岭算法基本思想

分水岭变换是一种基于拓扑理论的数学形态学的图像分割方法，其基本思想是把图像看作是测地学上的拓扑地貌，图像中每一点像素的灰度值表示该点的海拔高度，每一个局部极小值(minima)及其影响区域称为集水盆，而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面，刺穿一个小孔，然后把整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的影响域慢慢向外扩展，在两个集水盆汇合处构筑大坝(dam)，即形成分水岭^[34–36]。图3.1显示的是分水岭的形成