Solving Markov Random Fields using Semi Definite Programming
Philip H. S. Torr · 2003
This paper explores a new generic method for matching, when there are conditional dependencies between the matches. It allows different sorts of features to be matched in the same global optimization framework. The method is based on a binary Markov random field model which is defined on the product space of matches, and is shown to be equivalent to 0-1 quadratic programming, and the MAXCUT graph problem. In general these problem are complete. However our approach takes inspiration from the celebrated result of Goemans and Williamson (1995) that finds a polynomial time 0.879 approximation to several complete, using semidefinite programming. The method is demonstrated for the problem of curve matching. 1