Offline-Algorithmen zur Objektsegmentierung

Im folgenden werden Strategien zur Interpretation der Scan-Ergebnisse erläutert, insbesondere zur Segmentierung der Bildelemente in einzelne, größere Objekte. Im Gegensatz zu dem vorherigen Kapitel sind dies Algorithmen, die aufgrund ihrer Komplexität offline durchzuführen sind.

Projektion der Daten

Abbildung 4.1: Projektion eines 3D-Scans auf die $(X,Y)$-Ebene

Der Scanner liefert die Daten der Umgebung in einzelnen $(X,Z)$-Schnitten durch den Raum. Ein Scan läßt sich also als eine Art ,,Draufsicht`` auf den Raum von oben aus sehen, mit steigender Scannummer steigt insbesondere die Höhe des Schnittes.

Da diese Ansicht jedoch ausgesprochen unintuitiv ist, bestand der erste Versuch nun darin, die Daten eines kompletten 3D-Scan in $(X,Y)$-Richtung zu projizieren, um auf diese Weise eine Art Frontalansicht zu erhalten. Dies bedeutet, daß - vom Betrachter aus gesehen - mit wachsender Scannummer die $(X,Y)$-Ebene weiter nach hinten wandert.^4.1

Es folgen nun - sofern nicht anders erwähnt - zunächst einmal Algorithmen, die auf diesen 2D-Projektionen arbeiten. Später jedoch wird ein Wechsel zu Verfahren stattfinden, die direkt in dem 3D-Bild arbeiten.

Modifizierung der Daten

Zur besseren Handhabung der quasi-kontinuierlichen Daten des Scanners wurde zunächst der Datenstrom nach Abtastung in $X$-Richtung und Quantisierung in $Y$-Richtung in einer Booleschen Matrix $\Phi \in \mathbbm{B}^{n\times m}$ abgespeichert, also doppelt gleichförmig digitalisiert (Abbildung 4.2). In diesem digitalisierten Bild galt es nun, die Kanten der Objekte bzw. Objektflächen zu extrahieren: mittels Ortsraumfilterung sollten augefüllte Flächen eliminiert und einzig Pixel, die eine Hintergrund- von einer Objektfläche trennen, übriggelassen werden.

Abbildung 4.2: Digitalisierung der Daten

Der naheliegendste Ansatz bestand in der Anwendung eines Gradientenfilters [Hab91,Shi87] auf das Bild: Jeder Bildpunkt $\Phi(\xi,\zeta)_{\substack{\xi\,\in\,2,\dots,n-1\\ \zeta\,\in\,2,\dots,m-1}}$ mit Grauwert $\pi\bigl(\Phi(\xi,\zeta)\bigr)$ bekommt den neuen Grauwert

$$\pi'\bigl(\Phi(\xi,\zeta)\bigr) := \sum_{i=-\varrho }^{\varrho }\sum_{j=-\varrho }^{\varrho } \pi\bigl(\Phi(\xi,\zeta)\bigr)\cdot \Psi(i,j)$$ (4.1)

zugewiesen. Der Einfachheit halber wird im folgenden der Radius $\varrho = 1$ gesetzt.

Dabei ist die Filter-Matrix $\Psi$ je nach zu verwendetem Filtern ($X$-Gradient, $Y$-Gradient) zu wählen als:

$$\substack{\left[\begin{array}{*{3}{r}} -1 & -1 & -1 \\ 0 & 0 & 0... ... -1 & 0 & 1 \end{array}\right]\\ [1ex] \text{\footnotesize ($Y$--Gradient)}}$$

Es werden bei Verwendung der $X$-Gradientenmatrix jedoch lediglich horizontale Kanten in dem Bild erkannt, bzw. nur vertikale Kanten bei der zweiten Matrix. Abhilfe schafft das Kombinieren beider Filtermasken, jedoch brachte dieser Versuch auf den Testdaten noch keinen überzeugenden Erfolg.

Abbildung 4.3: Anwendung eines Laplacefilters auf das digitalisierte Bild

Ein sehr viel besseres Ergebnis lieferte ein Laplace-Filter mit folgender Filtermaske ( $\varrho = 1$):

$$\Phi := \left[\begin{array}{*{3}{r}} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{array}\right]$$

Dieser Filter erkennt auch nichtlineare Krümmungen im Grauwertverlauf des Bildes unabhängig von ihrer Richtung (siehe Abbildung 4.3). Da er im allgemeinen auf Rauschen empfindlich reagiert, wird gewöhnlich eine Glättung des Bildes vorgeschaltet, was jedoch bei Tests auf unseren Daten keinen positiven Erfolg brachte. Das mag daran liegen, daß im allgemeinen Fall von Grauwertbildern ausgegangen wird, hier jedoch binäre Bilddaten vorliegen.

Vektorisierung

Der vorherige Schritt liefert ein Bild, welches lediglich die relevanten Kanten der gescannten Objekte beinhaltet. Jedoch handelt es sich hier immer noch um Bitmap-Bilder, ist für die nachfolgende Flächen- und Objektsegmentierung in dieser Form also ungeeignet.

