PS: Einführung in die Bioinformatik (SS99) Fast Object Recognition

Obermair Christoph (cober@cosy.sbg.ac.at) Schmidbauer Josef (jschmid@cosy.sbg.ac.at) Stieglbauer Gerald (gstiegl@cosy.sbg.ac.at)

Version 0.2

Gruppe 3 Zeit: 17.45 - 18.15

Lehrveranstaltungsleiter: Schwaiger Roland

Inhaltsverzeichnis

1 Einleitung 2 1.1 Was ist Objekterkennung? . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Erkennung von Objekten in Bildern . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Abgrenzen der Objekte von ihrer Umwelt . . . . . . . . . . . . . . . 3 1.2.2 Klassifizieren von Objekten . . . . . . . . . . . . . . . . . . . . . . 3

A Protokolle 5

A.1 Besprechungsprotokolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 A.1.1 09.03.1999 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 A.1.2 16.03.1999 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Zusammenfassung

Ziel des Projekts ist eine ausführliche Auseinandersetzung mit dem Thema ”Objekterkennung“. Dabei werden eingangs grundlegende Methoden der Objekterkennung betrachtet und verglichen. In folge soll eine intensivere Auseinandersetzung mit der Objekterkennung mit Hilfe von künstlichen neuronalen Netzen erfolgen. Daraus soll ein möglichst schnelles Verfahren zur Objekterkennung gesucht werden, welches langfristig auf dem am Institut für Computerwissenschaften der Universität Salzburg entwickelten Roboter E.M.M.A. Einsatz finden soll.

Kapitel 1

Einleitung

1.1 Was ist Objekterkennung?

Informationsverarbeitende Systeme (IVS) können ihre Umwelt nur über bestimmte Schnittstellen wahrnehmen. Diese Schnittstellen empfangen Informationen von außen (Input) und werden als Sensoren bezeichnet. Die Sensordaten können auf auf verschiedene Weise ausgewertet werden. Ein wichtiges Gebiet ist dabei die ”Object Recognition“. Ein Objekt ist in diesem Kontext durch seine vordefinierten Eigenschaften eindeutig bestimmt und grenzt sich dadurch von seiner Umwelt ab. Man verwendet bestimmte Eigenschaften des Objektes um es von anderen unterscheiden zu können. Dieses Dokument beschränkt sich darauf, nur jene Eigenschaften zu verwenden, die aus Bildern bestimmt werden können, wobei Bild in diesem Zusammenhang eine zweidimensionales optische Abbildung der Umwelt ist.

Im weiteren verstehen wir im speziellen unter IVS Roboter. Damit diese intelligent und effizient mit ihrer Umwelt interagieren können, muß der Roboter Objekte in dieser Umwelt erkennen und lokalisieren können, was wie bereits erwähnt über Sensoren erfolgt. Diese Aufgabe läßt sich in drei Gebiete unterteilen [1]:

• Identitifikation der Gestalt des gesuchten Objektes in einer natürlichen Umgebung.

• Untersuchung des gefundenen Objektes auf seine definierenden Merkmale.

• Feststellung der Position des Objektes bezüglich einer räumlichen Abbildung der Umwelt.

Weitere wichtige Aspekte der Objekterkennung [1]:

• Welche Sensoren sind relevant, um ein bestimmtes Objekt zu erkennen?

• Wie soll man die definierenden Merkmale eines individuellen Objekt bestimmen?

• Wie können große Mengen von Klassifizierungsmerkmalen effizient gespeichert werden?

• Welche Adressierungsmethoden werden verwendet, um bestimmte Objekte aus einer solchen Datenbank ableiten zu können?

• Welche Methoden werden verwendet, um eine Beziehung zwischen Sensordaten und Objekteigenschaften herzustellen?

• Wie kann man aus Sensordaten die Position und Lage eines Objektes herleiten?

• Wie werden Eigenschaften neuer Objekte erkannt und in der Datenbank gespeichert?

• Welche Rolle spielt die Gewichtung bei der Auswahl derjenigen Sensordaten, die für das Objekt wesentlich sind?

• Welche Rolle spielt die Bewertung einer speziellen Situation bzw. die Wahrscheinlichkeit von Ereignissen bei der Erkennung?

• Welchen Beitrag leistet die Funktion oder der Zweck eines Objektes zu dessen Identifikation?

• Welche Rolle spielen die geometrischen Eigenschaften und Merkmale bei dessen Lokalisierung?

1.2 Erkennung von Objekten in Bildern

Die Erkennung von Objekten läßt sich wie in 1.1 beschrieben in zwei Gebiete einteilen:

• Abgrenzen der Objekte von ihrer Umwelt

• Klassifizieren von Objekten

1.2.1 Abgrenzen der Objekte von ihrer Umwelt

