- •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 |
213 |
Fig. 5.9 Retrieval results using bags of features computed with HKS and SI-HKS, tested on the SHREC’10 robust large-scale shape retrieval dataset. Left: query shapes, middle: first three matches obtained with HKS descriptors, right: first three matches obtained with SI-HKS descriptors. Only a single correct match exists in the database (marked in red), and ideally, it should be the first one
features to correctly find similarity between scaled shapes, which makes the use of SI-HKS preferable over HKS in problems involving arbitrary shape scaling.
5.5 Research Challenges
Current challenges in descriptor research include finding a good proportion between theoretical invariance, discriminativity, sensitivity to noise and computational complexity. A single ideal tradeoff is unlikely to be found, since these parameters heavily depend on the application.
Another important challenge of interest both in 2D image and 3D shape analysis is incorporating spatial relations between features. Most feature descriptors capture only local information of the shape, while it is known that, in many cases, the spatial relations between different features are not less important. For example, on a human hand one would find five similar features corresponding to fingers, while their particular spatial configuration is what makes the object recognizable as a hand. Taking this example ad absurdum, one can think of a “soup of features” which have no clear
214 |
A.M. Bronstein et al. |
spatial configuration. Recent works on symmetry [40, 59, 62, 66, 67], self-similarity [18, 64] and structure detection is a step in this direction.
5.6 Conclusions
This chapter described feature-based methods in 3D shape analysis that are commonly used in applications such as content-based shape retrieval and invariant shape correspondence. Though not completely new, this field is relatively unexplored in shape analysis and has lagged behind similar methods in 2D image analysis. The success of feature-based methods in computer vision has recently brought significant interest for developing similar approaches in shape analysis, either by finding analogies to 2D image features, or by exploiting 3D shape-specific construction.
This chapter tried to overview the basic ideas and principles in modern featurebased shape analysis models, placing an emphasis on feature detection and description, their invariance and quality. For different applications of these methods (e.g. in shape retrieval), the reader is referred to other chapters in this book.
It should be understood that feature-based shape analysis is a complicated pipeline with inter-dependent stages and, in particular, feature detection and description is a linked pair of operations. In some cases, the link is very natural and homogeneous and falls under the same mathematical model. For example, heat kernels can be used for both detection (heat kernel features) and description (heat kernel signatures).
More generically, it is possible to use different methods for feature detection and description. However, it is important to understand the strengths and limitations of each approach, which are often dependent on the data in hand. For example, one might use Gaussian curvature extrema as a detector, but then using spin images as a descriptor could be a bad idea, since they depend on the normal and Gaussian curvature extrema are exactly where this normal is changing the most.
5.7 Further Reading
For a broad overview of geometric foundations and algorithms in shape analysis, we refer the reader to [16]. For an excellent comprehensive treatment of differential and Riemannian geometry the reader is referred to [28] and [7]. While focusing on local features in this chapter, we intentionally completely left aside an interesting and broad field on global or holistic shape descriptors based on global geometric quantities such as metric distributions. The reader is referred to the chapter on manifold intrinsic similarity in [72] for an overview of these methods. An introduction to diffusion geometry and diffusion maps can be found in [25]. Details of SHREC’10 benchmarks mentioned in this chapter appear in [12–14]. Algorithms for dimensionality reduction and hashing of descriptors in the context of deformable shape retrieval are discussed in [11, 79]. For additional details on shape retrieval, refer to Chap. 7 of this book.
5 Feature-Based Methods in 3D Shape Analysis |
215 |
5.8 Questions
1.Give three example applications where feature-based methods in 3D shape analysis are useful.
2.What qualities do we look for in a good feature detector?
3.What qualities do we look for in a good feature descriptor?
4.Explain why descriptor invariance and the information richness of a descriptor often need to be traded-off against each other. Use spin images as an example in your argument.
5.Explain why Gaussian curvature is an intrinsic shape property, whereas mean curvature is not.
6.Outline how heat kernel signatures can be used to determine a set of correspondences across two shapes.
7.Explain the effect of global uniform shape scaling of the shape on the eigenfunctions and eigenvalues of the Laplace-Beltrami operator.
5.9 Exercises
1.Compute the Gaussian curvature map on a 3D shape and display it as a colormap. Which points have positive Gaussian curvature? Negative curvature?
2.Repeat Exercise 1 using several local scales. How does it affect the result?
3.Determine the local extrema of the Gaussian curvature at the most suitable scale. Display the detected points by overlaying them on the 3D shape.
4.Compute a set of descriptors at the points detected in Exercise 3. As the descriptor at each point, use the coordinates x, y, z. Under what circumstances is x, y, z a good/poor choice of descriptor with this particular detector?
5.Match the descriptors across a pair of facial scans of the same person using simple Euclidean metric. Note the problems matching across the symmetrical face. Suggest solutions to this problem of point matching for symmetrical objects.
6.Given a shape represented as a triangular mesh, discretize the Laplace-Beltrami operator using the cotangent weights formula. Compute and show the eigenvalues and eigenfunctions of the Laplace-Beltrami operator.
7.Test the effect of shape transformations on the eigenvalues and eigenfunctions of the Laplace-Beltrami operator. Experimentally confirm their bendinginvariance.
8.Using the eigenvalues and eigenfunctions of the Laplace-Beltrami operator, compute the heat kernel. Show the heat kernel diagonal values at points of different curvature.
9.Using the heat kernel diagonal, compute the HKS descriptor. Test its behavior for different values of time scale.
10.Compute dense HKS descriptor on multiple shapes (use for example the SHREC dataset). Create a geometric vocabulary by clustering in the HKS descriptor space. Compute a bag of features by means of vector quantization of
216 |
A.M. Bronstein et al. |
the descriptors in the geometric vocabulary. Compare different settings of hard and soft quantization.
11.Using bags of features computed in Exercise 10, perform shape retrieval on a dataset of shapes undergoing deformations. Experimentally observe invariance and sensitivity of the descriptors.
References
1.Agarwal, P.K., Edelsbrunner, H., Harer, J., Wang, Y.: Extreme elevation on a 2-manifold. In: SCG’04: Proceedings of the twentieth annual symposium on Computational Geometry,
pp.357–365 (2004)
2.Andreetto, M., Brusco, N., Cortelazzo, G.M.: Automatic 3D modeling of textured cultural heritage objects. IEEE Trans. Image Process. 13(3), 335–369 (2004)
3.Assfalg, J., Bertini, M., Pala, P., Del Bimbo, A.: Content-based retrieval of 3d objects using spin image signatures. IEEE Trans. Multimed. 9(3), 589–599 (2007)
4.Bay, H., Tuytelaars, T., Van Gool, L.: SURF: speeded up robust features. In: Proc. ECCV,
pp.404–417 (2006)
5.Belongie, S., Malik, J., Puzicha, J.: Shape matching and object recognition using shape contexts. Trans. PAMI, 509–522 (2002)
6.Ben-Chen, M., Weber, O., Gotsman, C.: Characterizing shape using conformal factors. In: Proc. 3DOR (2008)
7.Berger, M.: A Panoramic View of Riemannian Geometry. Springer, Berlin (2003)
8.Besl, P.J.: Surfaces in Range Image Understanding. Springer, Berlin (1988)
9.Besl, P.J., Jain, R.C.: Invariant surface characteristics for 3d object recognition in range images. Comput. Vis. Graph. Image Process. 33(1), 33–80 (1986)
10.Bronstein, A., Bronstein, M., Bruckstein, A., Kimmel, R.: Partial similarity of objects, or how to compare a centaur to a horse. Int. J. Comput. Vis. 84(2), 163–183 (2009)
11.Bronstein, A., Bronstein, M., Guibas, L., Ovsjanikov, M.: Shape Google: geometric words and expressions for invariant shape retrieval. ACM Trans. Graph. 30(1) (2011)
12.Bronstein, A.M., Bronstein, M.M., Bustos, B., Castellani, U., Crisani, M., Falcidieno, B., Guibas, L.J., Isipiran, I., Kokkinos, I., Murino, V., Ovsjanikov, M., Patané, G., Spagnuolo, M., Sun, J.: Shrec 2010: robust feature detection and description benchmark. In: Proc. 3DOR (2010)
13.Bronstein, A.M., Bronstein, M.M., Castellani, U., Falcidieno, B., Fusiello, A., Godil, A., Guibas, L.J., Kokkinos, I., Lian, Z., Ovsjanikov, M., Patané, G., Spagnuolo, M., Toldo, R.: Shrec 2010: robust large-scale shape retrieval benchmark. In: Proc. 3DOR (2010)
14.Bronstein, A.M., Bronstein, M.M., Castellani, U., Guibas, A.D.L.J., Horaud, R.P., Kimmel, R., Knossow, D., von Lavante, E., Mateus, D., Ovsjanikov, M., Sharma, A.: Shrec 2010: robust correspondence benchmark. In: Proc. 3DOR (2010)
15.Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Three-dimensional face recognition. Int. J. Comput. Vis. 64(1), 5–30 (2005)
16.Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Numerical Geometry of Non-rigid Shapes. Springer, New York (2008)
17.Bronstein, A.M., Bronstein, M.M., Kimmel, R., Mahmoudi, M., Sapiro, G.: A GromovHausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching. In: IJCV (2010)
18.Bronstein, A.M., Bronstein, M.M., Mitra, N.J.: Intrinsic regularity detection in 3D geometry. In: Proc. ECCV (2010)
19.Bronstein, A.M., Bronstein, M.M., Ovsjanikov, M., Guibas, L.J.: Shape Google: a computer vision approach to invariant shape retrieval. In: Proc. NORDIA (2009)
5 Feature-Based Methods in 3D Shape Analysis |
217 |
20.Bronstein, M.M., Kokkinos, I.: Scale-invariant heat kernel signatures for non-rigid shape recognition. In: Proc. CVPR (2010)
21.Castellani, U., Cristani, M., Fantoni, S., Murino, V.: Sparse points matching by combining 3D mesh saliency with statistical descriptors. Comput. Graph. Forum 27, 643–652 (2008)
22.Chazal, F., Guibas, L., Oudot, S., Skraba, P.: Persistence-based clustering in Riemannian manifolds. In: Proceedings of the 27th annual ACM symposium on Computational Geometry (2009)
23.Chum, O., Philbin, J., Sivic, J., Isard, M., Zisserman, A.: Total recall: automatic query expansion with a generative feature model for object retrieval. In: Proc. ICCV (2007)
24.Clarenz, U., Rumpf, M., Telea, A.: Robust feature detection and local classification for surfaces based on moment analysis. IEEE Trans. Vis. Comput. Graph. 10(5), 516–524 (2004)
25.Coifman, R., Lafon, S.: Diffusion maps. Appl. Comput. Harmon. Anal. 21(1), 5–30 (2006)
26.Dey, T.K., Li, K., Luo, C., Ranjan, P., Safa, I., Wang, Y.: Persistent heat signature for Poseoblivious matching of incomplete models. In: Proc. SGP, pp. 1545–1554 (2010)
27.Digne, J., Morel, J., Audfray, N., Mehdi-Souzani, C.: The level set tree on meshes. In: Fifth International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT’10) (2010)
28.Do Carmo, M.: Differential Geometry of Curves and Surfaces, vol. 2. Prentice-Hall, Englewood Cliffs (1976)
29.Edelsbrunner, H., Harer, J.: Computational Topology. An Introduction. Am. Math. Soc., Providence (2010)
30.Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002)
31.Elad, A., Kimmel, R.: On bending invariant signatures for surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 25(10), 1285–1295 (2003)
32.Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. Adv. Multiresol. Geom. Model. 1 (2005)
33.Gebal, K., Bærentzen, J.A., Aanæs, H., Larsen, R.: Shape analysis using the auto diffusion function. Comput. Graph. Forum 28(5), 1405–1413 (2009)
34.Gelfand, N., Mitra, N.J., Guibas, L.J., Pottmann, H.: Robust global registration. In: Proc. SGP (2005)
35.Glomb, P.: Detection of interest points on 3D data: extending the Harris operator. In: Computer Recognition Systems 3. Advances in Soft Computing, vol. 57, pp. 103–111. Springer, Berlin (2009)
36.Harris, C., Stephens, M.: A combined corner and edge detection. In: Proc. Fourth Alvey Vision Conference, pp. 147–151 (1988)
37.Itti, L., Koch, C., Niebur, E.: A model of saliency-based visual attention for rapid scene analysis. Trans. PAMI 20(11) (1998)
38.Johnson, A., Spin-images: a representation for 3-d surface matching. Ph.D. thesis, Carnegie Mellon University (1997)
39.Johnson, A.E., Hebert, M.: Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans. Pattern Anal. Mach. Intell. 21(5), 433–449 (1999)
40.Kazhdan, M., Funkhouser, T., Rusinkiewicz, S.: Symmetry descriptors and 3D shape matching. In: Proc. SGP, pp. 115–123 (2004)
41.Kim, V.G., Lipman, Y., Funkhouser, T.: Blended intrinsic maps. In: Proc. SIGGRAPH (2011)
42.Koehl, P.: Protein structure similarities. Curr. Opin. Struct. Biol. 11(3), 348–353 (2001)
43.Koenderink, J.J., van Doorn, A.J.: Surface shape and curvature scales. Image Vis. Comput. 10(8), 557–564 (1992)
44.Kokkinos, I., Yuille, A.: Scale invariance without scale selection. In: Proc. CVPR (2008)
45.Kolomenkin, M., Shimshoni, I., Tal, A.: On edge detection on surfaces. In: Proc. CVPR (2009)
46.Körtgen, M., Park, G., Novotni, M., Klein, R.: 3d shape matching with 3d shape contexts. In: Central European Seminar on Computer Graphics (2003)
218 |
A.M. Bronstein et al. |
47.Kovnatsky, A., Bronstein, M.M., Bronstein, A.M., Kimmel, R.: Photometric heat kernel signatures. In: Proc. Conf. on Scale Space and Variational Methods in Computer Vision (SSVM) (2011)
48.Lévy, B.: Laplace-Beltrami eigenfunctions towards an algorithm that “understands” geometry. In: Int. Conf. Shape Modeling and Applications (2006)
49.Litman, R., Bronstein, A.M., Bronstein, M.M.: Diffusion-geometric maximally stable component detection in deformable shapes. In: Computers and Graphics (2011)
50.Lo, T., Siebert, J.: Local feature extraction and matching on range images: 2.5 D SIFT. Comput. Vis. Image Underst. 113(12), 1235–1250 (2009)
51.Lowe, D.: Distinctive image features from scale-invariant keypoint. In: IJCV (2004)
52.Magid, E., Soldea, O., Rivlin, E.: A comparison of Gaussian and mean curvature estimation methods on triangular meshes of range image data. Comput. Vis. Image Underst. 107(3), 139– 159 (2007)
53.Mahmoudi, M., Sapiro, G.: Three-dimensional point cloud recognition via distributions of geometric distances. Graph. Models 71(1), 22–31 (2009)
54.Manay, S., Hong, B., Yezzi, A., Soatto, S.: Integral invariant signatures. In: Computer VisionECCV 2004, pp. 87–99 (2004)
55.Matas, J., Chum, O., Urban, M., Pajdla, T.: Robust wide-baseline stereo from maximally stable extremal regions. Image Vis. Comput. 22(10), 761–767 (2004)
56.Mateus, D., Horaud, R.P., Knossow, D., Cuzzolin, F., Boyer, E.: Articulated shape matching using Laplacian eigenfunctions and unsupervised point registration. In: Proc. CVPR (2008)
57.Meyer, M., Desbrun, M., Schroder, P., Barr, A.H.: Discrete differential-geometry operators for triangulated 2-manifolds. In: Visualization and Mathematics III, pp. 35–57 (2003)
58.Mitra, N.J., Guibas, L.J., Giesen, J., Pauly, M.: Probabilistic fingerprints for shapes. In: Proc. SGP (2006)
59.Mitra, N.J., Guibas, L.J., Pauly, M.: Partial and approximate symmetry detection for 3D geometry. ACM Trans. Graph. 25(3), 560–568 (2006)
60.Najman, L., Couprie, M.: Building the component tree in quasi-linear time. IEEE Trans. Image Process. 15(11), 3531–3539 (2006)
61.Natarajan, V., Koehl, P., Wang, Y., Hamann, B.: Visual analysis of biomolecular surfaces. In: Visualization in Medicine and Life Sciences, Mathematics and Visualization, pp. 237–255 (2008)
62.Ovsjanikov, M., Sun, J., Guibas, L.J.: Global intrinsic symmetries of shapes. Comput. Graph. Forum 27(5), 1341–1348 (2008)
63.Pauly, M., Keiser, R., Gross, M.: Multi-scale feature extraction on point-sampled surfaces. Comput. Graph. Forum 22(3), 281–289 (2003)
64.Pauly, M., Mitra, N.J., Wallner, J., Pottmann, H., Guibas, L.J.: Discovering structural regularity in 3D geometry. In: Proc. SIGGRAPH (2008)
65.Pinkall, U., Polthier, K.: Computing discrete minimal surfaces and their conjugates. Exp. Math. 2(1), 15–36 (1993)
66.Raviv, D., Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Symmetries of non-rigid shapes. In: Proc. NRTL (2007)
67.Raviv, D., Bronstein, A.M., Bronstein, M.M., Kimmel, R., Sapiro, G.: Diffusion symmetries of non-rigid shapes. In: Proc. 3DPVT (2010)
68.Raviv, D., Bronstein, M.M., Bronstein, A.M., Kimmel, R.: Volumetric heat kernel signatures. In: Proc. ACM Multimedia Workshop on 3D Object Retrieval (2010)
69.Reuter, M.: Hierarchical shape segmentation and registration via topological features of Laplace-Beltrami eigenfunctions. Int. J. Comput. Vis. 89(2), 287–308 (2010)
70.Reuter, M., Wolter, F.E., Peinecke, N.: Laplace-spectra as fingerprints for shape matching. In: Proc. ACM Symp. Solid and Physical Modeling, pp. 101–106 (2005)
71.Rustamov, R.M.: Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In: Proc. SGP, pp. 225–233 (2007)
72.Scherzer, O.: Handbook of Mathematical Methods in Imaging. Springer, Berlin (2010)
5 Feature-Based Methods in 3D Shape Analysis |
219 |
73.Shilane, P., Funkhauser, T.: Selecting distinctive 3D shape descriptors for similarity retrieval. In: Proc. Shape Modelling and Applications (2006)
74.Sipiran, I., Bustos, B.: A robust 3D interest points detector based on Harris operator. In: Proc. 3DOR, pp. 7–14. Eurographics (2010)
75.Sivic, J., Zisserman, A.: Video Google: A text retrieval approach to object matching in videos. In: Proc. CVPR (2003)
76.Skraba, P., Ovsjanikov, M., Chazal, F., Guibas, L.: Persistence-based segmentation of deformable shapes. In: Proc. NORDIA, pp. 45–52 (2010)
77.Sochen, N., Kimmel, R., Malladi, R.: A general framework for low level vision. IEEE Trans. Image Process. 7(3), 310–318 (1998)
78.Starck, J., Hilton, A.: Correspondence labelling for widetimeframe free-form surface matching. In: Proc. ICCV (2007)
79.Strecha, C., Bronstein, A.M., Bronstein, M.M., Fua, P.: LDAHash: improved matching with smaller descriptors. Technical Report, EPFL (2010)
80.Sumner, R.W., Popovic,´ J.: Deformation transfer for triangle meshes. In: Proc. Conf. Computer Graphics and Interactive Techniques, pp. 399–405 (2004)
81.Sun, J., Ovsjanikov, M., Guibas, L.: A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graph. Forum 28(5), 1383–1392 (2009)
82.Thorstensen, N., Keriven, R.: Non-rigid shape matching using geometry and photometry. In: Proc. CVPR (2009)
83.Toldo, R., Castellani, U., Fusiello, A.: Visual vocabulary signature for 3D object retrieval and partial matching. In: Proc. 3DOR (2009)
84.Torresani, L., Kolmogorov, V., Rother, C.: Feature correspondence via graph matching: models and global optimization. In: Proc. ECCV, pp. 596–609 (2008)
85.Wang, C., Bronstein, M.M., Bronstein, A.M., Paragios, N.: Discrete minimum distortion correspondence problems for non-rigid shape matching. In: Proc. Conf. on Scale Space and Variational Methods in Computer Vision (SSVM) (2011)
86.Wardetzky, M., Mathur, S., Kälberer, F., Grinspun, E.: Discrete Laplace operators: no free lunch. In: Conf. Computer Graphics and Interactive Techniques (2008)
87.Zaharescu, A., Boyer, E., Varanasi, K., Horaud, R.: Surface feature detection and description with applications to mesh matching. In: Proc. CVPR (2009)