Computer Vision4_Seite 1 Erste Stufe der Informationsgewinnung Interpretationszyklus für Einzelbilder Zuordnung von Modellausprägungen zu Bilddaten Generische

Computer Vision

4_Seite 1

Erste Stufe der Informationsgewinnung

Interpretationszyklus für Einzelbilder

Zuordnung von Modellausprägungen zu Bilddaten

Generische räumliche Beschreibung(parametrisierte Modelle für Szene,Objekte, Beleuchtung, Abbildung)

Modellausprägungen(Parametersätze)

Parameterschätzung,Klassifikation

Merkmale,Primitive

Modellelemente

ProjektionModellwelt-Bild

DigitalisiertesBild

Modellwelt

Synthetisches Bild,Szenenskizze

Bildsensor Display

Signal-verarbeitung

Bildauswertung

Synthese

BestimmtArt

Verfahrenextrahieren

BestimmtArt

Modifiziert

Computer Vision

4_Seite 2

Objektberandung Grauwertunterschiede Lokalisierung(Geometrie) Texturunterschiede Segmentierung

FreiheitsgradeForm

Oberflächeneigenschaft Grauwert Klassifikation(Radiometrie) Textur

Modellähnlichkeit Klassifikation(geometrisch, radiometrisch)

Bildmerkmale Informationsgewinnung

Bild

Merkmal 1-Bild

Merkmal N-Bild

......Merkmal 1 - Operator

Merkmal N - Operator

N Kanten-bilder

N Fleck-bilder

...

Kanten-operator

Fleck-operator

Computer Vision

4_Seite 3

Diskrete Signale

Videokamera

TDDn xnxnxnr ,,, 2211

D

dddde xnnxxxxd

1

