IRIS-95-341

Surface Approximation of Complex Objects

Chia-Wei Liao

October 1995

Building computer models of existing 3-D objects from sensor data is an interesting and difficult problem. We introduce a surface fitting scheme which, given data points collected from sensors, is able to perform segmentation on multiple complex objects and gives an analytical description as a result. There are two parts in this work. \\ First, assuming there is only one underlying object and it is of Genus 0, we use a deformable model to approximate a cloud of 3D points by a B-spline surface. The user (or the system itself) provides an initial simple surface, such as a closed cylinder, which is subject to internal forces (describing implicit continuity properties such as smoothness) and external forces which attract it toward the data points. The problem is cast in terms of energy minimization. We solve this non-convex optimization problem by using the Powell algorithm. The variables are the coordinates of the surface control points. The number of variables processed by Powell at any time is controlled. We keep the time and space complexities in check by a coarse to fine approach, a partitioning scheme, and breaking this surface fitting problem up into several curve fitting sub-problems. This methodology leads to a reasonable complexity, robustness, and good numerical stability. We handle closed surfaces by decomposing an object into two caps and an open cylinder, which are smoothly connected. The process is controlled by two parameters only, which are constant for all experiments. This part is the engine of the whole system. \\ Second, based on the surface fitting engine, we propose an approach that applies automatically more than one surface to approximate multiple objects. Using (1) the residual data points, (2) the bad parts of the fitting curve (surface), and (3) appropriate Boolean operations, our approach is able to approximate objects more complex than Genus 0 (objects with holes or cavities), and it performs segmentation by itself if there is more than one object. A 3-D surface representation for complex multipart objects is obtained without prior knowledge on the topology. We present experiments on 2D and 3D data points sampled from multiple complex objects \\ We show results on real range images to illustrate the applicability of our approach, and it gives a C0 (and C1 if needed) continuous analytical description of the data. \\ \\