Segmentierung

Trotz ihrer Einfachheit benötigt die Segmentierungsschicht eine längere Diskussion der Techniken und eine sorgfältige Implementierung. Weil die Daten hier noch in unkomprimierter Form vorliegen und mit einer Breite von bis zu 30 MB/s verarbeitet werden müssen, hat diese Schicht trotz der Einfachheit der durchzuführenden Operationen entscheidenden Einfluß auf die Performance des gesamten Systems (siehe Anhang A).

Es gibt eine Unmenge von Methoden, die Segmentierung vorzunehmen. Man unterscheidet zwischen partieller und vollständiger, lokaler und globaler, kontextabhängiger und -unabhängiger Segmentierung [7], [19]. Bei einer vollständigen Segmentierung stimmen die disjunkten Regionen eindeutig mit Objekten überein. Bei der partiellen Segmentierung gibt es hingegen keine direkte Übereinstimmung. Lokale Methoden verwenden zur Zuordnung eines Bildpunktes nur den Punkt selbst oder die lokale Nachbarschaft. Globale Methoden sind zum Beispiel alle modellbasierten Algorithmen oder die Houghtransformation. Je nachdem, ob die Methoden Wissen über den Inhalt des zu segmentierenden Bildes benötigen, teilt man sie auch in kontextabhängige und kontextunabhängige ein. Die Grenzen dieser Gruppen sind fließend.

Eine vollständige und korrekte Segmentierung ist nicht ohne die Zusammenarbeit mit höheren Schichten und ohne höheres Objektwissen möglich. Die hierarchische Architektur und die geringe zur Verfügung stehende Rechenzeit lassen somit nur eine partielle Segmentierung zu. Da das Ziel nicht die korrekte und vollständige Segmentierung des Bildes, sondern die Positionsbestimmung und Verfolgung von einzelnen Objekten ist, reicht eine einfache, partielle Segmentierung völlig aus. Unter Umständen kann die Segmentierung in höheren Schichten noch verbessert werden. Die Segmentierung muß gerade so gut sein, daß genügend Übereinstimmungen zwischen Regionen und Objekten bestehen, um höheren Schichten unter Heranziehung von Domänenwissen die Gewinnung der benötigten Informationen zu ermöglichen.

Unter diesen Gesichtspunkten kommen die von Jähne als elementare Segmentierungsverfahren bezeichneten Methoden in Frage. Diese lassen sich wiederum in drei Klassen einteilen: Pixelbasierte, regionenorientierte und kantenbasierte Methoden. Im Hinblick auf die zu unterstützende Problemklasse reicht die pixelbasierte Methode aus. Aber auch die Heranziehung lokaler Nachbarschaften könnte sich als vorteilhaft bei ungleichmäßigen Beleuchtungen und starken Schatten erweisen. Kantenbasierte Verfahren scheiden im Hinblick auf die untergeordnete Rolle der Objektform in der Aufgabenstellung und wegen des höheren Rechenaufwands aus.

Nun ist es bei der zu bearbeitenden Problemstellung so, daß Objekte und ihre Flächen durch ihre Farbe gekennzeichnet werden. Es gilt unterschiedliche Farbflächen und ihre Anordnung zu finden. Die Beleuchtung ist in der künstlichen Umgebung zumindest in soweit kontrollierbar, daß sehr starke Schwankungen und Schattenbildungen ausgeschlossen werden können. Die Ausleuchtung einer 2-dimensionalen Ebene gestaltet sich wesentlich einfacher als die gleichmäßige Ausleuchtung eines Raumes. Überdeckungen und damit verbundene Schattenbildungen können per Definition ausgeschlossen werden. Da die Verwendung lokaler Nachbarschaften sich in ersten Tests außerdem als zu langsam erwiesen hat und mit CMVision die Funktion von pixelbasierter Farbsegmentierung im RoboCup nachgewiesen wurde, wird auch hier der Weg der pixelbasierten Farbsegmentierung gewählt. Obwohl mit CMVision eine Referenzimplementierung dieser Schicht vorliegt, sollen die möglichen Algorithmen und ihre Vor- und Nachteile noch einmal beleuchtet werden. Da der Benutzer später bei der Kalibrierung unterstützt werden soll, gilt es auch die Eignung der einzelnen Verfahren für Kalibrierungstechniken im Auge zu behalten (siehe Abschnitt 3.2.1).

