Grundlagen: Bildverarbeitung / Objekterkennung

Technische Universitat Munchen

Fakultat fur Informatik

Seminar Thesis

Betreuer: Jan Bandouch

Abgabedatum: 05.07.2006

von

Julia Peterwitz

Grundlagen der Bildverarbeitung und Objekterkennung

Fakultat fur Informatik

Technische Universitat Munchen, Mai 2006

Master of Science

Julia Peterwitz

ABSTRACT

Diese Arbeit stellt einige Grundlagen der Bildverarbeitung vor. Es geht um Stan-dardmethoden die zum Verstehen aktueller Forschungsarbeiten notig sind.Als erstes wird auf die Segmentierung eingegangen. Es gibt drei große Gruppenvon Segmentierungsmethoden: Thresholding, Kanten-basierte und Regionen-basierteSegmentierung.Des Weiteren kann ein Bild nach bestimmten Merkmalen wie Kanten, Ecken oderganzen Templates durchsucht werden. Hierzu werden mehrere Standard-Detektorenvorgestellt.Zur Objekterkennung gehort die Klassifizierung der Objekte. Als Klassifizierung oderKlassifikation bezeichnet man einen Vorgang oder eine Methode zur Einteilung vonObjekten in Klassen oder Kategorien.Weiterhin geht diese Arbeit auf die Verarbeitung von gefundenen Merkmalen in derBildsequenz ein. Der Kalman-Filter trifft anhand bisheriger Koordinaten eine Vorher-sage fur die nachsten Koordinaten des Merkmals. Wahrend dessen wird die nachstePosition des Merkmals im Folgebild gesucht. Im nachsten Schritt wird die Vorhersagemit dem Suchergebnis fusioniert, um eine hohere Genauigkeit zu erreichen.Eine Optical-Flow Anwendung analysiert die Bewegungen die in einer Bildsequenz.Fur jedes Bildelement wird ein Bewegungsvektor berechnet, der die Bewegung inBildkoordinaten ausdruckt. Diese konnen unter anderem als Grundlage fur eine Be-wegungsschatzung in der realen Welt dienen.

KEYWORDS: Segmentieren, Kantendetektoren, Eckendetektoren, Templatematch-ing, Kalman-Filter, Optical-Flow

ii

Inhalt

1 Einleitung 1

2 Segmentierung 32.1 Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1.1 Thresholding Techniken . . . . . . . . . . . . . . . . . . . . . 32.1.2 Schwellwertbildung . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Region-Growing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Merkmalsextraktion 73.1 Kantendetektoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.1.1 Sobel Kantendetektion . . . . . . . . . . . . . . . . . . . . . . 83.1.2 Canny Kantendetektion . . . . . . . . . . . . . . . . . . . . . 9

3.2 Eckendetektoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2.1 Moravec’s Corner Detector . . . . . . . . . . . . . . . . . . . . 103.2.2 Harris Corner Detector . . . . . . . . . . . . . . . . . . . . . . 11

4 Objekterkennung 154.1 Templatematching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.2 Klassifizierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5 Verfolgung von Merkmalen/Objekten uber Bildsequenzen 195.1 Kalman-Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195.2 Optical-Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6 Zusammenfassung 26

iii

Kapitel 1

Einleitung

In dieser Arbeit sollen die Grundlagen der Bildverarbeitung vermittelt werden.

Die Bildverarbeitung nutzt die Mittel der Signalverarbeitung zur Aufbereitung und

Speicherung von visuellen Informationen. Die Manipulation und anschließende Darstel-

lung gehoren nicht zur Bildverarbeitung sondern zur Bildbearbeitung. Die Segmen-

tierung, die Merkmalsextraktion und die Objekterkennung sind Teilbereiche der Bild-

verarbeitung.

Diese Arbeit wird zuerst auf die Segmentierung von Bildbereichen eingehen. Im Zuge

dessen werden die Verfahren des Thresholding und des Region-Growing erlautert,

welche zur Segmentierung von Bildern eingesetzt werden.

Als nachstes geht die Arbeit auf die Merkmalsextraktion in digitalen Bildern ein.

Zwei wichtige Merkmale, die naher betrachtet werden, sind Kanten und Ecken. Hi-

erzu werden der Canny Kantendetektor und der Harris Corner Detektor vorgestellt.

Im Kapitel zur Objekterkennung wird zuerst das Templatematching Verfahren erklart,

welches Objekte beliebiger Form und Schattierung im Bild lokalisieren kann. An-

schließend wird auf die Erkennung der Objekte eingegangen. Das geschieht mittels

Klassifizierung der Objekte im Merkmalsraum.

Abschließend geht die Arbeit auf zwei wichtige Verfahren ein, um Merkmale bzw.

Objekte in der Bildsequenz zu verfolgen. Der Kalmanfilter sorgt fur die Kontinuier-

lichkeit von Messwerten und kann deshalb als Unterstutzung zur Objektverfolgung

verwendet werden. Der Optical-Flow Algorithmus hingegen liefert ein Feld von

1

Geschwindigkeitsvektoren fur Punkte in der Bildsequenz und stellt somit auch eine

Art Verfolgung von Merkmalen dar.

Anwendung finden diese grundlegenden Bildverarbeitungstechniken in vielen moder-

nen Verfahren zur Analyse von Bildern und Bildsequenzen. Oft werden sie in Ihrem

Ablauf modifiziert und dem Umfeld in dem sie vorkommen angepasst, jedoch ist die

