\documentclass[12pt,fleqn]{report}
\usepackage[austrian]{babel}
\usepackage{german}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{xspace}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage{graphicx}

\textheight	680pt
\textwidth	460pt
\topmargin	-40pt
\oddsidemargin	  5pt
\evensidemargin	  5pt
\parindent	  0pt

\title{PS: Einf"uhrung in die Bioinformatik (SS99)\\
       \textbf{Fast Object Recognition}}
\author{Obermair Christoph
        \\\textit{\normalsize{cober@cosy.sbg.ac.at}}
        \\Schmidbauer Josef
	\\\textit{\normalsize{jschmid@cosy.sbg.ac.at}}
	\\Stieglbauer Gerald
	\\\textit{\normalsize{gstiegl@cosy.sbg.ac.at}}\\
        \\\textbf{Version 1999-04-13}\\\\Gruppe 3\\Zeit: 17.45 - 18.15
	\\Lehrveranstaltungsleiter: Schwaiger Roland}
\date{}
\begin{document}
\maketitle
\tableofcontents

\abstract
Ziel des Projekts ist eine ausf"uhrliche 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"unstlichen neuronalen Netzen erfolgen. Daraus soll ein m"oglichst schnelles Verfahren
zur Objekterkennung gesucht werden, welches langfristig auf dem am Institut f"ur Computerwissenschaften
der Universit"at Salzburg entwickelten Roboter E.M.M.A. Einsatz finden soll.

\chapter{Einleitung}

\section{Was ist Objekterkennung?}
\label{EinleitungObjekterkennung}
Informationsverarbeitende Systeme (IVS) k\"onnen ihre Umwelt nur \"uber bestimmte Schnittstellen
wahrnehmen. Diese Schnittstellen empfangen Informationen von au\ss en (Input) und werden
als Sensoren bezeichnet. Die Sensordaten k\"onnen auf verschiedene Weise ausgewertet
werden. Ein wichtiges Gebiet ist dabei die "`Object Recognition"'.
\newline
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\"onnen.
\newline
Dieses Dokument beschr\"ankt sich darauf, nur jene Eigenschaften zu verwenden, die aus
Bildern bestimmt werden k\"onnen, wobei ein Bild in diesem Zusammenhang eine zweidimensionale
optische Abbildung der Umwelt ist.
\newline
\newline
Im weiteren verstehen wir im speziellen unter IVS Roboter. Damit diese intelligent und
effizient mit ihrer Umwelt interagieren k"onnen, mu"s der Roboter Objekte in dieser Umwelt
erkennen und lokalisieren k"onnen, was wie bereits erw"ahnt "uber Sensoren erfolgt. Diese
Aufgabe l"a"st sich in drei Gebiete unterteilen \cite{grimson}:
\begin{itemize}
\item Identitifikation der Gestalt des gesuchten Objektes in einer nat"urlichen Umgebung.
\item Untersuchung des gefundenen Objektes auf seine definierenden Merkmale.
\item Feststellung der Position des Objektes bez"uglich einer r"aumlichen Abbildung der
      Umwelt.
\end{itemize}
Weitere wichtige Aspekte der Objekterkennung \cite{grimson}:
\begin{itemize}
\item Welche Sensoren sind relevant, um ein bestimmtes Objekt zu erkennen?
\item Wie soll man die definierenden Merkmale eines individuellen Objekt bestimmen?
\item Wie k"onnen gro"se Mengen von Klassifizierungsmerkmalen effizient gespeichert werden?
\item Welche Adressierungsmethoden werden verwendet, um bestimmte Objekte aus einer solchen
      Datenbank ableiten zu k"onnen?
\item Welche Methoden werden verwendet, um eine Beziehung zwischen Sensordaten und
      Objekteigenschaften herzustellen?
\item Wie kann man aus Sensordaten die Position und Lage eines Objektes herleiten?
\item Wie werden Eigenschaften neuer Objekte erkannt und in der Datenbank gespeichert?
\item Welche Rolle spielt die Gewichtung bei der Auswahl derjenigen Sensordaten, die f"ur
      das Objekt wesentlich sind?
\item Welche Rolle spielt die Bewertung einer speziellen Situation bzw. die
      Wahrscheinlichkeit von Ereignissen bei der Erkennung?
