Farben sortieren, zweiter Teil

Über die Herausforderung, die Farbtöne eines Bildes zu sortieren, hatte ich hier jüngst berichtet. Inzwischen bin ich meinem Ziel näher gekommen, aber noch lange nicht dort angekommen.

Um es noch einmal zusammenzufassen: Mein Ziel war und ist, die Pixel in einem Bild so neu anzuordnen, dass sich die Pixel um so näher sind, je ähnlicher ihr Farbton ist. Klingt einfach, ist aber eine echte Herausforderung, da sich alle möglichen Farben nur in drei Dimensionen darstellen lassen, während es mir um ein zweidimensionales Bild geht.

Der erste Algorithmus, den ich zu diesem Zweck implementiert hatte, tat wie erwähnt nicht das Gewünschte. Ich wollte das Ausgangsbild Pixel für Pixel in ein neues Bild übertragen, und jedes weitere Pixel des Ausgangsbilds zwischen die ähnlichsten bereits platzierten Pixel setzen. Das klang logisch, zumindest für mich, aber als ich es ausprobierte, erkannte ich bald meinen Denkfehler: Sobald zwei Pixel über-, unter- oder nebeneinander angeordnet wurden, ordneten sich die weiteren entlang derselben Linie an. Der Algorithmus zog lange Fäden, statt das Bild in zwei Dimensionen wachsen zu lassen. Ein Wachstum in der Fläche konnte mein Verfahren leider nicht erzwingen.

Mein nächster Ansatz verzichtete darauf, einmal platzierte Pixel zu verschieben; die Idee war, das nach Farben sortierte Bild um einen Pixelkeim herum wachsen zu lassen, wobei jedes einmal gesetzte Pixel an seinem Platz blieb. Damit war jedoch ein Problem verbunden: Wenn Pixel einer Farbe platziert werden sollen, die schon einmal vorgekommen sind, werden die früher platzierten gleichfarbigen Pixel vielleicht nicht mehr zugänglich sein, weil sie inzwischen von andersfarbigen Pixeln umgeben sind. Dann entstehen mehrere isolierte Bereiche mit ähnlich gefärbten Pixeln, die nicht mehr zueinander finden. Um das zu verhindern, habe ich die Bildpixel zunächst nach ihrer Luminanz sortiert und sie dann nacheinander von dunkel nach hell platziert.

Die Ergebnisse fielen zwar besser als in den ersten Versuchen aus, aber abgesehen davon, dass noch immer nicht alle ähnlichen Farben zueinander fanden, rissen Löcher auf, die auch später nicht immer gefüllt wurden. Trotzdem habe ich dieses Verfahren als „Algorithmus A“ beibehalten und in drei Varianten implementiert, bei denen das Zielbild von der Mitte, der Mitte des oberen Bildrands oder der linken oberen Ecke aus wächst.

Übrigens gibt es noch ein weiteres Problem mit diesem Algorithmus: Er ist furchtbar langsam und braucht trotz aller Optimierungen auf meinem iMac mit M1-Prozessor manchmal mehrere Tage, um ein halbwegs hoch aufgelöstes Ergebnis zu berechnen. Da meine App ständig aktualisierte Zwischenschritte anzeigt (also die noch zu platzierenden Pixel des Ausgangsbilds und die bereits gesetzten Pixel im Zielbild), kann ich immerhin verfolgen, ich welche Richtung es geht, und offensichtliche Fehlversuche zügig abbrechen.

Für meinen Algorithmus B kehrte ich das Verfahren um: Statt Bildpixel für Bildpixel auf der Leinwand des Zielbilds zu positionieren, indem ich sie neben die jeweils ähnlichsten bereits platzierten Pixel setze, gehe ich von den bereits gesetzten Pixeln aus. Um einige dieser Pixel herum gibt es freie Plätze, und ich berechne die Durchschnittsfarbe der Umgebung, um dann in den noch verbliebenen Bildpixeln das Ähnlichste zu suchen, das folglich auf diese Leerstelle passt.

Da die Lage der Pixel im Ausgangsbild dabei keine Rolle spielt, organisiere ich sie für eine schnelle Ähnlichkeitssuche neu, nämlich in einem Farbwürfel mit den Dimensionen Rot, Grün und Blau. Bei 256 möglichen Helligkeitswerten jeder der drei Grundfarben gibt es im Farbwürfel insgesamt 16.777.216 Zellen für ebenso viele Farbtöne. In jede dieser Zellen trägt der Algorithmus ein, wie viele Pixel es mit der jeweiligen Farbe gibt. Wenn ich nun ein Bildpixel mit einer bestimmten Farbe suche und es genau so ein Pixel gibt, ist es im Farbwürfel sofort gefunden; andernfalls kann sich die Suche auf die Nachbarschaft dieser Farbkoordinaten beschränken – Algorithmus B weitet den Suchradius so lange aus, bis wenigstens ein Bildpixel gefunden ist. Meine App zeigt den Verlauf an, wobei immer mehr Bildpixel aus dem Farbwürfel verschwinden und dafür das Zielbild wächst.

Dieser Algorithmus arbeitet tatsächlich deutlich schneller als Algorithmus A. Er vermeidet auch weitgehend das Entstehen von Löchern im Zielbild – solche Löcher treten zwar noch auf, bleiben aber klein und werden meist im Nachhinein noch gefüllt. Allerdings bleibt das Problem, dass sich oft mehrere, durch Pixel anderer Farben getrennte Zonen mit ähnlicher Farbe bilden.

Mein Ziel ist, die Pixel sich selbst so organisieren zu lassen, dass ähnlichfarbige Pixel automatisch zusammenfinden. Das funktioniert jedoch offenbar weder, wenn man das Vorgehen von den noch zu platzierenden Bildpixeln aus plant (Algorithmus A), noch wenn man umgekehrt von den bereits platzierten Pixeln ausgeht (Algorithmus B); vielmehr scheint eine Kombination aus beiden Ansätzen nötig zu sein. Ich habe auch bereits zwei Ideen, die das einzeln oder gemeinsam verwirklichen könnten.

Eines haben mir die bisherigen Versuche erneut bewusst gemacht: Selbst relativ einfache Algorithmen wie diese zeigen ein komplexes Verhalten, das man (oder zumindest ich) nicht so einfach voraussagen kann; man muss daher ausprobieren, was sie aus verschiedenen Bildern machen. Und obwohl meine experimentellen Algorithmen noch nicht tun, was ich mir erhofft hatte, haben ihre Ergebnisse ihren eigenen ästhetischen Reiz.

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