Grundidee der Standardalgorithmen meist noch zu erkennen. Aus diesem Grund ist

es wichtig Einblick in die Standardmethoden zu haben. Ein besseres Verstandnis fur

aktuelle Forschungsarbeiten wird somit ermoglicht.

2

Kapitel 2

Segmentierung

Es gibt viele Techniken Bildern in Bereiche aufzuteilen. Die vollstandige und

uberdeckungsfreie Zerlegung nennt man Segmentierung. Es gibt drei große Gruppen

von Segmentierungsmethoden: Threshold-basierte, Kanten-basierte und Regionen-

basierte Segmentierung. Das Thresholding und das Region-Growing Verfahren sollen

im Folgenden naher betrachtet werden.

2.1 Thresholding

Thresholding ist die Anwendung eines Schwellwerts auf ein Grauwertbild (siehe

Abbildung ??). Dabei konvertiert eine nicht-lineare Funktion das Grauwertbild in ein

binares Bild in dem jedes Pixel entweder weiß oder schwarz eingefarbt wird. Je nach

dem ob der untersuchte Pixelwert uber oder unter dem Grenzwert liegt.

Das Thresholding gehort zur histogrammbasierten Segmentierung da sich der Gren-

zwert meist an den Extremwerten des Histogramms orientiert [Ton05, S.197-S.208].

Thresholding ist einfach umzusetzen und benotigt wenig Rechenleistung. Somit ist

es gut in Echtzeitanwendungen einsetzbar.

2.1.1 Thresholding Techniken

Thresholding kann auf verschiedene Arten eingesetzt werden: mit einem oder

mehreren, mit statischen oder dynamischen Schwellwerten.

Wird mehr als ein Schwellwert benutzt, bildet jeder Schwellwert die Ober- oder Un-

3

Abbildung 2.1: Histogramm Applet [FPWW03]

tergrenze eines Farbbereiches im Histogramm. Mehrere Schwellwerte fuhren folglich

nicht mehr zu Binarbildern, sondern die resultierenden Bilder haben so viele Farben,

wie die Anzahl der Bereiche im Histogramm.

Wahrend die einfachen Thresholding-Algorithmen einen globalen Schwellwert fur alle

Pixel verwenden, verandert sich beim Adaptive Thresholding bzw. Dynamic Thresh-

olding der Schwellwert wahrend des Prozesses. Dazu wird jeweils der Mittel- oder

Medianwert in einem ausreichend großen Bereich um das betrachtete Pixel berech-

net. Dieser Wert wird dann zur Anpassung des Thresholds benutzt[Rad05]. Dies

kann sinnvoll sein bei starken Beleuchtungsunterschieden im Bild. Je nach Beleuch-

tungssituation passt sich der Schwellwert den Gegebenheiten an [FPWW94]. Das

resultierende Bild ist binar und Beleuchtungsunterschiede sind durch das dynamische

Anpassen des Schwellwerts ausgeglichen worden.

2.1.2 Schwellwertbildung

Um moglichst gute Schwellwerte manuell zu bestimmen werden die Grenzen der

Bereiche vom Benutzer im Histogramm gesetzt. Das resultierende Threshold-Bild

wird dem Anwender in Echtzeit angezeigt, sodass er die Grenzen gegebenenfalls an-

passen kann. Das automatische Bestimmen von Schwellwerten erfolgt uber die Ex-

4

tremwerte des Histogramms. Es werden also die Stellen gesucht an denen die erste

Ableitung des Histogramms gleich Null ist. Die gefundenen lokalen Minima sind

potentielle Schwellwerte. Die eigentlichen Schwellwerte mussen als Nebenbedingung

noch zwischen zwei lokalen Maxima im Histogramm liegen. Die Extremwertbestim-

mung kann mit Hilfe verschiedener Techniken aus der diskreten Mathematik bestimmt

werden [Mey05].

2.2 Region-Growing

Da benachbarte Pixel meist ahnliche Eigenschaften haben und zu den gleichen

Bildregionen gehoren fuhrt der Ansatz des Region-Growing oft zu guten Ergebnissen.

Ausgehend von einem Start-Pixel wird fur alle benachbarten Pixel gepruft ob sie

die notige Gleichheit aufweisen um der Region hinzugefugt zu werden. Andernfalls

werden sie als außerhalb liegend verworfen. Startet man mit mehreren so genannten

Seed-Points kann ein gruppieren der sich bildenden Regionen notig sein, falls diese

beim Wachsen aneinander stoßen. Um sinnvolle Regionen zu erhalten ist das manuelle

setzen der Seed-Points notwendig. Naturlich gibt es schon vortgeschrittene Region-

Growing Algorithmen die selbst die Seed-Points bestimmen [NN06]. Genauso muss

der Threshold zum hinzufugen oder verwerfen von Pixeln gegebenenfalls an die Bild-

situation angepasst werden. Es ist beim Standard Region-Growing Verfahren somit

ein gewisses Vorwissen zum Bild notwendig und Interaktion vom Benutzer, damit der

Algorithmus das gewunschte Ergebnis liefert [Rad05].

Der Region-Growing Algorithmus mach nur Sinn, wenn sich das gesuchte Objekt

ausreichend vom Hintergrund unterscheidet [Ton05, Seite 243], in diesem Fall ist

der Algorithmus einfach, leicht verstandlich und flexibel. Eine Implementierung des

Region-Growing Algorithmus ist von R. Nock und F. Nielsen [NN06] (siehe Bildfolge

2.2).

