Side Note: First draft on Mar 31 2011.

2. Producing the Trimap

Below is an example of a trimap,

Figure 1. Trimap based on Iprob

How do we get this trimap?

Part 1 has covered how to compute the Iprob, once we have the Iprob for every pixel of a video frame, we compare the Iprob with a small real value epsilon.

here B stands for background, F stands for foreground and U refers to unknown. In figure 1, the white area are F, black area are B and gray area are U.

For the white and black areas, it’s confident to decide whether they’re foreground or background based on Iprob alone. The gray regions are further processed through MRF to decide it’s foreground or background.

As a matter of fact, the benefit of this trimap is to reduce the MRF processing. With the trimap, MRF processing is only done for pixels in unknown region.

3. GraphCut for Unkown Regions

There are many problems can be described using MRF in the form of

E = Ed+λEs

where the Ed is the data cost and Es is the smoothness cost. In essence, Ed describes the energy of a pixel being classified as certain category, Es describes the dependence of this classification’s dependency on its neighbors. The solution for these problems are usually finding a classification that results in minimum cost for all pixels.

There’re many ways to solve the cost (some refer as energy) minimization problem, one of them is GraphCut.

For this real-time bilayer segmentation, the Ed and Es function can be expressed as,

here Data(Seg) is the Ed for all pixels under unknown region. And,

here Sth(Seg) is the Es for all neighboring pixels under unknown region. dist(p,q) refers Euclidean distance between pixels p and q.

Note that Seg can be either F or B in the two equations above. For smoothness energy, if the two neighboring pixels p and q are classified as the same category (both F or both B), the energy is 0.

P(Cp|F), P(Cp|B) and Iprob are already calculated in part 1, smoonthness energy is also straightforward to calculated for two given pixels.

The method of calculating L(pi|F) and L(pi|B) will be covered in Part 3.