Dynamic quantization for belief propagation in sparse spaces

Graphical models provide an attractive framework for modeling a variety of problems in computer vision. The advent of powerful inference techniques such as belief propagation (BP) has recently made inference with many of these models tractable. Even so, the enormous size of the state spaces required for some applications can create a heavy computational burden. Pruning is a standard technique for reducing this burden, but since pruning is irreversible it carries the risk of greedily deleting important states, which can subsequently result in gross errors in BP. To address this problem, we propose a novel extension of pruning, which we call dynamic quantization (DQ) that allows BP to adaptively add as well as subtract states as needed. We examine DQ in the context of graphical-model based deformable template matching, in which the state space size is on the order of the number of pixels in an image. 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. Finally, we argue that DQ is applicable to a variety of graphical models in which the state spaces are sparsely populated. (C) 2006 Elsevier Inc. All rights reserved.