5

Abbildung 2.2: Region-Growing

6

Kapitel 3

Merkmalsextraktion

Die Segmentierung auf Grund von simplen Intensitats- und Farbunterschieden ist

ein Vorverarbeitungsschritt, reicht aber oft nicht aus, wenn nach bestimmten Bild-

inhalten gesucht werden soll. Deshalb kann es notwendig sein, gezielt Merkmale in

Bildern zu suchen die zu Objekten korrelieren.

3.1 Kantendetektoren

Eines der markantesten Bildmerkmale sind Kanten. Eine Kante bildet meist den

Abschluss eines Objektes, kann aber auch in anderen Zusammenhangen auftreten.

Eine Kante zeichnet sich durch einen Intensitatsunterschied im Bild aus. Nicht jeder

Intensitatsunterschied ist jedoch eine Kante. Bei der Kantendetektion werden diese

Intensitatsunterschiede durch einen Algorithmus gesucht und in Form einer binaren

Reprasentationen als Schwarzweißbild dargestellt [Rad05]. Die zu erkennenden Um-

risslinien nennt man auch Konturen.

Kantendetektoren arbeiten meist in drei wesentlichen Schritten:

1. Auf das Bild wird eine Maske angewendet, um Intensitatsgradienten zu erzeu-

gen.

2. Mittels Thresholding uber das Gradientenbild werden nennenswerte Gradienten

selektiert.

3. Verschiedene Operationen und Algorithmen verbinden die errechneten Daten

7

zu Kanten.

Je nach Verfahren haben die drei Schritte andere Auspragungen. Die Gradienten-

berechnung geschieht aber meist uber zentrale Differenzen, diese werden als 3x3 Ma-

trix implementiert. Hierfur konnen die Prewitt-Masken in x- und y-Richtung

1 0 −1

1 0 −1

1 0 −1

,

−1 −1 −1

0 0 0

1 1 1

oder die Sobel-Masken x- und y-Richtung

−1 0 1

−2 0 2

−1 0 1

,

1 2 1

0 0 0

−1 −2 −1

her genommen werden, die mittels Faltung auf das Bild angewendet werden. Bei ver-

waschenen, weichen Kanten im Bild entstehen schwache Gradienten uber eine großere

Flache. Es entstehen also breite Kanten wobei ein zusatzlicher Hochpassfilter dafur

sorgt, dass nur die hohen Frequenzen stehen bleiben und die Kanten somit ausgedunnt

werden.

3.1.1 Sobel Kantendetektion

Bei der Sobel Kantendetektion wird das ursprungliche Bild mit den Sobel-Matrizen

einmal in x- und einmal in y-Richtung gefaltet. Die entstehenden Daten konnen als

Approximation der ersten Ableitung des Bildes verstanden werden. Wie in Graphik

3.1 illustriert, wird jeweils ein 3x3 Bereich (gelb) mit der Maske (blau) multipliziert

und ergibt einen Teil des Gradienten im Ergebnisbereich (grun). Die Sobel-Maske fur

die x-Richtung filtert die horizontalen Kanten heraus, die fur die y-Richtung die ver-

tikalen Kanten. Nun werden die beiden Ergebnisse so zusammengefasst, dass immer

8

Abbildung 3.1: Faltung mittels Sobel-Operator

das Maximum ubernommen wird.

3.1.2 Canny Kantendetektion

Der Canny edge detector ist bekannt als eine der effektivsten Techniken zur Kan-

tenerkennung [Gre02]. Das Erkennen von nicht vorhandenen Kanten soll vermieden

werden, es sollen vorhandenen Kanten moglichst auch gefunden werden und eine ge-

fundene Kante sollte moglichst exakt mit ihrer realen Kante korrelieren. Der Canny

edge detector optimiert den Ablauf der Kantendetektion [Sch]:

1. Zweidimensionaler Gaußfilter zur Rauschreduktion. Dabei muss die Große des

Glattungs-Operators je nach Situation angepasst werden.

2. Das geglattete Bild wird mit gerichteten Ableitungsoperatoren versehen. Dazu

konnen der vorher beschriebene Sobel-Operator oder aber auch der Laplace-

Operator eingesetzt werden.

3. Nicht-maximale Ableitungen entlang der Kanten werden unterdruckt. Dadurch

wird eine Ausdunnung der Linien erreicht.

4. Fur Gradienten von mittlerer Steigung muss eine Entscheidung getroffen wer-

den, ob es sich um eine Kante oder Rauschen handelt. Dazu wird die Hysterese

angewendet. Dabei werden zu schwache Gradienten auf Grund ihrer Lage en-

tweder als Kanten- oder Nicht-Kanten-Pixel klassifiziert.

9

Abbildung 3.2: Canny Edge Detection Applet [Kra01]

Das resultierende Bild ist ein schwarzes Bild mit dunnen weißen Linien oder umgekehrt

(siehe Abbildung 3.2 rechts oben im Applet).

3.2 Eckendetektoren

Neben Kanten gibt es noch andere interessante Bildmerkmale. Der Punkt in dem

zwei Kanten enden ist eine Ecke. Ecken sind also auch ein wichtiges Merkmal fur einen

Objektabschluss. Ecken konnen ahnlich der Kantendetektion mittels Gradienten oder

aber auch mit Hilfe von Morphologie gesucht werden. Auf die erste Moglichkeit soll

hier naher eingegangen werden.

