Lehrstuhl Graphische Systeme Brandenburgische Technische Universität Cottbus 1 Einführung in die Objekterkennung im dreidimensionalen Raum Sind Objektrepräsentation

1

Lehrstuhl Graphische Systeme

Brandenburgische Technische Universität Cottbus

Einführung in die Objekterkennung im

dreidimensionalen RaumSind Objektrepräsentation und

Segmentierung trennbar?

Matthias Krause

nach Ruzena Bajcsy,Franc Solina,Alok Gupta

2

Lehrstuhl Graphische Systene


Matthias KrauseSeminar Mustererkennung2004

Definition der Vorverarbeitung

• Jeder geometrische Signalverarbeitungsalgorithmus, der die Daten eines Sensors in eine anwendungsoptimierte Form übersetzt

• Frühverarbeitungsalgorithmen partitionieren oder segmentieren idealerweise die Rohdaten in geometrische Grundformen, so dass jeder Bilddatenpunkt zu einer geometrisch gedeuteten Gruppe gehört

• Ziel: Rauschen entfernen, Geometrie erhalten

3




Range Images - Tiefenbilder

4




Oberflächengeometrie

• Vorverarbeitung: Glätten und Entfernen von irrelevanten Daten.

5




Glättungsverfahren:• Mittelwertglättung – linear oder

nichtlinear– Gute Rauschunterdrückung– Abschwächung hoher Ortsfrequenzen– Verwischen von Kanten

• Nichtlinearer Medianfilter– Keine Kantenverwischung– Rechenaufwand

• K-nearest-neighbor-Glättung– Gute Alternative bei K=5 zur 3x3

Mittelwertglättung

6




Glättungsverfahren(2)

• Jede Aufnahme benötigt andere Verfahren

• Verfahren nicht vergleichbar -> individuell anpassen

• Bestrebung, von möglichst wenigen Parametern abhängig zu sein

7




Objekterkennung

Objekt Objekt

Teile Teile

Features Features

DatenDaten

Modellierung Beobachtung

8




Objekterkennung – Aufgaben

• ALV – autonome Land-Fahrzeuge– Viele, wahrscheinlich unbekannte Objekte der Natur

• Industrielle Roboter-Bilderkennung– Wenige Objekte an einem Zeitpunkt– Dennoch bis zu 150.000 verschiedene Bauteile im

Repertoire• Industrielle Inspektion

– Fehlerentdeckung• Weltraumanwendungen

– On Board – gut beschrieben– Planetenerforschung

• Heim- und Dienstroboter– Komplexe Umgebung, komplexe Objekte

• Warenhausroboter– Flexible Routen

9




Objekterkennung – Dimensionen

• Zahl der Objekte• Variabilität der Modelle• Komplexität des Hintergrundes• Berechnungskomplexität

10




Einführung

• 1. Was sind die geometrischen Grundformen, die (möglicherweise eindeutig) die Daten beschreiben?

• 2. Welche Prozesse ermöglichen die Dekomposition?

• 3. Was ist die grundlegende Kontrollstrategie, um die gemessenen Daten zu erklären?

11




Die Rolle von Grundformen

• Die Welt ist zu komplex, um sie digital zu repräsentieren.

• Daher muss der visuelle Input auf ein Niveau reduziert werden, welches den jeweiligen Anforderungen genügt.

• Vereinfachung bedeutet, Bilder in Entitäten zu teilen, die den entsprechenden realen Objekten anwendungsgenügend entsprechen (Prinzip der Sparsamkeit).

12




Die Rolle von Grundformen (2)

• müssen Formanalyse ermöglichen• Polyeder• Kugeln• verallgemeinerte Zylinder• Superquadriken

13




Polyeder

http://mathworld.wolfram.com/Polyhedron.html

14




Kugeln

• http://mathworld.wolfram.com/Sphere.html

15




Verallgemeinerte Zylinder

• http://mathworld.wolfram.com/GeneralizedCylinder.html

16




Superquadriken

17




Superquadriken(2)

• Zum Ausprobieren:• http://www.gamedev.net/

reference/programming/features/superquadric/superquadric.zip

18




Wahl der Grundform

• Eine Grundform: einfacher Segmentierungsprozess, aber nicht natürlich– Bsp: Eine Gerade aus Kreisstücken

