L08 MDS

Flattening via Multi-Dimensional Scaling: 

Flattening via Multi-Dimensional Scaling Ron Kimmel www.cs.technion.ac.il/~ron Computer Science Department Geometric Image Processing Lab Technion-Israel Institute of Technology

Outline: 

On isometric surfaces and bending invariant signatures. Multi-dimensional scaling techniques: Classical. Least squares. Fast. Surface classification: experimental results. Outline

Matching Surfaces: 

Matching Surfaces Problem: Given 2D surfaces, define a measure of their similarity. Classical techniques: Find a rigid transformation that maximizes some measure. Match key points on the surface. Compare local or semi-differential invariants, e.g. matching graphs.

Bending Invariant Signatures: 

Isometric surface matching via bending invariant signatures: Map the surface into a small Euclidean space, in which isometric surfaces transform to similar (rigid) surfaces. Advantages: Handle (somewhat) non-rigid objects. A global operation, does not rely on selected key points or local invariants. Bending Invariant Signatures

Bending invariant signatures Basic Concept: 

Bending invariant signatures Basic Concept Input – a surface in 3D Extract from [D] coordinates in an m dimensional Euclidean space via Multi-Dimensional Scaling (MDS). Output – A 2D surface embedded in in R (for some small m) m

Slide6: 

Fast Marching on Surfaces Geodesic Distance

Multi-Dimensional Scaling: 

Multi-Dimensional Scaling MDS is a family of methods that map similarity measurements among objects, to points in a small dimensional Euclidean space. The graphic display of the similarity measurements provided by MDS enables to explore the geometric structure of the data.

A simple example: 

A simple example Rotation Reflection

Flattening via MDS: 

Flattening via MDS Compute geodesic distances between pairs of points. Construct a square distance matrix of geodesic distances^2. Find the coordinates in the plane via multi-dimensional scaling. The simplest is `classical scaling’. Use the flattened coordinates for texturing the surface, while preserving the texture features. Zigelman, Kimmel, Kiryati, IEEE TVCG 2002 Grossmann, Kiryati, Kimmel, IEEE TPAMI 2002 Bending invariant surface matching Elad (Elbaz), Kimmel CVPR 2001 0 0 0

Flattening: 

Flattening

Flattening: 

Flattening

Distances - comparison: 

Distances - comparison

Texture Mapping: 

Texture Mapping

Texture Mapping: 

Texture Mapping

Fattening via MDS: 3D: 

Fattening via MDS: 3D Original Fast Classical Least Squares Original Fast Least Squares Classical

Fattening via MDS: 3D: 

Fattening via MDS: 3D Original Fast Classical Least Squares Original Fast Least Squares Classical

Input Surfaces : 

Input Surfaces

Bending Invariant Signatures: 

Bending Invariant Signatures Elad, Kimmel, CVPR’2001 ?

Bending Invariant Signatures: 

Bending Invariant Signatures ? Elad, Kimmel, CVPR’2001

Bending Invariant Signatures: 

Bending Invariant Signatures ? Elad, Kimmel, CVPR’2001

Bending Invariant Signatures: 

Bending Invariant Signatures Elad, Kimmel, CVPR’2001

Bending Invariant Signatures: 

Bending Invariant Signatures Elad, Kimmel, CVPR’2001

Bending Invariant Signatures: 

Bending Invariant Signatures 3 Original surfaces Canonical surfaces in R Elad, Kimmel, CVPR’2001

Bending Invariant Clustering: 

0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 C C C C A A A A D D D D B B B B E E E E F F F F 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 C E C C B A D E E E B C A B D B F D A D F A F F Bending Invariant Clustering 2nd moments based MDS for clustering Original surfaces Canonical forms *A=human body *B=hand *C=paper *D=hat *E=dog *F=giraffe Elad, Kimmel, CVPR’2001

Classical Scaling Young et al. 1930: 

Classical Scaling Young et al. 1930 Given n points in , denote Define coordinates vector The Euclidean distance between 2 points:

Classical Scaling: 

Define the `centering’ matrix where Let the matrix We have that and also Thus, Classical Scaling

Classical Scaling: 

Classical Scaling The coordinates are related to by Thus the operation is also called `double centering’. Applying SVD, we can compute where and the coordinates can be extracted as If we choose to take only part of the eignstructure, then, our approximation minimizes the Frobenius norm

MDS: 

MDS Matlab code for 2D flattening Zigelman, Kimmel, Kiryati IEEE TVCG 2002

Classical Scaling: 

Classical Scaling The eigenvalues are the 2nd order moments of the flattened surface, since by definition all the cross 2nd order moments vanish by the unitarity of U, thus `flattening’.

Conclusions: 

Conclusions A method for bending invariant signatures Based on: Fast marching on surfaces MDS LS/Classical/Fast Results: Texture mapping Bending invariant signatures Classification of isometric surfaces.

Least Squares MDS: 

Least Squares MDS Standard optimization approach to solve the minimization problem of the stress cost function. Solved via ‘scaling by maximizing convex function’ (SAMCOF) algorithm. Starting with a random solution and iteratively minimizing another stress function, which satisfies. ƒ (x,z) ≥ ƒ (x) for x ≠ z and ƒ (z,z) = ƒ (z) The complexity is O(n ). Converges to the optimal solution. 2

Fast MDS: 

Fast MDS The fast MDS: heuristic efficient technique O(mn). Works recursively by generating a new dimension at each step, Providing m-dimensional coordinates after m recursion steps. Project the vertices on a selected ‘line’. First, the algorithm selects the Farthest two vertices. Next, all other vertices are projected On that line using the cosine law. Next step is to project all items to An (n-1) hyper plane (H) that is Perpendicular to the line that Connects those vertices. Generate a new distance matrix. Repeat the last three steps m times.