Bildverstehen

Grundlagen Bilderkennung und Bildverstehen.

Definition

...ist eines der kompliziertesten informatischen Gebiete. Bildverarbeitung und Bildverstehen stehen eng beieinander. Dabei ist das Bildverstehen eher der künstlichen Intelligenz zuzuordnen. Bildverstehen ist ein Prozess, welcher als Ausgabe eine Folge von Beschreibungen ausgibt. Diese hängen natürlich extrem vom Bild und der dazugehörigen Fragestellung ab.

Bildverstehen ist die Rekonstruktion und Deutung einer Szene anhand von Bildern, so dass mindestens eine der folgenden operationalen Leistungen erbracht werden kann:

Grundbegriffe

Das Systemmodell nach Marr

Bild < primiäre Skizze < 2 1/2D Skizze < 3D-Modellrepräsentation

Bild digitales Rasterbild mit radiometrischen Eigenschaften jedes Bildpunktes
primäre Skizze erster Eindruck - Datenmenge sinnvoll auf Wesentliche reduzieren
2 1/2 D Skizze Geometrische und photometrische Eigenschaften der Oberfläche, wie Tiefeninformation, Konturen oder Normalvektoren,partielle Form- und Geomiekonstruktion
3D-Modell Integration mehrerer 2 1/2 D Skizzen, Zerlegung in verallgemeinerte Zylinder, Aussagen über verdeckte Teile, Szenenbeschreibung

Modell

Repräsentationsebenen

Weltphyikalische Objekte mit Attributen, Objektkonfiguration, Bewegung der Objekte
Szene3D Ausschnitt der Welt und bestimmter Zeitpunkt
Bild2D Abbild einer Szene
BildbeschreibungBottum-up, 2D Bildelemente
SzenenbeschreibungInterpretation der Szenenelemente
WeltbeschreibungTop - down mit Vorwissen

Bildvorbereitung

...ist Grundlage zur Merkmalsextraktion und Bildsegmentierung. Es sollen Fehler im Bild korrigiert oder das Bild aufbereitet bzw. verbessert werden.

Dabei gibt es Punktoperationen, lokale Operationen und globale Operationen. Bei lokalen Operationen wird immer nur ein Teilbereich betrachtet, welcher meistens quadratisch gewählt wird. Dagegen ist bei globalen Operationen ein Ausgabebildpunkt von allen Eingangsbildpunkten, sprich den ganzen Originalbild, abhängig.

Punktoperationen

Dehnung der GrauskalaMultipikation einer Kontrast-und Addition einer Helligkeitskonstante (+/-), damit Invertierung)
Lineare Dehnung der GrauskalaDie Grauskala wird via Kontrast und Helligkeit so modifiziert, dass das ganze Spektrum ausgenutzt wird.
Binarisierung/SchwellwertbildungTrennen von bestimmten Objekten vom Hintergrund
Farbtransformationdie drei Farbauszüge R,G,B werden modifiziert
Hintergrundsubtraktiones wird ein zweites Bild, wo nur der Hintergrund aufgenommen wurde, subtrahiert)
MasikierungExtraktion semantisch bedeutsamer Bildteile durch eine Bitmaske)
Geometrische Transformationbei Vergleich unterschiedlich großer Bilder Ortskoordinatentransformation o.ä.

lokale Operationen

Lineare Faltung

Mit der Faltung lassen sich eine Vielzahl von Filtern (Hoch- und Tiefpassfilter) realisieren. Dabei wird ein LxM große Matrix benutzt, um den aktuellen Bildpunkt in Abhängigkeit von den umliegenden Punkten zu berechnen.

Die lineare Faltung berechnet die Werte des Ausgangsbildes aus einer rechteckigen (die Matrix H) Umgebung des Eingangsbildes. Die Eigenschaften der Faltungsoperation werden durch den Faltungskern (die Matrix H) bestimmt

Zeilen und Spalten der Matrix sind in der Bildverarbeitung immer kleiner als die des Eingangsbildes. Ausserhalb des Eingangsbildes liegende Punkte werden nach verschiedenen Verfahren gefüllt (Bereich ja für Matrixoperation notwendig)

Ausgangsbild

Eingangsbild Graustufe

Mittelwertoperator (Tiefpaßfilter)

3x3 Matrix mit 1/9 gefüllt zur Glättung der Grauwerte.. verstärkt tiefe Ortsfrequenzen und unterdrückt hohe. Somit verschinden kleine Grauwertspizen. Gleichmäßig helle Bildteile bleiben unverändert, Kanten werden aber verwischt. Es kann mit diesem Operator das Rauschen verringert werden. Dabei gehen aber andere relevante Informationen verloren.

