A Convex Max-Flow Approach to Distribution-Based Figure-Ground Separation

作者：Punithakumar Kumaradevan^*; Yuan Jing; Ben Ayed Ismail; Li Shuo; Boykov Yuri

来源：SIAM Journal on Imaging Sciences, 2012, 5(4): 1333-1354.

DOI：10.1137/110850372

• image segmentation
• convex optimization
• max-flow min-cut
• Bhattacharyya measure
• distribution matching
• iterative methods

This study investigates a convex relaxation approach to figure-ground separation with a global distribution matching prior evaluated by the Bhattacharyya measure. The problem amounts to finding a region that most closely matches a known model distribution. It has been previously addressed by curve evolution, which leads to suboptimal and computationally intensive algorithms, or by graph cuts, which result in metrication errors. Solving a sequence of convex subproblems, the proposed relaxation is based on a novel bound of the Bhattacharyya measure which yields an algorithm robust to initial conditions. Furthermore, we propose a novel flow configuration that accounts for labeling-function variations, unlike existing configurations. This leads to a new max-flow formulation which is dual to the convex relaxed subproblems we obtained. We further prove that such a formulation yields exact and global solutions to the original, nonconvex subproblems. A comprehensive experimental evaluation on the Microsoft GrabCut database demonstrates that our approach yields improvements in optimality and accuracy over related recent methods.

• 出版日期2012