Grundlagen Bildverarbeitung Kap 5 Vers 2

5/11/2018 Grundlagen Bildverarbeitung Kap 5 Vers 2 - slidepdf.com

http://slidepdf.com/reader/full/grundlagen-bildverarbeitung-kap-5-vers-2 1/11

Bekannte Objekte im Bild finden

Warum ist das Ergebnis einer Kreuzkorrelation ein Maß für die Ähnlichkeit zwischenZwei Vektoren a und b?

Bildausschnitt als Vektor dargestellt

= a

© B. Neumann 09

Template auch als Vektor dargestellt

( ) ( )7 7 8 5 5 6 8 8 9 9 9 4 9 4 6 5 6 7 410⋅ = ⋅ =TT

a b

Die Kreuzkorrelation an der rot gerahmten Stelle mit dem Template entspricht dem Skalarproduktaus Vektor a mit Vektor b. Als Ähnlichkeitsmaß dient die Kreuzkorrelation aber erst dann, wennDie Vektoren auf Länge 1 normiert werden. Es entsteht die normierte Kreuzkorrelation. Beispiel:

,, ,

a b

a b

⋅

= =⋅ ⋅

410

0 93321 4 20 52

= b



Die Korrelation zur Bestimmung

der Ähnlichkeit zwischen zweiVektoren

Zwei Vektoren a und b sind um so ähnlicher, je geringer der Betrag der Vektordifferenz ist.

a b a b a b− = + − ⋅

2 2 2

2Da die ersten beiden Terme auf der rechten Seite nur die Längen der beiden Vektorenangeben, befindet sich die Information über die Ähnlichkeit der Vektoren im dritten Term

a b⋅

© B. Neumann 09

Damit eine allgemeine Vergleichbarkeit unabhängig von der Länge der Vektoren gegebenist, müssen die Vektoren auf die Länge 1 normiert werden.

c ∗ ∗⋅= = ⋅

⋅

a ba b

a b

a*b*

1

a*⋅b*Große Ähnlichkeitzwischen a* und b*

Geringe Ähnlichkeitzwischen a* und b*

1

a*⋅b*

a*

b*



Objekte im Bild findenmit dernormierten Kreuzkorrelation

( , ) ( , ) / ( , )M x y C x y N x y mit=

( , ) ( , ) ( , )

L 1 K 1

u 0 v 0C x y T u v G x u y v

− −

= == ⋅ + +∑∑

© B. Neumann 09

( , ) ( , ) ( , )

L 1 K 1 L 1 K 1

2 2

u 0 v 0 u 0 v 0

N x y T u v G x u y v− − − −

= = = == ⋅ + +∑∑ ∑∑

C(x,y) ist der am Ort (x,y) des Bildes G erhaltene Grauwert nach normierterKreuzkorrelation des Bildes G mit dem Template (Suchvorlage) T. ⊗ bedeutetdas Korrelationszeichen.

( , ) ( , )( , )

( , )

G x y T x yC x y

N x y

⊗=



Gegenüberstellung von Faltungund Kreuzkorrelation

L 1 K 1

L 1 K 12 2

u 0 v 0

L 1 K 1L 1 K 1

2 2u 0 v 0

Kreuzkorrelation :

C(x,y) h(u,v) G(x u,y v), Template h ist L K Matrix

Faltung:

G´(x,y) h(u,v) G(x u,y v) Fenster h ist L K Matrix

− −− −

= =

− −− −

= =

= ⋅ − + − + × −

= ⋅ + − + − × −

∑∑

∑∑

© B. Neumann 09

x

x+u

y+v x

x-u

y-v

x

y

x-(K-1)/2+u

y-(L-1)/2+v

x

y

y+(L-1)/2-v

x+(K-1)/2-u

Links: Indizierung bei Korrelation, rechts: Indizierung bei Faltung.u = 0,1,2,3,...K-1; v = 0,1,2,3,...L-1. Die Pfeile deuten die Zählrich-tungen im Template bzw. Fenster an

G G

G G



Beispiel für eine Kreuzkorrelation 1

Erster berechenbarer Punkt © B. Neumann 09

Binärbild B Template Temp Norm. Kreuzkorrelationvon B mit Temp

Der Algorithmus zur Kreuzkorrelation entspricht mit kleinen Änderungen bei derZählweise dem der Faltung. Für große Templates T ist daher die Berechnungszeitsehr groß, so dass wir uns beschleunigende Maßnahmen einfallen lassen müssen.



Beispiel für eine Kreuzkorrelation 2

Ort größter Überein-

stimmung mit T

© B. Neumann 09

Urbild B

A: Binärbild von B

T: Template aus A

G: Bild nach Kreuzkorre-Lationvon A mit T



Beschleunigung der Suchprozesse 1

Das Aufsuchen von Bildorten, die eine hohe Ähnlichkeit mit dem Template haben,

