Alignment and Matching Thomas Funkhouser and Michael Kazhdan

Alignment and Matching Thomas Funkhouser and Michael Kazhdan Princeton University Challenge The shape of model does not change when the model is translated, scaled, or rotated Translation = Rotation Scale Outline Matching

Alignment Exhaustive Search Invariance Normalization Part vs. Whole Conclusion Exhaustive Search Search for the best aligning transformation: Compare at all alignments Match at the alignment for which models are closest Exhaustive search for optimal rotation Exhaustive Search Search for the best aligning transformation:

Compare at all alignments Match at the alignment for which models are closest Exhaustive Search Search for the best aligning transformation: Use signal processing for efficient correlation Represent model at many different transformations Properties: Gives the correct answer Is hard to do efficiently Outline Matching Alignment

Exhaustive Search Invariance Normalization Part vs. Whole Conclusion Invariance Represent a model with information that is independent of the transformation: Extended Gaussian Image, Horn: Translation invariant Shells Histograms, Ankerst: Rotation invariant D2 Shape Distributions, Osada: Translation/Rotation invariant EGI Shells Histogram

D2 Distribution Invariance Represent a model with information that is independent of the transformation Energy Energy Power spectrum representation Fourier Transform for translation and 2D rotations Spherical Harmonic Transform for 3D rotations Frequency Circular Power Spectrum Frequency

Spherical Power Spectrum Translation Invariance 1D Function Translation Invariance = + + + 1D Function Cosine/Sine Decomposition

+ Translation Invariance = + + + 1D Function = Constant Frequency Decomposition

+ Translation Invariance = + + + + 1D Function +

= Constant 1st Order Frequency Decomposition + Translation Invariance = + + +

+ + + 1D Function = Constant 1st Order 2nd Order Frequency Decomposition +

Translation Invariance = + + + + + + +

+ + 1D Function = Constant 1st Order 2nd Order 3rd Order Frequency Decomposition

Translation Invariance = Amplitudes invariant + + + to translation + + +

1D Function + = Constant + 1st Order + 2nd Order 3rd Order Frequency Decomposition Rotation Invariance

Represent each spherical function as a sum of harmonic frequencies (orders) = + + Constant 1st Order + + 3rd Order 2nd Order +

+ Rotation Invariance Store how much (L2-norm) of the shape resides in each frequency to get a rotation invariant representation Constant = 1st Order + 3rd Order 2nd Order

+ + Power Spectrum Translation-invariance: Represent the model in a Cartesian coordinate system Compute the 3D Fourier transform Store the amplitudes of the frequency components Cartesian Coordinates f ( x, y, z ) f l ,m ,n ei (lx my zn ) l ,m ,n y x

z f l ,m,n l ,m,n Translation Invariant Representation Power Spectrum Single axis rotation-invariance: Represent the model in a cylindrical coordinate system Compute the Fourier transform in the angular direction Cylindrical Coordinates Store the amplitudes of the frequency components

i ( k ) f ( r , h , ) f ( r , h ) e k r

k h f k ( r , h) k Rotation Invariant Representation Power Spectrum Full rotation-invariance: Represent the model in a spherical coordinate system Compute the spherical harmonic transform Store the amplitudes of the Spherical frequency components

Coordinates f (r , , ) f l ,m (r )Yl m ( , ) l r m l m l

f l (r ) l m 2 Rotation Invariant Representation Power Spectrum Power spectrum representations Are invariant to transformations Give a lower bound for the best match Tend to discard too much information Translation invariant: n3 data -> n3/2 data Single-axis rotation invariant: n3 data -> n3/2 data Full rotation invariant: n3 data -> n2

data Power Spectrum Shells Histogram Method Translation Rotation EGI Constant Order Crease Histograms Constant Order

Spherical: Constant Order D2 Square Spherical: Constant Order Shells Spherical: Constant Order Spherical Extent Cylindrical: Full Outline

Matching Alignment Exhaustive Search Invariance Normalization Part vs. Whole Conclusion Normalization Place a model into a canonical coordinate frame by normalizing for: Translation Scale Rotation

Translation Rotation Scale Normalization [Horn et al., 1988] Place a model into a canonical coordinate frame by normalizing for: Translation: Center of mass Scale Rotation Initial Models Translation-Aligned Models

Normalization [Horn et al., 1988] Place a model into a canonical coordinate frame by normalizing for: Translation Scale: Mean variance Rotation Translation-Aligned Models Translation- and Scale-Aligned Models Normalization Place a model into a canonical coordinate frame by normalizing for: Translation Scale Rotation: PCA alignment

Translation- and Scale-Aligned Models PCA Alignment Fully Aligned Models Rotation Properties: Translation and rotation normalization is guaranteed to give the best alignment Rotation normalization is ambiguous PCA Alignment Directions of the axes are ambiguous

Normalization (PCA) PCA defines a coordinate frame up to reflection in the coordinate axes. Make descriptor invariant to axial-reflections Reflections fix the cosine term Reflections multiply the sine term by -1 f ( ) ak cos(k ) bk sin( k ) k y a , b k x z k

k Translation Invariant Representation Retrieval Results (Rotation) Gaussian EDT 100% Precision Size: Method Exhaustive Search PCA + Flip Invariance Cylindrical Power Spectrum PCA

Spherical Power Spectrum 50% Floats Exhaustive Search 8192 PCA + Flip Invariance 8192 PCA 8192 Cylindrical PS