3.2.1 Moravec’s Corner Detector

Die Funktionalitat des Moravec’s Corner Detectors MCD basiert auf der Betra-

chtung eines kleinen lokalen Bildfensters. Es wird jeweils die Anderung der Bildin-

tensitat I gemessen, wenn das Fenster in eine bestimmte Richtung verschoben wird.

Es mussen drei Falle berucksichtigt werden:

1. Alle Verschiebungen ergeben einen geringen Intensitatsunterschied => einfar-

10

bige Region.

2. Alle Verschiebungen entlang der Kante ergeben einen geringen und alle lotrecht

zur Kante ergeben einen hohen Intensitatsunterschied => Kante.

3. Alle Verschiebungen ergeben einen hohen Intensitatsunterschied => Ecke.

Iu,v ist der Intensitatswert am Pixel (u, v). Um den Intensitatsunterschied festzustellen

kann folgende Formel verwendet werden:

Ex,y =∑u,v

wu,v[Ix+u,y+v − Iu,v]2

fur

(x, y) = {(1, 0), (1, 1), (0, 1), (−1, 1)}

Dabei ist wu,v = 0 außerhalb des MCD Fensters und wu,v = 1 innerhalb des Fensters

(siehe Abbildung 3.3 links). Vermutete Ecken sind dann die lokalen Maxima von E

uber alle Pixel [HS88].

3.2.2 Harris Corner Detector

Der Moravec’s Corner Detector MCD hat einige Schwachstellen. Diese Probleme

versucht der Harris Corner Detector HCD zu beheben [HS88].

1. Das Ergebnis des MCD kann tauschen, da nur in vier Richtungen zwischen 0◦

und 135◦ verschoben wird. Der HCD ersetzt das Verschieben in vier Richtungen

durch die Taylor Entwicklung

Ex,y =∑u,v

wu,v[x ∗ δI

δx+ y ∗ δI

δy+ O(x2, y2)]2

, wobei δIδr

die partielle Ableitung in Richtung r und O das Landau Symbol

darstellt.

11

Abbildung 3.3: Moravec-Fenster (l), Harris-Fenster (r)[Chu06]

Fur kleine Verschiebungen gilt

Ex,y = Ax2 + 2Cxy + By2

, wobei

A =δI

δx

2

∗ w,B =δI

δy

2

∗ w, C = (δI

δx∗ δI

δy) ∗ w

.

2. Das Ergebnis des MCD ist stark verrauscht weil das Fenster binar und rechteckig

ist. HCD benutzt statt dessen einen geglatteten Kreis

wu,v = eu2+v2

2σ2

(siehe Abbildung 3.3 rechts).

3. Der MCD reagiert zu oft. Das heißt es werden zu viele Regionen als Ecke

erkannt, da nur die lokalen Maxima von E fur das Ergebnis verantwortlich sind.

Aus E sollen nun andere Schlusse gezogen werden, welche die Schwankungen

und die Verschieberichtungen von E berucksichtigen. Es ist klar, dass gilt:

Ex,y = Ax2 + 2Cxy + By2 = (x, y)

A C

C B

(x, y)T

. Sei

M =

A C

C B

12

Abbildung 3.4: Eigenwerte dargestellt als Ellipsenachsen.

die 2x2 Matrix aus E. E ist der lokalen Autokorrelationsfunktion sehr ahnlich

und M beschreibt deren Form am Ursprung [Wik06a]. Seien α, β die Eigenwerte

von M. Ein Eigenwert zeigt die Schnelligkeit der Anderungen bei einem Shift

in eine Richtung an (siehe Abbildung 3.4). Die beiden Eigenwerte entsprechen

dem Verhaltnis der Hauptkrummungen von E [HS88].

Es lassen sich drei Falle in der Eigenwertbelegung unterscheiden wie in Abbil-

dung 3.5 dargestellt. Je nach dem wird entschieden ob es sich um Kante, Ecke

oder flache Region handelt:

(a) Beide Eigenwerte sind groß. E hat somit eine scharfe Spitze was auf eine

Ecke hinweist.

(b) Ein Eigenwert ist sehr groß im Vergleich zum Anderen. Das heißt E ist

sehr kantig und zeigt eine Kante an.

(c) Beide Eigenwerte sind klein. E ist also sehr flach und zeigt an, dass keiner

der Shifts eine Veranderung bringt. Es handelt sich somit um eine Region

mit konstanter Intensitat.

4. Weiterhin definiert der HCD noch die Qualitat einer Kante beziehungsweise

Ecke. Die so genannte Corner-Response (Eckenqualitat)

R = α ∗ β − k ∗ (α + β)2

13

Abbildung 3.5: Unterscheidungs-Raum

ist positiv fur Ecken, negativ fur Kanten und klein in einer uniformen Region.

5. Abschließend wird eine Kantenhysterese und eine Eckenverbindung durchgefuhrt

um kleine Locher zu schließen, Brucken zu bauen sowie kleine Kantenstuckchen

und isolierte Kanten zu loschen.

14

Kapitel 4

Objekterkennung

Die Objekterkennung in der Bildverarbeitung ist ein komplexer Vorgang der viele

Unsicherheitsfaktoren hat. Zuerst muss ein Objekt im Bild gefunden werden, hierbei

konnen falsche Objekte gefunden oder existierende nicht entdeckt werden. Sind die

Objekte gefunden, fehlt fur die Objekterkennung noch die Klassifikation der Objekte.

4.1 Templatematching

