J-Angelo Beraldin, National Research Council Canada Ottawa, Ontario, Canada
Title: Evaluating the performance of 3-D active vision systems
Active three-dimensional vision is concerned with extracting information from the geometry and the texture of the visible surfaces in a scene, reasoning about the data and finally, communicating the results. With the recent technological advances made in electronics, photonics, computer vision and computer graphics, it is now possible to construct reliable, high resolution and accurate three-dimensional active range cameras. In order to take full advantage of these vision systems, one must understand not only their advantages but also their limitations. This presentation covers some important issues that must be addressed before embarking in a 3-D modeling task or project. After reviewing the basic physical principles that underline the majority of these 3-D vision systems, resolution, uncertainty and accuracy of 3-D information measurement in the context of close-range measurement are covered. A number of examples illustrating these issues are shown. The goal is not to survey all commercial 3-D vision systems or present an exhaustive list of tests of the systems chosen for this paper. Instead, some theory about 3-D sensing is presented and is accompanied by selected results that should give the reader some pointers in order to become more critical when picking a 3-D vision system. Finally, in order to help the readers further their study of this topic; a number of references are listed.
Frederic Cazals, INRIA Sophia-Antipolis, France
Title: Point clouds, Surface Reconstruction, and Differential Geometry: two selected topics.
Surface Reconstruction is the process which consists of turning a 3D point cloud into a surface, either triangulated, defined implicitly, or defined parametrically. most surface reconstruction methods rely at some point upon estimates of differential quantities, so that several interesting questions lie at the crossroads of surface reconstruction and applied differential geometry. this talk will discuss two of them. in the first part, we will recall the fundamentals of the so-called natural interpolation method, and will discuss its application to surface reconstruction. in the second part, we will present a provably good algorithm to estimate local differential properties of any fixed order over a sampled smooth surface. the method consists of fitting the local representation of the manifold using a jet ---i.e. a truncated Taylor expansion, using either a polynomial interpolation or approximation.
Tamal K. Dey, Ohio State University
Title: Cocone algorithm and its variants for surface reconstruction
Ye Duan and Hong Qin, State University of New York at Stony Brook
Title: 2.5D Active Surface for Surface Reconstruction
In this paper, we present a new deformable model --- 2.5D Active Surface --- that is capable of directly extracting shape geometry from 3D unorganized point clouds datasets. The reconstructed surfaces are either open or closed. Furthermore, the new model can reconstruct and discover non-manifold geometry hidden in the point-cloud dataset. Our algorithm starts from a simple seed (e.g. a triangle) that can be automatically initialized, and always enlarges the model boundary outwards along its tangent direction suggested by the underlying dataset. This mechanism ensures that our novel models "flow" directly over the data boundary through the expansion of its bounding contour. To maintain the regularity of the model and the stability of the numerical integration process, commonly used mesh optimization techniques are employed throughout the deformation process. In addition, the new model can recover fine details of the underlying shape through local/adaptive refinement. We demonstrate both the accuracy and the robustness of our algorithm through a number of experiments on both real and synthetic datasets.
Yates Fletcher, Geomagic.com
Most commercial scanners acquire their data from a sequence of "shots" during which the scanner and the object are fixed but between which one or the other is moved in order to achieve full coverage of the surface. As a consequence, the raw data from these scans all lie in different coordinate systems and require some computational process to accurately place them in a single coordinate system before further processing can proceed. This is known as the registration problem for multiple partial scans, and a robust solution to this problem is one the keys to engineering reliable optical scanning systems for inspection, metrology, and reverse engineering applications. Current methods rely on heuristics that often break down when the number of scans is large, and tend to be quite slow to converge.
We define a merge as a solution to the registration problem for an arbitrary subset of the scans, and describe merge implementations in terms of ICP alignments of scan pairs. A full registration can now be specified by a tree whose nodes represent the merge of their children. The leaves of this "merge" tree are the individual scans and the root is the completed registration. If it is binary the tree describes a schedule of pair alignments yielding the registration. At the other extreme a depth one tree represents a global merge of all the scans. Each merge contains the possibility of alignment errors that may affect the accuracy of the parent merge and so propogate up the tree. As the degree of the nodes increases we can expect the depth of the tree to decrease, thus minimizing these cumulative effects. On the other hand, when the merge involves more than two scans we expect an increase in complexity and a decrease in stability of the calculations as the number of scans in the merge increases. The merge tree regime allows us to consider schedules which balance these considerations.
We consider the problem of constructing a merge tree from information provided by a graph whose nodes are the scans and whose edges are weighted by an a priori estimate of the registration potential of the corresponding pair. We introduce the notions of overlap strength and lockability to specify registration potential.
Outline
Herbert Edelsbrunner, Arts and Sciences Professor of Computer Science and Mathematics, Duke University
Title: The Importance of Topology in Surface Reconstruction
The original Wrap algorithm for surface reconstruction is based on discrete counterparts of Morse theoretic ideas. This talk presents both the intuition derived from the smooth category and the translation of that intuition into the combinatorial framework expressed by the Voronoi and Delaunay diagrams of the data. By the end of the talk we will have given an effective algorithm whose result is defined by a rather simple mathematical formalism.
Daniel Freedman, Assistant Professor of Computer Science Rensselaer Polytechnic Institute
Title: Surface and Manifold Reconstruction in Arbitrary Embedding Spaces
A new algorithm for combinatorial surface reconstruction is presented. This algorithm's novelty derives from two sources. First, it may be applied to surfaces embedded in arbitrary dimensional Hilbert spaces; this allows for the application of the algorithm to a wider variety of surfaces, including the class of non-orientable surfaces (such as the Klein Bottle). Second, the algorithm may be generalized to the case reconstruction of manifolds, of arbitrary dimension and codimension. An incremental technique is used to reconstruct the surface / manifold; as a result, the algorithm's complexity, as a function of the number of simplices, is independent of the dimension of the manifold or embedding space.
Ping Fu, CEO and President of Raindrop Geomagic
Title: Surface Reconstruction in Commercial Software
This talk presents the landscape of commercial software that uses and benefits from the latest surface reconstruction research. Based on applications in various industries, it illustrates the different requirements, such as software speed, accuracy of reconstruction, degree of automation, and reliability of implicit or explicit feature recognition. The talk concludes with some challenging problems that need further research.
Title: Surface Reconstruction based on a dynamical system
Title: Tight Cocone : A Water-tight Surface Reconstructor
Surface reconstruction from unorganized sample points is an important problem in computer graphics, computer aided design, medical imaging and solid modeling. Recently a few algorithms have been developed that have theoretical guarantee of computing a topologically correct and geometrically close surface under certain condition on sampling density. Unfortunately, this sampling condition is not always met in practice due to noise, non-smoothness or simply due to inadequate sampling. This leads to undesired holes and other artifacts in the output surface. Certain CAD applications such as creating a prototype from a model boundary require a water-tight surface, i.e., no hole should be allowed in the surface. In this paper we describe a simple algorithm called Tight Cocone that works on an initial mesh generated by a popular surface reconstruction algorithm and fills up all holes to output a water-tight surface. In doing so, it does not introduce any extra points and produces a triangulated surface interpolating the input sample points. In support of our method we present experimental results with a number of difficult data sets.
Title: Using Power Diagrams to Compute Implicitly Defined Surfaces
Thouis Jones, MIT LCS Graphics Group
Title: Non-Iterative, Feature-Preserving Mesh Smoothing
Thouis R. Jones, Frédo Durand, Mathieu Desbrun
To appear in the proceedings of SIGGRAPH 2003
With the increasing use of geometry scanners to create 3D models, there is a rising need for fast and robust mesh smoothing to remove inevitable noise in the measurements. While most previous work has favored diffusion-based iterative techniques for feature-preserving smoothing, we propose a radically different approach, based on robust statistics and local first-order predictors of the surface. The robustness of our local estimates allows us to derive a \emph{non-iterative} feature-preserving filtering technique applicable to arbitrary ``triangle soups''. We demonstrate its simplicity of implementation and its efficiency, which makes it an excellent solution for smoothing large, noisy, and non-manifold meshes.
Marc Levoy, Stanford University,
Leader of the Digital Michelangelo Project
Title: Why is 3D scanning hard?
Improvements in optical rangefinding technology have made it easy to acquire dense 3D samples of an object or scene. However, a fully automated procedure for assembling this data to create a geometric model still eludes us. This is especially true for large or complicated objects scanned under non-laboratory conditions. For example, although Stanford's Digital Michelangelo Project produced some nice models, it did not achieve many of its stated objectives.
In this talk, I briefly survey the unsolved problems of 3D scanning. For some of these problems, well defined solutions exist, and steady progress can be made on them. Examples of this type include calibration of scanning platforms, multi-view registration, surface reconstruction, view planning, and the handling of large datasets. For other problems, solutions exist but the problem is usually badly conditioned due to noise. Examples of this type include multi-view registration in the presence of scanner miscalibration, estimation of surface reflectance, and the scanning of optically uncooperative materials. In still other cases, the problem itself is ill-posed, admitting multiple correct answers. Classic examples of this type are surface reconstruction in the presence of missing data (i.e. holes), and estimation of surface shape and reflectance in the presence of interreflections or subsurface scattering. Finally, there are problems for which no good solutions exist, such as scanning geometrically convoluted objects, and insuring safety for the objects being scanned.
I end with a (mostly) upbeat assessement of the long-term prospects for 3D scanning and some predictions concerning its likely impact on industry and popular culture.
T. J. Peters,University of Connecticut
Title: Ambient Isotopy for Topological Equivalence in Surface Reconstruction
Topological equivalence for surface reconstruction has attracted considerable attention. We first show why traditional topological equivalence based upon homeomorphisms is inadequate and why the stronger equivalence relying upon ambient isotopy should be preferred. We then show how an established sampling and reconstruction technique does meet this stronger equivalence. We continue to offer new techniques for ambient isotopic approximations -- which need not be piecewise linear. The first proof relies upon the medial axis, whereas the second technique does not, using instead an analysis of focal points. Advantages of each will be described.
This talk describes two sets of collaborations; 1. with N. Amenta and A. C. Russell and 2. with K. Abe and T. Sakkalis.
Marc Pollefeys , University of North Carolina
Title: Reconstructing 3D surfaces from 2D images
In this talk a complete approach to reconstruct 3D surfaces from camera images is presented. The approach deals with uncalibrated image sequences acquired with a hand-held camera. Based on tracked or matched features the relation between multiple views are computed. From this both the structure of the scene and the motion of the camera are retrieved. The ambiguity on the reconstruction is restricted from projective to metric through self-calibration. A flexible multi-view stereo matching scheme is used to obtain a dense estimation of the surface geometry. From the computed data different types of visual models are constructed. Both 3D surface models and lightfield representations can be constructed. The recovered information can also be used to augment video footage with virtual objects. Some ongoing research towards real-time reconstruction of dynamic events from multiple cameras will also be presented.
Holly Rushmeier, IBM Watson Research Center
Title: 3D Scanning for Cultural Heritage Applications
Szymon Rusinkiewicz,Princeton University
Title: Fast and Flexible 3D Scanning
The digitization of the 3D shape of real objects is a rapidly expanding field, with applications in design, manufacturing, and mapping spaces such as buildings and caves. This talk will describe recent research aimed at increasing the speed and flexibility of 3D scanning systems. Two scanner designs will be presented, one based on active temporal stereo and the other based on projected structured light with stripe boundary coding. Both are based on a space-time stereo framework, in which correspondences between two cameras or between a camera and projector are obtained by correlating windows with extent in both space and time. The scanners are the first stage in a 3D model acquisition pipeline, which also includes algorithms for aligning and merging successive range images. The talk will discuss the value of having the entire pipeline operate in real time, which allows the user to see holes in the model and determine when the object has been completely covered. Results are presented from a prototype that incorporates 60 Hz. structured-light rangefinder, a real-time variant of ICP (iterative closest points) for alignment, and point-based merging and rendering algorithms.
Claudio T. Silva, Oregon Health & Science University
Title: Using Points for Rendering and Modeling Surfaces
Point sets are emerging as a robust technique for representing surfaces. The primary appeal of point sets is their generality: every shape can be represented by a set of points on its boundary, where the degree of accuracy typically depends only on the number of points.
In order to model 3D surfaces, it is necessary to develop a mathematical definition (and algorithm) for attaching a topology and geometric shape to the set of points. A natural way to do this is to use the inherent spatial interrelation among the points as implicit connectivity information to define the manifolds. This can be non-trivial since it is unclear what spacing of points represents connected or disconnected pieces of the surface.
In this talk, we will present some recent techniques for point-based modeling and rendering of surfaces. We believe that the importance of point-set representation is likely to play an increasing role in 3D geometric modeling. Part of the reason is that although considerable research has been devoted to developing and optimizing the ``mesh-based world'', using meshes is unnatural in several applications (e.g., 3D photography).
Joint work with Marc Alexa, Daniel Cohen-Or, and Shachar Fleishman.
Hongkai Zhao , University of California
Title: Computer Visualization using Partial Differential Equations and Implicit Surfaces
I will present mathematical formulations and efficient numerical algorithms for the construction, deformation and operation of implicit surfaces using variational methods and partial differential equations. In particular I will discuss surface resonctruction from unorganized data points using distance contours and minimal surfaces and solving partial differential equations on moving interfaces
DIMACS Homepage