Natasha Gelfand's Publications

Journal and conference papers

BibTeX for all papers.

Dynamic Geometry Registration
Niloy J. Mitra, Simon Flory, Maks Ovsjanikov, Natasha Gelfand, Leonidas Guibas and Helmut Pottmann
Symposium on Geometry Processing 2007
We propose an algorithm that performs registration of large sets of unstructured point clouds of moving and deforming objects without computing correspondences. Given as input a set of frames with dense spatial and temporal sampling, such as the raw output of a fast scanner, our algorithm exploits the underlying temporal coherence in the data to directly compute the motion of the scanned object and bring all frames into a common coordinate system. In contrast with existing methods which usually perform pairwise alignments between consecutive frames, our algorithm computes a globally consistent motion spanning multiple frames. We add a time coordinate to all the input points based on the ordering of the respective frames and pose the problem of computing the motion of each frame as an estimation of certain kinematic properties of the resulting space-time surface. By performing this estimation for each frame as a whole we are able to compute rigid inter-frame motions, and by adapting our method to perform a local analysis of the space-time surface, we extend the basic algorithm to handle registration of deformable objects as well. We demonstrate the performance of our algorithm on a number of synthetic and scanned examples, each consisting of hundreds of scans.
Video

Reassembling Fractures Objects by Geometric Matching
Qi-Xing Huang, Simon Flory, Natasha Gelfand, Michael Hofer and Helmut Pottmann
SIGGRAPH 2006
We present a system for automatic reassembly of broken 3D solids. Given as input digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our reconstruction pipeline consists of a graph-cuts based segmentation algorithm for identifying potential fracture surfaces, feature-based robust global registration for pairwise matching of fragments, and simultaneous constrained local registration of multiple fragments. We develop several new techniques in the area of geometry processing, including the novel integral invariants for computing multi-scale surface characteristics, registration based on forward search techniques and surface consistency, and a non-penetrating iterated closest point algorithm. We illustrate the performance of our algorithms on a number of real-world examples. motion.

Robust Global Registration
Natasha Gelfand, Niloy J. Mitra, Leonidas J. Guibas and Helmut Pottmann
Symposium on Geometry Processing, 2005
We present an algorithm for the automatic alignment of two 3D shapes (data and model), without any assumptions about their initial positions. The algorithm computes for each surface point a descriptor based on local geometry that is robust to noise. A small number of feature points are automatically picked from the data shape according to the uniqueness of the descriptor value at the point. For each feature point on the data, we use the descriptor values of the model to find potential corresponding points. We then develop a fast branch-and-bound algorithm based on distance matrix comparisons to select the optimal correspondence set and bring the two shapes into a coarse alignment. The result of our alignment algorithm is used as the initialization to ICP (iterative closest point) and its variants for fine registration of the data to the model. Our algorithm can be used for matching shapes that overlap only over parts of their extent, for building models from partial range scans, as well as for simple symmetry detection, and for matching shapes undergoing articulated motion.

Fragments of the City: Stanford's Digital Forma Urbis Romae Project
David Koller, Jennifer Trimble, Tina Najbjerg, Natasha Gelfand, and Marc Levoy
Proceedings of the Third Williams Symposium on Classical Architecture, Journal of Roman Archaeology suppl., 2005
In this article, we summarize the Stanford Digital Forma Urbis Project work since it began in 1999 and discuss its implications for representing and imaging Rome. First, we digitized the shape and surface of every known fragment of the Severan Marble Plan using laser range scanners and digital color cameras; the raw data collected consists of 8 billion polygons and 6 thousand color images, occupying 40 gigabytes. These range and color data have been assembled into a set of 3D computer models and high-resolution photographs - one for each of the 1,186 marble fragments. Second, this data has served in the development of fragment matching algorithms; to date, these have resulted in over a dozen highly probable, new matches. Third, we have gathered the Project's 3D models and color photographs into a relational database and supported them with archaeological documentation and an up-to-date scholarly apparatus for each fragment. This database is intended to be a public, web-based, research and study tool for scholars, students and interested members of the general public alike; as of this writing, 400 of the surviving fragments are publicly available, and the full database is scheduled for release in 2005. Fourth, these digital and archaeological data, and their availability in a hypertext format, have the potential to broaden the scope and type of research done on this ancient map by facilitating a range of typological, representational and urbanistic analyses of the map, some of which are proposed here. In these several ways, we hope that this Project will contribute to new ways of imaging Rome.

