基于GrabCut图像分割

RANDOM WALKS FOR INTERACTIVE ALPHA-MATTING

Leo Grady and Thomas Schiwietz and Shmuel Aharon

Imaging and Visualization

Siemens Corporate Research

755 College Road East

Princeton, NJ, USA

Leo.Grady@siemens.com

R

¨

Figure 1. By computing the alpha matte as the probability that a random walker first reaches a foreground pixel, a simple, fast

algorithm is presented that is capable of producing quality results, even when applied to low-contrast images or objects with

difficult or weak boundaries.

ABSTRACT

1

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-

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

Published in: Proceedings of the Fifth IASTED International Confer-

ence on Visualization, Imaging and Image Processing, J.J. Villanueva, Ed.

Benidorm, Spain: ACTA Press, Sept. 2005, pp. 423–429

1 Introduction

Interactive foreground extraction and alpha-matting of dig-

ital images remains a challenging problem. The difficulty

of this problem is a result of a simultaneous attempt to min-

imize user time/interaction, properly handle color, regular-

ize the ill-posedness of the alpha-matting model, provide an

efficient algorithm that is feasible to implement and, above

segmentation tasks on grayscale images, extra care must

be taken to extend those techniques to produce an alpha

matte on color images [2]. In contrast, the random walker

object extraction algorithm presented in [3] directly offers

the alpha matting. In this work, we make three extensions

to the algorithm presented in [3] to allow for application

in the interactive alpha-matting of digital images: 1) A

novel utilization of color information, 2) Use of random

walker probabilities as the alpha matte, and 3) Details for

an implementation on the graphics processor unit (GPU).

in the presence of low-contrast boundaries and noise. We

note also that this technique has straightforward extension

(a) Original (b) Trimap (c) Poisson matting (d) GrabCut (e) Random Walker

Figure 2. A comparison of matting algorithms on two images. a) Original images. b) Trimap, with foreground set to white,

background set to black and unknown set to gray. c) Poisson matting is derived with the assumption that the foreground and

background intensities are widely separated, which is violated by the llama image but more correct for the flower image. d)

GrabCut performs well, but the alpha matting resembles a steep (one-pixel) blur around the boundary. e) Random walker

matting. Note that Poisson matting, GrabCut and Random walker were all initialized with a trimap and no additional user-

interaction was supplied.

to 3D (e.g., video) or higher dimensional editing problems,

indicating “foreground”, “background” and “unknown” re-

gions, we set the

value at each pixel in P

u

as the proba-

bility that a random walker starting from this location will

reach a pixel in P

f

before striking a pixel in P

b

, when bi-

ased to avoid crossing the foreground boundary. Despite

efficient solution via a graphics processor unit.

Several properties of the solution to this random walker

problem, as demonstrated in [3], make it attractive for use

as the alpha-matte. First, it was shown that such an ap-

proach will cause the distribution of probabilities (i.e., the

matte) to respect low-contrast or even missing boundaries.

Second, the computed alpha-matte will vary smoothly, ex-

cept for clear transitions over an object boundary. Finally,

[3] showed that such an algorithm has provable robustness

to noise. Furthermore, the algorithm takes just one free

where

coefficient between the foreground object, F, and the back-

ground object, B. The

preted as a probability [5] that the pixel belongs to the fore-

ground object, a partial differential equation solution [6], or

as an interpolation [2] between the known foreground and

background objects. With the present approach, we take

all three viewpoints by formulating

malizes the algorithm and Section 4 discusses a particularly

efficient implementation on commodity graphics hardware.

More results follow in Section 5 with the conclusion and

future directions.

2 Related Work

A vast literature is devoted to the problems of foreground

extraction and alpha-matting. We therefore limit our review

to highly successful, ubiquitous and/or mathematically re-

lated techniques.

Foreground extraction via Intelligent Scissors (a.k.a.,

energy model for alpha-estimation.

Since GrabCuts and (global) Poisson matting were con-

vincingly shown to outperform the other methods re-

viewed, we compare our algorithm to these two techniques

in Figure 2 with detailed views shown in Figure 3. Al-

though GrabCuts allows for a less-informative bimap in-

put, all three algorithms were initialized with a trimap in

order to provide a fair comparison. Note the trouble with

the Poisson matting technique for the low-contrast llama

image due to the singularity of (2). Although GrabCuts

trajectory of the random walker and the analytical compu-

tation of the random walker probabilities. We formulate

the algorithm on a discrete space (i.e., a graph), where each

pixel corresponds to a node and edges are placed between a

pixel and its four neighbors in the cardinal directions. Be-

fore proceeding, we will fix our notation.

A graph [8] consists of a pair G = (V, E) with vertices