Random walks for interactive alpha-matting

Interactive, efficient, methods of foreground extraction and alpha-matting are of increasing practical importance for digital image editing. Although several new approaches to this problem have recently been developed, many challenges remain. We propose a new technique based on random walks that has the following advantages: First, by leveraging a recent technique from manifold learning theory, we effectively use RGB values to set boundaries for the random walker, even in fuzzy or low-contrast images. Second, the algorithm is straightforward to implement, requires specification of only a single free parameter (set the same for all images), and performs the segmentation and alpha-matting in a single step. Third, the user may locally fine tune the results by interactively manipulating the foreground/background maps. Finally, the algorithm has an inherit parallelism that leads to a particularly efficient implementation via the graphics processing unit (GPU). Our method processes a 1024×1024 image at the interactive speed of 0.5 seconds and, most importantly, produces high-quality results. We show that our algorithm can generate good segmentation and matting results at an interactive rate with minimal user interaction.