Efficient SDP Inference for Fully-connected CRFs Based on Low-rank Decomposition
This work addresses the computational bottleneck in fully-connected CRFs for computer vision tasks, offering a more general and efficient inference method compared to existing approximate approaches.
The paper tackles the problem of efficient inference for fully-connected Conditional Random Fields (CRFs), which model long-range contextual relationships but are computationally challenging, by developing a scalable algorithm based on low-rank decomposition and a tailored quasi-Newton method, enabling applications like pixel-level image co-segmentation that were previously infeasible.
Conditional Random Fields (CRF) have been widely used in a variety of computer vision tasks. Conventional CRFs typically define edges on neighboring image pixels, resulting in a sparse graph such that efficient inference can be performed. However, these CRFs fail to model long-range contextual relationships. Fully-connected CRFs have thus been proposed. While there are efficient approximate inference methods for such CRFs, usually they are sensitive to initialization and make strong assumptions. In this work, we develop an efficient, yet general algorithm for inference on fully-connected CRFs. The algorithm is based on a scalable SDP algorithm and the low- rank approximation of the similarity/kernel matrix. The core of the proposed algorithm is a tailored quasi-Newton method that takes advantage of the low-rank matrix approximation when solving the specialized SDP dual problem. Experiments demonstrate that our method can be applied on fully-connected CRFs that cannot be solved previously, such as pixel-level image co-segmentation.