Post on 06-Apr-2015
transcript
6_Informationsgewinnung_BildSeq Seite 1
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
6_Informationsgewinnung_BildSeq Seite 2
Merkmale aus Bildfolgen
Im Bildstapel ergeben
Statische Objektpunkte
senkrechte Geraden
Sich bewegende Bildpunkte
gleichförmige Bewegung: geneigte Geraden
beschleunigte Bewegung: gekrümmte Kurven
6_Informationsgewinnung_BildSeq Seite 3
Merkmale aus Bildfolgen: 1. Änderungsdetektion
Differenzbilder für statischen Hintergrund mitsich bewegenden Fahrzeugen
Dynamik eines Bildpunktes
6_Informationsgewinnung_BildSeq Seite 4
Bildfolgen: statische Kamera: Raum-Zeit-Kanten
Merkmale aus Bildfolgen: 1. Änderungsdetektion
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
6_Informationsgewinnung_BildSeq Seite 5
Bildfolgen: statische Kamera: Raum-Zeit-Kanten3D-Sobel-Oparator
Merkmale aus Bildfolgen: 1. Änderungsdetektion
6_Informationsgewinnung_BildSeq Seite 6
Bildfolgen: statische Kamera: Raum-Zeit-Kanten
Merkmale aus Bildfolgen: 1. ÄnderungsdetektionZeit
Flugzeug-Template
Raumkanten
Original
Raum-Zeit-Kanten
Raumkantenbild
Grauwertbild
Raum-Zeit-Kantenbild
6_Informationsgewinnung_BildSeq Seite 7
Bildfolgen: statische Kamera: BewegungssegmentierungDifferenzbildverfahren:
Merkmale aus Bildfolgen: 1. Änderungsdetektion
01
1
-1
1
Empfindlich gegen
BeleuchtungsänderungRauschenPeriodische Vorgänge
6_Informationsgewinnung_BildSeq Seite 8
Bildfolgen: statische Kamera: BewegungssegmentierungHintergrundschätzung:
Betrachtung der Vergangenheit zur Modellierung des „Normalprozesses“Ein Pixel:
Merkmale aus Bildfolgen: 1. Änderungsdetektion
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
6_Informationsgewinnung_BildSeq Seite 9
Konstant mit Rauschen
Bildfolgen: statische Kamera: BewegungssegmentierungHintergrundschätzung:
Betrachtung der Vergangenheit zur Modellierung des „Normalprozesses“Histogramm über M Bilder:
Merkmale aus Bildfolgen: 1. Änderungsdetektion
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
6_Informationsgewinnung_BildSeq Seite 10
Bildfolgen: statische Kamera: BewegungssegmentierungHintergrundschätzung: Vorgehensweise
Betrachtung 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
Merkmale aus Bildfolgen: 1. Änderungsdetektion
...
H(g)
g
H(g)
g
...
Letzte M Bilder aktuelles Bild
Histogramm für jedes Pixel
In Modell
In ModellBewegungssegment-Bild
6_Informationsgewinnung_BildSeq Seite 11
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)kleiner Öffnungswinkel und kleiner Drehwinkel
Merkmale aus Bildfolgen: 2. Bildstabilisierung
Feste Szenengegenstände
Kamera-drehung
Bildsensor
Bild Bild
Verschiebung
u
f
u = f tan u´ = f tan()
6_Informationsgewinnung_BildSeq Seite 12
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:
Merkmale aus Bildfolgen: 2. Bildstabilisierung
*21
1 )},({)},({),( yxgFyxgFFyxKKF tt
... ...
xmaxymax
Lage des Maximums der Kreuzkorrelationsfunktion:xmax, ymax
6_Informationsgewinnung_BildSeq Seite 13
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
1. „Blockmatching“Vollständige Suche eines Bildausschnitts in einer Umgebung um
Ursprungsposition
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
+
Bild zur Zeit t Bild zur Zeit t+
t
t+
6_Informationsgewinnung_BildSeq Seite 14
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
1. „Blockmatching“: Prinzip
Merkmale aus Bildfolgen : 3. Bewegungsschätzung
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.
6_Informationsgewinnung_BildSeq Seite 15
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
1. „Blockmatching“: Vorgehen
Merkmale aus Bildfolgen : 3. Bewegungsschätzung
• 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+
6_Informationsgewinnung_BildSeq Seite 16
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
1. „Blockmatching“: Ähnlichkeitsmaße
Merkmale aus Bildfolgen : 3. Bewegungsschätzung
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:
6_Informationsgewinnung_BildSeq Seite 17
Behandlung des „Blendenproblems“:
Abhilfe: Eckendetektor nach Harris und Stephens
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
1. „Blockmatching“: Auswahl geeigneter Blocks
Merkmale aus Bildfolgen : 3. Bewegungsschätzung
?
?
!Beide Flußkomponenten (lokal) nur an „Grauwertecken“ zu schätzen!
6_Informationsgewinnung_BildSeq Seite 18
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
1. „Blockmatching“: Auswahl geeigneter Blocks
Merkmale aus Bildfolgen : 3. Bewegungsschätzung
Abhilfe: Eckendetektor nach Harris und Stephens„Eckenhaftigkeits“maß E:Berechnung aus Strukturtensor S, wobei sich die Mittelung über ein lokales Fenster erstreckt,z.B. Faltung mit 3x3 Gauss.
222
2
2222
2
2
2
2
2
11det
,,
y
g
x
g
k
k
y
g
x
g
y
g
x
gStrace
k
kSE
y
g
y
g
x
g
y
g
x
g
x
g
y
g
y
g
x
g
y
g
x
g
x
g
y
g
x
g
y
g
x
gS
T
@@
@
6_Informationsgewinnung_BildSeq Seite 19
“unstrukturiertes” Gebiet:
in keiner Richtung Änderung
“Kante”:
keine Änderung in Kantenrichtung
“Ecke”:
Wesentliche Änderungen in alle Richtungen
Merkmale aus Bildfolgen : 3. Bewegungsschätzung
Grundlegende Idee des Harris und Stephens Detektors
6_Informationsgewinnung_BildSeq Seite 20
Fenster- funktion
oderw(x,y) =Gauss1 in Fenster, 0 außerhalb
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Intensitätsänderung für eine Verschiebung [u,v]
Bilineare Approximation für kleine Verschiebungen [u,v]:
2
,
,,,, yx
yxyx vgugyxwvuEvgugyxgvyuxg
yx
yxgvyuxgyxwvuE,
2),(),(,,
yxy
yxyx
yxyx
yxx
gyxwggyxw
ggyxwgyxw
Sv
uSvuvuE
,
2
,
,,
2
),(),(
),(),(
mit ,,@@
6_Informationsgewinnung_BildSeq Seite 21
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Intensitätsänderung E(u,v) im verschobenen Fenster: Eigenvektoren von S sind Achsen maximaler Varianz -> Eigenwertanalyse
1, 2 – Eigenwerte von S
Richtung höchster Änderung
Richtung niedrigster Änderung
(min)1/2
(max)1/2
Ellipse E(u,v) = const
yxy
yxyx
yxyx
yxx
gyxwggyxw
ggyxwgyxw
Sv
uSvuvuE
,
2
,
,,
2
),(),(
),(),(
mit ,,@@
6_Informationsgewinnung_BildSeq Seite 22
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
1, 2 – Eigenwerte von S
(min)1/2
(max)1/2
Ellipse E(u,v) = const
1
2
“Ecke”1 und 2 groß, 1 ~ 2;E wächst nach allen Richtungen
“Kante” 1 >> 2
“Kante” 2 >> 1
“Flaches” Gebiet
Klassifikation von Bildpunkten mittels Eigenwerten von M:
Abgeleitetes Eckhaftigkeitsmaß R:
(k – empirische Konstante, k = 0.04-0.06)
2121
2
spur ;det
spur det
SS
SkSR@@
@@
1 und 2 klein;E weitgehend konstant in allen Richtungen
6_Informationsgewinnung_BildSeq Seite 23
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Klassifikation von Bildpunkten mittels “Cornerness” R:
1
2
“Ecke”
“Kante”
“Kante”
“unstr.”
• R hängt nur von den Eigenwerten von M ab.
• R ist stark positiv für eine Ecke
• R ist stark negativ für eine Kante
• |R| ist klein für ein unstrukturiertes Gebiet
R > 0
R < 0
R < 0|R| klein
6_Informationsgewinnung_BildSeq Seite 24
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsBetrachte das „Grauwertgebirge“ eines Bildes:„Kuppen“ und „Senken“ sind stabile Merkmale von ObjektenQuadratische Formen: Zweite Ableitung konstant in Nähe Kuppe bzw.
Senke
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Grauwertbild „Grauwertgebirge“
6_Informationsgewinnung_BildSeq Seite 25
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsAm Boden einer Senke bzw. an der Decke einer Kuppe ist der
Gradientenbetrag klein.
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
6_Informationsgewinnung_BildSeq Seite 26
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsAlternative zu Gradientenbetrachtung: Monotonie-Operator (hier
Kuppe)
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
iz, jz
iz + iM , jz + jM
iz + iM , jz - jM iz - iM , jz - jM
iz - iM , jz + jM
sonst
jjiigjjiigjjiigjjiigggjigwennjig MMMMMMMM
K 0
)},(),,(),,(),,({),(1),(~
6_Informationsgewinnung_BildSeq Seite 27
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsAnwendung von Monotonie-Operatoren
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
sonst
jjiigjjiigjjiigjjiigggjigwennjig MMMMMMMM
K 0
)},(),,(),,(),,({),(1),(~
M-Operator-Blob
6_Informationsgewinnung_BildSeq Seite 28
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsEntfernung von Rauschen und BeleuchtungsinhomogenitätenBandpass-Filterung
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
BandpassBetragsquadrat
6_Informationsgewinnung_BildSeq Seite 29
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsAnwendung Monotonie-Operator auf bandpass-gefiltertes Bild
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Monotonie-Operator
6_Informationsgewinnung_BildSeq Seite 30
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsMerkmale der Monotonie-Operator-Blobs: Hauptachsen
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Hauptachsen-Berechnung
6_Informationsgewinnung_BildSeq Seite 31
Bildfolgen: BewegungsschätzungVerfolgung von Merkmalen
2. Verfolgung von Monotonie-Operator-BlobsVerfolgung der Blobs anhand der Merkmale
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
t1: bandpass-gefiltert
t2: bandpass-gefiltert
t1: Blob-Hauptachsen
t2: Blob-Hauptachsen
6_Informationsgewinnung_BildSeq Seite 32
Bildfolgen: BewegungsschätzungOptischer Fluss
Grundsätzliche Annahme:
Pixel zur Zeit t+T einer Bildsequenz wird modelliert als Pixel zur Zeit t, verschoben um einen Vektor (x, y)T: 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
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
)),,(),,((),,( tyxyyyxxxFttyxF
6_Informationsgewinnung_BildSeq Seite 33
Bildfolgen: BewegungsschätzungOptischer Fluss
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.
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
),(),(),(),(),( yxy
Fyxyyx
x
Fyxxyx
t
F
x
g
t t+t
x
gg(x0,t)
g(x0,t+t)
x0
dx
dgxmxg
6_Informationsgewinnung_BildSeq Seite 34
Bildfolgen: BewegungsschätzungOptischer Fluss
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
ty
tx
y
x
yyx
yxx
yxRyxtyx
tyyxx
yyxxt
FF
FF
FFF
FFF
yxyxRFFF
yx
FFF
FFF
yxy
Fyxyyx
x
Fyxxyx
t
F
@@
,v
vv,WmitvW
:ergibtsetzenNullvundvnachEvonAbleitung
).,(umRegion:),(mitvvE
sFehlertermdesgMinimierundurch),(Punktanv
vvvonBestimmung
0vvequationconstraintflowoptical
vvbweiseKurzschreiinoder
),(),(),(),(),(
2
2
yx
0000),(),(
2yx
y
x
00
6_Informationsgewinnung_BildSeq Seite 35
Bildfolgen: BewegungsschätzungOptischer Fluss
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
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
1112
2
22
1
11
221121
2121
2
2
@
@
@@
@
@@
W
W
WW
v
FF
FF
FFF
FFF
T
TT
ty
tx
y
x
yyx
yxx
6_Informationsgewinnung_BildSeq Seite 36
Bildfolgen: BewegungsschätzungOptischer Fluss
Berechnungsvorschrift
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
),(),(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
6_Informationsgewinnung_BildSeq Seite 37
Bildfolgen: BewegungsschätzungOptischer Fluss
Behandlung der Beschränkung des Algorithmus auf x und y kleiner ein Pixel:
Erzeugung einer Gauss´schen Auflösungspyramide:
Flussschätzung beginnend in kleinster Auflösung FlussvektorfeldWarping mit FlussvektorfeldFlussschätzung mit gewarptem Bild in nächster Auflösung, Addition zum
alten Flussvektorfeld
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Tiefpass-Filterung ¼ fmax
2-fache Unterabtastung
Tiefpass-Filterung ¼ fmax
2-fache Unterabtastung
Tiefpass-Filterung ¼ fmax
2-fache Unterabtastung
6_Informationsgewinnung_BildSeq Seite 38
Bildfolgen: BewegungsschätzungOptischer Fluss
Weitere Methoden:Horn und Schunck:
Kombination von „optical flow constraint“ (wie bisher) und Randbedingung „globale Glattheit“ (zusätzlicher Regularisierungsterm)
Minimierung von modifizierter Kostenfunktion:
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
).,(über vund veMittelwert als v und vmit
vvvv
vvvv
:Schema iterativesergibt setzenNullvundvnachEvonAbleitung
.meter erungsparaRegularisi und),(umRegion:),(mit
vvvvE
00yxyx
222
ky
kxk
y1k
y222
ky
kxk
x1k
x
yx
0000
),(),(
2222yxHS
00
yxR
FF
FFFFund
FF
FFFF
yxyxR
FFF
yx
tyxy
yx
tyxx
yxRyxyxtyx
6_Informationsgewinnung_BildSeq Seite 39
Bildfolgen: BewegungsschätzungOptischer Fluss
Weitere Methoden:Zweite-Ordnung-Methoden, z.B. Nagel
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
sFunktional des gMinimierun
:)Gradientenstarker Richtungin (nicht Glattheit"er orientiert" ungRandbeding :Nagel
0
0
),,(
),,(
v
v
),,(F),,(F
),,(F),,(F
ausn Ableitungezweiten aufberuhen
Methoden-Ordnung-Zweite
yyxy
yxxx
tyxF
tyxF
tyxtyx
tyxtyx
ty
tx
y
x
dxdyFFFFF
FFyyxyyxxxxyyyxyxyxyxxt
T 222222
2
22
vvvvvvvv2
v
6_Informationsgewinnung_BildSeq Seite 40
Bild 1 vertikaleFlusskomponente
Bild 13 horizontaleFlusskomponente
Bildfolgen: BewegungsschätzungOptischer Fluss: Beispielberechnungen
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
6_Informationsgewinnung_BildSeq Seite 41
Bildfolgen: BewegungsschätzungOptischer Fluss: Beispielberechnungen
Merkmale aus Bildfolgen: 3. Bewegungsschätzung
Statische Kamera
Kamerawackeln