Provably correct reconstruction of surfaces from sparse noisy samples. (English) Zbl 1183.68548
Summary: Automated three-dimensional surface reconstruction is a very large and still fast growing area of applied computer vision and there exists a huge number of heuristic algorithms. Nevertheless, the number of algorithms which give formal guarantees about the correctness of the reconstructed surface is quite limited. Moreover such theoretical approaches are proven to be correct only for objects with smooth surfaces and extremely dense samplings with no or very few noise. We define an alternative surface reconstruction method and prove that it preserves the topological structure of multi-region objects under much weaker constraints and thus under much more realistic conditions. We derive the necessary error bounds for some digitization methods often used in discrete geometry, i.e. supercover and \(m\)-cell intersection sampling. We also give a detailed analysis of the behavior of our algorithm and compare it with other approaches.
MSC:
| 68T10 | Pattern recognition, speech recognition |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
References:
| [1] | 3D Model Retrieval \(\langle;\) http://3d.csie.ntu.edu.tw/˜dynamic/cgi-bin/DatabaseII_v1.8/index.html \(\rangle;\); 3D Model Retrieval \(\langle;\) http://3d.csie.ntu.edu.tw/˜dynamic/cgi-bin/DatabaseII_v1.8/index.html \(\rangle;\) |
| [2] | Large Geometric Models Archive \(\langle;\) http://www-static.cc.gatech.edu/projects/large_models/\( \rangle;\); Large Geometric Models Archive \(\langle;\) http://www-static.cc.gatech.edu/projects/large_models/\( \rangle;\) |
| [3] | Cgal, Computational Geometry Algorithms Library \(\langle;\) http://www.cgal.org \(\rangle;\); Cgal, Computational Geometry Algorithms Library \(\langle;\) http://www.cgal.org \(\rangle;\) |
| [4] | Amenta, N.; Bern, M.; Kamvysselis, M., A new Voronoi-based surface reconstruction algorithm, (Conference on Computational Graphics and Interactive Techniques (1998)), 415-421 |
| [5] | Amenta, N.; Choi, S.; Dey, T.; Leekha, N., A simple algorithm for homeomorphic surface reconstruction, (Symposium on Computational Geometry (2000)), 213-222 · Zbl 1374.68636 |
| [6] | Amenta, N.; Choi, S.; Kolluri, R., The power crust, unions of balls, and the medial axis transform, Comput. Geom., 19, 2, 127-153 (2001) · Zbl 0988.65015 |
| [7] | Attali, D.; Boissonnat, J.; Lieutier, A., Complexity of the Delaunay triangulation of points on surfaces the smooth case, (Proceedings of the Nineteenth Annual Symposium on Computational Geometry (2003), ACM, New York: ACM, New York NY, USA), 201-210 · Zbl 1374.68638 |
| [8] | Bernardini, F.; Bajaj, C., Sampling and reconstructing manifolds using alpha-shapes, (Canadian Conference on Computational Geometry (1997)) |
| [9] | Bernardini, F.; Bajaj, C.; Chen, J.; Schikore, D., Automatic reconstruction of 3D CAD models from digital scans, Int. J. Comput. Geom. Appl., 9, 4/5, 327-369 (1999) |
| [10] | Bernardini, F.; Mittleman, J.; Rushmeier, H.; Silva, C.; Taubin, G., The ball-pivoting algorithm for surface reconstruction, (IEEE Trans. Visualization Comput. Graphics (1999)), 349-359 |
| [11] | Boissonnat, J.-D.; Oudot, S., Provably good sampling and meshing of lipschitz surfaces, (Proceedings of the 22th Annual ACM Symposium on Computational Geometry (2006)) · Zbl 1153.65315 |
| [12] | Dey, T.; Goswami, S., Tight cocone: a water-tight surface reconstructor, J. Comput. Inf. Sci. Eng., 3, 302 (2003) |
| [13] | Edelsbrunner, H., The union of balls and its dual shape, Discrete Comput. Geom., 13, 415-440 (1995) · Zbl 0826.68053 |
| [14] | Edelsbrunner, H.; Mücke, E., Three-dimensional alpha shapes, ACM Trans. Graphics, 13, 43-72 (1994) · Zbl 0806.68107 |
| [15] | Fejes, L., Über einige Extremaleigenschaften der regulären Polyeder und des gleichseitigen Dreiecksgitters, Ann. Sc. Norm. Super. Pisa-Classe Sci. Sér. 2, 13, 1-4, 51-58 (1948) · Zbl 0030.22102 |
| [16] | Klette, R.; Rosenfeld, A., Digital Geometry (2004), Morgan Kaufman: Morgan Kaufman Los Altos, CA · Zbl 1064.68090 |
| [17] | Kolluri, R.; Shewchuk, J.; O’Brien, J., Spectral surface reconstruction from noisy point clouds, (Eurographics Symposium on Geometry Processing (2004)) |
| [18] | Mederos, B.; Amenta, N.; Velho, L.; de Figueiredo, L., Surface reconstruction from noisy point clouds, (Eurographics Symposium on Geometry Processing (2005)) |
| [19] | Niyogi, P.; Smale, S.; Weinberger, S., Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39, 1, 419-441 (2008) · Zbl 1148.68048 |
| [20] | P. Stelldinger, Topologically correct 3d surface reconstruction and segmentation from noisy samples, in: V.E. Brimkov, R.P. Barneva, H.A. Hauptman (Eds.), Combinatorial Image Analysis, Lecture Notes Computer Science, vol. 4958, Springer, Berlin, 2008, pp. 274-285 (Special issue: IWCIA ’08).; P. Stelldinger, Topologically correct 3d surface reconstruction and segmentation from noisy samples, in: V.E. Brimkov, R.P. Barneva, H.A. Hauptman (Eds.), Combinatorial Image Analysis, Lecture Notes Computer Science, vol. 4958, Springer, Berlin, 2008, pp. 274-285 (Special issue: IWCIA ’08). |
| [21] | Stelldinger, P., Topologically correct surface reconstruction using alpha shapes and relations to ball-pivoting, (International Conference on Pattern Recognition (2008)) |
| [22] | Stelldinger, P.; Köthe, U.; Meine, H., Topologically correct image segmentation using alpha shapes, (Discrete Geometry for Computer Imagery (2006)) · Zbl 1136.68601 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
