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