\item Welchen Beitrag leistet die Funktion oder der Zweck eines Objektes zu dessen
      Identifikation?
\item Welche Rolle spielen die geometrischen Eigenschaften und Merkmale bei dessen
      Lokalisierung?
\end{itemize}

\section{Erkennung von Objekten in Bildern}
Die Erkennung von Objekten l"a"st sich wie in \ref{EinleitungObjekterkennung} beschrieben
in zwei Gebiete einteilen:
\begin{itemize}
\item Abgrenzen der Objekte von ihrer Umwelt
\item Klassifizieren von Objekten
\end{itemize}

\subsection{Abgrenzen der Objekte von ihrer Umwelt}
Eine wichtige und grundlegende Komponente der Objekterkennung ist das Abgrenzen der Objekte, die sogenannte
Segmentierung. Hier werden einzelne Pixel in einer Bildmatrix als Teile von verschiedenen Objekten bzw.
Bereichen einer Szene identifiziert.\\
Objekte k"onnen durch verschiedene physikalische Gesetzm"a"sigkeiten gekennzeichnt sein und somit aus
einem Bild herausgl"ost werden\cite{kleiter}:
\begin{itemize}
\item \textbf{Formkonturen}
      \\Kontinuierliche Kanten markieren meist die Grenze eines Objekts, das andere Gegenst"ande
      oder einen Hintergrund verdeckt. Solche Konturen h"angen in der Regel mit abrupten
      diskontinuierlichen Tiefen"anderungen zusammen. Dazu geh"oren aus Bewegungen resultierende,
      parallele Verschiebungen. Kontinuierliche Kanten, abrupte Tiefen"anderungen und Bewegungsparallaxen
      grenzen einen Gegenstand von seiner Umgebung ab.
\item \textbf{Textur}
      \\Die Textur einer Oberfl"ache ist durch Bereiche "ahnlicher Helligkeitsdichten gekennzeichnet.
      Es kommen keine Tiefen"anderungen vor.
\item \textbf{Helligkeit}
      \\Besondere Helligkeitseffekte entstehen besonders beim Zusammentreffen mehrerer Oberfl"achen
      in einer Ecke. Die Helligkeitsunterschiede auf den verschiedenen Oberfl"achen sind graduierlich
      und nicht abrupt.
\item \textbf{Schatten}
      \\Schatten sind auch kontinuierliche Kanten, gehen jedoch nicht mit abrupten Tiefen"anderungen
      einher.
\item \textbf{Bewegung}
      \\Sich parallel bewegende Teile geh"oren meist zum gleichen Objekt.
\end{itemize}
Textur geht "uber Helligkeitseffekte und Schatteneffekte hinweg, nicht jedoch "uber Formkonturen.\\
Es ist schwierig die Segmentierung als einen generellen L"osungsansatz zu implementieren, da die Auswahl
der angef"uhrten Gesetzm"a"sigkeiten typischerweise sehr problemabh"angig sind \cite{chenpauwang}.