Das Templatematching gehort zur modellbasierten Segmentierung. Beim Tem-

platematching wird mittels vollstandiger Suche entschieden wie gut ein vorgegebenes

Modell (Template) zu einem bestimmten Pixelbereich passt (match) [Ton05].

Das Modell beschreibt moglichst genau das zu suchende Objekt und seine Einbet-

tung in die Umgebung. Dabei wird das Objekt-Template in einem Pixel Abstand von

einer Bounding-Box begrenzt. Mehr Umgebung als notwendig wurde nur die Fehler-

rate erhohen. Das Template sollte moglichst die gleiche Große und Orientierung haben

wie das gesuchte Objekt. Die Auswirkung von Großenunterschieden ist in Abbildung

4.1 zu sehen. Falls diese Einschrankung der Große und Ausrichtung nicht gegeben ist,

wird noch in allen moglichen Skalierungen s und Drehungen r der Templates gesucht

[Ton05].

Als Maßstab dafur, ob das Template zu einer Bildregion passt, konnen verschiedene

Kriterien verwendet werden. Der durchschnittliche quadratische Abstand von Bild f

15

Abbildung 4.1: Matching Beispiel

und Template t

msd(x, y) =P−1∑p=0

Q−1∑q=0

(f(x + p, y + q) − t(p, q))2

oder der durchschnittliche Abstand der Betrage

mad(x, y) =P−1∑p=0

Q−1∑q=0

|f(x + p, y + q) − t(p, q)|

. Beide Maße sind relativ robust gegenuber Rauschen, aber haben Probleme bei In-

tensitatsunterschieden zwischen Bild und Template.

Der Korrelationskoeffizient cc basiert auf Intensitatsabweichungen anstatt auf Werten

und kann deshalb muhelos selbst Objekte finden die negativ zum Template sind

[Ton05]. Es sei nun g ein Bildausschnitt aus f der die gleiche Große wie t hat. Eg

und Et seien die Erwartungswerte von Bildausschnitt und Template. Dann ist der

Korrelationskoeffizient definiert als

cc(g, t) =

∑ni=1(gi − Eg)(ti − Et)√∑n

i=1(gi − Eg)2√∑n

i=1(ti − Et)2

16

Abbildung 4.2: Menschen und Hunde

Abbildung 4.3: Klassifikation von Mensch und Hund auf Basis von 2 Merkmalen

wobei ti, gi das i-te in Reihe gelesene Pixel von t bzw. vom Ausschnitt g ist. Der

Koeffizient bewegt sich im Wertebereich [−1, 1] und nimmt 1 an falls Template und

Bildausschnitt gleich sind und -1 falls das Template negativ zum Bildausschnitt ist

[Wik06d].

Fuhrt man die Berechnung von cc fur jeden moglichen Bildausschnitt g von f durch,

entsteht eine zweidimensionale Funktion mit Wertebereich [−1, 1] die im besten Fall

eindeutige Minima bzw. Maxima aufweist. Die Extremwerte geben jeweils die Fund-

stelle des Templates im Bild an.

17

4.2 Klassifizierung

Als Klassifizierung oder Klassifikation bezeichnet man einen Vorgang oder eine

Methode zur Einteilung von Objekten in Klassen oder Kategorien [Wik06c]. Die

zu klassifizierenden Objekte konnen Beispielsweise aus der Segmentierung stammen,

welche noch keine Wertung uber die Intensitaten hinaus vorgenommen hat. Die Ob-

jekte konnen auch bereits mit Merkmalen annotiert sein, die durch einen Detektor

gefunden wurden. Diese Merkmale konnen dann fur die Klassifikation verwendet wer-

den.

Durch die Klassifikation soll ein leichtes Verstehen ermoglicht und das Erkennen von

Zusammenhangen verbessert werden. Liegen alle Informationen uber ein Objekt vor,

so kann es immer korrekt klassifiziert werden. Beim Klassifizieren von Bildsegmenten

ist es aber sehr schwierig, alle relevanten Eigenschaften zu bestimmen. Somit muss die

Klassifizierung trotz unvollstandiger Aussagen uber ein Bildsegment funktionieren.

Zur Klassifizierung wird eine Reihe von passenden Merkmalen herangezogen, diese

bilden den so genannten Merkmalsvektor. Beispielsweise konnen zur Klassifizierung

von Menschen und Hunden die Merkmale Anzahl der Beine und Große herangezogen

werden. Hunde befinden sich also meist in der Klasse klein und vierbeinig wohinge-

gen Menschen zwei Beine und mindestens eine gewisse Große haben sollten (siehe

Abbildung 4.2). Bei einem zweidimensionalen Merkmalsvektor wie diesem konnen

die Klassen als Ellipsen in einem Koordinatensystem dargestellt werden (siehe Abbil-

dung 4.3). Dabei wird die Varianz der klassifizierten Objekte innerhalb einer Klasse

als Within-Class-Scatter bezeichnet. Der Between-Class-Scatter bezeichnet den Ab-

stand zwischen den Mittelwerten der Merkmale der einzelnen Klassen [Ton05, Seite

297].

Im Allgemeinen kann nach den unterschiedlichsten Merkmalen klassifiziert werden,

haufig werden Form, Kontrast, Segmentgroße, Farbe, Textur und vielen Andere ver-

wendet [Ton05].

18

Kapitel 5

Verfolgung von Merkmalen/Objekten uber Bildsequenzen

