IEEE TRANSACTIONS ON VISUALISATION AND COMPUTER GRAPHICS

Quentin Mérigot

Description

Niveau: Supérieur, Doctorat, Bac+8
IEEE TRANSACTIONS ON VISUALISATION AND COMPUTER GRAPHICS 1 Voronoi-based Curvature and Feature Estimation from Point Clouds Quentin Mérigot, Maks Ovsjanikov, and Leonidas Guibas Abstract—We present an efficient and robust method for extracting curvature information, sharp features and normal directions of a piecewise smooth surface from its point cloud sampling in a unified framework. Our method is integral in nature and uses convolved covariance matrices of Voronoi cells of the point cloud which makes it provably robust in the presence of noise. We show that these matrices contain information related to curvature in the smooth parts of the surface, and information about the directions and angles of sharp edges around the features of a piecewise-smooth surface. Our method is applicable in both two and three dimensions, and can be easily parallelized, making it possible to process arbitrarily large point clouds, which was a challenge for Voronoi-based methods. In addition, we describe a Monte-Carlo version of our method, which is applicable in any dimension. We illustrate the correctness of both principal curvature information and feature extraction in the presence of varying levels of noise and sampling density on a variety of models. As a sample application, we use our feature detection method to segment point cloud samplings of piecewise-smooth surfaces. Index Terms—Computational Geometry, Object Modeling F 1 INTRODUCTION E STIMATING surface normals, principal curvaturesand sharp edges from a noisy point cloud sampling has many applications in computer graphics, geometry processing and reverse engineering.

• can influence


• voronoi cells


• robustly fitting local


• method can


• voronoi-based normal


• point clouds


• sharp edges

Sujets

• Stanford University

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 31
• Langue: English
• Poids de l'ouvrage: 7 Mo

Extrait

IEEE TRANSACTIONS ON VISUALISATION AND COMPUTER GRAPHICS

Voronoi-based Curvature and Feature Estimation from Point Clouds Quentin Mérigot, Maks Ovsjanikov, and Leonidas Guibas

Abstract —We present an efficient and robust method for extracting curvature information, sharp features and normal directions of a piecewise smooth surface from its point cloud sampling in a unified framework. Our method is integral in nature and uses convolved covariance matrices of Voronoi cells of the point cloud which makes it provably robust in the presence of noise. We show that these matrices contain information related to curvature in the smooth parts of the surface, and information about the directions and angles of sharp edges around the features of a piecewise-smooth surface. Our method is applicable in both two and three dimensions, and can be easily parallelized, making it possible to process arbitrarily large point clouds, which was a challenge for Voronoi-based methods. In addition, we describe a Monte-Carlo version of our method, which is applicable in any dimension. We illustrate the correctness of both principal curvature information and feature extraction in the presence of varying levels of noise and sampling density on a variety of models. As a sample application, we use our feature detection method to segment point cloud samplings of piecewise-smooth surfaces.

Index Terms —Computational Geometry, Object Modeling

✦

1

1 I NTRODUCTION E S a T n I d M s A h T a I r N p G ed s g u e r s fa f c r e om no a r n m o a i l s s y , p p o r i i n n t ci c p lo al ud c s u a rv m a p t l u i r n e g si i s ng a t c o h e a s l t l i e m ng a i t n e g di t f a f s e k r . en T t h i i a s l i q s ua m n a t i it n i l e y s b w e h c i a c u h se by w n e at a u r r e e tr ar y e - has many applications in computer graphics, geometry very sensitive to local perturbations. The lack of a natural processing and reverse engineering. Principal curvatures parametrization of point cloud data introduces another are rotation-invariant local descriptors, which together challenge by making it difficult to estimate angles and with principal curvature directions have proven useful areas on the surface. Finally, devising a method with in detecting structural regularity [1], global matching [2], theoretical guarantees on the approximation quality is modeling and rendering of point-based surfaces [3], and not easy in the absence of a definition of curvature and anisotropic smoothing [4] to name just a few. In these sharp features that that would incorporate both point applications, various notions of curvature serve as local clouds and piecewise-smooth surfaces. descriptors that encode second order variations of the  In this paper, we address some of these challenges by surface. The location of sharp edges and highly curved  presenting a method for robustly estimating the location areas of the surface is a precious piece of information  and direction of sharp edges as well as highly curved in settings that include feature-aware reconstruction [5],  area from a possibly noisy point cloud sampling. We non photorealistic rendering [6], and industrial metrol-  also show that the same method can be used to recover ogy. curvature information of the underlying surface, when In practice, it is often interesting to recover this infor-  the sampling is dense enough. The sharp edge estimation mation when the input is an unstructured collection of  technique comes with theoretical guarantees on the qual- point coordinates, obtained by a range scanner, before  ity of the results as a function of the Hausdorff distance attempting surface reconstruction. These point clouds  between the point cloud and the underlying surface. We can be noisy, and can exhibit strong sampling bias. The  also address a certain class of outliers. ability to reliably estimate surface normals, principal curvatures, and curvature directions as well as sharp Prior work on feature and curvature estimation features directly on such point clouds can be used in  The questions of curvature estimation and sharp feature both geometry processing algorithms and in surface  detection are tightly related: sharp edges and corners can reconstruction to improve the quality of the resulting  be thought as parts of the surface with infinite concen- mesh. tration of curvature (mean and Gaussian, respectively). Devising robust local descriptors, which can handle  Surprisingly, however, these research topics have known both non-uniform noise, sampling bias and sharp edges  very different developments; we review the existing results separately. • Q. Mérigot is with Laboratoire Jean Kuntzmann, CNRS/Université Greno- ble I, 51 rue des Mathématiques Campus de Saint Martin d’Hères BP 53, Curvature estimation on meshes Grenoble Cedex 0 France • 3 M 8 . 04 O 1 vsjanikovandL.Gu 9 i , basarewiththeComputerScienceDepartment, Estimating the curvature of a smooth surface from a Stanford University, Stanford CA, CA 94305. mesh is an important question in discrete differential Manuscript received February 18, 2010; revised August 30, 2010. geometry has been studied for many years and is now