Abbildung 4.4: Ergebnis der Linienerkennung

Mit Hilfe des im Abschnitt 3.2.1 beschriebenen Linienerkennungs-Algorithmus wird nun das Kantenbild vektorisiert, d.h. es wird in eine Anzahl von Linien transformiert. Diese Linien, bestehend aus Anfangs- und Endpunkt, ermöglichen nun die weitere Untersuchung des Scans wie die Segmentierung und anschließende Erkennung von Objekten.

Ein mögliches Ergebnis der Vektorisierung ist in Abbildung 4.4 zu betrachten. Jedoch arbeitet der verwendete Linienerkennungs-Algorithmus naturgemäß unter Verwendung einer Vielzahl von heuristischen Parametern, so daß an dieser Stelle eine Optimierung dieser Parameter aufgrund einer größeren Anzahl von Bildvorlagen notwendig ist. Dabei ist die ,,optimale`` Einstellung allerdings nicht eindeutig, je nach Zielsetzung der Vektorisierung kann eine Änderung einiger Einstellungen vonnöten sein. So ist es hier beispielsweise sinnvoll, von einer allzu perfekten Nachbildung des Ausgangsbildes abzusehen (es ist durchaus möglich, jede Ecke und Kante durch eine eigene Linie beschreiben zu lassen), da solch ein Ergebnis zwar optisch sehr realistisch aussieht, jedoch beispielsweise eine sinnvolle Flächenerkennung als nahezu unmöglich gestaltet.

Evaluation

Dieser erste Versuch der Aufbereitung eines 3D-Scans erschien recht naheliegend, ist dann aber zunächst einmal zugunsten des im folgenden beschriebenen Vorgehens nicht weiter verfolgt worden [Blo82]. Grund dafür waren theoretische Überlegungen, daß mit dieser Projektion der dreidimensionalen Daten auf eine 2D-Ebene ein Informationsverlust einhergeht: dem Programm liegt ein $2\frac{1}{2}\,$-dimensionales Abbild eines Objektes (beispielsweise eines Stuhles) vor, jedoch werden nur 2 Dimensionen wirklich benutzt. Somit gingen die nächsten Versuche - einschließlich der aktuellen Implementation - in die Richtung, komplett auf den 3D-Daten zu arbeiten. Jedoch wurde der Algorithmus zur Vektorisierung beibehalten, da dieser Schritt eine notwendige Grundlage für eine Szeneninterpretation sein dürfte.

Es sei jedoch angemerkt, daß dieses Vorgehen trotz der damit einhergehenden Informationsreduzierung durchaus seine Berechtigung hat. Schließlich soll es nicht zur kompletten Interpretation der Szene dienen, sondern lediglich das Erkennen eines Objektes erleichtern, nachdem die Szene in einzelne Objekte/Cluster segmentiert worden ist. Eingedenk der bisher noch schwer zu bewertenden Ergebnisse der im folgenden skizzierte Algorithmen ist es durchaus möglich, daß der Ansatz der Koordinatenprojektion wieder als additives Vorgehen Verwendung findet, um die bereits implementierten Algorithmen bei der Aufgabe der Objekterkennung zu unterstützen.

Von dem ersten Versuch weitgehend abstrahiert, besteht die aktuelle Umsetzung schematisch gesehen aus folgenden Schritten:

Linien-Erkennung:

Wie bereits beschrieben liefert der Scanner die Daten in diskreten Schritten, die jeweils einen Scan der $(\xi,\zeta)$-Ebene darstellen. Sobald solch ein Scan abgeschlossen ist, wird der Linienerkenner (Abschnitt 3.2.1) auf dieser Ebene gestartet. Die resultierenden Linien (also das vektorisierte Bild) werden gespeichert und weiterverarbeitet, indem sie in Beziehung zu vorhergehenden bzw. nachfolgenden Scans gebracht werden.

Flächen-Segmentierung:

In diesem Schritt wird versucht, Linien aus unterschiedlichen Scans zu Flächen zusammenzufügen (Abschnitt 3.2.4). So wird eine eingescannte Wand beispielsweise nach dem ersten Schritt durch eine vertikal verlaufende Ansammlung von nahezu parallelen Linien repräsentiert. Die Flächensegmentierung soll nun alle diese Linien zu einer großen Fläche zusammenfügen.

Objekt-Segmentierung:

Schließlich werden singuläre (also nicht zu Flächen segmentierte) Linien sowie kleinere Flächen, die selbst nur einen Teil eines Objektes darstellen, zu größeren Objekten zusammengefügt.

Dieses Vorgehen wird im folgenden näher beschrieben.

Nähere Informationen über den genauen Ablauf und implementationsspezifische Details sind in Abschnitt 5, Seite zu finden.

Objekt-Segmentierung

