Paper Summary : A Global sampling method for Alpha Matting

In this article, we will try and Understand how a global sampling method is used for Alpha matting

Let us first understand why the paper is named this way.

Global — It uses all the known samples(In a trimap, where some pixels are marked as unknown and the others are known), Unlike other sampling methods which collect only the nearby samples

Sampling — It first estimates the foreground and background color and then computes the alpha matte.

Steps given in the paper to compute the alpha matte are the following:

1. Global Set

They use a global set, which is defined below :

Our foreground (background) sample set consists of all known foreground (background) pixels on the unknown region’s boundary.They also tested
even larger sample sets comprising of all known pixels k-pixel (k > 1) away from this boundary, and to the extreme of all known pixels in the image. They found that using the pixels on the unknown region’s boundary (k = 1)
is sufficient to produce good results.They defined the following terms:

Nf — Number of foreground samples,

Nb — Number of background samples

This image indicate the sample sets
(red: F; green: B).

2. Defining loss function

The goal is to select a good pair of sample Foreground and background pair for any unknown pixel from all candidate pairs. A “Good” foreground and background pixel is one which gives the minimum loss, defined below :

The loss function contains two components:

a. The spatial distance of the sample from the unknown pixel is taken

A spatial cost function Es, favors spatially closed samples

Es(Fi) = ∥xFi − xI ∥/Df

where xFi and xI are the spatial coordinates of the Foreground sample and the unknown pixel I respectively.Df is the normalization factor which is the minimum distance of the unknown pixel from the nearest foreground boundary.

Similarly, Es(Bi) is defined for the boundary sample.

b. The second cost function takes into account the color fitness of the samples

Given a pair of samples (F i , B j ) with the sample indexes i and j,first estimate the alpha value αp of an unknown pixel I by:
αp = (I − Bj )(F i − Bj )/(∥F i − B j ∥)²

Then a color cost function Ec is defined to describe how good a sample pair fits the matting equation (1):

Ec(Fi , Bj ) = ∥I − ( αp*Fi + (1- αp)*Bj)∥

Hence, The total loss function defined for samples (Fi,Bj) is the sum of the spatial error and the color cost error :

E = Ec(Fi,Bj) + Es(Fi) + Es(Bi)

3.How to select samples

Now, The point is how do we select the samples.

We have nf foreground samples and nb background samples, so a grid search for all the combination of samples would have a time complexity of O(nf*nb) for each unknown pixel, and let us say we have N unknown pixels, the total time complexity would amount to O(N*nf*nb)

The paper suggests a Randomized algorithm inspired by the PatchMatch algorithm, They have named this algorithm the SampleMatch Algorithm

I have mentioned the steps of the SampleMatch Algorithm below:

a. Sort all the foreground and background samples by a certain criterion, This paper uses Intensity to sort the samples.We denote their ordered set as follows:

Foreground ->{F i ∣i = 1, 2, …, nF }

Background->{{B j ∣j = 1, 2, …, nB}

For each unknown pixels our target is to find a point in the FB search space which has (approximately) smallest cost.

b. Maintain a current optimal (smallest cost) sample pair (F i , B j ) for each unknown pixel I(x, y). This current optimal sample pair is denoted by
Φ(x, y) = (F i , B j ). After the initialization , The algorithm iterates between two steps between propagation and random search.

Propagation:

For the unknown pixel I(x, y) being scanned, Φ(x, y) is updated by considering the current optimal sample pairs Φ(x ′ , y ′) of its neighboring pixels (x ′ , y ′ ):

Φ(x, y) ← arg min (E(Φ(x ′ , y ′ )))

Where E is the loss function defined before, (x’,y’) is in the first order neighborhood.

Random Search

For the unknown pixel I(x, y) being scanned, we update its Φ(x, y) by a sequence of random trials:

{(Fik , Bjk )∣k = 0, 1, 2…}. This sequence is generated by:

(ik , jk ) = (i, j) + ω*(β^k)*R,

where R is a uniform random number in [−1, 1],β^k is the kth exponential of a ratio β = 0.5, and ω is the size of the search space.The sequence goes in the order of k=0, 1, 2… until the search window radius ωβ k is below 1.
In this step, Φ(x, y) is updated if the new pair (Fik , Bjk )
has a smaller cost.

Intuitively, the random search step tests a sequence of
random points (ik , jk ) in a neighborhood (in the FB space) of the current optimal point (i, j). The neighborhood radius ω*β decreases exponentially (in each iteration).

4. Post Processing

The paper applies a kind of post-processing (smoothing) by considering neighboring pixels can further improve the matting results.

REFERENCES

1. . Wang and M. Cohen. An iterative optimization approachfor unified image segmentation and matting.ICCV, 2005
2. A Global Sampling Method for Alpha Matting Kaiming He1, Christoph Rhemann2, Carsten Rother3, Xiaoou Tang1,Jian Sun