Shape Similarity

27. Februar 2006

Michael Keller

Inhalt

• Einführung und Übersicht

• Elastic Matching

• Shock Graphs

• Vergleich und Schlusswort

Shape Similarity

• Shape: Linien oder Gebiete• Explizites Modellwissen ausgeschlossen!• Semantisches Wissen ausgeschlossen!

• Motivation: Basis für “höhere” Applikationen:– Modell erstellen/fitten– Datenbank erstellen/look-up– Korrespondenz/depth-from-stereo– Tracking

Klassifikation Methoden

2 Repräsentanten

• “Elastic Matching”: Linien, lokalR. Basri et al., “Determining the similarity of deformable shapes”, Vision Research, 38:2365-2385, 1998

• “Shock Graphs”: Gebiete, strukturell

K. Siddiqi et al., “Shock graphs and shape matching”, International Journal of Computer Vision, 30:1-24, 1999

Inhalt

• Einführung und Übersicht

• Elastic Matching

• Shock Graphs

• Vergleich und Schlusswort

Kurven

• Kurve, parametrisiert durch Bogenlänge

• Tangente

• Tangentenwinkel

• Krümmung

Elastic Matching

1. Korrespondenz zwischen

2. Berechne Kosten

… Korrespondenz meist

Kostenfunktion

• Mass für Ähnlichkeit

• bestimmt Korrespondenz

Design der Kostenfunktion Primäraufgabe!

Betrachtete Klasse:

Eigenschaften

• Stetigkeit

• Metrik

• Polygone

• Invarianz

• Implizite Erkennung von Struktur

• …

Federmodell

• Physik:

• Annahme: (damit )

Implementation• Bestimmung der Krümmungen

• Dynamisches Programmieren

Resultate

Inhalt

• Einführung und Übersicht

• Elastic Matching

• Shock Graphs

• Vergleich und Schlusswort

Blum’sches Skelett

• Grassfire-Transformation

• Skelett plus assoziierte t- resp. r-Werte

Skelett → Graph

• 4 Shock Typen (1,2,3,4), Startknoten (#), Endknoten (Φ)

• zeitlich rückwärts aufbauen

• azyklischer, gerichteter Graph

Vergleich: largest subgraph isomorphism (NP-hart)

Graph → Baum

• 10 Erzeugungsregeln schränken Topologie ein, Graph → Baum

• largest subtree polynomial

für gegebene Figur Baum eindeutig!

für gegebenen Baum Figur eindeutig?

Nein → t-Werte dazunehmen

Beispielbaum

Zusammenfassung

• Skelett → Graph → Baum

• largest subtree mit lokalen Kosten

• schnell am entry-level

• robust

• Nur Jordan curves

Inhalt

• Einführung und Übersicht

• Elastic Matching

• Shock Graphs

• Vergleich und Schlusswort

Methodenvergleich

Sebastian et al., Curves vs. Skeletons in Object Recognition, 2001

• Skelette besser bei – Artikulation– Umordnung– Verdeckung

• Direkter Kurvenvergleich– oft effizienter– bietet grossen Spielraum

Schlusswort

• Ähnlichkeit – intuitiv wichtig– schwer zu fassen– kontextabhängig

• Vielzahl an Methoden

• Keine “one-fits-all” Lösung!