darstellen oder umgekehrt• Natürliche Grundformwahl:

Kombinatorische Explosion• -> Limitierung der Anzahl von

Grundformen

19




Einflussfaktoren• Manchmal möglich, zu wissen, dass

eine bestimmte Klasse von geometrischen Modellen genügt, um die Welt zu beschreiben– Lagerverwaltung – aus Kisten, also

Quadern

• Weiß man die Komplexität der Szene, ist eine Vereinfachung der Kontrollstruktur möglich, da das Wissen um die Dimension der Objekte die Wahl des Formmodells vereinfacht

20




Einflussfaktoren(2)

• Unterschiedliche Ziele aufsteigender Komplexität– Objektvermeidung– Objektmanipulation– Objektidentifikation

21




Repräsentationsarten

• Volumetrische Repräsentation• Formbasierte Repräsentation• Grenzenbasierte Repräsentation

22




Volumetrische Repräsentation

• Liefert umfassende Eigenschaften– Gesamtform– Klassifizierung der Grundformen

nach• Länglich, flach, rund, zugespitzt,

gebogen oder verdreht

23




Formbasierte Repräsentation

• Liefert Details über Oberflächen, die Teile von größeren Volumenkörpern sind

• Differenziert zwischen – flachen oder gebogenen, – konkaven gegen konvexe, – glatten gegen raue Oberflächen

24




Grenzenbasierte Repräsentation

• Repräsentiert die Oberfläche und Biegung nahe der Grenzen

• Trennt Objekte vom Hintergrund -> definiert dadurch das Objekt

25




Vereinfachen der Wahl

• Statt kombinatorischer Suche:– Aus den Daten bestimmen, wo

welches Modell eingesetzt werden sollte

– Möglicherweise eine “grob zu fein”-Strategie

• Ein umfassendes System sollte alle Grundformarten beinhalten

26




Kriterien der Auswahl von Grundformen

• Dreidimensional: Superquadriken• Zweidimensional:

Oberflächengrundformen• Eindimensional:

Konturgrundformen

27




Konturgrundformen

Nachteile:Zu lokal, um Zusammenhänge zu

erkennenStörungsempfindlich gegenüber lokalen

Veränderungen

Vorteile:Erkennen KonturdetailsBeschreiben die globale FormTeilen Objekte auf

28




Oberflächengrundformen

• Unstetigkeiten werden als Begrenzungen gezählt

• Menschliche Wahrnehmung definiert Objekte als Ansammlung von Oberflächen

• werden Unstetigkeiten als Falten wahrgenommen, sind bessere Objektbeschreibungen möglich

29




Volumengrundformen• Parametrische Modelle sehr beliebt

– Kompakte Beschreibung (wenige Parameter) komplexer Formen

• Vorteile von Superquadriken– Überall differenzierbar– Enthalten eine große Bandbreite von natürlichen Formen– Einfach lösbare Parameter

30




Der Segmentierungsprozess

• Entscheidung, was zur Segmentierung benötigt wird

• Zwei Basisstrategien: Grob zu fein, Fein zu grob

• Beide vor- und nachteilbehaftet, beide benötigt

• Einteilung nach Repräsentationen ebenfalls möglich

31




Grob zu Fein

• Schnelle Abschätzung über Volumen/Grenzen/Oberflächen des Objekts

• Weitere Verfeinerung bis zum gewünschten Detailgrad

• Aber: die detektierbaren Details oft nur durch Repräsentationsänderung ermittelbar

32




Grundidee:

• Progressives blurring der Bilder klärt die Grobstruktur

• Details beeinflussen nicht die Grobstruktur, daher kein Backtracking erforderlich

33




Scale-Space

• Tiefpassfilter auf verschiedenen Auflösungen erzeugt einen Skalen-Raum

• Niedrige Skalen beschreiben Details

• Hohe Skalen beschreiben homogene Regionen

34




Fein zu Grob

• Einige Details können beim Klassifizierungsprozess helfen, da sie Objekte ausschließen können

• Zuviele Details enden in kombinatorischer Explosion

35




Segmentierung durch volumenbasierte Repräsentanten

• Binford und Nevatia: Basis = verallgemeinerte Zylinder

