Objekterkennung

Laut Problemstellung gilt es Objekte zu verfolgen, die mit einem oder mehreren Farbmarkern versehen sind. In der konzeptionellen Betrachtung wurde schon festgestellt, daß hierzu Domänenwissen, Wissen über die auftretenden Objekte, benötigt wird. Außerdem wurde die Beständigkeit der Längenverhältnisse und Winkel unter der hier auftretenden Projektion der ``Welt'' auf die Bildebene der Kamera schon festgestellt. Damit eignen sich diese Größen zur Beschreibung der auftretenden Objekte. Auch die Verwendung von die Objekte abbildenden Pixelmatrizen, sogenannten Schablonen, ist aufgrund dieser Invarianz denkbar. Translationen solcher Beschreibungen oder Vorlagen sind hier gar nicht, Rotationen nur um eine Achse notwendig. Die Anwendung solcher Schablonen erschwerende Verdeckungen treten per Definition der Problemstellung ebenfalls nicht (oder nur in Sonderfällen) auf. Ein Nachteil der Matrix-Schablonen ist der hohe Rechenaufwand beim Finden von Übereinstimmungen. Egal welcher Algorithmus verwendet wird, es ist immer ein Vergleich von Schablonen mit Matrixpixeln notwendig. In den meisten Fällen müssen auch Rotationen der Schablone am Bild getestet werden.

Wie man schon an der verwendeten Kodierung der Regionen in der vorigen Schicht erkennen kann, wird hier nicht der Weg der Schablonen - Matrizen gegangen. Vielmehr wird eine explizite Beschreibung der Objekte verwendet. Es werden mehrere Regionen, die ein bestimmtes Objekt bilden, und ihre Lage zueinander benannt. Bei der Beschreibung der Regionen werden nur die Farbe und optional die Fläche verwendet. Die Form der Regionen bleibt unbeachtet. Ein Objekt besteht aus mindestens einer Fläche, die das Zentrum markiert. Eine weitere Region des Objektes etabliert dann eine Objektachse. Hier wird außerdem der (Euklidsche) Abstand $\vert\vec{p}-\vec{p}'\vert$ vom Zentrum angegeben:

$\begin{displaymath} \vert\vec{p}-\vec{p}'\vert=\sqrt{(p_1-p'_1)^{2} + (p_2-p'_2)^{2}} \end{displaymath}$

(21)

**Abbildung:** Links die Ansicht eines Objektes mit Farbmarkern und rechts die Visualisierung einer möglichen Beschreibung. $d_{Mark}$ ist dabei der Abstand der Markierung vom Zentrum, und $w_{Mark}$ der Winkel des Positionsvektors der Markierung zur Objektachse.
$\resizebox {1\columnwidth}{!}{\includegraphics{objektschablone.eps}}$

Diese Beschreibung ist im Gegensatz zu Schablonen rotationsinvariant und muß daher nicht in verschiedenen Rotationen getestet werden. Zur Ablage dieser Beschreibungen wird eine sehr einfache Objektbeschreibungssprache samt Parser und Generator definiert. Die Beschreibungsdateien liegen dabei in für Menschen lesbarer und dokumentierter Form vor, so daß das Editieren von Hand leicht möglich ist.

Eine solche Beschreibung der Objekte soll später aber nicht von Hand, sondern vielmehr von einem grafischen Werkzeug erstellt werden (s. Abschnitt 3.2.2). Hier sollen auch die Toleranzgrenzen sinvoll eingestellt werden.

Die Objektbeschreibungsdatei wird eingelesen und aus ihr eine Liste von Schablonen generiert. Mit diesen Schablonen wird die Erkennungsschicht dann konfiguriert. Nun gilt es, anhand der Objektbeschreibungen in der Liste der Regionen Übereinstimmungen mit Objekten zu finden. Hierbei wird nicht eine Übereinstimmungswahrscheinlichkeit möglicher Treffer angegeben, sondern eine Entscheidung anhand der in der Objektbeschreibung angegebenen Toleranzschwellen getroffen. Liegen alle Größen in den spezifizierten Toleranzen, gilt ein Objekt als gefunden und wird der Ausgabeliste hinzugefügt.

Übereinstimmungen werden durch einen einfachen, intuitiven Algorithmus gesucht. Hierbei werden rekursiv die einzelnen spezifizierten Markierungen mit den gefundenen Regionen verglichen. Da die Regionen nach ihrer Farbe gruppiert vorliegen, müssen nicht für jede Markierung alle Regionen, sondern nur die mit gleicher Farbklasse verglichen werden. Nachdem eine Übereinstimmung gefunden wurde, wird nach weiteren Übereinstimmungen der gleichen Schablone gesucht, bis alle in Frage kommenden Regionen untersucht wurden. Hierbei handelt es sich im Prinzip um eine Tiefensuche in einem ``Zuordnungsbaum'', bei dem in jedem Sohn eine weitere Markierung einer Region zugeordnet wird. In den Blättern des Baumes finden sich dann vollständige Zuordnungen. Die Tiefe des Baumes wird durch die Anzahl der Markierungen in der Beschreibung bestimmt und ist damit beschränkt. Weil beim Finden einer passenden Region für eine Achse oder eine zusätzliche Markierung mehr Vergleiche als beim Finden eines Zentrums nötig sind (Abstand, Winkel bei Markierungen), somit also keine einheitliche Expandierungsfunktion definiert werden kann, eignet sich dieser Algorithmus nicht so sehr für die Implementierung mit Hilfe der allgemeinen Suchshell (siehe Abbildung 2.12).

Obwohl diese einfache Suche keine Heuristiken verwendet, ist sie bei der auftretenden Zahl von Objekten (11 im RoboCup) durchaus schnell genug. Weitere Optimierungen können direkt vom Klienten durch eine geschickte Wahl der Objektmarkierungen vorgenommen werden. So ist es zum Beispiel sinnvoll, gerade für die Markierungen der Zentren Farben auszuwählen, die nicht für andere Markierungen verwendet werden. Hält man die Zahl der gefundenen Regionen in einer speziellen Farbklasse niedrig, verringert sich der Suchaufwand. Allgemein gilt es, die Objekte so zu markieren, daß sie anhand von möglichst wenigen Vergleichen unterschieden werden können.

Zurückgegeben werden die gefundenen Objekte nach ihrem Typ (die ID der Beschreibung, mit der sie gefunden wurden) zusammengefaßt. Ein Objekt ist dabei eine Instanz der Klasse CObject, wobei die Eigenschaften Klasse, Position und Orientierung gültige Werte besitzen. Die ID und die Geschwindigkeit müssen erst noch bestimmt werden.