Bernhard Häussner

Bilder züchten

12.02.2009, 17:32

Mit freeSq gezüchtetes Bild

Der neueste Trend ist es ja anscheinend genetisch zu Programmieren (bzw. programmieren zu lassen). Der Webcomic xkcd greift das Thema auf und Roger Alsing zeigt wie es geht. Mir geht es natürlich nicht darum Algorithmen genetisch zu basteln, oder Bilder nach zu stellen, sondern ich wollte einfach mal den Computer etwas herumprobieren lassen. Da wir in Kunst zurzeit kubistische Bilder malen müssen, habe ich mir gedacht, so etwas könnte doch auch ein Computer hin bekommen. Der Computer malt also Rechtecke, und versucht sie so hin zu bekommen, dass es ungefähr aussieht, wie das Originalbild.

Da das Vorgehen ja ein bisschen an die Biologie angelehnt sein sollte, benutzte ich so etwas, wie einen genetischen Algorithmus. (Es ist also nicht der Algorithmus, der „genetisch“ erzeugt wurde). Im ersten Versuch habe ich dem Computer fünfhundert, zunächst gleiche, weiße Rechtecke auf schwarzem Hintergrund vorgesetzt. Der Computer hat dann immer ein zufälliges Rechteck genommen und zufällig platziert. Die neuen Bilder waren also so etwas wie Kinder. Dann hat eine Fitting-Funktion überprüft, ob sich die Ähnlichkeit zur Vorlage verbessert hat. Wenn ja, hat er dieses neue zufällige Rechteck gespeichert (also in die „DNA“) aufgenommen und dieses Kind als neues Mutterelement verwendet. Hat sich nichts verbessert, hat er einfach ein weiteres Kind erzeugt.

Die Fitting-Funktion

Ich habe ein kleines Python-Script gebastelt, dass die Übereinstimmung zweier Bilder ausrechnen kann. Da alles in schwarz-weiß passiert, geht es jeden Pixel durch und addiert jeweils die Differenz der Rotwerte. Je größer die Zahl ist, desto schlechter passt das Bild. Der Computer favorisiert also Kinder mit kleineren Werten.

Zweiter Algorithmus

Da der erste Algorithmus zwar mit nur 500 Rechtecken immer bessere Näherungen erreicht hat, aber zum Ende hin sehr viele Versuche brauchte um wieder ein besser angepasstes Kind zu finden habe ich einen zweiten Algorithmus gebastelt, der diese Probleme vermeiden soll:

Er züchtet aus einem Elternelement zunächst 500 Kinder. Die Zucht-Funktion fügt allerdings jetzt jeweils ein schwarzes oder weißes Rechteck hinzu, wodurch Fehler schneller korrigiert werden können. Beim alten Algorithmus konnte ein fehlerhaftes Rechteck ja nur verschoben werden, wenn es zufällig gewählt und zufällig richtiger platziert wurde. Die Zahl der Rechtecke entspricht also der der Generation.

Die 500 Kinder sind zunächst noch klein und es werden nur 25% der Pixel gerastert. Die Kinder werden dann mit einer kleineren Version der Vorlage verglichen, und nur die besten 10 werden erwachsen und dann in voller Größe vergleichen. Damit werden nicht mehr so viel Ressourcen (Rechenzeit) für grobe Fehlplatzierungen verschwendet. Aus den letzten 10 Kindern wird dann das, welches in groß am Besten passt, als neues Elternelement gewählt, aus dem wiederum 500 neue Kinder-Bilder gezüchtet werden. Die 499 anderen Kinder werden für immer gelöscht, sodass nun nur noch die Elternelemente (die mit Verbesserungen) konserviert werden um meine Felsplatte zu schonen. So werden immer weiter bessere Merkmale vererbt, bzw. alte Fehler in den Merkmalen korrigiert.

Die DNA

Genau wie bei der echten DNA auch, werden die Informationen so gespeichert, dass die Kinder „wachsen“ können, nämlich als SVG. PHP kann durch seine DOM-Funktionen die DNA leicht verändern und die Rechtecke sind in einem angemessenen Format gespeichert. Mit dem Programm rsvg lassen sich die Rechtecke auch schnell rastern in allen beliebigen Größen.

Das Ergebnis

Der erste Algorithmus „500“ hat nach 21 Stunden 50830 Generationen erzeugt und einen dabei Das Original recht nett angenähert. Ursprünglich habe ich geplant ein kleines Video daraus zu erstellen, doch selbst bei 30 fps wäre es etwa eine halbe Stunde lang, und man würde hauptsächlich die Fehlschläge sehen. Deshalb nur einige Auszüge aus dem Werdegang:

Der zweite Algorithmus „freeSq“ ist so gebaut, dass er ohne Probleme unterbrochen werden kann und deswegen werde ich ihn wohl noch deutlich länger laufen lassen. Aber nach den ersten rund 2 Stunden und 255 Generationen (127500 Versuchen) ist das Entsanden (links Vorlage):

Seltsamerweise ist es etwas zu klobig, es wirkt bisher nicht so fein, dafür ein bisschen komplexer, doch es wird sich zeigen, wie es nach einigen weiteren Generationen aussieht. Da das Ganze sehr viel Zufall beinhaltet, könnte bei einem weiteren Durchlauf auch ein völlig anderes Bild entstehen. Ich bin gespannt.

Übrigens: So sieht Evolution bei den Simpsons aus.

Kurze URL http://1-co.de/b/m. Post to twitter

Kommentare

keine





 
Χρόνογραφ
© 2008-2017 by Bernhard Häussner - Impressum - Login
Kurz-Link zu dieser Seite: http://1-co.de/b/m