Farben sortieren, dritter Teil

Vor Monaten hatte ich hier schon mal von meinem Hobby-Projekt berichtet, die Pixel eines Bildes algorithmisch nach ihrer Farbe zu sortieren. Eine Aufgabe, die auf den ersten Blick einfach erscheint, tatsächlich aber – wenn es perfekt sein soll – unmöglich ist, und die man auch näherungsweise nicht so einfach verwirklichen kann. Aber ein bisschen weiter bin ich mittlerweile schon gekommen.

Da Farben drei Dimensionen haben, seien es die additiven Primärfarben Rot, Grün und Blau, die subtraktiven Grundfarben Cyan, Magenta und Gelb, die Größen Farbton, Sättigung und Luminanz oder die Dimensionen in irgendeinem anderen Farbmodell, lassen sie sich auch nur in drei Dimensionen in eine systematische Ordnung bringen. In einem zweidimensionalen Bild kann das nicht funktionieren, oder jedenfalls nicht in einer allgemeingültigen Weise, die für jede Vorlage funktioniert. Aber man kann es immerhin so gut es geht versuchen …

Zuletzt hatte ich berichtet, wie mich nach einem ersten Fehlversuch zwei weitere Algorithmen A und B meinem Ziel zumindest etwas näher gebracht hatten. Nachdem DOCMA 113 fertig war, fand ich nun endlich genug Muße, meine App weiterzuentwickeln. Neben vielen Verbesserungen im Detail, die auch die Geschwindigkeit erhöhten, implementierte ich Algorithmus C – eine im Grunde geringfügige Variante von B, die allerdings zu völlig anderen Ergebnissen führte. Die Grundidee von Algorithmus B war, ein schwarzes Pixel als Keim im Zielbild zu platzieren und die Bildpixel dann eines nach dem anderen zu übertragen. Die unmittelbaren Nachbarn jedes bereits platzierten Pixels waren die als nächstes zu füllenden Leerstellen, die ich mit den verbliebenen Bildpixeln zu füllen versuchte.

Algorithmus B wählte zufällig eine der Leerstellen aus, ermittelte den Durchschnitt der Farben in dessen Umgebung, suchte das farblich ähnlichste verbliebene Bildpixel und platzierte dieses an der Leerstelle. Algorithmus C geht fast genauso vor, aber statt das gefundene Bildpixel stur an der Leerstelle einzufügen, für die es gedacht ist, geht er die Gesamtheit der Leerstellen durch, um zu sehen, ob es nicht woanders noch besser passt. Das klingt zunächst seltsam – als hätte man sich erst überlegt, was man dem einen Kind zu Weihnachten schenken könnte, nur um dann, nachdem man das Geschenk gekauft hat, herauszufinden, dass sich ein anderes Kind noch mehr darüber freuen würde. Intuitiv schien mir das dennoch eine aussichtsreiche Alternative zu sein, und so probierte ich diese Variante aus. Was ich mir davon versprach, kann ich gar nicht mehr sagen, aber jedenfalls führt der neue Algorithmus – wie erwähnt – zu ganz neuen Ergebnissen. Während Algorithmus B runde, irisartige Formen erzeugt, die mit ihren fließenden Farben an ein Aquarell erinnern, produziert Algorithmus C strengere Strukturen aus konzentrischen Quadraten:

Eine weitere Neuerung in meiner App ist die optionale Erzeugung eines Making-of-Movies, das die schrittweise Entstehung des Ergebnisbildes zeigt. Genau genommen werden dafür rund tausend Frames für die Zwischenschritte gespeichert, aus denen ich dann in Graphicconverter einen Film baue.

Der Algorithmus B bleibt weiter verfügbar, denn wenn er auch im Sinne meines eigentlichen Ziels einer Sortierung der Farben eines Bildes weniger erfolgreich ist, produziert er doch durchaus interessante Ergebnisse.

Ähnliches gilt für den Algorithmus A, der beim Sortieren fast gänzlich versagt (und überdies relativ langsam ist), dessen kristalline Strukturen aber ihren eigenen Reiz besitzen.

Die Verbesserungen, die ich an der App vorgenommen habe, betreffen auch den Vergleich von Farben, der für alle drei Algorithmen essentiell ist. Die wesentlichen Vergleichskriterien sind jetzt einerseits die Farbtöne (Hue) der beiden Farben, wofür diese in ein Vierfarbmodell mit den Grundfarben Rot, Gelb, Grün und Blau umgerechnet werden, die im Farbkreis um jeweils 90 Grad voneinander entfernt sind. Das zweite Kriterium ist der Helligkeitsunterschied. Die Gewichtung beider Faktoren hängt von der Luminanz der helleren der beiden Farben und der Sättigung der gesättigteren Farbe ab: Je größer das Produkt von Luminanz und Sättigung ist, desto stärker wird der Farbton-Unterschied gewichtet, während bei dunklen und/oder ungesättigten Farben der Faktor Luminanz dominiert.

Am Farbvergleich werde ich noch weiter arbeiten; außerdem könnte ein vierter Algorithmus hinzu kommen, in dem die Wahl der zu platzierenden Pixel mehr von den noch zu platzierenden Bildteilen als von den bereits platzierten getrieben wird. Meine erste Idee dazu hat sich allerdings als nicht gangbar erwiesen und mit einer weiteren Idee gibt es auch noch Probleme – schau’n wir mal.

Im DOCMAshop finden Sie alle Infos zum aktuellen Heft: Das ausführliche Inhaltsverzeichnis sowie einige Seiten als Kostprobe.