|M. Pawan Kumar|
SOLVING MARKOV RANDOM FIELDS USING SECOND ORDER CONE PROGRAMMING RELAXATIONS
M. Pawan Kumar, P. Torr and A. Zisserman
In Proceedings of Conference on Computer Vision and Pattern Recognition (CVPR), 2006
This paper presents a generic method for solving Markov random fields (MRF) by formulating the problem of MAP estimation as 0-1 quadratic programming (QP). Though in general solving MRFs is NP-hard, we propose a second order cone programming relaxation scheme which solves a closely related (convex) approximation. In terms of computational efficiency, our method significantly outperforms the semidefinite relaxations previously used whilst providing equally (or even more) accurate results. Unlike popular inference schemes such as Belief Propagation and Graph Cuts, convergence is guaranteed within a small number of iterations. Furthermore, we also present a method for greatly reducing the runtime and increasing the accuracy of our approach for a large and useful class of MRF. We compare our approach with the state-of-the-art methods for subgraph matching and object recognition and demonstrate significant improvements.