Random Walks for Interactive Alpha-Matting

L. Grady, T. Schiwietz, S. Aharon (USA), and R. Westermann (Germany)


Interactive Image Segmentation, Alpha Matting, Random Walks, General Purpose GPU, Image Editing, Object Ex traction


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 chal lenges remain. We propose a new technique based on ran dom walks that has the following advantages: First, by leveraging a recent technique from manifold learning the ory, 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, re quires 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 fore ground/background maps. Finally, the algorithm has an in herit parallelism that leads to a particularly efficient im plementation 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.

Important Links:

Go Back