Inhaltsverzeichnis

  Einf uhrung  1

1  Grundlagen  3

1.1  Likelihood-Wahrscheinlichkeit  3

1.2  Integration uber Zeit und Raum  5

2  Einsparung von Berechnungszeit  14

2.1  Reduktion des Geschwindigkeitsraumes  14

2.1.1  1D-Geschwindigkeitsraum  14

2.1.2  2D-Geschwindigkeitsraum  16

2.2  Zweistufiges System  19

3  Objekterkennung  22

3.1  Segmentierung  22

3.2  Objektzuweisung  26

3.3  Clustern  30

4  Anwendung  34

5  Programmierung und Benutzeroberfl ache  36

6  Ergebnisse  38

6.1  Einstufiges System  38

6.2  Einstufiges System mit reduziertem Geschwindigkeitsraum 1D  40

6.3  Einstufiges System mit reduziertem Geschwindigkeitsraum 2D  41

6.4  Zweistufiges System  42

6.5  Zusammenfassung  43

  Ausblick  44

  Literaturverzeichnis  45

I

  Abbildungsverzeichnis  

1  Zeitliche Propagation der Wahrscheinlichkeitsverteilung  6

2  Funktionsprinzip der zeitlichen Propagation  7

3  Beispiel f ur unterschiedliche Gewichtungsfenster  8

4  Funktionsprinzip der zeitlichen Propagation mit Einbezug von  

  Nachbarverteilungen  9

  Beispiel f ur eine Geschwindigkeitsverteilung ρ t (v x)  10

   5

  Schweifreduktion durch verschiedene Integrationsfenster ˆ  

W   x

6  v  11

7  Bildaufnahme in gleichen Abst anden  12

8  Bildaufnahme direkt hintereinander  13

9  Vertikaler oder horizontaler Suchraum  15

10  Eindimensionale Geschwindigkeitsverteilung  16

11  Horizontaler und vertikaler Suchraum gemeinsam  17

12  Schema Ermittlung der Verteilungen f ur schr age Geschwindigkeiten  18

13  Verteilungen f ur reduzierten 2D-Geschwindigkeitsraum  19

14  System mit zwei Aufl osungsstufen, Wahrscheinlichkeitsverteilungen  21

15  Schwellwertbildung der Wahrscheinlichkeitsverteilung  23

16  Verteilung und Segmentierungsfunktion  24

17  Gesamtsystem  25

18  Die Summationsfunktionen  26

19  Kombination der Maximum-Koordinaten  28

20  Integration in der Umgebung der Kombinationskoordinaten  30

21  Clustern der Objektkoordinaten  33

22  Z ahlmaske mit Z ahlbereich f ur Objektz ahlung  35

23  Grafische Benutzeroberfl ache und Visualisierung der Ergebnisse  37

24  Ergebnisse Einstufiges System  39

25  Ergebnisse Einstufiges System mit 1D-Geschwindigkeitsraum  40

26  Ergebnisse Einstufiges System mit 2D-Geschwindigkeitsraum  41

27  Ergebnisse Zweistufiges System  42

II

Einf¨ uhrung

