×

Curve reconstruction from noisy samples. (English) Zbl 1070.65013

The paper presents a new algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. A probabilistic model of noisy samples is proposed. Moreover it is proved that the reconstruction is faithful with probability close to 1 as the number of samples increases. The problem of reconstructing surfaces from noisy samples is also discussed.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Althaus, E.; Mehlhorn, K., Traveling salesman based curve reconstruction in polynomial time, SIAM J. Comput., 31, 27-66 (2001) · Zbl 0992.68070
[2] Amenta, N.; Bern, M.; Eppstein, D., The crust and the \(β\)-skeleton: Combinatorial curve reconstruction, Graphical Models and Image Processing, 60, 125-135 (1998)
[3] S.-W. Cheng, S.-H. Poon, Surface reconstruction from noisy samples, Manuscript, 2004; S.-W. Cheng, S.-H. Poon, Surface reconstruction from noisy samples, Manuscript, 2004
[4] Dedieu, J.-P.; Favardin, Ch., Algorithms for ordering unorganized points along parametrized curves, Numer. Algorithms, 6, 169-200 (1994) · Zbl 0789.65007
[5] Dey, T. K.; Goswami, S., Provable surface reconstruction from noisy samples, (Proc. 20th Annu. ACM Sympos. Comput. Geom. (2004)) · Zbl 1112.65014
[6] Dey, T. K.; Kumar, P., A simple provable algorithm for curve reconstruction, (Proc. 10th. Annu. ACM-SIAM Sympos. Discrete Alg. (1999)), 893-894 · Zbl 1052.65509
[7] Dey, T. K.; Mehlhorn, K.; Ramos, E., Curve reconstruction: connecting dots with good reason, Computational Geometry, 15, 229-244 (2000) · Zbl 0955.68113
[8] Dey, T. K.; Wenger, R., Reconstructing curves with sharp corners, Computational Geometry, 19, 89-99 (2001) · Zbl 0985.68081
[9] Dey, T. K.; Wenger, R., Fast reconstruction of curves with sharp corners, Computational Geometry, 12, 353-400 (2002) · Zbl 1152.68665
[10] Habib, M.; McDiarmid, C.; Ramirez-Alfonsin, J.; Reed, B., (Probabilistic Methods for Algorithmic Discrete Mathematics (1998), Springer-Verlag: Springer-Verlag Berlin), 198-200 · Zbl 0898.00019
[11] L. Fang, D.C. Gossard, Fitting 3D curves to unorganized data points using deformable curves, in: Visual Computing (Proc. CG International ’92), pp. 535-543; L. Fang, D.C. Gossard, Fitting 3D curves to unorganized data points using deformable curves, in: Visual Computing (Proc. CG International ’92), pp. 535-543
[12] Funke, S.; Ramos, E. A., Reconstructing a collection of curves with corners and endpoints, (Proc. 12th Annu. ACM-SIAM Sympos. Discrete Alg. (2001)), 344-353 · Zbl 0988.65019
[13] Giesen, J., Curve reconstruction, the Traveling Salesman Problem and Menger’s Theorem on length, Discrete Comp. Geom., 24, 577-603 (2000) · Zbl 0984.65012
[14] Gold, C.; Snoeyink, J., A one-step crust and skeleton extraction algorithm, Algorithmica, 30, 144-163 (2001) · Zbl 0983.68226
[15] Goshtasby, A. A., Grouping and parameterizing irregularly spaced points for curve fitting, ACM Trans. Graph., 19, 185-203 (2000)
[16] Lee, K. I., Curve reconstruction from unorganized points, Computer Aided Geometric Design, 17, 161-177 (2000) · Zbl 0939.68154
[17] Levin, D., The approximation power of moving least-squares, Math. Comput., 67, 1517-1531 (1998) · Zbl 0911.41016
[18] Levin, D., Mesh-independent surface interpolation, (Brunnett; Hamann; Mueller, Geometric Modeling for Scientific Visualization (2003), Springer-Verlag: Springer-Verlag Berlin)
[19] Pottmann, H.; Randrup, T., Rotational and helical surface approximation for reverse engineering, Computing, 60, 307-322 (1998) · Zbl 0906.68176
[20] Taubin, G.; Ronfard, R., Implicit simplicial models for adaptive curve reconstruction, IEEE Trans. Pattern Anal. Machine Intelligence, 18, 321-325 (1996)
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.