4352 Spherical PS 512 Time: 0% 0% 50% Recall 100% Method

Secs. Exhaustive Search 20.59 PCA + Flip Invariance .67 PCA .67 Cylindrical PS .32 Spherical PS

.03 Alignment Exhaustive search: Best results Inefficient to match Normalization: Provably optimal for translation and scale Works well for rotation if models have well defined principal axes and the directional ambiguity is resolved Invariance: Compact Efficient Often less discriminating Outline

Matching Alignment Exhaustive Search Invariance Normalization Part vs. Whole Conclusion Partial Shape Matching Cannot use global normalization methods that depend on whole model information: Center of mass for translation Mean variance for scale Principal axes for rotation

Normalized Whole Normalized Part (Mis-)Aligned Models Partial Shape Matching Cannot use global normalization methods that depend on whole model information: Exhaustively search for best alignment Normalize using local shape information Use transformation invariant representations Normalized Whole Normalized

Part (Mis-)Aligned Models Spin Images & Shape Contexts Translation (Exhaustive Search): Represent each database model by many descriptors centered at different points on the surface. Model Multi-Centered Descriptors Spin Images & Shape Contexts Translation (Exhaustive Search): To match, center at a random point on the query and compare against the different descriptors of the target

Query Part Randomly-Centered Descriptor Best Match Target Descriptor Spin Images & Shape Contexts Rotation (Normalization): For each center, represent in cylindrical n coordinates about the normal vector [Spin Images]: Store energy in each ring [Harmonic Shape Contexts]: Store power spectrum of each ring

[3D Shape Contexts]: Search over all rotations about the normal for best match n n Spin Images & Shape Contexts Image courtesy of Frome et al, 2003 Spin images and shape contexts allow for part-inwhole searches by exhaustively searching for translation and using the normal for rotation alignment [Spin Images]: Store energy in each ring [Harmonic Shape Contexts]: Store power spectrum of

each ring [3D Shape Contexts]: Search over all rotations about the normal for best match Conclusion Aligning Models: Exhaustive Search Normalization Invariance Partial Object Matching Cant use global normalization techniques Translation: Exhaustive Search Rotation: Normal + Exhaustive/Invariant Conclusion Shape Descriptors and Model Matching: Decoupling representation from registration Can design and evaluate descriptors without

having to solve the alignment problem Can develop methods for alignment without considering specific shape descriptors

Recently Viewed Presentations

  • Budget Project Vocabulary - Woodland Hills School District

    Budget Project Vocabulary - Woodland Hills School District

    Health Insurance. A health maintenance organization (HMO) is a type of managed care organization (MCO) that provides a form of health care coverage in the United States that is fulfilled through hospitals, doctors, and other providers with which the HMO...
  • Ecd (Age 0-4) in South Africa: Policy, Demographics, Child ...

    Ecd (Age 0-4) in South Africa: Policy, Demographics, Child ...

    TOWARDS A JOB HIERARCHY FOR ECD PROVISION & SUPERVISION IN SOUTH AFRICA Linda Biersteker presentation to the Western Cape COP meeting 25 October 2017 CONTRIBUTION For ECD sector to expand and be upgraded it will need to become more attractive...
  • Kematian Pada Tumor Sinus Endodermal Pasca Operasi Debulking

    Kematian Pada Tumor Sinus Endodermal Pasca Operasi Debulking

    Upaya untuk mengidentifikasi masalah kegawatan akut utama yang dijumpai pada ginekologi : * Kegawatan Ginekologi Syok Abortus Mola Kista terpuntir / pecah * Syok Berkurangnya aliran darah dalam " sirkulasi mikro " MENGANCAM JIWA MEMERLUKAN PENGOBATAN YANG SEGERA DAN INTENSIF...
  • 3.1 Structure Charts - WhatDoTheyKnow

    3.1 Structure Charts - WhatDoTheyKnow

    Lambeth Living Structure Charts December 2011 Keys: RESTRICTED VACANT PERMANENT DISPLACED (incl in totals) Total for Entire Directorate (at the top of the first slide for
  • Civil Rights Graphic Organizers - birdvilleschools.net

    Civil Rights Graphic Organizers - birdvilleschools.net

    Civil Rights Protests/sit ins. Tactic: Protesters peacefully sat-in at segregated places. If they were refused service, they simply stayed where they were. Outcome: It forced the business owners to choose between serving the protestors or lose business. 1000s of students...
  • International Trade Issues, Part 1 Amanda Hodges, Ph.D.

    International Trade Issues, Part 1 Amanda Hodges, Ph.D.

    Terminology and Trade Concepts. Eighth GATT round (1986-1994), Uruguay round. Significant flexibility was provided to member nations in terms of restricting imports to protect human, animal, or plant life prior to this conference.
  • The patient with 20/20 vision who cant read

    The patient with 20/20 vision who cant read

    2. Eye movements and reading. A. Inability to maintain steady fixation: (i) Nystagmus in primary position - congenital (usually with reduced acuity) - acquired - vestibular (usually too dizzy to read) - central (downbeat! - worse in downgaze) (ii) Saccadic...
  • Interactive Notebook

    Interactive Notebook

    AP Human Geography/World Geography Ravenwood High School . Ashley Flood. a. [email protected] AP Human Geography/World HistoryFranklin High School . So, what is an Interactive Notebook? How many of you have heard of an Interactive Notebook? ... Nuts and Bolts.