Eine Methode ist die der linearen Schwellwerte. Hierbei wird der Farbraum durch lineare Grenzen unterteilt. Dieses Verfahren kann daher einfach trainiert werden. Eine andere Methode, die den Farbraum ebenfalls linear aufteilt, ist die Nächster-Nachbar-Klassifikation. Hier gibt es einen oder mehrere Prototypen einer jeden Klasse. Ein bestimmter Farbwert wird der Klasse des nächsten Prototyps zugeordnet. Diese Technik eignet sich ebenfalls für Trainingsmethoden wie z.B. Learning Vector Quantization (LVQ) und Clustering Techniken. Beide Methoden liefern gute Resultate bei der Klassifikationsgenauigkeit, sind aber nach eigenen Tests zu langsam für die direkte Verwendung in Echtzeitanwendungen.

Eine weitere Methode ist die der konstanten Schwellenwerte. Hierbei werden die Klassen von Rechtecken eingeschlossen. Während diese Methode schneller bei der Klassifizierung eines Farbwertes ist, werden aber die Bedeutungen der Achsen des Farbraums unter Umständen nicht ausreichend berücksichtigt. Gleiche Farben befinden sich im RGB Raum schließlich auf einer Diagonalen und können nicht von Rechtecken umfaßt werden. Diese Technik setzt also die Verwendung eines geeigneten Farbraumes voraus.

Außerdem können auch statistische Methoden verwendet werden. Eine Möglichkeit ist es z.B., die Wahrscheinlichkeitsverteilung (``Pixel gehört zum Vordergrund'') für jeden Kanal im Speicher zu behalten. Die Wahrscheinlichkeitsverteilung kann aus Beispieldaten direkt berechnet werden.

Bruce entscheidet sich nach dieser Betrachtung aufgrund von Performance- und Speicheraspekten für eine raffinierte Version der multidimensionalen konstanten Schwellwerte. Seine Methode verwendet Rechtecke, die durch Projektion von Markierungen an den Achsen aufgespannt werden. Ein Farbwert der Dimension kann in logischen Verknüpfungen zu mehreren von 32 überlappenden Farbklassen zugeordnet werden. Durch die Verwendung der Projektion müssen nicht ( sei hier die Anzahl der Intensitätsquanten), sondern nur Werte im Speicher behalten werden. Bruce legt sich in seiner Arbeit auf den YUV Farbraum fest [2]. Bruce stellt in seinen Beispielen ad hoc Schwellwerte bereit, ein Verfahren zum automatischen Kalibrieren wird nicht bereitgestellt. Durch die Festlegung auf Rechtecke im YUV Farbraum werden die Trainingsmöglichkeiten eingeschränkt -- beliebige Klassengrenzen sind nicht möglich.

Diese Arbeit macht einen anderen Vorschlag. Nachdem der Speicherverbrauch heutzutage auch bei Embedded Systems kein ernsthaftes Argument mehr ist, bietet die Verwendung von Lookup-Tabellen die allgemeinste und schnellste Lösung. Im Falle des Computer-Sehens stellt inzwischen wohl immer die Rechenzeit und nicht die Speicherkapazität die leistungsbegrenzende Ressource dar. Lookup-Tabellen verlagern das eigentliche Problem der Farbsegmentierung, das Aufteilen des Farbraumes in Farbklassen aus der Segmentierungschicht hinaus. Das Problem ist nun, die Lookup-Tabelle vorzubereiten.

Eine Lookup-Tabelle speichert alle Funktionswerte einer beliebigen diskreten Funktion

			(16)

(17)

(18)

(19)

Die vorliegende Implementierung verwendet Lookup-Tabellen variabler Größe. Dem Anwender steht es frei, den gesamten Farbraum zu kodieren oder eine Quantisierung, realisiert durch schnelle Shift-Operationen, vorzunehmen. Die Kodierung des gesamten RGB-Farbraumes bei einer Farbtiefe von 24 bit (True Color) benötigt zum Beispiel Byte bei 256 disjunkten Farbklassen. Die bibliothekseigenen Beispielprogramme verwenden dagegen nur 6 Bit, also 64 Quanten pro Kanal ohne Qualitätsverlust der Segmentierung. Damit werden nur noch Byte, also ca. 256KB benötigt. Im Vergleich zum Speicherbedarf der zu segmentierenden Bilder in voller Auflösung und Farbtiefe (640x480x3) von ca. 1 MB ist die Lookup-Tabelle nicht mehr so entscheidend. Eine weitere Reduktion ist bei den meisten Anwendungen möglich.

