Brian Potetz

Thesis Title: Efficient Statistical Methods for 3D Shape Inference
Degree Type: Ph.D. in Computer Science
Advisor(s): Tai Sing Lee
Graduated: May 2008

Abstract:

Visual inference is a complex and ambiguous problem, and these properties have presented a significant obstacle to developing effective algorithms for many visual tasks. In this thesis, I begin by developing a methodology for statistical inference that is particularly suited for the complex tasks of visual perception. The approach is based on Belief Propagation, a highly successful inference technique that has lead to notable progress in a number of statistical inference applications. Unfortunately, the computational complexity of belief propagation allows it to be applied to only fairly simple statistical distributions, thus excluding many of the rich statistical problems encountered in computer vision. In this thesis, I introduce a new technique to reduce the computational complexity of belief propagation from exponential to linear in the clique size of the underlying graphical model. These advancements allow us to efficiently solve inference problems that were previously intractable. I then apply this methodology to several visual tasks. In one example, I develop a statistical approach to the problem of estimating 3D shape from shading in a single image, a classic problem of computer vision that has been a subject of research since the lunar surface studies of the 1920's. Previous approaches typically have worked by forming a deterministic model of image formation and then attempting to invert this model. These approaches struggled with the nonlinearity and ambiguity inherent in the problem; the best algorithms were described as "generally poor" in a recent survey [109]. The statistical approach introduced here produces fairly convincing reconstructions, and also offers several novel flexibilities that previous approaches lack.

One difficulty faced by shape-from-shading and several other areas of computer vision is the ambiguity inherent in the problem. To produce successful statistical inference in an underconstrained problem, we must exploit a strong statistical prior. While previous applications of belief propagation could only be run using weaker, pairwise-connected models of spatial priors, the efficient techniques introduced here make more sophisticated approaches possible. Additionally, I address the issue of learning the parameters of spatial priors, by leveraging the power of efficient belief propagation towards efficient learning. These learned spatial priors are then applied successfully to image denoising and shape-from-shading.

Thesis Committee:
Tai Sing Lee (Chair)
John Lafferty
Ann Lee
Mike Lewicki
Alan Yuille (UCLA)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science