Bildanalyse: Von der Bildverarbeitung zur räumlichen Interpretation von Bildern [1 ed.] 3540797424, 9783540797425, 9783540797432 [PDF]

Zitiervorschau

eXamen.press

sUppLex

eXamen.press ist eine Reihe, die Theorie und Praxis aus allen Bereichen der Informatik für die Hochschulausbildung vermittelt.

sUppLex

Johannes Steinmüller

Bildanalyse Von der Bildverarbeitung zur räumlichen Interpretation von Bildern

123 sUppLex

Dr. rer. nat. Johannes Steinmüller Technische Universität Chemnitz Fakultät für Informatik Straße der Nationen 62 09111 Chemnitz [email protected]

ISBN 978-3-540-79742-5

e-ISBN 978-3-540-79743-2

DOI 10.1007/978-3-540-79743-2 eXamen.press ISSN 1614-5216 Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. c 2008 Springer-Verlag Berlin Heidelberg
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Einbandgestaltung: KünkelLopka, Heidelberg Gedruckt auf säurefreiem Papier 987654321 springer.de

sUppLex

Vorwort Dieses Buch gibt eine Einf¨ uhrung in die Bildanalyse. Dabei werden neben der eigentlichen digitalen Bildverarbeitung auch die Mustererkennung (Objekterkennung in Bildern) sowie die dreidimensionale Bildinterpretation behandelt. Die beiden letzten Gebiete spielen unter anderem in der autonomen mobilen Robotik eine wichtige Rolle. Das Material entstand aus einer einsemestrigen Vorlesung an der TU Chemnitz, die ich seit u ¨ber 10 Jahren halte. Teilnehmer sind Studenten verschiedener Studienrichtungen wie Informatik, Mathematik, Medientechnik, Maschinenbau und Elektrotechnik. Es werden folgende Themen behandelt: Bildverarbeitung Morphologische Operationen Bildsegmentierung Berechnung von Objektmerkmalen Klassifikation (Mustererkennung) Dreidimensionale Bildinterpretation Bewegungsanalyse aus Bildfolgen Dieses Buch soll keine Einf¨ uhrung in die Praxis der Bildverarbeitung mit Softwarepaketen (wie z.B. ImageJ) sein. Dazu liegen schon zahlreiche Lehrb¨ ucher vor. Es enth¨ alt deshalb auch keine konkrete Umsetzung von Algorithmen. ¨ Ebenso sind Ubungsaufgaben weitgehend theoretischer Natur. Hauptziel ist die Darstellung der Hintergr¨ unde und mathematischer Prinzipien der Bildverarbeitung und der Bildanalyse. Viele mathematische Methoden, die f¨ ur die Bildverarbeitung eine große Bedeutung haben, werden ausf¨ uhrlich dargestellt. Trotzdem ist es kein rein mathematisches Buch. Es werden auch zahlreiche praktische Hinweise gegeben. Ein weiterer Schwerpunkt ist die Einbeziehung von Methoden der K¨ unstlichen Intelligenz, wozu die Mustererkennung geh¨ ort. Einige Themen (z.B. Neuronale Netze) w¨ urden den Rahmen des Buches sprengen und sind deshalb bewusst weggelassen worden. Das Buch ist f¨ ur eine einsemestrige zweist¨ undige Vorlesung im Grund- oder Hauptstudium (ab 3. Semester) gut geeignet und hat sich in der Praxis ¨ bew¨ ahrt. Die Aufgaben eines jeden Kapitels erlauben eine begleitende Ubung. Es kann aber auch zum Selbststudium von Wissenschaftlern benutzt werden, die sich erste Kenntnisse im Bereich der Bildanalyse aneignen m¨ochten.

sUppLex

VI

Vorwort

Viele Personen haben mich bei der Erstellung des Buches unterst¨ utzt. Besonderer Dank gilt Prof. Werner Dilger †, der mir die M¨oglichkeit gab, mich intensiv mit der Vorbereitung und Durchf¨ uhrung einer Vorlesung zur Bildanalyse zu besch¨ aftigen. Von ihm stammen auch viele Hinweise zur inhaltlichen Gestaltung. Bei meiner Frau Heidrun und meinen Kindern Jan und Florian bedanke ich mich daf¨ ur, dass sie jederzeit meine Arbeit unterst¨ utzten. Meinen Kollegen Holger Langner und Marc Ritter danke ich f¨ ur die Gestaltung des Abschnittes 6.6 und f¨ ur viele spezielle Hinweise. Eine Reihe von Kollegen wie Jens Zeidler, Falk Schmidsberger, Andreas Ittner, J¨ org Wellner, Ulf Niel¨ ander, Niko S¨ underhauf und Andrea Sieber standen mir hilfreich bei der Gestaltung der Lehrveranstaltungen zur Seite. Daf¨ ur mein herzlicher Dank. Unserer Sekret¨arin Karin G¨ abel danke ich f¨ ur die Bereitschaft, mich bei der Erledigung organisatorischer Aufgaben zu entlasten. Auch allen Zuh¨ orern der Vorlesungen gilt mein Dank f¨ ur viele Anregungen zur Verbesserung des Skriptes. Dem Springer-Verlag und der Firma le-tex publishing services oHG danke ich f¨ ur ihre freundliche Unterst¨ utzung. Chemnitz, Juni 2008

Johannes Steinm¨ uller

sUppLex

Inhaltsverzeichnis 1 1.1 1.2 1.3 1.4 1.4.1 1.4.2 1.5 1.6

Einf¨ uhrung Einordnung des Fachgebietes .................................. Was ist Bildanalyse? ............................................ Einige Daten zur Entwicklung des Fachgebietes ........... Grundbegriffe und Vorgehensweise bei der Bildanalyse ... Modell nach Marr................................................ Modell der Bildanalyse.......................................... Anwendungen..................................................... Ausgew¨ahlte allgemeine Literaturhinweise ..................

2 2.1 2.2 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 2.3 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.3.6 2.3.7 2.3.8 2.3.9 2.4 2.4.1 2.4.2 2.4.3

Bildverarbeitung Einf¨ uhrung ........................................................ Punktoperationen ................................................ Kontrast und Helligkeit ......................................... Dehnung der Grauskala ......................................... Histogrammebnung .............................................. Schwellwertbildung – Binarisierung........................... Weitere Beispiele f¨ ur Punktoperationen ..................... Aufgaben .......................................................... Lokale Operationen .............................................. Lineare Faltung................................................... Lineare Faltung und Tiefpassfilter ............................ Lineare Faltung mit der Gaußverteilung ..................... Lineare Faltung und Kanten ................................... Separierbarkeit der linearen Faltung .......................... Gradient und Kanten ............................................ Rangfolgeoperationen ........................................... Auffinden von Eckpunkten ..................................... Aufgaben .......................................................... Globale Operationen ............................................ Grundidee ......................................................... Diskrete zweidimensionale Fouriertransformation.......... Anwendung der Fouriertransformation in der Bildverarbeitung.................................................. Faltungssatz ...................................................... Anwendung des Faltungssatzes................................ Schnelle Fouriertransformation – FFT ....................... Aufgaben ..........................................................

2.4.4 2.4.5 2.4.6 2.4.7

3 4 5 6 6 8 11 12

15 18 18 19 19 20 21 22 23 24 25 27 28 35 36 38 39 41 46 46 47 52 54 54 55 60

sUppLex

VIII

Inhaltsverzeichnis

3 3.1 3.2 3.3 3.4 3.4.1 3.4.2 3.4.3 3.4.4 3.4.5 3.5 3.6

Morphologische Operationen Dilation ............................................................ Erosion ............................................................. Opening und Closing ............................................ Anwendungen..................................................... Detektion von Bildanteilen mit bekannter Form ........... F¨ ullen von L¨ ochern .............................................. Extraktion von zusammenh¨angenden Komponenten ...... Alles oder Nichts-Transformation ............................. Abmagerung, Skelettierung .................................... Morphologische Operationen f¨ ur Grauwertbilder ........... Aufgaben ..........................................................

4 4.1 4.2 4.3 4.3.1 4.3.2 4.3.3 4.3.4 4.4 4.4.1 4.4.2 4.4.3 4.5 4.5.1 4.5.2 4.5.3 4.6 4.6.1 4.6.2 4.6.3 4.6.4 4.6.5 4.7 4.7.1 4.7.2 4.7.3

Bildsegmentierung Einf¨ uhrung ........................................................ Punktorientierte Segmentierung .............................. Mathematische Grundlagen .................................... Nachbarschaft .................................................... Weg und Zusammenhang ...................................... Komponentenzerlegung ......................................... Aufgaben .......................................................... Bestimmung von Komponenten............................... Ein allgemeiner Algorithmus – Region Growing ............ Zeilenkoinzidenzverfahren ...................................... Aufgaben .......................................................... Regionenorientierte Segmentierung........................... Allgemeine Definition der Segmentierung ................... Algorithmen zur Segmentierung............................... Aufgaben .......................................................... Kantenorientierte Segmentierung ............................. ¨ Uberblick .......................................................... Kantendetektion ................................................. Kantenverd¨ unnung............................................... Skelettierung ...................................................... Aufgaben .......................................................... Kantenverfolgung ................................................ Freemancode...................................................... Kantenverfolgung – Suchen von Wegen ..................... Aufbau einer Kostenfunktion und Anwendung von Suchverfahren .................................................... Aufgaben ..........................................................

4.7.4

67 70 76 81 81 81 83 83 84 85 86

93 94 96 96 99 101 104 105 105 106 111 112 112 115 118 119 119 121 121 122 124 125 126 128 130 130

sUppLex

Inhaltsverzeichnis

IX

4.8 4.9 4.9.1 4.9.2 4.9.3

Gebietsnachbarschaftsgraph ................................... Modellabh¨angige Verfahren zur Segmentierung............ Matchen ........................................................... Hough-Transformation .......................................... Aufgaben ..........................................................

131 134 135 136 142

5 5.1 5.2 5.2.1 5.2.2 5.2.3 5.2.4 5.2.5 5.2.6 5.3 5.4 5.5 5.6 5.7 5.8 5.9

Merkmale von Objekten Einf¨ uhrung ........................................................ Geometrische Merkmale ........................................ Fl¨ache eines Segmentes......................................... Umfang eines Segmentes ....................................... Kompaktheit eines Segmentes................................. Umschreibende Rechtecke...................................... Konvexe H¨ ulle eines Segmentes ............................... Weitere geometrische Merkmale .............................. Momente .......................................................... Laufl¨angenkodierung ............................................ Eulerzahl........................................................... Fourierdarstellung von Segmentkonturen.................... Relationalstrukturen ............................................. Statistische Merkmale – Textur ............................... Aufgaben ..........................................................

145 146 146 146 147 148 149 149 149 152 154 157 158 159 160

6 6.1 6.2 6.2.1 6.2.2 6.3 6.4 6.5 6.5.1 6.5.2 6.5.3 6.6 6.6.1 6.6.2 6.6.3 6.6.4 6.6.5

Klassifikation Prinzipielle Vorgehensweise bei der Klassifikation ......... Numerische Klassifikation ...................................... Lineare Klassifikation............................................ Abstandsklassifikatoren ......................................... Statistische Klassifikation ...................................... Syntaktische Klassifikation ..................................... Kontextabh¨angige Klassifikation .............................. Graphmatching ................................................... Diskrete Relaxation .............................................. Kontinuierliche Relaxation ..................................... Hauptkomponentenanalyse (PCA) ........................... Zweck der Hauptkomponentenanalyse ....................... Hauptkomponententransformation ........................... Formalisierung als Maximierung der Datenvarianz ........ Formalisierung als Minimierung der Datenredundanz ..... Hauptkomponentenbestimmung durch L¨osung des Eigenwertproblems............................................... Hauptkomponentenanalyse: Schritt f¨ ur Schritt ............

6.6.6

165 166 168 169 170 172 175 176 177 179 180 180 181 182 184 185 186

sUppLex

X

Inhaltsverzeichnis

6.6.7 6.6.8 6.7

Hauptkomponentenanalyse f¨ ur h¨oherdimensionale Daten 186 Anwendung in der Bildverarbeitung .......................... 188 Aufgaben .......................................................... 191

7 7.1 7.2 7.3 7.4 7.5 7.5.1 7.5.2 7.5.3 7.5.4 7.5.5

Dreidimensionale Bildinterpretation Einf¨ uhrung ........................................................ Generierung der 21/2 D-Skizze................................... Formale Pr¨azisierung der Gestaltsrekonstruktion .......... Naheliegende Grenzen der Gestaltsrekonstruktion ......... Zentralprojektion................................................. Definition .......................................................... Zentralprojektion von Geraden ................................ Zentralprojektion im Koordinatensystem .................... Homogene Koordinaten......................................... Rekonstruktion von 3D-Informationen aus der Zentralprojektion................................................. Doppelverh¨altnis ................................................. Aufgaben .......................................................... Shape from Stereo ............................................... Grundlagen ........................................................ Korrespondenzproblem.......................................... Epipolarlinien ..................................................... Korrespondierende Punkte auf Grund von Bildeigenschaften ................................................ Disparit¨atslimit ................................................... Kontinuit¨at von Disparit¨aten .................................. Disparit¨atsgradientenlimit ...................................... Reihenfolge der Punkte ......................................... Aufgaben .......................................................... Shape from shading ............................................. Einf¨ uhrung ........................................................ Lambertsche Oberfl¨ache ........................................ Problemstellung .................................................. Reflektivit¨atskarte................................................ Reflektivit¨atsgleichung .......................................... L¨ osung der Reflektivit¨atsgleichung ........................... Aufgaben .......................................................... Shape from contour ............................................. Einf¨ uhrung ........................................................ Kantenmarken .................................................... Knotentypen ......................................................

7.5.6 7.5.7 7.6 7.6.1 7.6.2 7.6.3 7.6.4 7.6.5 7.6.6 7.6.7 7.6.8 7.6.9 7.7 7.7.1 7.7.2 7.7.3 7.7.4 7.7.5 7.7.6 7.7.7 7.8 7.8.1 7.8.2 7.8.3

199 200 201 202 204 204 205 208 212 215 217 220 222 222 224 225 228 228 229 230 230 230 231 231 232 235 236 237 238 240 240 240 242 242

sUppLex

Inhaltsverzeichnis

XI

7.8.4 7.8.5 7.8.6 7.8.7 7.9 7.9.1 7.9.2 7.9.3 7.9.4

Knotenmarken .................................................... Waltz-Algorithmus ............................................... Erweiterungen .................................................... Aufgaben .......................................................... Weitere M¨ oglichkeiten f¨ ur Shape from X ................... Shape from motion .............................................. Shape from texture .............................................. Shape from focus ................................................ Shape from structured light ...................................

242 244 245 246 247 247 247 247 247

8 8.1 8.2 8.3 8.3.1 8.3.2 8.3.3 8.3.4 8.3.5 8.3.6

Bewegungsanalyse aus Bildfolgen Einleitung.......................................................... Lokale Verschiebungsvektoren ................................. Optischer Fluss ................................................... Vorbemerkungen ................................................. Horn-Schunck-Verfahren ....................................... L¨ osung mit Hilfe der Variationsrechnung.................... L¨ osung mit diskreter Iteration ................................. Algorithmus zur Berechnung des optischen Flusses ....... Aufgaben ..........................................................

251 252 255 255 257 259 260 264 265

Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

267

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

sUppLex

Kapitel 1 Einf¨ uhrung

1

sUppLex

1

1 1.1 1.2 1.3 1.4 1.4.1 1.4.2 1.5 1.6

Einf¨ uhrung Einordnung des Fachgebietes .................................. Was ist Bildanalyse? ............................................ Einige Daten zur Entwicklung des Fachgebietes ........... Grundbegriffe und Vorgehensweise bei der Bildanalyse ... Modell nach Marr................................................ Modell der Bildanalyse.......................................... Anwendungen..................................................... Ausgew¨ahlte allgemeine Literaturhinweise ..................

3 4 5 6 6 8 11 12

sUppLex

1 Einfu ¨hrung In diesem Kapitel ordnen wir das Fachgebiet der Bildanalyse in u ¨bergreifende Konzepte ein. Wir beschreiben kurz einige Grundbegriffe und die prinzipielle Vorgehensweise der Bildverarbeitung und der Bildanalyse. Weiter geben wir einige geschichtliche Daten und listen verschiedene Anwendungen auf.

1.1

1.1 Einordnung des Fachgebietes Bildverarbeitung und insbesondere Bildanalyse (Bildverstehen) besch¨aftigt sich mit der Analyse und Interpretation von visueller Information, d.h. mit Bildern oder Bildfolgen und ist eines der schwierigsten Teilgebiete der Informatik. Es wird oft der K¨ unstlichen Intelligenz zugeordnet. Neben der Bearbeitung von Bildern geht es bei der Bildanalyse darum, auf den Bildern etwas zu erkennen. Dies k¨ onnen z.B. Objekte sein, die sich vom Bildhintergrund abheben. Trotz seiner mehr als 50-j¨ ahrigen Geschichte sind noch viele Fragen offen. Es gibt noch keine maschinellen Sehsysteme, die auch nur ann¨ahernd die Leistungsf¨ ahigkeit des menschlichen Sehsystems erreichen. Daf¨ ur gibt es zahlreiche Gr¨ unde: Die Konzepte wandelten sich in der Vergangenheit mehrfach grundlegend und sind auch heute noch im Fluss. Bildanalyse stellt hohe Anspr¨ uche an das formale R¨ ustzeug der Wissenschaftler. Es werden komplexe mathematische Modelle benutzt. Die Funktionsweise biologischer Sehsysteme ist erst wenig verstanden. Oft ben¨ otigt man Systeme, die in kurzer Zeit viele Bilder auswerten m¨ ussen. Beispiel 1.1 Ein kleines Kind kann aus 100 Bildern verschiedener Frauen pro-

1.1

blemlos das mit seiner Mutter herausfinden. Ein Computerprogramm, das 10 einfache geometrische Figuren unterscheiden soll, ist schon aufwendig. Man kann sich dem Problem der Erforschung des Sehens von verschiedenen Seiten n¨ ahern: Informatik: K¨ unstliche Intelligenz Digitale Bildverarbeitung Mustererkennung

sUppLex

4

1. Einf¨ uhrung

Neurokognition (Verhalten und Erleben des Menschen) Neurophysiologie (Lebensvorg¨ ange und Funktionen des menschlichen Nervensystems) Es gibt zahlreiche interdisziplin¨ are Forschungsgruppen. Wir beschr¨anken uns auf Aspekte der Informatik. Innerhalb der graphischen Datenverarbeitung ordnen wir uns wie folgt ein (Abb. 1.1): Eingabe Bild

Beschreibung

Bildverarbeitung

Computergrafik

Ausgabe

Bild

Bildanalyse Beschreibung

Andere Bildverstehen

Abb. 1.1. Einordnung der Bildverarbeitung und der Bildanalyse als Teilgebiete der graphischen Datenverarbeitung

Das vorliegende Buch besch¨ aftigt sich sowohl mit der Bildverarbeitung als auch mit der Bildanalyse.

1.2

1.2 Was ist Bildanalyse? Bildanalyse (Computer Vision) ist ein komplizierter Prozess. Man geht aus von einem Bild oder mehreren Bildern (z.B. Bildfolgen) und einer Fragestellung. Resultat des Prozesses ist eine Beschreibung des Bildes oder der Bildfolge. Was diese Beschreibung enth¨ alt, h¨angt oft vom Bild und von der Fragestellung ab.

1.2

Beispiel 1.2 Einige m¨ ogliche Beschreibungen f¨ ur die Abb. 1.2 sind:

ein Bin¨ arbild eine Kreislinie, und 25 Strecken 1 Kreis, 4 Rechtecke und 10 einzelene Linien Sonne und Haus es ist sch¨ ones Wetter, die Sonne scheint

sUppLex

1.3

Einige Daten zur Entwicklung des Fachgebietes

5

Abb. 1.2. Wie versteht man dieses Bild?

Man sieht, dass jede dieser Beschreibungen in einem gewissen Kontext relevant ist. Die Arbeitsweise eines bildverstehenden Systems wird also von der jeweiligen Fragestellung und der Anwendung abh¨angen. Definition 1.1 Bildverstehen ist die Rekonstruktion und Deutung einer Szene (zeitlich-r¨ aumlicher Ausschnitt der Realwelt) anhand von Bildern (zweidimensionale Projektionen einer Szene).

1.1

Einige m¨ ogliche und schon anspruchsvollere Fragestellungen (Anwendungen) sind: kollisionsfreies Navigieren eines Roboters in der Szene planm¨ aßiges Greifen und Manipulieren von Objekten in der Szene durch einen Industrieroboter Ausgabe von Warnsignalen bei gef¨ ahrlichen Situationen inhaltsbasierte Bildsuche im Internet Ausgabe einer sprachlichen Szenenbeschreibung Beantworten sprachlicher Anfragen bez¨ uglich der Szene

1.3 Einige Daten zur Entwicklung des Fachgebietes

1.3

