A Fast and Adaptive Random Walks Approach for the Unsupervised Segmentation of Natural Images

Image segmentation is a challenging task that has several applications in domains like medical imaging and surveillance. Among the various approaches proposed for this task, unsupervised methods have the advantage of being able to segment images without any assistance from the user. However, such methods often suffer from long runtimes and tend to be sensitive to the choice of parameters. Because of these problems, users will often prefer semi-supervised methods, which provide a more controllable output in the same amount of time. This paper proposes a new unsupervised approach, based on random walks, which maps each pixel to the most probable label in a local neighborhood. To make this approach more robust to the choice and learning of the parameters, we propose an efficient computational technique, in which the parameters and the segmentation probabilities are recomputed alternatively. We also describe a refinement strategy that improves the speed and accuracy of the segmentation by applying random walks at different scales. We evaluate the usefulness of our approach on the segmentation of natural images from the Berkeley segmentation database (BSD300). Results show our approach to have an accuracy comparable to state-of-the-art segmentation methods, while being much faster than these methods.