图像分割是以人类的视觉认知形态为基础，利用相应算法将就是把图像分成多个特定的、具有实际应用意义的图像区域，并提取出感兴趣目标的过程。由于图像分割在计算机视觉等应用领域中作为一个相对底层的应用，图像分割结果的好坏在一定程度上会影响高层应用对图像含义的理解。因此，设计准确高效并且适用性高的图像分割算法，对图像处理和计算机视觉领域的发展意义是十分重要的。图像分割算法按有无人工指导信息分割自动和交互式的图像分割。由于自然图像中的纹理较为复杂，颜色分布较为多样，自动化的图像分割在复杂的自然图像下进行分割时受到诸多约束。而交互式的图像分割利用了用户交互来指导图像分割，它较之自动化图像分割，能根据用户交互产生先验知识，弥补了自动化分割在复杂图像下的错误分割问题。因此，近年来，基于图的这种交互式图像分割方法受到广泛的关注。

基于随机游走的分割算法，是一种基于图理论的交互式的图像分割算法。其抗噪声性就好，准确度较高，对弱边界处理能力较强，因此在图像分割算法中被广泛应用。而本文从随机游走的理论出发，提出了一个带有Sub-Markov转移概率的随机游走框架去统一基于随机游走的算法，去用于交互式的多标签图像分割。并通过先验标签的引入来改进算法，并对其在复杂的自然图像分割问题上展开研究。

本文主要的具体工作如下：1）对随机游走的数学理论进行研究；对其应用于图像分割领域的计算原理做详细分析；对基于随机游走模型的几类算法：随机游走算法、随机游走重启算法、惰性随机游走算法进行原理和比较分析。2）针对随机游走算法的Sub-Markov属性，构建出一个随机游走算法的框架（Sub-Markov Random Walk）去统一基于随机游走的各种改进算法，而后框架上进行参数和结构修改，比较几类基于随机游走的算法，验证提出框架的高适用性3）针对复杂纹理和前景目标细长分支信息分割效果不佳的问题，通过在Sub-Markov Random Walk框架上引入先验标签节点，来设计处本文提出的带有先验标签的Sub-Markov Random Walk算法。并通过相应数据集上的图像分割实验，比较本文提出方法和其他几类基于随机游走的算法的结果和准确度，验证此方法的显著优势。

Based on human visual cognition, image segmentation is the process of dividing the image into several specific areas with practical application meaning and extracting the target of interest with corresponding algorithm. Since image segmentation is a relatively low-level application in applications such as computer vision, the results of image segmentation will largely affect the understanding of image meaning in high-level applications. Therefore, the image segmentation algorithm with accuracy , high efficiency and applicability is very important for the development of image processing and computer vision. The image segmentation algorithm separates automatic and interactive image segmentation with or without manual guidance information. Because the textures in natural images are more complex and the color distribution is more diverse, automated image segmentation is subject to many constraints when segmenting under complex natural images. Interactive image segmentation utilizes user interaction to guide image segmentation. Compared with automated image segmentation, it can generate prior knowledge based on user interaction, and compensates for the problem of automatic segmentation in complex images. Therefore, in recent years, such interactive image segmentation methods based on graph theory have received extensive attention.

The image segmentation algorithm based on Random Walk is an interactive image segmentation algorithm based on graph theory. It has good robustness, high precision and strong processing ability for weak boundaries, so it is widely used in image segmentation algorithms. Based on the theory of Random Walk, this paper proposes a framework with Sub-Markov transition probability to unify the algorithm based on Random Walk for interactive multi-label image segmentation. And through the introduction of a priori tags ,we improve the algorithm, and study it on the complex natural image segmentation.

The main work of this paper is as follows: 1) Research on the mathematical theory of Random Walk; analyze the calculation principle applied in the field of image segmentation; and does the principle and comparative analysis on algorithms based on random walk model: Random Walk algorithm, Random Walk with Restart algorithm and the Lazy Random walk algorithm. 2) For the Sub-Markov property of the Random Walk algorithm, Sub-Markov Random Walk is constructed to unify various improved algorithms based on Random Walk. And then we compare several types of algorithms based on Random Walks with modifying the parameters and structure on the framework to verify the high applicability of the framework. 3) For the problem of  poor segmentation performance of the image with complex texture and with slender branch of foreground target. Sub-Markov Random Walk with Prior Label is designed by introducing a prior tag node on the Sub-Markov Random Walk framework. Through the image segmentation experiment on the corresponding dataset, the results and accuracy of the proposed method and other types of random walk-based algorithms are compared to verify the significant advantages of this method.