Video object segmentation via random walks on two-frame graphs comprising superpixels

We propose a novel video object segmentation method employing random walkers to travel on graphs constructed on two consecutive frames. First, we estimate the initial foreground and background distributions by minimising an energy function that incorporates the stationary distributions of the random walks. The random walkers frequently travel between similar nodes of the graph constructed on two adjacent frames, which enables the incorporation of the inter-frame information into the energy function effectively and elegantly. Then, we refine the initial results by simulating the movements of multiple random walkers. We process the sequence in a recursive manner, which naturally propagates the previous segmentation labels to the subsequent frames. Additionally, we develop a strategy for adjusting the superpixel number using region similarity and the average Frobenius norm of optical flow gradient. This strategy can improve performance significantly. Furthermore, we discuss the feature selection problem in the method to select a more effective feature representation. Extensive and comparable experiments on Segtrack and Segtrack v2 demonstrate that the proposed algorithm yields higher performance than several recent state-of-the-art approaches.