Im Folgenden werden nur einige Eckpunkte der Entwicklung der Bildanalyse aufgelistet. Eine vollst¨ andigere geschichtliche Abhandlung ist nicht Ziel des Buches. 1955: Aufbereitung von Luftbildern (milit¨ arisch interessante Aufgaben im Bereich der Bildverarbeitung) 1960: Zeichenerkennung, Mustererkennung (Klassifikation) 1965: Analyse von Polyederszenen (Blockswelt, Roberts[43])

sUppLex

6

1. Einf¨ uhrung

1975: Rekonstruktion dreidimensionaler Informationen aus zweidimensionalen Bildern, Klassifizierung von Knoten und Kanten in Blocksweltszenen (Waltz[55]) 1979: erste internationale Arbeitstagung zum Thema Bildfolgen (Bewegungsanalyse) 1979: Analyse von Straßenverkehrsszenen 1982: Untersuchung biologischer Systeme, Einbeziehung von Forschungsergebnissen aus der Neurophysiologie und Psychophysik f¨ ur das Bildverstehen, Orientierung an kognitiven Zielen Entwurf einer hierarchischen Rahmenarchitektur f¨ ur Sehsysteme, in der verschiedene Zwischenrepr¨ asentationen und Verarbeitungsprozesse vorgesehen sind (Marr[37]). 1990: Modellierung eines Sehsystems als aktiv handelnder Agent (Aktives Sehen) 1990: Anwendung neuronaler Netze 1992: automatische Fahrzeugsteuerung

1.4

1.4 Grundbegriffe und Vorgehensweise bei der Bildanalyse Wir betrachten 2 Modelle, um wesentliche Begriffe und die prinzipielle Vorgehensweise der Bildanalyse zu demonstrieren. 1.4.1 Modell nach Marr Dazu betrachten wir Abb. 1.3 auf Seite 7. Im Einzelnen bedeuten: Bild: digitales Rasterbild mit radiometrischen Eigenschaften jedes Bildpunktes, wie: Grauwert Farbe prim¨ are Skizze: erster Eindruck, die sehr große Datenmenge des Bildes soll sinnvoll reduziert werden, ohne wesentliche Informationen f¨ ur die nachfolgenden Verarbeitungsschritte zu verlieren, z.B.: Grauwert¨ anderungen, Kanten lokale 2D-Geometrie einfacher Bildelemente Gruppierung einfacher Elemente

sUppLex

1.4

Grundbegriffe und Vorgehensweise bei der Bildanalyse

7

Bild

prim¨are Skizze

21/2 D-Skizze

3D-Modellrepr¨asentation Abb. 1.3. Modell der Bildanalyse nach Marr [37]

1 2/ 2 D-Skizze: geometrische und photometrische Eigenschaften der sichtbaren Oberfl¨ achen: partielle Form- und Geometriekonstruktion Tiefeninformation Orientierung der sichtbaren Oberfl¨ achen (Normalvektoren) Konturen von Oberfl¨ achendiskontinuit¨ aten (Orientierungsspr¨ unge, Entfernungs¨ anderungen)

3D-Repr¨ asentation: Integration mehrerer 21/2 D-Skizzen Aussagen u ¨ber verdeckte Teile Szenenbeschreibung (Objekte und deren Relationen zueinander)

sUppLex

8

1. Einf¨ uhrung

1.4.2 Modell der Bildanalyse Wir betrachten ein einfaches Gesamtmodell der Bildanalyse (Abb. 1.4). Es besteht aus 6 Repr¨ asentationsebenen. Drei in der Realit¨at und die anderen drei auf der Computerebene. Szene

Szenenauswahl

Aufnahme

Welt

Bild

Realität

Interaktion

Bildverarbeitung Segmentierung

Computer

Weltbeschreibung

Bildbeschreibung

Bildanalyse Objekterkennung

Höhere Bilddeutung

Szenenbeschreibung

Abb. 1.4. Gesamtmodell zum Bildverstehen nach Pinz [40]

Die 6 Repr¨ asentationsebenen k¨ onnen wir folgendermaßen charakterisieren. Welt: physikalische Objekte mit Attributen Objektkonfigurationen Bewegung der Objekte

sUppLex

1.4

Grundbegriffe und Vorgehensweise bei der Bildanalyse

9

