Evolutionäre Bildverarbeitung

Die evolutionäre Bildverarbeitung (EB) ist ein Teilgebiet der digitalen Bildverarbeitung. Zur Optimierung und Lösung verschiedener Problemstellungen der Bildverarbeitung werden evolutionäre Algorithmen (EA) eingesetzt. Die evolutionäre Bildverarbeitung stellt damit die Kombination aus evolutionärer Optimierung und digitaler Bildverarbeitung dar.

EA werden seit mehreren Jahrzehnten in der Informatik zur Optimierung verschiedener Problemstellungen eingesetzt. Die Anwendung in der Bildverarbeitung stellt hingegen noch ein recht junges Forschungsgebiet dar. Dies ist vorrangig auf die technologische Entwicklung der Computersysteme zurückzuführen, da die EB ein verhältnismäßig rechenintensives Verfahren darstellt.

Anwendungsgebiete

Rekonstruktion von Bildverarbeitungsalgorithmen

Problemstellung bei der Rekonstruktion eines Bildverarbeitungsalgorithmus

Durch die Anwendung verschiedener Operationen auf ein Bild entsteht durch die sequenzielle Abarbeitung eine Bildoperationskette. In Bildverarbeitungsprogrammen oder medizinischen sowie industriellen Anlagen, die mit visuellen Systemen arbeiten, sind oft Bildverarbeitungsverfahren enthalten, deren Funktionen nicht vollständig einsehbar sind. Wird ein Bild bearbeitet, entsteht neben dem Originalbild ein sogenanntes Ergebnisbild. Eine manuelle Rekonstruktion der Bildoperationskette, die zwischen Originalbild und Ergebnisbild liegt, ist in den meisten Fällen nicht möglich. In der evolutionären Bildverarbeitung wird ein EA so angepasst, dass die Operationskette automatisch rekonstruiert werden kann.

Optimierung von Bildverarbeitungsalgorithmen

Mithilfe der Rekonstruktion ist es möglich, verschiedene Bildverarbeitungsprobleme zu optimieren. Über eine Anpassung des EA können kürzere Bildoperationsketten gefunden werden. Durch das Auffinden von kürzeren Lösungswegen wird die Rechenzeit des Lösungsverfahrens der Problemstellung reduziert. Durch eine gezielte Gewichtung der Bildoperationen können zusätzlich leichtere Operationsketten gefunden werden, die eine kürzere Rechenzeit benötigen.

Anpassung des evolutionären Algorithmus

Gene und Individuen

Gene eines Individuums in der EB

Die Anpassung verschiedener Individuen ist für den Einsatz eines EA ein hinreichendes Kriterium. Die Informationen, die man aus einer Filterkette gewinnen kann, müssen entsprechend auf ein Individuum abgebildet werden. Ein Filter kann dabei ein Gen repräsentieren. Die genaue Reihenfolge der Filter, die die Kette beinhaltet, ist ein Merkmal, die die Eindeutigkeit ermöglicht. Somit kann die Reihenfolge einer Kette auf das Chromosom eines Individuums übertragen werden. Jedem Individuum kann damit eine Funktion zugewiesen werden, in der es die Reihenfolge entsprechend seiner Gene abarbeitet. Jedem Individuum steht das Originalbild der Problemstellung zur Verfügung. Aus seiner Funktion ergibt sich dann ein entsprechendes Ergebnisbild, mit dessen Hilfe die Fitness ermittelt werden kann. Die Größe eines Individuums kann dabei von 1 bis hin zur maximal festgelegten Größe variieren. Durch die Erzeugung vieler Individuen kann die Ansammlung in einer Population zusammengefasst werden.

Genetische Operatoren

Um Teilergebnisse weiterzuentwickeln und fortzuführen, sind genetische Anpassungen notwendig. Den erzeugten Individuen wird das Recht der Fortpflanzung zugesprochen, damit sie ihre Gene weitergeben können. Die Rekombination bestimmter Individuen erzeugt damit die passende Folgegeneration, in der die passenden Gene für die Problemstellung enthalten sind.

Rekombination

Rekombination bei der EB

Für die Rekombination zweier Individuen bietet sich ein sogenannter One-Point-Crossover an. Bei diesem Crossover wird mit Hilfe eines Kreuzungspunktes die Hälfte der Vatergene sowie die Hälfte der Muttergene auf ein neues Individuum übertragen. Vor der Rekombination muss zunächst die Länge des Kindchromosoms (Länge des Kindes) festgelegt werden. Dies geschieht über die Längen der Chromosomen von Vater und Mutter. Die Anwendung eines One-Point-Crossovers auf zwei Elternteile lässt zwei Kinder (sogenannte Genome) entstehen. Da aber nur ein Kind aus der Rekombination entstehen soll, wird aus den beiden Genomen per Zufall das Kind bestimmt. Die beiden Genome erben sich dabei entsprechend aus den Hälften der jeweiligen Elterngene. Die Genome unterscheiden sich in der Kombination der beiden Hälften.

Mutation

Mutation bei der EB

Mithilfe der Mutation kann die Vielfalt innerhalb der Population erhalten und erhöht werden. Die Mutation geschieht durch das Ersetzen eines Filters innerhalb der Kette gegen einen zufällig gewählten Filter. Die Mutation wird nach der Rekombination durchgeführt und nur auf einen Teil der Population angewandt. Mithilfe einer Zufallsvariable wird eine gewisse Anzahl an Kindindividuen nach der Rekombination durch die Mutation verändert.

Eigenschaften der evolutionären Bildverarbeitung

Vorteile

Eine Rekonstruktion von Bildverarbeitungsalgorithmen ist mithilfe der EB möglich. Der EA führt gezielt gute Teilergebnisse fort und findet in den meisten Fällen die Operationskette schneller als bei einer manuellen Rekonstruktion. Durch das Auffinden von Algorithmen, die weniger rechenintensiv sind, können verschiedene Lösungsansätze optimiert werden.

Nachteile

EA besitzen meist einen großen Rechenzeitbedarf. In Kombination mit Operatoren der Bildverarbeitung und abhängig von der Größe der Bilddaten, wird der Rechenzeitbedarf zusätzlich erhöht. Eine Verbesserung der Laufzeit kann mithilfe der parallelen Programmierung erreicht werden. Zudem ist eine Optimierung über Grafikprozessoren möglich.

Literatur

• Roman Kalkreuth, Jörg Krone, Michael Schneider: Automatische Generierung von Bildoperationsketten mittels genetischer Programmierung, Fachhochschule Südwestfalen, Institut für Computer Vision & Computational Intelligence, in: Proceedings 22. Workshop Computational Intelligence, Seite 325–340, 2012, ISBN 978-3-86644-917-6.
• Marc Ebener: Evolutionäre Bildverarbeitung, Gesellschaft für Informatik e. V., 2008.
• Marc Ebner: Color Constancy, John Wiley & Sons, 2007, ISBN 0-470-05829-3.
• Marc Ebner: Evolving color constancy. Special Issue on Evolutionary Computer Vision and Image Understanding of Pattern Recognition Letters, 2006.
• Christoph Bullmann: Evolutionäre Bildverarbeitung (PDF), HTWK Leipzig, Fachbereich Mathematik, Informatik und Naturwissenschaften, 2009.
• Jun Ando, Tomoharu Nagao: Fast Evolutionary Image Processing Using Multi-GPUs Yokohama National University, 2009, ISBN 978-953-307-026-1.

Weblinks

• Institut für Computer Vision & Computational Intelligence der Fachhochschule Südwestfalen