Tiefpassfilter

Ausgangsbild durch Tiefpassfilter

Laplace Operator (Hochpaßfilter)

Der Laplace hebt Grauwertdifferenzen hervor und dient zur Kantenhervorhebung). Er unterdrückt tiefe Ortsfrequenzen und hebt hohe hervor. Dadurch verschwinden gleichmäßig helle Bildanteile. Kanten werden somit betont.

Hochpassfilter

Ausgangsbild durch Hochpassfilter

Anhebung von Kanten in eine Vorzugsrichtung

.. durch je eine Faltungsmatrix für N,S,NO und SO-Richtung

Sobeloperator

Differenzbildung je zur übernächsten Zeile, um kleine Störungen zu umgehen.

...kleine Störungen benachbarter Zeilen / Spalten gehen nicht in das Ergebnis ein. Der Sobeloperator dient auch zur Kantenhervorhebung.

Sobeloperator

Gradient

Der Gradient ist ein weiteres Maß für die Uneinheitlichkeit in der lokalen Grauwertverteilung. Der Gradient-Operator ist eine Formel, welche eine Faltungsmatrix (z.B. einen Soebeloperator) einbezieht. Der Gradientoperator ist somit ein richtungsunabhängiger Operator, welcher aber nicht linear ist.

Rangfolgeoperationen

Rangfolgeoperationen basieren darauf, daß die N Bildpunkte in einer vorgegebenen lokalen Umgebung zu einem Bildpunkt in Abhängigkeit von ihrem Grauwert sortiert werden.

Minimaloperation

Entfernt Spitzen hoher Grauwerte und unschaft zu machen, aber vergrößert Flecken niederer Grauewerte)

Maximaloperation

Entfernt kleine Flecken niedriger Grauwerte, aber vergrößert Spitzen hoher Grauwerte

Medianoperation

Enfernt punktförmige Gebilde ohne unscharf zu machen, es entstehen keine neunen Grauwerte, dünne Linien können verschwinden)

globale Operationen

Um ein Problem zu lösen, ist es manchmal notwendig ein mathematisches Objekt in ein anderes Objekt zu transformieren und verwandtes Problem an diesem neu transformierten Objekt zu lösen. Dies wird im Besonderen in der Bildvererarbeitung genutzt, da es verschiedene Ansätze gibt, nach denen Berechnungen, um ein vielfaches einfacher werden.(Diskrete 2D-Fouriertransformation)

Mathematische Morphologie (Lehre der Form)

Beispielbild für die Erosion und Dilatation

Binarisiertes Ausgangsbild

Eingangsbild ist das binarisiertes Ursprungsbild (Schwellwertbildung)

Jedes Rasterbild ist als Teilmenge von Z^n darstellbar. Binärbilder werden als Teilmengen von Z^2, bestehend aus Ortskoordinaten der Bildpunkte beschrieben. Dagegen werden Grauwert- oder zeitinvariante Binärbilder in Z^3 aus Ortskoordinaten und der Zeit bzw. dem Grauwert gebildet. Viele komplexe Bildverarbeitungsalgorithmen lassen sich auf folgende elementare Operationen zurückfühen.

Dilatation (X+B)

Die Dilatation fügt einem Bild X ein Strukturelement B zu. Deshalb ist es auch eine Bildverstärkende bzw. Bildverdickende Operation. Es ist möglich Teilchengruppen zu vereinigen, Löcher zu füllen oder Risse zu schliessen. Eine sehr einfache Art der Kantendetektion ist (X+B)\X.

Dilatation

Bild nach Mehrfachanwendung der Dilatation (Beachte die Pixelzunahme)

Erosion (X-B)

Die Erosion ist das Gegenstück der Dilatation und entfernt die passenden Bildpunkte. Die Erosion vermindert somit die Bilddaten.

Anders gesagt, findet die Erosion Bildpunkte, die mit einem speziellem Muster von Elementen umgeben sind. Bei de Erosion werden schmale Stellen und kleine Objekte, deren Größe kleiner als die des Strukturelementes B ist, vollständig eliminiert. Die Erosion dient auch zur Kantenfindung.

Erosion

Bild nach Mehrfachanwendung der Erosion (man beachte die Pixelminderung)

Closing

Mehrfach angewandtes Closing (Beachte verschwundenen Gitarrenhals)

Von diesen beiden Operationen werden das Opening ((X-B)+B) und das Closing ((X+B)-B) abgeleitet. Dabei bewirkt das Opening eine Eliminierung von im Verhältnis zum Strukturelement B kleinen Teilmengen des Bildes X. D.h. schmale Verbindungen oder auch alleinstehende Mengenelemente werden gelöscht. Dagegen werden beim Closing kleine Einschnitte und Zwischenräume geschlössen.

