Evolutionäre Bildverarbeitung

Das visuelle System des Menschen hat eine beachtliche Leistungsfähigkeit erreicht. Im Bereich der maschinellen Bildverarbeitung wurden in den letzten Jahren zwar große Fortschritte erzielt, dennoch sind wir weit davon entfernt, ein künstliches visuelles System aufzubauen, das ähnlich leistungsfähig ist, wie das menschliche System. Da das visuelle System letztlich ein Produkt der natürlichen Evolution ist, ist es sinnvoll, sich einerseits mit dem biologischen Vorbild und andererseits mit dem Prozess zu beschäftigen, der dieses erzeugt hat.DieEvolutionkann auf einem Rechner simuliert werden. So können wir versuchen, ein vergleichbar leistungsfähiges System aufzubauen. Der Ansatz, Probleme aus dem Bereich der maschinellen Bildverarbeitung mithilfe der simulierten Evolution zu lösen,wird als evolutionäre Bildverarbeitung bezeichnet (siehe Abb. 1).

Die wesentlichen Merkmale der natürlichen Evolution sind Reproduktion, Variation und Selektion. Aus einer Population von Individuen werden geeignete Individuen selektiert. Hierbei kommt das Darwin'sche Prinzip "Survival of the Fittest" zum Einsatz. Nur den besten Individuen ist es möglich, Nachkommen zu produzieren. In der Natur hängt die Auswahl geeigneter Individuen sowohl von der Zusammensetzung der Population, d.h. von den anderen Individuen, ab, als auch von der Umgebung. Die Zahl der Nachkommen eines Individuums während seines Lebens ist die Fitness des Individuums. Das Darwin’sche Prinzip können wir nutzen, um technische Optimierungsprobleme zu lösen. Wie in der Natur arbeiten wir mit einer Population von Individuen. Jedes Individuumstellt eine mehr oder weniger gute Lösung unseres Optimierungsproblems dar.Wir dekodieren das genetische Material des Individuums, um eine Lösung, z.B. optimale Parametereinstellungen für ein Optimierungsproblem, zu erhalten.Wie gut ein Individuum das gegebene Problem löst, wird durch eine Fitnessfunktion beschrieben, die durch das Problem defniert ist. Geeignete Individuen werden aus der Population anhand ihrer Fitness ausgewählt. Dabei wird darauf geachtet, dass überdurchschnittlich gute Individuen stärker ausgewählt werden als Individuen mit einer unterdurchschnittlichen Fitness. Auf die ausgewählten Individuen wenden wir in Anlehnung an die Natur eine Reihe von genetischen Operatoren an. Bei Anwendung eines Crossoveroperators wird das genetische Material zweier oder mehrerer Individuen miteinander kombiniert. Bei Anwendung eines Mutationsoperators wird das das genetischeMaterial leicht variiert. Die so produzierten Nachkommen werden in eine neue Population integriert. Diese Population wird zur nächsten Generation der Individuen. Wir iterieren diesen Prozess (Selektion, Reproduktion und Variation) solange, bis ein Abbruchkriterium erfüllt ist, z.B. bis eine maximale Zahl an Generationen erzeugt wurde. Derartige Verfahren werden unter dem Oberbegriff evolutionäre Algorithmen [10] zusammengefasst. Der Ablauf eines evolutionären Algorithmus ist in Abb. 1 dargestellt.

