Efficient mean-shift belief propagation and its applications in computer vision
Yanxi Liu, Minwoo Park · 2010
Probabilistic graphical models (PGMs) are widely used in many areas of computer vision and machine learning. Since classic belief propagation is not suitable for a continuous state space, sampling-based belief propagation methods have been developed, e.g. non-parametric belief propagation (NBP). However NBP requires a large number of samples and its resampling process is slow, preventing its wide applicability. We are motivated to develop an efficient belief propagation method. Starting with a new heuristic method, mean-shift belief propagation (MSBP) that works iteratively with local weighted samples to infer max-marginals within a large or continuous state space, we further propose a novel data-driven MSBP (DDMSBP) based on recent work of smoothing-based optimization that is even more robust at finding a significant mode of the marginal density. We prove that the inference time for DDMSBP is bilinear in terms of the number of samples and the number of nodes in a graph for arbitrary unary potential functions as long as the pair-wise compatibility functions remain Gaussian. We demonstrate the effectiveness of our novel MSBP and DDMSBP methods through simulation and on five challenging computer vision applications: (1) multi-target tracking, (2) 2D articulated body tracking, (3) 3D deformable neuro-image registration, (4) detection of near-regular patterns in real-world images, and (5) perceptual grouping of 2D lattices in urban scenes. The main contributions of this thesis are: (1) the development and validation of a provable inference algorithm DDMSBP for PGMs with state of the art performance; and (2) a set of novel, robust and efficient solutions to five challenging computer vision problems. These solutions are achieved by incorporating our effective inference methods with group theory and domain knowledge into a graphical model framework. Our proposed inference tools and novel applications have demonstrated the power of MSBP and DDMSBP in diverse, high dimensional computer vision problems especially in computational symmetry.