Anwendungen

Dies sind iterierende Operationen, bei denen die gleiche Operation mit mehreren Strukturelementen hintereinander angewendet wird.b

Bildsegmentierung

Einleitung

Segmentierung bedeuted, das Bild in sinnvolle Bildteile aufzuteilen. Ziele der Segmentierung sind unter anderem

Arten von Segmentierung

Punktorientierte Segmentierung

Die einfachste Form der Segmentierung ist das Schwellwertverfahren. Ein Bildpunkt des Ausgangabildes wird auf 1 gesetzt, falls der Bildpunkt des Eingangsbildes einen bestimmten Wert übersteigt. Im Histogramm erkennt man oft ein oder mehrere Extremwerte. Zwischen den Extremwerten liegen die sinnvollsten Schwellwerte, da die lokalen Minima die Stellen darstellen, welche Vorder- und Hintergrund voneinander trennen. Da bei den meisten Bildern aber viele Extremwerte (multimodale Histogramme) sichtbar werden, treten natürlich Überschneidungen auf. Deshalb reicht die Schwellwertbildung auch nur in den seltesten Fällen für eine akzeptable Segmentation aus.

Mathematische Grundlagen der Bildsegmentierung

Nachbarschaftsrelationen

Zwei Punkte sind verbunden, wenn es einen Weg zwischen diesen gibt. Eine nichtleere Teilmenge einer Nachbarschaftsstruktur heißt zusammenhängend (Gebiet, Region), falls zwei beliebige Punkte der Teilmenge miteinander verbunden sind.

Eine Menge von untereinander diskunkten Gebieten der Nachbarschaftsstruktur heißt Zerlegung, wenn die Vereinigung aller Gebiete wieder das Gesamtbild ergibt. Die durch die Verbundenheitsrelation erzeugten Äquivalenzklassen heissen Komponenten. Die Komponenten sind die maximal zusammenhängenden Teilmengen des Bildes.

Bestimmung von Komponenten

Ein Algorithmus errinnert an die Tiefensuche. Die Komponenten werden nacheinander gefunden. Ein anderer ist das Zeilenkoinzidenzverfahren.

Gebietsbasierte Segmentierung

Mit dem Region Growing Verfahren werden die Komponenten bestimmt. Es können mehrere Startpunkte (Saatzellen) i, Bild festgelegt werden, von denen ausgehend die Segmentierung erfolgen soll. Falls sich im Laufe des Algorithmus zwei Gebiete berühren sollte, wird das Homogenitätskriterium überprüft, um eventuell die Gebiete zu einem zu vereinigen.

Ein weiterer Ansatz ist der Split and Merge Algorithmus. Bei diesem Algorithmus wird in der Splitphase das Bild rekursiv solange in Teilgebiete zerlegt, bis jedes Teilgebiet das Homogenitätskriterium erfüllt. In der Merge Phase werden nun diejenigen Teilgebiete die das gleiche Homogenitätskriterium erfüllen und benachbart sind, zu einem Gebiet zusammengefasst.

Kantenorientierte Segmentierung

Das Ziel dieser Art der Segmentierung ist das Auffinden von Randkanten (Randwege oder Konturen) von Gebieten. Dazu gehören folgende Aufgaben:

Ein Gebietsnachbarschaftsgraph zeigt in Form eines Graphen, wie die Segmente in welcher Hierachie im Bild liegen. Der Umgibtgraph zeigt dagegen wunderbar auf, welche Gebiete wie eingeschlossen sind.

Modellabhängige Segmentierung

Merkmale von Objekten

Zur automatischen Erkennung von Bildern sind Verfahren notwendig, welche die Merkmal von Objekten extrahieren können. Diese Merkmale dienen zur charakteristischen Beschreibung von Objekten und der wesentlichen Unterstützung bei der Objekterkennung. Voraussetzung ist ein segmentiertes Bild, wo für einzelne Segmente die Merkmale berechnet werden können. Mit Hilfe der gewonnenen Merkmale will man die Segmente bestimmten Objekten zuordnen können. Um dies zu erreichen, sind zwei fast unvereinbare Kriterien notwendig:

Geometrische Merkmale

Momente

...dienen zum Finden von invarianten Merkmalen. Momente erster Ordnung sind die Merkmale, die nicht translationsinvariant sind, d.h. die von der Position des Objektes im Bild abhängig sind.

Momente erster Ordnung

