Erkennung mehrerer Objekte durch parallele Suchagenten

Diplomarbeit von Markus Volkmer

Einleitung:

Im Rahmen der vorliegenden Diplomarbeit wird ein System zur maschinellen Erkennung mehrerer Objekte (basierend auf Intensitätsbildern) erarbeitet, implementiert und analysiert.

Diese Problemstellung erforderte eine selbständige Einarbeitung in die die Arbeit betreffenden Gebiete und deren Einordnung zur Entwicklung eines Systems. Die in Erwägung gezogenen aktuellen Verfahren werden dazu erläutert und vor dem Hintergrund der Problemstellung und weiteren Randbedingungen betrachtet. Als Folge dieser Betrachtungen ergibt sich die Umsetzung eines homogenen Multi-Agenten-Systems. Die implementierten Agenten realisieren parallel Intensitäts-basiertes Template-Matching und Fast Simulated Annealing mit Temperatur-parametrisiertem Suchraum. Der konzeptionelle Weg von der Betrachtung von Lösungsmöglichkeiten, über die Entscheidungsfindung, die Integration, bis hin zur Implementierung und Bewertung des Systems, ist daher Teil dieser Arbeit und nicht lediglich die Vorstellung eines umgesetzten Verfahrens.

Die der Arbeit zugrundeliegenden theoretischen Prinzipien werden erörtert. Eine Darstellung der implementatorischen Aspekte und die Analyse der Ergebnisse wird durch eine Bewertung des Systems und seiner problemspezifischen Anwendbarkeit, sowie durch Aufzeigen von Modifikationen und möglichen Erweiterungen ergänzt. Zur Entwicklung zählt auch die Installation unterstützender Software sowie die Implementierung einer graphischen Benutzeroberfläche zur Steuerung des Systems, einer Testumgebung für die relevanten (Bild-)Operationen des Verfahrens und einer Online-Visualisierung.

Gang der Untersuchung:

Es folgt zunächst eine kurze inhaltliche Übersicht über die einzelnen Kapitel. Danach wird die Erkennung mehrerer Objekte durch parallele Suchagenten, im Vorgriff auf die anschließende Entwicklung dieses Konzeptes, motivierend vorgestellt. Mit der Festlegung der im Rahmen der Arbeit verwendeten Notation endet dieses Kapitel.

Der Aufbau der Arbeit entspricht dem verfolgten Weg von der Problemdefinition bis zur Umsetzung und Evaluierung der implementierten Lösung. Zuerst wird in diesem Kapitel in Abschnitt 1.2 eine Motivation für den verfolgten Suchagenten-Ansatz vor dem Hintergrund der konkreten Problemstellung gegeben. Nach einem kurzen Abschnitt (1.3) zur Festlegung der Notation werden in Kapitel 2 die in der Recherche nach Lösungsmöglichkeiten erwogenen Ansätze vorgestellt. Der Entscheidungsweg wird skizziert und der favorisierte Ansatz zur Lösung der Aufgabenstellung „Objekterkennung“ motiviert. Dabei kommen die in den folgenden Kapiteln erläuterten Methoden Template-Matching- und Optimierungstechniken zum Einsatz. Kapitel 3 erörtert das verwendete Konzept des Template Matching und gibt eine Übersicht zu Ähnlichkeits- und Korrelationsmaßen in Bezug auf die verwendeten bildbasierten Templates. Auf deren Anwendungsgebiete und Eigenschaften wird ebenfalls eingegangen.

Das folgende Kapitel (Kapitel 4) stellt das zur Korrelations-Maximierung verwendete Annealing-Verfahren vor und geht auf verwandte und abgewandelte Verfahren ein. Dabei werden Optimierungsprinzipien allgemein und im Kontext der Computer Vision betrachtet. Die in den Kapiteln 3 und 4 erläuterten Konzepte und Methoden finden direkten Eingang in das im nächsten Kapitel vorgestellte Agentensystem. Nachdem somit eine Grundlage für die Erkennung von Objekten vorhanden ist, wird in Kapitel 5 der Suchagenten-Ansatz eingeführt. Dabei werden, ausgehend von der Problematik der Erkennung mehrerer Objekte, grundlegende Konzepte zum Agentenkonzept und konkrete Strategien zur Lösung des vorliegenden Problems dargestellt. Auch auf verteilte Strategien zur Erkennung einzelner Objekte und die Möglichkeiten der Parallelisierung allgemein wird eingegangen, da hier ein entwicklungsgeschichtlicher und implementierungstechnischer Zusammenhang besteht. Kapitel 6 geht auf implementatorische Details ein. Die benutzten Software-Pakete und Bibliotheken werden kurz erläutert. Danach wird das Programmpaket bestehend aus den Programmen Matchlt und (Visual-)Slave im Detail erläutert, das die Erkennung mehrerer Objekte durch parallele Suchagenten implementiert. Die experimentellen Ergebnisse werden in Kapitel 7 dokumentiert. Hierbei liegt der Schwerpunkt auf der Erkennungsleistung des Systems unter verschiedenen experimentellen Bedingungen und nicht auf der durch parallele Implementierung mögliche Beschleunigung (Speed- Up) in der Erkennung mehrerer Objekte. Weiterhin erfolgt hier die Diskussion und Bewertung des Systems und der erzielten Ergebnisse. Die Arbeit schließt in Kapitel 8 mit einer rückblickenden Zusammenfassung der Diplomarbeit und einem Ausblick auf mögliche zukünftige Erweiterungen und Anwendungen des vorgestellten Verfahrens.

