New Approaches to Reconstructing Geometric Models From Noisy Measurements

Abstract

This dissertation is comprised of four different studies in the areas of shape/surface/trajectory reconstruction based on point cloud data (potentially with time stamps) and sensor localization (with measurements of distances among neighboring sensors) in a noisy environment on a distributed system. A noise resistant ellipse/spheroid fitting algorithm is discussed first, with an innovative objective function that provides more accurate axial direction estimation in noisy environments. This new objective function is combined with an efficient iterative algorithm with a correction term so that it can obtain accurate axial estimation as well as accurate fitting of the size of the ellipse/spheroid. Secondly, to better deal with outliers in ellipse fitting, and more generally, in curve and surface fitting, a hybrid outlier detection algorithm is proposed, combining both proximity-based and model-based outlier detection techniques. This hybrid technique can effectively eliminate outliers of various types, and considerably improve the robustness of ellipse/spheroid fitting for scenarios with large portions of outliers and high levels of inlier noise. Thirdly, the shape reconstruction is generalized to shape-trajectory reconstruction of rigid bodies, from distributively collected, asynchronous point cloud data with time stamps. An energy-minimization scheme is first proposed to solve the trajectory reconstruction problem of rigid bodies with known shape parameters, assuming that the rigid body moves in an energy efficient manner, with an acceleration upper limit. Then, this method is generalized to the case with unknown rigid body shape parameters, employing cross-validation techniques to determine the best parameter hypothesis. Finally, a series of techniques to improve the spring-model-based sensor localization algorithm are proposed, including dimension expansion, which solves a 2-D sensor localization problem in 3-D space to reduce the chance of "folding'' phenomena, an Lp spring potential function that generalizes quadratic potential of Hooke spring to arbitrary power functions, and a customized spring force with "lock-in'' mode that provides a compromise between incremental sensor localization and concurrent sensor localization to achieve rapid convergence.