Für den Wettbewerb IARC 1998-2000 sollten die teilnehmenden Flugroboter verschiedene Dinge aus der Luft finden. Dazu gehörten schwarze Tonnen, deren Kennzeichnung erkannt werden sollte, die aus den internationalen Symbolen für explosiv, biologische Gefahrenstoffe und radioaktiv bestanden. Außerdem sollten Menschen gefunden werden, die durch Puppen dargestellt wurden. In dem simulierten Katastrophenszenario gab es sogenannte Opfer (unbewegliche Puppen) und Überlebende (sich bewegende Puppen), die ebenfalls unterschieden werden sollten.

MARVIN verfügte über eine handelsübliche digitale Fotokamera, deren Bilder alle 5 s zur Bodenstation gefunkt wurden. Im Folgenden werden zwei der verwendeten Menschenerkennungen beschrieben.

Die Algorithmen werden anhand von Beispielbildern aus dem Wettbewerb illustriert. Die hier präsentierten Luftaufnahmen sind zwar überdurchschnittlich leicht zu analysieren, allerdings läßt sich so die Erkennung anschaulich darstellen.

Bei der Konturerkennung wird versucht, das aufgenommene Foto geeignet zu segmentieren und in den gefundenen Kanten die Umrisse eines Menschen zu finden. Die Segmentierung und die Kantenerkennung in Bildern können durch eine Reihe verschiedener Ansätze erfolgen.

Die nebenstehende Abbildung zeigt eine der besonders übersichtlichen Luftaufnahmen, wie sie von der Kamera an Bord von MARVIN aufgenommen wurden. Die Extremitäten der Puppe sind gut erkennbar, sogar die Arme befinden sich neben dem Körper. Die Farbe der Hose ist allerdings dem Untergrund sehr ähnlich.

Vorverarbeitung
Der erste Verarbeitungsschritt ist ein Tiefpaßfilter zur Reduktion des Grundrauschens. Um eine schnelle Berechenbarkeit zu erreichen, wurde ein 2D Gauß-Tiefpaß gewählt. Für die Aufnahmequalität der verwendeten Kamera und der größe der interessanten Strukturen (abhängig von der Flughöhe), wurde ein Filterkern mit einer Größe von 5x5 Pixeln gewählt.

Die Berechnung erfolgt hierbei in zwei Schritten. Der symmetrische 2D Filterkern wird in zwei einzelne Vektoren (1 4 6 4 1) aufgeteilt, einer horizontal und einer vertikal. Diese werden dann nacheinander auf das Bild angewendet. Hierdurch steigt der Aufwand mit der Filterkerngröße nicht mehr quadratisch, sondern nur noch linear. Der verwendete Kern mit Größe 5 kann außerdem durch zweimaliges Anwenden des Kerns (1 2 1) realisiert werden.

Segmentierung
Die entscheidende Frage bei Objekterkennungen ist die Segmentierung der Objekte vom Hintergrund. In dieser Arbeit hat sich als besonders effektiv die Suche nach seltenen Farben herausgestellt. Damit sind Farben gemeint, die im Gesamtbild kaum vorkommen und damit wahrscheinlich zu einem kleineren Objekt gehören.

Es wird also für jeden der 3 Farbkanäle ein Histogramm gebildet und in einem zweiten Durchlauf durch das Bild jedem Pixel ein Grauwert entsprechend der Häufigkeit des jeweiligen Farbwertes im Histogramm zugeordnet. Anschließend werden die drei Farbebenen zusammengefaßt, indem jeweils die kleinste Häufigkeit übernommen wird. Im Bild rechts ist das Ergebnis zu sehen. Je dunkler ein Pixel dargestellt ist, desto seltener ist die Farbe im Gesamtbild vertreten.

Anshließend kann mit einem einfachen Schwellenwert ein Schwarzweißbild gebildet werden. Hier stellen die weißen Pixel Bildelemente dar, die wegen ihrer besonderen Farbe wahrscheinlich zu einem Objekt gehören.