Viele der vorher vorgestellten Verfahren liefern Messwerte. Diese Messwerte

konnen Gradienten, Positionen, Winkel oder Ahnliches sein. Angenommen das Ziel

der anfanglichen Objektsuche bzw. Objekterkennung im Bild war die kontinuierliche

Positionsverfolgung von Objekten uber langere Bildsequenzen hinweg. Da keines der

Verfahren der Segmentierung perfekt ist, sollten die gemessenen Werte noch moglichst

genau an die exakten Werte angenahert werden. Ein bewahrtes Verfahren hierfur ist

der Kalman-Filter.

5.1 Kalman-Filter

Der Kalman-Filter arbeitet auf einer kontinuierlichen Folge von Messwerten, die

aus einem beliebigen Verfahren stammen konnen. Zum Zeitpunkt t existiert eine

Vorhersage x−t , die am Ende von Schritt t-1 erstellt wurde. Außerdem liefert das

gewahlte Verfahren zu jedem Zeitpunkt t einen Messwert zt. Die Kalman-Gain-

Matrix K gewichtet nun abhangig vom Fehler P ob man dem Messwert zt oder dem

zugrunde liegenden Bewegungsmodell, d.h. der Vorhersage, mehr vertraut. Messwert

und Vorhersage werden dann zu einem Schatzwert fusioniert. Der Kalman-Filter ist

ein stochastischer Zustandsschatzer mit iterativer Struktur der in Echtzeitsystemen

angewendet werden kann.

Es wird angenommen, dass Vorhersage und Messung normalverteilt sind. Anhand

des Erwartungswerts und der Varianz werden die beiden Werte fusioniert (siehe auch

19

Abbildung 5.1: Fusionierung von Vorhersage und Messung

5.1).

Die Kalman-Gain-Matrix K, die zur Fusionierung benutzt wird, setzt sich aus dem

geschatzten Vorhersagefehler P−t , der Abhangigkeitsmatrix H und einer Messfehlerko-

varianzmatrix R zusammen [WB04, S.3]:

Kt =P−

t H t

HP−t H t + R

Dabei erfasst H die Abhangigkeit zwischen dem echten Zustand xt und der Messung

zt. In

P−t = APt−1A

T + Q

aus [WB04, S.3, S.5] fließen der Vorhersagefehler

Pt−1 = (I − Kt−1H)P−t−1

aus dem Schritt davor, die Zustandsubergangsmatrix A und ein Modellfehler Q ein.

Die vorhergesagte Messung x−t und die Messung zt werden in [WB04, S.3] nun zu

einer Schatzung xt des realen Wertes xt verbunden.

xt = x−t + Kt(zt − Hx−t )

Dabei wird res = zt−Hx−t als Innovationsschritt oder Residuum bezeichnet, res = 0

heißt Pradiktion und Messung sind gleich.

20

Fur die neue Vorhersage

x−t+1 = Axt + But

wird die Zustandsubergangsmatrix A auf die aktuelle Schatzung angewendet und ein

Regeleingriff But ([Wik06b]: oft nicht vorhanden) addiert.

Es folgt eine kurze Zusammenfassung des Ablaufs eines Kalman Filters fur einen

Zeitpunkt t.

Zusammenfassung Schritt t:

1. Algorithmus liefert zt

2. Kalman-Gain-Matrix berechnen Kt =P−t Ht

HP−t Ht+R

3. Schatzung xt = x−t + Kt(zt − Hx−t )

4. Fehler berechnen Pt = (I − KtH)P−t

5. Vorhersage machen x−t+1 = Axt + But

6. Fehler vorhersagen P−t+1 = APtA

T + Q

5.2 Optical-Flow

Der Begriff des Optical-Flow (Optischer Fluss) wurde erstmals 1950 von J.Gibson

[Gib50] gepragt. Er beschreibt damit die Art, wie Lebewesen ihre Umwelt wahrnehmen.

Dabei erhalten Oberflachen jeweils eine Geschwindigkeit und eine Richtung. Etwa

ein viertel Jahrhundert spater definieren Horn und Schnuck 1981 [HS81, S.185] den

Optical-Flow als die Verteilung von sichtbaren Bewegungsvektoren der Helligkeits-

Muster. Praktisch ausgedruckt durch Rowekamp [Row99, S.5] analysiert eine Optical-

Flow Anwendung die Bewegung, welche von der 3D Szene in die 2D Bildebene pro-

jiziert wird (Abbildung 5.2). Fur jedes Bildelement wird ein Bewegungsvektor berech-

net, der die Bewegung in Bildkoordinaten ausdruckt. Diese konnen unter anderem

21

Abbildung 5.2: 3D Bewegung in die 2D Bildebene projiziert

als Grundlage fur eine Bewegungsschatzung in der realen Welt dienen.

Da der Optical-Flow schon lange erforscht wird gibt es eine Vielzahl von Algorith-

men die diesen berechnen. Diese Algorithmen lassen sich wie folgt einteilen [Row99,

S.15, S.16]:

• Merkmals-basierte Methoden

• Intensitats-basierte Methoden

– Gradienten-basierte Techniken

– Korrelations-basierte Techniken

– Filter-basierte Techniken

Auf Merkmals-basierte Methoden wird nicht weiter eingegangen, da die Berechnung

von Merkmalen viel Rechenzeit erfordert und somit diese Methoden schlecht fur

Echtzeitanwendungen geeignet sind. Wir beschranken uns in dieser Arbeit auf die