Zentrierte Moment(p,q) - ter Ordnung sind invariant gegenüber Translation. Das normierte zentrierte Moment(p,q) - ter Ordnung ist invariant gegenüber Ähnlichkeitstransformation.

Lauflängenkodierung

Ein Lauf ist ein Tripel (s,z,n), wobei S die Spalte, Z die Zeile und n die Länge eines zusammenhängenden Bereichs von horizontal aneinandergrenzenden Objektpunkten ist. Unter einer Lauflängenkodierung versteht man eine Menge von solchen Läufen. Mit Hilfe der Lauflängenkodierung lassen sich sehr einfach die Momente berechnen.

Eulerzahl

Die Eulerzahl E ist definiert durch E = B - L. B ist die Anzahl der Objekte und L die Anzahl an Löchern (Hintergrund, der von einem Objekt umgeben wird). Die Eulerzahl wird ermittelt, indem mehrere 2x2 Masken über das Bild geführt werden und die jeweiligen Trefferhäufigkeiten benutzt werden, um mit Hilfe einer Formel die Eulerzahl zu berechnen.

Relationalstrukturen

...erlauben eine Formbeschreibung auf der Basis lokaler Beschreibungselemente und Ihrer Beziehung untereinander und werden als Graphen dargestellt.

Mustererkennung

Ziel ist es, den durch Segmentierung gefundenen Objekten, Bedeutungen zuzuweisen. Dabei können einzelne Objekte, Gruppen oder auch Relationen zwischen Objekten die Grundlage sein. Das Grundprinzip ist einfach. Aus den berechnetet Objekten oder Gebieten werden Merkmale extrahiert, welche durch Training und bekanntes Wissen klassifiziert und mit einer bestimmten Bedeutung versehen werden.

Numerische Klassifikation

Ein Objekt wird durch einen Merkmalsvektor beschrieben. Bei einer numerischen Klassifikation wird jeder Vektor einer bestimmten Klasse K zugeordnet.

Lineare Klassifikation

Einordnung durch eine Entscheidungsfunktion

Abstandsklassifikatoren

Klassifizierung durch "geometrischen Abstand" des Objektes zu den Klassen Minimum - Distance - Klassifikator sowie Nearest - Neighbour - Klassifikator

statistische Klassifikation

Hier wird die Wahrscheinlichkeitsrechnung mit bedingten Wahrscheinlichkeiten genutzt. Ein Klassifikator aus dieser Gruppe ist der Maximum - Likelihood - Klassifikator.

Kontextabhängige Klassifikation

Ein Objekt wird hier nicht allein klassifiziert, sondern im Verbund bzw. im Kontext mit anderen Objekten. Somit findet hier eine Klassifikation von Strukturen (Graphen mit Objekten oder Kanten als Knoten und Nachbarschaftsrelationen) statt. Es gibt zwei Verfahren:

Diskrete Relaxation

Es wird von einer Segmentierung einer Nachbarschaftstruktur und einem Gebietsnachbarschaftsgraphen ausgegangen. Durch ein iteratives Verfahren wird versucht die Bedeutungen B sinnvoll unter Beachtung der Kanten zuzuordnen.

Kontinuierliche Relaxation

Hier wird jedem Objekt eine Wahrscheinlichkeit zugeordnet, die die Zugehörigkeit zu den entsprechenden Klassen spezifizieren soll. Im Folgenden wird iteriert und in jedem Durchgang diese Wahrscheinlichkeiten angepasst. Dabei werden die Nachbarobjekte betrachtet und überprüft, ob die Klassifizierung mit dem aktuellen Objekt kompatibel ist oder nicht. Sind die benachbarten Objekte kompatibel, so werden die entsprechenden Wahrscheinlichkeiten der Klassenzuweisungen erhöht. Sind sie inkompatibel, so werden die Wahrscheinlichkeiten verringert. Bei Erfüllung einer bestimmten Bedingung (Abbruchbedingung), wird die Iteration beendet.

Dreidimensionale Bildinterpretation

...ist die Gestaltsrekonstruktion dreidimensionaler Objekte. Grundlage sind visuelle Eingangsdaten von visuellen Sensoren (eine oder mehrere Kameras), die eine statische oder dynamische Szene abbilden.

Generierung einer 2 1/2 D-Skizze

Diese Skizze ist ein wichtiger Zwischenschritt auf dem Weg zur Gestaltsrekonstruktion. Sie beschreibt eine unvollständige räumliche Information der sichtbaren Oberflächen eines Objektes. Für die Erstellung der Skizze gibt es verschiedene Vorgehensweisen. Einige sind eng an der meschlichen Wahrnehmung orientiert. Die meisten dieser Prinzipien kann man isoliert betrachten, hat sich der Begriff Shape from X (X steht für die jeweilige Methode) entwickelt.

