EFFICIENT MEAN-SHIFT BELIEF PROPAGATION AND ITS APPLICATIONS IN COMPUTER VISION
Open Access
- Author:
- Park, Minwoo
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 08, 2010
- Committee Members:
- Yanxi Liu, Dissertation Advisor/Co-Advisor
Yanxi Liu, Committee Chair/Co-Chair
Robert T Collins, Committee Chair/Co-Chair
Jesse Louis Barlow, Committee Member
Runze Li, Committee Member - Keywords:
- MRF
Inference
Graphical Model
Belief Propagation
Computer Vision - Abstract:
- 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.