Die Datenbestände lokaler Fernsehsender umfassen oftmals mehrere zehntausend Videokassetten. Moderne Verfahren werden benötigt, um derartige Datenkollektionen inhaltlich automatisiert zu erschließen. Das Auffinden relevanter Objekte spielt dabei eine übergeordnete Rolle, wobei gesteigerte Anforderungen wie niedrige Fehler- und hohe Detektionsraten notwendig sind, um eine Korruption des Suchindex zu verhindern und erfolgreiche Recherchen zu ermöglichen. Zugleich müssen genügend Objekte indiziert werden, um Aussagen über den tatsächlichen Inhalt zu treffen. Diese Arbeit befasst sich mit der Anpassung und Optimierung bestehender Detektionsverfahren. Dazu wird ein auf die hohen Leistungsbedürfnisse der Videoanalyse zugeschnittenes holistisches Workflow- und Prozesssystem mit der Zielstellung implementiert, die Entwicklung von Bilderkennungsalgorithmen, die Visualisierung von Zwischenschritten sowie deren Evaluation zu ermöglichen. Im Fokus stehen Verfahren zur strukturellen Zerlegung von Videomaterialien und zur inhaltlichen Analyse im Bereich der Gesichtsdetektion und Fußgängererkennung.:1. Motivation . . . 1 1.1. Einordnung in den Retrievalprozess . . . . . . . . . . . . . . . . . . . 2 1.2. Infrastruktur zur Optimierung von Verfahren zur Videoanalyse . . . . 4 1.3. Herausforderungen der Bilderkennung . . . . . . . . . . . . . . . . . . 6 1.4. Wissenschaftliche Ergebnisse dieser Arbeit . . . . . . . . . . . . . . . 9 1.5. Kapitelübersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2. Methoden und Strategien der Videoanalyse . . . 15 2.1. Fachgebiete der Bilderkennung . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1. Maschinelles Lernen . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.2. Maschinelles Sehen . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.3. Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.4. Mustererkennung . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2. Strukturelle Analyse von generischen Mustererkennungsystemen . . . 22 2.2.1. Datenakquisition . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2. Musteranalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.3. Musterklassifizierung . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.4. Bilderkennungssysteme . . . . . . . . . . . . . . . . . . . . . . 28 2.2.5. Wissensentdeckung in Datenbanken . . . . . . . . . . . . . . . 28 2.3. Bilderkennung in der inhaltsbasierten Bildsuche . . . . . . . . . . . . 29 2.3.1. Paradigmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.2. Bildsignaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.3. Signaturtypen . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.4. Lerntechniken . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4. Holistische Bilderkennungssysteme im Überblick . . . . . . . . . . . . 44 2.4.1. Ein segment- und konturbasiertes CBIR-System . . . . . . . . 45 2.4.2. Biologisch inspirierte Systeme . . . . . . . . . . . . . . . . . . 48 2.4.3. Lernen aus wenigen Beispielen . . . . . . . . . . . . . . . . . . 51 2.5. Objekterkennung im Szenenkontext . . . . . . . . . . . . . . . . . . . 55 2.6. Aktuelle Grenzen der Muster- und Objekterkennung . . . . . . . . . . 60 2.7. Konzept eines generischen Workflows zur Objekterkennung in Videos . . . 64 2.7.1. Strukturelle Analyse . . . . . . . . . . . . . . . . . . . . . . . 64 2.7.2. Inhaltliche Analyse . . . . . . . . . . . . . . . . . . . . . . . . 66 2.7.3. Erweiterung des klassischen Paradigmas zur Objekterkennung . . . 67 2.7.4. Anwendungsdomänen . . . . . . . . . . . . . . . . . . . . . . . 68 2.8. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3. Systemarchitektur zur Optimierung von Bilderkennungsverfahren . . . 71 3.1. Vorüberlegungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.1.1. Softwaretechnische Anforderungen . . . . . . . . . . . . . . . . 72 3.1.2. Bewertung der Systemleistung . . . . . . . . . . . . . . . . . . 75 3.1.3. Ein- und Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.1.4. Modellierung von Domänenwissen . . . . . . . . . . . . . . . . 90 3.1.5. Diskriminierbarkeit von Merkmalen . . . . . . . . . . . . . . . 92 3.1.6. Zusammenfassende Darstellung . . . . . . . . . . . . . . . . . 95 3.2. Architektur des Gesamtsystems . . . . . . . . . . . . . . . . . . . . . 95 3.3. Struktureller Aufbau von AMOPA . . . . . . . . . . . . . . . . . . . 97 3.3.1. Verwendung von Prozessketten . . . . . . . . . . . . . . . . . 101 3.3.2. Bild- und Videoverarbeitung . . . . . . . . . . . . . . . . . . . 106 3.4. Annotation von Bildern und Videos . . . . . . . . . . . . . . . . . . . 107 3.4.1. Ein Annotationswerkzeug für Videos . . . . . . . . . . . . . . 108 3.4.2. Ein Ansatz zu Annotation, Klassifikation und Evaluation . . . 111 3.5. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4. Videosegmentierung . . . 119 4.1. Schnitterkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.1.1. Struktureller Aufbau von Videos . . . . . . . . . . . . . . . . 121 4.1.2. Klassische Verfahren . . . . . . . . . . . . . . . . . . . . . . . 124 4.1.3. TRECVid: Evaluationskampagne und Datensätze . . . . . . . 125 4.1.4. Das Verfahren von AT&T . . . . . . . . . . . . . . . . . . . . 130 4.2. Schnittkomposition und Ähnlichkeit . . . . . . . . . . . . . . . . . . . 137 4.2.1. Dominant-Color-Deskriptor . . . . . . . . . . . . . . . . . . . 140 4.2.2. Color-Layout-Deskriptor . . . . . . . . . . . . . . . . . . . . . 140 4.2.3. Scalable-Color-Deskriptor . . . . . . . . . . . . . . . . . . . . 141 4.2.4. Edge-Histogram-Deskriptor . . . . . . . . . . . . . . . . . . . 142 4.3. Konzeption und Implementierung . . . . . . . . . . . . . . . . . . . . 143 4.3.1. Einbindung in das Prozesskonzept von AMOPA . . . . . . . . 144 4.3.2. Auswahl des Farbraums . . . . . . . . . . . . . . . . . . . . . 148 4.3.3. Bewegungsanalyse . . . . . . . . . . . . . . . . . . . . . . . . 151 4.3.4. Bestimmung und Verifikation von Schnittkandidaten . . . . . 159 4.3.5. Ergebnisdarstellung und -speicherung . . . . . . . . . . . . . . 171 4.4. Evaluation und Optimierung der harten Schnitterkennung . . . . . . 173 4.4.1. Die TRECVid Evaluationsmethodologie . . . . . . . . . . . . 174 4.4.2. Optimierung von Recall und Laufzeit . . . . . . . . . . . . . . 176 4.4.3. Optimierung der Precision . . . . . . . . . . . . . . . . . . . . 181 4.4.4. Validierung der Ergebnisse . . . . . . . . . . . . . . . . . . . . 183 4.5. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 5. Gesichtsdetektion . . . 187 5.1. Stand der Technik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.1.1. Verfahrensklassen und Datensätze . . . . . . . . . . . . . . . . 189 5.1.2. Boosting-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 192 5.2. Realisierung eines Systems zur Musterklassifizierung . . . . . . . . . . 200 5.2.1. Trainingsphase . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5.2.2. Klassifikation mit Hilfe von Detektorketten . . . . . . . . . . . 203 5.2.3. Erlernen eines geboosteten Gesichtsklassifikators . . . . . . . . 206 5.2.4. Exkurs: Gesichtslokalisation mittels Schwarmintelligenz . . . . 210 5.3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 5.3.1. Datensatz TS100 . . . . . . . . . . . . . . . . . . . . . . . . . 214 5.3.2. Annotation von Gesichtern in unbeschränkten Domänen . . . 217 5.3.3. Evaluationsmethodik und Ergebnisdiskussion . . . . . . . . . . 218 5.4. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 6. Erkennung weiterer Objektklassen am Beispiel von Personen . . . 229 6.1. Merkmale für die Personenerkennung . . . . . . . . . . . . . . . . . . 230 6.2. Datensätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 6.3. Evaluation von Merkmalen auf verschiedenen Datensätzen . . . . . . 234 6.3.1. Evaluationsmethodik . . . . . . . . . . . . . . . . . . . . . . . 235 6.3.2. Auswertung und Ergebnisdiskussion . . . . . . . . . . . . . . . 238 6.4. Evaluation eines kaskadierten Klassifikationssystems . . . . . . . . . . 242 6.4.1. Systemarchitektur und Training . . . . . . . . . . . . . . . . . 242 6.4.2. Klassifikation und Evaluation . . . . . . . . . . . . . . . . . . 244 6.5. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 7. Zusammenfassung und Ausblick . . . 251 Anhang . . . 257 A. Übersicht zu den Experimenten zur Schnitterkennung . . . . . . . . . 259 A.1. Konfiguration und Laufzeiten der Experimente . . . . . . . . . 259 A.2. Stufe I: Farbraum und Bewegungsschätzung . . . . . . . . . . 261 A.3. Stufe II: Optimierung der Precision . . . . . . . . . . . . . . . 261 A.4. Echtzeitfähige Datenvisualisierung . . . . . . . . . . . . . . . . 267 A.5. Visualisierung einzelner Komponenten an Beispielen . . . . . . 269 B. Ergänzungen zu den Experimenten zur Gesichtsdetektion . . . . . . . 273 B.1. Trainingsverlauf des Klassifikators TUC FD . . . . . . . . . . 273 B.2. Übersicht zu den Mindestdetektionsgrößen auf TS100 . . . . . 273 B.3. Visualisierung der Detektionen auf TS100 . . . . . . . . . . . 279 C. Systemkonfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Verzeichnis der Abkürzungen und Begriffe . . . v Literaturverzeichnis . . . vii / The data collections of local television stations often consist of multiples of ten thousand video tapes. Modern methods are needed to exploit the content of such archives. While the retrieval of objects plays a fundamental role, essential requirements incorporate low false and high detection rates in order to prevent the corruption of the search index. However, a sufficient number of objects need to be found to make assumptions about the content explored. This work focuses on the adjustment and optimization of existing detection techniques. Therefor, the author develops a holistic framework that directly reflects on the high demands of video analysis with the aim to facilitate the development of image processing algorithms, the visualization of intermediate results, and their evaluation and optimization. The effectiveness of the system is demonstrated on the structural decomposition of video footage and on content-based detection of faces and pedestrians.:1. Motivation . . . 1 1.1. Einordnung in den Retrievalprozess . . . . . . . . . . . . . . . . . . . 2 1.2. Infrastruktur zur Optimierung von Verfahren zur Videoanalyse . . . . 4 1.3. Herausforderungen der Bilderkennung . . . . . . . . . . . . . . . . . . 6 1.4. Wissenschaftliche Ergebnisse dieser Arbeit . . . . . . . . . . . . . . . 9 1.5. Kapitelübersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2. Methoden und Strategien der Videoanalyse . . . 15 2.1. Fachgebiete der Bilderkennung . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1. Maschinelles Lernen . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.2. Maschinelles Sehen . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.3. Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.4. Mustererkennung . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2. Strukturelle Analyse von generischen Mustererkennungsystemen . . . 22 2.2.1. Datenakquisition . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2. Musteranalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.3. Musterklassifizierung . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.4. Bilderkennungssysteme . . . . . . . . . . . . . . . . . . . . . . 28 2.2.5. Wissensentdeckung in Datenbanken . . . . . . . . . . . . . . . 28 2.3. Bilderkennung in der inhaltsbasierten Bildsuche . . . . . . . . . . . . 29 2.3.1. Paradigmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.2. Bildsignaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.3. Signaturtypen . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.4. Lerntechniken . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4. Holistische Bilderkennungssysteme im Überblick . . . . . . . . . . . . 44 2.4.1. Ein segment- und konturbasiertes CBIR-System . . . . . . . . 45 2.4.2. Biologisch inspirierte Systeme . . . . . . . . . . . . . . . . . . 48 2.4.3. Lernen aus wenigen Beispielen . . . . . . . . . . . . . . . . . . 51 2.5. Objekterkennung im Szenenkontext . . . . . . . . . . . . . . . . . . . 55 2.6. Aktuelle Grenzen der Muster- und Objekterkennung . . . . . . . . . . 60 2.7. Konzept eines generischen Workflows zur Objekterkennung in Videos . . . 64 2.7.1. Strukturelle Analyse . . . . . . . . . . . . . . . . . . . . . . . 64 2.7.2. Inhaltliche Analyse . . . . . . . . . . . . . . . . . . . . . . . . 66 2.7.3. Erweiterung des klassischen Paradigmas zur Objekterkennung . . . 67 2.7.4. Anwendungsdomänen . . . . . . . . . . . . . . . . . . . . . . . 68 2.8. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3. Systemarchitektur zur Optimierung von Bilderkennungsverfahren . . . 71 3.1. Vorüberlegungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.1.1. Softwaretechnische Anforderungen . . . . . . . . . . . . . . . . 72 3.1.2. Bewertung der Systemleistung . . . . . . . . . . . . . . . . . . 75 3.1.3. Ein- und Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.1.4. Modellierung von Domänenwissen . . . . . . . . . . . . . . . . 90 3.1.5. Diskriminierbarkeit von Merkmalen . . . . . . . . . . . . . . . 92 3.1.6. Zusammenfassende Darstellung . . . . . . . . . . . . . . . . . 95 3.2. Architektur des Gesamtsystems . . . . . . . . . . . . . . . . . . . . . 95 3.3. Struktureller Aufbau von AMOPA . . . . . . . . . . . . . . . . . . . 97 3.3.1. Verwendung von Prozessketten . . . . . . . . . . . . . . . . . 101 3.3.2. Bild- und Videoverarbeitung . . . . . . . . . . . . . . . . . . . 106 3.4. Annotation von Bildern und Videos . . . . . . . . . . . . . . . . . . . 107 3.4.1. Ein Annotationswerkzeug für Videos . . . . . . . . . . . . . . 108 3.4.2. Ein Ansatz zu Annotation, Klassifikation und Evaluation . . . 111 3.5. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4. Videosegmentierung . . . 119 4.1. Schnitterkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.1.1. Struktureller Aufbau von Videos . . . . . . . . . . . . . . . . 121 4.1.2. Klassische Verfahren . . . . . . . . . . . . . . . . . . . . . . . 124 4.1.3. TRECVid: Evaluationskampagne und Datensätze . . . . . . . 125 4.1.4. Das Verfahren von AT&T . . . . . . . . . . . . . . . . . . . . 130 4.2. Schnittkomposition und Ähnlichkeit . . . . . . . . . . . . . . . . . . . 137 4.2.1. Dominant-Color-Deskriptor . . . . . . . . . . . . . . . . . . . 140 4.2.2. Color-Layout-Deskriptor . . . . . . . . . . . . . . . . . . . . . 140 4.2.3. Scalable-Color-Deskriptor . . . . . . . . . . . . . . . . . . . . 141 4.2.4. Edge-Histogram-Deskriptor . . . . . . . . . . . . . . . . . . . 142 4.3. Konzeption und Implementierung . . . . . . . . . . . . . . . . . . . . 143 4.3.1. Einbindung in das Prozesskonzept von AMOPA . . . . . . . . 144 4.3.2. Auswahl des Farbraums . . . . . . . . . . . . . . . . . . . . . 148 4.3.3. Bewegungsanalyse . . . . . . . . . . . . . . . . . . . . . . . . 151 4.3.4. Bestimmung und Verifikation von Schnittkandidaten . . . . . 159 4.3.5. Ergebnisdarstellung und -speicherung . . . . . . . . . . . . . . 171 4.4. Evaluation und Optimierung der harten Schnitterkennung . . . . . . 173 4.4.1. Die TRECVid Evaluationsmethodologie . . . . . . . . . . . . 174 4.4.2. Optimierung von Recall und Laufzeit . . . . . . . . . . . . . . 176 4.4.3. Optimierung der Precision . . . . . . . . . . . . . . . . . . . . 181 4.4.4. Validierung der Ergebnisse . . . . . . . . . . . . . . . . . . . . 183 4.5. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 5. Gesichtsdetektion . . . 187 5.1. Stand der Technik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.1.1. Verfahrensklassen und Datensätze . . . . . . . . . . . . . . . . 189 5.1.2. Boosting-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 192 5.2. Realisierung eines Systems zur Musterklassifizierung . . . . . . . . . . 200 5.2.1. Trainingsphase . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5.2.2. Klassifikation mit Hilfe von Detektorketten . . . . . . . . . . . 203 5.2.3. Erlernen eines geboosteten Gesichtsklassifikators . . . . . . . . 206 5.2.4. Exkurs: Gesichtslokalisation mittels Schwarmintelligenz . . . . 210 5.3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 5.3.1. Datensatz TS100 . . . . . . . . . . . . . . . . . . . . . . . . . 214 5.3.2. Annotation von Gesichtern in unbeschränkten Domänen . . . 217 5.3.3. Evaluationsmethodik und Ergebnisdiskussion . . . . . . . . . . 218 5.4. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 6. Erkennung weiterer Objektklassen am Beispiel von Personen . . . 229 6.1. Merkmale für die Personenerkennung . . . . . . . . . . . . . . . . . . 230 6.2. Datensätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 6.3. Evaluation von Merkmalen auf verschiedenen Datensätzen . . . . . . 234 6.3.1. Evaluationsmethodik . . . . . . . . . . . . . . . . . . . . . . . 235 6.3.2. Auswertung und Ergebnisdiskussion . . . . . . . . . . . . . . . 238 6.4. Evaluation eines kaskadierten Klassifikationssystems . . . . . . . . . . 242 6.4.1. Systemarchitektur und Training . . . . . . . . . . . . . . . . . 242 6.4.2. Klassifikation und Evaluation . . . . . . . . . . . . . . . . . . 244 6.5. Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 7. Zusammenfassung und Ausblick . . . 251 Anhang . . . 257 A. Übersicht zu den Experimenten zur Schnitterkennung . . . . . . . . . 259 A.1. Konfiguration und Laufzeiten der Experimente . . . . . . . . . 259 A.2. Stufe I: Farbraum und Bewegungsschätzung . . . . . . . . . . 261 A.3. Stufe II: Optimierung der Precision . . . . . . . . . . . . . . . 261 A.4. Echtzeitfähige Datenvisualisierung . . . . . . . . . . . . . . . . 267 A.5. Visualisierung einzelner Komponenten an Beispielen . . . . . . 269 B. Ergänzungen zu den Experimenten zur Gesichtsdetektion . . . . . . . 273 B.1. Trainingsverlauf des Klassifikators TUC FD . . . . . . . . . . 273 B.2. Übersicht zu den Mindestdetektionsgrößen auf TS100 . . . . . 273 B.3. Visualisierung der Detektionen auf TS100 . . . . . . . . . . . 279 C. Systemkonfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Verzeichnis der Abkürzungen und Begriffe . . . v Literaturverzeichnis . . . vii