Gradienten-basierten Methoden.

Die Helligkeit des Bildes am Punkt (x, y) zum Zeitpunkt t wird mit E(x, y, t) beze-

22

Abbildung 5.3: Partielle Ableitungen

ichnet [HS81]. Bleibt die Helligkeit in (x, y) konstant so gilt

∆E

∆t= 0

. Seien

Ex =δE

δx, Ey =

δE

δy, Et =

δE

δt

die partiellen Ableitungen von E nach x, y und t. Die Ableitungen werden uber den

Durchschnitt der vier benachbarten Differenzen berechnet (Abbildung 5.3) [HS81].

Nach Anwendung der Kettenregel ergibt sich

Ex∆x

∆t+ Ey

∆y

∆t+ Et

∆t

∆t= 0

. Diese Bedingung an die lokale Flow Geschwindigkeit (u, v) lasst sich nun mit

u =∆x

∆t, v =

∆y

∆t

als

(Ex, Ey) · (u, v) = −Et

schreiben, wobei u und v Unbekannte sind. In einfacheren Worten ausgedruckt darf

sich die Flow Geschwindigkeit (u, v) nur auf der Geraden lotrecht zu (Ex, Ey) im

23

Abbildung 5.4: Flug uber einen Tisch auf einer Wiese

Abstand von

Et

|(Ex, Ey)|

befinden.

Leider ist diese eine Gleichung nicht ausreichend um beide Komponenten u und v des

Feldes von Geschwindigkeitsvektoren zu finden. Die Gleichung liefert nur die Kompo-

nente in die Richtung des Gradienten ∇E. Diese Komponente wird als Normalfluss

und das Problem wird in [Jah03, S.230] als Blendproblem bezeichnet. In Abbildung

5.4 ist dargestellt wie das Problem entsteht. An der glatten Tischkante kann nicht

identifiziert werden woher das Pixel aus dem vorherigen Sequenzbild genau stammt

(graue Pfeile). Es korrespondiert mit allen Pixeln auf der Tischkante.

Um das Blendproblem zu uberwinden muss eine weitere Bedingung an die Vektoren

(u, v) gestellt werden. Dazu gibt es viele Ansatze in der Literatur. Horn und Schnuck

[HS81] fordern eine moglichst glatte/ruhige Veranderung uber das Bild hinweg. Dazu

minimieren sie die Quadrate der Gradientenlangen der Optical-Flow Geschwindigkeit:

(δuδx

)2+

(δuδy

)2

und(

δvδx

)2+

(δvδy

)2

.

Das minimieren der Fehler

℘b = Ex∆x

∆t+ Ey

∆y

∆t+ Et, ℘

2c = (

δu

δx)2 + (

δu

δy)2 + (

δv

δx)2 + (

δv

δy)2

24

Abbildung 5.5: Velocity Vector Field

geschieht uber

℘2 =

∫ ∫(α2℘2

c + ℘2b)dxdy

. Die Werte (u, v) die ℘2 minimieren liegen auf einer Senkrechten in Richtung der

Bedingungslinie fur (u, v). Die Gleichungen hierfur sind:

(α2 + E2x + E2

y)(u − u) = −Ex[Exu + Eyv + Et]

(α2 + E2x + E2

y)(v − v) = −Ex[Exu + Eyv + Et]

wobei u, v die lokalen Durchschnittswerte fur u und v sind. Durch weitere Uberlegungen

stellt sich heraus, dass α2 vernachlassigt werden kann.

Es existiert nun fur jeden Punkt (x, y) des Bildes ein Gleichungspaar. Die Berech-

nung ware sehr rechen- und speicherintensiv, wenn fur jeden Bildpunkt gleichzeitig

das oben beschriebene Gleichungspaar gelost werden wurde. Es wird deshalb die iter-

ative Losungsmethode Gauss-Seidel aus der Numerik gewahlt [Wei06]. Um ein gutes

Ergebnis zu bekommen wird der Optical-Flow uber mehrere Iterationen berechnet um

den Fehler zu minimieren. Die erste Iteration berechnet die Vektoren der Helligkeits-

Gradienten-Richtung. Nach 32 Iterationen weisen die Optical-Flow Vektoren einen

annehmbaren Fehler auf (siehe Abbildung 5.5).

25

Kapitel 6

Zusammenfassung

Diese Arbeit gibt einen Einblick in die grundlegenden Methoden der Bildverar-

beitung.

Zunachst wurde die Segmentierung vorgestellt. Diese findet als Vorverarbeitungss-

chritt in sehr vielen Verfahren ihre Anwendung. Deshalb ist die Segmentierung ein

wichtiger Grundbaustein in der der Bildverarbeitung.

Anschließend ging die Arbeit auf die Merkmalsextraktion in Bildern ein. Uber Merk-

male konnen wichtige Aussagen uber Objekte gemacht werden. Zu erwahnen sind

hier Kanten und Ecken welche Objekte von der Umgebung abgrenzen. Außerdem

werden Merkmale benotigt um Objekte zu Klassifizieren. Als Klassifizierung oder

Klassifikation bezeichnet man einen Vorgang oder eine Methode zur Einteilung von

Objekten in Klassen oder Kategorien.

Ist im Vorab bekannt, welche Form und Schattierung ein gesuchtes Objekt hat, kann

das Templatematching mit dem Korrelationskoeffizienten fur die Suche her genom-

men werden.

Die Weiterverarbeitung von Segmenten, Merkmalen und Templates in der Bildsequenz