\subsection{Vorverarbeitung der Objekte}
Vor der Klassifizierung wird eine Vorverarbeitung durchgef"uhrt. Dabei werden wichtige
Eigenschaften von Objekten extrahiert und in einem n-dimensionalen Raum, den sogenannten
Feature Raum (oder Eigenschafts-Raum), eingetragen \cite{chenpauwang}, \cite{kulkarni}. 
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 eine Achse im Feature Raum abgebildet.
Je gr"o"ser die Anzahl der verwendeten Eigenschaften (Features) ist, desto besser k"onnen
die Objekte im allgemeinen differenziert werden, aber die Performance (Geschwindigkeit)
sinkt mit der Anzahl der verwendeten Features \cite{annforpat}. Durch eine vorangehende
Reduzierung des Feature Raums (Veringerung der Dimension des Raumes) auf die jeweils 
wesentlichsten Eigenschaften kann man die Komplexit"at verringern und die Geschwindigkeit
erh"ohen. W. Siedlecki und J. Sklansky \cite{chenpauwang} beschreiben genetische Ans"atze 
um die Dimension des Feature Space zu reduzieren.\\
Wesentliche Eigenschaften sind vom Anwendungsfall abh"angig. So ist z.B. die Verwendung 
der Objekthelligkeit als Feature f"ur die Objektklassifizierung in einer
Umgebung mit konstanter Helligkeit sinnvoller als in Umgebungen mit ver"anderlichen
Beleuchtungsverh"altnissen.\\
Eine g"angige Methode zur Extraktion von Features ist die Fourier Transformation \cite{hl}.
Dabei werden aus dem Bild des Objektes Frequenz und Phaseninformationen gewonnen. Je nach
Anwendungsfall kann man dadurch erreichen das z.B. beim Verwenden der Frequenzinformation
und Weglassen der Phaseninformation ein Objekt auch bei einer
verschobenen Abbildung die selbe Position im Feature Space hat \cite{kulkarni}.
Weitere Feature-Extraktionsverfahren sind z.B. Moment Feature Space \cite {kulkarni}, 
Chord Distribution Feature Space, die Hough Transformation \cite{chenpauwang}, 
Wigner Distribution Feature Space \cite{chenpauwang}, Orthogonal
Transformations \cite{kulkarni} und Gabor Funktionen \cite{chenpauwang}.\\
Bei verschiedenen Feature-Extraktionsverfahren lassen sich neuronale Netze einsetzten.
So beschreibt z.B. Kulkarni \cite{kulkarni} Modelle k"unstlicher neuronaler Netze 
(Artificial Neural Networks, ANN) f"ur die Feature-Extraktion via Fourier Transformation und
via Walsh-Hadamard Transformation.\\
Im Feature Space wird nun jedem Objekt aufgrund seiner Eigenschaften ein eindeutiger Punkt 
zugeordnet. Je geringer die Distanz zwischen zwei benachbarten Punkten im Feature Space ist 
desto "ahnlicher sind die Eigenschaften der Objekte die sie repr"asentieren. Das bedeutet aber im
allgemeinen nicht, da"s benachbarte Objekte unbedingt der selben Klasse angeh"oren m"ussen 
\cite{annforpat}.
Die Feature Space Abbildungen einer Klasse von Objekten befinden sich in einem Teilraum des 
Features Space. Im Idealfall "uberschneiden sich die Teilr"aume verschiedener Objektklassen nicht
und jedes Objekt l"asst sich direkt zu dem entsprechenden Teilraum und damit einer eindeutigen
Objektklasse zuordnen \cite{annforpat}.\\
Klassifizierungstechniken unterteilen anschlie"send den Feature Space in diese
Teilr"aume und schlie"sen durch den, dem Punkt zugeteilten Teilraum auf die Klasse des Objektes
(z.B. \cite{kulkarni},\cite{schalkoff}).

\subsection{Klassifizieren von Objekten}
Die konventiellen Klassifizierungstechniken f"ur Objekte lassen sich in Anlehnung an 
\cite{kulkarni} grob in zwei Kategorien eingeteilt werden:
\begin{enumerate}
\item{{\bf Statistische Methoden}\\
      Verwendet statistische Eigenschaften im Objekt-Eigenschafts-Raum (Feature Space) um
      Objekte zu klassifizieren.}
\item{{\bf Syntaktische Methoden}\\
      Verwendet eventuell wichtige, strukturelle Beziehungen zwischen Eigenschaften um
      Objekte zu klassifizieren.}