Möglichkeiten der 2 1/2 D - Repräsentation

Formale Präzisierung

Der Vektor zum aufzunehmenden Punkt ist der zu messende Szenenwert. Er wird über die dreidimensionale Umgebung des Sensors aufgenommen. Somit stellt dies eine Abbildung eines Vektors (x,y,z) in die reellen Zahlen dar. Szenenwerte können u.a. Grau- oder Farbwerte bei Kameras oder Entfernungen bei Lasern sein.

Eine optische Abbildung A ist vereinfacht nichts anderes als eine Projektion der Szene S auf ein Bild E, also E = A(S).

Probleme

Szenenobjekte sind nun anhand der Bilder wieder als dreidimensionale Körper darzustellen. So ist es notwendig die inverse Abbildung von A zu untersuchen. Eine eindeutige zuordnung ist aber i.a. nicht möglich. Aus diesem Grund ist das Problem beinahe immer nur eingeschränkt lösbar

Drei naheliegende Grenzen der Gestaltsrekonstruktion

Shape from contour

Einführung

Beliebige dreidimensionale Objekte können anhand ihrer Konturen erkannt und lokalisiert werden. Voraussetzung dafür ist, dass ausreichend geometrische Modelle der Objekte vorhanden sind. Der Walz-Algorithmus versucht, zweidimensionale Linienzeichnungen dreidimensional zu interpretieren.

Die Linienzeichnung ist ein ungerichteter Graph, welche aus Knoten und Abschnitten besteht. Während der 3d-Interpretation werden den Knoten und Abschitten unterschiedliche Bedeutungen zugeordnet. (Markierung durch Marken an den jeweiligen Bildelementen)

Bildelemente mit Bedeutung können nicht wahllos zugeordnet werden. Es müssen dabei die bestehenden Relationen (physikalische Fakten) zwischen den Bedeutungen beachtet werden. Aufgabe ist es nun, konsistente Markierungen für eine 2d-Linienzeichnung zu finden oder wenigstens die Ausgangsmenge von Markierungen durch Entfernen der inkonsistenten Markierungen stark einzuschränken.

Annahmen

Kantenmarken

Es gibt vier Möglichkeiten:

Knotenmarken

Knoten können aufgrund der einlaufenden Kanten ebenfalls mit Marken versehen werden. Von der kombinatorischen Menge der theroretisch möglichen Anzahl ist aber nur ein geringer Teil (18) möglich.

Da an jedem Knoten genau drei Flächen zusammenstoßen, unterteilt ein Knoten den 3d-Raum in acht Oktanten. Stellt man sich nun ein,zwei.. oder sieben Oktanten ausgefüllt vor und und den Betrachter im freien Oktanten, dann erhält man alle möglichen Knotentypen. Der Fall das nur 2, 4 oder 6 Oktanten ausgefüllt sind, kann nicht eintreten.

Es gibt vier Knotentypen:

Nun hat man aber noch nicht die Marken der Kanten berücksichtigt, die in den jeweiligen Knoten zusammenlaufen. Physikalisch sind von den rein kominatorisch Möglichen 208 nur 18 möglich.

Walz Algorithmus

Ziel: Finde für die Linienzeichnung eine Zuordnung der Marken und Knoten so, dass jeder Knoten eine zulässige Markierung im Sinne der 18 Möglichkeiten besitzt und die Marken der zusammengesetzten Kantenstücke übereistimmen.

Eine weitere Annahme soll sein, das jeder Gegenstand im Raum nur aufgehängt ist, d.h. die Hintergrundbegrenzungslinien sind nur Pfeilmarken.

Hinweise zur Markierung

Der Knotenmarkierungsalgorihmus Waltz

Ohne die Annahme, dass Objekte frei im Raum hängen, wären die Interpretationen nicht mehr eindeutig. Durch Einführen von Schatten können solche Mehrdeutigkeiten beseitigt werden. Dazu benötigt man aber weitere Kantenmarkierungen für die Schatten und Bruchlinien. Die Anzahl der zulässigen Markierungen erhöht sich dann aber sprunghaft!

Quellen

Quelle: Skript von Dr. Johannes Steinmüller an der Technischen Universität Chemnitz

Links

Das Programm habe ich geschrieben, um einige Filter ausprobieren zu können. Alle obigen Bilder sind Screenshots des Programms. Es dient zum ausprobieren. Eine kleine Textfile mit Hilfe wird beigelegt.

Bildverarbeitungstool