ist das Ziel der meisten Verfahren auf Bildsequenzen. Standardalgorithmen die hier-

bei Verwendung finden sind unter anderem der Kalman-Filter und der Optikal-Flow

Algorithmus. Der Kalman-Filter ist ein stochastischer Zustandsschatzer mit itera-

tiver Struktur der in Echtzeitsystemen angewendet werden kann. Der Optical-Flow

analysiert Bewegungen von Objekten in einer Bildsequenz. Fur die Bildelemente wird

26

jeweils ein Geschwindigkeitsvektor berechnet, der die Bewegung in Bildkoordinaten

ausdruckt. Diese konnen unter anderem als Grundlage fur eine Bewegungsschatzung

in der realen Welt dienen.

Ein großes Anwendungsfeld der Bildverarbeitung ist die Robotik. Selbstgesteuerte

Roboter sind dabei denkbar, die ihre Umgebung analysieren und erkennen wohin sie

gehen mussen. Auch in der Industrie, z.B. in der Qualitatssicherung ist eine Automa-

tisierung mittels Bildverarbeitung in vielen Bereichen moglich. Andere Bereiche wie

die Bewegungsanalyse im Sport, die Uberwachung von Raumen oder Platzen oder die

Zugangskontrolle setzen auch die Bildverarbeitung fur ihre Berechnungen ein. Viele

Bereiche haben schon sehr ausgereifte Verfahren, aber es gibt noch viel zu verbessern.

Diese Arbeit soll eine Wissensbasis zur Analyse und Verbesserung bestehender Ver-

fahren bieten und genauso auch Anregung sein um neues zu Entwickeln.

27

Referenzen

[Chu06] Yung-Yu Chuang. Features, digital visual effects. Techni-

cal report, National Taiwan University, March 2006. URL

http://www.csie.ntu.edu.tw/cyy/ courses/vfx/06spring/lectures/h and-

outs/lec04 feature.pdf.

[FPWW94] Bob Fisher, Simon Perkins, Ashley Walker, and Erik Wolfart.

Adaptive thresholding. URL, 1994. http:// www.cee.hw.ac.uk/

hipr/html/adpthrsh.html.

[FPWW03] R. Fisher, S. Perkins, A. Walker, and E. Wolfart. Histogram equaliza-

tion experimentation. URL, 2003. http://homepages.inf.ed.ac.uk/rbf/

HIPR2/histeqdemo.htm.

[Gib50] J. Gibson. The perception of the visual World. River Side Press, Came-

bridge, 1950.

[Gre02] William E. Green. Canny edge detection tutorial. Tech-

nical report, Drexel University, Philadelphia, 2002. URL

http://www.pages.drexel.edu/weg22/can tut.html.

[HS81] B. Horn and B. Schnuck. Determining optical flow. In Artifical Intel-

lience, number MA 02139, pages 185–204. Artifical Intellience Labora-

tory, MIT, Cambridge, USA, 1981.

28

[HS88] Chris Harris and Mike Stephens. A combined corner and edge detector.

Plessey Research Roke Manor, United Kingdom, 1988.

[Jah03] Bernd Jahne. Digitale Bildverarbeitung. Springer Verlag, Heidelberg,

2003.

[Kra01] Susanne Krabbe. Still image segmentation. URL, June 2001.

http://www-mm.informatik.uni-mannheim.de/veranstaltungen/ anima-

tion/multimedia/ segmentation/Applet/Segmentation.html.

[Mey05] Ernst W. Meyer. Vorlesung Diskrete Strukturen, chapter 4.8.2 Differen-

zenoperator. Technische Universitat Munchen, December 2005.

[NN06] R. Nock and F. Nielsen. Statistical region merging (srm). URL, May

2006. http://www.csl.sony.co.jp/person/nielsen/SRM/.

[Rad05] B. Radig. Vorlesung Bildverstehen, chapter Segmentation. Technische

Universitat Munchen, 2005.

[Row99] Thomas Rowekamp. A smart Sensor System for Real-time Optical Flow

Estimation. PhD thesis, Fakultat fur Mathematik, Naturwissenschaften

und Informatik der Brandenburgischen Technischen Universitat Cottbus,

1999.

[Sch] Th. Schmidt. Kantenerkennung. Technical report, Uni Halle. URL

http://users.informatik.uni-halle.de/schmidt/kanten.htm.

[Ton05] Klaus D. Tonnies. Grundlagen der Bildverarbeitung. Pearson Studium,

2005. ISBN 3-8273-7155-4.

[WB04] Greg Welch and Gary Bishop. An introduction to the kalman filter.

Technical report, Department of Computer Science University of North

Carolina at Chapel Hill, April 2004.

29

[Wei06] Eric W. Weisstein. Gauss-seidel method. URL, 2006.

http://mathworld.wolfram.com/Gauss-SeidelMethod.html.

[Wik06a] Wikipedia. Autokorrelation. URL, April 2006.

http://de.wikipedia.org/wiki/Autokorrelation.

[Wik06b] Wikipedia. Kalman-filter. URL, February 2006.

http://de.wikipedia.org/wiki/Kalman-Filter.

[Wik06c] Wikipedia. Klassifizierung. URL, February 2006.

http://de.wikipedia.org/wiki/Klassifizierung.

[Wik06d] Wikipedia. Korrelationskoeffizient. URL, April 2006.

http://de.wikipedia.org/wiki/Korrelationskoeffizient.

30