Shape Matching with Belief Propagation: Using Dynamic Quantization to Accomodate Occlusion and Clutter

Graphical models provide an attractive framework for shape matching because they are well-suited to formulating Bayesian models of deformable templates. In addition, the advent of powerful inference techniques such as belief propagation (BP) has recently made these models tractable. However, the enormous size of the state spaces involved in these applications (about the size of the pixel lattice) has restricted their use to models drawing on sparse feature maps (e.g. edges), which are typically unable to cope with missing or occluded features since the locations of missing features are not represented in the state space. We propose a novel method for allowing BP to handle partial occlusions in the presence of clutter, which we call dynamic quantization (DQ). DQ is an extension of standard pruning techniques which allows BP to adaptively add as well as subtract states as needed. Since DQ allows BP to focus on more probable regions of the image, the state space can be adaptively enlarged to include locations where features are occluded, without the computational burden of representing all possible pixel locations. The combination of BP and DQ yields deformable templates that are both fast and robust to significant occlusions, without requiring any user initialization. Experimental results are shown on deformable templates of planar shapes.