Real-time 3-D Scene Reconstruction

Abstract

This dissertation describes a complete system that captures image data from multiple stereoscopic camera pairs and reconstructs a 3-D model of the imaged scene in real-time. To achieve real-time rates, the system is organized in a distributed hierarchical fashion to maximize parallelism and uses algorithms that, in many instances, are suitable for direct implementation in digital hardware rather than software on a general purpose computer. At the lowest level of the hierarchy, image data is acquired from a single camera and processed to compensate for lens distortion and to apply rectification in preparation for stereo image processing. At the next level, data from pairs of cameras is matched to compute a dense stereoscopic disparity map from which 3-D surfaces are inferred and a mesh model is constructed. Finally, at the top level all of the individual 3-D mesh models are merged into a single 3-D model. If desired, the camera image data can be applied to the resultant 3-D model as a texture and the model re-rendered from a virtual camera viewpoint.

Previous 3-D research focuses on individual steps in this process (lens distortion correction, image rectification, stereoscopic disparity computation, and model building). This dissertation considers them instead in the context of a complete end-to-end system. Traditional approaches to model building begin with an unstructured "point cloud" that is neutral with respect to how the data was acquired; this allows model building to be studied independent of data acquisition but may miss some opportunities available in a more tightly coupled interface. By taking a broader view of the problems faced by the entire system, a novel algorithm for 3-D model building has been developed that takes advantage of the organization in the dense stereoscopic disparity map to efficiently build its model. The core of this novel algorithm is a method of evaluating linear regression error to fit a series of line segments to data points in a way that can be efficiently implemented directly in hardware.