skip to main content
10.5555/1281991.1281993acmotherconferencesArticle/Chapter ViewAbstractPublication PagessgpConference Proceedingsconference-collections
Article

Robust statistical estimation of curvature on discretized surfaces

Published: 04 July 2007 Publication History

Abstract

A robust statistics approach to curvature estimation on discretely sampled surfaces, namely polygon meshes and point clouds, is presented. The method exhibits accuracy, stability and consistency even for noisy, non-uniformly sampled surfaces with irregular configurations. Within an M-estimation framework, the algorithm is able to reject noise and structured outliers by sampling normal variations in an adaptively reweighted neighborhood around each point. The algorithm can be used to reliably derive higher order differential attributes and even correct noisy surface normals while preserving the fine features of the normal and curvature field. The approach is compared with state-of-the-art curvature estimation methods and shown to improve accuracy by up to an order of magnitude across ground truth test surfaces under varying tessellation densities and types as well as increasing degrees of noise. Finally, the benefits of a robust statistical estimation of curvature are illustrated by applying it to the popular applications of mesh segmentation and suggestive contour rendering.

References

[1]
{ACSD*03} Alliez P., Cohen-Steiner D., Devillers O., Lévy B., Desbrun M.: Anisotropic polygonal remeshing. ACM Transactions on Graphics 22, 3 (2003), 485--493.
[2]
{CDR00} Clarenz U., Diewald U., Rumpf M.: Anisotropic geometric diffusion in surface processing. In VIS '00: Proceedings of the conference on Visualization '00 (2000), IEEE Computer Society Press, pp. 397--405.
[3]
{CP03} Cazals F., Pouget M.: Estimating differential quantities using polynomial fitting of osculating jets. In Eurographics Symposium on Geometry processing (2003), Eurographics Association, pp. 177--187.
[4]
{CR88} Carroll R., Ruppert D.: Transformation and Weighting in Regression. Chapman and Hall, 1988.
[5]
{CS92} Chen X., Schmitt F.: Intrinsic surface properties from surface triangulation. In European Conference on Computer Vision (1992), Springer-Verlag, pp. 739--743.
[6]
{CSM03} Cohen-Steiner D., Morvan J.-M.: Restricted delaunay triangulations and normal cycle. In Symposium on Computational geometry (2003), pp. 312--321.
[7]
{DFRS03} DeCarlo D., Finkelstein A., Rusinkiewicz S., Santella A.: Suggestive contours for conveying shape. In ACM SIGGRAPH (2003), ACM Press, pp. 848--855.
[8]
{DKT06} Desbrun M., Kanso E., Tong Y.: Discrete differential forms for computational modeling. In ACM SIGGRAPH Courses (2006), ACM Press, pp. 39--54.
[9]
{DTB06} Diebel J. R., Thrun S., Brunig M.: A bayesian method for probable surface reconstruction and decimation. ACM Transactions on Graphics 25, 1 (2006), 39--59.
[10]
{FP02} Forsyth D. A., Ponce J.: Computer Vision: A Modern Approach, first ed. Prentice Hall, 2002.
[11]
{GG06} Gatzke T., Grimm C.: Estimating curvature on triangular meshes. International Journal of Shape Modeling 12, 1 (2006), 1--29.
[12]
{GGRZ06} Grinspun E., Gingold Y., Reisman J., Zorin D.: Computing discrete shape operators on general meshes. Eurographics (Computer Graphics Forum) 25, 3 (2006).
[13]
{GI04} Goldfeather J., Interrante V.: A novel cubic-order algorithm for approximating principal direction vectors. ACM Transactions on Graphics 23, 1 (2004), 45--63.
[14]
{Ham93} Hamann B.: Curvature approximation for triangulated surfaces. Geometric modelling (1993), 139--153.
[15]
{HDD*92} Hoppe H., DeRose T., Duchamp T., McDonald J., Stuetzle W.: Surface reconstruction from unorganized points. In ACM SIGGRAPH (1992), ACM Press, pp. 71--78.
[16]
{HFG*06} Huang Q.-X., Flöry S., Gelfand N., Hofer M., Pottmann H.: Reassembling fractured objects by geometric matching. ACM Transactions on Graphics 25, 3 (2006), 569--578.
[17]
{HG99} Heckbert P. S., Garland M.: Optimal triangulation and quadric-based surface simplification. Comput. Geom. Theory Appl. 14, 1--3 (1999), 49--65.
[18]
{HPW05} Hildebrandt K., Polthier K., Wardetzky M.: Smooth feature lines on surface meshes. In Eurographics Symposium on Geometry processing (2005), pp. 85--90.
[19]
{HRRS86} Hampel F. R., Ronchetti E. M., Rousseeuw P. J., Stahel W. A.: Robust Statistics: The Approach Based on Influence Functions. Wiley-Interscience, 1986.
[20]
{HS02} Hameiri E., Shimshoni I.: Estimating the principal curvatures and the darboux frame from real 3d range data. 3dpvt 00 (2002), 258--266.
[21]
{Hub81} Huber P.: Robust Statistics. Wiley-Interscience, 1981.
[22]
{JF89} Jain A., Flynn P.: Error bounds and optimal neighborhoods for mls approximation. In Computer Vision and Pattern Recognition (1989), pp. 110--116.
[23]
{Kay93} Kay S. M.: Fundamentals of Statistical Signal Processing. Prentice Hall PTR, 1993.
[24]
{LBS07} Langer T., Belyaev A., Seidel H.-P.: Exact and interpolatory quadratures for curvature tensor estimation. Computer Aided Geometric Design Accepted (2007).
[25]
{LCOLTE07} Lipman Y., Cohen-Or D., Levin D., Talezer H.: Parameterization-free projection for geometry reconstruction. In ACM SIGGRAPH, to appear (2007), ACM Press.
[26]
{LDB05} Lavoue G., Dupont F., Baskurt A.: A new cad mesh segmentation method, based on curvature tensor analysis. Computer-Aided Design (CAD) 37, 10 (2005), 975--987.
[27]
{LP05} Lange C., Polthier K.: Anisotropic smoothing of point sets. Computer Aided Geometric Design 22, 7 (2005), 680--692.
[28]
{LPRM02} Lévy B., Petitjean S., Ray N., Maillot J.: Least squares conformal maps for automatic texture atlas generation. In ACM SIGGRAPH (2002), ACM Press, pp. 362--371.
[29]
{LPW*06} Liu Y., Pottmann H., Wallner J., Yang Y.-L., Wang W.: Geometric modeling with conical meshes and developable surfaces. ACM Transactions on Graphics 25, 3 (2006), 681--689.
[30]
{LZH*07} Lai Y.-K., Zhou Q.-Y., Hu S.-M., Wallner J., Pottmann H.: Robust feature classification and editing. IEEE Transactions on Visualization and Computer Graphics 13, 1 (2007), 34--45.
[31]
{Max99} Max N.: Weights for computing vertex normals from facet normals. Journal of Graphics Tools 4, 2 (1999), 1--6.
[32]
{MDSB02} Meyer M., Desbrun M., Schröder P., Barr A. H.: Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, Hege H.-C., Polthier K., (Eds.). Springer-Verlag, 2002, pp. 35--57.
[33]
{MGP06} Mitra N. J., Guibas L. J., Pauly M.: Partial and approximate symmetry detection for 3d geometry. ACM SIGGRAPH 25, 3 (2006), 560--568.
[34]
{MNG04} Mitra N. J., Nguyen A., Guibas L.: Estimating surface normals in noisy point cloud data. In Special issue of International Journal of Computational Geometry and Applications (2004), vol. 14, pp. 261--276.
[35]
{PSK*02} Page D. L., Sun Y., Koschan A. F., Paik J., Abidi M. A.: Normal vector voting: crease detection and curvature estimation on large, noisy meshes. Graph. Models 64, 3/4 (2002), 199--229.
[36]
{RL01} Rusinkiewicz S., Levoy M.: Efficient variants of the ICP algorithm. In Proceedings of the Third Intl. Conf. on 3D Digital Imaging and Modeling (2001), pp. 145--152.
[37]
{RMB07} Ramamoorthi R., Mahajan D., Belhumeur P.: A first-order analysis of lighting, shading, and shadows. ACM Transactions on Graphics 26, 1 (2007), 2.
[38]
{Rus04} Rusinkiewicz S.: Estimating curvatures and their derivatives on triangle meshes. 3DPVT (2004), 486--493.
[39]
{SAG95} Sawhney H. S., Ayer S., Gorkani M.: Model-based 2d&3d dominant motion estimation for mosaicing and video representation. In ICCV (1995), IEEE Computer Society, pp. 583--590.
[40]
{She01} Sheffer A.: Model simplification for meshing using face clustering. Computer Aided Design (CAD), 33 (2001), 925--934.
[41]
{SKS06} Simari P., Kalogerakis E., Singh K.: Folding meshes: Hierarchical mesh segmentation based on planar symmetry. In Symposium on Geometry Processing (2006), pp. 111--119.
[42]
{SS05} Simari P. D., Singh K.: Extraction and remeshing of ellipsoidal representations from mesh data. In Graphics Interface (2005), pp. 161--168.
[43]
{SSK*05} Surazhsky V., Surazhsky T., Kirsanov D., Gortler S. J., Hoppe H.: Fast exact and approximate geodesics on meshes. ACM Transactions on Graphics 24, 3 (2005), 553--560.
[44]
{Ste99} Stewart C. V.: Robust parameter estimation in computer vision. SIAM Rev. 41, 3 (1999), 513--537.
[45]
{SW92} Stokely E., Wu S. Y.: Surface parametrization and curvature measurement of arbitrary 3-d objects: Five practical methods. IEEE Trans. Pattern Anal. Mach. Intell. 14, 8 (1992), 833--840.
[46]
{Tau95} Taubin G.: Estimating the tensor of curvature of a surface from a polyhedral approximation. In ICCV (1995), IEEE Computer Society, pp. 902--909.
[47]
{TRZS04} Theisel H., Rossl C., Zayer R., Seidel H.-P.: Normal based estimation of the curvature tensor for triangular meshes. In Computer Graphics and Applications (2004), IEEE Computer Society, pp. 288--297.
[48]
{TT05} Tong W.-S., Tang C.-K.: Robust estimation of adaptive tensors of curvature by tensor voting. IEEE Trans. Pattern Anal. Mach. Intell. 27, 3 (2005), 434--449.
[49]
{YLHP06} Yang Y.-L., Lai Y.-K., Hu S.-M., Pottmann H.: Robust principal curvatures on multiple scanes. In Eurographics Symposium on Geometry Processing (2006), pp. 223--226.