(Genauere Behandlung zu einem späteren Zeitpunkt!)

1.2.2 Klassifizieren von Objekten

Die konventiellen Klassifizierungstechniken für Objekte lassen sich in Anlehnung an [2] grob in zwei Kategorien eingeteilt werden:

1. Statistische Methoden Verwendet statistische Eigenschaften im Objekt-Eigenschafts-Raum (Feature Space) um Objekte zu klassifizieren.

2. Syntaktische Methoden Verwendet eventuell wichtige, strukturelle Beziehungen zwischen Eigenschaften um Objekte zu klassifizieren.

Weiters kann man die Klassifizierungstechniken auch in

1. Überwachte (supervised) Methoden Hier steht für jede Klasse eine Anzahl von Übungsbeispielen zur Verfügung, welche verwendet werden um das System zu trainieren 2. Nicht-überwachte (unsupervised) Methoden

Bei nicht überwachten Verfahren stehen keine Beispiele zur Verfügung. Das System versucht die Daten selbst zu klassifizieren.

einteilen. Vor der Klassifizierung wird eine Vorverarbeitung durchgeführt. Dabei werden wichtige Eigenschaften von Objekten extrahiert und in einem n-dimensionalen Raum, den sogenannten Feature-Raum (oder Eigenschafts-Raum), eingetragen [3], [2]. Methoden zum Klassifizieren von Objekten setzen auf diesen Feature-Raum auf und versuchen anhand der darin enthaltenen Daten Objekte einzuteilen. Jede verwendete Eigenschaft eines Objektes wird auf einer Achse im Feature-Raum abgebildet. Je größer die Anzahl der verwendeten Eigenschaften (Features) ist, desto besser können die Objekte im allgemeinen differenziert werden, aber die Performance (Geschwindigkeit) sinkt mit der Anzahl der verwendeten Features [4]. Durch eine vorangehende Reduzierung des Feature-Raums (Veringerung der Dimension des Raumes) auf die jeweils wesentlichsten Eigenschaften kann man die Komplexität verringern und die Geschwindigkeit erhöhen [3].

Anhang A

Protokolle

A.1 Besprechungsprotokolle

A.1.1 09.03.1999

Teilnehmende Personen: Schwaiger Roland Obermair Christoph Schmidbauer Josef Stieglbauer Gerald

Protokollführer: Stieglbauer Gerald Ort: Büro von Schwaiger Roland Zeit: 17.55 - 18.10 Einführende Besprechung über das Projekt und erste Aufgabenstellung Spezifikation des abzugebenden Projektberichtes:

• Zu verwendendes Satzsystem: L^{A}TEX

• Eigene Titelseite

• Abstract (Übersicht)

• Einleitung (Um was geht es?)

• Literaturübersicht

• Literaturverzeichnis Abgabe der Projektberichte jeweils bis Montag 13.00 Uhr Erste Fragestellung:

• Was ist Object Recognition?

A.1.2 16.03.1999

Teilnehmende Personen: Schwaiger Roland Obermair Christoph Schmidbauer Josef Stieglbauer Gerald

Protokollführer: Schmidbauer Josef Ort: Büro von Schwaiger Roland Zeit: 17.45 - 18.05 Vorzunehmende Verbesserungen am Projektbericht:

• Angaben auf der Titelseite um Lehrveranstaltung, Version, Zeit, Gruppe, E-Mail-Adressen und Lehrveranstaltungsleiter ergänzen

• Abstract hinzufügen

• Einführung von Abkürzungen für häufig verwendete Begriffe

• Angaben im Protokoll um Zeit, Ort und teilnehmende Personen ergänzen

• Abgabe via E-Mail mit Subject ”Bioinformatik, Gruppe 3“ Aufgaben bis zum 23.03.1999:

• Suche nach Beschreibung für ”Object Recognition“ in anderen Büchern

• Suche nach weiteren Verfahren zur Objekterkennung

• Ausführlichere Beschreibung der statistischen Objekterkennung

• Warum ist die statistische Objekterkennung so wichtig?

• Stufen der Vorverarbeitung (Pre-Processing) eines Bildes, Analyse in einem anderen Abbildungsraum

Literaturverzeichnis

[1] W. E. L. Grimson, Object Recognition by Computer: The Role of Geometric Constraints. The MIT Press, first ed., 1990.

[2] A. D. Kulkarni, Artificial Neural Networks for Image Understanding. Van Nostrand Reinhold, first ed., 1994.

[3] C. H. Chen, L. F. Pau, and P. S. P. Wang, Handbook of Pattern Recognition and Computer Vision. World Scientific Publishing, first ed., 1993.

[4] C. M. Bishop, Neural Networks for Pattern Recognition. Clarendon Press, Oxford, fourth ed., 1997.