Es existieren unterschiedliche Ausprägungen evolutionärer Algorithmen, die sich imWesentlichen in der Repräsentation der Individuen unterscheiden. Bei den genetischen Algorithmen wird meist mit einer binären Repräsentation der Individuen gearbeitet. Bei den sog. Evolutionsstrategien werden Vektoren aus Fließkommazahlen optimiert. Diese Verfahren eignen sich für Probleme der Bildverarbeitung, bei denen lediglich eine Reihe von Parametern, z.B. von Bildverarbeitungsoperatoren, optimiert werdenmüssen. Als Beispiel für eine Parameteroptimierung schauen wir uns an, wie wir mithilfe einer Evolutionsstrategie die Absorptionscharakteristik eines optischen Systems anhand eines Kalibrierungsbildes bestimmen können [2]. Zunächst nehmen wir mit dem optischen System, bestehend aus Optik und digitalem Sensor, ein Foto eines Kalibrierungsbildes auf. Das Foto besteht aus mehreren farbigen Flächen, deren Reflektionseigenschaften im Bereich des sichtbaren Spektrums bekannt sind. Jedes Individuum unserer Population beschreibt die Absorptionscharakteristik der drei Sensoren (Rot, Grün und Blau) des digitalen Sensors. Um die Fitness eines Individuums zu bestimmen, dekodieren wir das genetischeMaterial. Wir erhalten die Absorptionscharakteristik eines durch das Individuum repräsentierten Sensors.Wir simulieren die Absorption des Lichts durch den Sensor, das vom Kalibrierungsbild re.ektiertwurde. Je nach der Qualität des Individuums erhalten wir ein Bild, das dem Foto des Kalibrierungsbildes mehr oder weniger ähnlich ist. Je ähnlicher das durch das Individuum erstellte Bild zu dem Foto des Kalibrierungsbildes ist, desto höher die Fitness des Individuums. Durch die Evolution werden nun solange die Individuen, d.h. die Absorptionscharakteristik des Sensors, variiert, bis ein Individuum gefunden wird, das die Absorptionscharakteristik des optischen Systems beschreibt.

Bei vielen Problemen der maschinellen Bildverarbeitung ist nicht bekannt,wie wir welche Operatoren auf ein Bild anwenden müssen, um ein gewünschtes Ergebnis zu erhalten. Der Anwender muss zur Lösung des Problems oft eine Folge von Operatoren zusammenstellen, die das gegebene Problem löst. Er muss also ein Programm schreiben, das aus einer Sequenz von Bildbearbeitungsoperatoren besteht. Zur Lösung derartiger Probleme ist besonders der Bereich der genetischen Programmierung relevant [7]. Im Bereich der genetischen Programmierung wird versucht,mithilfe der simulierten Evolution automatisch ein Computerprogramm zu .nden, das ein gegebenes Problem löst. Bei der Baumbasierten genetischen Programmierung werden Baumstrukturen evolviert, die den von Compilern generierten Parse-Bäumen entsprechen. Jedes Individuum besteht aus einem oder auch mehreren Bäumen. Um die genetische Programmierung auf ein Problem der Bildverarbeitung anzuwenden, muss de.niert werden, aus welchen inneren und äußeren Knoten ein Baum aufgebaut werden kann. Die inneren Knoten werden als elementare Funktionen, die äußeren Knoten werden als Terminalsymbole bezeichnet. Als elementare Funktionen können z.B. Operatoren de.niert werden, die ein oder mehrere Eingabebilder in ein anderes Bild transformieren, z.B. Addition zweier Bilder, Anwendung eines Kantendetektors, einer morphologischen Operation oder eines Schwellwertoperators auf ein Bild (siehe Abb. 2).

Auch bei der genetischen Programmierung werden die Individuen durch Crossover und Mutation variiert. Bei einer Mutationsoperation wird ein Individuum aus der Population ausgewählt und dann ein Teilbaum dieses Individuums zufällig neu erzeugt. Bei einem Crossover werden zunächst zwei Individuen aus der Population ausgewählt. Aus jedem Individuum wird ein Teilbaum ausgewählt und diese zwischen den Individuen ausgetauscht. Auf dieseWeise wandern evtl. relevante Programmstücke von einem Individuum zum anderen bzw. werden dort mit anderen Programmstücken kombiniert. Die elementaren Funktionen sind meist so aufgebaut, dass sie die Ausgabe der anderen elementaren Funktionen als Eingabe verarbeiten können. Auf dieseWeise entsteht bei einer Rekombination des genetischen Materials immer ein gültiger Baum als Nachkomme. Es ist jedoch auch möglich, mit elementaren Funktionen zu arbeiten, die nur auf bestimmten Datentypen arbeiten können. In diesem Fall muss bei der Anwendung der genetischen Operatoren darauf geachtetwerden, dass nur gültige Individuen erzeugt werden.

