A Compact Linear Programming Relaxation for Binary Sub-modular MRF
This is an incremental improvement for computer vision researchers working on interactive object segmentation, offering a more efficient method with better performance.
The authors tackled the problem of binary sub-modular MRF for object segmentation by proposing a compact linear programming relaxation, which outperformed quadratic programming in segmentation accuracy on the Oxford dataset and reduced computational complexity compared to conventional LP.
We propose a novel compact linear programming (LP) relaxation for binary sub-modular MRF in the context of object segmentation. Our model is obtained by linearizing an $l_1^+$-norm derived from the quadratic programming (QP) form of the MRF energy. The resultant LP model contains significantly fewer variables and constraints compared to the conventional LP relaxation of the MRF energy. In addition, unlike QP which can produce ambiguous labels, our model can be viewed as a quasi-total-variation minimization problem, and it can therefore preserve the discontinuities in the labels. We further establish a relaxation bound between our LP model and the conventional LP model. In the experiments, we demonstrate our method for the task of interactive object segmentation. Our LP model outperforms QP when converting the continuous labels to binary labels using different threshold values on the entire Oxford interactive segmentation dataset. The computational complexity of our LP is of the same order as that of the QP, and it is significantly lower than the conventional LP relaxation.