Dynamic Random Walk for Superpixel Segmentation

In this paper, we propose a novel random walk model, called Dynamic Random Walk (DRW), which adds a new type of dynamic node to the original RW model and reduces redundant calculation by limiting the walk range. To solve the seed-lacking problem of the proposed DRW, we redefine the energy function of the original RW and use the first arrival probability among each node pair to avoid the interference for each partition. Relaxation of our DRW is performed with the help of a greedy strategy and the Weighted Random Walk Entropy(WRWE) that uses the gradient feature to approximate the stationary distribution. The proposed DRW not only can enhance the boundary adherence but also can run with linear time complexity. To extend our DRW for superpixel segmentation, a seed initialization strategy is proposed. It can evenly distribute seeds in both 2D and 3D space and generate superpixels in only one iteration. The experimental results demonstrate that our DRW is faster than existing RW models and better than the state-of-the-art superpixel segmentation algorithms with respect to both efficiency and segmentation effects.