Das Mona Lisa Malproblem (Mona Lisa Painting Problem)

Roger Alsing hat nach meiner Kenntnis als erster das Problem formuliert, die Mona Lisa von Leonardo da Vinci unter Verwendung Genetischer Programmierung möglichst genau mit möglichst wenigen einfarbig gefüllten Polygonen nachzuzeichnen. Dabei sollen die Polygone zudem aus möglichst wenigen Punkten bestehen, also am besten aus maximal drei Punkten. Dieses Problem ist komplex, da es quasi unendlich viele Möglichkeiten für eine potentielle Lösung gibt. Die Varianzen sind gegeben durch die Form (Anzahl der Punkte, Koordinaten pro Punkt) und Füllfarbe der Polygone, deren Transparenz (Alpha-Komponente) sowie die Anzahl der verwendeten Polygone.

Im Javamagazin erscheint zum Mona Lisa Problem ein Artikel von mir, der die Herangehensweise zur Realisierung mit dem Open Source Java-Framework JGAP beschreibt (s.u.).

Im Internet sind diverse Lösungsansätze auf Basis genetischer Algorithmen und genetischer Programmierung kostenlos erhältlich:

Java-Version mit JGAP

Siehe auch die JGAP-Homepage. JGAP demonstriert die Umsetzung sowohl mit genetischen Algorithmen (Package examples.monalisa) als auch mit der genetischen Programmierung (Package examples.gp.monalisa).
Interessant ist hier die Verwendung des Frameworks, die einiges an Programmieraufwand einspart und weiter gehende Funktionalitäten direkt verfügbar macht. Die Implementierung des Beispiels hat zur Verbesserung der Evolutionseigenschaften von JGAP geführt.

Die Fitnessfunktion in der GP-Version arbeitet wie folgt:

• Der Fitnesswert drückt die Fehlerzahl der betrachteten generierten Lösung aus.

• Für jeden Pixel wird die Differenz des Farbwertes zwischen generiertem und Eingabebild errechnet. Dazu wird jede Farbkomponente (R, G, B) getrennt betrachtet. Die Differenzen werden pro Farbkomponente quadriert und aufaddiert, danach wird die Wurzel gezogen.

• Pixel, die im generierten Bild überhaupt nicht abgedeckt sind, also quasi leere Stellen, werden besonders negativ gewichtet.

• Pro verwendetem Polygon werden fünf Maluspunkte zum Ergebnis hinzugezählt. Fünf, weil in einer minimalen Kodierung pro Polygon ein Trenner erforderlich ist und weiterhin für die Füllfarbe des Polygons vier Komponenten angegeben werden müssen, nämlich R, G, B und Alpha (Transparenz)

• Pro  verwendetem Punkt werden zwei Maluspunkte geltend gemacht, je einer für die X- und einer für die Y-Koordinate.

Der Fortschritt der Evolution wird in Form einer Grafik dargestellt, die die Anzahl der Generationen mit der Fitness des besten generierten Bildes pro Generation gegenüberstellt. Die bis dato beste Lösung wird weiterhin als Grafik angezeigt.

Java-Version (Stand alone)

siehe Weblog-Eintrag

Flash-version

Interessanter Ansatz, auch wenn die Evolution anscheinend sehr langsame vonstatten geht.

Clojures

Etwas exotischer Ansatz, aber scheinbar effizient. Von derselben Person, die auch zur Java-Version von JGAP beigetragen hat.

Sonstiges

• Das Geheimnis des Lächelns der Mona Lisa

Copyright © 2006-2012 Dr.-Ing. Klaus Meffert. All rights reserved.