Justin Solomon
MIT, Spring 2017
http://pngimg.com/upload/hammer_PNG3886.png
You can learn a lot
about a shape by
hitting it (lightly)
with a hammer!
What can you learn about its shape from
vibration frequencies and
oscillation patterns?
THE COTANGENT LAPLACIAN
Induced by the connectivity of
the triangle mesh.
Discrete Laplacian operators:
What are they good for?
Useful properties of the Laplacian
Applications in graphics/shape analysis
Applications in machine learning
Discrete Laplacian operators:
What are they good for?
Useful properties of the Laplacian
Applications in graphics/shape analysis
Applications in machine learning
https://en.wikipedia.org/wiki/Laplacian_matrix
Deviation from neighbors
Decreasing E
Images made by E. Vouga
Dirichlet energy: Measures smoothness
http://alice.loria.fr/publications/papers/2008/ManifoldHarmonics//photo/dragon_mhb.png
Vibration modes
Image/formula in “Functional Characterization of Instrinsic and Extrinsic Geometry,” TOG 2017 (Corman et al.)
Laplacian only depends on edge lengths
Isometry
[ahy-som-i-tree]:
Bending without stretching.
Global isometry
Local isometry
http://www.revedreams.com/crochet/yarncrochet/nonorientable-crochet/
Isometry invariant
http://www.flickr.com/photos/melvinvoskuijl/galleries/72157624236168459
http://www.4tnz.com/content/got-toilet-paper
Few shapes can deform isometrically
http://www.4tnz.com/content/got-toilet-paper
Few shapes can deform isometrically
Image from: Raviv et al. “Volumetric Heat Kernel Signatures.” 3DOR 2010.
Not the same.
Encodes intrinsic geometry
Edge lengths on triangle mesh, Riemannian metric on manifold
Multi-scale
Filter based on frequency
Geometry through linear algebra
Linear/eigenvalue problems, sparse positive definite matrices
Connection to physics
Heat equation, wave equation, vibration, …
Discrete Laplacian operators:
What are they good for?
Useful properties of the Laplacian
Applications in graphics/shape analysis
Applications in machine learning
http://liris.cnrs.fr/meshbenchmark/images/fig_attacks.jpg
Pointwise quantity
Characterize local geometry
Feature/anomaly detection
Describe point’s role on surface
Symmetry detection, correspondence
http://www.sciencedirect.com/science/article/pii/S0010448510001983
Gaussian and mean curvature
Distinguishing
Provides useful information about a point
Stable
Numerically and geometrically
Intrinsic
No dependence on embedding
Invariant under
Rigid motion
Bending without stretching
Theorema Egregium
(“Totally Awesome
Theorem”):
Gaussian curvature
is intrinsic.
http://www.sciencedirect.com/science/article/pii/S0010448510001983
Gaussian curvature
Second derivative quantity
http://www.integrityware.com/images/MerceedesGaussianCurvature.jpg
Non-unique
Incorporates neighborhood
information in an intrinsic fashion
Stable under small deformation
http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/11_shape_matching.pdf
Heat equation
Heat diffusion patterns are not
affected if you bend a surface.
2 3 4 5 6 7 8 9 10
“Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation”
Rustamov, SGP 2007
2 3 4 5 6 7 8 9 10
If surface does not self-intersect, neither
does the GPS embedding.
Proof: Laplacian eigenfunctions span 𝑳𝟐 (𝚺); if GPS(p)=GPS(q), then all functions
on 𝚺 would be equal at p and q.
2 3 4 5 6 7 8 9 10
GPS is isometry-invariant.
Proof: Comes from the Laplacian.
Assumes unique λ’s
Potential for eigenfunction
“switching”
Nonlocal feature
http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/11_shape_matching.pdf
Heat equation
Image courtesy G. Peyré
Wave equation
Image courtesy G. Peyré
Wave equation
Heat equation
Continuous function of 𝒕 ∈ [𝟎, ∞)
How much heat
diffuses from x to
itself in time t?
“A concise and provably informative multi-scale signature based on heat diffusion”
Sun, Ovsjanikov, and Guibas; SGP 2009
Good properties:
Isometry-invariant
Multiscale
Not subject to switching
Easy to compute
Related to curvature at small scales
Bad properties:
Issues remain with repeated
eigenvalues
Theoretical guarantees require
(near-)isometry
Initial energy
distribution
Average probability over
time that particle is at x.
“The Wave Kernel Signature: A Quantum Mechanical Approach to Shape Analysis”
Aubry, Schlickewei, and Cremers; ICCV Workshops 2012
HKS WKS
vision.in.tum.de/_media/spezial/bib/aubry-et-al-4dmod11.pdf
Good properties:
[Similar to HKS]
Localized in frequency
Stable under some non-isometric
deformation
Some multi-scale properties
Bad properties:
[Similar to HKS]
Can filter out large-scale features
Lots of spectral descriptors in
terms of Laplacian
eigenstructure.
Learn f rather than defining it
Learning Spectral Descriptors for Deformable Shape Correspondence
Litman and Bronstein; PAMI 2014
Maxima of kt(x,x) over x for large t.
A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion
Sun, Ovsjanikov, and Guibas; SGP 2009
Feature points
http://graphics.stanford.edu/projects/lgl/papers/ommg-opimhk-10/ommg-opimhk-10.pdf
http://www.cs.princeton.edu/~funk/sig11.pdf
http://gfx.cs.princeton.edu/pubs/Lipman_2009_MVF/mobius.pdf
Simply match closest points in
descriptor space.
Symmetry
How much heat diffuses from p to x in time t?
One Point Isometric Matching with the Heat Kernel
Ovsjanikov et al. 2010
Theorem: Only have to match one point!
One Point Isometric Matching with the Heat Kernel
Ovsjanikov et al. 2010
Intrinsic symmetries
become extrinsic in
GPS space!
Global Intrinsic Symmetries of Shapes
Ovsjanikov, Sun, and Guibas 2008
“Discrete intrinsic” symmetries
Laplacians appear everywhere
in shape analysis and
geometry processing.
“Biharmonic distance”
Lipman, Rustamov & Funkhouser, 2010
“Geodesics in heat”
Crane, Weischedel, and Wardetzky; TOG 2013
Crane, Weischedel, and Wardetzky. “Geodesics in Heat.” TOG, 2013.
“Implicit fairing of irregular meshes using diffusion and curvature flow”
Desbrun et al., 1999
Choice: Evaluate at time T
Unconditionally stable, but not necessarily accurate for large T!
Implicit time stepping
“Multiresolution analysis of arbitrary meshes”
Eck et al., 1995 (and many others!)
Shape retrieval from
Laplacian eigenvalues
“Shape DNA” [Reuter et al., 2006]
Quadrangulation
Nodal domains [Dong et al., 2006]
Surface deformation
“As-rigid-as-possible” [Sorkine & Alexa, 2007]
Discrete Laplacian operators:
What are they good for?
Useful properties of the Laplacian
Applications in graphics/shape analysis
Applications in machine learning
“Semi-supervised learning using Gaussian fields and harmonic functions”
Zhu, Ghahramani, & Lafferty 2003
Dirichlet energy Linear system of equations (Poisson)
Step 1:
Build k-NN graph
Step 2:
Compute p smallest Laplacian eigenvectors
Step 3:
Solve semi-supervised problem in subspace
“Using Manifold Structure for Partially Labelled Classification”
Belkin and Niyogi; NIPS 2002
Potential fix:
Higher-order
operators
Loss function Regularizer
Dirichlet energy
“Manifold Regularization:
A Geometric Framework for Learning from Labeled and Unlabeled Examples”
Belkin, Niyogi, and Sindhwani; JMLR 2006
Laplacian-regularized least squares (LapRLS)
Laplacian support vector machine (LapSVM)
“On Manifold Regularization”
Belkin, Niyogi, Sindhwani; AISTATS 2005
Embedding from first k eigenvalues/vectors:
Roughly:
𝚿𝐭 𝐱 − 𝚿𝒕 𝒚 is probability that x, y diffuse to the same point in time t.
Robust to sampling
and noise
“Diffusion Maps”
Coifman and Lafon; Applied and Computational Harmonic Analysis, 2006
Image from http://users.math.yale.edu/users/gw289/CpSc-445-545/Slides/CPSC445%20-%20Topic%2010%20-%20Diffusion%20Maps.pdf (nice slides!)
Justin Solomon
MIT, Spring 2017
