Automatic Three-dimensional Modeling from Reality

Abstract

In this dissertation, we develop techniques to fully automate the process of constructing a digital, three-dimensional (3D) model from a set of 3D views of a static scene obtained from unknown viewpoints. Since 3D sensors only capture scene structure from a single viewpoint, multiple views must be combined to create a complete model. Existing methods require measurement of the sensor viewpoints or manual view registration. Given a set of 3D views, the challenge is to align the views in a common coordinate system without knowing the original sensor viewpoints or even which views overlap one another. This problem is analogous to assembling a jigsaw puzzle in 3D. The views are the puzzle pieces, and the problem is to correctly assemble the pieces without even knowing what the puzzle is supposed to look like. Our approach uses pair-wise surface matching to align pairs of views. These pair-wise matches, some of which will be incorrect, are stored as edges in a graph that contains a node for each view. A sub-graph of this graph is a model hypothesis. Our goal is to find a model hypothesis that connects all the views and contains only correct matches. First, we develop a framework for evaluating the quality of model hypotheses, using maximum likelihood estimation to learn a probabilistic model of pair-wise registration success. This method provides a principled way to combine multiple measures of registration accuracy. We then extend this local quality measure to form a global measure of model quality. Next, we describe two classes of algorithms for robustly searching the large space of possible models for the best model hypothesis. Our approach can detect situations in which no solution exists, outputting a set of model parts if a single model using all the views cannot be found. We show results for a large collection of automatically modeled scenes and demonstrate that our algorithm works independently of scene size and the type of range sensor used.