Szene: 3D-Ausschnitt der Welt bestimmter Zeitpunkt Bild: 2D-Abbild einer Szene Bildbeschreibung: vom Bild ausgehend (Bottom-up 2D-Bildelemente (Kanten, Segmente) ohne Vorerwartungen Szenenbeschreibung: Interpretation der Bildelemente als Szenenelemente, z.B. Bildkante – Hauskante oder Schattengrenze, roters Segment – Hauswand, gr¨ unes Segment – Gras Weltbeschreibung: von einer Fragestellung ausgehend (Top-down) es wird Vorwissen (Hintergrundwissen) ben¨otigt

Wir beschreiben nun die einzelnen Prozesse etwas genauer. Szenenauswahl Welt

Szene

Abb. 1.5. Szenenauswahl

Was soll betrachtet werden? Wann wird betrachtet?

Aufnahme Szene

Bild

Abb. 1.6. Bildaufnahme

sUppLex

10

1. Einf¨ uhrung

Wie soll die Szene betrachtet werden? Sensorauswahl Auf einige Probleme der Bildaufnahme werden wir im Kapitel 7 eingehen. Bildverarbeitung, Bildsegmentierung Bild-

Bild

beschreibung

Abb. 1.7. Bildverarbeitung und Bildsegmentierung

Bildverbesserung Bild zu Bild Transformationen Finden von Kanten Finden von homogenen Bildbereichen (Bildsegmentierung) Diese Probleme werden in den Kapiteln 2, 3 und 4 behandelt. Bildanalyse, Objekterkennung Bild-

Szenen-

beschreibung

beschreibung

Abb. 1.8. Bildanalyse – Objekterkennung

Gruppierung einfacher geometrischer Objekte Berechnung von Objektmerkmalen Klassifikation von Objekten Shape from X (die Form wird aufgrund einer bestimmten Methode X errechnet) 21/2 D-Rekonstruktion der Szene Darauf gehen wir in den Kapiteln 5, 6 und 7 n¨aher ein. H¨ ohere Bilddeutung Szenen-

Welt-

beschreibung

beschreibung

Abb. 1.9. H¨ ohere Bilddeutung

sUppLex

1.5

Anwendungen

11

Repr¨ asentation und Prozesse oberhalb der Ebene erkannter Objekte Objektkonfigurationen Situationen Bewegungsabl¨ aufe Episoden Diese Probleme gehen weit u ¨ber den Rahmen des Buches hinaus und werden nicht behandelt. Interaktion Weltbeschreibung

Welt

Abb. 1.10. Interaktion mit der Umwelt

direkte Interaktion mit der Umwelt Umwelt ver¨ andern Richtigkeit des bildverstehenden Systems verifizieren aktiver Roboter Auch dies ist Gegenstand anderer Gebiete (wie der Robotik).

1.5

1.5 Anwendungen Die Bildverarbeitung hat trotz vieler offener Fragen bereits zahlreiche erfolgreiche spezielle Anwendungen: Zeichenerkennung Qualit¨ atspr¨ ufung in der industriellen Produktion Medizinische Bildanalyse Luftbildauswertung Fahrzeugsteuerung Gesichtserkennung Robotik Inhaltsbasierte Bildsuche im Internet (Suche nach vermissten Kindern, Suche nach staatsfeindlichen Symbolen) Auf Details dieser Anwendungen werden wir nicht weiter eingehen.

sUppLex

12

1.6

1. Einf¨ uhrung

1.6 Ausgew¨ ahlte allgemeine Literaturhinweise Allgemeine Lehrb¨ ucher zur Bildverarbeitung und Bildanalyse sind [1], [4], [9], [12], [14], [16], [25], [27], [31], [40], und [50]. Die Verbindung zur Programmierung mit Java und ImageJ wird in [9] hergestellt. B¨ ucher zur K¨ unstlichen Intelligenz, die auch Kapitel zur Bildanalyse enthalten sind [15], [44] und [56]. In [38] wird die Computergrafik und die Bildverarbeitung gemeinsam dargestellt. Eine Sammlung von Operatoren zur Bildverarbeitung enth¨alt [28]. Ein ganzes Buch u ¨ber morphologische Operationen ist [47]. Theoretische Aspekte zur diskreten Geometrie im Zusammenhang mit der Bildverarbeitung enth¨ alt [53], [54] und [30]. Fragen zur Klassifikation und des Maschinellen Lernens werden in [2], [6], und [44] behandelt. Die dreidimensionale Bildinterpretation wird in [12], [18], [26], [29] und [36] behandelt. Bewegungsanalyse aus Bildfolgen findet man in [29]. Aspekte der parallelen Bildverarbeitung beschreibt [7] und [8]. Objektorientierte Methoden in der Bildverbeitung nutzt [57]. Fuzzy und Bildverarbeitung behandelt [49]. Verschiedene Anwendungen findet man in [11], [24], [33] und [48].

sUppLex

Kapitel 2 Bildverarbeitung

2

sUppLex

2

2 2.1 2.2 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 2.3 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.3.6 2.3.7 2.3.8 2.3.9 2.4 2.4.1 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6 2.4.7

Bildverarbeitung Einf¨ uhrung ........................................................ Punktoperationen ................................................ Kontrast und Helligkeit ......................................... Dehnung der Grauskala ......................................... Histogrammebnung .............................................. Schwellwertbildung – Binarisierung........................... Weitere Beispiele f¨ ur Punktoperationen ..................... Aufgaben .......................................................... Lokale Operationen .............................................. Lineare Faltung................................................... Lineare Faltung und Tiefpassfilter ............................ Lineare Faltung mit der Gaußverteilung ..................... Lineare Faltung und Kanten ................................... Separierbarkeit der linearen Faltung .......................... Gradient und Kanten ............................................ Rangfolgeoperationen ........................................... Auffinden von Eckpunkten ..................................... Aufgaben .......................................................... Globale Operationen ............................................ Grundidee ......................................................... Diskrete zweidimensionale Fouriertransformation.......... Anwendung der Fouriertransformation in der Bildverarbeitung.................................................. Faltungssatz ...................................................... Anwendung des Faltungssatzes................................ Schnelle Fouriertransformation – FFT ....................... Aufgaben ..........................................................

15 18 18 19 19 20 21 22 23 24 25 27 28 35 36 38 39 41 46 46 47 52 54 54 55 60

sUppLex

2 Bildverarbeitung Dieses Kapitel behandelt die wichtigsten Operationen (Transformationen, Operatoren) der Bildverarbeitung. Großer Wert wird auf die Darstellung des mathematischen Hintergrunds gelegt. Technische Anwendungsdetails werden relativ kurz besprochen.

2.1

2.1 Einf¨ uhrung In der Bildverarbeitung (oder Bildvorverarbeitung) werden Bilder immer wieder zu Bildern transformiert. Einige Aufgaben der Bildverarbeitung sind: Bildverbesserung, Korrektur von Bildfehlern Kantendetektion Segmentierung des Bildes, Finden homogener Bereiche erste Bildanalyse Unter einem Bild verstehen wir eine Matrix von Bildpunkten (Abb. 2.1) G = (g(i, j))

0 0

I −1

J −1

mit

i = 0, . . . , I − 1;

6 0 0 .. 0 . 0 0 1 0 0 0 0

0 0 0 0 0 0 0 1

0 0 0 3 9 9 0

0 0 3 3 9 9 0

0 0 3 0 3 3 3 3 9 9 9 9 0 0 ...

0 0 0 3 9 9 0

j = 0, . . . , J − 1. 0 0 0 0 0 0 0

(2.1)

0 0 0 0 0 0 0 8

Abb. 2.1. Ein Bild (links) wird als Matrix von Grauwerten (rechts) dargestellt.

Dabei ist I die Anzahl der Bildzeilen und J die Anzahl der Bildspalten. Die 0-te Spalte wird wie u ¨blich links angeordnet. Die 0-te Zeile kann unten stehen (wie beim (i, j)-Koordinatensystem) oder oben (Matrixnotation) und wird in der Bildverarbeitung je nach Kontext verschieden angewendet. Falls es von Bedeutung ist, werden wir immer explizit darauf hinweisen. Die Matrixelemente g(i, j) sind reelle Zahlen (z.B. Grauwerte) und geh¨oren einer festgelegten Menge W an.

sUppLex

16

2. Bildverarbeitung

Mit Gmin bzw. Gmax bezeichnen wir den kleinsten bzw. gr¨oßten Wert aus W . Z.B. kann man f¨ ur W die Menge der nat¨ urlichen Zahlen des Intervalls [0, 255] nehmen, dann gilt Gmin = 0 und Gmax = 255. Unter einer Bildfolge verstehen wir eine Folge von Matrizen

G(k) = (g(i, j, k))

mit

i = 0, . . . , I − 1;

j = 0, . . . , J − 1;

k = 1, . . . , K.

Dabei ist K die Anzahl der Bilder und g(i, j, k) ∈ W sind reelle Zahlen. Bildfolgen werden u. a. bei der Bewegungsanalyse ben¨otigt (siehe Kapitel 8). Die beiden folgenden Begriffe werden in der Bildverarbeitung oft verwendet. 2.1

Definition 2.1: Histogramm

Sei G = (g(i, j)) ein Bild und W ⊂ R die Menge der m¨oglichen Bildwerte, d.h. g(i, j) ∈ W . Die Funktion H(w) = |{(i, j) : g(i, j) = w}| : W → N heißt Histogramm des Bildes G. Dabei bezeichne N = 0, 1, 2, . . . die Menge der nat¨ urlichen Zahlen. H(w) ist also die Anzahl der Bildwerte g(i, j) mit g(i, j) = w. 2.2

Definition 2.2: kumulatives Histogramm

Die Funktion



H(w) =

H(w ) : W → N

w ∈W :w ≤w

heißt kumulatives Histogramm des Bildes G. Falls W die Menge der nat¨ urlichen Zahlen zwischen Gmin und Gmax ist, so gilt  H(w) =

H(Gmin )

falls

w = Gmin

H(w − 1) + H(w)

falls

Gmin < w ≤ Gmax .

Folgerung 1

H(Gmax ) = I · J

sUppLex

2.1

Einf¨ uhrung

17

Sei nun GE = (gE (i, j))

mit

i = 0, . . . , I − 1;

j = 0, . . . , J − 1

das Eingabebild bzw. GE (k) = (gE (i, j, k));

k = 1, . . . , K

eine Eingabebildfolge und GA = (gA (i, j)) das Ausgabebild. Wir unterscheiden in der Bildverarbeitung 3 Arten von Operationen: Punktoperationen lokale Operationen globale Operationen Definition 2.3: Punktoperation

2.3

Ein Bildpunkt gA (i, j) des Ausgabebildes ist nur eine Funktion eines einzelnen Bildpunktes gE (i1 , j1 ) des Eingabebildes bzw. der Eingabebildfolge (i, i1 = 0, . . . , I − 1; j, j1 = 0, . . . , J − 1): gA (i, j) = f [{gE (i1 , j1 , k) : k = 1, . . . , K}]

Hierzu geh¨ oren auch Operationen zur geometrischen Entzerrung eines Bildes, bei der die Koordinaten (i1 , j1 ) in die Koordinaten (i, j) transformiert werden. Oft ist i = i1 und j = j1 . Definition 2.4: Lokale Operation

2.4

Ein Bildpunkt gA (i, j) des Ausganbebildes ist eine Funktion der Bildpunkte in einer wohldefinierten lokalen Umgebung U um den entsprechenden Punkt (i, j) des Eingabebildes bzw. der Eingabebildfolge. Die lokale Umgebung wird meist symmetrisch zum betrachteten Punkt, oft quadratisch gew¨ahlt : gA (i, j) = f [{gE (i , j  , k) : (i , j  ) ∈ U ;

k = 1, . . . , K}]

sUppLex

18

2. Bildverarbeitung

Falls U ein Rechteck, so gilt gA (i, j) = f [{gE (i − l, j − m, k) : L−1 L−1 ,...,+ l=− 2 2 M −1 M −1 m=− ,...,+ 2 2 k = 1, . . . , K}]. Dabei sind L und M ungerade nat¨ urliche Zahlen. Selten (wie bei der RobertsOperation Beispiel 2.16) verwendet man Rechtecke mit geradzahligen Seitenl¨ angen. 2.5

Definition 2.5: Globale Operation

Ein Bildpunkt gA (i, j) des Ausgabebildes ist eine Funktion aller Punkte des Eingabebildes bzw. der Eingabebildfolge: gA (i, j) = f [{gE (i, j, k) : i = 0, . . . , I − 1;

j = 0, . . . , J − 1;

k = 1, . . . , K}]

Anmerkung 2.1.1 F¨ ur die bildliche Darstellung der mit den Operationen be-

rechneten Werte gA (i, j) ist noch oft eine Nachbearbeitung n¨otig, da auch negative oder nichtganzzahlige Werte entstehen k¨onnen. Auf diese Details gehen wir nicht weiter ein.

2.2

2.2 Punktoperationen 2.2.1 Kontrast und Helligkeit Die Grauwerte des Ausgabebildes berechnen wir wie folgt: gA (i, j) = K · gE (i, j) + H Die Konstante H entspricht der Helligkeit und die Konstante K entspricht dem Kontrast. Wenn K > 1 wird der Kontrast erh¨oht und wenn 0 < K < 1 wird der Kontrast erniedrigt. Durch Addition von H wird das ganze Bild heller oder dunkler (Abb. 2.2).

sUppLex

2.2

Punktoperationen

19

Helligkeit erh¨ ohen

Abb. 2.2. Erh¨ ohen der Helligkeit

Hierzu geh¨ ort auch das Invertieren (K = −1): gA (i, j) = Gmax − gE (i, j) 2.2.2 Dehnung der Grauskala Sei Emin = min{gE (i, j)} i,j

und Emax = max{gE (i, j)}. i,j

Die zur Verf¨ ugung stehende Grauwertskala des Ausgabebildes liege zwischen A1 und A2 , d.h. A1 ≤ gA (i, j) ≤ A2 . Die Transformationsgleichung lautet dann: gA (i, j) =

A2 − A1 · (gE (i, j) − Emin ) + A1 Emax − Emin

In dieser Gleichung wird die Grauskala so modifiziert, dass der volle Zahlenbereich zwischen A1 und A2 im Ausgabebild ausgenutzt wird (Abb. 2.3 und 2.4). 2.2.3 Histogrammebnung Der zu dehnende Bereich kann auch automatisch aus den Eingabebild berechnet werden. Dazu benutzt man das kommulative Histogramm (siehe Definition 2.2). Die Grauwerte des Ausgabebildes berechnen sich dann wie folgt: gA (i, j) =

Gmax · [H(gE (i, j)) − H(Gmin )] I · J − H(Gmin )

sUppLex

20

2. Bildverarbeitung

Gmax

Ausgabebild GA

A2

A1

0 Emin

Emax

Gmax

Eingabebild GE Abb. 2.3. Lineares Dehnen der Grauwerte

Abb. 2.4. Lineares Dehnen der Grauwerte – der Kontrast wird erh¨ oht.

2.2.4 Schwellwertbildung – Binarisierung Hier wird das Eingabebild mit Hilfe von ein oder mehreren Schwellwerten in ein Bin¨ arbild transformiert (Abb. 2.5):  gA (i, j) =  gA (i, j) =

0 1

falls

0 1

falls

gE (i, j) ≤ T gE (i, j) > T

gE (i, j) ≤ T1 oder T1 < gE (i, j) ≤ T2

gE (i, j) > T2

F¨ ur die Schwellwerte k¨ onnen lokale Minima des Histogramms gew¨ahlt werden.

sUppLex

2.2

Punktoperationen

21

gA

gA

1

0

T

gE

T1

T2

gE

Abb. 2.5. Transformation mit Schwellwerten

2.2.5 Weitere Beispiele f¨ ur Punktoperationen Beispiel 2.1: Farbtransformationen

2.1

Von einer Szene wurden die drei Farbausz¨ uge GR , GG , GB ( R – rot, G – gr¨ un, B – blau ) erstellt. Mit Hilfe der Farbtransformation kann die aufgrund ihrer farblichen Eigenschaften relevante Information durch Wahl geeigneter skalarer Gewichte a, b, c hervorgehoben werden: gA (i, j) = a · gR (i, j) + b · gG (i, j) + c · gB (i, j) Beispiel 2.2: Hintergrundsubtraktion

2.2

Vor dem zu verarbeitenden Bild GE = (gE (i, j)) wird ein Hintergrundbild GH = (gH (i, j)) aufgenommen, das die relevanten Objekte nicht enth¨alt. Die Hintergrundsubtraktion trennt dadurch die relevanten Objekte vom Hintergrund insofern, als der Hintergrund praktisch durch Nullen und der Bereich der relevanten Objekte durch von Null verschiedene Werte charakterisiert wird: gA (i, j) = gE (i, j) − gH (i, j)

sUppLex

22

2.3

2. Bildverarbeitung

Beispiel 2.3: Maskierung

Zur Extraktion semantisch bedeutsamer Teile eines Bildes dient eine Bin¨armaske GB = (gB (i, j)) in der mit gB (i, j) = 1 die Punkte gekennzeichnet sind, die zu dem interessierenden Objekt geh¨oren und mit gB (i, j) = 0 die Punkte außerhalb des interessierenden Objektes: gA (i, j) = gB (i, j) · gE (i, j) 2.4

Beispiel 2.4: Geometrische Transformationen

Bei den bisher betrachteten Bildpunkttransformationen wurden die Ortskoordinaten der Bildpunkte nicht ge¨ andert. Oft besteht jedoch die Notwendigkeit, eine Ortskoordinatentransformation durchzuf¨ uhren. So muss man beim Vergleich von Bildern unterschiedlicher Gr¨oße vor der Verarbeitung eine Gr¨ oßennormierung vornehmen, oder Abb.sfehler und Bildverzerrungen beseitigen. Eine Abb. ist die Verschiebung: gA (i, j) = gE (i + p, j + q)p, q

Konstanten

Allgemein kann die Transformation folgendermaßen beschrieben werden: gA (i, j) = gE (i1 , j1 ) mit

i1 = f1 (i, j);

j1 = f2 (i, j)

Dabei sind f1 und f2 beliebige Abbildungsfunktionen. Probleme treten am Bildrand auf, da (i1 , j1 ) nicht im Indexbereich des Eingangsbildes liegen muss. 2.2.6 Aufgaben 2.2.1

Aufgabe 2.2.1 Sei

⎛

50 ⎜ 40 ⎜ ⎜ 40 ⎜ ⎜ ⎜ 40 GE = ⎜ ⎜ 40 ⎜ ⎜150 ⎜ ⎝150 200

50 100 100 100 100 100 100 200

50 100 110 110 100 120 120 200

50 100 110 110 100 120 120 200

50 100 110 110 100 120 120 200

50 100 110 110 100 120 120 200

50 100 100 100 100 100 100 200

⎞ 50 40 ⎟ ⎟ 40 ⎟ ⎟ ⎟ 40 ⎟ ⎟ 40 ⎟ ⎟ 150⎟ ⎟ 150⎠ 200

(2.2)

ein Eingabebild. Berechnen Sie das Histogramm.

sUppLex

2.3

Lokale Operationen

23

Aufgabe 2.2.2 Berechnen Sie ein Ausgabebild GA , indem Sie eine lineare Deh-

2.2.2

nung der Grauwerte von GE aus Aufgabe 2.2.1 auf dem Bereich A1 = 25 ≤ gA (i, j) ≤ A2 = 250 vornehmen. Vergleichen Sie die Histogramme von GE und GA . Aufgabe 2.2.3 Im Bild GE aus Aufgabe 2.2.1 sollen die Grauwerte von 100

2.2.3

bis 120 auf dem Bereich von 0 bis 250 linear transformiert werden. Grauwerte kleiner als 100 oder gr¨ oßer als 120 werden auf 0 abgebildet. Beschreiben Sie die Abbildungsfunktion und berechnen Sie das entsprechende Ausgabebild GA . Aufgabe 2.2.4 Im Bild GE aus Aufgabe 2.2.1 sollen die Grauwerte von 100

2.2.4

bis 120 auf dem Bereich von 50 bis 200 linear transformiert werden, sowie der Bereich 0 bis 100 auf 0 bis 50 und der Bereich 120 bis 200 auf 200 bis 250. Beschreiben Sie die drei Abbildungsfunktionen und berechnen Sie das entsprechende Ausgabebild GA . Aufgabe 2.2.5 Berechnen Sie das kumulative Histogramm des Bildes GE aus

2.2.5

Aufgabe 2.2.1. Aufgabe 2.2.6 Wenden Sie auf das Bild GE aus Aufgabe 2.2.1 die Histogram-

2.2.6

mebnung (Abschnitt 2.2.3) an. Vergleichen Sie danach die Histogramme von GE und GA . Aufgabe 2.2.7 Wenden Sie auf das Bild GE aus Aufgabe 2.2.1 verschiedene Schwellwertoperationen aus Abschnitt 2.2.4 an. Untersuchen Sie die Wirkung verschiedener Schwellwerte T .

2.2.7

2.3

2.3 Lokale Operationen Hier kann man jene Informationen aus einem Bild extrahieren, die durch eine Verkn¨ upfung eines Bildpunktes mit seiner lokalen Nachbarschaft gewonnen werden k¨ onnen. Ein Beispiel ist das Auffinden von Kanten. Um Kantenstrukturen zu finden, gen¨ ugt es nicht, Punktoperationen durchzuf¨ uhren. Eine solche Fragestellung kann man nur l¨osen, wenn man die Bild-

sUppLex

24

2. Bildverarbeitung

punkte eines Bildes zusammen mit ihrer Nachbarschaft untersucht. Bei einer Kante ¨ andern sich zum Beispiel die Grauwerte innerhalb eines kleinen Bereiches sehr stark.

2.3.1 Lineare Faltung 2.6

Definition 2.6 Seien L, M ungerade nat¨ urliche Zahlen,

GE = (gE (i, j)) ein Eingabebild und ⎛

M −1 L−1 M −1 ⎞ h(− L−1 2 , − 2 ) . . . . . . h(− 2 , 2 ) ⎜. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎟ ⎜ ⎟ ⎟ H = (h(l, m)) = ⎜ ⎜. . . . . . . . . . . . . . . . h(0, 0) . . . . . . . . . . . . . .⎟ ⎝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .⎠ M −1 L−1 M −1 h( L−1 2 , − 2 ) . . . . . . h( 2 , 2 )

eine Matrix mit i = 0, . . . , I − 1; l=−

L−1 L−1 ,..., ; 2 2

j = 0, . . . , J − 1 m=−

M −1 M −1 ,..., 2 2

Die lineare Faltung GF = (gF (i, j)) = H ∗ GE von GE mit dem Faltungskern H wird durch die folgende Faltungssumme definiert:

gF (i, j) =

L−1

M −1 2

l=− L−1 2

m=− M2−1

2 



h(l, m) · gE (i − l, j − m)

(2.3)

:= h(i, j) ∗ gE (i, j)

sUppLex

2.3

Lokale Operationen

25

Anmerkung 2.3.1

Die lineare Faltung berechnet die Werte gF (i, j) des Ausgabebildes aus den Werten einer (rechteckigen) Umgebung des Punktes (i, j) des Eingabebildes GE . Die Eigenschaften der Faltungsoperation werden durch den Faltungskern H = (h(i , j  )) bestimmt. In der Bildverarbeitung nehmen wir an, dass L und M wesentlich kleiner als die Zeilen- und Spaltenl¨ ange des Bildes sind. In einigen F¨ allen k¨ onnen L und M auch gerade nat¨ urliche Zahlen sein (siehe Beispiel 2.16). Dann kann man die Gleichung (2.3) sinngem¨aß ebenfalls anwenden. Die Lage des Bezugspunktes (0, 0) in der Matrix muss man dann allerdings noch festlegen. Bei Anwendung der Gleichung (2.3) auf randnahe Bildbereiche treten Indizes auf, die Bildpunkte außerhalb des Bildes GE = (gE (i, j)) ansprechen. Es gibt eine Reihe von Verfahren, wie Zeilen- und Spaltenwiederholung, Bildspiegelung usw., um diesen Punkten geeignete Werte zuzuweisen. Eine exakte mathematische Definition der Faltung ist nur f¨ ur diskrete zweidimensionale Funktionen m¨ oglich, deren Definitionsbereich die gesamte Menge Z der ganzen Zahlen ist. Wir werdem im Abschnitt 2.4.4 noch einmal darauf zur¨ uckkommen. Wir betrachten im Folgenden nur kleine Werte f¨ ur L und M . In der Praxis sind oft gr¨ oßere Werte u ¨blich. 2.3.2 Lineare Faltung und Tiefpassfilter Tiefpassfilter dienen zur Gl¨ attung der Grauwerte. Durch Tiefpassfilterung k¨ onnen Bildst¨ orungen (z.B. Rauschen) beseitigt werden. Allerdings werden dabei auch scharfe Kanten oder d¨ unne Linien mitgegl¨attet. Das Bild wirkt unsch¨ arfer (Abb. 2.6). Ein Tiefpassfilter verst¨ arkt tiefe Ortsfrequenzen, hohe Ortsfrequenzen werden unterdr¨ uckt. Gleichm¨ aßig helle Bildteile bleiben unver¨andert, w¨ahrend ¨ pl¨ otzliche Hell-Dunkel-Uberg¨ ange (Kanten) verschmiert werden. Beispiel 2.5: Mittelwertoperation

Sei L = M = 3 und die Matrix (H =)HM

2.5

⎛ ⎞ 111 1 = ⎝1 1 1⎠ 9 111

der Faltungskern.

sUppLex

26

2. Bildverarbeitung

Hier gilt: gF (i, j) =

1 1 1   gE (i − l, j − m) 9 m=−1 l=−1

Der Operator HM ∗ GE heißt Mittelwertoperation.

Abb. 2.6. Mittelwertoperator

Die einfache Mittelwertbildung reicht in vielen F¨allen nicht aus. Besser ist es, die Werte der Faltungsmatrix zu wichten. Eine einfache M¨ oglichkeit ist die Benutzung der Binomialkoeffizienten. Diese tragen wir in die erste und letzte Zeile bzw. Spalte ein. Die Werte der Elemente im Innern der Matrix sind dann das Produkt der Zahlen am linken und oberen Rand. 2.6

Beispiel 2.6: Binomialoperation

W¨ ahlt man die Binomialkoeffizienten  2 , k = 0, 1, 2 k so erh¨ alt man die Matrix

HB1

2.7

⎛ ⎞ 121 1 ⎝ = 2 4 2⎠ . 16 121

Beispiel 2.7: Binomialoperation

Benutzt man

 4 , k

k = 0, 1, 2, 3, 4

so erh¨ alt man die Matrix

sUppLex

2.3

Lokale Operationen

27

HB 2

⎛ 1 ⎜4 1 ⎜ ⎜6 = 256 ⎜ ⎝4 1

4 16 24 16 4

6 24 36 24 6

4 16 24 16 4

⎞ 1 4⎟ ⎟ 6⎟ ⎟ 4⎠ 1

2.3.3 Lineare Faltung mit der Gaußverteilung Hier benutzen wir die zweidimensionale Gaußsche Normalverteilung. G(x) =

1

1

2π · det(Σ)

1 2

Dabei sei

· e− 2 (x−μ)

T

Σ−1 ( x−μ)

 x , y

x =

μ der Mittelwertvektor und Σ die Kovarianzmatrix. Wir w¨ ahlen speziell μ=

 0 0

und  σ 0 Σ= . 0σ Dann erhalten wir: G(x) = G(x, y) =

2 2 1 1 · e− 2·σ2 (x +y ) 2π · σ

Eine geeignete Diskretisierung f¨ uhrt zu folgenden 2 einfachen Faltungsmatrizen:

sUppLex

28

2.8

2. Bildverarbeitung

Beispiel 2.8: Gaußoperation

⎛

HG1

2.9

⎞ 131 1 ⎝ = 3 8 3⎠ 24 131

Beispiel 2.9: Gaußoperation

⎛

HG2

1 ⎜3 1 ⎜ ⎜5 = 245 ⎜ ⎝3 1

3 15 24 15 3

5 24 41 24 5

3 15 24 15 3

⎞ 1 3⎟ ⎟ 5⎟ ⎟ 3⎠ 1

Hier gibt es zahlreiche andere Varianten. Gaußoperationen werden vielf¨ altig benutzt. Eine aktuelle Anwendung ist die Berechnung von SIFT-Merkmalen. Hier berechnet man Differenzen von Gaußoperationen (DoG-Filter) mit σ Werten, die sich um einen geeigneten Faktor k unterscheiden. Die Grundidee wird in [34] dargestellt. Diese Merkmale besitzen z.B. in der autonomem mobilen Robotik eine große Bedeutung bei der Erkennung von Landmarken. 2.3.4 Lineare Faltung und Kanten Diese Operatoren nennt man auch Hochpassfilter. Sie unterdr¨ ucken tiefe Ortsfrequenzen, hohe werden verst¨ arkt. Dadurch verschwinden gleichm¨aßig helle Bildteile. Bildbereiche, wo benachbarte Bildpunkte verschiedene Grauwerte aufweisen, werden betont. Deshalb kann man damit Kanten hervorheben. ¨ Dazu benutzen wir eine sinnvolle Ubertragung der Berechnung der ersten partiellen Ableitung auf diskrete Funktionen. Ist s(x, y) eine stetige Funktion zweier Ver¨anderlicher, so sind die ersten partiellen Ableitungen von s(x, y) nach x bzw. y definiert als s(x + Δx, y) − s(x, y) ∂s(x, y) = lim Δx→0 ∂x Δx

sUppLex

2.3

Lokale Operationen

29

∂s(x, y) s(x, y + Δy) − s(x, y) = lim Δy→0 ∂y Δy Die sinngem¨ aßen Differenzenbildungen bei einer Funktion g(i, j) mit diskreten i und j lauten ( Δi = Δj = 1 ): g(i + 1, j) − g(i, j) = g(i + 1, j) − g(i, j) i+1−i g(i, j + 1) − g(i, j) = g(i, j + 1) − g(i, j) j+1−j Damit ergeben sich die beiden folgenden einfachen Faltungskerne (wieder ist L = M = 3): Beispiel 2.10

2.10

⎛ 0 Hz = ⎝0 0 ⎛ 0 Hs = ⎝1 0

⎞ 0 0⎠ 0 ⎞ 0 0 −1 0⎠ 0 0 1 −1 0

Die Werte des Ausgabebildes GA berechnen sich zu gA (i, j) =

1 1  

hz (l, m) · gE (i − l, j − m) = gE (i + 1, j) − gE (i, j)

l=−1 m=−1

bzw. gA (i, j) =

1 1  

hs (l, m) · gE (i − l, j − m) = gE (i, j + 1) − gE (i, j).

l=−1 m=−1

Hz findet vorzugsweise horizontale Kanten und Hs vertikale Kanten. Dies ist die einfachste Form zur Hervorhebung von Grauwertkanten. Eine andere M¨ oglichkeit zur Darstellung der ersten Ableitungen sind die Differenzen g(i − 1, j) − g(i, j) g(i, j − 1) − g(i, j) und damit die Faltungskerne.

sUppLex

30

2.11

2. Bildverarbeitung

Beispiel 2.11

⎛ 0 Hz1 = ⎝0 0 ⎛ 0 Hs1 = ⎝0 0

⎞ 0 0⎠ 0 ⎞ 0 0 −1 1⎠ 0 0 0 −1 1

Die Werte des Ausgabebildes GA berechnen sich hier zu gA (i, j) =

1 1  

h1z (l, m) · gE (i − l, j − m) = gE (i − 1, j) − gE (i, j)

l=−1 m=−1

bzw. gA (i, j) =

1 1  

h1s (l, m) · gE (i − l, j − m) = gE (i, j − 1) − gE (i, j).

l=−1 m=−1

Hz1 findet vorzugsweise horizontale Kanten und Hs1 vertikale Kanten (siehe Abb. 2.7).

Hz1

Hs1

Abb. 2.7. Kantenhervorhebung mit einfachen Differenzen

sUppLex

2.3

Lokale Operationen

31

Eine weitere M¨ oglichkeit bilden die symmetrischen Differenzen g(i + 1, j) − g(i − 1, j) g(i, j + 1) − g(i, j − 1) und damit die Faltungskerne. Beispiel 2.12

2.12

⎛ 0 HzS = ⎝0 0 ⎛ 0 HsS = ⎝1 0

⎞ 1 0 0 0⎠ −1 0 ⎞ 0 0 0 −1⎠ 0 0

Die Werte des Ausgabebildes GA berechnen sich hier zu gA (i, j) =

1 1  

hSz (l, m) · gE (i − l, j − m) = gE (i + 1, j) − gE (i − 1, j)

l=−1 m=−1

bzw. gA (i, j) =

1 1  

hSs (l, m) · gE (i − l, j − m) = gE (i, j + 1) − gE (i, j − 1).

l=−1 m=−1

HzS findet vorzugsweise horizontale Kanten und HsS vertikale Kanten Diese einfachen Kantendetektoren kann man nat¨ urlich noch auf viele Arten verallgemeinern. Beispiel 2.13: Sobeloperation

2.13

Sei L = M = 3 und

⎛

HSz

H Ss

⎞ 1 2 1 =⎝ 0 0 0 ⎠ −1 −2 −1 ⎛ ⎞ 1 0 −1 = ⎝2 0 −2⎠ . 1 0 −1

sUppLex

32

2. Bildverarbeitung

Hier wird eine Differenzbildung jeweils zur u ¨bern¨achsten Zeile (Spalte) durchgef¨ uhrt. Kleine St¨ orungen benachbarter Zeilen (Spalten) gehen nicht in das Ergebnis ein (Abb. 2.8).

H Sz

H Ss

Abb. 2.8. Kantenhervorhebung mit der Sobel-Operation

Es gibt zahlreiche Faltungsoperationen, die Kanten in bestimmten Richtungen filtern. 2.14

Beispiel 2.14: Filtern von Kanten in einer Vorzugsrichtung

Sei wieder L = M = 3. Ostwest-Richtung (horizontal): ⎛

HOW Nordost-Richtung:

⎞ 1 1 1 = ⎝ 1 −2 1 ⎠ −1 −1 −1 ⎛

HNO

⎞ 1 1 1 = ⎝−1 −2 1⎠ −1 −1 1

sUppLex

2.3

Lokale Operationen

33

Nords¨ ud-Richtung (vertikal): ⎛

HNS

⎞ −1 1 1 = ⎝−1 −2 1⎠ −1 1 1

S¨ udost-Richtung: ⎛

HSO

⎞ −1 −1 1 = ⎝−1 −2 1⎠ 1 1 1

HOW

HNS

HNO

Abb. 2.9. Kantenhervorhebung in einer Vorzugsrichtung

Die folgende Operation ist richtungsunabh¨ angig. Beispiel 2.15: Laplace-Operation

Sei L = M = 3 und

2.15

⎛

⎞ 0 −1 0 HL = ⎝−1 4 −1⎠ 0 −1 0

sUppLex

34

2. Bildverarbeitung

Diese Faltungsmatrix heißt Laplace-Operator. Er hebt Grauwertdifferenzen hervor und dient somit ebenfalls zur Bestimmung von Kanten. Der Laplace-Operator kann mit Hilfe der zweiten partiellen Ableitungen interpretiert werden. F¨ ur stetige Funktionen s(x, y) ist der Laplace-Operator wie folgt definiert: Δs =

∂ 2 s(x, y) ∂ 2 s(x, y) + ∂x2 ∂y 2

Im diskreten Fall erhalten wir: ∂[g(i + 1, j) − g(i, j)] ∂ 2 g(i, j) (Beispiel 2.10) = ∂i2 ∂i = (g(i, j) − g(i + 1, j)) − (g(i − 1, j) − g(i, j))

(Beispiel 2.11)

= −g(i − 1, j) − g(i + 1, j) + 2g(i, j) ∂ g(i, j) ∂[g(i, j + 1) − g(i, j)] = 2 ∂j ∂j = (g(i, j) − g(i, j + 1) − (g(i, j − 1) − g(i, j)) 2

= −g(i, j − 1) − g(i, j + 1) + 2g(i, j) Δg = 4g(i, j) − g(i − 1, j) − g(i, j − 1) − g(i + 1, j) − g(i, j + 1) Die letzte Gleichung f¨ uhrt zu den angegebenen Werten der Matrix HL . Modifikationen sind ⎛ ⎞ −1 −1 −1 HL1 = ⎝−1 8 −1⎠ oder −1 −1 −1 ⎛ ⎞ 1 −2 1 HL2 = ⎝−2 4 −2⎠ . 1 −2 1 Diese Operatoren finden Kanten in beliebiger Richtung (Abbbildung 2.10).

Abb. 2.10. Kantenhervorhebung mit der Laplace-Operation

sUppLex

2.3

Lokale Operationen

35

Der folgende Operator ist sehr einfach und benutzt eine 2 × 2 Umgebung, ist also nicht symmetrisch bez¨ uglich des Punktes (i, j). Beispiel 2.16: Roberts-Operation

2.16

Wir verwenden die beiden folgenden Faltungskerne:  0 1 1 HR = −1 0 Der Bezugspunkt liegt rechts oben. Damit gilt gA (i, j) = gE (i, j) − gE (i − 1, j + 1).  2 HR =

−1 0 0 1



Der Bezugspunkt liegt rechts unten. Damit gilt gA (i, j) = gE (i, j) − gE (i + 1, j + 1). Diese Operationen filtern Kanten vorzugsweise in den beiden diagonalen Richtungen. 2.3.5 Separierbarkeit der linearen Faltung Die Faltung mit gr¨oßeren Matrizen kann oft auf die Hintereinanderausf¨ uhrung mit einfacheren Faltungskernen zur¨ uckgef¨ uhrt werden. Beispiel 2.17 Sei

⎛

H=

111 1⎝ 1 1 1⎠ 9 111

H1 = und

2.17

⎞

 1 111 3

⎛ ⎞ 1 1⎝ ⎠ H2 = 1 . 3 1

Dann gilt H2 ∗ (H1 ∗ G) = H1 ∗ (H2 ∗ G) = H ∗ G.

(2.4)

sUppLex

36

2. Bildverarbeitung

Ein weiteres Beispiel ist die Binomialoperation (Beispiel 2.6). 2.18

Beispiel 2.18 Sei

HB

⎛ ⎞ 121 1⎝ = 2 4 2⎠ 9 121

H1B = und H2B

 1 121 3

⎛ ⎞ 1 1⎝ ⎠ = 2 . 3 1

Dann gilt H2B ∗ (H1B ∗ G) = H1B ∗ (H2B ∗ G) = H B ∗ G.

(2.5)

Auch die Gaußoperation (Abschnitt 2.3.3) ist separierbar. 2.3.6 Gradient und Kanten Der Gradient stellt eine weitere M¨ oglichkeit f¨ ur die Untersuchung der lokalen Grauwertverteilung dar und kann deshalb auch zur Filterung von Kanten benutzt werden. Ist s(x, y) eine stetige Funktion zweier Ver¨anderlicher, so ist er definiert durch:  grad(s) = Wir ben¨ otigen den Betrag | grad(s)| =



∂s ∂s ∂x ∂y

∂s ∂x

T

2

 +

∂s ∂y

2

dieses Vektors. Wir k¨ onnen nun 2 Faltungskerne, die Kanten in aufeinaner senkrecht stehenden Richtungen filtern, kombinieren. Dadurch approximieren wir die beiden partiellen Ableitungen.

sUppLex

2.3

Lokale Operationen

37

Beispiel 2.19: Gradientsobel

2.19

Sei HSz = (hz (i, j)) HSs = (hs (i, j))

mit

i, j = −1, 0, 1

(siehe Beispiel 2.13)

und L−1

g1 (i, j) =

2 

M −1 2



hz (l, m) · gE (i − l, j − m)

l=− L−1 m=− M2−1 2 L−1

g2 (i, j) =

2 

M −1 2



hs (l, m) · gE (i − l, j − m).

l=− L−1 m=− M2−1 2

Dann berechnen wir das Ausgabebild GA folgendermaßen:  gA (i, j) = (g1 (i, j))2 + (g2 (i, j))2 Man kann auch die beiden Roberts-Operationen (siehe Beispiel 2.16) nehmen. Mit dem Gradientenfilter haben wir somit einen richtungsunabh¨angigen Operator, der allerdings nicht linear ist. Oft wird in der Bildverarbeitung auch die Richtung des Gradienten benutzt. Definition 2.7: lokale Strukturmatrix

2.7

Sei Gz = HzS ∗ GE = (gz (i, j)) und Gs = HsS ∗ GE = (gs (i, j)) (siehe Beispiel 2.12). Die Matrix  a(i, j) c(i, j) m(i, j) = . c(i, j) b(i, j) heißt lokale Strukturmatrix im Punkt (i, j). Dabei ist A = G2z = (a(i, j)) B = G2s = (b(i, j)) C = Gz · Gs = (c(i, j)). Die Eigenwerte der Matrix m(i, j) sind λ1 (i, j) = a(i, j) + b(i, j) λ2 (i, j) = 0.

sUppLex

38

2. Bildverarbeitung

Der von 0 verschiedene Eigenwert gibt also die St¨arke der Grauwert¨anderung an der Stelle (i, j) an. Der Eigenvektor zum Eigenwert λ1 (i, j) ist gleich  a(i, j) x(i, j) =  b(i, j) und entspricht damit dem Gradienten. 2.3.7 Rangfolgeoperationen Rangfolgeoperationen basieren darauf, dass die Bildwerte der N Bildpunkte des Eingabebildes GE in einer vorgegebenen lokalen Umgebung U zu einem Bildpunkt (i, j) in aufsteigender Reihenfolge gmin = g0 ≤ g1 ≤ · · · ≤ gN −2 ≤ gN −1 = gmax sortiert werden. 2 2 3 1 1 4

2 3 3 3 5 3

3 4 3 5 6 5

4 5 4 8 9 7

4 5 7 9 8 7

5 6 6 9 7 8

3 4 5 3 3 4 3 5 8 Sortieren 3 3 3 3 4 4 5 5 8

Min

Median

Max

Abb. 2.11. Arbeitsweise der Rangfolgeoperationen

Je nachdem, durch welches Element gi (i = 0, . . . , N −1) der geordneten Folge, der Bildpunkt gE (i, j) ersetzt wird, ergeben sich unterschiedliche Operationen (Abb. 2.11 und 2.12).

sUppLex

2.3

Lokale Operationen

39

Definition 2.8: Minimaloperation

2.8

gA (i, j) = gmin = min {gE (i, j)} (i,j)∈U

U – vorgegebene Umgebungsmenge

Er entfernt Spitzen hoher Grauwerte, ohne ein unscharfes Gesamtbild zu erzeugen, aber vergr¨ oßert die Flecken niedriger Grauwerte. Definition 2.9: Maximaloperation

2.9

gA (i, j) = gmax = max {gE (i, j)} (i,j)∈U

Er entfernt kleine Flecken sehr niedriger Grauwerte, aber er vergr¨oßert die Spitzen hoher Grauwerte. Definition 2.10: Medianoperation

2.10

gA (i, j) = g[ N ] N  2

2

– ganzzahliger Teil von

N 2.

Entfernt punktf¨ ormige Gebilde (hohe bzw. sehr niedrige Grauwerte) ohne ein unscharfes Bild zu erzeugen. Der Medianoperator hat gegen¨ uber dem Tiefpassfilter den Vorteil, dass im Ausgabebild keine neuen Grauwerte entstehen. Kanten bleiben sch¨arfer erhalten als beim Tiefpassfilter. D¨ unne Linien k¨onnen allerdings ganz verschwinden. 2.3.8 Auffinden von Eckpunkten Wir beschreiben hier den Harris-Operator zur Eckendetektion [19]. Ausgangspunkt ist die lokale Strukturmatrix m(i, j) aus Abschnitt 2.3.6. Die Matrizen A, B und C werden mit einem Gaußoperator H G gegl¨attet. Also A = H G ∗ A = (a(i, j)) B = H G ∗ B = (b(i, j)) C = H G ∗ C = (c(i, j)).

sUppLex

40

2. Bildverarbeitung

Abb. 2.12. Rangfolgeoperationen

Dann betrachten wir die Matrix m(i, j) =

 a(i, j) c(i, j) . c(i, j) b(i, j).

Die Eigenwerte sind λ1,2

spur(m) ± = 2



spur(m)2 − det(m), 4

wobei spur(m) = a + b. Die Argumente i und j haben wir der Einfachheit weggelassen. Falls beide Eigenwerte gr¨ oßer als Null sind an der Stelle (i, j), deutet dies auf einem Eckpunkt hin. Davon ausgehend betrachtet der Harris Detektor die Funktion Q(i, j) = det(m(i, j)) − α · (spur(m(i, j)))2 .

sUppLex

2.3

Lokale Operationen

41

Falls Q(i, j) > T , liegt ein Kandidat f¨ ur einen Eckpunkt vor (T ≈ 25000). F¨ ur α kann man 0.05 w¨ ahlen. 2.3.9 Aufgaben Aufgabe 2.3.1 Sei

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 1 1 1 1 1 1 0

0 2 2 2 2 2 2 0

0 3 3 100 3 3 3 0

0 3 3 3 3 3 3 0

0 2 2 2 2 2 2 0

0 1 1 1 1 1 1 0

⎞

2.3.1

0 0⎟ ⎟ 0⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

das Eingabebild. Berechnen Sie die Mittelwertoperation HM ∗ GE (siehe Beispiel 2.5) und interpretieren Sie das Ergebnis. Aufgabe 2.3.2 Sei

⎛

0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

⎞ 30 30⎟ ⎟ 30⎟ ⎟ ⎟ 30⎟ ⎟ 30⎟ ⎟ 30⎟ ⎟ 30⎠ 30

2.3.2

das Eingabebild. Berechnen Sie die Mittelwertoperation HM ∗ GE (siehe Beispiel 2.5) und interpretieren Sie das Ergebnis.

sUppLex

42

2.3.3

2. Bildverarbeitung

Aufgabe 2.3.3 Sei

⎛

30 ⎜30 ⎜ ⎜30 ⎜ ⎜ ⎜30 GE = ⎜ ⎜30 ⎜ ⎜30 ⎜ ⎝30 30

30 30 30 30 30 30 30 30

0 0 0 0 0 0 0 0

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

0 0 0 0 0 0 0 0

30 30 30 30 30 30 30 30

⎞ 30 30⎟ ⎟ 30⎟ ⎟ ⎟ 30⎟ ⎟ 30⎟ ⎟ 30⎟ ⎟ 30⎠ 30

das Eingabebild. Berechnen Sie die Mittelwertoperation HM ∗ GE (siehe Beispiel 2.5) und interpretieren Sie das Ergebnis. 2.3.4

Aufgabe 2.3.4 Sei

⎛

0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 1 1 1 1 1 1 0

0 2 2 2 2 2 2 0

0 3 3 100 3 3 3 0

0 3 3 3 3 3 3 0

0 2 2 2 2 2 2 0

0 1 1 1 1 1 1 0

⎞ 0 0⎟ ⎟ 0⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

das Eingabebild. Wenden Sie auf dieses Bild die Medianoperation an (siehe Abschnitt 2.3.7) und interpretieren Sie das Ausgabebild. Vergleichen Sie das Ergebnis mit Aufgabe 2.3.1. 2.3.5

Aufgabe 2.3.5 Sei

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

30 30 30 30 30 30 30 30

⎞ 30 30⎟ ⎟ 30⎟ ⎟ ⎟ 30⎟ ⎟ 30⎟ ⎟ 30⎟ ⎟ 30⎠ 30

das Eingabebild. Wenden Sie auf dieses Bild die Medianoperation an (siehe Abschnitt 2.3.7) und interpretieren Sie das Ausgabebild.

sUppLex

2.3

Lokale Operationen

43

Vergleichen Sie das Ergebnis mit Aufgabe 2.3.2. Aufgabe 2.3.6 Sei

⎛ 20 ⎜20 ⎜ ⎜20 ⎜ ⎜ ⎜20 GE = ⎜ ⎜20 ⎜ ⎜20 ⎜ ⎝20 20

20 20 20 20 20 20 20 20

20 20 20 20 20 20 20 20

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

⎞

2.3.6

0 0⎟ ⎟ 0⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

das Eingabebild. Wenden Sie auf dieses Bild die Kantenfilter Hz1 ∗ GE und Hs1 ∗ GE (siehe Beispiel 2.11) an und interpretieren Sie die Ausgabebilder. Aufgabe 2.3.7 Sei

2.3.7

⎛ 20 ⎜20 ⎜ ⎜20 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

⎞ 20 20⎟ ⎟ 20⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

das Eingabebild. Wenden Sie auf dieses Bild die Kantenfilter Hz1 ∗ GE und Hs1 ∗ GE (siehe Beispiel 2.11) an und interpretieren Sie die Ausgabebilder.

sUppLex

44

2.3.8

2. Bildverarbeitung

Aufgabe 2.3.8 Sei

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

20 20 20 20 20 20 20 20

20 20 20 20 20 20 20 20

⎞ 20 20⎟ ⎟ 20⎟ ⎟ ⎟ 20⎟ ⎟ 20⎟ ⎟ 20⎟ ⎟ 20⎠ 20

das Eingabebild. Wenden Sie auf dieses Bild die Kantenfilter Hz1 ∗ GE und Hs1 ∗ GE (siehe Beispiel 2.11) an und interpretieren Sie die Ausgabebilder. 2.3.9

Aufgabe 2.3.9 Sei

⎛

0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

20 20 20 20 20 20 20 20

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

⎞ 0 0⎟ ⎟ 0⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

das Eingabebild. Wenden Sie auf dieses Bild die Kantenfilter Hz1 ∗ GE und Hs1 ∗ GE (siehe Beispiel 2.11) an und interpretieren Sie die Ausgabebilder.

sUppLex

2.3

Lokale Operationen

Aufgabe 2.3.10 Sei

45

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

20 20 20 20 20 20 20 20

20 20 20 20 20 20 20 20

⎞

2.3.10

20 20⎟ ⎟ 20⎟ ⎟ ⎟ 20⎟ ⎟ 20⎟ ⎟ 20⎟ ⎟ 20⎠ 20

das Eingabebild. Wenden Sie auf dieses Bild den Kantenfilter HsS ∗ GE (siehe Beispiel 2.12) an und interpretieren Sie das Ergebnis. Aufgabe 2.3.11 Sei

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

20 20 20 20 20 20 20 20

20 20 20 20 20 20 20 20

⎞

2.3.11

20 20⎟ ⎟ 20⎟ ⎟ ⎟ 20⎟ ⎟ 20⎟ ⎟ 20⎟ ⎟ 20⎠ 20

das Eingabebild. Berechnen Sie die Laplaceoperation HL ∗ GE (siehe Beispiel 2.15) und interpretieren Sie das Ergebnis. Aufgabe 2.3.12 Sei

2.3.12

⎛ 20 ⎜20 ⎜ ⎜20 ⎜ ⎜ ⎜0 GE = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

20 20 20 0 0 0 0 0

⎞ 20 20⎟ ⎟ 20⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

sUppLex

46

2. Bildverarbeitung

das Eingabebild. Berechnen Sie die Laplaceoperation HL ∗ GE (siehe Beispiel 2.15) und interpretieren Sie das Ergebnis. 2.3.13

¨ Aufgabe 2.3.13 Uberpr¨ ufen Sie die Gleichung (2.4) aus Beispiel 2.17.

2.3.14

¨ Aufgabe 2.3.14 Uberpr¨ ufen Sie die Gleichung (2.5) aus Beispiel 2.18.

2.3.15

Aufgabe 2.3.15 Finden Sie Verallgemeinerungen der Gleichungen (2.4) und

(2.5). 2.3.16

Aufgabe 2.3.16 Untersuchen Sie den Harris-Operator zur Eckendetektion (Abschnitt 2.3.8) f¨ ur das Eingabebild ⎛ ⎞ 00000000 ⎜0 0 0 0 0 0 0 0⎟ ⎜ ⎟ ⎜0 0 1 1 1 1 1 0⎟ ⎜ ⎟ ⎜ ⎟ ⎜0 0 1 1 1 1 1 0⎟ GE = ⎜ ⎟ ⎜0 0 1 1 1 1 1 0⎟ ⎜ ⎟ ⎜0 0 1 1 1 1 1 0⎟ ⎜ ⎟ ⎝0 0 0 0 0 0 0 0⎠ 00000000

2.4

2.4 Globale Operationen Wir behandeln nur eine globale Operation, die Fourier-Transformierte. Eine andere wichtige Transformation sind Wavelets, auf die wir aber nicht weiter eingehen. Gute Darstellungen findet man in [5] und [14].

2.4.1 Grundidee Wenn man ein Berechnungsproblem zu l¨ osen hat, das ein bestimmtes mathematisches Objekt X betrifft, ist es manchmal m¨oglich, X in ein anderes Objekt zu transformieren und ein (verwandtes) Problem mit dem neu transformierten Objekt zu l¨ osen.

sUppLex

2.4

Globale Operationen

47

Beispiel 2.20 Seien X und Y reelle Zahlen. Um das Produkt X · Y zu berech-

2.20

nen, betrachtet man die Logarithmen von X und Y . Diese braucht man dann nur zu addieren und die R¨ ucktransformation ergibt das gesuchte Produkt. Transformation: X −→ log X = XT Y −→ log Y = YT Addition: XT + YT = ZT R¨ ucktransformation: ZT −→ Z = X · Y Wenn X eine reellwertige Funktion ist, dann ist es bei bestimmten Problemen sinnvoll, die Fourier-Transformierte von X zu nehmen, bevor man fortf¨ahrt. Diese Idee wird bei der Bildverarbeitung oft benutzt. 2.4.2 Diskrete zweidimensionale Fouriertransformation Sei QIJ die Menge aller I · J-Matrizen, wobei die Elemente einer Matrix auch komplexe Zahlen sein k¨ onnen, d.h.: A ∈ QIJ i = 0, . . . , I − 1;

⇒

A = (a(i, j))

j = 0, . . . , J − 1;

C – komplexe Zahlen

a(i, j) ∈ C

(z = a + b · i)

Wir benutzen hier i sowohl als Zeilenindex als auch f¨ ur die komplexe Zahl √ orige Bedeutung aber immer klar. i = −1. Aus dem Kontext wird die zugeh¨ QIJ wird zu einem linearen Raum (Vektorraum) u ¨ber dem K¨orper C der komplexen Zahlen, wenn die u ¨bliche Addition von 2 Matrizen und die Multiplikation einer komplexen Zahl mit einer Matrix eingef¨ uhrt werden. Addition: S = (s(i, j));

T = (t(i, j))

⇒

S + T = (s(i, j) + t(i, j))

Multiplikation: a ∈ C;

S = (s(i, j))

⇒

a · S = (a · s(i, j)

sUppLex

48

2. Bildverarbeitung

Schließlich definieren wir noch ein Skalarprodukt I−1 J−1 1  s(i, j) · t∗ (i, j), I · J i=0 j=0

S, T  =

wobei mit t∗ (i, j) die konjugiert komplexe Zahl zu t(i, j) bezeichnet wird. Wenn z =a+b·i∈C dann ist z ∗ = a − b · i. arer Raum u Damit ist QIJ ein unit¨ ¨ber dem K¨orper C der komplexen Zahlen. Die Elemente S von QIJ sind als Linearkombinationen von M = I · J linear unabh¨ angigen Basismatrizen   B (u,v) = b(i, j)(u,v) u = 0, . . . , I − 1;

v = 0, . . . , J − 1

(einer Basis) darstellbar, d.h.:

s(i, j) =

I−1 J−1  

f (u, v) · b(i, j)(u,v)

u=0 v=0

i = 0, . . . , I − 1;

j = 0, . . . , J − 1;

f (u, v) ∈ C

f¨ ur alle

u, v

Eine Basis heißt orthonormiert, falls:  B

2.1

(u1 ,v1 )

,B

(u2 ,v2 )



 =

0 1

falls

(u1 , v1 ) = (u2 , v2 ) (u1 , v1 ) = (u2 , v2 )

Satz 2.1 Die Matrizen

  jv iu B (u,v) = e2πi( I + J )

mit

u = 0, . . . , I − 1;

sind linear unabh¨ angig und orthonormiert (i = im Raum QIJ .

v = 0, . . . , J − 1

(2.6)

√ −1) und bilden eine Basis

sUppLex

2.4

Globale Operationen

49

Beispiel 2.21 Sei I = J = 2. Dann erhalten wir

B (0,0) =

 1 1  1 = 1

1 1

B (0,1)

eiπ eiπ



2.21



1 −1 1 −1

=



(wegen eiπ = cos(π) + i · sin(π) = −1) 

1 −1  1 = −1

B (1,0) = B (1,1)

1 −1 −1 . 1

F¨ ur die lineare Unabh¨ angigkeit ist zu zeigen:

a · B (0,0) + b · B (0,1) + c · B (1,0) + d · B (1,1) =

 00 00

⇒

a=b=c=d=0

Die folgende einfache Rechnung zeigt die lineare Unabh¨angigkeit der obigen 4 Basismatrizen:

a+b+c+d=0 a−b+c−d=0 a+b−c−d=0 a−b−c+d=0

a+c=0 a+b=0 a+d=0

⇒

a−a−a−a=0

⇒

a=0

⇒

c=b=d=0

Die Basis ist auch orthonomiert, z.B. gilt:  1  B (0,1) , B (0,1) = (1 · 1 + (−1)(−1) + 1 · 1 + (−1)(−1)) = 1 4   1 (0,1) (1,0) B = (1 · 1 + (−1) · 1 + 1 · (−1) + (−1)(−1)) = 0 ,B 4

sUppLex

50

2.2

2. Bildverarbeitung

Jede I · J-Matrix S = (s(i, j)) kann als Linearkombination der Basismatrizen (2.6) dargestellt werden, d.h., Satz 2.2

s(i, j) =

I−1 J−1  

f (u, v) · e2πi(

j·v i·u I + J

)

(2.7)

u=0 v=0

mit

i = 0, . . . , I − 1;

j = 0, . . . , J − 1.

Die Linearfaktoren f (u, v) ∈ C berechnen sich aus

f (u, v) =

mit Damit gilt

2.11

I−1 J−1 j·v i·u 1  s(i, j) · e−2πi( I + J ) I · J i=0 j=0

u = 0, . . . , I − 1;

(2.8)

v = 0, . . . , J − 1.

  f (u, v) = S, B (u,v) .

Definition 2.11: Fouriertransformation

Gleichung (2.8) wird als diskrete, zweidimensionale Fouriertransformation und Gleichung (2.7) als inverse, diskrete, zweidimensionale Fouriertransformation bezeichnet. Die Matrizen S = (s(i, j)) und F = (f (u, v)) sind ein Fouriertransformationspaar und F heißt die Fouriertransformierte von S. Wir benutzen die Bezeichnung F = F T (S). 2.22

Beispiel 2.22 Sei I = J = 2 und

 S=

12 . 34

Dann ist

 F = (f (u, v)) =

− 12 −1 0 5 2

,

wegen    1 5 12 11 f (0, 0) = , = (1 + 2 + 3 + 4) = 34 11 4 2

sUppLex

2.4

Globale Operationen

51



  1 1 12 1 −1 , = (1 − 2 + 3 − 4) = − 34 1 −1 4 2

f (0, 1) =  f (1, 0) =

  1 12 1 1 , = (1 + 2 − 3 − 4) = −1 34 −1 −1 4

 f (1, 1) =

  1 12 1 −1 , = (1 − 2 − 3 + 4) = 0. 34 −1 1 4

Wir erweitern nun die Definition der Fouriertransformation auf die gesamte diskrete zweidimensionale Ebene. Definition 2.12 Mit QZ IJ bezeichnen wir die Menge aller Funktionen

S : Z × Z → C S  = (s (i, j))

mit

2.12

(Z – ganze Zahlen),

i, j = . . . , −2, −1, 0, 1, 2, . . .

mit folgenden Eigenschaften: ∃I, J ∈ {1, 2, . . . } mit

∀a, b ∈ Z

s (a · I + i, b · J + j) = s (i, j)

und ∀i ∈ {0, . . . , I − 1} und ∀j ∈ {0, . . . , J − 1}

Die Funktionen aus QZ IJ sind periodisch in i- und j-Richtung mit den Perioden I bzw. J. Definition 2.13: periodische Fortsetzung

2.13

Sei S ∈ QIJ ;

S = (s(i, j)).

Wir konstruieren eine Funktion S  = (s (i, j)) : Z × Z → C

(d.h. S  ∈ QZ IJ )

sUppLex

52

2. Bildverarbeitung

mit: s (a · I + i, b · J + j) = s(i, j)

i = 0, . . . , I − 1;

j = 0, . . . , J − 1;

a, b ∈ Z

S  heißt periodische Fortsetzung (Erweiterung) von S. 2.14

Definition 2.14

Sei S  ∈ QZ IJ . S ∈ QIJ definieren wir durch s(i, j) := s (i, j)

f¨ ur

i = 0, . . . , I − 1;

j = 0, . . . , J − 1.

F = (f (u, v)) sei die F T von S = (s(i, j)). Dann definieren wir die F T F : Z × Z → C

(F  = (f  (u, v)))

von S  durch: f  (a · I + u, b · J + v) = f (u, v)

u = 0, . . . , I − 1;

v = 0, . . . , J − 1;

a, b ∈ Z.

Es gilt also F  ∈ QZ IJ . 2.4.3 Anwendung der Fouriertransformation in der Bildverarbeitung Eine Bildmatrix G = (g(i, j)) mit I Bildzeilen und J Bildspalten ist ein onnen auf Bilder die Transformationen (2.7) Element der Menge QIJ . Damit k¨ und (2.8) angewendet werden. F¨ ur die bildliche Darstellung von F = (f (u, v)) verwendet man dann den Betrag |f (u, v)| =

 p2 (u, v) + t2 (u, v).

Manchmal benutzt man auch die Gr¨ oßen  ln |f (u, v)| ,

2

|f (u, v)| ,

φ(u, v) = arctan

t(u, v) p(u, v)

.

sUppLex

2.4

Globale Operationen

53

Dabei ist f (u, v) = p(u, v) + i · t(u, v). Die komplexen Zahlen f (u, v) heißen Ortsfrequenzen und |f (u, v)| heißt Fourierspektrum oder Spektrum der Ortsfrequenzen. Manche Eigenschaften eines Bildes k¨ onnen mit Hilfe der Frequenzen f (u, v) besser erkannt werden. Die Ortsfrequenzen charakterisieren periodische Wiederholungen im Ausgabebild (Abb. 2.13). Es ist u ¨blich, den Koordinatenursprung (0, 0) des Spektrums zentriert darzustellen, mit den Koordinaten u, v im Bereich −

−

    I I −1 ≤u≤ 2 2

    J −1 J ≤v≤ . 2 2

inverse FT

FT

Entfernung der Spitzen

Abb. 2.13.

Die Fouriertransformation eignet sich zum Entfernen von periodischen Bildst¨ orungen

Bei einer Verschiebung eines Objektes im Bild ¨ andern sich die Werte |f (u, v)| nicht.

sUppLex

54

2. Bildverarbeitung

2.4.4 Faltungssatz Wir k¨ onnen nun die Faltung aus Abschnitt 2.3.1 (Definition 2.6) genauer definieren. 2.15

Definition 2.15: Faltung Z Seien f, h ∈ QZ IJ . Die Funktion g ∈ QIJ mit

g(i, j) =

I−1 J−1 1  f (k, l) · h(i − k, j − l) I ·J k=0 l=0

heißt Faltung der Funktionen f und h. Wir benutzen die u ¨bliche Bezeichnung g = f ∗ h. Anmerkung 2.4.1 Die Faltung kann man als Multiplikation im Raum QZ IJ

auffassen. 2.3

Satz 2.3 (Faltungssatz) F¨ ur alle f, h ∈ QZ IJ gilt

F T (f ∗ h) = F T (f ) · F T (h).

2.4.5 Anwendung des Faltungssatzes Sei GE = (gE (i, j)) ein Eingabebild und GA = (gA (i, j)) das Ausgabebild, sowie K = (k(i, j)) eine beliebige Matrix, die wir Impulsantwort nennen ( i = 0, . . . , I − 1; j = 0, . . . , J − 1). GE , GA und K setzen wir periodisch fort und nehmen deshalb an GE , GA , K ∈ QZ IJ .

sUppLex

2.4

Globale Operationen

55

Weiter sei H = F T (K) ¨ die Fouriertransformierte von K. H = (h(u, v)) heißt Ubertragungsfunktion. Schließlich sei FE = (fE (u, v)) die FT von GE . Die Faltung K ∗ GE = GA l¨asst sich auf das Produkt der Funktionen h(u, v) · fE (u, v) zur¨ uckf¨ uhren, denn es gilt: GA = F T −1 [F T (K ∗ GE )] = F T −1 [F T (K) · F T (GE )] = FT ⇒

gA (i, j) = F T

−1

[H · FE ]

−1

[h(u, v) · fE (u, v)]

(Faltungssatz)

Anmerkung 2.4.2 Man hat zwei M¨ oglichkeiten, ein Bild zu manipulieren (Abb.

2.14 und 2.15): 1. Durch die Faltung mit der Impulsantwort K GA = K ∗ GE . ¨ 2. Durch die Multiplikation mit einer Ubertragungsfunktion H (hier ben¨otigt man die Fouriertransformation) gA (i, j) = F T −1 [h(u, v) · fE (u, v)] .

2.4.6 Schnelle Fouriertransformation – FFT Die Berechnung der Fouriertransformation f (u, v) =

I−1 J−1 j·v i·u 1  s(i, j) · e−2πi( I + J ) I · J i=0 j=0

l¨ asst sich sehr effizient durchf¨ uhren.

sUppLex

56

2. Bildverarbeitung

FT

inverse FT

Abb. 2.14. Beim Entfernen des mittleren Bereiches innerhalb der Fouriertransformation

k¨ onnen Kanten im Bild hervorgehoben werden.

FT

inverse FT

Abb. 2.15. Beim Entfernen des ¨ außeren Bereiches innerhalb der Fouriertransformation

k¨ onnen Bildst¨ orungen analog zur Mittelwertoperation im Bild behandelt werden. Es entsteht aber ein unscharfes Bild.

sUppLex

2.4

Globale Operationen

57

Zun¨ achst gilt ⎛ ⎞ I−1 J−1   j·v i·u 1 ⎝ f (u, v) = s(i, j) · e−2πi J ⎠ e−2πi I , I · J i=0 j=0 d.h. wir k¨ onnen die zweidimensionale diskrete FT auf mehrere eindimensionale diskrete FT der Art

f (k) =

N −1 

k·t

g(t) · e−2πi N ,

k = 0, . . . , N − 1

(2.9)

t=0

zur¨ uckf¨ uhren. Im ersten Schritt setzen wir

k=v t=j N =J g(t) = s(i, t) und berechnen f¨ ur alle i = 0, . . . , I − 1 die Funktionen J−1 

f1 (i, v) =

s(i, j) · e−2πi

j·v J

v = 0, . . . , J − 1.

,

j=0

Danach setzen wir k=u t=i N =I g(t) = f1 (t, v) und berechnen f¨ ur alle v = 0, . . . , J − 1 die Funktionen f2 (u, v) =

I−1 

f1 (i, v) · e−2πi

i·u I

,

u = 0, . . . , J − 1.

i=0

Schließlich erhalten wir f (u, v) =

1 · f2 (u, v). I ·J

sUppLex

58

2. Bildverarbeitung

Wir arbeiten also die Eingabematrix S = (s(i, j)) erst zeilenweise und dann spaltenweise ab. Nun zeigen wir, wie man die eindimensionale diskrete Fouriertransformation (2.9) rekursiv berechnen kann. Dabei nehmen wir an, dass N = 2p eine Potenz von 2 ist. F¨ ur andere N gibt es ebenfalls Rekursionsformeln (Aufgabe 2.4.14). Sei WN = e−

2πi N

,

dann gilt 2πi

WN2 = e− N/2 . F¨ ur k
f

wird in 2 korrespondierende Bildpunkte Pl = (xl , yl , f ) Pr = (xr , yr , f ) in der linken bzw. in der rechten Bildebene abgebildet. Dann gilt f ·x z f ·y yr = z

xr =

(7.11) (7.12)

und f (x − a) z f ·y . yl = z

xl = a +

(7.13) (7.14)

Wir setzen yr = yl = yB . In den folgenden Rechnungen sei x = 0 und x = a. Die beiden Spezialf¨alle ¨ x = 0 bzw. x = a k¨ onnen Sie in der Ubungsaufgabe 7.6.2 betrachten. Aus (7.11) und (7.13) folgt z= und

f ·x f · (x − a) = xr xl − a x−a x . = xr xl − a

Wegen x = 0 und x = a gilt xr = 0 und xl = a. Damit erhalten wir die x-Koordinate des Punktes P x=

a · xr −a · xr = xl − xr − a xr − xl + a

und schließlich (aus (7.11) bzw. (7.12)) z=

a·f xr − xl + a

sUppLex

224

7. Dreidimensionale Bildinterpretation

und y=

a · yB . xr − xl + a

¨ In der Ubungsaufgabe 7.6.3 k¨ onnen Sie zeigen, dass xr − xl + a = 0 ist. Damit ist die Entfernung z zum Punkt P (x, y, z) umgekehrt proportional zu oße heißt auch Disparit¨ at. xr − xl . Diese Gr¨ Das eigentliche Problem ist, korrespondierende Punkte im linken und rechten Bild zu finden, so dass die Disparit¨ at gemessen werden kann. Dieses Problem wird auch Korrespondenzproblem genannt. Es gibt zahlreiche M¨oglichkeiten, dieses Problem anzugehen. 7.6.2 Korrespondenzproblem Hier geht es um die Zuordnung korrespondierender Bildpunkte in den beiden Bildern (linkes und rechtes Bild). Dabei heißen 2 Bildpunkte korrespondierend, wenn sie Abbilder desselben Objektpunktes in der realen Welt (Szene) sind. Sind die Bildpunkte ununterscheidbar, so hat man bei jeweils n Punkten im linken bzw. rechten Bild n! m¨ ogliche Zuordnungen, die alle zu anderen dreidimensionalen Interpretationen f¨ uhren. 7.10

Beispiel 7.10 Wir betrachten 3 Punkte P1 , P2 und P3 in der Szene. In jeder

Bildebene haben wir dann 3 Bildpunkte Pln1 , Pln2 , Pln3 bzw. Prm1 , Prm2 , Prm3 (Abb. 7.9). Wir erhalten 3! = 6 m¨ ogliche Zuordnungen n1 = m1 ,

n2 = m2 ,

n3 = m3

n1 = m1 ,

n2 = m3 ,

n3 = m2

n1 = m2 ,

n2 = m1 ,

n3 = m3

n1 = m2 ,

n2 = m3 ,

n3 = m1

n1 = m3 ,

n2 = m1 ,

n3 = m2

n1 = m3 ,

n2 = m2 ,

n3 = m1 .

Dies ergibt 6 verschiedene r¨ aumliche Anordnungen der Punkte P1 , P2 und P3 . Die Abb. 7.10 und 7.11 zeigen 2 der 6 M¨oglichkeiten. Man erkennt, dass sehr verschiedene Anordnungen entstehen k¨onnen. Es ist deshalb n¨ otig, korrespondierende Punkte zu finden. Wir untersuchen jetzt einige M¨ oglichkeiten.

sUppLex

7.6

Shape from Stereo

225

Pln1

Prm3

Pln2 Prm2 Pln3

Prm1

Zl

Zr

Abb. 7.9. 3 Bildpunkte in jeder Bildebene

7.6.3 Epipolarlinien Es seien P = (x, y, z) ein Szenenpunkt und Zl bzw. Zr die beiden Projektionszentren mit den zugeh¨ origen Bildebenen Bl und Br (Abb. 7.12). Pl und Pr seien die beiden Bildpunkte von P. Weiter sei B die Verbindungsgerade zwischen den beiden Projektionszentren (d.h. Zl , Zr ∈ B). B nennen wir auch Basislinie. Definition 7.13: Epipole

7.13

Die beiden Punkte PlE = B ∩ Bl PrE = B ∩ Br heißen Epipole. PlE ist der Bildpunkt des Projektionszentrums Zr in der linken Bildebene und PrE ist der Bildpunkt des Projektionszentrums Zl in der rechten Bildebene.

sUppLex

226

7. Dreidimensionale Bildinterpretation

P2 P1

P3

Pln1

Prm3

Pln2 Prm2 Pln3

Prm1

Zl

Zr

Abb. 7.10. Lage der Punkte P1 , P2 und P3 bei der Zuordnung n1 = m1 , n2 = m2 und

n3 = m3

P1

P2

Pln1

P3

Prm3

Pln2 Prm2 Pln3 Zl

Prm1 Zr

Abb. 7.11. Lage der Punkte P1 , P2 und P3 bei der Zuordnung n1 = m3 , n2 = m2 und

n3 = m1

sUppLex

7.6

Shape from Stereo

227

Definition 7.14: Epipolare Ebene

7.14

Die Ebene E(P ), die die Punkte P, Zl und Zr enth¨alt, heißt epipolare Ebene bez¨ uglich P . Es gilt B ⊆ E(P ). Definition 7.15: Epipolare Linien

7.15

Die beiden Geraden Ll (P ) = E(P ) ∩ Bl Lr (P ) = E(P ) ∩ Br . heißen epipolare Linien bez¨ uglich P .

P

E(P )

Bl

Br Pr Pl

Zl

Zr PlE

PrE B

Ll (P )

Lr (P )

Abb. 7.12. Epipole PlE , PrE , epipolare Ebene E(P ) und epipolare Linien Ll (P ), Lr (P )

sUppLex

228

7.9

7. Dreidimensionale Bildinterpretation

Satz 7.9 Es gilt

Pl ∈ Ll (P ) Pr ∈ Lr (P ). Beweis 7.9 Folgt unmittelbar aus Pl ∈ E(P ) ∩ Bl und Pr ∈ E(P ) ∩ Br .

F¨ ur einen gegebenen Bildpunkt Pl im linken Bild kann man die Ebene E(P ) konstruieren (man hat 3 Punkte Zl , Zr und Pl dieser Ebene) und damit auch die Epipolarlinie Lr (P ). Ein Punkt Pl im linken Bild kann nur mit einem Punkt Pr im rechten Bild korrespondieren, wenn dieser auf der zugeh¨ origen Epipolarlinie Lr (P ) im rechten Bild liegt. Die Suche nach einem korrespondierenden Bildpunkt Pr im rechten Bild reduziert sich damit auf ein eindimensionales Problem Pr ∈ Lr (P ). Bei der Standardstereogeometrie (Bl = Br ) folgt Ll (P ) = Lr (P ). Korrespondierende Punkte liegen also auf einer gegebenen Geraden Ll (P ). 7.6.4 Korrespondierende Punkte auf Grund von Bildeigenschaften Hier gibt es zahlreiche M¨ oglichkeiten: Zu einem Bildpunkt im linken Bild wird man einen korrespondierenden Punkt nur in einem gewissen Bildausschnitt des rechten Bildes suchen. Punkte in den beiden Bildern k¨ onnen nur dann miteinander korrespondieren, wenn sie die gleiche physikalische Ursache, wie Grauwert Farbe Element einer Kante, außer Glanzlichtkanten und Verdeckungskanten Kantenenden in der Szene haben. 7.6.5 Disparit¨ atslimit 2 Punkte Pl und Pr mit den Bildkoordinaten Pl = (xl , yl , zl ) und Pr = (xr , yr , zr )

sUppLex

7.6

Shape from Stereo

229

im linken bzw. rechten Bild korrespondieren miteinander, wenn  (xl − xr )2 + (yl − yr )2 + (zl − zr )2 < dmax . Bei der Standardstereogeometrie vereinfacht sich dies zu |xl − xr | < dmax . Anmerkung 7.6.1 Es wird ein Mindestabstand zwischen den Punkten der Sze-

ne und der Kamera festgelegt. 7.6.6 Kontinuit¨ at von Disparit¨ aten Wenn 2 Punkte Pl1 und Pr1 mit den Bildkoordinaten Pl1 = (xl1 , yl1 , zl1 ) und Pr1 = (xr1 , yr1 , zr1 ) im linken bzw. rechten Bild miteinander korrespondieren, so kann ein im linken Bild zu Pl1 benachbarter Punkt Pl2 = (xl2 , yl2 , zl2 ) nur dann mit einem Punkt Pr2 = (xr2 , yr2 , zr2 ) im rechten Bild korrespondieren, wenn die absolute Differenz der Disparit¨ atswerte |d1 − d2 | < ε klein ist. Dabei ist

d1 = d2 =

 

(xl1 − xr1 )2 + (yl1 − yr1 )2 + (zl1 − zr1 )2 (xl2 − xr2 )2 + (yl2 − yr2 )2 + (zl2 − zr2 )2 .

Bei der Standardstereogeometrie vereinfacht sich dies zu ||xl1 − xr1 | − |xl2 − xr2 || < ε. Eine Ausnahme bilden Punkte entlang der Objektbegrenzungen.

sUppLex

230

7. Dreidimensionale Bildinterpretation

7.6.7 Disparit¨ atsgradientenlimit Hier nehmen wir die Standardstereogeometrie an. Es seien Al = (xAl , yA ) und Ar = (xAr , yA ) sowie Bl = (xBl , yB ) und Br = (xBr , yB ) jeweils korrespondierende Punkte im linken und rechten Bild. 7.16

Definition 7.16: Disparit¨ atsgradient

Die Gr¨ oße Γd = 5

|Δxl − Δxr | 1 4 (Δxl

− Δxr )2 + (Δy)2

mit (Δxl = |xAl − xBl | ,

Δxr = |xAr − xBr | ,

Δy = |yA − yB |)

heißt Disparit¨ atsgradient. Zwei Punktepaare im linken und im rechten Bild korrespondieren, wenn Γd < Γmax ,

0.5 ≤ Γmax ≤ 2.

Es wird damit gleichzeitig die maximal zul¨assige Neigung von Objektoberfl¨ achen der Szene gegen¨ uber der Kamera festgelegt. 7.6.8 Reihenfolge der Punkte Punkte, die in einem Stereobild auf einer Epipolarlinie liegen, werden in genau derselben Reihenfolge auf der korrespondierenden Epipolarlinie des anderen Bildes abgebildet. Dabei m¨ ussen die Punkte sich in etwa gleicher Entfernung zur Kamera befinden. 7.6.9 Aufgaben 7.6.1

Aufgabe 7.6.1 Zeigen Sie die Gleichungen (7.13) und (7.14).

7.6.2

Aufgabe 7.6.2 Untersuchen Sie die Rechnungen aus Abschnitt 7.6.1 f¨ ur die F¨ alle x = 0 und x = a.

7.6.3

Aufgabe 7.6.3 Zeigen Sie, dass in den Rechnungen aus Abschnitt 7.6.1

xr − xl + a = 0 gilt.

sUppLex

7.7

Shape from shading

231

Aufgabe 7.6.4 Legen Sie das linke Projektionszentrum in den Rechnungen aus

7.6.4

Abschnitt 7.6.1 in den Punkt (a, b, 0), a = 0, b = 0 und zeigen Sie dann z=

f ·b f ·a = . xr − xl + a xr − xl + b 7.7

7.7 Shape from shading Wenn man bestimmte Annahmen u ¨ber die Lichtquellen und die Reflexionseigenschaften der Objekte treffen kann, so k¨ onnen aus der Schattierung auf der Objektoberfl¨ ache R¨ uckschl¨ usse u ber die Form der Oberfl¨ache gezogen ¨ werden.

7.7.1 Einf¨ uhrung Schattierungen entstehen auf der Objektoberfl¨ ache selbst durch unterschiedliche Orientierungen der Oberfl¨ ache relativ zur Lichtquelle und zum Betrachter. Schatten sind etwas anderes und entstehen auf dem Hindergrund durch Verdeckung der Lichtquelle. Wir betrachten hier Lambertsche Oberfl¨ achen, die man auch matt oder nichtspiegelnd nennt. Hier h¨ angt die beobachtete Helligkeit nur von der Richtung zur Lichtquelle ab. F¨ ur diese Oberfl¨ achen stehen Ver¨ anderungen der reflektierten Lichtintensit¨at eines gegebenen Punktes in direkter Beziehung zum Normalenvektor dieses Punktes. Falls die Richtung zur Lichtquelle parallel zum Normalenvektor ist, erscheint die Oberfl¨ ache am hellsten und falls die Richtung zur Lichtquelle senkrecht zum Normalenvektor steht, ist die Oberfl¨ache dunkel (Abb. 7.13. Damit kann man die Oberfl¨ achenorientierung berechnen.

Abb. 7.13. Hier kommt das Licht von vorn (links) oder von rechts oben (rechts)

sUppLex

232

7. Dreidimensionale Bildinterpretation

7.7.2 Lambertsche Oberfl¨ ache Wir betrachten hier nur parallele Beleuchtung, also eigentlich eine unendlich weit entfernte Punktlichtquelle, wie z.B. die Sonne. Nat¨ urlich erf¨ ullen auch normale Beleuchtungsanordnungen oft angen¨ahert diese Bedingung. Wir betrachten aber keine ungerichtete Beleuchtung, wie z.B. einen bedeckten Himmel. Dann ben¨ otigen wir nur die Richtung zur Lichtquelle und die zum Betrachter. Sei l mit "l" = 1 die Richtung zur Lichtquelle, n

mit

"n" = 1

der Normalenvektor und ϕ = (l, n) der Winkel zwischen l und n. Die Richtung zum Betrachter bezeichnen wir mit a (Abb. 7.14).

Lichtquelle

ϕ

− → n

− → l

− → a

Betrachter

Objekt

Abb. 7.14. Reflexion an einer Oberfl¨ ache

Wir f¨ uhren kurz zwei physikalische Begriffe an, die f¨ ur das weitere von Bedeutung sind. 7.17

Definition 7.17: Irradianz

Die Irradianz (Bestrahlungsst¨ arke) ist die eingestrahlte Leistung, bezogen auf die Fl¨ ache A.

sUppLex

7.7

Shape from shading

233

Es gilt E=

dΦ , dA

[E] =

W . m2

Dabei ist Φ der Strahlungsfluss, gemessen in Watt. Die Irradianz bestimmt z.B. die Erregung eines Fotorezeptors in der Netzhaut oder die Schw¨ arzung eines fotographischen Films. Irradianzen beschreiben sowohl die Bildintensit¨ at, als auch die St¨ arke der Beleuchtung einer Oberfl¨ache in der Szene durch die Lichtquelle. Definition 7.18: Radianz

7.18

Die Radianz (Strahlungsdichte) ist die pro Fl¨ ache A in einem Kegel vom Raumwinkel Ω in Richtung θ abgestrahlte Leistung. Es gilt L=

d2 Φ , cos θdΩdA

[L] =

W m2 sr

Der Raumwinkel ist eine Fl¨ ache, die ein Kegel aus der Einheitskugel herausschneidet, gemessen in sr (Steradian). Der Vollwinkel hat die Gr¨oße 4πsr. Bei einer Lambertschen Oberfl¨ ache bzw. einer Lambertschen Reflexion berechnet man die Radianz folgendermaßen: L = cd I0 cos ϕ = cd I0 (l · n)

f¨ ur cos ϕ ≥ 0

(7.15)

und (die Lichtquelle liegt hinter der Oberfl¨ ache) L = 0 f¨ ur cos ϕ < 0 Dabei bedeutet I0 die einfallende Lichtmenge, die durch einen Querschnitt der Fl¨ ache 1 senkrecht zur Lichtrichtung durchtritt. I0 wird auf einer Oberfl¨ache oßer ist (Abb. 7.15). A verteilt, die um den Faktor cos1 ϕ gr¨ Damit erhalten wir f¨ ur die Irradianz E = I0 cos ϕ. Die Konstante cd (Albedo) ist der Anteil des eingestrahlten Lichtes, welches durch die Reflexion wieder abgegeben wird und zwar in alle Raumrichtungen gleichm¨ aßig. Die Oberfl¨ ache sieht also aus jeder Betrachtungsrichtung gleich hell aus.

sUppLex

234

7. Dreidimensionale Bildinterpretation

− → l F =1

− → n

I0

ϕ A Abb. 7.15. Berechnung der Irradianz

Anmerkung 7.7.1 Eine Lambertsche Ober߬ ache hat folgende Eigenschaften:

Bewegt man sich um die Oberfl¨ ache herum, ¨andert sich ihre Helligkeit nicht. Es ist eine matte Oberfl¨ ache. Bewegt man die Lichtquelle, so ist die Oberfl¨ache am hellsten bei ϕ = 0◦ und dunkel bei ϕ = 90◦ . 7.11

Beispiel 7.11: Matte Kugel unter paralleler Beleuchtung

Die Kugeloberfl¨ ache sei durch x2 + y 2 + z 2 = 1 gegeben. Die Beobachtungsrichtung sei die z-Richtung des Koordinatensystems. Die parallele Beleuchtung habe die St¨ arke I0 . Dann gilt:  n = (x, y, 1 − (x2 + y 2 ))T Wir betrachten 2 F¨ alle f¨ ur die Richtung zur Lichtquelle. Sei l = (0, 0, 1)T , d.h. frontale Beleuchtung aus der Beobachtungsrichtung. Dann gilt:  L = cd I0 (l · n) = cd I0 1 − (x2 + y 2 ) Sei l = (1, 0, 0)T , d.h. Beleuchtung von der Seite senkrecht zur Beobachtungsrichtung. Dann gilt:

sUppLex

7.7

Shape from shading

235

 L=

cd I0 x 0

falls

x≥0 x 0 – Regularisierungsparameter r(i, j) – Datenfehler an der Stelle (i, j): r(i, j) = (I(i, j) − R(p(i, j), q(i, j)))2 s(i, j) – Glattheitsforderung, wegen (7.18): s(i, j) =

1 ((p(i + 1, j) − p(i, j))2 + (p(i, j + 1) − p(i, j))2 4 + (q(i + 1, j) − q(i, j))2 + (q(i, j + 1) − q(i, j))2 )

sUppLex

7.7

Shape from shading

239

Man minimiert nun e als Funktion der Unbekannten p(i, j), q(i, j) und erh¨alt damit eine Sch¨ atzung der Orientierung an jeder Stelle der Oberfl¨ache. Im Minimum m¨ ussen die partiellen Ableitungen ∂e ∂p(i, j) und ∂e ∂q(i, j) f¨ ur alle i, j verschwinden. ur die 2n2 Unbekannten p(i, j), q(i, j). Man hat dann 2n2 Gleichungen f¨ Es gilt 1 ∂e = [(p(i, j) − p(i + 1, j)) + (p(i, j) − p(i, j + 1)) ∂p(i, j) 2 + (p(i, j) − p(i − 1, j)) + (p(i, j) − p(i, j − 1))] ∂R − 2λ(I(i, j) − R(p(i, j), q(i, j)) · (p(i, j), q(i, j)) = 0. ∂p Man beachte, dass p(i, j) in der Summe n  n 

s(i, j)

i=1 i=1

mehrmals auftritt. Weiter haben wir 1 ∂e = [(q(i, j) − q(i + 1, j)) + (q(i, j) − q(i, j + 1)) ∂q(i, j) 2 + (q(i, j) − q(i − 1, j)) + (q(i, j) − q(i, j − 1))] ∂R − 2λ(I(i, j) − R(p(i, j), q(i, j)) · (p(i, j), q(i, j)) = 0. ∂q Man kann nun diese beiden Gleichungen nicht direkt nach p(i, j) bzw. q(i, j) aufl¨ osen, da die jeweils im zweiten Summanden auftretende Reflektivit¨ atsfunktion R nicht invertierbar ist. Eine iterative L¨ osung erh¨ alt man, indem man die lokalen Mittelwerte 1 (p(i + 1, j) + p(i, j + 1) + p(i − 1, j) + p(i, j − 1)) 4 1 q(i, j)∗ = (q(i + 1, j) + q(i, j + 1) + q(i − 1, j) + q(i, j − 1)) 4

p(i, j)∗ =

einf¨ uhrt und dann folgende Iteration ansetzt:

sUppLex

240

7. Dreidimensionale Bildinterpretation

∗

∂R (p(i, j)n , q(i, j)n ) ∂p

∗

∂R (p(i, j)n , q(i, j)n ) ∂q

p(i, j)n+1 = p(i, j)n + λ(I(i, j) − R(p(i, j)n , q(i, j)n ) ·

q(i, j)n+1 = q(i, j)n + λ(I(i, j) − R(p(i, j)n , q(i, j)n ) ·

Die Startbedingungen p(i, j)0 , q(i, j)0 erh¨ alt man aus geeigneten Randbedingungen, z.B. der Verdeckungskante der Oberfl¨ache. Das vorgestellte Verfahren geht auf [23] zur¨ uck. 7.7.7 Aufgaben 7.7.1

Aufgabe 7.7.1 Untersuchen Sie Beispiel 7.11 auch f¨ ur andere Richtungen zur

Lichtquelle. 7.7.2

Aufgabe 7.7.2 Beweisen Sie die Gleichung (7.16).

7.8

7.8 Shape from contour 7.8.1 Einf¨ uhrung Beliebige dreidimensionale Objekte k¨ onnen anhand ihrer Konturen erkannt und lokalisiert werden, wenn ausreichend genaue geometrische Modelle der Objekte vorhanden sind. Hier betrachten wir nur Polyeder als Objekte (Abb. 7.18).

Abb. 7.18. Eine einfache Linienzeichnung mit Polyederobjekten.

sUppLex

7.8

Shape from contour

241

Beim Waltz-Algorithmus ([55]) geht es um die dreidimensionale Interpretation zweidimensionaler Linienzeichnungen. Die Linienzeichnung ist zun¨achst ein ungerichteter Graph, bestehend aus Kanten und Knoten. Bei der dreidimensionalen Interpretation bekommen die Kanten und Knoten unterschiedliche Bedeutungen. Diese markiert man durch Marken an den entsprechenden Bildelementen. Bildelemente mit Bedeutungen k¨onnen nicht in beliebiger Weise kombiniert werden, sondern nur im Rahmen bestimmter Relationen zwischen diesen Bedeutungen, die aus physikalischen Gr¨ unden bestehen. Die Aufgabe ist es, konsistente Markierungen f¨ ur eine zweidimensionale Linienzeichnung zu finden oder zumindest die Ausgangsmenge von Markierungen durch Entfernen inkonsistenter Markierungen stark einzuschr¨anken. Wir treffen zun¨ achst einige vereinfachende Annahmen: Es werden keine Schatten oder Bruchlinien betrachtet (Abb. 7.19). Alle Eckpunkte sind Schnittpunkte genau drei aufeinandertreffender Ebenen eines Objektes. Die oberen Eckpunkte von Pyramiden sind also nicht erlaubt (Abb. 7.20). Wir nehmen einen allgemeinen Beobachterstandpunkt ein, d.h., dass bei geringer Bewegung der Kamera keine Schnittpunkte ihren Typ ver¨andern.

Bruchlinien

Abb. 7.19. Bruchlinien werden zun¨ achst nicht zugelassen.

Abb. 7.20. Der obere Eckpunkt ist nicht erlaubt.

sUppLex

242

7. Dreidimensionale Bildinterpretation

7.8.2 Kantenmarken Unter den obigen Annahmen gibt es 4 M¨ oglichkeiten (Abb. 7.21 und 7.22). −

konkave Kante mit 2 sichtbaren Fl¨achen

+

konvexe Kante mit 2 sichtbaren Fl¨achen konvexe Kante mit genau einer sichbaren Fl¨ ache. Die sichtbare Fl¨ache liegt rechts vom Pfeil (in Pfeilrichtung)

Abb. 7.21. Markierung der Kanten

+

+ +

-

-

Abb. 7.22. Beispiele f¨ ur Kantenmarken

7.8.3 Knotentypen Man erh¨ alt 4 Knotentypen (Abb. 7.23). ¨ Anmerkung 7.8.1 Der Typ T ist nur bei partieller Uberdeckung m¨oglich (siehe auch Abb. 7.18). 7.8.4 Knotenmarken Die Kantenmarken und Knotentypen kann man nun kombinieren. Dann erh¨alt man an den Knoten Markierungen f¨ ur alle einlaufenden Kanten. Rein komur die u binatorisch gibt es f¨ ur den Knotentypen L 42 , f¨ ¨brigen Knotentypen

sUppLex

7.8

Shape from contour

243

L

Gabel

T

Pfeil

Abb. 7.23. Typen von Knoten

43 M¨ oglichkeiten, die Kanten zu markieren, insgesamt also 208. Physikalisch m¨ oglich ist aber nur ein kleiner Teil davon, n¨ amlich 18 (Abb. 7.24). −

+

−

+

−

−

−

−

+

+

+

−

+

−

−

+

+

−

−

+

+ −

Abb. 7.24. Die 18 physikalisch m¨ oglichen Markierungen von Knoten mit einlaufenden Kan-

ten ([22]).

An jedem Knoten stoßen genau drei Fl¨ achen zusammen (obige Annahme). Deshalb unterteilt ein Knoten den dreidimensionalen Raum in 8 Oktanten. Stellt man sich nun einen oder zwei oder drei usw. bis sieben der Oktanten

sUppLex

244

7. Dreidimensionale Bildinterpretation

ausgef¨ ullt vor und dem Betrachter in jedem der jeweils freien Oktanten, dann erh¨ alt man alle m¨ oglichen Knotenmarken. Der Fall, dass 2,4 oder 6 Oktanten ausgef¨ ullt sind, kann nicht eintreten. In [56] kann man die Herleitung genauer nachlesen. Man erkennt aus Abb. 7.24 2 interessante Eigenschaften: Es gibt nur eine Art Pfeil mit Pfeilmarken an der linken und rechten Kante. F¨ ur solch einen Pfeil muss die mittlere Kante mit einem + versehen werden. Es gibt nur eine Art Gabel mit irgendeinem +. F¨ ur diese Gabel m¨ ussen alle Kanten mit + versehen werden. 7.8.5 Waltz-Algorithmus Die Aufgabe der dreidimensionalen Interpretation l¨asst sich nun folgendermaßen definieren. Finde f¨ ur eine vorgegebene zweidimensionale Linienzeichnung eine Zuordnung von Marken zu den Knoten derart, dass jeder Knoten eine zul¨ assige Markierung im Sinne der 18 M¨ oglichkeiten besitzt und die Marken der zusammengesetzten Kantenst¨ ucke u ¨bereinstimmen. Programm 7.1 (Knotenmarkierungsalgorithmus (Waltz [55]))

1. Bilde eine Liste L mit allen Knoten. 2. Bis die Liste L leer ist, entferne 2.1. das erste Element in der Liste L. Nenne es aktueller Knoten. 2.1.1. Falls der aktuelle Knoten noch niemals aufgesucht wurde, erstelle f¨ ur ihn eine Menge an Knotenmarken, die f¨ ur den betreffenden Knotentyp alle m¨ oglichen Marken enth¨ alt. Eine Mengen¨ anderung hat stattgefunden. 2.1.2. Wenn irgendeine Knotenmarke aus der Menge des aktuellen Knotens mit allen Knotenmarken in der Menge irgendeines benachbarten Knotens nicht kompatibel ist, eliminiere diese inkompatible Marke aus der Menge des aktuellen Knotens. Eine Mengen¨ anderung hat stattgefunden. 2.2. Wenn eine Mengen¨ anderung stattfand, setze jeden benachbarten Knoten, der eine Markenmenge besitzt und nicht in der Liste L enthalten ist, an den Anfang der Liste L. Dieser Algorithmus ist eine Anwendung der Constraintpropagierung. 7.12

Beispiel 7.12 Abbildung 7.25 zeigt die einzelnen Schritte bei der Markierung

eines W¨ urfels, der frei im Raum aufgeh¨ angt ist.

sUppLex

7.8

Shape from contour

245

+ + +

+ +

+ + + +

Abb. 7.25. Markierung eines W¨ urfels, der im Raum aufgeh¨ angt ist.

Beispiel 7.13 Wit betrachten das folgende einfache Beispiel (Abb. 7.26), das

7.13

wir [56] entnehmen. Hier lassen sich die Eckpunkte A, B, C, D klassifizieren ¨ (siehe Ubungsaufgabe 7.8.2).

C

B

D

A

Abb. 7.26. Die Knoten A, B, C, D lassen sich eindeutig markieren.

7.8.6 Erweiterungen Weitere Kantenmarkierungen kann man f¨ ur Schatten und Bruchlinien betrachten. Auch die Anzahl der Knotentypen kann erweitert werden, wenn die Eckpunkte der Polyeder auch als Schnittpunkt von mehr als 3 Ebenen enstehen k¨ onnen

sUppLex

246

7. Dreidimensionale Bildinterpretation

Die Anzahl der zul¨ assigen Markierungen erh¨oht sich dann aber sprunghaft. 7.8.7 Aufgaben 7.8.1

Aufgabe 7.8.1 Untersuchen Sie die Ergebnisse des Markierungsalgorithmus

von Waltz auch f¨ ur W¨ urfel, die nicht frei im Raum aufgeh¨angt sind. 7.8.2

Aufgabe 7.8.2 Markieren Sie die Eckpunkte A, B, C und D aus Abb. 7.26 mit

Hilfe des Waltz-Algorithmus. 7.8.3

Aufgabe 7.8.3 Markieren Sie die Eckpunkte A, B, C, D und E aus Abb. 7.27

mit Hilfe des Waltz-Algorithmus.

E

A

D

C

B

Abb. 7.27. Die Knoten A, B, C, D und E sollen mit Markierungen versehen werden.

7.8.4

Aufgabe 7.8.4 Markieren Sie die Eckpunkte A, B, C, D und E aus Abb. 7.28

mit Hilfe des Waltz-Algorithmus.

D

A

C

B

Abb. 7.28. Die Knoten A, B, C und D sollen mit Markierungen versehen werden.

sUppLex

7.9

Weitere M¨ oglichkeiten f¨ ur Shape from X

247

7.9

7.9 Weitere M¨ oglichkeiten f¨ ur Shape from X 7.9.1 Shape from motion Von einer Szene, die bewegte Objekte enth¨ alt, wird eine Bildfolge aufgenommen. Hieraus k¨ onnen dann unter bestimmten Annahmen, R¨ uckschl¨ usse auf die Form des Objektes gezogen werden. Diese Problematik behandeln wir im Kapitel 8. Werden von einem rotierenden Objekt mehrere 21/2 D-Repr¨asentationen gewonnen, so k¨ onnen diese zu einem vollst¨ andigen 3D-Objektmodell zusammengestzt werden. Eine weitere M¨ oglichkeit stellt die Bewegung der Kamera selbst dar, um sich auf diese Weise mehrere Ansichten derselben Szene zu verschaffen. 7.9.2 Shape from texture Wenn man annimmt, dass auf einer Objektoberfl¨ache eine homogene Textur aufgebracht ist, so wird aufgrund der perspektivischen Betrachtung jede nicht senkrecht auf der Betrachtungsrichtung stehende Fl¨ache eine entsprechend verzerrte Textur aufweisen. Aus dieser Verzerrung l¨asst sich der Normalenvektor der Oberfl¨ ache ableiten. 7.9.3 Shape from focus Verf¨ ugt man u ¨ber ein Kamerasystem, das eine Ver¨anderung der Fokussierung erlaubt, so kann man versuchen, durch Scharfstellen auf einen Punkt der Szene dessen Entfernung zur Kamera festzustellen. Ist die Fokussierung der Kamera fest vorgegeben, so kann andererseits die Unsch¨arfe von Kanten im Bild zur Berechnung der Entfernung herangezogen werden. 7.9.4 Shape from structured light Eine spezielle Lichtquelle wird benutzt, um die Szene mit strukturiertem Licht zu beleuchten. Verzerrungen im beobachteten Muster lassen R¨ uckschl¨ usse auf die 3 D Form zu.

sUppLex

Kapitel 8 Bewegungsanalyse aus Bildfolgen

8

sUppLex

8

8 8.1 8.2 8.3 8.3.1 8.3.2 8.3.3 8.3.4 8.3.5 8.3.6

Bewegungsanalyse aus Bildfolgen Einleitung.......................................................... Lokale Verschiebungsvektoren ................................. Optischer Fluss ................................................... Vorbemerkungen ................................................. Horn-Schunck-Verfahren ....................................... L¨ osung mit Hilfe der Variationsrechnung.................... L¨ osung mit diskreter Iteration ................................. Algorithmus zur Berechnung des optischen Flusses ....... Aufgaben ..........................................................

251 252 255 255 257 259 260 264 265

sUppLex

8 Bewegungsanalyse aus Bildfolgen 8.1

8.1 Einleitung Hier untersuchen wir Bewegungen (Translation, Rotation) von formfesten Szenenobjekten. Wir betrachten dynamische Szenen mit fester Kameraposition. Aber auch statische Szenen mit beweglicher Kamera w¨aren denkbar. Ausgangspunkt ist dabei eine Bildfolge: G0 , G1 , G2 , · · ·

(8.1)

Die Bilder werden in konstanten Zeitabst¨ anden δtconst aufgenommen. Oft nehmen wir δtconst = 1 an. Die r¨ aumliche Bewegung eines Punktes P = (x, y, z) kann in der Bildebene anhand der Bewegung eines projizierten Punktes P ∗ = (u, v, z ∗ ) verfolgt werden. Als Projektionart kann man die Zentralprojektion auf 2 Arten w¨ahlen: kamerazentriert: Das Projektionszentrum befindet sich im Punkt (0, 0, 0) und die Bildebene ist Z = f, f = 0. Dabei ist f eine Kamerakonstante (Abstand zwischen Projektionszentrum und Bildebene). Hier gilt (siehe Satz 7.5 auf Seite 208): f ·y f ·x v= u= z z bildzentriert: Das Projektionszentrum befindet sich im Punkt (0, 0, −f ), f = 0 und die Bildebene ist Z = 0. Hier gilt (siehe Satz 7.6 auf Seite 208): u=

f ·x f +z

v=

f ·y f +z

Die z-Koordinate z ∗ des Punktes P ∗ ist in beiden F¨allen konstant und deshalb nicht von Bedeutung.

sUppLex

252

8.2

8. Bewegungsanalyse aus Bildfolgen

8.2 Lokale Verschiebungsvektoren Wir betrachten nun zwei aufeinanderfolgende Bilder Gk

und Gk+1 ,

k = 0, 1, · · ·

∗ ∗ und in Gk+1 auf Pneu projiziert der Bildfolge (8.1). P wird in Gk auf Palt (siehe Abb. 8.1).

Bildebene v · δtconst

P = (x, y, z) ∗ Pneu

∗ Palt

Z

f

0

Abb. 8.1. Bewegung bei der kamerazentrierten Zentralprojektion.

8.1

Definition 8.1: Lokaler Verschiebungsvektor

Sei tk = k · δtconst Dann heißt

k = 0, 1, · · · .

∗ ∗ − Palt = δtconst · (ξuv (tk ), ψuv (tk ))T duv (tk ) = Pneu

(8.2)

lokaler Verschiebungsvektor im Punkt (u, v) der Bildebene zum Zeitpunkt tk .

Anmerkung 8.2.1

ξuv und ψuv bezeichnen die Geschwindigkeit in u- bzw. v-Richtung in der Bildebene. duv repr¨ asentiert in der Bildebene die 3D-Bewegung des Punktes P = (x, y, z).

sUppLex

8.2

Lokale Verschiebungsvektoren

253

In der Bildebene wird also eine beliebige 3D-Bewegung zwischen 2 Bildaufnahmen approximativ durch lokale Verschiebungsvektoren beschrieben. Eine Menge solcher lokaler Verschiebungsvektoren duv (t) f¨ ur festes t definiert ein lokales Verschiebungsvektorfeld in der Bildebene. Es ist einem Bildpaar Gk und Gk+1 zugeordnet. Abbildung 8.2 zeigt einfache Verschiebungsvektorfelder.

Abb. 8.2. Einfache Verschiebungsvektorfelder – Translation in der Bildebene (oben) – Translation senkrecht zur Bildebene von der Kamera weg (mitte) – Rotation um eine Achse senkrecht zur Bildebene (unten)

sUppLex

254

8. Bewegungsanalyse aus Bildfolgen

Lokale Verschiebungsvektorfelder k¨ onnen aus Bildfolgen berechnet werden, wenn einzelne Oberfl¨ achenpunkte eindeutig in der Bildfolge verfolgt werden k¨ onnen. Dies ist wieder ein Korrespondenzproblem. Die Verfolgung einzelner Oberfl¨ achenpunkte ist nicht einfach. Gegenst¨ande k¨ onnen hinter anderen verschwinden bzw. wieder auftauchen. Ebenso k¨onnen bisher unsichtbare Objektfl¨ achen durch Drehung erscheinen. Zu den neu auftauchenden bzw. verschwindenden Objektpunkten gibt es keine korrespondierenden Punkte im anderen Bild. Ein weiteres Problem ist das Aperturproblem oder Blendenproblem. Ein lokal beschr¨ ankter Ausschnitt einer Bildfolge liefert oft keinen Anhaltspunkt oder nur unzureichende Information u ¨ber die stattfindende Bewegung. 8.1

Beispiel 8.1 Hier betrachten wir die Bewegung einer periodischen Struktur

(z.B. ein horizontales Gitter). Eine Verschiebung um ein Vielfaches des Gitterabstandes ist nicht erkennbar, wenn man nur einen Ausschitt des Objektes sieht (Abb. 8.3).

Abb. 8.3. Die horizontale Bewegung kann u ande verlau¨ber ein, zwei oder drei Gitterabst¨

fen. Dabei k¨ onnen wir nur den rechteckigen Ausschnitt im Bild betrachten.

8.2

Beispiel 8.2 In der Abb. 8.4 ist nur die horizontale Bewegung der Kante fest-

stellbar. Eine vertikale Verschiebung ist nicht zu ermitteln. Es gibt also unendlich viele lokale Verschiebungsvektoren, die alle von einem Punkt der Kante zu einem beliebigen anderen Punkt der verschobenen Kante f¨ uhren k¨ onnen. Erst weitere Informationen (z.B. eine Ecke) f¨ uhren zu einer eindeutige Bestimmung der lokalen Verschiebungsvektoren (Abb. 8.5). Zur approximativen Berechnung lokaler Verschiebungsfelder benutzt man den optischen Fluss.

sUppLex

8.3

Optischer Fluss

255

? Abb. 8.4. Hier ist die vertikale Komponente der Bewegung nicht zuermitteln.

Abb. 8.5. An einer Ecke bekommt man eindeutige lokale Verschiebungsvektoren.

8.3

8.3 Optischer Fluss 8.3.1 Vorbemerkungen ¨ Der optische Fluss (optical flow) repr¨asentiert den Verlauf der Anderungen von Bildgrauwerten zweier Bilder Gk und Gk+1 einer Bildfolge. ¨ Unter der Annahme, dass die Anderung der Grauwerte durch relative oder absolute Objektbewegungen verursacht wird, ist der optische Fluss eine Approximation der lokalen Verschiebungsvektoren. Damit kann der optische Fluss zur Berechnung solcher lokaler Verschiebungsvektorfelder benutzt werden. Der optische Fluss kann aber nicht generell mit einem Feld lokaler Verschiebungsvektoren identifiziert werden, z.B.:

sUppLex

256

8. Bewegungsanalyse aus Bildfolgen

eine vor einer Kamera rotierende Kugel mit konstanter Oberfl¨ achenbeschaffenheit hat keinen optischen Fluss (da keine Grauwert¨ anderung), aber es findet eine Bewegung statt. Eine fest stehende Kugel und sich ver¨ andernde Lichtverh¨altnisse erzeugen einen optischer Fluss, ohne dass eine Bewegung vorliegt. Deshalb ist die Berechnung lokaler Verschiebungsvektoren durch den optischen Fluss nur unter bestimmten Annahmen m¨oglich. Sei G(x, y, tk ) der Grauwert des Bildes Gk im Punkt (x, y) der Bildebene ( k = 0, 1, 2, · · · tk = k · δtconst ). Wir verwenden ab jetzt auch f¨ ur die Bildebene die Koordinaten x und y anstelle von u und v. Eine Diskretisierung von x und y werden wir erst sp¨ ater betrachten. 8.2

Definition 8.2: optischer Fluss

Das Vektorfeld fk (x, y) = (uk (x, y), vk (x, y))T

(8.3)

G(x + uk (x, y), y + vk (x, y), tk + δtconst ) = G(x, y, tk )

(8.4)

mit

heißt optischer Fluss des Bildpaares (Gk , Gk+1 ) und charakterisiert den Ver¨ lauf der Anderungen von Grauwerten von Bild Gk zu Bild Gk+1 . Die Gleichung (8.4) nennt man auch Bildwerttreue des optischen Flusses. Die Bildwerttreue unterst¨ utzt die Berechnung der Vektoren (uk (x, y), vk (x, y))T nur sehr gering, da die einzelnen Grauwerte i. a. in einer sehr großen Anzahl von Bildpunkten identisch auftreten. F¨ ur den optischen Fluss sind also weitere Annahmen zu finden. Unserer Zielstellung gem¨ aß soll der optische Fluss den lokalen Verschiebungsvektoren entsprechen. Es soll also gelten: uk (x, y) = ξxy (tk ) · δtconst vk (x, y) = ψxy (tk ) · δtconst Damit ist fk (x, y) = dxy (tk ).

sUppLex

8.3

Optischer Fluss

257

Dies nennt man Bewegungstreue des optischen Flusses. 8.3.2 Horn-Schunck-Verfahren Dieses Verfahren wurde in [21] vorgestellt. Wir betrachten die Taylorreihenentwicklung der Funktion G(x, y, t) und erhalten:

G(x + δx, y + δy, tk + δt) = ∂G(x, y, tk ) ∂G(x, y, tk ) ∂G(x, y, tk ) + δy · + δt · +e G(x, y, tk ) + δx · ∂x ∂y ∂t Sei speziell δx = uk (x, y) δy = vk (x, y) δt = δtconst = 1 Aus der Bildwerttreue folgt 0 = uk (x, y)

∂G(x, y, tk ) ∂G(x, y, tk ) ∂G(x, y, tk ) + vk (x, y) + + e. ∂x ∂y ∂t

Wir k¨ onnen e = 0 annehmen und erhalten die Horn-Schunck-Bedingung: 0 = uk (x, y)

∂G(x, y, tk ) ∂G(x, y, tk ) ∂G(x, y, tk ) + vk (x, y) + ∂x ∂y ∂t

(8.5)

Die Horn-Schunck-Bedingung folgt also aus der Bildwerttreue des optischen Flusses und aus der Annahme, dass diese Vektoren nur kleine Schritte beschreiben, f¨ ur die die Linearit¨ atsannahme f¨ ur G(x, y, t) gerechtfertigt ist, d.h. f¨ ur die e = 0 angenommen werden kann. F¨ ur einen bestimmten Zeitpunkt t = tk der Bildfolge nimmt die HornSchunck-Bedingung also die Form uGx + vGy = −Gt bzw. (Gx , Gy )(u, v)T = −Gt an. onnen als gegeben vorausgesetzt werden und u, v sind gesucht. Gx , Gy , Gt k¨ Die Horn-Schunck-Bedingung schr¨ ankt die m¨ oglichen Werte des optischen Flusses (u, v) nur auf eine Gerade der uv-Ebene ein. Dies ist gerade das Aperturproblem.

sUppLex

258

8. Bewegungsanalyse aus Bildfolgen

Ausgehend von der Feststellung, dass benachbarte Oberfl¨achenpunkte eines sich bewegenden Objektes in etwa dieselben lokalen Verschiebungsvektoren besitzen, kann als globale Annahme die Glattheit des Vektorfeldes des optischen Flusses getroffen werden. Die Glattheit ist gegeben, falls die ersten Ableitungen ux , uy , vx , vy nahe bei Null liegen, d.h.: u2x (x, y) + u2y (x, y) + vx2 (x, y) + vy2 (x, y) nimmt einen minimalen Wert an f¨ ur die Bildpunkte (x, y) eines zu betrachtenden Teilbildes Ω (fester Zeitpunkt). Dies ist u ¨ber alle (x, y) ∈ Ω aufzusummieren. Wir betrachten nun das Funktional 66 (u2x (x, y) + u2y (x, y) + vx2 (x, y) + vy2 (x, y)) dxdy. Fg (u, v) = Ω

Es gibt den Glattheitsfehler f¨ ur ein Funktionenpaar (u(x, y), v(x, y)) an, welcher zu minimieren ist. Ω ist dabei die Menge aller Bildpunkte, f¨ ur die der optische Fluss zu berechnen ist. Weiter betrachten wir das Funktional 66 (u(x, y)Gx (x, y, t) + v(x, y)Gy (x, y, t) + Gt (x, y, t))2 dxdy. Fh (u, v) = Ω

Es gibt f¨ ur ein Funktionenpaar (u(x, y), v(x, y)) den Fehler bez¨ uglich der G¨ ultigkeit der Horn-Schunck-Bedingung an. Dieser ist ebenfalls zu minimieren. Sei λ ≥ 0 ein Wichtungsparameter, der den Einfluss der beiden Funktionale auf die L¨ osung beschreibt. Man kann z.B. λ = 10 w¨ahlen. Insgesamt ist also das Funktional F (u, v) = Fg (u, v) + λFh (u, v)

(8.6)

zu minimieren. F¨ ur die L¨ osung der Optimierungsaufgabe F (u, v) = Fg (u, v) + λFh (u, v) → M IN sind zwei verschiedene Wege m¨ oglich. Man kann Methoden der Variationsrechnung benutzen oder eine diskrete Iteration durchf¨ uhren.

sUppLex

8.3

Optischer Fluss

259

8.3.3 L¨ osung mit Hilfe der Variationsrechnung F¨ ur das Funktional 66 f (x, y, u, v, ux , uy , vx , vy ) dxdy Ω

sind die Euler-Gleichungen d ∂f − ∂u dx d ∂f − ∂v dx





∂f ∂ux ∂f ∂vx





d − dy d − dy





∂f ∂uy ∂f ∂vy

=0

(8.7)

=0

(8.8)



notwendige Bedingungen f¨ ur ein schwaches relatives Extremum. Wir haben wegen (8.6) f = (u2x + u2y + vx2 + vy2 ) + λ(uGx + vGy + Gt )2 und ∂f = 2λ(uGx + vGy + Gt )Gx . ∂u Weiter gilt ∂f = 2ux ∂ux ∂f = 2uy ∂uy  ∂f d = 2uxx dx ∂ux  ∂f d = 2uyy . dy ∂uy Die erste Euler-Gleichung (8.7) hat dann die Form 2λ(uGx + vGy + Gt )Gx = 2(uxx + uyy ) = 2∇2 u bzw. ∇2 u = λ(uGx + vGy + Gt )Gx ,

sUppLex

260

8. Bewegungsanalyse aus Bildfolgen

wobei ∇2 u = uxx + uyy der Laplace-Operator bedeutet. Anolog erh¨ alt man aus (8.8) die Gleichung ∇2 v = λ(uGx + vGy + Gt )Gy . Diese partiellen elliptischen Differentialgleichungen 2.Ordnung k¨onnen durch numerische Iterationsverfahren gel¨ ost werden. Durch die Vorgabe von Randwertbedingungen f¨ ur u und v kann die L¨ osungsmannigfaltigkeit eingeschr¨ankt werden. 8.3.4 L¨ osung mit diskreter Iteration F¨ ur die diskrete Iteration werden die Bildpunkte nur in ganzzahligen Koordinaten (i, j) mit 0 ≤ i ≤ I − 1 und 0 ≤ j ≤ J − 1 und f¨ ur ganzzahlige Zeitpunkte t = 0, 1, 2, · · · betrachtet. Der Glattheitsfehler des diskreten optischen Flusses (u(i, j), v(i, j)) im Punkt (i, j) wird wie folgt berechnet fg (i, j) =

1 ((u(i + 1, j) − u(i, j))2 + (u(i, j + 1) − u(i, j))2 + 4 (v(i + 1, j) − v(i, j))2 + (v(i, j + 1) − v(i, j))2 ).

Die ersten Ableitungen sind hier durch einfache Differenzen von Funktionswerten in benachbarten Bildpunkten approximiert. F¨ ur Randpunkte sind spezielle Festlegungen zu treffen. Der Fehler der Horn-Schunck-Bedingung ist fh (i, j) = (Gx (i, j, t) · u(i, j) + Gy (i, j, t) · v(i, j) + Gt (i, j, t))2 . Der zu minimierende Gesamtfehler ergibt sich zu f=



(fg (i, j) + λfh (i, j)).

0≤i≤I−1,0≤j≤J−1

Dabei ist t fest. Zu bestimmen sind die 2 · I · J Unbekannten u(i, j), v(i, j) so, dass f minimal wird. Hierzu werden die ersten Ableitungen des Gesamtfehlers f nach u(i, j) und v(i, j) gebildet und Null gesetzt (notwendige Bedingung f¨ ur ein Minimum).

sUppLex

8.3

Optischer Fluss

261

Wir erhalten ∂

-

fg (i, j)

i,j

∂u(i, j)

1 = − ((u(i + 1, j) − u(i, j)) + (u(i, j + 1) − u(i, j))) 2 1 + ((u(i, j) − u(i − 1, j)) + (u(i, j) − u(i, j − 1))) 2

und ∂

-

fg (i, j)

i,j

∂u(i, j)

1 = 2u(i, j)−2( (u(i+1, j)+u(i, j +1)+u(i−1, j)+u(i, j −1))) 4 = 2u(i, j) − 2¯ u(i, j).

Man beachte, dass die Unbekannte u(i, j) in den Summanden fg (i, j),

fg (i − 1, j)

und fg (i, j − 1)

auftritt. Dabei ist u ¯(i, j) = u(i + 1, j) + u(i, j + 1) + u(i − 1, j) + u(i, j − 1). Somit ergibt sich ∂f = 2u(i, j) − 2¯ u(i, j)+ ∂u(i, j) 2λ(Gx (i, j, t) · u(i, j) + Gy (i, j, t) · v(i, j) + Gt (i, j, t))Gx (i, j, t) und analog ∂f = 2v(i, j) − 2¯ v (i, j)+ ∂v(i, j) 2λ(Gx (i, j, t) · u(i, j) + Gy (i, j, t) · v(i, j) + Gt (i, j, t))Gy (i, j, t), mit v¯(i, j) = v(i + 1, j) + v(i, j + 1) + v(i − 1, j) + v(i, j − 1).

sUppLex

262

8. Bewegungsanalyse aus Bildfolgen

Aus ∂f ∂f = =0 ∂u(i, j) ∂v(i, j) folgt das Gleichungssystem (1 + λG2x )u(i, j) + λGx Gy v(i, j) = u ¯(i, j) − λGx Gt

λGx Gy u(i, j) + (1 + λG2y )v(i, j) = v¯(i, j) − λGy Gt . Hieraus folgt

u(i, j) =

u ¯(i, j)(1 + λG2y ) − λGx Gt (1 + λG2y ) (1 + λG2x )(1 + λG2y ) − λ2 G2x G2y v¯(i, j)λGx Gy − λGy Gt λGx Gy − (1 + λG2x )(1 + λG2y ) − λ2 G2x G2y

und somit u(i, j) =

(1 + λG2y )¯ u(i, j) − λGx (Gt + Gy v¯(i, j)) . 1 + λ(G2x + G2y )

Analog erh¨ alt man v(i, j) =

(1 + λG2x )¯ v (i, j) − λGy (Gt + Gx u ¯(i, j)) . 1 + λ(G2x + G2y )

Allerdings sind in dieser L¨ osung die Werte in den Punkten (i, j) von den Werten in der 4-Nachbarschaft von (i, j) abh¨angig. Die L¨osungen k¨onnen aber in den verschiedenen Bildpunkten nicht gleichzeitig berechnet werden. Deshalb wird ein iteratives Verfahren benutzt. Im Iterationsschritt 0 initialisieren wir die Werte f¨ ur u(i, j), v(i, j), z.B. mit u0 (i, j) = 0 v 0 (i, j) = 0. Im Iterationsschritt n + 1 werden dann zur Berechnung der Werte un+1 (i, j),

v n+1 (i, j)

sUppLex

8.3

Optischer Fluss

263

die arithmetischen Mittelwerte u ¯n (i, j) bzw. v¯n (i, j) des vorhergehenden Iterationsschrittes n verwendet. Wir erhalten ¯n (i, j) − λGx un+1 (i, j) = u

Gx u ¯n (i, j) + Gy v¯n (i, j) + Gt 1 + λ(G2x + G2y )

und v n+1 (i, j) = v¯n (i, j) − λGy

Gx u ¯n (i, j) + Gy v¯n (i, j) + Gt . 1 + λ(G2x + G2y )

In jedem Iterationsschritt n = 0, 1, 2, · · · werden die Werte des optischen Flusses in allen relevanten Bildpunkten berechnet. Die diskrete Berechnung der Ableitungen Gx (i, j, t),

Gy (i, j, t),

Gt (i, j, t)

geschieht folgendermaßen

Gx (i, j, t) =

Gy (i, j, t) =

Gt (i, j, t) =

1 ((G(i + 1, j, t) + (G(i + 1, j, t + 1) + 4 +(G(i + 1, j + 1, t) + (G(i + 1, j + 1, t + 1)) 1 − ((G(i, j, t) + (G(i, j, t + 1) + 4 +(G(i, j + 1, t) + (G(i, j + 1, t + 1)) 1 ((G(i, j + 1, t) + (G(i, j + 1, t + 1) + 4 +(G(i + 1, j + 1, t) + (G(i + 1, j + 1, t + 1)) 1 − ((G(i, j, t) + (G(i, j, t + 1) + 4 +(G(i + 1, j, t) + (G(i + 1, j, t + 1)) 1 ((G(i, j, t + 1) + (G(i, j + 1, t + 1) + 4 +(G(i + 1, j, t + 1) + (G(i + 1, j + 1, t + 1)) 1 − ((G(i, j, t) + (G(i, j + 1, t) + 4 +(G(i + 1, j, t) + (G(i + 1, j + 1, t)).

sUppLex

264

8. Bewegungsanalyse aus Bildfolgen

Eine andere einfachere M¨ oglichkeit ist Gx (i, j, t) = G(i, j, t) − G(i + 1, j, t) Gy (i, j, t) = G(i, j, t) − G(i, j + 1, t) Gt (i, j, t) = G(i, j, t) − G(i, j, t + 1). Randpunkte muss man gesondert behandeln. 8.3.5 Algorithmus zur Berechnung des optischen Flusses Programm 8.1

begin for j := 0 to J − 1 do for i := 0 to I − 1 do begin Berechne die Werte Gx (i, j, t), Gy (i, j, t) und Gt (i, j, t) ; u(i, j) := 0; v(i, j) := 0; end; w¨ ahle λ (z.B. λ = 10); w¨ ahle Iterationsanzahl n0 (z.B. 8 ≤ n0 ≤ 12); n := 1; while n ≤ n0 do begin for j := 0 to J − 1 do for i := 0 to I − 1 do begin u ¯ := 14 ((u(i − 1, j) + u(i + 1, j) + u(i, j − 1) + u(i, j + 1)); v¯ := 14 ((v(i − 1, j) + v(i + 1, j) + v(i, j − 1) + v(i, j + 1)); α := λ ·

Gx (i,j,t)¯ u+Gy (i,j,t)¯ v +Gt (i,j,t) ; 1+λ(G2x (i,j,t)+G2y (i,j,t))

u(i, j) := u ¯ − αGx (i, j, t); v(i, j) := v¯ − αGy (i, j, t); end; n := n + 1; end; end;

sUppLex

8.3

Optischer Fluss

265

8.3.6 Aufgaben Aufgabe 8.3.1 Wir betrachten zum Zeitpunkt t = 1 das Bild

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 G1 = G(i, j, 1) = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2

3 3 3 3 3 3 3 3

4 4 4 4 4 4 4 4

5 5 5 5 5 5 5 5

⎞ 5 5⎟ ⎟ 5⎟ ⎟ ⎟ 5⎟ ⎟ 5⎟ ⎟ 5⎟ ⎟ 5⎠ 5

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2

3 3 3 3 3 3 3 3

4 4 4 4 4 4 4 4

⎞ 5 5⎟ ⎟ 5⎟ ⎟ ⎟ 5⎟ ⎟. 5⎟ ⎟ 5⎟ ⎟ 5⎠ 5

8.3.1

und zum Zeitpunkt t = 2 das Bild ⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 G2 = G(i, j, 2) = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

Berechnen Sie iterativ u(i, j) und v(i, j) f¨ ur geeignete Bildpunkte (i, j). Aufgabe 8.3.2 Wir betrachten zum Zeitpunkt t = 1 das Bild

⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 G1 = G(i, j, 1) = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 1 1 0 0

0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

8.3.2

⎞ 0 0⎟ ⎟ 0⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

sUppLex

266

8. Bewegungsanalyse aus Bildfolgen

und zum Zeitpunkt t = 2 das Bild ⎛ 0 ⎜0 ⎜ ⎜0 ⎜ ⎜ ⎜0 G2 = G(i, j, 2) = ⎜ ⎜0 ⎜ ⎜0 ⎜ ⎝0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0

⎞ 0 0⎟ ⎟ 0⎟ ⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎟ ⎟ 0⎠ 0

Berechnen Sie iterativ u(i, j) und v(i, j) f¨ ur geeignete Bildpunkte (i, j).

sUppLex

Literaturverzeichnis [1] Abmayr, W.: Einf¨ uhrung in die digitale Bildverarbeitung. B.G. Teubner, Stuttgart 1994 [2] Alpaydin, E.: Machine Learning. The MIT Press, Massachusetts 2004 [3] Bennamoun, M., Mamic, G.J.: Object Recognition – Fundamentals and Case Studies. Springer, London 2002 [4] B¨ assmann, H., Besslich Ph. W.: Bildverarbeitung Ad Oculos. Springer, Berlin Heidelberg 2004 [5] Bergh, J., Ekstedt F., Lindberg, M.: Wavelets mit Anwendungen in Signal- und Bildverarbeitung. Springer, Berlin Heidelberg 2007 [6] Bishop, Ch.M.: Pattern Recognition and Machine Learning. Springer, New York 2006 [7] Br¨ aunl, Th., Feyrer St., Rapf, W., Reinhardt, M. : Parallele Bildverarbeitung. Addison-Wesley, Bonn 1995 [8] Br¨ aunl, Th., Feyrer St., Rapf, W., Reinhardt, M.: Parallel Image Processing. Springer, Berlin Heidelberg 2001 [9] Burger, W., Burge M. J.: Digitale Bildverarbeitung – Eine Einf¨ uhrung mit Java und ImageJ. Springer, Berlin Heidelberg 2006 [10] Davies, E.R.: Machine Vision – Theory Algorithms Practicalities. Morgan Kaufmann, San Francisco 2005 [11] Demant, Ch., Streicher-Abel, B., Waszkewitz, P.: Industrielle Bildverarbeitung – Wie optische Qualit¨ atskontrolle wirklich funktioniert. Springer, Berlin Heidelberg 1998 [12] Forsyth, D. A., Ponce, J.: Computer Vision A Modern Approach. Pearson Education, Upper Saddle River, NJ 2003 [13] Gold, St., Rangarajan, A.: A graduarted assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996 [14] Gonzalez, R. C., Woods, R. E.: Digital Image Processing. Pearson Education, Upper Saddle River, NJ 2008 [15] G¨ orz, G., Rollinger, C.-R., Schneeberger, J. (Hrsg): Handbuch der K¨ unstlichen Intelligenz. Oldenbourg, M¨ unchen 2003 [16] Haber¨ acker, P.: Praxis der Digitalen Bildverarbeitung und Mustererkennung. Carl Hanser Verlag, M¨ unchen 1995 [17] Haralick, R. M., Shapiro, L. G.: Computer and Robot Vision Volume I. Addison-Wesley, Massachusetts 1992

sUppLex

268

Literaturverzeichnis

[18] Haralick, R. M., Shapiro, L. G.: Computer and Robot Vision Volume II. Addison-Wesley, Massachusetts 1993 [19] Harris, C. G., Stephens, M.: A combined corner and edge detector. In: 4th Alvey Vision Conference, S. 147–151, 1988 [20] Haykin, S.: Neural Networks: A Comprehensive Foundation. Macmillan, New York 1994 [21] Horn, B. K. P., Schunck, B. G.: Determining optical flow. Artificial Intelligence 17, S. 185–203, 1981 [22] Huffman, D.: Impossible objects as nonsense sentence. In: R.Meltzer and D.Michie (Eds.):Machine Intelligence 6, New York: Elsevier 1971 S.295–323 [23] Ikeuchi, K., Horn, B. K. P.: Numerical shape from shading and occluding boundaries. Artificial Intelligence, 17, pp. 141–184, 1981 [24] J¨ ahne, B., Massen, R., Nickolay, B., Scharfenberg, H.: Technische Bildverarbeitung – Maschinelles Sehen. Springer, Berlin Heidelberg 1996 [25] J¨ ahne, B.: Digitale Bildverarbeitung. Springer, Berlin Heidelberg 2005 [26] Jiang, X., Bunke, H.: Dreidimensionales Computersehen – Gewinnung und Analyse von Tiefenbildern. Springer, Berlin Heidelberg 1997 [27] Klas, J.: Digitale Bildverarbeitung. moreno, Buchloe 1996 [28] Klette, R., Zamperoni, P.: Handbuch der Operatoren f¨ ur die Bildverarbeitung. Vieweg, Braunschweig Wiesbaden 1995 [29] Klette, R., Koschan A., Schl¨ uns, K.: Computer Vision – R¨ aumliche Information aus diditalen Bildern. Vieweg, Braunschweig Wiesbaden 1996 [30] Klette, R., Rosenfeld A.: Digital Geometry – Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco 2004 [31] Kopp, H.: Bildverarbeitung interaktiv. B.G. Teubner, Stuttgart 1997 [32] LeCun, Y., Cortes, C.: MNIST database of handwritten digits. http://yann.lecun.com/exdb/mnist/, Online Ressource, letzter Zugriff: Mai 2008 [33] Lehmann, Th., Oberschelp, W., Pelikan, E., Repkes, R.: Bildverarbeitung f¨ ur die Medizin. Springer, Berlin Heidelberg 1997 [34] Lowe, D.: Object Recognition from Local Scale-Invariant Features. In: ICCV., 1150–1157, 1999 [35] L¨ u, H. E., Wang, P. S. P.: A Comment on “A Fast Parallel Algorithm for Thinning Digital Patterns“. Communications of the ACM, vol.29,no.3,pp. 239–242(4), 1986

sUppLex

Literaturverzeichnis

269

[36] Mallot, H. A.: Sehen und die Verarbeitung visueller Informationen. Vieweg, Braunschweig Wiesbaden 1998 [37] Marr, D.: Vision. Freeman & Co, San Francisco 1982 [38] Nischwitz, A., Fischer, M., Haber¨ acker, P.: Computergrafik und Bildverarbeitung. Vieweg, Wiesbaden 2007 [39] Paulus, D. W. R., Hornegger, J.: Pattern Recognition and Image Processing in C++. Vieweg, Braunschweig Wiesbaden 1995 [40] Pinz, A.: Bildverstehen. Springer, Wien 1994 [41] Pitas, I.: Digital Image Processing Algorithms and Applications. John Wiley & Sons, New York 2000 [42] Radig, B.: Verarbeiten und Verstehen von Bildern. Oldenbourg, M¨ unchen 1993 [43] Roberts, L. G.: Machine Perception of Three-Dimensional Solids. In Tippet et. al. (Hg.), Optical and Electro-Optical Information Processing, Seite 159–197, The MIT Press, Cambridge Mass. 1965 [44] Russell, St., Norvig, P.: K¨ unstliche Intelligenz – Ein moderner Ansatz. Pearson Studium, M¨ unchen 2004 [45] Schmidt, K., Trenkler, G.: Einf¨ uhrung in die Moderne Matrix-Algebra. Springer, Heidelberg 2006 [46] Schunck, B. G., Horn, B. K. P.: Constraints on optical flow computation. Proc. Pattern Recognition and Image Processing Conf., Dallas, S. 205–210, 1981 [47] Soille, P.: Morphological Image Analysis. Springer, Berlin Heidelberg 2004 [48] Steinbrecher, R.: Bildverarbeitung in der Praxis. Oldenbourg, M¨ unchen 1993 [49] Tishoosh, H. R.: Fuzzy-Bildverarbeitung. Springer, Berlin Heidelberg 1998 [50] T¨ onnies, K. D.: Grundlagen der Bildverarbeitung. Pearson Studium, M¨ unchen 2005 [51] Ullmann, J.: An Algorithm for Subgraph Isomorphism Testing. Journal of ACM 23, 1976 [52] Vince, J.: Vector Analysis for Computer Graphics. Springer, London 2007 [53] Voss, K.: Theoretische Grundlagen der digitalen Bildverarbeitung. Akademie Verlag, Berlin 1988 [54] Voss, K.: Discrete Images, Objects and Functions in Z n . Springer, Berlin 1993 [55] Waltz, D.: Understanding Line Drawings of Scenes with Shadows. In P. H. Winston (Hg.), The Psychology of Computer Vision, Seite 19–91, McGraw-Hill, New York 1975

sUppLex

270

Literaturverzeichnis

[56] Winston, P. H.: K¨ unstliche Intelligenz Addison-Wesley, Bonn 1989 [57] Zimmer, W. D., Bonz, E.: Objektorientierte Bildverarbeitung – Datenstrukturen und Anwendungen in C++. Carl Hanser, M¨ unchen 1996

sUppLex

Index 21/2 D-Skizze

7, 200

Abmagerung 84 Abstandsklassifikatoren 169 Alles oder Nichts-Transformation Aperturproblem 254, 257 Aspekt Ratio 148 Aufl¨ osung 203 Basismatrizen 48 Bayes-Klassifikator 171 Bedeutungen 165 Bestrahlungsst¨ arke 233 Bewegungsanalyse 251 Bewegungstreue 257 Bild 9 Bildanalyse 4, 10 Bildaufnahme 9, 204 dynamisch 199 optischer Mittelpunkt 204 statisch 199 Bildbeschreibung 9 Bildebene 204 Bildfolge 16, 251 Bildintensit¨ at 233 Bildmatrix 15 Bildsegmentierung 10, 94 Bildverarbeitung 4, 10 Bildverstehen 4, 5 Bildwerttreue 256 Binomialoperation 27 Blendenproblem 254 Bruchlinien 241, 246 Closing 76 Co-Occurrence-Matrix 160 Constraintpropagierung 178, 244 Dehnung der Grauskala 19 Differenzoperation 29 symmetrisch 31 Dilation 67 Kantendetektion 69

83

Disparit¨ at 224 Disparit¨ atsgradient 230 Disparit¨ atsgradientenlimit 230 Disparit¨ atslimit 228 DoG-Filter 28 Doppelverh¨ altnis 217 dreidimensionale Bildinterpretation 199 Eckendetektion 39 Eigenvektor 184 Eigenwertproblem 184 eindimensional 119 Entscheidungsfunktion 168 Epipol 225 epipolare Ebene 227 epipolare Linien 227 Erosion 70 Kantendetektion 72 Euler-Gleichungen 259 Eulerzahl 154 Berechnung 154 F¨ ullungsgrad 148 Faltung 54 f¨ ur lokale Operationen 24 Separierbarkeit 35 Faltungsatz 54 Anwendung 54 Faltungskern 24 FFT 55 Fl¨ ache 146 Fluchtpunkt 206 Fourierdarstellung von Segmentkonturen 157 Fouriertransformation Anwendung 52 diskrete zweidinmensionale 47 inverse diskrete zweidinmensionale 50 schnelle 55 Freemancode 126, 146 Addition 127

sUppLex

272

Index

Drehung 128 Subtraktion 127 Umfang 146 Weg 128 Winkeldifferenz 127 Gauß’sche Fl¨ achenformel 146 Gaußoperation 28 Gebietshierarchie 132 Gebietsnachbarschaftsgraph 131, 175, 177 Gestaltsrekonstruktion 199 Glattheitsfehler 258 globale Operation 18 Gradient 36, 200 Gradientenfilter 37 Grammatik 172 attributiert 175 Graphmatching 176, 177 Grauwert¨ ubergangsmatrizen 160 Grauwertdilation 86 Grauwerterosion 86 Hauptkomponentenanalyse 180 Anwendung 188 Hauptkomponententransformation 181 Hauptpunkt 205 Helligkeit 18 Histogramm 16 bimodal 94 kumulativ 16 multimodal 94 Histogrammebnung 19 Hochpassfilter 28 homogene Koordinaten 212 homogene Transformationsmatrix 212 Rotation 213 Skalierung 213 Translation 212 Zentralprojektion 214 Homogenit¨ atsfunktion 112 Horn-Schunck-Bedingung 257 Fehlerfunktional 258 Horn-Schunck-Verfahren 257

Houghtransfermation Geraden 137 Kreise 141 Parameter 136 Hyperebene 168

136

inverses Bild 19 Irradianz 233 isolierter Punkt 97 isomorphe Graphen 176 k-nearest neighbour 189 Kantendetektion 28, 121 Kantenmarken 242 Kantenverd¨ unnung 120 Kantenverfolgung 120, 125 Kostenfunktion 130 lokale Wegkr¨ ummung 129 Suchen von Wegen 128 Suchverfahren 130 Kern 119 Kernpunkt 119 Klassen 166 Klassifikation 165 kontextabh¨ angig 165, 175 kontextunabh¨ angig 165 linear 168 numerisch 166 statistisch 170 syntaktisch 172 Klassifikation von Graphen 175 Knotenmarken 242 Knotenmarkierungsalgoithmus 244 Knotentypen 242 Kompaktheit 147 Komplement¨ arkomponenten 103 Komponenten 103 Komponentenzerlegung 103 Kontrast 18 konvexe H¨ ulle 83, 149 Korrespondenzproblem 224, 254 korrespondierende Punkte 224 Kovarianzmatrix 184 Lambertsche Oberfl¨ ache

232, 234

sUppLex

Index

273

Lambertsche Reflexion 233 Laplaceoperation 34 Lauf 152 Laufl¨ angenkodierung 152 Fl¨ ache 153 Schwerpunkt 153 Lernphase 169 Lernverfahren 165 Levenshtein-Abstand 174 Linienzeichnung 240 lokale Operation 17 lokale Strukturmatrix 37 lokaler Verschiebungsvektor 252 lokales Verschiebungsvektorfeld 253 approximative Berechnung 254 Maschinelles Lernen 165 Matchen 135 Maximum-Likelihood-Klassifikator 171 Medianoperation 39 Mengennachbarschaft 112 Merkmale statistisch 160 Merkmalsvektor 166 Minimum-Distance-Klassifikator 169 Mittelwertoperation 26 MNIST Datenbank 188 Momente 149 ahnlichkeitsinvariant 152 ¨ Fl¨ ache 149 normiert 151 Orientierung 152 rotationsinvariant 152 Schwerpunkt 150 translationsinvariant 150 zentriert 150 Morphologische Operationen 67 f¨ ur Grauwertbilder 85 Muster 167 Mustererkennung 165 Nachbarn 96 Nachbarschaft 96 4-Nachbarschaft

97

6-Nachbarschaft 98 8-Nachbarschaft 97 Diagonal-Nachbarschaft 97 Nachbarschaftsstruktur 96 Nearest-Neighbour-Klassifikator Normalenvektor 200, 232, 235

170

Oberfl¨ ache diffus 235 Lambertsche 234 matt 234 Orientierung 201 spiegelnd 235 Verdeckungskante 238 Objekt Oberfl¨ ache 199 sichtbare Oberfl¨ achen 200 Objekterkennung 10, 145 Objektmerkmale 145 geometrische 146 Invarianten 146 Opening 76 Anwendungen 81 optische Abbildung 201 inverse 202 optischer Fluss 255 Algorithmus 264 diskrete Iteration 260 Gesamtfehler 260 Orientierung 152 Ortsfrequenzen 53 PCA 180 Photogrammetrie 205 Polyederobjekte 240 Projektionszentrum 204 Punktoperation 17 Quadtree

118

Radianz 233 Rand 119 Randpunkt 119 Rangfolgeoperationen Raumwinkel 233

38

sUppLex

274

Index

Reflektivit¨ atsgleichung 237 L¨ osung 238 Reflektivit¨ atskarte 236 Region Growing 105, 115 Relationalstrukturen 158 Relationen zwischen Segmenten Relaxation 176 diskret 177 kontinuierlich 179 Richtung 126 Richtung zur Lichtquelle 232 Robertsoperation 35 Rundheit 147

Strahlungsfluss 233 Szene 9 dynamisch 199 statisch 199 Szenenbeschreibung 9 134

Schatten 246 Schattierung 231 Schwellwertoperation 20, 94 Schwerpunkt 150 Segmentierung 94 Algorithmen 115 Definition 113 kantenorientiert 119 modellabh¨ angig 134 punktorientiert 94 regionenorientiert 112 Sehachse 205 Shape from contour 240 Shape from focus 247 Shape from motion 247 Shape from shading 231 Shape from Stereo 222 Shape from structured light 247 Shape from texture 247 Shape from X 201 SIFT-Merkmale 28 Skelettierung 84, 122 L¨ u Wang 122 morphologische Operationen 84 Sobeloperation 32 Split-and-Merge-Algorithmus 116 Sprache 173 Spurpunkt 205 Standardstereogeometrie 222 Stereo 222 Kameramodell 222 Korrespondenzproblem 224 Strahlungsdichte 233

Tangentialebene 200 Teilverh¨ altnis 217 Textur 159 statistisch 160 strukturell 160 Texturmerkmale 160 Tiefpassfilter 25 Umfang 146 Umgibtgraph 133 umschreibendes Rechteck achsenparallel 148

148

Variationsrechnung 259 Verbundenheitsrelation 99, 102 Verschwindungsebene 205 Waltz-Algorithmus 241, 244 Erweiterungen 245 Weg 99 Weltkoordinaten 199 Zeilenkoinzidenzverfahren 106 Zentralprojektion 201, 204, 251 bildzentriert 210, 251 Distanz 205 Geraden 205 homogene Koordinaten 214 homogene Transformationsmatrix 214 Invariante 217 Inverse eines Punktes 215 kamerazentriert 208, 251 Koordinaten 208 parallele Geraden 206 Rekonstruktion 3D-Information 215 Zerlegung einer Nachbarschaftsstruktur 101 zusammenh¨ angende Teilmenge 99 maximal 103

sUppLex