ist sehr zeitaufwendig. Dies gilt um so mehr für große Templates. Aus diesemGrund lohnt es sich über Verfahren nachzudenken, die die Suchzeit verkürzen.Eine Möglichkeit besteht in der Verringerung der Rasterpunkte des Templats.

Gitterförmige Anordnung der Rasterpunkte

© B. Neumann 09

T

T

Ungleichmäßige Anordnung der Rasterpunkte

Weitere Möglichkeiten der Datenreduktion zur Beschreibung eines Templates

besteht in der Hervorhebung von Kanten, Ecken, Löchern etc.



Beschleunigung der Suchprozesse 2

Die Erhöhung der Prozessgeschwindigkeit wird insbesondere dann erforderlich,wenn eine größen- und/ oder rotationsinvariante Suche nach dem Template im

Bild notwendig wird. Auch für die 3D-Bildverarbeitung ist eine hoheProzessgeschwindigkeit erforderlich, weil die Tiefeninformationen über dieKorrespondenzanalyse erhalten wird. Dabei werden in den Stereobildpaarendie Orte gleicher Objektpunkte gesucht.

© B. Neumann 09

Die Suche wird durch folgende Maßnahmen schneller:• Reduktion der Quantisierungsstufen von Bild und Template• Reduktion des Rasterabstands und der Quantisierungsstufen von Bildund Template (siehe Gaußpyramide auf der nächsten Folie)

• Einschränkung des Suchbereiches durch ROI (sehr wichtig in 3D-CV)

• Auffällige Merkmale wie Kanten, Ecken, starke hell-dunkel-Kontrastehervorheben

• Graubild und Template Binarisieren• Das Template so klein wie möglich machen• Den Kontrast von Bild und Template möglichst groß machen und Rauschen

unterdrücken.



Beschleunigung der Suchprozesse 3Gaußpyramide

Ein Weg zur Beschleunigung des Suchprozesses hat zum Ziel, die Bildinforma-tionen mit einer immer gröberen Auflösung und Abtastung sukzessive zu verrin-

gern. Dabei muss auf analoge Weise eine reduzierte Auflösung und Abtastungdes Templates einhergehen.Hierzu wird für Bild G die Gaußpyramide berechnet. Beispielsweise wird nur

jeder zweite Bildpunkt abgetastet (der Operator hierfür ist ↓2 ) und derErgebnisgrauwert ergibt sich aus der Faltung an der Stelle des Abtastpunktes

© B. Neumann 09

mit einem Mittelwertoperator, z.B. mit dem binomialen 3x3 Glättungsfilter

Demnach geht die (q+1)-te Ebenene der Pyramide aus der q-ten durch die

Operation

hervor.

Bem.: das Operatorzeichen für die doppelt so feine Bildabtastung ist ↑2.

Anderer Verfeinerungen/Vergröberungen der Abtastung werden analogdargestellt.

.binom

1 2 11

h 2 4 216

1 2 1

= ⋅

( ) ( )q q q (0)

binomG h 2G mit G G+ = ↓ =



Beschleunigung der Suchprozesse 4Gaußpyramide

Ebene4

1 2 1Wichtung

© B. Neumann 09

2

1

0

Entstehung einer Gaußpyramide für den 1D-Fall. Ebene 0entspricht dem Original. Der Informationsgehalt der höherenEbenen verringert sich sukzessive.

Gaußpyramide im 2D-Fall



Rotation und Skalierungbei der Suche zulassen

Sind Rotation und Skalierung bei der Suche erlaubt, so sollte

dies aus Gründen einer hohen Verarbeitungsgeschwindigkeit

bei der Modellerzeugung berücksichtigt werden.Für die Rotation müssen das Winkelin

[ ]

[ ]

,

,

min max

min max

krement und das Win-

kelintervall , für die Skalierung das Skalierungsin-

krement s sowie das Intervall s s angegeben werden.

∆φ

φ φ

∆

T

© B. Neumann 09

eines Bildpunktes im Template (in homogenen

Ko

Rotation x

min min

cos sin

, , sin cos ,

,

-1

i

Z 1 Z 1i i2 2

1S 1 S 1i i i2 2

i max

ordinaten):

= T RT

1 0 1 0 0

T 0 1 T 0 1 R 0

0 0 1 0 0 1 0 0 1

mit i i=0, 1,...,n und n

eines Bildpunkte

− −

−− −

′

− φ − φ = − = = φ φ

φ = φ + ⋅ ∆φ φ = φ + ⋅ ∆φ

ix x

Skalierung

min min, .

i

i max

s im Templates:

= s

mit s s i s i=0, 1,...,n und s s n s

′ ⋅

= + ⋅ ∆ = + ⋅ ∆i

x

x x

R

T-1

Drei Abbildungen sind für die

Rotation des Templates nötig

Documents

Grundlagen Bildverarbeitung Kap 5 Vers 2