Fortschritte in der Robotik Band 5 Probabilistische

Fortschritte in der Robotik
Band 5
Probabilistische Erkennung von 3d
Freiformobjekten mit Bayesschen Netzen
Björn Krebs
Dissertation, Technische Universität Braunschweig, 1999
Fortschritte in der Robotik
Band 5
Technische Universität Braunschweig
Institut für Robotik und Prozeßinformatik
Prof. Dr.-Ing. Friedrich M. Wahl (Hrsg.)
Björn Krebs
Probabilistische Erkennung von 3d Freiformobjekten
mit Bayesschen Netzen
.
Shaker Verlag
Aachen 2000
Die Deutsche Bibliothek
-
CIP-Einheitsaufnahme
Krebs, Björn:
Probabilistische Erkennung von 3d Freiformobjekten mit Bayesschen Netzen /
Björn Krebs. - Als Ms. gedr. - Aachen : Shaker, 2000
(Fortschritte in der Robotik ; Bd. 5)
Zugl.: Braunschweig, Techn. Univ., Diss., 2000
ISBN 3-8265-7316-1
.
Copyright Shaker Verlag 2000
Alle Rechte, auch das des auszugsweisen Nachdruckes, der auszugsweisen
oder vollständigen Wiedergabe, der Speicherung in Datenverarbeitungsanlagen und der Übersetzung, vorbehalten.
Als Manuskript gedruckt. Printed in Germany.
ISBN 3-8265-7316-1
ISSN 1431-7222
Shaker Verlag GmbH • Postfach 1290 • 52013 Aachen
Telefon: 02407 / 95 96 - 0 • Telefax: 02407 / 95 96 - 9
Internet: www.shaker.de • eMail: [email protected]
v
Vorwort
Die vorliegende Arbeit ist im Rahmen meiner Tatigkeit als wissenschaftlicher Mitarbeiter am
Institut f
ur Robotik und Prozeinformatik der Technischen Universitat Braunschweig entstanden. Sie steht in engem Zusammenhang mit dem von der Deutschen Forschungsgemeinschaft
gef
orderten Projekt "Objekterkennung durch geplante Erkennungsstrategien" 1 .
Ich m
ochte mich in erster Linie bei Herrn Prof. Wahl f
ur die fruchtbare Zusammenarbeit herzlich
bedanken. Er regte diese Arbeit an und unterst
utzte mich wahrend ihrer Erstellung stets auf

umfangreiche Weise. Herrn Prof. Niemann, der sich zur Ubernahme
des Koreferats bereit erklart
hat, gilt ebenfalls mein Dank.
Meinen wissenschaftlichen Kollegen danke ich f
ur die gute Zusammenarbeit in einer angenehmen, freundschaftlichen Atmosph
are. Dar
uberhinaus gilt mein Dank all denen, die mich beim
Korrekturlesen meiner Arbeit unterst
utzt haben; hierbei insbesondere meiner Freundin Bettina Darda. Auch die Anregungen von Ronald Krebs und Marc Burkhardt haben mir bei der
Erstellung dieser Arbeit sehr geholfen.
Schlielich m
ochte ich an dieser Stelle auch meinen Eltern f
ur ihre bestandige, personliche
Unterst
utzung danken.
Braunschweig, im Oktober 1999
1 DFG
Projekt Wa 848/5
Bjorn Krebs
vii
Inhaltsverzeichnis
1 Einleitung
1.1 3d Objekterkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Zielsetzung und Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Abgrenzung zu anderen Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
3
4

