数字图像分割是指将图像中具有特定涵义且互不交叠的不同区域划分出来,这些区域均满足特定区域的一致性。图像分割在图像工程中占据很重要的位置,它是图像识别的基础,且图像分割的结果对后续的分析及处理工作有很大的影响。人工干预的基于图论的图像分割算法近年来凭借自身优势引起了研究人员的广泛关注,如基于随机游走算法的图像分割就是一种半自动的图像分割方法。随机游走是目前人们研究最早的随机过程之一,它不仅在数学、博弈、网络和金融等诸多领域中得到了广泛的应用,而且也有很多关于分析排队、场论方面以及破产系统等方面的研究理论。随机游走有着良好的数学基础使得在分割图像时,不仅抗噪声能力比较强,而且也可以很好地检测出弱边界,因此是一种有效的图像分割方法,而且近年来也发展成为了组合图论界研究最多成果最丰富的课题之一本文以随机游走理论为支撑,对图像分割问题进行了研究,主要进行了以下几个方面的工作：(1)归纳和总结了传统的和现代的图像分割方法,比较了各自的优缺点,并介绍了相应的改进方法。其中主要对随机游走方法进行了概述。(2)介绍了几种基于图论的方法,如随机游走,最大流最小割,最小生成树等,给出了随机游走理论相关的基本内容,包括直线上的以及平面上的随机游走,给出了基于随机游走理论进行图像分割的框架等,并通过随机游走和电路理论的内在联系将求解调和函数问题转化为求解稀疏的线性方程的系统问题。(3)由于医学超声图像存在斑点噪声强、对比度低、弱边界等特点,导致传统方法难以得到较好的分割效果,在详细介绍了随机游走的优点后,将随机游走算法应用于医学超声图像分割,不仅有效地抑制了斑点噪声,而且能准确地检测出医学超声图像中目标的弱边缘,得到的分割结果较为准确。而且此算法通过求解稀疏的、对称的、正定的线性方程的系统来获得Dirichlet问题的解,所以计算速度大为提高。(4)由于传统的随机游走算法在构造连通带权图时,权值只考虑了相邻像素间的相似度,而没有考虑像素周围的梯度信息,因而抑制了随机游走者沿着某些与种子点灰度接近的边向种子点的行走,造成漏分或错分。而且由于传统的随机游走算法采用4邻域方式,即当前像素只能对其邻域的4个方向进行选择,所以对图像的分割不够精确,因此本文以传统随机游走算法为基础,提出了一种鲁棒性更强的融合灰度和梯度方向信息的改进随机游走算法。此算法采用图像像素的8邻域的梯度信息和灰度信息共同为图网络的边的权重赋值,然后为每个像素进行标记来实现图像的分割。