Title : Fast Globally Optimal 2D Human Detection with Loopy Graph Models
Authors : Tai-Peng Tian and Stan Sclaroff
Date: March 31, 2010
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.