Heutzutage wird in vielen Sicherheits- und Servicebereichen Videoberwachung eingesetzt, um Gefahrensituationen erkennen und Informationen gewinnen zu k¨ onnen. Immer ¨ ofter kommt es dabei zum Einsatz von Videokameras und Webcams, deren Qualit¨ at st¨ andig steigt und deren Preis-Leistungsverh¨ altnis sich ebenfalls zunehmend verbessert. Die Verarbeitungskette der Bilddaten ist aber im Allgemeinen nicht ¨ uberm¨ aßig lang und endet meist schon mit der einfachen Bildanzeige in ¨ Uberwachungsmonitoren oder mit der Speicherung der Bilddaten auf Datentr¨ agern zwecks Archivierung. Eine Auswertung und Bewertung dieser Bildinformationen erfordert immer noch in den h¨ aufigsten F¨ allen das Urteils-und Entscheidungsverm¨ ogen eines Menschen und ist im Regelfall noch nicht selbst¨ andig von einem automatisierten System durchf¨ uhrbar. Existierende Auswertungssoftware ist zum ¨ uberwiegenden Teil auf bestimmte definierte Umgebungen oder Objekte spezialisiert und daher auf nur wenige Einsatzm¨ oglichkeiten beschr¨ ankt. Treten hier beispielsweise Szenerie¨ anderungen, Wetter- oder Beleuchtungsschwankungen auf, so kommt es h¨ aufig zu Fehlverhalten und damit zur Beschneidung der Sicherheitsgew¨ ahrleistung. Gerade in Sicherheitssystemen ist jedoch die Zuverl¨ assigkeit von absolut zentraler Bedeutung. In dieser Arbeit wird der Versuch unternommen, ein solches System zu entwerfen, welches unabh¨ angig von den genannten Einflussfaktoren ist und das eigenst¨ andig und ohne menschliche ¨ Uberwachung arbeitet. Das hier vorgestellte System soll dazu dienen, in Echtzeit mehrere bewegte Objekte innerhalb einer Bildfolge zu erkennen und diese auch zu verfolgen. In herk¨ ommlichen Anwendungen werden Bewegungssch¨ atzungen von bewegten Objekten im Allgemeinen durch Geschwindigkeitsvektoren repr¨ asentiert, die jedem Bildpunkt eine bestimmte Geschwindigkeit zuordnen. Diese Darstellungsweise ist jedoch f¨ ur eine eindeutige Beschreibung von Bewegungen nicht ausreichend und kann daher zu gr¨ oßeren Fehlern bei der Sch¨ atzung f¨ uhren. Eine L¨ osung hierf¨ ur stellt der Einsatz von bestehenden Sch¨ atzverfahren dar, welche auf einer Beschreibung der Geschwindigkeiten jedes Bildpunktes durch Wahrscheinlichkeitsverteilungen beruhen. Hierbei werden die Geschwindigkeiten von Bildbereichen innerhalb eines Bildes als statistisches Signal aufgefasst, so dass bestimmte Bildmerkmale mit einer Wahrscheinlichkeit beschrieben werden k¨ onnen. Auf dieser Grundlage wird dann ein Verfahren entworfen, welches zur Erkennung von bewegten Objekten dient. Dabei werden Wahrscheinlichkeitsverteilungen dazu benutzt, um Bereiche innerhalb eines Bildes zu bestimmen, die sich homogen mit der gleichen Geschwindigkeit bewegen. Diese Bereiche k¨ onnen dann gezielt untersucht und bewegten Objekten zugeord-

1

net werden.

Im Kapitel 1 werden zun¨ achst die Grundlagen f¨ ur die Beschreibung von Bildbewegungen mit Wahrscheinlichkeiten vorgestellt. Es folgt dann in Kapitel 2 die effiziente Umsetzung des vorgestellten Modells, bevor in Kapitel 3 auf das eigentliche Ziel dieser Arbeit, die Objektverfolgung, eingegangen wird. Kapitel 4 zeigt, wie sich aus dem vorgestellten Verfahren eine einfache Anwendung realisieren l¨ asst. In Kapitel 5 wird die programmtechnische Umsetzung der Algorithmen zusammengefasst und das letzte Kapitel 6 zeigt Ergebnisse des entworfenen Systems.

2

1 Grundlagen

1.1 Likelihood-Wahrscheinlichkeit

Zun¨ achst werden hier die Notationen vorgestellt, die im weiteren f¨ ur die mathematische Beschreibung des Systemmodells verwendet werden.

Jedes Bild I ^t einer Bildsequenz zum Zeitpunkt t besteht aus Pixeln an den Orten x. Jedem Pixel werden Eigenschaften wie z.B. Grauwert G t schwindigkeitsvektor v ^t x zugeordnet. F¨ ur das gesamte Bild I ^t ist dann G ^t

die Matrix aller Grauwerte. Um Informationen ¨ gungsflusses in einer Bildsequenz zu erhalten, werden gew¨ ohnlich Bereiche von zwei aufeinanderfolgenden Bildern I ^t und I ^t+∆t miteinander verglichen. Ein solcher Bereich eines Bildes I ^t wird mit WG ^t,x definiert, wobei G ^t,x alle Grauwerte des Bildes I ^t sind, die um den Wert x verschoben wurden. Die Matrix W ist ein r¨ aumliches 2D-Fenster, welches die Gr¨ oße des Bildbereiches festlegt und eine Gewichtung (z.B. Gauss-Fenster) enthalten kann. Die Zeitdifferenz ∆t zwischen zwei aufeinanderfolgenden Bildern wird hier als eine Funktion der Zeit t selbst angesetzt. Sie ist also nicht konstant und kann sich mit der Zeit ¨ andern. Dies ist von Vorteil, wenn man bedenkt, daß die nachfolgenden Algorithmen auf einem Rechner implementiert und ausgef¨ uhrt werden sollen. Denkbar w¨ are, daß parallel noch andere Programme bearbeitet werden und somit die notwendigen Ressourcen nicht kontinuierlich f¨ ur die hiesigen Algorithmen verf¨ ugbar sind. Daher kann es zu Verz¨ ogerungen bei der Bildaufnahme oder der Berechnung selbst kommen. Die Zeitdifferenz zwischen zwei Bildern ist also

Die Vorgehensweise f¨ ur die Sch¨ atzung der im Bild enthaltenen Geschwindigkeiten soll im folgenden erkl¨ art werden. Es wird zun¨ achst angenommen, daß sich alle Grauwerte innerhalb des Bildbereiches um den Punkt x f¨ ur eine gewisse Zeit ∆t mit gemeinsamer Geschwindigkeit v ^t x bewegen. Dies bedeutet, daß sich der

gesamte Bildbereich WG ^t,x des Bildes I ^t gleichf¨ ormig mit der Geschwindigkeit

3

1 GRUNDLAGEN

v ^t x = ∆x/∆t bewegt und nach der Zeit ∆t im Bild I ^t+∆t wieder an der Position x + ∆x erscheint . Es gilt somit

WG ^{t+∆t,x+∆x} = WG ^t,x . (2)

Zus¨ atzlich wird angenommen, daß den Grauwerten ein Rauschen ¨ uberlagert ist

und daß Helligkeits- und Kontrastschwankungen im Bild auftreten. Bezeichnet man das Rauschen mit dem Faktor η, die Helligkeits- und Kontrastschwankungen mit Offset κ bzw. dem Skalierungsfaktor λ, so l¨ asst sich der Zusammenhang zwischen zwei Bildbereichen schreiben als

Wird das Rauschen modelliert als mittelewertfreies Gaußsches Rauschen mit der Varianz σ η , so l¨ asst sich die Wahrscheinlichkeit, daß zwei Bereiche WG ^{t+∆t,x+∆x} und WG ^t,x zusammenpassen, ausdr¨ ucken als

² ||W(λ G ^t,x +κ 1−G ^{t+∆t,x+∆x} )|| − 1

^{2σ 2} = ¹ e . (4) √ η

ση 2π

Die Einfl¨ usse der Helligkeits- und Kontrastschwankungen lassen sich hierin minimieren und man erh¨ alt dann als Ergebnis die von den Parametern λ und κ unabh¨ angige Wahrscheinlichkeit

2 ^σ G ^{t,x 1− 2} − 1 2 ^· = ¹ (5) ^ση G ^{t,x ,G t+∆t,x+v·∆t} e . √

ση 2π

Zur Vereinfachung wurde G ^t,x und G ^{t+∆t,x+∆x} durch x ersetzt und σ η sowie W weggelassen. Der Korrelationskoeffizient ² G ^t,x ,G t+∆t,x+v·∆t berechnet sich wie folgt zu

^{1 1} µ X = X := und (7)

1 ^T W 2

1

− X ² σ ² X = X ² (8)

Der Ausdruck ρ ^t (x|v) beschreibt die Wahrscheinlichkeit, daß sich Bildpunkte zum Zeitpunkt t mit der Geschwindigkeit v zum Ort x bewegt haben. Er wird im weiteren als Likelihood-Messung bezeichnet.

4

1 GRUNDLAGEN

1.2 Integration ¨ uber Zeit und Raum

Um aus der vorgestellten Messung ρ ^t (x|v) eine Wahrscheinlichkeit ρ ^t (v|x) f¨ ur die Geschwindigkeiten zu bekommen, wird die Bayessche Inferenz angewendet. ρ ^t (v|x) ist die Wahrscheinlichkeit, daß sich die Bilddaten an dem Ort x mit der Geschwindigkeit v durch das Bild bewegen. Durch das Bayessche Theorem wird die Likelihood-Messung verkn¨ upft mit einer A-Priori-Wahrscheinlichkeit ρ(v) zu der A-Posteriori-Wahrscheinlichkeit

Hierbei ist ρ(v) eine Geschwindigkeitsverteilung f¨ ur das gesamte Bild, die an keinerlei Bedingungen hinsichtlich Bilddaten gebunden ist. Wird nun eine ganze Folge von Bildern untersucht und liegen Sch¨ atzungen von vergangenen Zeitpunkten vor, so k¨ onnen diese Sch¨ atzungen dazu verwendet werden, um den A-Priori-Sch¨ atzwert anzun¨ ahern und zu aktualisieren. Dies f¨ uhrt zur modifizierten Sch¨ atzgleichung f¨ ur den A-Posteriori-Wert

ρ ^t Die angen¨ aherte A-Priori-Wahrscheinlichkeit ˆ x (v) ist abh¨ angig von der Zeit

t und vom Ort x. Sie ist eine Pr¨ adiktion der Geschwindigkeitsverteilung aufgrund von Wahrscheinlichkeitsdichten ρ ^t−∆t (v|x) vorheriger Zeitpunkte. Es sind also zwei Operationen notwendig, um den A-Posteriori-Wert zu berechnen. Zuerst muss der A-Priori-Wert pr¨ adiziert werden und danach muss die Aktualisierung des A-Posteriori-Wertes erfolgen. Die Aktualisierung verkn¨ upft die aktuelle Likelihood-Messung mit dem aktuellen pr¨ adizierten A-Priori-Wahrscheinlichkeitswert ρ ^t ˆ x (v), siehe Abbildung 1.

5

1 GRUNDLAGEN

Bild 1: Zeitliche Propagation: Die A-Posteriori-Wahrscheinlichkeit ρ ^t (v|x) wird aktualisiert mit Hilfe der aktuellen Likelihood-Messung ρ ^t (x|v) und der aktuellen pr¨ adizierten ρ ^t A-Priori-Wahrscheinlichkeit ˆ x (v)

Die Pr¨ adiktion dieses Wahrscheinlichkeitswertes verwendet die A-Posteriori-Wahrscheinlichkeit ρ ^t−∆t (v|x) des vorherigen Zeitschrittes und kann auf zwei Arten erfolgen:

• Unter der Annahme, daß sich die Bildbereiche aus der Likelihood - Messung statistisch unabh¨ angig voneinander bewegen, lautet die Pr¨ adiktionsgleichung f¨ ur unkorrelierte Bildbereiche

Diese Berechnung wird f¨ ur alle Pixel und f¨ ur jede untersuchte Geschwindigkeit v durchgef¨ uhrt und erfordert anschliessend eine Normierung ¨ uber

alle Geschwindigkeiten, damit die Summe aller pr¨ adizierten, zu einem Pixel

x geh¨ origen A-Priori-Wahrscheinlichkeiten Eins ergibt Abbildung 2 ist das Berechnungsschema dargestellt.

6

1 GRUNDLAGEN

Bild 2: Funktionsprinzip der zeitlichen Propagation der Geschwindigkeitsverteilungen verdeutlicht an enem eindimensionalen Beispiel. In a) ist ein Ausschnitt der Grauwerte des

Bildes G ^t−∆t mit den Pixeln x 5 bis x 9 zu sehen. Unter b) sind die zugeh¨ origen gesch¨ atzten x

Geschwindigkeitsverteilungen zum Zeitpunkt t − ∆t gezeigt. Um eine Pr¨ adiktion der Geschwindigkeitsverteilungen zum Zeitpunkt t zu erhalten, werden diese Verteilungen mit- ρ ^t (v|x 7 ) Verkn¨ upfung ist beispielhaft einander verkn¨ upft. Das Pr¨ adiktionsergebnis ˆ f¨ ur den Pixel x 7 in c) gezeigt.

• Geht man davon aus, daß ein gewisser statistischer Zusammenhang zwischen den Bewegungen der Bilbereiche besteht, so ist es sinnvoll, auch die Wahrscheinlicheitswerte in einer Umgebung x eines Pixels x zu ber¨ ucksichtigen. Die Beitr¨ age der einzelnen Wahrscheinlichkeiten k¨ onnen gewichtet werden mit einem Fenster ˆ wie weit sie sich ¨ uberlappen. Desweiteren ist dieses Fenster variabel f¨ ur verschiedene untersuchte Geschwindigkeiten v. Dies bietet die M¨ oglichkeit, daß man beispielsweise jene Wahrscheinlichkeitswerte st¨ arker gewichten kann, die sich im Bezug auf eine Position x in Richtung der Geschwindigkeit v befinden. Dies hat den Vorteil, daß sich damit hinter bewegten Objekten eine schweifartige Ausbildung der Wahrscheinlichkeiten ρ ^t (v|x) beeinflussen und reduzieren l¨ asst. Dies f¨ uhrt zur Pr¨ adiktionsgleichung f¨ ur korrelierte Bildbereiche

In der Implementierung wurden f¨ ur die Fenster Gaussfunktionen verwendet,

7