Consolidation of unorganized point clouds for surface reconstruction

Abstract

We consolidate an unorganized point cloud with noise, outliers, non-uniformities, and in particular interference between close-by surface sheets as a preprocess to surface generation, focusing on reliable normal estimation. Our algorithm includes two new developments. First, a weighted locally optimal projection operator produces a set of denoised, outlier-free and evenly distributed particles over the original dense point cloud, so as to improve the reliability of local PCA for initial estimate of normals. Next, an iterative framework for robust normal estimation is introduced, where a priority-driven normal propagation scheme based on a new priority measure and an orientation-aware PCA work complementarily and iteratively to consolidate particle normals. The priority setting is reinforced with front stopping at thin surface features and normal flipping to enable robust handling of the close-by surface sheet problem. We demonstrate how a point cloud that is well-consolidated by our method steers conventional surface generation schemes towards a proper interpretation of the input data.

References

1. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE Trans. Vis.&Comp. Graphics 9, 1, 3--15.
2. Amenta, N., and Bern, M. W. 1998. Surface reconstruction by Voronoi filtering. In Symp. on Comp. Geom., 39--48.
3. Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. ACM Trans. on Graphics 23, 3, 264--270.
4. Amenta, N., Choi, S., and Kolluri, R. K. 2001. The power crust. In ACM Symp. on Solid Modeling and Appl., 249--266.
5. Ascher, U., and Petzold, L. 1998. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM, Philadelphia, PA.
6. Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proc. of ACM SIGGRAPH, 67--76.
7. Cazals, F., and Giesen, J. 2006. Delaunay triangulation based surface reconstruction. In Effective Computational Geometry for Curves and Surfaces. Springer, 231--276.
8. Dey, T. K., and Giesen, J. 2001. Detecting undersampling in surface reconstruction. In Symp. on Comp. Geom., 257--263.
9. Dey, T. K., and Goswami, S. 2006. Provable surface reconstruction from noisy samples. Comp. Geom.: Theory&Appl. 35, 1, 124--141.
10. Dey, T. K., and Sun, J. 2005. An adaptive MLS surface for reconstruction with guarantees. In Symp. on Geom. Proc. (SGP), 43--52.
11. Dey, T. K., and Sun, J. 2006. Normal and feature estimations from noisy point clouds. In Proc. of Foundations of Software Technology and Theoretical Computer Science, 21--32.
12. Fleishman, S., Cohen-Or, D., and Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM Trans. Graph. 24, 3, 544--552.
13. Guennebaud, G., Barthe, L., and Paulin, M. 2004. Real-time point cloud refinement. In Eurographics Symp. on Point-Based Graphics, 41--49.
14. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proc. of ACM SIGGRAPH, 71--78.
15. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. on Geom. Proc. (SGP), 61--70.
16. Lange, C., and Polthier, K. 2005. Anisotropic smoothing of point sets. Comput. Aided Geom. Des. 22, 7, 680--692.
17. Lehtinen, J., Zwicker, M., Turquin, E., Kontkanen, J., Durand, F., Sillion, F., and Aila, T. 2008. A meshless hierarchical representation for light transport. ACM Trans. on Graphics 27, 3 (Aug.), 37.
18. Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. on Graphics 26, 3 (Aug.), 22.
19. Ma, W.-C., Hawkins, T., Peers, P., Chabert, C.-F., Weiss, M., and Debevec, P. 2007. Rapid acquisition of specular and diffuse normal maps from polarized spherical gradient illumination. In Eurographics Symp. on Rendering, 183--194.
20. Mello, V., Velho, L., and Taubin, G. 2003. Estimating the in/out function of a surface represented by points. In ACM Symp. on Solid Modeling and Appl., 108--114.
21. Mitra, N. J., Nguyen, A., and Guibas, L. 2004. Estimating surface normals in noisy point cloud data. Int. J. Comput. Geom. and Appl. 14, 261--276.
22. Nehab, D., Rusinkiewicz, S., Davis, J., and Ramamoorthi, R. 2005. Efficiently combining positions and normals for precise 3D geometry. ACM Trans. on Graphics 24, 3, 536--543.
23. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition of unity implicits. ACM Trans. on Graphics 22, 3, 463--470.
24. Page, D. L., Sun, Y., Koschan, A., Paik, J., and Abidi, M. A. 2002. Normal vector voting: Crease detection and curvature estimation on large noisy meshes. Graphical Models 64, 199--229.
25. Pauly, M., Gross, M., and Kobbelt, L. P. 2002. Efficient simplification of point-sampled surfaces. In Proc. of IEEE Visualization, 163--170.
26. Sun, J., Smith, M., Smith, L., and Farooq, A. 2007. Examining the uncertainty of the recovered surface normal in three light photometric stereo. Image Vis. Comput. 25, 7, 1073--1079.
27. Turk, G., and Levoy, M. 1994. Zippered polygon meshes from range images. In Proc. of ACM SIGGRAPH, 311--318.
28. Woodham, R. J. 1980. Photometric method for determining surface orientation from multiple images. Optical Engineering 19, 1, 139--144.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision problems

        • Reconstruction

      • Computer vision representations

        • Image representations

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models