No Access

SCALE SELECTION FOR GEOMETRIC FITTING IN NOISY POINT CLOUDS

RANJITH UNNIKRISHNAN

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA

Search for more papers by this author

JEAN-FRANÇOIS LALONDE

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA

Search for more papers by this author

NICOLAS VANDAPEL

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA

Search for more papers by this author

, and

MARTIAL HEBERT

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA

Search for more papers by this author

https://doi.org/10.1142/S0218195910003438Cited by:10 (Source: Crossref)

Abstract

In recent years, there has been a resurgence in the use of raw point cloud data as the geometric primitive of choice for several modeling tasks such as rendering, editing and compression. Algorithms using this representation often require reliable additional information such as the curve tangent or surface normal at each point. Estimation of these quantities requires the selection of an appropriate scale of analysis to accommodate sensor noise, density variation and sparsity in the data. To this goal, we present a new class of locally semi-parametric estimators that allows analysis of accuracy with finite samples, as well as explicitly addresses the problem of selecting optimal support volume for local fitting. Experiments on synthetic and real data validate the behavior predicted by the model, and show competitive performance and improved stability over leading alternatives that require a preset scale.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

M. Alexaet al., Point set surfaces, VIS '01: Proc. Conf. Visualization '01 (IEEE Computer Society, Washington, DC, USA, 2001) pp. 21–28. Google Scholar
N. Amenta and M. Bern, Discr. Comput. Geom. 22(4), 481 (1999), DOI: 10.1007/PL00009475. Crossref, Web of Science, Google Scholar
N. Amenta , M. Bern and M. Kamvysselis , A new voronoi-based surface reconstruction algorithm , Int. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH) . Google Scholar
N. Amentaet al., A simple algorithm for homeomeorphic surface reconstruction, Proc. 16th ACM Ann. Symp. Computational Geometry pp. 213–222. Google Scholar
M. A. Carreira-Perpinán and R. S. Zemel, Proximity graphs for clustering and manifold learning, Neural Information Processing Systems (NIPS) pp. 225–232. Google Scholar
F. Cazals, J. Giesen and M. Yvinec, Delaunay triangulation based surface reconstruction: a short survey, Research Report 5394, INRIA, 2004 . Google Scholar
F. Cazals and M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Proc. 2003 Eurographics/ACM SIGGRAPH Symp. Geometry Processing pp. 177–187. Google Scholar
F. R. K. Chung , Spectral Graph Theory ( American Mathematical Society , 1997 ) . Google Scholar
T. K. Dey and S. Goswami, Provable surface reconstruction from noisy samples, Proc. 20th ACM Ann. Symp. Computational Geometry pp. 330–339. Google Scholar
M. do Carmo , Differential Geometry of Curves and Surfaces ( Prentice Hall , 1976 ) . Google Scholar
H. Edelsbrunner, D. Kirkpatrick and R. Seidel, IEEE Trans. Inform. Th. 29, 551 (1983), DOI: 10.1109/TIT.1983.1056714. Crossref, Web of Science, Google Scholar
H. Edelsbrunner and E. P. Mücke, ACM Trans. Graph. 13, 43 (1994), DOI: 10.1145/174462.156635. Crossref, Web of Science, Google Scholar
J. Goodman and J. O. Rourke (eds.) , Handbook of Discrete and Computational Geometry ( CRC press , 2004 ) . Crossref, Google Scholar
H. Hoppeet al., Comput. Graph. 26(2), 71 (1992). Crossref, Google Scholar
K. Kanatani , Statistical optimization for geometric fitting: Theoretical accuracy analysis and high order error analysis , 21st Int. Conf. Image and Vision Computing New Zealand (IVCNZ) . Google Scholar
K. Kanatani, Int. J. Comput. Vis. 80(2), 167 (2008), DOI: 10.1007/s11263-007-0098-0. Crossref, Web of Science, Google Scholar
B. Kéglet al., IEEE Trans. Patt. Anal. Mach. Intell. (PAMI) 22(3), 281 (2000). Crossref, Web of Science, Google Scholar
D. Langeret al., Int. J. Robot. Res. 19(11), (2000), DOI: 10.1177/02783640022067986. Crossref, Web of Science, Google Scholar
I.-K. Lee, Comput. Aided Geomet. Design 17(2), 161 (2000), DOI: 10.1016/S0167-8396(99)00044-8. Crossref, Web of Science, Google Scholar
D. Levin, Math. Computat. 67(224), 1517 (1998), DOI: 10.1090/S0025-5718-98-00974-0. Crossref, Web of Science, Google Scholar
D. Levin , Geometric Modeling for Scientific Visualization ( Springer-Verlag , 2004 ) . Google Scholar
T. Lewineret al., Comput. Graph. 29(5), 641 (2005), DOI: 10.1016/j.cag.2005.08.004. Crossref, Web of Science, Google Scholar
D. J. C. MacKay, Introduction to Gaussian Processes, NATO ASI 168 (Springer, 1998) pp. 133–165. Google Scholar
B. Matei and P. Meer, IEEE Trans. Patt. Anal. Mach. Intell. (PAMI) 28, 1537 (2006), DOI: 10.1109/TPAMI.2006.205. Crossref, Web of Science, Google Scholar
J. Miller, A 3D Color Terrain Modeling System for Small Autonomous Helicopters, PhD thesis, Carnegie Mellon University, 2002 . Google Scholar
N. J. Mitra, A. Nguyen and L. Guibas, Special Issue of Int. J. Comput. Geom. Appl. 14(4), 261 (2004), DOI: 10.1142/S0218195904001470. Link, Web of Science, Google Scholar
A. Y. Ng, A. X. Zheng and M. Jordan, Link analysis, eigenvectors, and stability, Proc. Intl. Joint Conf. Artificial Intelligence (IJCAI) pp. 903–910. Google Scholar
A. C. Oztireli, G. Guennebaud and M. Gross, Comput. Graph. Forum 28, 493 (2009), DOI: 10.1111/j.1467-8659.2009.01388.x. Crossref, Web of Science, Google Scholar
C. E. Rasmussen and C. K. I. Williams , Gaussian Processes for Machine Learning ( MIT Press , Cambridge, MA , 2006 ) . Google Scholar
V. C. Raykar and R. Duraiswami , Fast large scale gaussian process regression using approximate matrix-vector products , Learning Workshop . Google Scholar
G. W. Stewart and J.-G. Sun , Matrix Perturbation Theory ( Academic Press , 1990 ) . Google Scholar
C. K. Tang and G. Medioni, IEEE Trans. Patt. Anal. Mach. Intell. (PAMI) 20(11), 1206 (1998). Crossref, Web of Science, Google Scholar
C. K. Tanget al., IEEE Trans. Patt. Anal. Mach. Intell. (PAMI) 26(5), 594 (2004). Web of Science, Google Scholar
B. Triggs , A new approach to geometric fitting , Int. Conf. Computer Vision . Google Scholar
R. Unnikrishnan and M. Hebert , Denoising manifold and non-manifold point clouds , British Machine Vision Conf. . Google Scholar
R. Unnikrishnan et al. , Scale selection for the analysis of point-sampled curves , Third Int. Symp. 3D Processing, Visualization and Transmission (3DPVT 2006) . Google Scholar
R. Unnikrishnan, J.-F. Lalonde, N. Vandapel and M. Hebert, Scale selection for the analysis of point sampled curves, Technical report, Robotics Institute, CMU (2006) . Google Scholar
C. Walder, B. C. Lovell and P. J. Kootsookos, Algebraic curve fitting support vector machines, Digital Image Computing Techniques and Applications pp. 693–702. Google Scholar
C. Walder , B. Schölkopf and O. Chapelle , Implicit surfaces with globally regularized and compactly supported basis functions , Advances in Neural Information Processing Systems . Google Scholar
H. Wang, C. Scheidegger and C. Silva, IEEE Trans. Visual. Comput. Graph. 15(4), 572 (2009), DOI: 10.1109/TVCG.2009.187. Crossref, Web of Science, Google Scholar
T. Willmore , Riemannian Geometry ( Clarendon Press , 1993 ) . Crossref, Google Scholar
M. Zwickeret al., Pointshop 3D: An interactive system for point-based surface editing, Conf. Computer Graphics and Interactive Techniques pp. 322–329. Google Scholar