Die implementierten Lookup-Tabellen unterstützen nur disjunkte Farbklassen. Die Verwendung überlappender Farbklassen erscheint nicht zwingend notwendig; es muß an einer späteren Stelle dann doch eine Entscheidung zugunsten einer Region vollzogen werden. Kein Pixel kann schließlich zu zwei Flächen gleichzeitig gehören, es sei denn, er ist ein Randpixel und fällt auf eine Objektkante. Werden aber doch überlappende Farbklassen benötigt, stellt ihre Aufnahme, wie oben erwähnt, kein größeres Problem dar.

Aus Speicherzugriffsgründen kann es von Vorteil sein, für die einzelnen Einträge der Lookup-Tabelle Integer anstelle von Bytes zu verwenden. In der vorliegenden Bibliothek wird standardmäßig die speichersparende Variante benutzt. Die Tabellen sind als Template realisiert, dessen Argument die Quantisierung in Form eines Shift-Wertes von Null bis 7 ist:

template<int SHIFT>
class CLookUpTable 
  : public CPixelDecisionStrategy {
public:
  CLookUpTable();
   
  virtual unsigned char& 
    lookup(int r, int g, int b);
  virtual unsigned char& 
    lookup(const RGBValue& rgb);
  virtual const unsigned char& 
    lookup(const RGBValue& rgb) const;
  virtual const unsigned char& 
    lookup(int r, int g, int b) const;
    
  unsigned int getSize() const;
  int getShift() const;
  virtual int getNumberOfClasses() const;
  virtual void setNumberOfClasses(int numC);
    
protected:
  unsigned char 
    table[256>>SHIFT][256>>SHIFT][256>>SHIFT];
  unsigned int table_size;
  int nClass;
};

Nachdem die Lookup-Tabellen vorbereitet wurden, gilt es, während der eigentlichen Segmentierung eines Bildes nur den Farbwert eines jeden Pixels in der Lookup-Tabelle nachzuschlagen:

(20)

RGBValue* imageBuf = image->getBuffer();
int* regionsBuf = regions->getBuffer(); 

for (int y=0; y < image->getHeight(); ++y)
  for (int x=0; 
       x < image->getWidth(); 
       ++x, ++imageBuf, ++regionsBuf)
    *regionsBuf = lut->lookup(imageBuf->r, 
                              imageBuf->g, 
                              imageBuf->b);

Im Vergleich zu der von Bruce entwickelten Segmentierungschicht in CMVision ist diese Implementierung in realen Umgebungen etwas (ca. ) langsamer (Tabelle 2.1), obwohl sie bei einfarbigen Bildern schneller ist. Dies liegt wahrscheinlich an Cachingvorteilen, die erst bei häufig wechselnden Farbwerten zum Tragen kommen. Im Falle der zufällig gefüllten Bilder wiederholen sich die nachzuschlagenden Farbwerte nur sehr selten und ihre Klassifizierungen müssen daher erst aus dem langsameren Hauptspeicher geholt werden. Da CMVision jeden Kanal einzeln nachschlägt, befindet sich der Eintrag wesentlich häufiger im schnelleren Zwischenspeicher.

In der Tabelle 2.1 kann man ablesen, daß die hier implementierte schnelle Segmentierung selbst im schlimmsten Fall der Zufallsbilder noch eine Framerate von über 25 Hz erzielt. In realen Umgebungen wird auf einem aktuellen 800 MHz Prozessor eine Framerate von über 60 Hz erreicht. Hier wird also bei leichter Geschwindigkeitseindbuße gegenüber CMVision eine wesentlich größere Flexibilität bei den verwendeten Segmentierungs- und Kalibrierungsverfahren erzielt.

Abbildung 2.6: Verschiedene Anaylsestufen eines Einzelbildes (oben links): Visualisierungen der Segmentierung (oben rechts), der in den Kettenkodes kodierten Umrisse (unten links) und der erkannten Objekte mit Position und Orientierung (unten rechts).

• Regionenkodierung
• Objekterkennung
• Objektgeschichte
  • Kostenfunktionen
• Ausgabe
• Fassade