Shape Segmentation Using Local Slippage Analysis
Natasha Gelfand and Leonidas J. Guibas
Symposium on Geometry Processing, 2004
We propose a method for segmentation of 3D scanned shapes into simple geometric parts. Given an input point cloud, our methodc omputes a set of components which possess one or more slippable motions: rigid motions which, when applied to a shape, slide the transformed version against the stationary version without forming any gaps. We show how to determine the slippable motions of a given shape by computing eigenvalues of a certain symmetric matrix derived from the points and normals of the shape. Our algorithm then discovers slippable components in the input data by computing local slippage signatures at a set of points of the input and iteratively aggregating regions with matching slippable motions.

Registration of Point Cloud Data from a Geometric Optimization Perspective
Niloy J. Mitra, Natasha Gelfand, Helmut Pottmann and Leonidas J. Guibas
Symposium on Geometry Processing, 2004
We propose a framework for pairwise registration of shapes represented by point cloud data (PCD). We assume that the points are sampled from a surface and formulate the problem of aligning two PCDs as a minimization of the squared distance between the underlying surfaces. Local quadratic approximants of the squared distance function are used to develop a linear system whose solution gives the best aligning rigid transform for the given pair of point clouds. The rigid transform is applied and the linear system corresponding to the new orientation is build. This process is iterated until it converges. The point-to-point and the point-to-plane Iterated Closest Point (ICP) algorithms can be treated as special cases in this framework. Our algorithm can align PCDs even when they are placed far apart, and is experimentally found to be more stable than point-to-plane ICP. We analyze the convergence behavior of our algorithm and of point-to-point and point-to-plane ICP under our proposed framework, and derive bounds on their rate of convergence. We compare the stability and convergence properties of our algorithm with other registration algorithms on a variety of scanned data.

Geometrically Stable Sampling for the ICP Algorithm
Natasha Gelfand, Leslie Ikemoto, Szymon Rusinkiewicz, and Marc Levoy
Fourth International Conference on 3D Digital Imaging and Modeling, 2003
The Iterative Closest Point (ICP) algorithm is a widely used method for aligning three-dimensional point sets. The quality of alignment obtained by this algorithm depends heavily on choosing good pairs of corresponding points in the two datasets. If too many points are chosen from featureless regions of the data, the algorithm converges slowly, finds the wrong pose, or even diverges, especially in the presence of noise or miscalibration in the input data. In this paper, we describe a method for detecting uncertainty in pose, and we propose a point selection strategy for ICP that minimizes this uncertainty by choosing samples that constrain potential unstable transformations.

A Hierarchical Method for Aligning Warped Meshes
Leslie Ikemoto, Natasha Gelfand, and Marc Levoy
Fourth Internaltional Conference on 3D Digital Imaging and Modeling, 2003
Current alignment algorithms for registering range data captured from a 3D scanner assume that the range data depicts identical geometry taken from different views. However, in the presence of scanner calibration errors, the data will be slightly warped. These warps often cause current alignment algorithms to converge slowly, find the wrong alignment, or even diverge. In this paper, we present a method for aligning warped range data represented by polygon meshes. Our strategy can be characterized as a coarse-to-fine hierarchical approach, where we assume that since the warp is global, we can compensate for it by treating each mesh as a collection of smaller piecewise rigid sections, which can translate and rotate with respect to each other. We split the meshes subject to several constraints, in order to ensure that the resulting sections converge reliably.

Thesis:

Feature analysis and registration of scanned surfaces.

Advisors: Leonidas J. Guibas and Marc Levoy
Stanford University, September 2006

Home

	Dynamic Geometry Registration Niloy J. Mitra, Simon Flory, Maks Ovsjanikov, Natasha Gelfand, Leonidas Guibas and Helmut Pottmann Symposium on Geometry Processing 2007 We propose an algorithm that performs registration of large sets of unstructured point clouds of moving and deforming objects without computing correspondences. Given as input a set of frames with dense spatial and temporal sampling, such as the raw output of a fast scanner, our algorithm exploits the underlying temporal coherence in the data to directly compute the motion of the scanned object and bring all frames into a common coordinate system. In contrast with existing methods which usually perform pairwise alignments between consecutive frames, our algorithm computes a globally consistent motion spanning multiple frames. We add a time coordinate to all the input points based on the ordering of the respective frames and pose the problem of computing the motion of each frame as an estimation of certain kinematic properties of the resulting space-time surface. By performing this estimation for each frame as a whole we are able to compute rigid inter-frame motions, and by adapting our method to perform a local analysis of the space-time surface, we extend the basic algorithm to handle registration of deformable objects as well. We demonstrate the performance of our algorithm on a number of synthetic and scanned examples, each consisting of hundreds of scans.	Video
	Reassembling Fractures Objects by Geometric Matching Qi-Xing Huang, Simon Flory, Natasha Gelfand, Michael Hofer and Helmut Pottmann SIGGRAPH 2006 We present a system for automatic reassembly of broken 3D solids. Given as input digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our reconstruction pipeline consists of a graph-cuts based segmentation algorithm for identifying potential fracture surfaces, feature-based robust global registration for pairwise matching of fragments, and simultaneous constrained local registration of multiple fragments. We develop several new techniques in the area of geometry processing, including the novel integral invariants for computing multi-scale surface characteristics, registration based on forward search techniques and surface consistency, and a non-penetrating iterated closest point algorithm. We illustrate the performance of our algorithms on a number of real-world examples. motion.
	Robust Global Registration Natasha Gelfand, Niloy J. Mitra, Leonidas J. Guibas and Helmut Pottmann Symposium on Geometry Processing, 2005 We present an algorithm for the automatic alignment of two 3D shapes (data and model), without any assumptions about their initial positions. The algorithm computes for each surface point a descriptor based on local geometry that is robust to noise. A small number of feature points are automatically picked from the data shape according to the uniqueness of the descriptor value at the point. For each feature point on the data, we use the descriptor values of the model to find potential corresponding points. We then develop a fast branch-and-bound algorithm based on distance matrix comparisons to select the optimal correspondence set and bring the two shapes into a coarse alignment. The result of our alignment algorithm is used as the initialization to ICP (iterative closest point) and its variants for fine registration of the data to the model. Our algorithm can be used for matching shapes that overlap only over parts of their extent, for building models from partial range scans, as well as for simple symmetry detection, and for matching shapes undergoing articulated motion.
	Fragments of the City: Stanford's Digital Forma Urbis Romae Project David Koller, Jennifer Trimble, Tina Najbjerg, Natasha Gelfand, and Marc Levoy Proceedings of the Third Williams Symposium on Classical Architecture, Journal of Roman Archaeology suppl., 2005 In this article, we summarize the Stanford Digital Forma Urbis Project work since it began in 1999 and discuss its implications for representing and imaging Rome. First, we digitized the shape and surface of every known fragment of the Severan Marble Plan using laser range scanners and digital color cameras; the raw data collected consists of 8 billion polygons and 6 thousand color images, occupying 40 gigabytes. These range and color data have been assembled into a set of 3D computer models and high-resolution photographs - one for each of the 1,186 marble fragments. Second, this data has served in the development of fragment matching algorithms; to date, these have resulted in over a dozen highly probable, new matches. Third, we have gathered the Project's 3D models and color photographs into a relational database and supported them with archaeological documentation and an up-to-date scholarly apparatus for each fragment. This database is intended to be a public, web-based, research and study tool for scholars, students and interested members of the general public alike; as of this writing, 400 of the surviving fragments are publicly available, and the full database is scheduled for release in 2005. Fourth, these digital and archaeological data, and their availability in a hypertext format, have the potential to broaden the scope and type of research done on this ancient map by facilitating a range of typological, representational and urbanistic analyses of the map, some of which are proposed here. In these several ways, we hope that this Project will contribute to new ways of imaging Rome.
	Shape Segmentation Using Local Slippage Analysis Natasha Gelfand and Leonidas J. Guibas Symposium on Geometry Processing, 2004 We propose a method for segmentation of 3D scanned shapes into simple geometric parts. Given an input point cloud, our methodc omputes a set of components which possess one or more slippable motions: rigid motions which, when applied to a shape, slide the transformed version against the stationary version without forming any gaps. We show how to determine the slippable motions of a given shape by computing eigenvalues of a certain symmetric matrix derived from the points and normals of the shape. Our algorithm then discovers slippable components in the input data by computing local slippage signatures at a set of points of the input and iteratively aggregating regions with matching slippable motions.
	Registration of Point Cloud Data from a Geometric Optimization Perspective Niloy J. Mitra, Natasha Gelfand, Helmut Pottmann and Leonidas J. Guibas Symposium on Geometry Processing, 2004 We propose a framework for pairwise registration of shapes represented by point cloud data (PCD). We assume that the points are sampled from a surface and formulate the problem of aligning two PCDs as a minimization of the squared distance between the underlying surfaces. Local quadratic approximants of the squared distance function are used to develop a linear system whose solution gives the best aligning rigid transform for the given pair of point clouds. The rigid transform is applied and the linear system corresponding to the new orientation is build. This process is iterated until it converges. The point-to-point and the point-to-plane Iterated Closest Point (ICP) algorithms can be treated as special cases in this framework. Our algorithm can align PCDs even when they are placed far apart, and is experimentally found to be more stable than point-to-plane ICP. We analyze the convergence behavior of our algorithm and of point-to-point and point-to-plane ICP under our proposed framework, and derive bounds on their rate of convergence. We compare the stability and convergence properties of our algorithm with other registration algorithms on a variety of scanned data.
	Geometrically Stable Sampling for the ICP Algorithm Natasha Gelfand, Leslie Ikemoto, Szymon Rusinkiewicz, and Marc Levoy Fourth International Conference on 3D Digital Imaging and Modeling, 2003 The Iterative Closest Point (ICP) algorithm is a widely used method for aligning three-dimensional point sets. The quality of alignment obtained by this algorithm depends heavily on choosing good pairs of corresponding points in the two datasets. If too many points are chosen from featureless regions of the data, the algorithm converges slowly, finds the wrong pose, or even diverges, especially in the presence of noise or miscalibration in the input data. In this paper, we describe a method for detecting uncertainty in pose, and we propose a point selection strategy for ICP that minimizes this uncertainty by choosing samples that constrain potential unstable transformations.
	A Hierarchical Method for Aligning Warped Meshes Leslie Ikemoto, Natasha Gelfand, and Marc Levoy Fourth Internaltional Conference on 3D Digital Imaging and Modeling, 2003 Current alignment algorithms for registering range data captured from a 3D scanner assume that the range data depicts identical geometry taken from different views. However, in the presence of scanner calibration errors, the data will be slightly warped. These warps often cause current alignment algorithms to converge slowly, find the wrong alignment, or even diverge. In this paper, we present a method for aligning warped range data represented by polygon meshes. Our strategy can be characterized as a coarse-to-fine hierarchical approach, where we assume that since the warp is global, we can compensate for it by treating each mesh as a collection of smaller piecewise rigid sections, which can translate and rotate with respect to each other. We split the meshes subject to several constraints, in order to ensure that the resulting sections converge reliably.