2 3d Objekterkennung im Uberblick
2.1 Problembeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Der Computer als Beobachter . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Objektreprasentationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Bildbasierte Objekterkennung . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Merkmalsbasierte Erkennung ohne geometrische 3d Modelle . . . . . . .
2.3.3 Merkmalsbasierte Erkennung mit geometrischen 3d Modellen . . . . . . .
2.3.4 CAD-basierte Objekterkennung . . . . . . . . . . . . . . . . . . . . . . .
2.4 Sensordaten fur die Erkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 Sensoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Sensordatenanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.3 Merkmale in Sensordaten . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.4 Merkmale als Relationen von Sensordaten . . . . . . . . . . . . . . . . .
2.5 Interpretationsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1 Lageberechnungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.2 Zuordnungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Motivation einer probabilistischen Modellierung von Objekterkennungssystemen
2.7 Probabilistische Objekterkennung . . . . . . . . . . . . . . . . . . . . . . . . . .
7
7
16
18
19
21
22
24
26
27
28
29
32
34
35
36
39
45
3 Ein didaktisches Erkennungsbeispiel
49
4 Merkmale von 3d Objekten
4.1 Merkmale von Freiformobjekten . . . . . . . . . . . . . . . . .
4.2 Merkmale an Ecken und Kanten . . . . . . . . . . . . . . . . .
4.2.1 Extraktion planarer Flachensegmente aus Tiefendaten .
4.2.2 Merkmale an planaren Flachensegmenten . . . . . . . .
4.3 Merkmale an 3d Randkurven . . . . . . . . . . . . . . . . . .
4.4 Darstellung von 3d Randkurven . . . . . . . . . . . . . . . . .
4.5 Geometrische Eigenschaften von 3d Randkurven . . . . . . . .
4.6 Teilkurven denieren Merkmale . . . . . . . . . . . . . . . . .

