- •Preface
- •Biological Vision Systems
- •Visual Representations from Paintings to Photographs
- •Computer Vision
- •The Limitations of Standard 2D Images
- •3D Imaging, Analysis and Applications
- •Book Objective and Content
- •Acknowledgements
- •Contents
- •Contributors
- •2.1 Introduction
- •Chapter Outline
- •2.2 An Overview of Passive 3D Imaging Systems
- •2.2.1 Multiple View Approaches
- •2.2.2 Single View Approaches
- •2.3 Camera Modeling
- •2.3.1 Homogeneous Coordinates
- •2.3.2 Perspective Projection Camera Model
- •2.3.2.1 Camera Modeling: The Coordinate Transformation
- •2.3.2.2 Camera Modeling: Perspective Projection
- •2.3.2.3 Camera Modeling: Image Sampling
- •2.3.2.4 Camera Modeling: Concatenating the Projective Mappings
- •2.3.3 Radial Distortion
- •2.4 Camera Calibration
- •2.4.1 Estimation of a Scene-to-Image Planar Homography
- •2.4.2 Basic Calibration
- •2.4.3 Refined Calibration
- •2.4.4 Calibration of a Stereo Rig
- •2.5 Two-View Geometry
- •2.5.1 Epipolar Geometry
- •2.5.2 Essential and Fundamental Matrices
- •2.5.3 The Fundamental Matrix for Pure Translation
- •2.5.4 Computation of the Fundamental Matrix
- •2.5.5 Two Views Separated by a Pure Rotation
- •2.5.6 Two Views of a Planar Scene
- •2.6 Rectification
- •2.6.1 Rectification with Calibration Information
- •2.6.2 Rectification Without Calibration Information
- •2.7 Finding Correspondences
- •2.7.1 Correlation-Based Methods
- •2.7.2 Feature-Based Methods
- •2.8 3D Reconstruction
- •2.8.1 Stereo
- •2.8.1.1 Dense Stereo Matching
- •2.8.1.2 Triangulation
- •2.8.2 Structure from Motion
- •2.9 Passive Multiple-View 3D Imaging Systems
- •2.9.1 Stereo Cameras
- •2.9.2 3D Modeling
- •2.9.3 Mobile Robot Localization and Mapping
- •2.10 Passive Versus Active 3D Imaging Systems
- •2.11 Concluding Remarks
- •2.12 Further Reading
- •2.13 Questions
- •2.14 Exercises
- •References
- •3.1 Introduction
- •3.1.1 Historical Context
- •3.1.2 Basic Measurement Principles
- •3.1.3 Active Triangulation-Based Methods
- •3.1.4 Chapter Outline
- •3.2 Spot Scanners
- •3.2.1 Spot Position Detection
- •3.3 Stripe Scanners
- •3.3.1 Camera Model
- •3.3.2 Sheet-of-Light Projector Model
- •3.3.3 Triangulation for Stripe Scanners
- •3.4 Area-Based Structured Light Systems
- •3.4.1 Gray Code Methods
- •3.4.1.1 Decoding of Binary Fringe-Based Codes
- •3.4.1.2 Advantage of the Gray Code
- •3.4.2 Phase Shift Methods
- •3.4.2.1 Removing the Phase Ambiguity
- •3.4.3 Triangulation for a Structured Light System
- •3.5 System Calibration
- •3.6 Measurement Uncertainty
- •3.6.1 Uncertainty Related to the Phase Shift Algorithm
- •3.6.2 Uncertainty Related to Intrinsic Parameters
- •3.6.3 Uncertainty Related to Extrinsic Parameters
- •3.6.4 Uncertainty as a Design Tool
- •3.7 Experimental Characterization of 3D Imaging Systems
- •3.7.1 Low-Level Characterization
- •3.7.2 System-Level Characterization
- •3.7.3 Characterization of Errors Caused by Surface Properties
- •3.7.4 Application-Based Characterization
- •3.8 Selected Advanced Topics
- •3.8.1 Thin Lens Equation
- •3.8.2 Depth of Field
- •3.8.3 Scheimpflug Condition
- •3.8.4 Speckle and Uncertainty
- •3.8.5 Laser Depth of Field
- •3.8.6 Lateral Resolution
- •3.9 Research Challenges
- •3.10 Concluding Remarks
- •3.11 Further Reading
- •3.12 Questions
- •3.13 Exercises
- •References
- •4.1 Introduction
- •Chapter Outline
- •4.2 Representation of 3D Data
- •4.2.1 Raw Data
- •4.2.1.1 Point Cloud
- •4.2.1.2 Structured Point Cloud
- •4.2.1.3 Depth Maps and Range Images
- •4.2.1.4 Needle map
- •4.2.1.5 Polygon Soup
- •4.2.2 Surface Representations
- •4.2.2.1 Triangular Mesh
- •4.2.2.2 Quadrilateral Mesh
- •4.2.2.3 Subdivision Surfaces
- •4.2.2.4 Morphable Model
- •4.2.2.5 Implicit Surface
- •4.2.2.6 Parametric Surface
- •4.2.2.7 Comparison of Surface Representations
- •4.2.3 Solid-Based Representations
- •4.2.3.1 Voxels
- •4.2.3.3 Binary Space Partitioning
- •4.2.3.4 Constructive Solid Geometry
- •4.2.3.5 Boundary Representations
- •4.2.4 Summary of Solid-Based Representations
- •4.3 Polygon Meshes
- •4.3.1 Mesh Storage
- •4.3.2 Mesh Data Structures
- •4.3.2.1 Halfedge Structure
- •4.4 Subdivision Surfaces
- •4.4.1 Doo-Sabin Scheme
- •4.4.2 Catmull-Clark Scheme
- •4.4.3 Loop Scheme
- •4.5 Local Differential Properties
- •4.5.1 Surface Normals
- •4.5.2 Differential Coordinates and the Mesh Laplacian
- •4.6 Compression and Levels of Detail
- •4.6.1 Mesh Simplification
- •4.6.1.1 Edge Collapse
- •4.6.1.2 Quadric Error Metric
- •4.6.2 QEM Simplification Summary
- •4.6.3 Surface Simplification Results
- •4.7 Visualization
- •4.8 Research Challenges
- •4.9 Concluding Remarks
- •4.10 Further Reading
- •4.11 Questions
- •4.12 Exercises
- •References
- •1.1 Introduction
- •Chapter Outline
- •1.2 A Historical Perspective on 3D Imaging
- •1.2.1 Image Formation and Image Capture
- •1.2.2 Binocular Perception of Depth
- •1.2.3 Stereoscopic Displays
- •1.3 The Development of Computer Vision
- •1.3.1 Further Reading in Computer Vision
- •1.4 Acquisition Techniques for 3D Imaging
- •1.4.1 Passive 3D Imaging
- •1.4.2 Active 3D Imaging
- •1.4.3 Passive Stereo Versus Active Stereo Imaging
- •1.5 Twelve Milestones in 3D Imaging and Shape Analysis
- •1.5.1 Active 3D Imaging: An Early Optical Triangulation System
- •1.5.2 Passive 3D Imaging: An Early Stereo System
- •1.5.3 Passive 3D Imaging: The Essential Matrix
- •1.5.4 Model Fitting: The RANSAC Approach to Feature Correspondence Analysis
- •1.5.5 Active 3D Imaging: Advances in Scanning Geometries
- •1.5.6 3D Registration: Rigid Transformation Estimation from 3D Correspondences
- •1.5.7 3D Registration: Iterative Closest Points
- •1.5.9 3D Local Shape Descriptors: Spin Images
- •1.5.10 Passive 3D Imaging: Flexible Camera Calibration
- •1.5.11 3D Shape Matching: Heat Kernel Signatures
- •1.6 Applications of 3D Imaging
- •1.7 Book Outline
- •1.7.1 Part I: 3D Imaging and Shape Representation
- •1.7.2 Part II: 3D Shape Analysis and Processing
- •1.7.3 Part III: 3D Imaging Applications
- •References
- •5.1 Introduction
- •5.1.1 Applications
- •5.1.2 Chapter Outline
- •5.2 Mathematical Background
- •5.2.1 Differential Geometry
- •5.2.2 Curvature of Two-Dimensional Surfaces
- •5.2.3 Discrete Differential Geometry
- •5.2.4 Diffusion Geometry
- •5.2.5 Discrete Diffusion Geometry
- •5.3 Feature Detectors
- •5.3.1 A Taxonomy
- •5.3.2 Harris 3D
- •5.3.3 Mesh DOG
- •5.3.4 Salient Features
- •5.3.5 Heat Kernel Features
- •5.3.6 Topological Features
- •5.3.7 Maximally Stable Components
- •5.3.8 Benchmarks
- •5.4 Feature Descriptors
- •5.4.1 A Taxonomy
- •5.4.2 Curvature-Based Descriptors (HK and SC)
- •5.4.3 Spin Images
- •5.4.4 Shape Context
- •5.4.5 Integral Volume Descriptor
- •5.4.6 Mesh Histogram of Gradients (HOG)
- •5.4.7 Heat Kernel Signature (HKS)
- •5.4.8 Scale-Invariant Heat Kernel Signature (SI-HKS)
- •5.4.9 Color Heat Kernel Signature (CHKS)
- •5.4.10 Volumetric Heat Kernel Signature (VHKS)
- •5.5 Research Challenges
- •5.6 Conclusions
- •5.7 Further Reading
- •5.8 Questions
- •5.9 Exercises
- •References
- •6.1 Introduction
- •Chapter Outline
- •6.2 Registration of Two Views
- •6.2.1 Problem Statement
- •6.2.2 The Iterative Closest Points (ICP) Algorithm
- •6.2.3 ICP Extensions
- •6.2.3.1 Techniques for Pre-alignment
- •Global Approaches
- •Local Approaches
- •6.2.3.2 Techniques for Improving Speed
- •Subsampling
- •Closest Point Computation
- •Distance Formulation
- •6.2.3.3 Techniques for Improving Accuracy
- •Outlier Rejection
- •Additional Information
- •Probabilistic Methods
- •6.3 Advanced Techniques
- •6.3.1 Registration of More than Two Views
- •Reducing Error Accumulation
- •Automating Registration
- •6.3.2 Registration in Cluttered Scenes
- •Point Signatures
- •Matching Methods
- •6.3.3 Deformable Registration
- •Methods Based on General Optimization Techniques
- •Probabilistic Methods
- •6.3.4 Machine Learning Techniques
- •Improving the Matching
- •Object Detection
- •6.4 Quantitative Performance Evaluation
- •6.5 Case Study 1: Pairwise Alignment with Outlier Rejection
- •6.6 Case Study 2: ICP with Levenberg-Marquardt
- •6.6.1 The LM-ICP Method
- •6.6.2 Computing the Derivatives
- •6.6.3 The Case of Quaternions
- •6.6.4 Summary of the LM-ICP Algorithm
- •6.6.5 Results and Discussion
- •6.7 Case Study 3: Deformable ICP with Levenberg-Marquardt
- •6.7.1 Surface Representation
- •6.7.2 Cost Function
- •Data Term: Global Surface Attraction
- •Data Term: Boundary Attraction
- •Penalty Term: Spatial Smoothness
- •Penalty Term: Temporal Smoothness
- •6.7.3 Minimization Procedure
- •6.7.4 Summary of the Algorithm
- •6.7.5 Experiments
- •6.8 Research Challenges
- •6.9 Concluding Remarks
- •6.10 Further Reading
- •6.11 Questions
- •6.12 Exercises
- •References
- •7.1 Introduction
- •7.1.1 Retrieval and Recognition Evaluation
- •7.1.2 Chapter Outline
- •7.2 Literature Review
- •7.3 3D Shape Retrieval Techniques
- •7.3.1 Depth-Buffer Descriptor
- •7.3.1.1 Computing the 2D Projections
- •7.3.1.2 Obtaining the Feature Vector
- •7.3.1.3 Evaluation
- •7.3.1.4 Complexity Analysis
- •7.3.2 Spin Images for Object Recognition
- •7.3.2.1 Matching
- •7.3.2.2 Evaluation
- •7.3.2.3 Complexity Analysis
- •7.3.3 Salient Spectral Geometric Features
- •7.3.3.1 Feature Points Detection
- •7.3.3.2 Local Descriptors
- •7.3.3.3 Shape Matching
- •7.3.3.4 Evaluation
- •7.3.3.5 Complexity Analysis
- •7.3.4 Heat Kernel Signatures
- •7.3.4.1 Evaluation
- •7.3.4.2 Complexity Analysis
- •7.4 Research Challenges
- •7.5 Concluding Remarks
- •7.6 Further Reading
- •7.7 Questions
- •7.8 Exercises
- •References
- •8.1 Introduction
- •Chapter Outline
- •8.2 3D Face Scan Representation and Visualization
- •8.3 3D Face Datasets
- •8.3.1 FRGC v2 3D Face Dataset
- •8.3.2 The Bosphorus Dataset
- •8.4 3D Face Recognition Evaluation
- •8.4.1 Face Verification
- •8.4.2 Face Identification
- •8.5 Processing Stages in 3D Face Recognition
- •8.5.1 Face Detection and Segmentation
- •8.5.2 Removal of Spikes
- •8.5.3 Filling of Holes and Missing Data
- •8.5.4 Removal of Noise
- •8.5.5 Fiducial Point Localization and Pose Correction
- •8.5.6 Spatial Resampling
- •8.5.7 Feature Extraction on Facial Surfaces
- •8.5.8 Classifiers for 3D Face Matching
- •8.6 ICP-Based 3D Face Recognition
- •8.6.1 ICP Outline
- •8.6.2 A Critical Discussion of ICP
- •8.6.3 A Typical ICP-Based 3D Face Recognition Implementation
- •8.6.4 ICP Variants and Other Surface Registration Approaches
- •8.7 PCA-Based 3D Face Recognition
- •8.7.1 PCA System Training
- •8.7.2 PCA Training Using Singular Value Decomposition
- •8.7.3 PCA Testing
- •8.7.4 PCA Performance
- •8.8 LDA-Based 3D Face Recognition
- •8.8.1 Two-Class LDA
- •8.8.2 LDA with More than Two Classes
- •8.8.3 LDA in High Dimensional 3D Face Spaces
- •8.8.4 LDA Performance
- •8.9 Normals and Curvature in 3D Face Recognition
- •8.9.1 Computing Curvature on a 3D Face Scan
- •8.10 Recent Techniques in 3D Face Recognition
- •8.10.1 3D Face Recognition Using Annotated Face Models (AFM)
- •8.10.2 Local Feature-Based 3D Face Recognition
- •8.10.2.1 Keypoint Detection and Local Feature Matching
- •8.10.2.2 Other Local Feature-Based Methods
- •8.10.3 Expression Modeling for Invariant 3D Face Recognition
- •8.10.3.1 Other Expression Modeling Approaches
- •8.11 Research Challenges
- •8.12 Concluding Remarks
- •8.13 Further Reading
- •8.14 Questions
- •8.15 Exercises
- •References
- •9.1 Introduction
- •Chapter Outline
- •9.2 DEM Generation from Stereoscopic Imagery
- •9.2.1 Stereoscopic DEM Generation: Literature Review
- •9.2.2 Accuracy Evaluation of DEMs
- •9.2.3 An Example of DEM Generation from SPOT-5 Imagery
- •9.3 DEM Generation from InSAR
- •9.3.1 Techniques for DEM Generation from InSAR
- •9.3.1.1 Basic Principle of InSAR in Elevation Measurement
- •9.3.1.2 Processing Stages of DEM Generation from InSAR
- •The Branch-Cut Method of Phase Unwrapping
- •The Least Squares (LS) Method of Phase Unwrapping
- •9.3.2 Accuracy Analysis of DEMs Generated from InSAR
- •9.3.3 Examples of DEM Generation from InSAR
- •9.4 DEM Generation from LIDAR
- •9.4.1 LIDAR Data Acquisition
- •9.4.2 Accuracy, Error Types and Countermeasures
- •9.4.3 LIDAR Interpolation
- •9.4.4 LIDAR Filtering
- •9.4.5 DTM from Statistical Properties of the Point Cloud
- •9.5 Research Challenges
- •9.6 Concluding Remarks
- •9.7 Further Reading
- •9.8 Questions
- •9.9 Exercises
- •References
- •10.1 Introduction
- •10.1.1 Allometric Modeling of Biomass
- •10.1.2 Chapter Outline
- •10.2 Aerial Photo Mensuration
- •10.2.1 Principles of Aerial Photogrammetry
- •10.2.1.1 Geometric Basis of Photogrammetric Measurement
- •10.2.1.2 Ground Control and Direct Georeferencing
- •10.2.2 Tree Height Measurement Using Forest Photogrammetry
- •10.2.2.2 Automated Methods in Forest Photogrammetry
- •10.3 Airborne Laser Scanning
- •10.3.1 Principles of Airborne Laser Scanning
- •10.3.1.1 Lidar-Based Measurement of Terrain and Canopy Surfaces
- •10.3.2 Individual Tree-Level Measurement Using Lidar
- •10.3.2.1 Automated Individual Tree Measurement Using Lidar
- •10.3.3 Area-Based Approach to Estimating Biomass with Lidar
- •10.4 Future Developments
- •10.5 Concluding Remarks
- •10.6 Further Reading
- •10.7 Questions
- •References
- •11.1 Introduction
- •Chapter Outline
- •11.2 Volumetric Data Acquisition
- •11.2.1 Computed Tomography
- •11.2.1.1 Characteristics of 3D CT Data
- •11.2.2 Positron Emission Tomography (PET)
- •11.2.2.1 Characteristics of 3D PET Data
- •Relaxation
- •11.2.3.1 Characteristics of the 3D MRI Data
- •Image Quality and Artifacts
- •11.2.4 Summary
- •11.3 Surface Extraction and Volumetric Visualization
- •11.3.1 Surface Extraction
- •Example: Curvatures and Geometric Tools
- •11.3.2 Volume Rendering
- •11.3.3 Summary
- •11.4 Volumetric Image Registration
- •11.4.1 A Hierarchy of Transformations
- •11.4.1.1 Rigid Body Transformation
- •11.4.1.2 Similarity Transformations and Anisotropic Scaling
- •11.4.1.3 Affine Transformations
- •11.4.1.4 Perspective Transformations
- •11.4.1.5 Non-rigid Transformations
- •11.4.2 Points and Features Used for the Registration
- •11.4.2.1 Landmark Features
- •11.4.2.2 Surface-Based Registration
- •11.4.2.3 Intensity-Based Registration
- •11.4.3 Registration Optimization
- •11.4.3.1 Estimation of Registration Errors
- •11.4.4 Summary
- •11.5 Segmentation
- •11.5.1 Semi-automatic Methods
- •11.5.1.1 Thresholding
- •11.5.1.2 Region Growing
- •11.5.1.3 Deformable Models
- •Snakes
- •Balloons
- •11.5.2 Fully Automatic Methods
- •11.5.2.1 Atlas-Based Segmentation
- •11.5.2.2 Statistical Shape Modeling and Analysis
- •11.5.3 Summary
- •11.6 Diffusion Imaging: An Illustration of a Full Pipeline
- •11.6.1 From Scalar Images to Tensors
- •11.6.2 From Tensor Image to Information
- •11.6.3 Summary
- •11.7 Applications
- •11.7.1 Diagnosis and Morphometry
- •11.7.2 Simulation and Training
- •11.7.3 Surgical Planning and Guidance
- •11.7.4 Summary
- •11.8 Concluding Remarks
- •11.9 Research Challenges
- •11.10 Further Reading
- •Data Acquisition
- •Surface Extraction
- •Volume Registration
- •Segmentation
- •Diffusion Imaging
- •Software
- •11.11 Questions
- •11.12 Exercises
- •References
- •Index
5 Feature-Based Methods in 3D Shape Analysis |
189 |
5.2 Mathematical Background
Throughout this chapter, an object is some subset of the ambient Euclidean space, Ω R3. In many cases (e.g. data acquired by a range scanner), we can access only the boundary ∂Ω of the object, which can be modeled as a two-dimensional smooth manifold or surface, denoted here by X. Photometric information is given as a scalar or a vector field α : X → Rd on the manifold and referred to as texture. If the surface is sampled at some discrete set of points {x1, . . . , xN } X, then this representation is called a point cloud; if, in addition, connectivity information is available in the form of a simplicial complex (triangulation, consisting of a set of edges (xi , xj ) E and faces (xi , xj , xk ) F), such a representation is called a mesh.
In medical applications, such as tomographic data analysis, information about the internal structure of the object in addition to its boundary is often available. A common representation in such applications is a volumetric image, which can be represented as a 3D matrix, where each voxel (3D pixel) describes the properties of the object (e.g. its penetrability by X-ray radiation). Segmentation algorithms applied to volumetric data used in medical applications often extract boundaries of 3D objects in implicit form, represented as level-sets of some function f : R3 → R.
5.2.1 Differential Geometry
Both the two-dimensional boundary surface and the three-dimensional volume enclosed by it can be modeled as, respectively, twoand three-dimensional complete Riemannian sub-manifolds of R3. Every point x on the manifold X is assigned a tangent space Tx X. For two dimensional surfaces, the vector N orthogonal to Tx X is called the normal to the surface at x. The tangent space at each point is associated with a smooth inner product gx : Tx X × Tx X → R, usually referred to as the metric tensor. Denoting by x : U R2 → R3 the regular map embedding X into R3, the metric tensor can be expressed in coordinates as
gij = |
∂xT ∂x |
(5.1) |
∂ui ∂uj , |
where ui are the coordinates of U . The metric tensor relates infinitesimal displacements du in the parametrization domain U to displacement on the manifold,
dp2 = g11du12 + 2g12du1du2 + g22du22. |
(5.2) |
This quadratic form is usually referred to as the first fundamental form and it provides a way to define length structures on the manifold. Given a curve C : [0, T ] → X, its length can be expressed as
T
L(C) =
0
C(t ), C(t ) |
1/2 |
dt, |
(5.3) |
|
g ˙ |
˙ |
C(t ) |
|
|
190 A.M. Bronstein et al.
where |
˙ |
denotes the velocity vector. Minimal geodesics are the minimizers of |
L(C) |
, |
||||
|
C |
|
|
|
|
|
|
|
giving rise to the geodesic distances |
|
|
|
|
|
|
||
|
|
d x, x |
= C |
min |
L(C), |
(5.4) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
Γ (x,x ) |
|
|
where Γ (x, x ) is the set of all admissible paths between the points x and x on the surface X (due to completeness assumption, the minimizer always exists). Structures expressible solely in terms of the metric tensor g are called intrinsic. For example, the geodesic can be expressed in this way. The importance of intrinsic structures stems from the fact that they are invariant under isometric transformations (bendings) of the shape. In an isometrically bent shape, the geodesic distances are preserved, which is a property that allows the design of isometrically invariant shape descriptors [31].
The metric tensor also allows the definition of differential operations on the tangent space. Given a smooth scalar field f : X → R, its (intrinsic) gradient X f at point x is defined through the relation f (x + dv) = f (x) + gx ( X f (x), dv), where dv Tx X is an infinitesimal tangent vector. For a given tangent vector v, the quantity
D |
f |
= |
lim |
f (x + εv) − f (x) |
(5.5) |
||
√ |
|
|
|||||
v |
|
ε 0 |
|
|
|
||
|
|
|
→ |
ε gx (v, v) |
|
is called the directional derivative of f at point x in the direction v.
5.2.2 Curvature of Two-Dimensional Surfaces
Given a curve γ : [0, L] → R3, its first-order and second-order derivatives with respect to the parameter, γ˙ and γ¨ , are called the tangent and curvature vectors, respectively. The magnitude of γ¨ (t ) measures the curvature of γ at a point. The curvature of a surface at a point x can be expressed in terms of curves passing through it confined to the surface. Every direction v Tx X can be associated with a curve γ such that γ (0) = x and γ˙ (0) = v, and, thus, with a curvature vector γ¨ (0). The projection of the curvature vector on the tangent plane is called the geodesic curvature, and it vanishes if and only if γ is a geodesic. The projection κn = PN γ¨ (0) of the curvature vector on the normal is called the normal curvature. The minimum and the maximum values of κn are called the principal curvatures κ1 ≤ κ2, and the corresponding directions the principal directions. The average of the two principal curvatures H = 12 (κ1 + κ2) is called the mean curvature, and their product K = κ1κ2 is called the Gaussian curvature.
Surprisingly enough, though the principal curvatures are extrinsic quantities (i.e. quantities depending on the way the surface is embedded into the Euclidean space), the Gaussian curvature is an intrinsic quantity, that is, it can be fully expressed in terms of the metric of the surface. One of such definitions considers the perimeter P (r) of a geodesic circle of radius r centered at a point x on the surface. On
5 Feature-Based Methods in 3D Shape Analysis |
191 |
a Euclidean surface, P (r) = measured. The defect of the cording to
2π r , while on curved surfaces a different quantity is perimeter is governed by the Gaussian curvature ac-
K |
lim |
3(2π r − P (r)) |
. |
(5.6) |
|
||||
|
= r 0 |
π r3 |
|
|
|
→ |
|
|
|
5.2.3 Discrete Differential Geometry
The discretization of differential geometric quantities such as tangent and normal vectors, principal directions and curvatures, gradients, and the Laplace-Beltrami operator requires some attention, as straightforward differentiation with respect to some parametrization coordinates usually amplifies noise to unreasonable levels. In what follows, we briefly overview naïve and more robust methods for estimation of such quantities. The simplest discrete representation of a two-dimensional surface is a point cloud consisting of a set X = {x1, . . . , xn} of discrete points in R3 taken from the underlying continuous surface. Local connectivity information can be introduced by defining an edge set E X × X indicating for each pair of samples (x, x ) in the cloud whether they are adjacent (i.e., (x, x ) E) or not. This leads to an undirected graph representation. It is frequently convenient to approximate a continuous surface by a piecewise-planar one, consisting of a collection of polygonal patches glued together along their edges. A particular case of such polyhedral approximations are triangular meshes in which all faces are triangles built upon triples of points in the point cloud. Each triangle xi , xj , xk can be associated with the normal vector
N |
= |
(xj − xi ) × (xk − xi ) |
. |
(5.7) |
|
||||
|
(xj − xi ) × (xk − xi ) |
|
The normal at a vertex of the mesh can be computed by averaging the normals to the triangles sharing that vertex, possibly weighted by the triangle areas. Such a neighborhood of a vertex is usually referred to as the 1-ring.
In the presence of noisy samples, the support of the 1-rings can be insufficient to reliably approximate the normal vectors. As an alternative, given a vertex x, we can consider the r -neighborhood Nr (x) = Br (x) ∩ X where the ball Br (x) is with respect to the Euclidean metric. The samples in Nr (x) can be further weighted inversely proportionally to their Euclidean distances from x. The weighted second-order moment matrix
M = |
α(y)(y − x)(y − x)T |
(5.8) |
y Nr (x)
represents the orientation of the surface in the vicinity of x. Here, α(y) are assumed to be non-negative weights summing to one. The two largest eigenvectors T1 and
192 |
A.M. Bronstein et al. |
T2 of M span the tangent plane Tx X, while the third, smallest, eigenvector N corresponds to the normal. The tradeoff between sensitivity to small geometric features and robustness to noise is controlled by the local neighborhood radius r .
In the same way that local plane fitting constitutes a robust tool for the approximation of normals and tangents, fitting of a quadratic surface allows the estimation of second-order quantities related to curvature. For that purpose, the points in Nr (x) are first transformed so that x coincides with the origin, the z axis coincides with the normal, and the x and y axes coincide with the tangent vectors (i.e., a point y is represented as y = x + uT1 + vT2 + wN). A paraboloid
w(u, v) = au2 + buv + cv2 |
(5.9) |
is then fit using weighted least squares. The Gaussian and mean curvatures can now be estimated using the closed-form expressions K = 4ac − b2 and H = a + c; the principal curvatures and directions are obtained in a similar way [9]. For a comprehensive overview of curvature discretization methods, the reader is referred to [52].
5.2.4 Diffusion Geometry
The positive semi-definite self-adjoint Laplace-Beltrami operator X associated with the metric tensor g is defined by the identity
f X h dvol = − gx ( X f, X h)dvol, |
(5.10) |
which holds for any pair of smooth scalar fields f, h : X → R;. Here, dvol denotes the differential area or volume element of the manifold, depending, respectively, whether the latter is 2D or 3D.
The Laplace-Beltrami operator can be expressed in the parametrization coordinates as
1 |
∂i det ggij−1∂j . |
|
||
X = − |
√ |
|
(5.11) |
|
det g |
||||
|
|
|
ij |
|
When the metric is Euclidean (gij = I), the operator reduces to the familiar
f = − |
∂2f |
+ |
∂2f |
(5.12) |
∂u12 |
∂u22 |
(note that, in this chapter, we define the Laplacian with the minus sign in order to ensure its positive semi-definiteness).
The Laplace-Beltrami operator gives rise to the partial differential equation
∂ |
+ X f (t, x) = 0, |
(5.13) |
∂t |