|
 ABSTRACT
Point clouds are one of the most primitive and fundamental surface representations. A popular source of point clouds are three dimensional shape acquisition devices such as laser range scanners. Another important field where point clouds are found is in the representation of high-dimensional manifolds by samples. With the increasing popularity and very broad applications of this source of data, it is natural and important to work directly with this representation, without having to go to the intermediate and sometimes impossible and distorting steps of surface reconstruction. A geometric framework for comparing manifolds given by point clouds is presented in this paper. The underlying theory is based on Gromov-Hausdorff distances, leading to isometry invariant and completely geometric comparisons. This theory is embedded in a probabilistic setting as derived from random sampling of manifolds, and then combined with results on matrices of pairwise geodesic distances to lead to a computational implementation of the framework. The theoretical and computational results here presented are complemented with experiments for real three dimensional shapes.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
E. Arias-Castro, D. Donoho, and X. Huo, "Near-optimal detection of geometric objects by fast multiscale methods," Stanford Statistics Department TR, 2003.
|
| |
2
|
M. Belkin and P. Niyogi, "Laplacian eigenmaps for dimensionality reduction and data representation." University of Chicago CS TR-2002-01, 2002.
|
| |
3
|
J-D. Boissonnat and F. Cazals, in A. Chalmers and T-M. Rhyne, Editors, EUROGRAPHICS '01, Manchester, 2001.
|
| |
4
|
M. Botsch, A. Wiratanaya, and L. Kobbelt, EUROGRAPHICS Workshop on Rendering, 2002.
|
| |
5
|
D. Burago, Y. Burago, and S. Ivanov, A Course in Metric Geometry, AMS Graduate Studies in Math., Vol. 33.
|
| |
6
|
D. Burago and B. Kleiner, Geom. Funct. Anal.8, pp. 273--282, 1998.
|
| |
7
|
D. Burago and B. Kleiner, Geom. Funct. Anal.12, pp 80--92, 2002.
|
| |
8
|
G. Carlsson, A. Collins, L. Guibas, and A. Zomorodian, "Persistent homology and shape description I, preprint, Stanford Math Department, September 2003.
|
| |
9
|
G. Charpiat, O. Faugeras, and R. Keriven. Proceedings of the International Conference on Image Processing, IEEE Signal Processing Society, September 2003.
|
| |
10
|
T. K. Dey, J. Giesen, and J. Hudson, Proc. 13th Canadian Conf. on Comp. Geom., pp. 85--88, 2001.
|
| |
11
|
D. L. Donoho and C. Grimes, "Hessian eigenmaps: New locally-linear embedding techniques for high-dimensional data," Technical Report Department of Statistics, Stanford University, 2003.
|
| |
12
|
|
| |
13
|
A. Elad (Elbaz) and R. Kimmel, In Proc. of CVPR'01, Hawaii, Dec. 2001.
|
| |
14
|
W. Feller, An Introduction to Probability Theory and its Applications, John Wiley & Sons, Inc., New York-London-Sydney, 1971.
|
| |
15
|
J. Giesen and U, Wagner, ACM Symposium on Computational Geometry, San Diego, June 2003.
|
| |
16
|
|
| |
17
|
M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Progress in Mathematics 152, Birkhäuser Boston, Inc., Boston, MA, 1999.
|
| |
18
|
M. Gromov, Geometric group theory, Vol. 2: Asymptotic invariants of infinite groups. Edited by A. Niblo and Martin A. Roller. London Math. Soc. Lecture Note Ser., vol. 182, Cambridge Univ. Press, 1993.
|
| |
19
|
M. Gross et al, Point Based Computer Graphics, EUROGRAPHICS Lecture Notes, 2002.
|
| |
20
|
K. Grove, "Metric differential geometry," Differential geometry (Lyngby, 1985), 171--227, Lecture Notes in Math., 1263, Springer, Berlin, 1987.
|
| |
21
|
|
| |
22
|
|
| |
23
|
P. W. Jones, Invent. Math.102, pp. 1--15, 1990.
|
| |
24
|
D. W. Kahn, Topology. An Introduction to the Point-Set and Algebraic Areas, Williams & Wilkins Co., Baltimore, Md., 1975.
|
| |
25
|
N. J. Kalton and M. I. Ostrovskii, Forum Math.11:1, pp. 17--48, 1999.
|
| |
26
|
R. Kimmel and J. A. Sethian, Proc. National Academy of Sciences95:15, pp. 8431--8435, 1998.
|
| |
27
|
G. Leibon and D. Letscher, Computational Geometry 2000, Hong Kong, 2000.
|
| |
28
|
L. Linsen, "Point cloud representation," CS Technical Report, University of Karlsruhe, 2001.
|
| |
29
|
L. Linsen and H. Prautzsch, EUROGRAPHICS '01, 2001.
|
| |
30
|
C. T. McMullen Geom. Funct. Anal.8, pp. 304--314, 1998.
|
| |
31
|
F. Mémoli and G. Sapiro, IEEE Workshop on Variational and Level-Sets Methods in Computer Vision, Nice, France, October 2003.
|
| |
32
|
N. J. Mitra and A. Nguyen, ACM Symposium on Computational Geometry, San Diego, June 2003.
|
| |
33
|
C. Moenning and N. A. Dodgson, "Fast marching farthest point sampling for implicit surfaces and point clouds," Computer Laboratory Technical Report565.
|
| |
34
|
V. V. Nekrashevych, Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki, pp. 18--21, 1997.
|
| |
35
|
M. Pauly, M. Gross, and L. Kobbelt, IEEE Vis. 2002.
|
| |
36
|
P. Petersen, Riemannian Geometry, Springer-Verlag, New York, 1998.
|
| |
37
|
P. Petersen, Differential geometry: Riemannian geometry (Los Angeles, CA, 1990), pp 489--504, Proc. Sympos. Pure Math., 54, Part 3, Amer. Math. Soc., Providence, RI, 1993.
|
| |
38
|
S. Rusinkiewicz and M. Levoy, Computer Graphics (SIGGRAPH 2000 Proceedings), 2000.
|
| |
39
|
J. B. Tenenbaum, V. de Silva, and J. C. Langford, Science, pp. 2319--2323, December 2000.
|
| |
40
|
D.Toledo, Bull. Amer. Math. Soc.33, pp. 395--398, 1996.
|
| |
41
|
H. Von Schelling, Amer. Math. Monthly61, pp. 306--311, 1954.
|
| |
42
|
E. W. Weisstein, mathworld.wolfram.com/HyperspherePointPicking.html
|
| |
43
|
M. Zwicker, M. Pauly, O. Knoll, and M. Gross, SIGGRAPH, 2002.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf