I

Inhaltsverzeichnis

1  Einf uhrung  1

1.1  Einleitung  1

1.2  Erl auterung der Aufgabenstellung  2

1.3  Gliederung der Arbeit  6

2  Der Weg vom Grauwertbild zur Hypothese  7

2.1  Bewegungsdetektion aus der Bildsequenz  7

2.2  Bildbasierte Vorselektion der Hypothesen  13

3  Erfassung und Beschreibung der Bewegungsvorg ange  15

3.1  Situations ubersicht  16

3.2  Terminologie  20

3.3  Initialzustand  22

3.4  Auswahl eines Nachfolgezustands  22

3.5  Pr adiktion  23

3.5.1  Wissensbasierte Verfahren  24

3.5.2  Kalmanfilter  25

3.5.3  lineare Pr adiktion  27

3.6  Bestimmung eines adaptiven Suchraumes  28

3.6.1  Berechnung von r aus dem Pr adiktionsfehler  30

3.6.2  Berechnung von r aus der Schrittweite  31

3.7  Zusammenf uhrung und Auftrennung  32

3.8  Inaktivit at bei Instanzen  34

3.9  Z ahlung der Personen und Konzepte gegen Fehlz ahlungen  35

3.9.1  Durchtrittsrichtung  37

Inhaltsverzeichnis II

3.9.2  Pendeln von Personen  38

4  Entwurf und Implementierung  39

4.1  Terminologie  39

4.2  Sequentielle und verkettete (lineare) Listen  40

4.3  Dll-Programmierung  41

4.4  Beschreibung des Algorithmus  41

4.5  Parameter zur Anpassung  44

5  Ergebnisse und Interpretation  47

5.1  Darstellung und Pr ufung definierter Situationen  47

5.2  Test an praktischen Beispielsequenzen  51

5.3  Komplexes Beispiel uber ca. 4 Minuten Beobachtungsdauer  55

6  Zusammenfassung und Ausblick  56

A  Dateiformat (Quelldaten)  61

Literaturverzeichnis   62

Verzeichnis  von WWW-Seiten  64

Abbildungsverzeichnis   65

Tabellenverzeichnis 67   

1

Kapitel 1

Einf ¨ uhrung

1.1 Einleitung

Dank der großen Fortschritte im Bereich der Computerhardware in den letzten Jahren stehen heute preisg¨ unstige Rechner mit vor einigen Jahren noch unvorstellbarer Kapazit¨ at sowohl in Bezug auf Rechenleistung als auch Speicherkapazit¨ aten bereit. Letztlich sind es diese Fortschritte, welche zu immer neuen Anwendungen so auch im Bereich der Bildverarbeitung f¨ uhren. Das Erfassen und Verfolgen von Personen zumindest in Echtzeit, ist nicht ohne leistungsf¨ ahige Rechentechnik m¨ oglich, wenngleich die in dieser Arbeit be-handelte Aufgabe lediglich die Grundlage f¨ ur einen sp¨ ateren Echtzeiteinsatz darstellt. So stellt vor allem die inhaltliche Deutung von Bildern sehr hohe Anspr¨ uche an die Rechenleistung.

Eine große Anzahl an interessanten und sinnvollen Anwendungsm¨ oglichkeiten liefert die Motivation f¨ ur solche Systeme. So wurden und werden Systeme zur Objektverfolgung sehr viel in milit¨ arischen Anwendungen verwendet. Jedoch auch in der zivilen Welt sind eine große Anzahl von Anwendungsm¨ oglichkeiten zu finden. So wird in der Verhaltensforschung der Einsatz solcher Systeme sehr begr¨ ußt, da hier eine große Arbeitserleichterung zu erreichen ist, indem Aufgaben wie Beobachtung von Bewegungen auto-

Einf¨ uhrung 2

matisiert und objektiviert werden k¨ onnen. Hierzu sind in [ct200023] einige Ausf¨ uhrungen zu finden.

Ein weiterer Anwendungsfall ist die Z¨ ahlung von Personen. Dieser Anwendungsfall findet sich in vielen Bereichen des t¨ aglichen Lebens. So besteht großes Interesse daran, Personen zu z¨ ahlen und deren Wege zu erfassen, in den Konsumbereichen, wie Kaufh¨ ausern und Superm¨ arkten.

Auch eine Anwendung im Bereich des ¨ offentlichen Nahverkehrs ist sinnvoll. So k¨ onnten Personenstr¨ ome auf Bahnh¨ ofen und deren Zu- und Abstrom automatisiert erfasst werden. Hierdurch k¨ onnten pr¨ azise Statistiken ¨ uber das

Verkehrsaufkommen erstellt werden, wodurch sicherlich eine Optimierung der Wartezeit der Passagiere und der notwendigen Einsatzh¨ aufigkeit (Taktung) des Transportmittels erreicht werden k¨ onnte. Die dazu n¨ otige Infrastruktur, das sind insbesondere entsprechend positionierte Kameras, ist heute bereits aus sicherheitsrelevanten Erw¨ agungen oft vorhanden. Somit ist die Umstellung beziehungsweise Aufwertung vorhandener ¨ Uberwachungssysteme sicherlich nur eine Frage der Zeit, das heißt wann solche Systeme marktreif verf¨ ugbar sind und weniger eine Frage der Kosten, da entsprechende Infrastruktur bereits vorhanden ist.

Vielleicht wird es in Zukunft auch Systeme in Verbindung mit Gesichtserkennung geben, so dass einzelne Pers¨ onlichkeiten differenziert werden k¨ onnen. Mit diesem Schritt w¨ urde die Vision des ¨ Uberwachungsstaates von George Orwell ¹ , die 1949 in dem Roman ”

bekannten Ausspruch ” sicherlich wesentlich realer werden. 1.2 Erl¨ auterung der Aufgabenstellung

Ziel dieser Arbeit ist die Z¨ ahlung von Personenbewegungen bezogen auf das Durchschreiten von ” Z¨ ahlschranken“ wie zum Beispiel das Betreten oder Verlassen eines definierten Szenenbereiches.

¹ George Orwell,englischer Schriftsteller.

Einf¨ uhrung 3

Diese Arbeit entstand als Diplomarbeit im Rahmen eines Projektes in der Gesellschaft zur F¨ orderung angewandter Informatik e. V. (GFaI). ” Die

GFaI wurde am 01.06.1990 in Berlin gegr¨ undet und verfolgt gemeinn¨ utzige forschungsf¨ ordernde Zwecke. Mit ihren ca. 70 Mitarbeitern ist sie vor allem in den Bereichen Bildverarbeitung und Multimedia t¨ atig. Die GFaI ist Mitglied der Arbeitsgemeinschaft industrieller Forschungsvereinigungen e. V. (AiF) und An-Institut der Technischen Fachhochschule Berlin (TFH) und der Fachhochschule f¨ ur Technik und Wirtschaft Berlin (FHTW).“ [GFaI]

Ausgangsbasis f¨ ur das Bildmaterial ist eine Beobachtungssituation, bei uber der zu betrachtenden Szene ² befindet. welcher sich die Kamera senkrecht ¨

Wie in Abbildung 1.1 dargestellt, betr¨ agt der vertikale Abstand zwischen Kamera und Boden zwischen 3 und 5 m und der Bildausschnitt bezogen auf den Fußboden ist ca. 4 m * 5 m.

Das Bildmaterial liegt zur Zeit als Folge von Grauwert-Einzelbildern vor. Die Beobachtungssituation stellt sich sehr flexibel dar, da Szenen sowohl im Innenbereich als auch im Außenbereich verarbeitet werden sollen. St¨ orungen sind dabei in allen Szenen zu erwarten. Im Innenbereich werden diese

² Unter dem Begriff Szene wird hier ein feststehender Bildausschnitt mit feststehender

Kamera verstanden.

Einf¨ uhrung 4

zum Beispiel durch mitgef¨ uhrte Einkaufswagen oder bewegte Europaletten hervorgerufen.

Ein Beispiel f¨ ur eine Szene im Innenbereich, dargestellt im oberen Teil von Abbildung 1.2, befindet sich in einem Einkaufszentrum. Im Außenbereich sind St¨ orungen durch wechselnde Wetterverh¨ altnisse sowie durch hochgradig unterschiedliche Beleuchtungsverh¨ altnisse (nat¨ urlichen und k¨ unstlichen Ursprungs) zu erwarten.

Die Aufgabe, sich bewegende Personen in Videosequenzen zu verfolgen, ist gepr¨ agt von den Erscheinungsbildern der Personen, wie sie sich in der Szene ergeben. Diese Personen stellen sich innerhalb dieser Bilder als nicht-rigide ³ Objekte dar. Das Erkennen von Personen in Einzelbildern beziehungsweise in einer Sequenz von aufeinanderfolgenden Bildern wird hier durch das in Kapitel 2.1 beschriebene Verfahren realisiert, welches nicht Gegenstand der Diplomarbeit ist, aber schon vorliegt.

Darauf aufbauend ist es Ziel der vorliegenden Arbeit, ein Trackingmodul zu schaffen. Aufgabe dieses Trackingmodules ist es, basierend auf der Erkennung von Bewegungen von Personen in aufeinanderfolgenden Bildern, deren Bewegung ¨ uber die ganze Szene in einer entsprechenden Bildfolge zu erfassen.

Das Datenmaterial welches dieser Arbeit zugrunde liegt zeigt einen Supermarkt, wie in Abbildung 1.2 oben dargestellt. Die Beobachtungssituation ist so gew¨ ahlt, dass die Kamera senkrecht ¨ uber dem zu beobachtenden

Bildausschnitt steht. Daher liegen die Ergebnisse der Beobachtung als zweidimensionale Bilder, in Form einer Draufsicht, vor.

Die gesamte Aufgabe der Personenverfolgung erfordert im Wesentlichen drei Schritte, wie in Abbildung 1.2 dargestellt.

• Im 1. Schritt werden die sensorischen Daten in Form von Grauwert-Bildern bereitgestellt.

³ Als nicht rigid werden Objekte bezeichnet, welche keine konstante Form besitzen.

Nicht-rigid kann also mit nicht-formfest umschrieben werden.

Einf¨ uhrung 5

• Der 2. Schritt umfasst die Bildverarbeitung und Bildanalyse und liefert aufbereitete Daten (Hypothesen) aus den Bildersequenzen zur Weiterverarbeitung, dem Tracking.

• Der 3. Schritt ist die Analyse durch das Trackingmodul. Hier werden die aus der Bildverarbeitung gewonnen Daten zu einer Bewegungsanalyse in der Szene verarbeitet. Dadurch lassen sich auch Z¨ ahlergebnisse f¨ ur Personenz¨ ahlungen erstellen, die letztlich Ziel dieser Arbeit sind.

Diese Funktionalit¨ at soll mittels ANSI ⁴ C in einer Dynamic Link Library (siehe dazu Kapitel 4.3) implementiert werden.

⁴ American National Standards Institute

Einf¨ uhrung 6

1.3 Gliederung der Arbeit

Das erste Kapitel soll die Aufgabenstellung erl¨ autern und m¨ ogliche Anwendungsbereiche f¨ ur dieses und ¨ ahnlich geartete Systeme aufzeigen.

In Kapitel zwei wird erl¨ autert, wie die per Kamera gewonnenen Bilder verarbeitet werden. Wie werden ¨ uberhaupt interessierende Objekte erkannt und identifiziert? Welche Daten werden aus den Bildern gewonnen?

Kapitel drei zeigt, wie die aus der Bildanalyse gewonnenen Daten verarbeitet werden, so dass die Bewegung von Personen tats¨ achlich verfolgt wird. Auch werden ” Probleme“ aufgezeigt, die es zu l¨ osen gibt, wenn ein Algorithmus nicht nur eine Person, sondern mehrere Personen gleichzeitig verfolgen soll. Hierzu werden Konzepte entwickelt und vorgestellt.

In Kapitel vier wird auf die Implementierung des Algorithmus eingegangen. Der Algorithmus wird graphisch veranschaulicht und erl¨ autert. Auch die Parameter, die der Flexibilit¨ at des Algorithmus dienen werden erl¨ autert.

Kapitel f¨ unf veranschaulicht die Funktionsf¨ ahigkeit des Algorithmus. Hierzu werden Testreihen an ” synthetischen“ Beispielen durchgef¨ uhrt. Weiterhin wird Bildmaterial aus praktischen Beispielsequenzen sowohl ¨ uber den

Algorithmus als auch visuell ausgewertet, wobei eventuell entstehende Unterschiede erl¨ autert werden.

Eine Zusammenfassung der Ergebnisse, die in Kapitel f¨ unf gewonnen wurden, wird in Kapitel sechs gegeben. Weiterhin werden m¨ ogliche Vorschl¨ age zur Verbesserung und Weiterentwicklung gemacht.

7

Kapitel 2

Der Weg vom Grauwertbild zur

Hypothese

Dieses Kapitel soll einen ¨ Uberblick ¨ uber die Verfahren geben, die zur Gewinnung von Daten aus Bildern n¨ otig sind und damit die Voraussetzung f¨ ur eine Auswertung und Analyse schaffen.

2.1 Bewegungsdetektion aus der Bildsequenz

Die Bilder beziehungsweise Bildsequenzen liegen in Videonorm vor. Die Aufl¨ osung betr¨ agt (Vollbild) 768x572 Pixel ² mit 256 Grauwerten, der Abstand zwischen zwei Bildern betr¨ agt 40ms.

Der Weg vom Grauwertbild zur Hypothese 8

Abbildung 2.1 zeigt eine typische 40ms-Sequenz von 10 Bildern mit einem zeitlichen Abstand von 40ms zwischen den Einzelbildern. In Abbildung 2.2 sind aus der gleichen Sequenz 10 Bilder mit einem zeitlichen Abstand von je 200ms dargestellt.

Die Aufgabe der Bewegungsdetektion (oder wie hier definiert das Auffinden von Hypothesen f¨ ur eine Objektbewegung) l¨ asst sich in mehrere Teilschritte gliedern, die durch Verfahren der digitalen Bildverarbeitung und Bildanalyse bestimmt werden (Abbildung 2.3).

Abbildung 2.3: Teilschritte Bildverarbeitung und Bildanalyse

So steht zu Beginn die Wahl eines geeigneten (minimalen) Zeitintervalls zwischen zwei Bildaufnahmen, bestimmt durch das Ziel der Erkennung re-

Der Weg vom Grauwertbild zur Hypothese 9

levanter Ereignisse und der auftretenden gesamten Verarbeitungszeit im System. Hier kommt das Problem der Datenmenge zum Tragen. Wird der zeitliche Abstand zwischen den zu verarbeitenden Bildern verringert, so ist mit einer h¨ oheren Leistung in Bezug auf die Erkennung von relevanten Ereignissen zu rechnen. Nachteil hierbei ist die hohe Datenmenge. Wird der Abstand zwischen zwei Bildern hingegen relativ groß gew¨ ahlt, sinkt die Erkennungsleistung. Auch die zu verarbeitende Datenmenge sinkt mit zunehmendem Bildabstand. Dieser Umstand erlaubt jedoch auch den Einsatz von leistungsschw¨ acheren Systemen. Ziel ist deshalb ein optimaler zeitlicher Abstand zwischen den Bildern. Nach [Schulz00] sind 5 Bilder/s eine ¨ ubliche Gr¨ oße bei dieser Art der Beobachtung.

Die eigentliche Aufgabe besteht in der Ermittlung der Hypothesen. Dabei wird aus dem Vergleich von Grauwertbildern (unter Anwendung zus¨ atzlicher Filter oder Methoden zur Beseitigung von Bildrauschen) der interessierende Bildinhalt ermittelt und dann ¨ uber die Segmentierung (Binarisierung) die signifikante Information (Fl¨ achenobjekte) bereitstellt. ¨ Uber eine entsprechende Analyse entstehen daraus die Hypothesen, beschrieben durch Gr¨ oße und Position. Hier finden im wesentlichen folgende Methoden zur Bewegungsdetektion in Bildsequenzen Anwendung:

• Differenzbildung zu einem Hintergrundbild (DiffHGB) 1

• Bildung der absoluten Differenz (AbsDiff) ² zwischen zwei (gem¨ aß gew¨ ahltem Zeitintervall) aufeinanderfolgenden Bildern

• Spezielle Methoden, zum Beispiel Motion Energy Method (MoEnMe) 3

In Abbildung 2.4 ist das Verfahren der Differenzbildung zu einem Hinter-grundbild (DiffHGB) dargestellt. Links oben ist ein Hintergrundbild dargestellt, rechts oben ein Bild aus der aktuellen Szene. Die Differenz aus diesen beiden Bildern ist im Bild in der linken unteren Ecke dargestellt. Nach der

¹ vgl. [Zedler01]

² vgl. [Zedler01]

³ vgl. [Tse98]

Der Weg vom Grauwertbild zur Hypothese 10

Abbildung 2.4: DiffHGB - Differenzbildung zu einem Hintergrundbild

darauf folgenden Segmentierung mit einem Schwellwert erh¨ alt man das Ergebnis, wie es rechts unten dargestellt ist. Zur Veranschaulichung ist dieses Ergebnis noch mit dem Bild rechts oben ¨ uberlagert.

Die Methode DiffHGB liefert die eindeutigsten Bilder bez¨ uglich Objektlage und Objektform, ist aber in den vorliegenden realen Szenen schwierig in der Realisierung.

Ein Hintergrundbild ⁴ ist nicht immer ermittelbar und zweitens ist das Hintergrundbild nicht station¨ ar, das heißt es sind Aktualisierungen notwendig in bestimmten Zeitabschnitten beziehungsweise in Abh¨ angigkeit von l¨ anger wirkenden St¨ orungen, die dann auch erst als solche detektiert werden m¨ ussen. Eine Variante dieser Methode bedient sich einer fortlaufenden adaptiven Anpassung des Hintergrundbildes durch ” Berechnung eines Hintergrundbil-

des“ aus der laufenden Sequenz. Dazu existieren unterschiedliche Methoden, die sich im Aufwand der Berechnung, dem Bedarf an Speicher und ihrer Anpaßgeschwindigkeit zu Bildver¨ anderungen unterscheiden.

In Abbildung 2.5 ist das Verfahren der Bildung der absoluten Differenz

⁴ Unter einem Hintergrundbild ist die leere Szene zu verstehen. D.h. sich bewegende

Objekte wie zum Beispiel Personen sind darin nicht enthalten.

Der Weg vom Grauwertbild zur Hypothese 11

Abbildung 2.5: AbsDiff - Bildung der absoluten Differenz

(AbsDiff) dargestellt. Links und rechts oben befinden sich zwei Bilder, die zu unterschiedlichen Zeitpunkten entstanden sind. Zwischen diese beiden Bildern wird die absolute Differenz gebildet, wobei das Ergebnis entsteht, wie es unten links abgebildet ist. Das Ergebnis wird binarisiert und darauf ein Sobel-Filter ⁵ angewandt, wobei das Ergebnis entsteht, das unten rechts dargestellt ist. Zur Veranschaulichung wurde eine ¨ Uberlagerung mit einem Bild der Szene vorgenommen.

Die Methode AbsDiff liefert bez¨ uglich Objektlage und Objektform keine eindeutigen Informationen ¨ uber die Bewegung im Bild, insbesondere dann, wenn sich ein Objekt nicht ¨ uber seine vorherige r¨ aumliche Ausdehnung hinaus bewegt hat.

Die Funktionsweise der Motion Energy Method (MoEnMe) ist in Abbildung 2.6 dargestellt.

Die Motion Energy Method benutzt auch die absolute Differenz zwischen zwei Bildern. Dies sind die beiden oberen Bilder. Dann erfolgt aber eine

⁵ Der Sobel-Filter geh¨ ort zur Klasse der sogenannten Kantendetektionsfilter beziehungs-

weise Kantenextraktionsfilter. Zweck der Anwendung ist die Erlangung eines Kantenbildes,

d.h. der Umriss eines Objektes wird dargestellt.