• No results found

Spectral Geometry

N/A
N/A
Protected

Academic year: 2022

Share "Spectral Geometry"

Copied!
76
0
0

Laster.... (Se fulltekst nå)

Fulltekst

(1)

Inverse Computational Spectral Geometry

Simone Melzi Luca Cosmo Emanuele Rodolà Maks Ovsjanikov Michael Bronstein

Tutorial:

4/4

(2)

Partial shapes

(3)

Subregions of a given shape

(4)

Motivations

Full shape

Partial shape Mask

Interface / Non-interface Protein A Protein B

Scan

Template Registration

(5)

Question 1

• What is the relation between the global spectrum and the spectrum of the partialities?

Spectrum

?

Spectrum

(6)

Question 1b

• What is the relation between the spectra of different partialities?

Spectrum

?

Spectrum

(7)

Question 2

• Can we solve inverse problems starting from the spectrum of partialities?

Spectrum

?

(8)

The spectrum of Partial shapes

Spectrum Operator

(9)

Different possible operators

Laplacian of the patch Hamiltonian LMH

Increasing dependency between the entire shape and the partiality

“Localized Manifold Harmonics for Spectral Shape Analysis”,

S. Melzi et al. 2018.

“Computing Discrete Minimal Surfaces and Their Conjugates”,

U. Pinkall et al. 1993.

“Hamiltonian operator for spectral shape analysis”, Y. Choukroun et al. 2018.

(10)

Partial Functional Maps (PFM)

“Partial functional correspondence”, E. Rodolà et al. 2017.

(11)

“Partial functional correspondence”, E. Rodolà et al. 2017.

Partial Laplacian eigenfunctions

(12)

Partial Laplacian eigenvalues

“Partial functional correspondence”, E. Rodolà et al. 2017.

Weyl’s law: The Laplacian spectrum has a slope inversely proportional to the surface area.

(13)

Partial Functional Maps (PFM)

“Partial functional correspondence”, E. Rodolà et al. 2017.

data regularity

𝒗 Preserve the area of 𝑌+ smoothness

𝑌

(14)

Remark

• Spectral quantities can be used to analyze partialities of 3D objects

(15)

Can we retrieve the partial shape that generates a given

spectrum?

(16)

Correspondence-Free Region Localization for

Partial Shape Similarity via Hamiltonian Spectrum Alignment

“Correspondence-Free Region Localization for Partial Shape Similarity via Hamiltonian Spectrum Alignment”, A. Rampini et al. 2019.

(17)

Background: Laplace-Beltrami operator

(18)

Background: Laplace-Beltrami operator

… …

Laplacian spectrum

(19)

Background: Hamiltonian operator

Potential function

“Hamiltonian operator for spectral shape analysis”, Y. Choukroun et al. 2018.

(20)

Background: Hamiltonian operator

Potential function

“Hamiltonian operator for spectral shape analysis”, Y. Choukroun et al. 2018.

(21)

Background: Hamiltonian operator

… …

Hamiltonian spectrum Step potential

“Hamiltonian operator for spectral shape analysis”, Y. Choukroun et al. 2018.

(22)

Our approach: main idea

… …

… …

Theorem: There exists a step potential for which the Hamiltonian on the full shape and the LBO on the partial shape share the same spectrum:

(23)

Optimization problem

(24)

Optimization problem

(25)

Optimization problem

(26)

Optimization problem

(27)

Optimization problem

(28)

Implementation details:

• Optimize over with saturation

• Trust Region

• Initialization: multistart

Optimization problem

(29)
(30)

Examples

0.90 0.85 0.95

0.96 0.99 0.98

(31)

Pros

1. Correspondence-free

2. Invariance to isometries

3. No descriptors in the optimization

Partial Functional Maps (PFM) is the main competitor

(32)

Qualitative comparisons

0.39 0.79 0.48 0.77

0.38 0.96 0.62 0.96

PFM PFM

(33)

Limitations and future directions

• Different local minima

• Strong dependency on the discretization

• Computation of the spectrum is not efficient

• Improve robustness to noise

• Consider other data

• Learning pipeline

(34)

Can we perform operations in

the space of partial spectra?

(35)
(36)

Spectrum

Spectrum

Spectrum

(37)

Spectral Unions of Partial Deformable 3D Shapes

“Spectral Unions of Partial Deformable 3D Shapes”, L. Moschella et al. 2021.

(38)

Motivation

Localization of the union on a given template

• Full geometry reconstruction from partial views

Shape retrieval from partial views

(39)

Do we need correspondences?

(40)

Do we need correspondences?

Typical pipeline:

1. Find partial correspondence

(41)

Do we need correspondences?

Typical pipeline:

1. Find partial correspondence

2. Extract non-rigid transformation

(42)

Do we need correspondences?

