Natural Image Matting

CS129 Computational Photography Final Project

December 21, 2012

A closed form solution to Natural Image Matting - Levin et al.

Background

Matting refers to the process of extracting foreground object from an image. Matting is an important task in image and video editing. Matting tasks usually produces a "matte" that can be used to separate foreground from the background in a given image. Matte can also used to combine a given foreground on a different background to produce new plausible image.

Goal

The goal of this project is to produce an alpha matte that can be used to extraxt foreground from an image with limited user input. The task is challenging because at each pixel we need to estimate the foreground , background and the foreground opacity (matte).

The Matting Equation

A image is a composite of foreground and background. Hence each pixel intensity is a linear combination of a foreground and background that can be written as :


            	I_i = α_i*F_i + (1-α_i)*B_i			(1)

In matting equation all quantities on the right of the equation are unknown. Thus for a color image we have 7 unknowns and 3 equations. Hence this problem is severely under-constrained. So a rough segmentation of foreground and background is required to extract a good matte. This segmentation can be in form of trimap or scribbles.

Some methods take trimap in addition to given image to solve for foreground, background and alpha. For example Bayesian Matting - Chuang et al. CVPR '01, Poisson Matting - Sun et al. SIGGRAPH '04 etc use a trimap while Wang and Cohen ICCV '05 used a scribble based interface. Most methods solve for alpha, F and B simultaneously by iterative non-linear optimization, alternating the estimation of F, B with that of alpha. In this method a scribble based segmentation is used to solve for alpha matte.

Derivation

As the matting problem is under-constrained, we assume that F and B are locally smooth over a small window. Rewriting the above matting equation and expressing alpha in terms of Image intensities.


            	α_i = a*I_i + b	∀i∈w      		(2)
		
		a = 1/F-B
		b = -B/F-B
		for a small window w

Our goal is to find alpha, a and b to minimize the following cost function

w_j is a small window around j. ε is a regularization term.

Windows of 3 X 3 pixels is used which enables propagation of information between neighbouring pixels. The cost function in alpha is quadratic in alpha,a and b with 3N unknowns for an image of size N pixels.

Similarly for color images we replace the linear model with a 4D linear model assuming that for a small window each of F and B is a linear combination of two colors.