Cited By

View all
  • (2017)Data-Driven Shape Analysis and ProcessingComputer Graphics Forum10.1111/cgf.1279036:1(101-132)Online publication date: 1-Jan-2017
  • (2016)Data-driven shape analysis and processingSIGGRAPH ASIA 2016 Courses10.1145/2988458.2988473(1-38)Online publication date: 28-Nov-2016
  • (2016)Mesh statistics for robust curvature estimationProceedings of the Symposium on Geometry Processing10.1111/cgf.12982(271-280)Online publication date: 20-Jun-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing
July 2007
273 pages
ISBN:9783905673463

Sponsors

  • EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 04 July 2007

Check for updates

Qualifiers

  • Article

Conference

SGP '07
Sponsor:
  • EUROGRAPHICS
SGP '07: Geometry processing
July 4 - 6, 2007
Barcelona, Spain

Acceptance Rates

SGP '07 Paper Acceptance Rate 21 of 74 submissions, 28%;
Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Data-Driven Shape Analysis and ProcessingComputer Graphics Forum10.1111/cgf.1279036:1(101-132)Online publication date: 1-Jan-2017
  • (2016)Data-driven shape analysis and processingSIGGRAPH ASIA 2016 Courses10.1145/2988458.2988473(1-38)Online publication date: 28-Nov-2016
  • (2016)Mesh statistics for robust curvature estimationProceedings of the Symposium on Geometry Processing10.1111/cgf.12982(271-280)Online publication date: 20-Jun-2016
  • (2015)Stable topological signatures for points on 3D shapesProceedings of the Eurographics Symposium on Geometry Processing10.1111/cgf.12692(1-12)Online publication date: 6-Jul-2015
  • (2015)A framework for automatic and perceptually valid facial expression generationMultimedia Tools and Applications10.1007/s11042-014-2125-974:21(9427-9447)Online publication date: 1-Nov-2015
  • (2014)Continuous projection for fast L1 reconstructionACM Transactions on Graphics10.1145/2601097.260117233:4(1-13)Online publication date: 27-Jul-2014
  • (2014)3D ear recognition using local salience and principal manifoldGraphical Models10.1016/j.gmod.2014.03.00376:5(402-412)Online publication date: 1-Sep-2014
  • (2011)SlicesACM Transactions on Graphics10.1145/2070781.202420230:6(1-12)Online publication date: 12-Dec-2011
  • (2011)SlicesProceedings of the 2011 SIGGRAPH Asia Conference10.1145/2024156.2024202(1-12)Online publication date: 12-Dec-2011
  • (2011)Adaptive simplification of huge sets of terrain grid data for geosciences applicationsJournal of Computational and Applied Mathematics10.1016/j.cam.2011.09.005236:6(1410-1422)Online publication date: 1-Oct-2011
  • Show More Cited By

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media