| Three dimensional data capture is an essential tool in mechanical engineering and graphics arts, and is currently gaining popularity in fields as widespread as archaeology, architecture, biology, dentistry, and medicine. Typical applications include reverse engineering, inspection, measurement, preservation of archival records, and facility mapping. To capture an object or scene, a range scanner acquires dense range images from multiple viewpoints, which must then be registered within a global coordinate frame to make a useful parametric model. This thesis will discuss research into the design of algorithms for large scale registration of 3D surfaces. Three aspects of this research will be described: automatic registration using invariant features, stable registration in the presence of missing data, and registration of multiple views.; The registration process typically starts with a manual rough alignment, followed by an automatic procedure that iteratively minimizes the distance between the two surfaces. To reduce the requirement that the initial rough alignment be known, this thesis introduces the use of invariant features to guide the automatic alignment process. In particular, surface patches are matched with each other based on both their shape similarity and their relative positions in space. The result is an algorithm that is more fully automatic and less sensitive to errors in the initial relative alignment.; One of the most difficult problems in surface registration arises from surface regions are seen in only one of two views. These missing surface patches may be caused by differences in the field of view or occlusions that occur when the sensor is placed at different viewpoints. But sometimes the missing surface patches are caused by limitations in the sensor, such as poor signal quality due to unreflective, specular, or distant surfaces. These missing data are a valuable source of information, as long as their cause can be identified. In this thesis, geometric reasoning is used together with a sensor response model to determine the most likely cause of each missing data and thereby estimate more accurate joint likelihoods. This use of missing data is shown to contribute to the accurate registration of surfaces where more than 90% of the data readings are outliers.; When multiple pairs of views are successively registered, registration errors accumulate. For 3D map building and other large scale problems, the registration problem may consist of hundreds of views and hundreds of millions of data points. In this situation, it is better to separate the local problem of pairwise registration on neighboring views from the global problem of distribution of accumulated errors. This thesis discusses how to perform geometric optimization with respect to the relative rotations and translations defined on a graph of neighboring views. By decomposing the graph into a set of cycles, the optimal parameters can be solved in closed form, and solutions for each cycle can be combined in an iterative procedure that propagates the solution across the entire graph. This optimization on a graph of rigid links is simple, flexible and scales well to large scale problems. |
