VISION LAB

Efficient and Exact Inference using Branch-and-Bound
Typical results from Buffy, Pascal Stickmen, and VideoPose2 datasets [4] shown in Stickmen representation from top to bottom, respectively. In each set of results, we show our result on the left and the Sapp et al.’s [3,4] result on the right.

We propose a novel Branch-and-Bound (BB) method to efficiently solve exact MAP-MRF inference on problems with a large number of states (per variable). These problems are common in computer vision or computational biology. For example, in computer vision, the problem of estimating the pose of a person (i.e., body part configurations, see figure) can be addressed by modeling the human body using a MRF wherein states correspond to locations and orientations of each body part. In computational biology, protein design can be modeled using a MRF model wherein states corresponding to combinations of different amino acids and rotamers. Our BB approach leverages a novel data structure to reduce the time complexity and a novel branching strategy that reduces the number of branches that are to be evaluated. Extensive theoretical and experimental analysis demonstrates that our method is provably faster than naive BB algorithms and other state-of-the-art methods [3,4] for extract inference on loopy believe models. Anecdotal results are shown in the figure on the right.

Publications

  • Min Sun, Murali Telaprolu, Honglak Lee, and Silvio Savarese, "An Efficient Branch-and-Bound Algorithm for Optimal Human Pose EStimation." CVPR'12 (pdf) (bibtex) (technical report).
  • Min Sun, Murali Telaprolu, Honglak Lee, and Silvio Savarese, "Efficient and Exact MAP Inference using Branch and Bound." AISTATS'12 (pdf) (bibtex) (technical report).

Source Codes

  • April 3rd, 2012, 0.1 version Matlab script + C mex BB code.
  • April 30th, 2012, 0.2 version (fix small bug in matlab wrapper) Matlab script + C mex BB code.

References

  • A. Globerson and T. Jaakkola. "Fixing max-product: Convergent message passing algorithms for MAP LP-relaxatons." NIPS'07.
  • D. Sontag, T. Meltzer, A. Globerson, Y. Weiss, and T. Jaakkola. "Tightening LP relaxations for MAP using message passing." UAI'08
  • B. Sapp, A. Toshev, and B. Taskar. "Cascaded models for articulated pose estimation." ECCV'10.
  • B. Sapp, D. Weiss, and B. Taskar. "Parsing human motion with stretchable models." CVPR'11.

Contact : sunmin at umich dot edu

Last update : April 3rd, 2012