Interessanterweise kann so sogar die graue Hose segmentiert werden, obwohl sie dem Untergrund farblich sehr ähnlich ist. Auch der Schotter in der linken Bildhälfte wird erfolgreich ausgeblendet, obwohl er für übliche Kantenverfolger ein Problem darstellt.

Im nächsten Schritt sollen die von der Größe her interessanten Gebiete gefunden werden. Die kleinen Flecken und Linien z.B. durch den Schlauch im Bild können schon aufgund ihrer Größe keinen Menschen darstellen. Die Größe läßt sich schnell mittels eines besonders aggressiven Weichzeichners aussortieren. Das segmentierte Bild wird hierfür mit einem quadratischen Weichzeichner mit einer Kantenlänge von etwa 75 cm (umgerechnet auf Pixel im Bild) bearbeitet. Das Ergebnis ist nebenstehend zu sehen. Diese Operation kann sehr schnell ausgeführt werden, indem wieder die erwähnte Vektorzerlegung angewendet wird. Außerdem muß beim "über das Bild schieben" des Filterkerns immer nur ein Pixel addiert und einer subtrahiert werden.

Wird anschließend wieder ein Schwellenwert angewendet (auf 50 % Helligkeit), so bleiben nur noch Objekte übrig, die groß genug sind. Mittels eines Konturverfolgers wird um die noch übrigen "Flecken" jeweils eine Kontur gelegt. Ist diese zu lang, handelt es sich um ein für einen Menschen zu großes Objekt.

Mit dieser in Listenform gspeicherten Kontur können nun noch weitere Operationen sehr effizient durchgeführt werden. Der Schwerpunkt des Objekts wird durch den arithmetischen Mittelwert der Kontur bestimmt. Für eine spätere Verwendung wird außerdem die Ausrichtung der Kontur als Winkel (0°...180°) bestimmt.

Da jetzt eine Liste von verbleibenden interessanten Objekten aufgestellt wurde, reduzieren sich alle weiteren Operationen nur noch auf die Positionen dieser Objekte im Bild.

Konturerkennung
Für die Konturerkennung wird das segmentierte Bild vor dem starken Weichzeichnen wiederverwendet. Mittels Konturverfolger werden die Umrisse der verbliebenen Objekte bestimmt. Zu kleine Konturen werden hierbei ignoriert.

Als nächstes muß nun in den gefundenen Konturen nach menschenähnlichen Umrissen gesucht werden. Hierfür ist eine Art Vorlage erforderlich, die beschreibt, was eine Menschenkontur ausmacht. Das zentrale Problem hierbei liegt in der großen Variabilität von Körperhaltungen. Jeder Arm und jedes Bein kann in viele verschiedene Positionen bewegt werden.

Um die Zahl der zu vergleichenden Prototypen klein zu halten, wird nach dem Rumpf mit Kopf sowie nach den Extremitäten einzeln gesucht. Für jedes Körperteil gibt es dabei mehrere Prototypen für die verschiedenen Positionen, wie beispielhaft für einen Arm nebenstehend abgebildet.

Um die Ähnlichkeit der gefundenen Konturen mit denen von Menschen zu bestimmen, wird die sogenannte Chamfer-Distanz genutzt. Hierbei wird die Kontur eines zu vergleichenden Prototypen über die im Bild gefundene gelegt. Nun wird für jeden Pixel des Prototypen der Abstand zum nächstgelegenen gefunden Konturpunkt bestimmt und aufsummiert. Je ähnlicher sich Prototyp und gefundene Kontur sind, desto kleiner ist also der Wert für die Chamfer-Distanz. Bei exakter Übereinstimmung ergibt sich der Wert 0.

Die Aufsummierung der Anstände kann recht leicht erfolgen, indem aus dem gefundenen Konturbild ein passendes Abstandsbild generiert wird, wie nebenstehend dargestellt. In jedem Pixel ist hierin der Abstand zum nächstgelegenen Konturpunk vermerkt. Für einen Prototypen kann nun die Chamfer-Distanz einfach bestimmt werden, indem sämtliche zum Prototypen gehörenden Pixelwerte aus diesem Bild aufsummiert werden. Da viele Prototypen vergleichen werden müssen, lohnt sich der Aufwand, ein solches Abstandsbild zu generieren.

