L08 MDS

Information about L08 MDS

Published on October 31, 2007

Author: Nastasia

Source: authorstream.com

Content

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.

Related presentations


Other presentations created by Nastasia

ICU acquired weakness Ron Jou
24. 10. 2007
0 views

ICU acquired weakness Ron Jou

ppt 14
14. 12. 2007
0 views

ppt 14

griffith seminar 150306
01. 10. 2007
0 views

griffith seminar 150306

Ch 2 Climate Causes of Aridity
03. 10. 2007
0 views

Ch 2 Climate Causes of Aridity

Anti Anxiety Agents
28. 11. 2007
0 views

Anti Anxiety Agents

lect8
04. 12. 2007
0 views

lect8

25271
06. 12. 2007
0 views

25271

GoalSetting
10. 12. 2007
0 views

GoalSetting

Consol Serra
25. 10. 2007
0 views

Consol Serra

3 The Model Treaties
29. 10. 2007
0 views

3 The Model Treaties

CHAP09
02. 11. 2007
0 views

CHAP09

noaa updta isom 2004
05. 11. 2007
0 views

noaa updta isom 2004

oct energy narayana
05. 11. 2007
0 views

oct energy narayana

TS1 2 1
04. 10. 2007
0 views

TS1 2 1

Case Volkswagen
16. 11. 2007
0 views

Case Volkswagen

school pp
19. 11. 2007
0 views

school pp

hedgefunds bubble slides
20. 11. 2007
0 views

hedgefunds bubble slides

fuel tank safety bahrami medal
06. 11. 2007
0 views

fuel tank safety bahrami medal

POA nsrc 2005 02 15
26. 11. 2007
0 views

POA nsrc 2005 02 15

Brand Presentation UofA
23. 11. 2007
0 views

Brand Presentation UofA

who are you
28. 12. 2007
0 views

who are you

WM TB2
31. 12. 2007
0 views

WM TB2

NDM Workshop
04. 01. 2008
0 views

NDM Workshop

chap11a
07. 01. 2008
0 views

chap11a

nutrient murray
07. 01. 2008
0 views

nutrient murray

harmon05
24. 12. 2007
0 views

harmon05

5 coldwar lesson
25. 12. 2007
0 views

5 coldwar lesson

Program Overview2
01. 01. 2008
0 views

Program Overview2

Kaal Dorst Beyond MIP final
21. 11. 2007
0 views

Kaal Dorst Beyond MIP final

Presentation Barbarosie
01. 12. 2007
0 views

Presentation Barbarosie

GRP 12 LA buffet
12. 12. 2007
0 views

GRP 12 LA buffet

SSA Presentation
05. 01. 2008
0 views

SSA Presentation

dnttour leader english
02. 10. 2007
0 views

dnttour leader english

cg 00 36
20. 02. 2008
0 views

cg 00 36

copyright authorship
27. 02. 2008
0 views

copyright authorship

masterclass
13. 11. 2007
0 views

masterclass

McCreight
05. 03. 2008
0 views

McCreight

Ling Chen
27. 03. 2008
0 views

Ling Chen

RameshNarayanSciWrit ers
29. 11. 2007
0 views

RameshNarayanSciWrit ers

6 2buscycle
13. 04. 2008
0 views

6 2buscycle

CAP June07
15. 11. 2007
0 views

CAP June07

2007 01vadmSullivan
06. 11. 2007
0 views

2007 01vadmSullivan

cabwrcpresentation final
11. 12. 2007
0 views

cabwrcpresentation final

GoetzAccelChange
21. 12. 2007
0 views

GoetzAccelChange

Internet QoS Technique
04. 01. 2008
0 views

Internet QoS Technique

Blue
16. 11. 2007
0 views

Blue

nabucco Sep14 2007
26. 10. 2007
0 views

nabucco Sep14 2007

PPT Mearns Intro2 health 2006
25. 10. 2007
0 views

PPT Mearns Intro2 health 2006

rm2403
30. 10. 2007
0 views

rm2403

FAO Peres Oct06
30. 10. 2007
0 views

FAO Peres Oct06

KateBTina
12. 12. 2007
0 views

KateBTina

urbana web
21. 11. 2007
0 views

urbana web

xml in mozilla
28. 12. 2007
0 views

xml in mozilla

Pablo
07. 11. 2007
0 views

Pablo

cookware energy2
03. 01. 2008
0 views

cookware energy2

ponencia NOM 030
15. 11. 2007
0 views

ponencia NOM 030

La civilisation romaine
30. 10. 2007
0 views

La civilisation romaine

Stata20060629
02. 01. 2008
0 views

Stata20060629

Permanentflowers
07. 12. 2007
0 views

Permanentflowers

s1310 amer yahia
03. 12. 2007
0 views

s1310 amer yahia