Eine der ersten Arbeiten im Bereich der evolutionären Bildverarbeitung wurde von Lohmann [5] vorgelegt. Lohmann evolviertemit einer geschachtelten Evolutionsstrategie Filter, um die in einem Bild Vorhandenen Objekte zu zählen. Der evolvierte Filter berechnet die Eulerzahl des Bildes. Johnson et al. [4] evolvierten mit der genetischen Programmierung komplexe visuelle Routinen, die die Position der linken oder rechten Hand aus einem Bild, das die Silhouette einer Person zeigt, extrahieren. Treptow und Zell [8] kombinierten einen evolutionären Algorithmus mit dem Adaboost-Verfahren, um Bilder, die Gesichter zeigen, von Bildern zu unterscheiden, die keine Gesichter enthalten. Mithilfe des evolutionären Algorithmus wurde nach optimalen Filtern gesucht, die an Haar-Wavelets angelehnt sind. Heinemann et al. [3] setzten einen evolutionären Algorithmus im Bereich des "RoboCups" ein. Beim RoboCup ist das Spielfeld standardisiert und die Roboter müssen innerhalb des Spielfeldes lokalisiert werden. Die von Heinemann et al. verwendeten Roboter sind mit einer omnidirektionalen Kamera ausgestattet. Der evolutionäre Algorithmus optimierte eine Abbildung, die das vom Roboter aufgenommene Bild entzerrt und somit auf Weltkoordinaten transformiert. Auf diese Weise ist der Roboter in der Lage, die Kamera erneut zu kalibrieren, sofern dies nach einer Wartung oder nach dem Transport der Roboter notwendig sein sollte. Anhand der simulierten Evolution kann auch untersucht werden, wie verschiedene visuelle Fähigkeiten entstanden sein könnten. Ein menschlicher Betrachter ist z.B. in der Lage, die Farbe von Objekten unabhängig von der Farbe der Lichtquelle, die diese beleuchtet, korrekt einzuschätzen. Diese Fähigkeit wird als Farbkonstanz bezeichnet. Mithilfe der genetischen Programmierung ist es gelungen, diese Fähigkeit in einem simulierten, parallelen, visuellen System zu evolvieren [1]. Ferner kann mit der evolutionären Bildverarbeitung untersucht werden, wie sich einfache Operatoren zu komplexen visuellen Operatoren, z.B. zur Merkmalsextraktion zusammensetzen lassen [9].

Die evolutionäre Bildverarbeitung kann in vielen unterschiedlichen Bereichen von der Verarbeitung medizinischer Bilddaten bis hin zu Vision-Systemen für autonome mobile Service- Roboter eingesetzt werden. Betrachten wir ein Beispiel aus dem Bereich Objekterkennung. Wenn wir die evolutionäre Bildverarbeitung verwenden wollen, um einen Algorithmus zu generieren, der ein bestimmtes Objekt extrahiert, so würden wir zunächst Experten in einer Reihe von Bildern die zu extrahierenden Objekte markieren lassen. Dem evolutionären Algorithmus wird dann ein Teil der Bilder, zusammen mit Bildern, die das Objekt nicht enthalten, übergeben. Als Fitnessfunktion wird ein Maß definiert, das beschreibt, wie ähnlich die Ausgabe des Individuums, d.h. des evolvierten Algorithmus, zu der Markierung durch die Experten ist. Mithilfe der simulierten Evolution wird nun versucht, einen Algorithmus zu finden, der die gleiche Ausgabe wie die der Experten liefert. Nachdem ein geeigneter Algorithmus gefunden wurde, wird dieser Algorithmus zur Validierung auf den restlichen Teil der Bilder angewandt und mit den Expertendaten verglichen, um zu überprüfen, ob der Algorithmus allgemeingültig ist und auch unbekannte Daten korrekt verarbeitet. Dieses Prinzip kann auf beliebige zu erkennende Objekte angewandt werden.

Wir können evolutionäre Algorithmen immer dann anwenden, wenn wir in der Lage sind, zu sagen, ob ein Algorithmus besser bei der Lösung des gegebenen Problems ist als ein anderer Algorithmus. Die Evolution von Algorithmen für die Bildverarbeitung ist derzeit noch sehr aufwändig, was die erforderliche Rechenzeit anbelangt. Jedes Individuum verarbeitet ein Bild durch Anwendung eines oder mehrerer Bildverarbeitungsoperatoren. Die Rechenzeit, die für die genetischen Operatoren benötigt wird, kann dagegen vernachlässigt werden. Daher ist die erforderliche Rechenzeit grob durch die Zeit gegeben, die wir für die Bewertung eines Individuums benötigen, multipliziert mit der Größe der Population, multipliziert mit der Zahl der Generationen, die wir bewerten. Simulationszeiten von mehreren Tagen bis hin zu ein oder zwei Wochen sind dabei keine Seltenheit. In Zukunft könnten Verfahren der evolutionären Bildverarbeitung eingesetzt werden, um adaptive Systeme aufzubauen, die sich an ihre jeweilige Umgebung anpassen und unter schwierigen Lichtverhältnissen bzw. auch mit veränderten Lichtverhältnissen weiterhin funktionieren.

