SURFACE APPROXIMATION OF A CLOUD OF 3D POINTS

We present an implementation of deformable models to approximate a 3-D surface given by a cloud of 3D points. It is an extension of our prev ious work on ''B-snakes'' (S. Menet, P. Saint-Marc, and G. Medioni, in Proceedings of Image Understanding Workshop, Pittsburgh, 1990, pp. 72 0-726; and C. W. Liao and G. Medioni, in Proceedings of International Conference on Pattern Recognition, Hague, Netherlands, 1992, pp. 745-7 48), which approximates curves and surfaces using B-splines. The user (or the system itself) provides an initial simple surface, such as clo sed cylinder, which is subject to internal forces (describing implicit continuity properties such as smoothness) and external forces which a ttract it toward the data points. The problem is cast in terms of ener gy minimization. We solve this nonconvex optimization problem by using the web-known Powell algorithm which guarantees convergence and does not require gradient information. The variables are the positions of t he control points. The number of control points processed by Powell at one time is controlled. This methodology leads to a reasonable comple xity, robustness, and good numerical stability. We keep the time and s pace complexities in check through a coarse-to-fine approach and a par titioning scheme. We handle closed surfaces by decomposing an object i nto two caps and an open cylinder, smoothly connected. The process is controlled by two parameters only, which are constant for all our expe riments. We show results on real range images to illustrate che applic ability of our approach. The advantages of this approach are that it p rovides a compact representation of the approximated data and lends it self to applications such as nonrigid motion tracking and object recog nition. Currently, our algorithm gives only a CO continuous analytical description of the data, but because the output of our algorithm is i n rectangular mesh format, a C-1 or C-2 surface can be constructed eas ily by existing algorithms (F. J. M. Schmitt, B. A. Barsky, and W.-H. Du, in ACM SIGGRAPH 86, pp. 179-1988). (C) 1995 Acadcmic Press, Inc.