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.