4.7 Die Ahnlichkeit
von Teilkurven . . . . . . . . . . . . . . . . .
4.8 Extraktion aus Tiefendaten . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
73
74
76
76
78
80
81
84
87
91
94
viii
Inhaltsverzeichnis
4.8.1 Segmentierung von Randpunkten . . . . . . . . . . . .
4.8.2 Eliminierung fehlerhafter Daten . . . . . . . . . . . . .
4.8.3 3d kubische B-Spline Approximation . . . . . . . . . .
4.8.4 Glattung von Randkurven . . . . . . . . . . . . . . . .
4.9 Ein Extraktionsbeispiel von Randkurven . . . . . . . . . . . .
4.10 Genauigkeitsanalyse der Kurvenextraktion . . . . . . . . . . .
4.10.1 Geometrische Bedeutung von Krummung und Torsion .
4.10.2 Genauigkeit der Krummung . . . . . . . . . . . . . . .
4.10.3 Genauigkeit der Torsion . . . . . . . . . . . . . . . . .
4.10.4 Genauigkeit der Zuordnung von Kurven . . . . . . . .
5
6
Generierung der Bayesschen Netze
5.1 Grundlegende Modellierungskonzepte . . . . . . . . . . . .
5.1.1 Das Prinzip der Kausalitat . . . . . . . . . . . . . .
5.1.2 Bewertung kausaler Abhangigkeiten . . . . . . . . .
5.1.3 Multikausale Abhangigkeiten . . . . . . . . . . . . .
5.2 Bestimmende Faktoren bei der Modellierung . . . . . . . .
5.2.1 Die Signikanz von Merkmalen . . . . . . . . . . .
5.2.2 Individuelle Gewichtung von Signikanzen . . . . .
5.2.3 Einuder a priori Wahrscheinlichkeit . . . . . . . .
5.2.4 Die Verlalichkeit von Merkmalen . . . . . . . . . .
5.3 Netzgenerierung aus CAD-Modellen . . . . . . . . . . . . .
5.3.1 Aufbau der Netzstruktur . . . . . . . . . . . . . . .
5.3.2 Generierung der Bayesschen Netze . . . . . . . . .
5.3.3 Merkmale in CAD-Daten . . . . . . . . . . . . . . .
5.3.4 Generierung uber relationale Strukturen . . . . . .
5.3.5 Netzgenerierung aus statistischen Daten . . . . . .
5.4 Geometrische Relationen . . . . . . . . . . . . . . . . . . .
5.5 Netzgenerierung mit 3d Merkmalen . . . . . . . . . . . . .
5.5.1 Generierung fur Merkmale an Ecken und Kanten .
5.5.2 Generierung fur Randkurven . . . . . . . . . . . . .
5.5.3 Beispiel fur Objekte mit sehr ahnlichen Randkurven
5.5.4 Beispiel fur Freiformobjekte . . . . . . . . . . . . .
5.5.5 Integration unterschiedlicher Merkmale . . . . . . .
5.5.6 Beispiel fur geometrische Relationen . . . . . . . .
Der Fuzzy-ICP Zuordnungsalgorithmus
6.1 ICP Algorithmus . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Keine Segmentierung mit dem ICP Algorithmus .
6.2 Fuzzy ICP Algorithmus . . . . . . . . . . . . . . . . . . .
6.2.1 Zugehorigkeitsfunktionen . . . . . . . . . . . . . .
6.2.2 Korrekte Segmentierung mit dem Fuzzy ICP . . .
6.3 Die Referenz-Evidenz der Zuordnung . . . . . . . . . . .
6.4 Die Transformationsberechnung . . . . . . . . . . . . . .
6.5 Die Korrespondenzpunktbestimmung . . . . . . . . . . .
6.5.1 Der Korrespondenzpunkt auf einer Dreiecksache
6.5.2 Der Korrespondenzpunkt auf einer Freiformache
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
94
96
97
97
102
103
104
108
111
114
117
119
119
122
123
126
127
129
130
131
133
134
136
136
138
140
143
145
145
149
152
156
158
161
163
163
164
167
170
170
171
174
175
176
176
ix
Inhaltsverzeichnis
6.6 Konvergenzverhalten des Fuzzy ICP Algorithmus
6.7 Aufwand des Fuzzy ICP Algorithmus . . . . . . .
6.7.1 3d Hashing . . . . . . . . . . . . . . . . .
6.7.2 Reduktion der Sensordaten . . . . . . . . .
6.7.3 Erreichte Beschleunigung . . . . . . . . . .
6.8 Genauigkeit des Fuzzy ICP Algorithmus . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7.1 Das Prinzip der Planung von Aktionsschritten . . . . . . . . . .
7.2 Bayessches Netz zur Planung . . . . . . . . . . . . . . . . . . . .
7.3 Erkennungsstrategien . . . . . . . . . . . . . . . . . . . . . . . .
7.3.1 Akquisition neuer Sensordaten . . . . . . . . . . . . . . .
7.3.2 Extraktion von 3d Hypothesen . . . . . . . . . . . . . . .
7.3.3 Validierung von 3d Hypothesen . . . . . . . . . . . . . .
7.3.4 Zuordnung von Sensordaten zu 3d Hypothesen . . . . . .
7.3.5 Ergebnisse verschiedener Erkennungsstrategien . . . . . .
7.4 Atomare Aktionen und ihre Kosten . . . . . . . . . . . . . . . .
7.5 Grundlagen der Entscheidungsndung . . . . . . . . . . . . . . .
7.6 Entscheidungen in Bayesschen Netzen . . . . . . . . . . . . . . .
7.6.1 Inuenzgraphen . . . . . . . . . . . . . . . . . . . . . . .
7.6.2 Unsicherheiten bei der Aktionsauswahl . . . . . . . . . .
7.6.3 Inuenzgraphen als Bayessche Netze . . . . . . . . . . .
7.6.4 Folgen von Aktionen . . . . . . . . . . . . . . . . . . . .
7.7 Erkennungsergebnisse realer Szenen . . . . . . . . . . . . . . . .
7.7.1 Erkennung mit Ecken- und Kantenmerkmalen . . . . . .
7.7.2 Erkennung fur eine Szenenmanipulation . . . . . . . . .
7.7.3 Erkennung mit Randkurven . . . . . . . . . . . . . . . .
7.7.4 Erweiterung der Kurvenklassen . . . . . . . . . . . . . .
7.7.5 Erkennungsergebnisse komplexer Szenen . . . . . . . . .
7.7.6 Kombination verschiedener Kurventypen und Merkmale .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Aktive 3d Objekterkennung
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
181
181
183
185
186
188
189
190
190
194
194
194
195
195
197
198
200
203
204
205
207
215
217
218
221
221
221
222
222
8 Zusammenfassung und Ausblick
226
Literatur
229
Betreute Studien- und Diplomarbeiten
253
Eigene Veroentlichungen
254
Index
256
x
Inhaltsverzeichnis
xi
Zusammenfassung
In dieser Arbeit werden neue Konzepte zur expliziten Modellierung von Unsicherheiten wahrend
des Erkennungsprozesses mit Hilfe von Bayesschen Netzen vorgestellt. Diese erlauben die statistischen Eigenschaften von Merkmalen und Objekten in einer konsistenten Form zu modellieren,
um so die Bewertung der aktuellen Erkennungssicherheit zu ermoglichen. Die Berucksichtigung
der Signikanz von Merkmalen und deren Abhangigkeiten mit Hilfe von Zugehorigkeitsrelationen garantiert die konsistente Integration unterschiedlicher Merkmale, um die Selektion der
wahrscheinlichsten Objekte zu ermoglichen. Eine Losung des Segmentierungsproblems, zum
einen auf Merkmalsebene mit Hilfe geometrischer Relationen, zum anderen auf Objektebene
durch eine robuste Zuordnung von Freiformmodellen zu Sensordaten mittels des Fuzzy ICP
Algorithmus, erlaubt die korrekte Validierung von Objekthypothesen. Durch eine Ausgleichsberechnung uber viele Sensordaten kann die 3d Lage eines erkannten Objekts hinreichend genau
bestimmt werden.
Verlaliche 3d Merkmale in Form von Ecken, Kanten und Randkurven werden vorgestellt.
Die eÆziente Extraktion sowohl aus Tiefendaten als auch aus CAD-Objektdenitionen stellt
hierbei die Basis fur ein robustes 3d Objektkennungssystem von Freiformachen dar. Eine
dem Extraktionsverfahren in Tiefendaten gleichartige Berechnung von Merkmalen aus CADObjektmodellen erlaubt die automatische Generierung der Bayesschen Netze aus CAD-Daten.
Die einzelnen Evidenzen der erkannten Objekte werden in eine Planung von Aktionsschritten integriert. Die Interaktion von Evidenzpropagation und Aktionsauswahl ermoglicht ein exibles,
aktives 3d Objekterkennungssystem, das sich an die aktuelle Komplexitat der beobachteten
Szene adaptiert.
In dieser Arbeit werden innovative, grundlegende Konzepte fur eine probabilistische 3d Erkennung von beliebigen Objekten vorgestellt. Die Einbettung in ein theoretisches Modell und die
Verwendung mathematisch fundierter Konzepte stellen die vorgeschlagenen Methoden auf eine
solide Basis, die die Allgemeingultigkeit dieser neuen Sichtweise unterstreichen und die vorgestellten Methoden auch fur andere Anwendungen attraktiv machen. Die Entwicklung einer
konzeptionell neuen Sichtweise zur Losung der 3d Erkennungsproblematik steht deshalb im Mittelpunkt dieser Arbeit. Die Methoden werden in ein 3d Erkennungssystem fur Freiformobjekte
umgesetzt und deren Tragfahigkeit anhand einer Validierung an praktischen Erkennungsaufgaben unter Beweis gestellt.
xii
Inhaltsverzeichnis
xiii
Abstract
In this work a new approach to 3d object recognition for free form objects is introduced. The
statistical behavior of features and objects is modeled in terms of Bayesian networks. A consistent representation of statistical and geometrical a priori knowledge allows to evaluate the
uncertainty within the recognition process. The signicance of features to discriminate the set
of object hypotheses and their dependencies to the whole database of objects guarantees the
selection of the most probable object hypotheses. The integration of dierent types of features
can be achieved consistently within the framework of a Bayesian net representation. A solution
to the segmentation problem is presented on the feature level by geometrical relations and on
the object level by a fuzzy ICP matching algorithm. A weighted least square minimization of
matched correspondences allows the robust computation of the object locations even in the
case of noise.
Reliable features for free form objects like corners, edges and rims are introduced. EÆcient algorithms for the extraction of these features forms the basis of robust 3d CAD object recognition
systems. By extracting features in range data and CAD data in the same way an automatic
construction of Bayesian nets is achieved. The recognition system adapts to the current complexity of the scene by integrating the recognition results from the evidence propagation into a
decision reasoning.
The proposed methods are basic concepts for 3d object recognition. The consistent representation in a theoretical and mathematical framework guarantees a sound foundation which makes
their application for other purposes of uncertain data processing available, too. The introduction into a new approach to 3d probabilistic recognition is the major goal of this work. The
proposed methods are integrated into a robust and exible 3d object recognition system and
evaluated in practical experiments.