Für den Vergleich der Prototypen mit dem Abstandsbild müssen die Konturen in Größe und Ausrichtung übereinstimmen. Hierfür wird die gefundene Kontur geeignet skaliert und gedreht. Die Skalierung kann aus der bekannten Flughöhe bestimmt werden. Die Rotation ergibt sich aus dem Winkel, der bei der Segmentierung bestimmt wurde. Da hierbei noch nicht klar ist, wo oben und unten ist, wird das Abstandsbild auch vertikal gespiegelt mit den Prototypen verglichen.

Einzelne gefundene Körperteile können nun mit geeigneten Punkten bewertet werden. Auch der Wert der Chamferdistanz kann als Wahrscheinlichkeit mit benutzt werden. Mittels geeignet gewählter Schwellenwerte wird so entschieden, ob eine menschliche Kontur erkannt wurde oder nicht. Wird zu unterschiedlichen Zeitpunkten an etwa derselben Stelle zweimal ein Mensch identifiziert, dessen Arm- oder Beinpositionen sich signifikant verändert haben, so handelt es sich offensichtlich um einen Überlebenden, da er sich bewegt hat. Auch diese Unterscheidung ist mit dem beschriebenen Ansatz möglich. Die Rechenzeit auf einem Pentium III mit 600 MHz beträgt etwa 4,5 s, liegt also unterhalb der geforderten 5 s. Hierfür sind vor allem die vielen Optimierungen der Algorithmen und der Einsatz von optimierten MMX Assembler-Routinen verantwortlich.

Eine weitere sehr viel einfachere Erkennung basiert auf der Auswertung der Farben im Bild. Ist z.B. bekannt daß sich in dem zu untersuchenden Katastrophengebiet viele uniformierte Arbeiter befinden, deren Kleidung eine bekannte Farbe aufweist, bietet es sich an, gezielt nach diesen uniformen zu suchen.

Für die Segmentierung werden hier nicht "seltene" Farben gesucht wie bei der Konturerkennung. Stattdessen werden die Abstände der Pixelfarben zu der gesuchten Farbe innerhalb eines geeigneten Farbraums bestimmt. Für eine bessere Unabhängigkeit von veränderlichen Beleuchtungsverhältnissen wird das RGB-Bild zunächst in den HSL-Farbraum konvertiert. Hier werden die Pixel durch die drei Werte Farbe (Hue), Sättigung (Saturation) und Helligkeit (Luminance) dargestellt.

Mittels Schwellenwert wird aus der Farbdifferenz zwischen den Bildpixeln und der gesuchten Farbe wieder ein segmentiertes Bild erzeugt. Dieses segmentierte Bild wird im Anschluß wieder stark weichgezeichnet, um mittels weiterem Schwellenwert zu kleine Objekte auszuschließen. Dieses Vorgehen ist dasselbe wie oben für die Segmentierung bei der Konturerkennung. Zu große Objekte werden mittels Konturverfolger erkannt und ausgeschlossen.

Die übrigen Objekte haben also die richtige Farbe und die richtige Größe, werden also als erkannt eingestuft.

Der gesamte Farberkennungsalgorithmus benötigt auf einem Pentium III mit 600 MHz unter 0,5 s. Im Wettbewerb hat er außerdem zu fast 100 % funktioniert. Lediglich eine Puppe wurde wegen zu verwaschener Farbe nicht erkannt. Die anderen wurden auf jeder Aufnahme zuverlässig identifiziert. Fehlerkennungen gab es keine.

Die einzelnen Schritte zur Bildauswertung werden mittels eines Skriptes beschrieben. Ein solches Skript kann eine vielzahl von Befehlen enthalten, sogar Schleifen und bedingte Verzweigungen wurden implementiert. Durch diese flexible Programmiermöglichkeit konnte z.B. die Farberkennung sehr schnell und leicht Programmiert werden, da fast alle notwendigen Funktionen schon für die Konturerkennung vorhanden war. Selbst die Prototypen werden über ein solches Skript generiert, indem z.B. der Konturverfolger auf gemalte Prototypen angewendet wird.