Der erste Workshop zur evolutionären Bild- und Signalverarbeitung fand im Jahr 1999 in Göteborg, Schweden, statt und wird seither jährlich unter der Leitung von Stefano Cagnoni, University of Parma, Italien, organisiert. Im Jahr 2008 wird dieser Workshop bereits zum elften Mal abgehalten. Er findet in Neapel, Italien, im Rahmen der EvoStar- Tagung (www.evostar.org) statt, die Konferenzen zur genetischen Programmierung, zu evolutionären Algorithmen zur kombinatorischen Optimierung sowie zur Bioinformatik umfasst. Im vergangenen Jahr wurden auf der Tagung in Valencia, Spanien, unter anderem Arbeiten aus den Gebieten Objekterkennung, Bildregistrierung, Gesichtserkennung, Merkmalsextraktion, Bildsegmentierung, Evolution von Filtern zur Erkennung von Defekten bei der Papierproduktion, Reduktion von Rauschen, Bildkompression, Analyse von Ultraschallbildern und 3D-Modellierung im Bereich der forensischen Identifizierung vorgestellt. Weitere Arbeiten aus dem Bereich evolutionäre Bildverarbeitung wurden vor kurzem in einer Sonderausgabe der Zeitschrift Pattern Recognition Letters [6] zusammengefasst. Dort finden sich Artikel zur Evolution eines visuellen Sonars, zur Evolution von Farbkonstanz, zur Bildregistrierung, Bildsegmentierung, Objektklassifizierung bzw. Objekterkennung, zur Erkennung von Gesichtsausdrücken sowie zur Platzierung von Kameras. Eine weitere Sonderausgabe zum Thema evolutionäre Bildverarbeitung wird in der Zeitschrift Evolutionary Computation, MIT Press, erscheinen.

1. Ebner M (2006) Evolving color constancy. Special Issue on Evolutionary Computer Vision and Image Understanding of Pattern Recognition Letters 27(11): 1220-1229

2. Ebner M (2007) Estimating the spectral sensitivity of a digital sensor using calibration targets. In: Proceedings of the Genetic and Evolutionary Computation Conference, July 7-11, 2007, London, England. ACM, New York, pp 642-649

3. Heinemann P, Streichert F, Sehnke F, Zell A (2006) Automatic calibration of camera to world mapping in robocup using evolutionary algorithms. In: Proceedings of the IEEE International Congress on Evolutionary Computation, San Francisco, CA. IEEE, pp 1316-1323

4. Johnson MP, Maes P, Darrell T (1994) Evolving visual routines. In: Rodney A, Maes B, Maes P (eds) Artificial Life IV, Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, Cambridge, Massachusetts. The MIT Press, Cambridge, pp 198-209

5. Lohmann R (1991) Bionische Verfahren zur Entwicklung visueller Systeme. Dissertation, Technische Universität Berlin, Fachbereich 10 Verfahrenstechnik und Energietechnik

6. Pattern Recognition Letters 27(11), Sonderausgabe, Elsevier, 2006

7. Poli R (1996) Genetic programming for image analysis. In: Koza JR, Goldberg DE, Fogel DB, Riolo RL (eds) Genetic Programming 1996, Proceedings of the First Annual Conference, July 28-31, 1996, Stanford University. The MIT Press, Cambridge, pp 363-368

8. Treptow A, Zell A (2004) Combining adaboost learning and evolutionary search to select features for real-time object detection. In: Proceedings of the IEEE Congress on Evolutionary Computation, Portland, Oregon, vol 2. IEEE, pp 2107-2113

9. Trujillo L, Olague G (2006) Synthesis of interest point detectors through genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference 2006, Seattle, Washington, July 8-12. ACM, pp 887-894

10. Weicker K (2007) Evolutionäre Algorithmen. B.G. Teubner Verlag, Wiesbaden

Marc Ebner

Lehrstuhl für Informatik II, Universität Würzburg,

Am Hubland,

97074 Würzburg, Deutschland

E-Mail

© Springer-Verlag 2008