An Improved Random Walk Algorithm for Interactive Image Segmentation

Interactive image segmentation is an important issue in computer vision. Many algorithms have been proposed for this problem. Among them, random walk based algorithms have been proved to be efficient. However, a large number of seeds (i.e., pixels with user-specified labels) must be given in advance to achieve a desirable segmentation for such algorithms, which makes user interaction inconvenient. To solve this problem, we improve the random walk algorithm in two aspects: (1) label prior is taken into account when computing edge weights between adjacent pixels; (2) each unseeded pixel is assigned with the same label as the seed with maximum first arrival probability to reduce the bias effect of seed size. The improved algorithm can achieve a desirable segmentation with few seeds. Experiment results on natural images illustrate the accuracy of the proposed algorithm.