Das Skript wird vor der Ausführung vollständig eingelesen, so daß es zu keinem unnötigen wiederholten Rechenaufwand bei der Analyse des Skriptes kommt. Zuvor wird es außerdem vom gcc Präprozessor verarbeitet, so daß Kommentare, Makros und inkludierte Dateien möglich sind. Hier als Beispiel das Farberkennungs-Skript:

---------------------------------------------------------------------------------------------------- #include "macro.cxx"  //Einige vereinfachte Schreibweisen

InitMarvin(L0,L1,4);  //Initialisieren: L0=host, L1=path, 4=Visionnummer
OnErrorGoto("loop");  //Sollte ein Fehler auftreten, mit nächstem Bild fortfahren

//Schleife
Label("loop");
  L(2,3)=ReceiveMarvin();                //Auf neues Bild warten, L2=Bildauflösung Pixel/Meter, L3=Bildname
  P(0,1,2)=Load(RGB,L3,Detect);          //Bild Laden

  //Vorverarbeitung
  P3=GAUSS5(P0);                         //Tiefpaßfilter mit Filterkernbreite von 5
  P4=GAUSS5(P1);                         //(aus macro.cxx)
  P5=GAUSS5(P2);
  P(3,4,5)=RGBtoHSL(3,4,5);              //Farbraum wechseln
  P0=CmpHSL(3,4,5,238,6,70,255,40,185);  //Pixel hinreichend rot?

  //Nur Objekte mit richtiger Größe beachten
  L0=Calc((L2*.6));                      //Auflösung * 0,6 Meter
  P1=AVERAGE(P0,L0);
  P0=Between(P1,R.3,R1);                 //Zu kleine aussortieren
  L0=Calc((L2*2));                       //Auflösung * 2 Meter
  P1=Contour(P0,10,L0,1,3);              //Zu große aussortieren
  L4=ObjectMaximum(P1,20,-2);

  SendMarvin(L4);                        //Ergebnis senden
  L0=ContinueMarvin();                   //Programm fortsetzen?
Goto("loop",L0);

OffError();   //Fehlerbehandlung deaktivieren
EndMarvin();  //Kommunikation beenden
----------------------------------------------------------------------------------------------------

Es existieren viele Funktionen, die innerhalb eines solchen Skriptes aufgerufen werden können. Sie sind in einzelne Module unterteilt:

• aritlogic
  Einfache arithmetische bzw. logische Operationen auf Bildern
• colorsystem
  Umwandlung und Interpretation verschiedener Farbräume (RGB, HSL)
• filter
  Flexible Filtermasken, Farbdistanzberechnungen usw.
• inout
  Laden und Speichern von Bildern.
• chamfer
  Funktionen zur Arbeit mit Chamferdistanzen.
• other
  Alle sonstigen Funktionen.
• marvin
  Anbindung an das Gesamtsystem (Kommunikation).
• paint
  Malen von Linien, Rechtecken usw. zur Prototypengenerierung

Zur Beschleunigung der Programmausführung wurden einige Routinen optimiert. Die Zerlegung des 2D Filterkerns eines Gaußschen Weichzeichners in zwei Vektoren wurde schon erwähnt. Neben solchen algorithmischen Optimierungen wurden außerdem einige besonders wichtige bzw. aufwendige Routinen von Roland Stahn in Assembler geschrieben unter Benutzung von MMX Optimierungen:

• GAUSS3, GAUSS5
  Dies sind zwei Gaußsche Weichzeichner mit Kantenlänge 3 bzw. 5 Pixel.
• AVERAGE
  Dieses Filter berechnet den arithmetischen Mittelwert der Pixel in einer rechteckigen Nachbarschaft. Er stellt also auch einen Tiefpaß dar, aber mit variabler Fenstergröße.
• FREQUENCY
  Zum Finden der seltenen Farben, muß ein Histogramm des gesamten Bildes erstellt werden, das anschließend auf jedes Pixel angewendet werden muß.
• JIMPORT
  Laden eines Jpeg Bildes.