Alle bisherigen Elemente (Punkte, Linien, Flächen) sind im Grunde genommen lediglich geschickte ,,Umstrukturierungen`` der 3D-Daten gewesen. Mit der Datenstruktur object hingegen wird eine neue Klasse eingeführt, die ermöglichen soll, die einzelnen Objekte der Szene effizient zu segmentieren und später einmal auch zu klassifizieren. Aus diesem Grund ist object auch die einzige Element-Klasse, die nicht - direkt oder indirekt - Punkte referenziert, sondern eigenständig neue Informationen einfügt -- die sinnvollerweise jedoch in Termen der schon bekannten Elemente implementiert worden sind.

Ziel eines solchen Objektes ist es nun, hinreichend nahe beieinander liegende Elemente - dies sind primär kleinere Flächen und Anhäufungen von singulären Linien, jedoch können auch Punkte/Punktwolken durchaus von Interesse sein - zu clustern. Diese Cluster werden mit einer Bounding Box umgeben und im folgenden als ein einzelnes Objekt betrachtet; jedoch bleiben Referenzen auf diese das Objekt bestimmenden Elemente weiterhin gespeichert, um spätere direkte Zugriffe zu ermöglichen.

Abbildung: Repräsentation eines Objektes

Der Objektsegmentierung liegt die Idee zugrunde, daß die oben beschriebenen, noch verbleibenden Elemente sich im allgemeinen zu sinnvoll segmentierbaren Wolken gruppieren, die ein Clustering ermöglicht. Sei beispielsweise ein Stuhl gegeben. Dieser wird im 3D-Scan zwar ein recht klares Bild aus Einzel-Punkten ergeben, jedoch schon die Linienerkennung wird bestenfalls viele kurze, gegeneinander verdrehte Linien finden, welche unmöglich zu einer (großen) Fläche segmentiert werden können (was im Übrigen trivialerweise auch nicht erwünscht wäre).

Wenn jedoch nun ein Element dieses Stuhles, beispielsweise eine kleine Fläche, die die Rückenlehne approximiert, oder auch nur eine einzelne Linie, als Ausgangspunkt genommen wird und davon ausgehend alle Elemente gruppiert werden, welche sich in hinreichend enger Nachbarschaft zu diesem Ausgangspunkt befinden, so werden im Idealfall auf diese Weise alle Elemente, die den Stuhl bestimmen, zu einem Objekt geclustert.

Zum besseren Verständnis sei noch erwähnt, daß bei oben beschriebenem Szenario der ,,Ausgangspunkt`` selber schon als Objekt betrachtet wird, welches es im folgenden gilt zu vergrößern, zu expandieren. Durch das Aufnehmen weiterer Elemente, die sich hinreichend nahe befinden, ,,wächst`` das Objekt, es vergrößert sich in seinen Ausmaßen. Auf diesen Sachverhalt wird jedoch in Abschnitt 4.2.1 noch näher eingegangen.

Algorithmus

Die eigentliche Objektsegmentierung verläuft in folgenden Schritten:

1. In einem Vorverarbeitungs-Schritt werden alle Flächen, deren Fläche einen Schwellwert übersteigt, direkt als Objekte klassifiziert. Dies werden im allgemeinen Wände, Schränke und ähnliche große, flächige Gegenstände sein.
2. Die erste Fläche wird aus der Menge der gespeicherten Flächen entfernt und in ein Objekt transformiert:
   Es muß der Mittelpunkt der Fläche bestimmt werden sowie die Achsen so gesetzt, daß der daraus aufgespannte Würfel die gesamte Fläche umschließt. Ferner ist der Radius so zu wählen, daß der Würfel seinerseits von der Kugel vollständig umschlossen wird.
3. Nun werden die drei Elemente-Listen, die ja stets alle bisher noch singulären Elemente beinhalten, durchlaufen auf der Suche nach Elementen, welche nahe genug zu dem neuen Objekt liegen. Bildlich gesehen werden also alle Elemente in der Nähe des Objektes ,,aufgesogen``, welches sich dadurch immer weiter aufbläht, bis es (im idealen Fall) alle an dieser Stelle zusammenliegenden Elemente geclustert hat.

   Je nach Einstellung zugehöriger heuristischer Parameter werden dabei offensichtlich nahe beieinander stehende Objekte zu einem einzigen verschmolzen. Dies ist zur Erkennung von Hindernissen, denen ein Roboter auszuweichen hat, gerade erwünscht. (Für dicht möblierte Räume kann sogar nur eine einzige Bounding Box existieren.)

4. Die letzten beiden Schritte werden mit allen anderen Einträgen der Elemente-Listen wiederholt.

Resultat: Der Algorithmus liefert eine Aufteilung der Scene in Objekte dergestalt, daß Akkumulationen von Punkten, Linien und/oder Flächen zu einzelnen Objekten zusammengefaßt und dabei von einer Bounding Box umschlossen werden. Diese Bounding Box stellt nicht nur einen wichtigen Schritt zur Objekterkennung dar. Vielmehr ermöglicht sie ferner die effiziente Navigation um dreidimensionale Hindernisse herum, deren exakte Form zu diesem Zweck nicht notwendig ist [Sur01].