22´´´ )(),(

D

dddb nnxxd

1

´´),(

´

,...,1

´ max),( ddDd

c nnxxd

Abstandsmaße im diskreten Gitter

Euklidische Distanz

City-block-Distanz

Schachbrett-Distanz

Aliasing räumlich und zeitlich:Signale halbe Abtastfrequenz!

Computer Vision

4_Seite 4

Textur-Deskriptoren• Texturelle• Statistische• Fourier

Berandungsdeskriptoren• Einfache• shape numbers• Fourier• Momente

Regionale Deskriptoren• Einfache• Topologische

Merkmale Informationsgewinnung

Computer Vision

4_Seite 5

Grauwert-Deskriptoren: Textur

Keine formale Beschreibung von Textur.Maße für Glattheit, Rauhigkeit, Regelmäßigkeit, etc.

Drei Ansatzpunkte zur Beschreibung von Textur:• Statistisch: glatt, rauh, körnig,grob• Strukturell: Anordnung geometrischer Primitive (z.B. reguläre Anordnung v. Linien)• Spektral: Detektion globaler Periodizitäten als Peaks im räumlichen Frequenzspektrum


Rauhfraktal

homogen

periodisch

Computer Vision

4_Seite 6

Textur: Statistische Ansätze


Rauhfraktal

homogen

.

.

.

.

.

.

0 255 g

h

1. Auswertung des Histogrammsdes durch die Maske definierten Bildbereichs

h

0 255 g

Computer Vision

4_Seite 7

Textur: Statistische Ansätze: Momente des Grauwerthistogramms

0 255 g

h

L

iii

L

ii

nin

ghgm

ghmgg

1

1

)(

)()()(

Wenn L die Anzahl der Grauwerte ist und h(gi) das Histogramm in der Maske, so sind die n-ten Momente:

Das zweite Moment heisst Varianz und wird mit ² bezeichnet. Es ist ein Maß des Grauwertkontrasts. Z.B. ist

R=0 für konstanten Grauwert und geht gegen 1 für große .n=3: Skewness des Histogrammsn=4: relative Plattheit des Histogramms

h

0 255 g 21

11

R


Computer Vision

4_Seite 8

Ergibt die und damitMatrix Cooccurrence

Matrix

ci,j ist ein Schätzwert für die bedingte Wahrscheinlichkeit, dass ein Paar von Punkten, das P erfüllt die Werte i,j hat.

Textur: Statistische Ansätze: 2. Auswertung der Coocurrence-Matrix

Nachteil der reinen Histogramm-Ansätze: keine Information über relativen Position der Pixel zueinander (Phase).

Information über die Positionen von Pixeln mit gleichem oder ähnlichem Grauwert: Coocurrence-Matrix.Positionsoperator Pk,l : In Bezug auf aktuellen Punkt (u,v) wähle aus Punkt (u+k, v+l).Anzahl der unterschiedlichen Grauwerte GMatrix A mit GxG Elementen ai,j : Anzahl, wie oft g(u,v)=i und g(u+k,v+l)=j. Coocurrence-Matrix C: Matrix A dividiert durch Anzahl der Punktpaare, die P erfüllen.

Beispiel:G=3: g {0,1,2}; Positionsoperator P1,1

10100

02011

00122

11011

21000Angewendetauf das Bild

021

232

024

AD

021

232

024

16

1CD


Computer Vision

4_Seite 9

Textur: Statistische Ansätze: Coocurrence-Matrix

Aus der Coocurrence-Matrix C können Maße zur Charakterisierung einer Textur gewonnen werden. Eine solche Menge von Deskriptoren ist z.B.:

(1) Maximale Wahrscheinlichkeit Stärkste Antwort auf P

(2) Moment der Elemente-Differenz der Ordnung k relativ kleiner Wert, wenn hohe Werte nahe Hauptdiag.

(3) Moment der inversen Elemente-Differenz der Ordnung k Gegenteiliger Effekt wie (2)

(4) Entropie Maß für die Unordnung

(5) Gleichförmigkeit Entgegengesetzt zu (4)

i jij

iji j

ij

i jk

ij

i jij

k

ijji

c

cc

ji

c

cji

c

2

,

)(log

)(

)(

)(max


Computer Vision

4_Seite 10

Textur: Statistische Ansätze: Unser´s Summen- und DifferenzhistogrammeVereinfachung gegenüber Coocurrence-Matrix

Bildfenster gleicher Größe, deren Mitte um du und dv gegeneinander verschoben ist:{gm´,n´ } = {gm+du, n+dv }, m = 1, ... ,M; n = 1, ... ,N

Summen und Differenzen der Grauwerte:

Summen- und Differenzhistogramme:

}{}{};{}{ ,,,,,, vuvu dndmnmnmdndmnmnm ggdggs

is

ssnmnmsvus iN

iNihissAnzahliNddiN)(

)()();|}({)(),;( ,,

id

ddnmnmdvud iN

iNihiddAnzahliNddiN)(

)()();|}({)(),;( ,,


Computer Vision

4_Seite 11

du

dvgm,n

sm,n = gm,n + gm+du,n+dv dm,n = gm,n - gm+du,n+dv

gm+du,n+dv

is

ss iN

iNih)(

)()(

id

dd iN

iNih)(

)()(

0 i

hshd

0 i


Computer Vision

4_Seite 12

Textur: Statistische Ansätze: Unser´s Summen- und Differenzhistogramme

Maße aus den normierten Histogrammen:

können berechnet werden für verschiedene du und dv, meist(1,0), (1,1), (0,1), (-1,0)

G

Gidd

UnserEntrds

G

is

UnserEntrs

G

Gid

UnserMitd

UnserKontrd

G

is

UnserMits

UnserKontrs

G

Gid

UnserZwMomd

G

is

UnserZwMoms

G

Gid

UnserMitd

G

is

UnserMits

ihihMihihM

ihMiMihMiM

ihMihM

ihiMihiM

)(ln)();(ln)(

)()(;)()(

)(;)(

)(;)(

,

2

0,

2,,

2

0

2,,

2,

2

0

2,

,

2

0,


Computer Vision

4_Seite 13

Textur: Statistische Ansätze: Momente

Zweidimensionale, kontinuierliche Funktion f(x,y): Moment der Ordnung (p+q):

für p,q = 0,1,2,...Wenn f(x,y) kontinuierlich und nicht-verschwindende Elemente nur in einem Teil derxy-Ebene, existieren Momente jeder Ordnung und sind eindeutig durch f(x,y) bestimmt.Die Menge aller Momente bestimmt seinerseits f(x,y).

Zentrale Momente

Für ein digitales Bild wird daraus

dydxyxfyxm qppq ),(

00

01

00

10),()()(m

myund

m

mxmitdydxyxfyyxx qp

pq

x y

qppq yxfyyxx ),()()(


Um Schwerpunkt verschoben: translationsinvariant

Computer Vision

4_Seite 14

Textur: Statistische Ansätze: MomenteZentrale Momente bis zur Ordnung 3:

;23),()()(

;22),()()(

;22),()()(

;23),()()(

;),()()(

;2

),()()(

;),()()(

;0;0),()()(

012

020330

03

012

20112112

21

102

02111221

12

102

203003

30

00

201

0220

02

00

210

2000

210

00

210

2002

20

00

011011

1111

010000

1010

0110

mymymyxfyyxx

mxmymxmyxfyyxx

mymxmymyxfyyxx

mxmxmyxfyyxx

m

mmyxfyyxx

m

mm

m

m

m

mmyxfyyxx

m

mmmyxfyyxx

mm

mmyxfyyxx

x y

x y

x y

x y

x y

x y

x y

x y

Normierte zentrale Elemente: ,...3,21200

qpfürqp

mitpqpq


Skaleninvarianz durchNormierung

Computer Vision

4_Seite 15

Textur: Statistische Ansätze: Invariante Momente

Eine Menge von 7 invarianten Momenten aus den zweiten und dritten Momenten:

Translations-, rotations- und skaleninvariant

])()(3)[)(3(

])(3))[()(3(

))((4])())[((

])()(3)[)(3(

)]3(3)[())(3(

)()3(

)3(

4)(

20321

2123003123012

20321

21230123003217

03211230112

03212

120302206

20321

2123003210321

12302

1230123012305

20321

212304

212303

211

202202

02201

C


Computer Vision

4_Seite 16

Textur: Vergleich der Trennungswirksamkeit von Texturmerkmalen


Quelle: Handbook of Computer Vision

Computer Vision

4_Seite 17

Detektion von Diskontinuitäten• Kanten• Linien• Punkte

Detektion von Ähnlichkeiten

Segmentierung Informationsgewinnung

Computer Vision

4_Seite 18

Detektion von DiskontinuitätenKanten

Segmentierung

Grauwertprofil erste Ableitung zweite Ableitung(Gradient) (Laplace)

Computer Vision

4_Seite 19

Merkmal Gradient

Motivation: Wenn Objekte homogen bezüglich Grauwert oder Texturmerkmal sind, dann treten an Objektgrenzen starke Gradienten auf.

Grauwertbild Gradientenbild

Bildmerkmale

Computer Vision

4_Seite 20

Merkmal Gradient

Bildmerkmale

yyxg

xyxg

eyxgyxg

y

yxg

x

yxgyxg

yxi

T

),(

),(

arctan

),(),(

),(,

),(),(

),(

Betrag gibt Stärke des Grauwertübergangs.• Rotationsinvariant• Invariant gegen homogene GW-ÄnderungenPhase gibt Richtung.• Invariant gegen homogene GW-Änderungen

Diskretisierung im Bild -> Differenzenquotienten

Computer Vision

4_Seite 21

Merkmal Gradient

Bildmerkmale

T

y

yxg

x

yxgyxg

),(,

),(),(

Diskretisierung im Bild -> Differenzenquotienten

x

yxxfyxxfx

yxfyxxfx

yxxfyxf

x

yxf

2

),(),(

),(),(

),(),(),( Rückwärts-x-Gradient –Dx

Vorwärts-x-Gradient +Dx

Symmetrischer-x-Gradient SDx

Ergibt Faltungsmaske

1,0,12

1x

SD

Analog y, z.B.:

1

0

1

2

1y

SD

Computer Vision

4_Seite 22

Erinnerung: Faltung

Bildmerkmale

0

10

20

30

40

50

60

70

80

90

100

1 3 5 7 9 11 13 15 17 190

5

10

15

20

25

30

-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9

j k

knjmgkjKnmgnmKnmg ),(),(),(),(),(~

j

jmgjKmgmKmg )()()()()(~

0

10

20

30

40

50

60

70

80

90

100

1 3 5 7 9 11 13 15 17 19

g(m) K(m)

m=17

Eindimensional, diskret

2D, diskret

ddyxgKyxgyxKyxg ),(),(),(),(),(~2D, kontinuierlich

Computer Vision

4_Seite 23

Erinnerung: Faltung

Bildmerkmale

2D, diskret, endl. Faltungskern

g1,1 g1,2 g1,3 g1,4 g1,5 g1,6 g1,7 g1,8 g1,9 g1,9 ...

g2,1 g2,2 g2,3 g2,4 g2,5 g2,6 g2,7 g2,8 g2,9 g2,9 ...

g3,1 g3,2 g3,3 g3,4 g3,5 g3,6 g3,7 g3,8 g3,9 g3,9 ...

g4,1 g4,2 g4,3 g4,4 g4,5 g4,6 g4,7 g4,8 g4,9 g4,9 ...

g5,1 g5,2 g5,3 g5,4 g5,5 g5,6 g5,7 g5,8 g5,9 g5,9 ...

g6,1 g6,2 g6,3 g6,4 g6,5 g6,6 g6,7 g6,8 g6,9 g6,9 ...

g7,1 g7,2 g7,3 g7,4 g7,5 g7,6 g7,7 g7,8 g7,9 g7,9 ...

g8,1 g8,2 g8,3 g8,4 g8,5 g8,6 g8,7 g8,8 g8,9 g8,9 ...

g9,1 g9,2 g9,3 g9,4 g9,5 g9,6 g9,7 g9,8 g9,9 g9,9 ...

... ... ... .... ... ... ... ... ... ... ...

K-1,-

1

K-1,0 K-1 1

K0,-1

XK0,0

K0,1

K1,-1 K1,0 K1,1

Bild {gm,n}, 0 m M, 0 n N Faltungskern {Km,n}

K

K

K

K

J

Jj

K

Kkhshs knjmKknjmgnmg ),(),(),(~

)1,1()3,3(

)0,1()4,3()1,1()5,3(

)1,0()3,4()0,0()4,4(

)1,0()5,4()1,1()3,5(

)0,1()4,5()1,1()5,5(

),()4,4()4,4(~1

1

1

1

Kg

KgKg

KgKg

KgKg

KgKg

kjKkjggj k

Beispiel:m = 4, n = 4, mhs=0Jk = 1, Kk = 1, nhs=0

K-1,-

1

K-1,0 K-1 1

K0,-1

XK0,0

K0,1

K1,-1 K1,0 K1,1

Computer Vision

4_Seite 24

Merkmal Gradient

Einige gängige Gradienten-Operatoren:

Bildmerkmale

121

000

121

101

202

101

121

000

121

101

202

101

111

000

111

101

101

101

10

01

01

10Roberts

Prewitt

Sobel

Isotrop

Computer Vision

4_Seite 25

Merkmal Gradient

Gradienten-Operatoren verstärken Rauschen:Vorzugsweise Operatoren mit Glättungseigenschaften

Sobel

Alternativ: Tiefpassfilterung mit Gaussfunktion und anschließende AbleitungGaussfunktion

Bildmerkmale

)2()2(

121

000

121

101

202

101

131211333231 ggggggDDD xyx

)()(2

1

2

1

2

1),(

2

2

2

2

2

22

22

22

yGxG

ee

eyxG

yx

yx

Computer Vision

4_Seite 26

Merkmal Gradient

Faltung mit der Ableitung der Gaussfunktion: Canny-Filter

Bildmerkmale

),(,1

,2

1),(

22

4

2

22

yxGyxyxeyxGyx

Separierbar in x und y

Computer Vision

4_Seite 27

Merkmal Laplace

Laplace-Operator einer 2-dimensionalen Funktion f(x,y):Im Fall einer diskreten 3x3-Maske:

Laplace-Operatoren verstärken Rauschen:Glättung mit Gauss-Funktion

Nulldurchgänge des Hildreth-Marr-gefilterten Bildes geben Kantenpixel-Kandidaten.Überschwellige Pixel des Gradientenbildes geben Kantenpixel-Kandidaten.

Bildmerkmale

2

2

2

22

y

f

x

ff

)(4

010

141

010

3,22,32,11,22,222 gggggfDdamitD

2

22

2

22

2

22

2

22

22224

22

2222

1

),(),(

yxyx

yxyx

eyxe

yxfeyxfe

Hildreth-Marr- oder Mexican Hat-Operator

2

2

22

222

2

2

1

yx

eGH

Computer Vision

4_Seite 28

Konturpunktextraktion beim Canny-Operator1. Faltung mit Filter

2. Im faltungsgefilterten Bild: Gradientenbetragsmaximum in Gradientenrichtung

Konturextraktion

),(,1

,2

1),(

22

4

2

22

yxGyxyxeyxGyx

dy

ydgyxGygycGyxG

)(),()(),(),(

BCD

AME

HGF

0°

45°90°135°

180°

225° 270° 315°

Gradienten-Richtung in M Maximumbedingung1°...22°, 158°...202°, 338°...360° b(A) b(M) und b(E) b(M)23°...67°, 203°...247° b(B) b(M) und b(F) b(M)68°...112°, 248°...292° b(C) b(M) und b(G) b(M)113°...157°, 293°...337° b(D) b(M) und b(H) b(M)

Wenn M Maximum, trage in Ergebnisbild Betrag und Richtung ein, sonst 0.

Computer Vision

4_Seite 29


Konturextraktion

Betra

g

Richtung

Computer Vision

4_Seite 30

Konturpunktextraktion beim Canny-Operator2. Gradientenbetragsmaximum in Gradientenrichtung

Konturextraktion

Computer Vision

4_Seite 31


Betra

g

Richtung

Konturextraktion

Computer Vision

4_Seite 32

Konturpunktextraktion beim Canny-Operator2. Gradientenbetragsmaximum in Gradientenrichtung

Konturextraktion

Computer Vision

4_Seite 33

Kantenpixel-Verkettung

Vorgestellte Methoden liefern Intensitäts-DiskontinuitätenLeider nicht immer Objektränder: Zusätzliche Struktur undKantenunterbrechungen durch Rauschen und

Beleuchtungsdiskontinuitäten. Daher weitere Verarbeitung zur Zusammenstellung von

Kantenpixelkandidaten zu Rändern.

1. Unterdrückung zusätzlicher Strukturen:I.A. kleiner GradientenbetragVorgehen:Zwei Schwellen zur Unterdrückung: 1. Größere Schwelle zur Filterung ausgeprägter Konturpunkte2. Dort Verfolgung der Kontur mit kleinerer Schwelle

Konturextraktion

Computer Vision

4_Seite 34

2. Verdünnung auf pixelbreite Strukturen:Durch Diskretisierung bis zu 3 Pixel breite Strukturen.Gütekriterium in 3x1-Maske in Gradientenrichtung (Lacroix)

3. Lokale Verarbeitung:Analyse in einer kleinen Nachbarschaft (z.B. 3x3 oder 5x5) um einenKandidaten:Alle ähnlichen Kandidaten werden verbunden. Rand von Pixeln ähnlicher Eigenschaft.Verwendete Maße: (1) Gradientenstärke und (2) Gradientenrichtung

TyxyxTyxgyxg ´)´,(),(´)´,(),(

Konturextraktion

Computer Vision

4_Seite 35

Histogramm-Auswertung

Bild eines Merkmals, das sich für das Objekt charakteristisch ausprägt:

Bildsegmentierung durch Schwellwerte

0

200

400

600

800

1000

1200

1400

20 40 60 80 100 120 140 160 180 200 220 240 260

An

zah

l B

ild

pu

nkte

Helligkeit (Grauwert)

Hintergrund Objekt

Histogrammsegmentierung

Schwelle T

g(x,y) H(x,y)=0, wenn g(x,y) TH(x,y)=1, wenn g(x,y) T

SegmentierungMerkmalsbild

Computer Vision

4_Seite 36

Auffinden der Schwelle mittels Histogramm-Auswertung (1)

Verteilungsfunktionen (Wahrscheinlichkeitsdichten) eines Merkmals z für Objekt pO(z) und Hintergrund pH(z)

mit a priori Auftrittswahrscheinlichkeiten von Objektpunkten PO und Hintergrundpunkten PH. Bedingung PO + PH = 1.

Ergibt Gesamtwahrscheinlichkeitsdichte p(z) = PO pO(z) + PH pH(z)

Im Gauss´schen Fall:


2

2

2

2

2

)(

2

)(

22)( H

H

O

O z

H

H

z

O

O eP

eP

zp

Computer Vision

4_Seite 37


Wahrscheinlichkeit einer Fehlzuordnung E:

Minimierung von E

Gauss´sche pO und pH: Einsetzen, logarithmieren und vereinfachen ergibt quadratische Gleichung

mit


HO

OHHOOHHOOHHOHO

HHOO

T

OOO

T

HH

P

PCBA

CTBTA

TpPTpPdT

TdE

dzzpPPdzzpPTE

ln2);(2;

0

)()(0!)(

)()()(

2222222222

2

Computer Vision

4_Seite 38


Vorgehen nach obiger Methode:

1. Trainingsstichprobe Bildmaterial2. Histogramm für Objektpixel hO

3. Histogramm für Hintergrundpixel hH

4. Berechnung von O und O aus hO

5. Berechnung von H und H aus hH

6. Berechnung von A, B und C:

7. Berechnung der Schwelle durch Lösung der quadratischen Gleichung

8. Anwenden der Schwelle auf neues Bildmaterial


HO

OHHOOHHOOHHOHO P

PCBA

ln2);(2; 2222222222

02 CTBTA

Computer Vision

4_Seite 39

Darstellung der Objekt-Berandung: Ketten-Code

Darstellung und Beschreibung

x x X

x X

X X

X x

X X

X X

X X

X x

2

21

10 0 6

7

Kettencode-Erstellung:Folge der Richtungen entlang der Kontur ab beliebigem Startpunkt.Beispiel: 22110067665654323

Anfangspunktinvarianz1. Startpunkt-Normierung:Verschiebe zirkular so, dass die Sequenz eine Zahl minimaler Größe bildet.Beispiel: 22110067665654323 00676656543232211

Rotationsinvarianz2. Rotationsnormierung:Erste Differenz: Anzahl der Richtungen, die zwei aufeinanderfolgende Elemente des Codes trennen.Beispiel: 22110067665654323 07070617071777717

Anfangspunkt- und RotationsinvarianzKettencode Rotationsnormierung StartpunktnormierungBeispiel: 22110067665654323 07070617071777717 06170717777170707

1

0

23

4

5 6 7

1

0

23

4

5 6 7

7

654

3

21

Computer Vision

4_Seite 40

Darstellung der Objekt-Berandung: Polygon-Approximationen

Polygon-Approximationen einer digitalen Berandung mit beliebiger Genauigkeit.Aber gesucht: Repräsentation der wesentlichen Berandungseigenschaften mit

möglichst kleiner Anzahl an Segmenten.Nicht-triviales Problem iterativer Suche.

Einfache Methode für Polygone mit minimalem Umfang:

1. BedeckungRandkurve mitrechtwinkligangeordnetenQuadraten


2. Gerade Verbindungen der Außenecken des „Quadrate-schlauches“

Computer Vision

4_Seite 41

Beschreibung der Objekt-Berandung: Polardarstellung


r

Schwerpunkt

Ar

Schwerpunkt

A

r

r

A/2 A/2

A/2

Computer Vision

4_Seite 42

Beschreibung der Objekt-Berandung: Momente

1. Umwandlung einer Berandung in eine 2. Berechnung Momente der Kurve

eindimensionale Kurve (z.B. Polardarst.)


r

Schwerpunkt

A

r

A/2

A/2

K

iii

K

ii

nin

K

iii

K

ii

nin

r

mit

g

ellungPolardarstBei

p

mit

p

1

1

1

1

)(

)()()(

:

)(

)()()(

Computer Vision

4_Seite 43

Beschreibung der Objekt-Berandung: Fourier-Deskriptoren

Rand ermittelt: Zähler s längs Berandung ergibt Menge {x(s),y(s)} s=0,...,L-1Als komplexe Zahl: u(s) = x(s) + iy(s)L-periodisch für geschlossene Konturen.

DFT:

a(k): Fourier-Deskriptoren der Berandung.

Transformationseigenschaften:Identität u(s) -> a(k)Translation u´(s) = u(s)+u0 -> a´(k) = a(k)+ u0(k)Skalierung u´(s) = u(s) -> a´(k) = a(k) Anfangspunkt u´(s) = u(s-s0) -> a´(k) = a(k) exp(-is0k/L)Rotation u´(s) = u(s) exp(i2) -> a´(k) = a(k) exp(i2)


10,)()(

10,)(1

)(

1

0

2

1

0

2

Lkesuka

LsekaL

su

L

s

L

ksi

L

k

L

ksi

Computer Vision

4_Seite 44

Beschreibung der Objekt-Berandung: Fourier-Deskriptoren

Ähnlichkeit der Form von Randkurven mit Fourier-DeskriptorenRandkurven u(s) und v(s) mit a(k) und b(k):

Ist für mittelwertfreie u(s) und v(s) erfüllt, wenn


1

0

2

00,,,

00 )()(min),,,(00

L

s

i

suuessvsusud

2)(

0*

2

0

)()(min)(min

/2,)()()(

)cos()(

)sin()(tan

)(

)cos()(

0

ki

i

kk

kk

k

kk

ekbkadddann

Lsekckbkamit

kkc

kkc

kb

kkc

u

k

d kann für jedes = (s0) berechnet werden.Das Minimum ergibt dann d, welches dann ein Ähnlichkeitsmaß für die Formen ist.

Computer Vision

4_Seite 45

Ortsraum - Frequenzraum

Signale können als Überlagerung (Summe) periodischer Funktionen

mit Frequenzen undmit Amplituden F

dargestellt werden:

Transformation in Frequenzraum

Diskrete Fourier-(Rück)Transformation

Frequenzraum-Darstellung gibt an,mit welcher Häufigkeit jeweilsperiodische Funktionen vorkommen.

Darstellung im Frequenzraum

Cosinus Funktionen Sinus Funktionen

xN

kkFxN

kkF

NkxkFxkFxy

o

N

ke

kko

N

kke

2sin)(

2cos)(

2;sin)(cos)()(

1

0

1

0

y(x)

Computer Vision

4_Seite 46

Ortsraum - Frequenzraum

Im Frequenzraum sind viele Operationen günstiger.Alle linearen Operationen z.B.

Hochpass, Tiefpass, Bandpass und Bandsperremit hoher Güte

Erkennung periodischer StrukturenManipulation periodischer Strukturen

Nach einer Bearbeitung im Frequenzraum Fe(k)→Fe

~(k) und Fo(k)→Fo~(k)

kann wieder in den Ortsraum zurück transformiert werden.


xN

kxy

NkFx

N

kxy

NkF

N

kxxy

NkFxxy

NkF

N

xo

N

xe

kk

N

xo

N

xke

2sin)(

1)(;

2cos)(

1)(

2;sin)(

1)(;cos)(

1)(

1

0

1

0

1

0

1

0

Signal y im Ortsraum, Abtastwerte y(i)

Analyse:TransformationOrtsraum Frequenzraum

Synthese:TransformationFrequenzraum Ortsraum

xN

kkFxN

kkF

NkxkFxkFxy

o

N

ke

kko

N

kke

2sin)(

2cos)(

2;sin)(cos)()(~

~1

0

~

~1

0

~

Computer Vision

4_Seite 47

Ortsraum – Frequenzraum

Polare Notation – komplexe Schreibweise


Fe(k)

Fo(k)

F(k)

)(

)(arctan)(

;)()()( 22

kF

kFk

kFkFkF

e

o

oe

Amplitude (Magnitude)

Phase)](sin[)()(

)](cos[)()(

kkFkF

kkFkF

o

e

Komplexe Schreibweise )()()( kiekFkF

|F(k

)|

xN

kxy

NkFx

N

kxy

NkF

N

kxxy

NkFxxy

NkF

N

xo

N

xe

kk

N

xo

N

xke

2sin)(

1)(;

2cos)(

1)(

2;sin)(

1)(;cos)(

1)(

1

0

1

0

1

0

1

0

1

0

1

0

)()(;2

;)(1

)(N

x

xik

N

x

xi kk ekFxyN

kexy

NkF

Computer Vision

4_Seite 48


Filterung der abgetasteten Funktion y:1. Analyse

2. Multiplikation mit Filterfunktion

3. Synthese


Filterfunktion, Abtastwerte f(k)

)()()(~

)()()(~

kFkfkF

kFkfkF

oo

ee

xN

kxy

NkFx

N

kxy

NkF

N

kxxy

NkFxxy

NkF

N

xo

N

xe

kk

N

xo

N

xke

2sin)(

1)(;

2cos)(

1)(

2;sin)(

1)(;cos)(

1)(

1

0

1

0

1

0

1

0

N

xkkF

N

xkkF

N

xkkFkFxy

o

N

ke

kko

N

kke

2sin)(

~2cos)(

~

2;sin)(

~cos)(

~)(~

1

0

1

0

Computer Vision

4_Seite 49

Ortsraum – FrequenzraumEigenschaften der Fourier-Transformation


Aus: Handbook of Computer Vision

Computer Vision

4_Seite 50


Eigenschaften der Fourier-Transformation



Computer Vision

4_Seite 51

Ortsraum – FrequenzraumBezüglich Fourier-Transformation invariante Funktionen



Computer Vision

4_Seite 52

Ortsraum – FrequenzraumWichtige Fourier-Transformationspaare



Computer Vision

4_Seite 53

Ortsraum – Frequenzraum2-Dimensionale diskrete Fourier-Transformation


1

0

1

0

)v(2

1

1

0

1

0

)v(2

)v,(1

)v,()k,(

),(1

),()v,(

N

j

N

k

kujN

i

N

j

N

k

kujN

i

eugN

ugFjg

ekjgN

kjgFug

Computer Vision

4_Seite 54

Beschreibung der Objekt-Berandung: Umschreibendes Rechteck (Bounding box)


1. Große Halbachse: Gerade, welche die am weitesten entfernten Punkte der Objektberandung verbindet.

2. Kleine Halbachse: Zur großen Halbachse senkrechte kürzeste Gerade, so dass die Objektberandung im damit gebildeten Rechteck liegt.

3. Exzentrizität: Verhältnis von großer zu kleiner Halbachse

Computer Vision

4_Seite 55

Bildfolgen: statische Kamera Bewegte Kamera

Merkmale aus Bildfolgen

Zeit

Original

Aufgaben:•Detektion sich bewegender Objekte•Verfolgung sich bewegender Objekte•Objektklassifikation anhand Bewegungsmuster

Zeit

Aufgaben:•Eigenbewegungsschätzung•Detektion sich bewegender Objekte•Verfolgung sich bewegender Objekte•Objektklassifikation anhand Bewegungsmuster

Computer Vision

4_Seite 56


Im Bildstapel ergeben

Statische Objektpunktesenkrechte Geraden

Sich bewegende Bildpunktegleichförmige Bewegung:

geneigte GeradenBeschleunigte Bewegung:

gekrümmte Kurven

Computer Vision

4_Seite 57


Differenzbilder für statischen Hintergrund mitsich bewegenden Fahrzeugen

Dynamik eines Bildpunktes

Computer Vision

4_Seite 58

Bildfolgen: statische Kamera: Raum-Zeit-Kanten

Merkmale aus BildfolgenZeit

Flugzeug-Template

Raumkanten

Original

Raum-Zeit-Kanten

Raumkantenbild

Grauwertbild

Raum-Zeit-Kantenbild

Computer Vision

4_Seite 59

Bildfolgen: statische Kamera: Raum-Zeit-Kanten


Interpretation einer BildfolgeGt1(x,y), Gt2(x,y), ..., GtN(x,y)

als dreidimensionales FeldG(x,y,t)

Raum-Zeit-Kantenz.B. durch3-D Sobel-Operator

Beispiel: Infrarotbildfolge (Luftbild) eines Ausschnitts der Meeresoberfläche

Computer Vision

4_Seite 60

Bildfolgen: statische Kamera: Bewegungssegmentierung

Differenzbildverfahren:


01

1

-1

1

Empfindlich gegen

BeleuchtungsänderungRauschenPeriodische Vorgänge

Computer Vision

4_Seite 61


Hintergrundschätzung:Betrachtung der Vergangenheit zur Modellierung des „Normalprozesses“Ein Pixel:


g(t)

t

g(t)

t

g(t)

t

g(t)

t

g(t)

t

Ideal konstant Konstant mit Rauschen Einmaliges Ereignis

Langsame Veränderung Periodische Schwankung

Computer Vision

4_Seite 62

Konstant mit Rauschen


Hintergrundschätzung:Betrachtung der Vergangenheit zur Modellierung des „Normalprozesses“Histogramm über M Bilder:


H(g)

g

H(g)

g

H(g)

g

H(g)

g

H(g)

g

Ideal konstant Einmaliges Ereignis

Langsame Veränderung Periodische Schwankung

N

i

gg

i

iM

iie

h

NgH

1

2

1 22

2

1)(

ge

Änderung, wenn HM(g) < HSchwelle

Computer Vision

4_Seite 63


Hintergrundschätzung: VorgehensweiseBetrachtung der Vergangenheit zur Modellierung des „Normalprozesses“Berechnung eines Bewegungssegment-Bildes (binär Bewegtobjekt-stat.

Hintergrund):Für jedes Pixel1. Histogramm über die M letzten Bilder2. Modellierung des Histogramms als Summe von Gaussfunktionen3. Aktueller Grauwert in Modell?

Ja: Eintrag als Hintergrund-Pixel (z.B. 0 für unverändert), Update ModellNein: Eintrag als Vordergrund-Pixel (z.B. 1 für verändert), Update Modell


...

H(g)

g

H(g)

g

...

Letzte M Bilder aktuelles Bild

Histogramm für jedes Pixel

In Modell

In ModellBewegungssegment-Bild

Computer Vision

4_Seite 64

Bildfolgen: Kamera-BewegungsschätzungBildstabilisierung („Wackelkompensation“): Anwendung z. B.

Handycams

Annahmen: Translationen der Kamera vernachlässigbar, nur wenige sich in der Szene bewegende Objekte.Drehung der Kamera um Achsen des Bildsensors (Nick- und Gier-, kein Rollwinkel)


Feste Szenengegenstände

Kamera-drehung

Bildsensor

Bild Bild

Verschiebung

Computer Vision

4_Seite 65

Bildfolgen: Kamera-BewegungsschätzungBildstabilisierung („Wackelkompensation“): Anwendung z. B.

Handycams

Vorgehen: 1. Schätzung der Translation: Lage des Kreuzkorrelationsmaximums zweier Frames2. Korrektur der Translation

Berechnung z.B. mittels FFT:


*21

1 )},({)},({),( yxgFyxgFFyxKKF tt

... ...

xmaxymax

Lage des Maximums der Kreuzkorrelationsfunktion:xmax, ymax

Computer Vision

4_Seite 66

Bildfolgen: Bewegungsschätzung

Verfolgung von Merkmalen1. „Blockmatching“Vollständige Suche eines Bildausschnitts in einer Umgebung um

Ursprungsposition


+

Bild zur Zeit t Bild zur Zeit t+

t

t+

Computer Vision

4_Seite 67


Verfolgung von Merkmalen1. „Blockmatching“: Prinzip


t t+ t+Ausschnitt aus Bild zur Zeit t:Template zur Suche imnächsten Bild

Suche im Bild zur Zeit t+:An welcher Stelle „passt“ dasTemplate am besten?Suche beschränkt auf Suchbereichum Templatepos. im Bild z. Zeit t.

Position im Bild zur Zeit t+, an derdas Template der Bildstruktur amÄhnlichsten ist.

Computer Vision

4_Seite 68


Verfolgung von Merkmalen1. „Blockmatching“: Vorgehen


• Messung der Ähnlichkeit eines Bildausschnitt B(t) von Bild zur Zeit t mit einem darunter liegenden Ausschnitt B(t+) gleicher Form und Größe von Bild zur Zeit t+. Ein Ähnlichkeitsmaß wird für eine Menge von Verschiebungen von B(t) gegenüber der Ursprungsposition berechnet.• Verschiebung, bei der die Ähnlichkeit maximal ist und einen Schwellwert überschreitet, gibt eine Schätzung für die Blockbewegung.• Ähnlichkeitsmaße: Euklidische Distanz (Unähnlichkeit) Kreuzkorrelation (Ähnlichkeit)

t t+

Computer Vision

4_Seite 69


Verfolgung von Merkmalen1. „Blockmatching“: Ähnlichkeitsmaße


i

i

j

j

ji

K

Km

K

KnnjminjmijiE tggjid 2

,, )(),,,(

i

i

j

j

i

i

j

j

ji

i

i

j

j

ji

K

Km

K

Kn

K

Km

K

Knnjminjmi

K

Km

K

Knnjminjmi

jiKK

tgtg

tgtg

jid2

,2

,

,,

)()(

)()(2

),,,(

-Ki, -Kj

-Ki, +Kj

+Ki, -Kj

+Ki, +Kj

Template „Block“

Verschiebungen i und j um Ursprungsposition i,j des Templates

Normierte Kreuzkorrelation:

Euklidischer Abstand:

i

i

j

j

ji

K

Km

K

KnnjminjmijiCB tggjid ,, )(),,,(

City-Block-Distanz:

Computer Vision

4_Seite 70

Bildfolgen: BewegungsschätzungOptischer Fluss

Grundsätzliche Annahme:

Jedes Pixel zur Zeit t+1 einer Bildsequenz kann modelliert werden als ein Pixel zur Zeit t, das um einen Vektor (x, y)T verschoben wurde: Konstanz der Beleuchtung.

Optischer Fluss: Finde ein Vektorfeld (x(x,y), y(x,y))T, das die opt. Fluss Gleichung löst.

Problem: UnterbestimmtheitBetrachte Grauwertbild mit 8 Bit Dynamik und 512x512 Pixel: Durchschnittlich 1024 Pixel/Grauwert.

Zusätzliche Einschränkungen nötig:1. Glattheit des Flussfeldes2. Kleine Flussvektoren


)),,(),,(()1,,( tyxyyyxxxFtyxF

Computer Vision

4_Seite 71


Zusätzliche Einschränkungen:1. Glattheit des Flussfeldes2. Kleine Flussvektoren

Dann Entwicklung der opt. Fluss Gleichung in Taylor-Reihe und Vernachlässigung quadratischer und höherer Glieder:

Lokale Gleichung erster Ordnung „optical flow constraint equation“Nicht an jedem Punkt lösbar, da zwei Unbekannte.Nimm gleiche Flussvektoren in kleiner Umgebung um Punkt (x,y) an (Glattheitsannahme) überbestimmtes Gleichungssystem

Einschränkung: x und y klein genug für Abbruch der Taylor-Reihe.Abhängig von Bildinhalt, gewährleistet nur bei kleiner ein Pixel.


),(),(),(),(),( yxy

Fyxyyx

x

Fyxxyx

t

F

x

g

t t+t

x

gg(x0,t)

g(x0,t+t)

x0

dx

dgxmxg

Computer Vision

4_Seite 72



ty

tx

y

x

yyx

yxx

yxRyxtyx

tyyxx

yyxxt

FF

FF

FFF

FFF

yxyxRFFF

yx

FFF

FFF

yxy

Fyxyyx

x

Fyxxyx

t

F

DD

,v

vv,WmitvW

:ergibtsetzenNullvundvnachEvonAbleitung

).,(umRegion:),(mitvvE

sFehlertermdesgMinimierundurch),(Punktanv

vvvonBestimmung

0vvequationconstraintflowoptical

vvbweiseKurzschreiinoder

),(),(),(),(),(

2

2

yx

0000),(),(

2yx

y

x

00

Computer Vision

4_Seite 73



0.vPunkt dieseman setze und Null als betrachte ,1Wenn

.,nach , Sortiere

:Maßnahme

kt.unbeschrängkeit Geschwindi Null n)(Gradiente von Elemente alle sinddann ,0Wenn

undsingulär ist dann ,0Wenn

und ergibt Einsetzen

:0,wenn

, nEigenwertedenmitundren EigenvektodieinLösungdergEntwicklun

.Eigenwertenegativenichtreelledefinit,semipositivundhsymmetriscistWMatrix

,v

vv,WmitvW

max

maxmin21

1

2222

2

22

1

11

221121

2121

2

2

D

D

DD

D

DD

W

W

WW

v

FF

FF

FFF

FFF

T

TT

ty

tx

y

x

yyx

yxx

Computer Vision

4_Seite 74


Berechnungsvorschrift


),(),(2

1),(

)1,()1,(2

1),(

),1(),1(2

1),(

:nDifferenze zentrale als tung Zeitableiund Gradienten

.100: Bedingungfür WahlMögliche

:ichkeitenerungsmöglImplementi

10

00

00

00

minmaxminmax

minmax

max

2211

maxmax

yxFyxFyxF

yxFyxFyxF

yxFyxFyxF

sonst

für

für

v

ttttt

tty

ttx

Computer Vision

4_Seite 75


Verfolgung von Merkmalen2. Verfolgung von Monotonie-Operator-Blobs

Betrachte das „Grauwertgebirge“ eines Bildes:„Kuppen“ und „Senken“ sind stabile Merkmale von ObjektenQuadratische Formen: Zweite Ableitung konstant in Nähe Kuppe bzw.

Senke


Computer Vision

4_Seite 76


Verfolgung von Merkmalen2. Verfolgung von Monotonie-Operator-Blobs

Am Boden einer Senke bzw. an der Decke einer Kuppe ist die dritte Ableitung klein.


Computer Vision

4_Seite 77

Bildfolgen: Flussvektor-Schätzer nach Lukas und KanadeErmittlung der Verschiebung eines kleinen Blocks an Position x,y in Bild zur Zeit t2

gegenüber Bild zur Zeit t1: dx, dy


Blockyx

yxyx dydxIyxIddE,

221 ,,,

Blockyx

yxyx

yx

yx

dydxIdydxIyxI

yx

ddE

,

221

,,,2

,

yxyx d

y

yxId

x

yxIyxIdydxI

,,,, 22

22

Computer Vision

4_Seite 78

Bildfolgen: Flussvektor-Schätzer nach Lukas und KanadeErmittlung der Verschiebung eines kleinen Blocks an Position x,y in Bild zur Zeit t2

gegenüber Bild zur Zeit t1: dx, dy


BlockyxyxId

dyxIyxI

BlockyxyxIyxIdy

yxId

x

yxI

Blockyxdy

yxId

x

yxIyxIyxI

BlockyxdydxIyxIyx

ddE

ty

xyx

yx

yx

yxyx

,),(),(),(

,),(),(),(),(

,0),(),(

),(),(

,0),(),(0),(

1222

2221

21

Documents

Computer Vision4_Seite 1 Erste Stufe der Informationsgewinnung Interpretationszyklus für Einzelbilder Zuordnung von Modellausprägungen zu Bilddaten Generische