• Solina: Basis = Superquadriken

36




Solina

• Gegeben: Tiefenbild• Fasse alle Objektpunkte in einem

Elipsoid zusammen• Minimierung des Ellipsoids: Beziehe

rekursiv die Objektpunkte mit ein und finde Parameter, damit die Form die Objektpunkte schneidet oder nahe der Oberfläche ist

• Problem: mehrere Objekte nicht separierbar

37




Segmentierung durch Informationen über die

Grenzen• Basiert auf der Erkennung von

Unstetigkeiten in Tiefenwerten und Orientierung

• Objektpunkte mit ähnlichen Eigenschaften werden verschmolzen

• Kurvenannäherung kann durchgeführt werden (Splines, etc)

38




Segmentierung durch Informationen über die

Grenzen(2)• Verdeckungen (und Unterbrechungen)

erkennbar durch Weiterführung der Kurven

• Ramachandran zeigt: uneindeutige Oberflächeninformationen können durch die Kanteninformationen gelöst werden

39




Segmentierung durch Oberflächengrundformen

• Sehr beliebt, da einfacher handhabbar als Volumenkörper

• Der Prozess beginnt bei lokalen Nachbarschaften und wird ausgedehnt– Wasserscheiden-Verfahren

• Problem: unwichtige lokale Minima• Für den Gesamtkontext volumetrische

Modelle besser geeignet

40




Kontrollstruktur

• Wie sollen die drei Strukturen verwoben werden?

• Zwei Extrema– Parallele Abarbeitung

• Auftauchen von Konfliktsituationen, die gelöst werden müssen

– Sequenzielle Abarbeitung• Bei Erreichen von „falschen Fährten“

wäre Backtracking nötig

41




Kontrollstruktur (2)

• Menschliche Erkennung kann Kanten ergänzen

• Ziel: Rechnerbasiert muss ein System ebenfalls anpassungsfähig sein

42




Vorschlag• Paralleles Abarbeiten von volumen-

und grenzbasierter Segmentierung– da gegensätzlich– Interaktion zwischen den Methoden zur

Kontrolle und Präzisierung von Grenzen/Körpern

• Oberflächenanalyse für Details– Konflikt-Lösungsmöglichkeit für

„unsichtbare Kanten“ -> Ermittlung der Unstetigkeitstellen

43




Kontrollstruktur (3)• Muss Verlässlichkeit der Informationen

feststellen• Muss Teil/Ganzes-Beziehungen entscheiden• Braucht viele Parameter -> vorfestgelegt

oder im Prozess ermittelt• Z.B.

– Größe(-nbereich) der lokalen Nachbarschaften– Größe(-nbereich) der volumetrischen Modelle– Anzahl (oder Bereich) der erwarteten Einheiten– Schwellenwerte für Partitionierung und

Zusammenführung– Detailgrad

44




Zusammenfassung

• Bei der Bilderkennung gibt es zwei grundlegende Verfahren

• Objektrepräsentation und Segmentierung• Diese sollten zusammen angewendet

werden, da sie einander ergänzen können• Ein Vorschlag zur Zusammenarbeit wurde

vorgestellt:– Das Finden von Volumenkörpern wird

einschränkend unterstützt durch Kantenfindung

– Feinere Details werden mittels Oberflächenrepräsentierung gefunden

45




Quellen:• EarlyProcessing – EP discussion group• Segmentation versus object representation - are they

separable? Ruzena Bajcsy, Franc Solina, Alok Gupta• Superquadriken

– http://www.gamedev.net/reference/articles/article1172.asp – http://graphics.tu-bs.de/lvcg01-02/Vorlesung1/

Superquadriken.pdf• Skalenräume

– http://cyvision.if.sc.usp.br/msskeletons/– http://www.isip.uni-luebeck.de/~metzler/pdf

/bvm99-metzler.pdf• Segmentierung mit Superquadriken

– http://www.cs.caltech.edu/~arvo/papers/GenMod.pdf• Objekte:

– http://mathworld.wolfram.com• Webquellen vom 27.7.2004

Documents

Lehrstuhl Graphische Systeme Brandenburgische Technische Universität Cottbus 1 Einführung in die Objekterkennung im dreidimensionalen Raum Sind Objektrepräsentation