Fast Globally Optimal 2D Human Detection with Loopy Graph Models
Date
2010-03-31
DOI
Authors
Tian, Tai-Peng
Sclaroff, Stan
Version
OA Version
Citation
Tian, Tai-Peng; Sclaroff, Stan. "Fast Globally Optimal 2D Human Detection with Loopy Graph Models", Technical Report BUCS-TR-2010-007, Computer Science Department, Boston University, March 31, 2010. [Available from: http://hdl.handle.net/2144/3786]
Abstract
This paper presents an algorithm for recovering the globally optimal 2D human figure detection using a loopy graph model. This is computationally challenging because the time complexity scales exponentially in the size of the largest clique in the graph. The proposed algorithm uses Branch and Bound (BB) to search for the globally optimal solution. The algorithm converges rapidly in practice and this is due to a novel method for quickly computing tree based lower bounds. The key idea is to recycle the dynamic programming (DP) tables associated with the tree model to look up the tree based lower bound rather than recomputing the lower bound from scratch. This technique is further sped up using Range Minimum Query data structures to provide $O(1)$ cost for computing the lower bound for most iterations of the BB algorithm. The algorithm is evaluated on the Iterative Parsing dataset and it is shown to run fast empirically.