Das Literaturverzeichnis im Anhang wird ergänzt durch Verzeichnisse der Abbildungen, Tabellen und Algorithmen.

Inhaltsverzeichnis:

1.	Einleitung und Problemstellung	1
1.1	Aufbau der Arbeit	2
1.2	Objekterkennung durch Suchagenten - Motivation	3
1.3	Notation	5
2.	Lösungsansätze zur Objekterkennung	7
2.1	Geometrie-basierte Verfahren	8
2.1.1	Erkennung durch Invarianten	8
2.2	Appearance-basierte Verfahren	14
2.2.1	Appearance-based Object Recognition und Eigenraumverfahren	14
2.3	Motivation des gewählten Ansatzes: Erkennung durch Template-Matching	22
2.3.1	Geometrie-basiert versus Appearance-basiert	22
2.3.2	Eigenraumverfahren versus Template-Matching	23
3.	Template-Matching und Korrelationstechniken	26
3.1	Template-Matching	27
3.1.1	Modellbasierte Templates	27
3.1.2	Bildbasierte Templates	27
3.2	Ähnlichkeits- und Korrelationsmasse	28
3.2.1	Korrelationsebenen	29
3.2.2	Kreuz-Korrelation und abgeleitete Masse	30
4.	Simulated Annealing zur Korrelations-Maximierung	37
4.1	Objekterkennung durch Optimierung	38
4.1.1	Lokale Verfahren	39
4.1.2	Globale Verfahren	41
4.2	Simulated Annealing und (stochastische) Relaxationsverfahren	43
4.2.1	Simulated Annealing	44
4.2.2	Annealing versus Evolutionäre (Genetische) Algorithmen	49
4.2.3	Deterministische Relaxation	50
4.2.4	Fast Simulated Annealing mit Temperatur-parametrisiertem Suchraum	54
5.	Parallele Suchagenten zur Lösung des Multiple-Objekte-Problems	57
5.1	Verteilte Lösungen und Parallelisierungsstrategien	58
5.1.1	Daten- versus Aufgaben-Parallelisierung	59
5.1.2	Parallelisierungen des Erkennungsalgorithmus	60
5.2	Parallele Suchagenten	66
5.2.1	Agenten, Agentensysteme und Suchagenten	66
5.2.2	Agenten in der Computer Vision	71
5.2.3	Interface-Agent MatchIt	78
5.2.4	Der Suchagent (Visual-)Slave	80
6.	Implementierung	83
6.1	Unterstützende Software und Werkzeuge	84
6.1.1	Die Bildverarbeitungsumgebung Vista	84
6.1.2	Die Parallele Virtuelle Maschine (PVM)	85
6.2	Master and Slave(s) - MatchIt und die Suchagenten	87
6.2.1	MatchIt	88
6.2.2	Slave und Visualslave	95
7.	Experimentelle Ergebnisse, Diskussion und Bewertung	101
7.1	Erkennung durch einen Suchagenten	102
7.1.1	Erkennung nicht verdeckter Objekte	102
7.1.2	Erkennung eines teilweise verdeckten Objektes	107
7.1.3	Variation der Objektmenge	108
7.2	Parallele Erkennung durch mehrere Suchagenten	109
7.2.1	Parallele Erkennung - Einzelaufgaben	109
7.2.2	Parallele Erkennung - Team	112
7.2.3	Parallele Erkennung von Objektteilen (Sub-Templates)	116
7.3	Korrelation als Matching-Kriterium	118
7.4	Experimentelle Ergebnisse - Fazit	120
8.	Zusammenfassung und Ausblick	121
	Literaturverzeichnis
	Abbildungsverzeichnis
	Tabellenverzeichnis
	Algorithmen