\end{enumerate}
Weiters kann man die Klassifizierungstechniken auch in
\begin{enumerate}
\item{{\bf "Uberwachte (supervised) Methoden}\\
      Hier steht f"ur jede Klasse eine Anzahl von "Ubungsbeispielen zur Verf"ugung, welche
      verwendet werden um das System zu trainieren}
\item{{\bf Nicht-"uberwachte (unsupervised) Methoden}\\
      Bei nicht "uberwachten Verfahren stehen keine Beispiele zur Verf"ugung. Das System 
      versucht die Daten selbst zu klassifizieren.}
\end{enumerate}
einteilen. Beispiele f"ur die Verwendung von "uberwachten und nicht-"uberwachten Methoden in
den konventionellen Klassifizierungstechniken (nicht ANN-basierende Verfahren) finden sich
in \cite[58 ff., 109 ff.]{schalkoff}\\


\appendix
\chapter{Protokolle}
\section{Besprechungsprotokolle}
\subsection{09.03.1999}
\begin{tabbing}
Teilnehmende Personen: \=Stieglbauer Gerald, \kill \\
Teilnehmende Personen: \>Schwaiger Roland\\
                       \>Obermair Christoph\\
		       \>Schmidbauer Josef\\
		       \>Stieglbauer Gerald
\end{tabbing}		       
Protokollf"uhrer: Stieglbauer Gerald\\
Ort: B"uro von Schwaiger Roland\\
Zeit: 17.55 - 18.10\\\\
Einf"uhrende Besprechung "uber das Projekt und erste Aufgabenstellung
\newline
\newline
Spezifikation des abzugebenden Projektberichtes:
\begin{itemize}
\item Zu verwendendes Satzsystem: \LaTeX
\item Eigene Titelseite
\item Abstract ("Ubersicht)
\item Einleitung (Um was geht es?)
\item Literatur"ubersicht
\item Literaturverzeichnis
\end{itemize}
Abgabe der Projektberichte jeweils bis Montag 13.00 Uhr
\newline
\newline
Erste Fragestellung:
\begin{itemize}
\item{Was ist Object Recognition?}
\end{itemize}

\subsection{16.03.1999}
\begin{tabbing}
Teilnehmende Personen: \=Stieglbauer Gerald, \kill \\
Teilnehmende Personen: \>Schwaiger Roland\\
                       \>Obermair Christoph\\
		       \>Schmidbauer Josef\\
		       \>Stieglbauer Gerald
\end{tabbing}		       
Protokollf"uhrer: Schmidbauer Josef\\
Ort: B"uro von Schwaiger Roland\\
Zeit: 17.45 - 18.05\\\\
Vorzunehmende Verbesserungen am Paper:
\begin{itemize}
\item{Angaben auf der Titelseite um Lehrveranstaltung, Version, Zeit, Gruppe,
      E-Mail-Adressen und Lehrveranstaltungsleiter erg"anzen}
\item{Abstract hinzuf"ugen}
\item{Einf"uhrung von Abk"urzungen f"ur h"aufig verwendete Begriffe}
\item{Angaben im Protokoll um Zeit, Ort und teilnehmende Personen erg"anzen}
\item{Abgabe via E-Mail mit Subject "`Bioinformatik, Gruppe 3"'}
\end{itemize}
Aufgaben bis zum 23.03.1999:
\begin{itemize}
\item{Suche nach Beschreibung f"ur "`Object Recognition"' in anderen B"uchern}
\item{Suche nach weiteren Verfahren zur Objekterkennung}
\item{Ausf"uhrlichere Beschreibung der statistischen Objekterkennung}
\item{Warum ist die statistische Objekterkennung so wichtig?}
\item{Stufen der Vorverarbeitung (Pre-Processing) eines Bildes,\\
      Analyse in einem anderen Abbildungsraum}
\end{itemize}

\subsection{23.03.1999}
\begin{tabbing}
Teilnehmende Personen: \=Stieglbauer Gerald, \kill \\
Teilnehmende Personen: \>Schwaiger Roland\\
                       \>Obermair Christoph\\
		       \>Schmidbauer Josef\\
		       \>Stieglbauer Gerald
\end{tabbing}		       
Protokollf"uhrer: Stieglbauer Gerald\\
Ort: B"uro von Schwaiger Roland\\
Zeit: 17.45 - 18.10\\\\
Vorzunehmende Verbesserungen am Paper:
\begin{itemize}
\item{E-Mail-Adressen auf Titelseite unter die Namen schreiben}
\item{Datum als Versionsnummer}
\end{itemize}

Aufgaben bis zum 13.04.1999:

\begin{itemize}
\item{Abgrenzung der Objekte von der Umwelt, Image Segmentation}
\item{Was sind "uberwachte Methoden bei dem statistischen Verfahren? (Beispiel)}
\item{Ans"atze f"ur die Transformation in den Feature-Raum}
\item{Was sind wichtige Eigenschaften bei der Ermittlung der Features von Objekten?}
\item{Was bedeuten Nachbarschaftsbeziehungen im Feature-Raum?}
\end{itemize}

\bibliographystyle{ieeetr}
\bibliography{bio_paper}
\end{document}
