Abstract: A new natural image matting method is proposed based on the graph theory.This algorithm begins from the image mapped into a weighted undirected graph and marks seeds in the graph with different colors，then uses the random Walk with Restart algorithm to calculate similarity of the pixels，and proposes a linear model.Finally，the problem is solved and the foreground and background color components of each unknown point are estimated.Experimental results have shown that the proposed method has many advantages.The RWR method is quoted in the natural image matting with the use of graph theory.It avoids the high complexity of the inverse in image and solves the weak boundary problem.

Key words: natural image matting, blue screen matting, Random Walk with Restart

摘要： 提出了一种基于图论的自然图像抠图方法。该算法首先在图像上建立图的模型，并用不同颜色标记目标种子点和背景种子点；接着采用有重启概率的随机游走方法计算像素点之间的相似性，进而提出一个线性概率模型；最后求解模型并分别估计前景和背景物体。与目前的抠图方法相比，该算法具有以下特点：将RWR方法结合图论用于自然图像抠图中；减小了RWR算法在图像分割中迭代求逆的高复杂度，大大提高了抠图速度；解决了“弱”边界的问题。

关键词: 自然图像抠图, 蓝屏抠图, 有重启概率的随机游走（RWR）