Solving Markov Random Fields using Second Order Cone Programming Relaxations
Manish Kumar, Philip H. S. Torr, Andrew Zisserman · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · 2006
This paper presents a generic method for solvingMarkov 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 MRFs. We compare our approach with the state-of-the-art methods for subgraph matching and object recognition and demonstrate significant improvements.
Cited by 37 works. doi:10.1109/cvpr.2006.283
Authors
References
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
- Fast approximate energy minimization via graph cuts
- What energy functions can be minimized via graph cuts?
- Applications of second-order cone programming
- Loopy Belief Propagation for Approximate Inference: An Empirical Study
- OBJ CUT
- Spatial Priors for Part-Based Recognition Using Statistical Models
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.
- A new point matching algorithm for non-rigid registration
- Bethe free energy, Kikuchi approximations, and belief propagation algorithms