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
  • Yanxi Liu, Committee Chair
  • Robert T Collins, Committee 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.