Typical pipeline:

1. Find partial correspondence

2. Extract non-rigid transformation 3. Merge partial views into a

consistent discretization

(43)

Isometry invariant representation

(44)

The Spectrum is the right tool

• Invariant to isometries

• Invariant to different representations

• Does not require a correspondence

(45)

Spectral decoder

Laplacian eigenvalues

Laplacian eigenvalues

Laplacian eigenvalues

Spectral

union

Learning the spectral union

(46)

Spectral Union

(47)
(48)
(49)

“Instant recovery of shape from spectrum via latent space connections”, R. Marin et al., 2020.

(50)
(51)
(52)

Limitations and future directions

• Different local minima

• Strong dependency on the boundary

• Missing guarantee that the predicted sequences are eigenvalues

• Improve robustness to noise

• Injecting a spectral term in the loss

• Other operations

(53)

What is next?

(54)

Other data

Range map

Point clouds Volumetric

“Implicit Geometric Regularization for Learning Shapes”, A. Gropp et al., 2020

Implicit

“Fast Parallel Surface and Solid Voxelization on GPUs”, M. Schwarz et al., 2010

(55)

General approach

1. Define an operator (Laplacian)

2. Study its eigenvalues

3. Analyze the variables that define the data

4. Write these variables as a function of the spectrum

5. Define a procedure to solve this function

Spectrum Operator

?

(56)

Graphs

Social networks Molecules Functional networks Road maps

(57)

Graph spectrum

0=0 1=0.15 2=0.25 3=0.59 4=0.95 18=5.27

(58)

Graph spectrum

?

(59)

Is it possible to recover a graph

from its eigenvalues?

(60)

“Generation of isospectral graphs“, L. Halbeisen et al., 1999

General answer: NO

(61)

A special case

“Reconstruction of weighted graphs by their spectrum“, L. Halbeisen et al., 2000

Generalized eigenproblem:

L x =  M x

M = diag(m1,…,mn)

m1

m3

m2

(62)

“Isospectral and Subspectral Molecules“, S. S. D’Amato et al., 1980

Subspectral and graphs

(63)

Are graphs harder than shapes?

Isospectralization recovers 3×N numbers from k eigenvalues

it works well if we parametrize the shape with O(k) parameters

Graphs are defined by N2numbers of the adjacency matrix

(64)

Open problems

(65)

Standard eigenvalues computation

Compute eigenvalues of an operator via eigensolvers (Lanczos method)

operator

eigensolver

Spectrum

(66)

“Alien” Learnable eigenvalues computation

Estimated spectrum GT spectrum We can try to learn them via neural networks.

(67)

Why is it important?

Standard methods are slow for optimization-online augmentation:

Standard eigensolver: ~0.3 s (~6K vertices – first order) Standard eigensolver: ~48 s (~30K vertices – third order)

We can use NNs as differentiable blocks in other pipelines

(68)

A first solution

“Instant recovery of shape from spectrum via latent space connections”, R. Marin et al., 2020.

(69)

Application: fast isospectralization

Isospectralization requires gradient with respect to eigenvalues

With solver is hard/slow to compute

Use eigenvalue approximator

“Isospectralization, or how to hear shape, style, and correspondence“, L. Cosmo et al., 2019

(70)

Some considerations

Instability of higher frequencies: could be solved via hierarchical architectures

Invariance to isometry must be imposed:

Training loss not clearly defined

(71)

Several local minima

Existence of several local minima in the isospectralization problem

Symmetries and Isometries

(72)

Space of meaningful shapes

The spectral information can lead out of the space of “real” shapes

Target With prior Without prior

(73)

Thanks!

Special thanks to A. Rampini, E. Postolache and L. Moschella for some of these slides

(74)

Outline

Partialities and geometry processing

Correspondence-free region localization

Spectral Unions

Other domains

Open problems and Limitations

(75)
(76)

Referanser

RELATERTE DOKUMENTER

In this contest the structural shape retrieval track focuses on the retrieval of 3d models which exhibit a relevant similarity in the shape structure.. Shape structure is

To this end, we compare three approaches to se- lect a specific set of eigenvalues such that the corresponding shape classification error on the input benchmark data set is

Figure 5: Different manners of solving the correspondence problem for the input shapes shown in (a) and their feature points (indicated by the circles): (b) computing a

correspondence deformation partial overlap.. Chicken &

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis... Dimensions

Whether cut regions are patched up or not, the geodesic information on a partial surface slightly changes with respect to its complete version, introducing some extra imperfection

It covers algorithms for establishing correspondence, methods for modeling shape variation, image segmentation algorithms such as the Active Shape Model and evaluation methodology

Then, we apply a sequence alignment algorithm to compute the locally optimal alignment between the two cluster label sequences, and to compute the similarity metric by normalizing