StringArt Generator

Bevor ich überhaupt auf das Thema eingehe, weshalb ich einen Generator für etwas benötige, sollte ich zuerst darauf eingehen was Stringart überhaupt ist.
Schaut man sich den Begriff an, so besteht er aus zwei englischen Wörtern „String“ und „Art“. Übersetzt man diese beiden Wörter und verbindet sie wieder, so lässt sich Stringart als „Kunst der Fäden“ oder genauer „Kunst mit Fäden“ bezeichnen. Und tatsächlich geht es bei Stringart um eine Kunstform, bei der auf einer Platte Nägel im Kreis angeordnet werden und ein Faden gespannt wird. Dieser Faden hat einen Startpunkt und wird um verschiedene Nägel in einer bestimmten Reihenfolge gewickelt ohne abgeschnitten zu werden. Durch die große Anzahl an (geraden) Linien, welche vom Faden gebildet werden, entsteht ein Bild mit Graustufen.

Da ich das Konzept des Stringarts sehr schön finde um ein Bild darzustellen, jedoch eher unkreativ , was das herausfinden der Reihenfolge angeht, bin, dachte ich mir, dass das doch leichter gehen muss. Hieraus entwickelte sich die Idee einer Anwendung, welche aus einem Bild die Positionen der Nägel und die Reihenfolge des Fadens um diese Nägel erstellt.

Der Algorithmus hat eine Aufgabe, das Bild möglichst genau aus geraden Linien nachzubilden. Dabei ist wichtig, dass diese Strecken von einem Ende des Bildes bis zum nächsten Ende konstant durchgezogen werden. Eine solche Aufgabe ist eine Optimierungsaufgabe. Diese lässt sich mit einem Greedy-Algorithmus erstellen. Ein solcher Algorithmus hat ein Ziel, Schritt für Schritt das beste Ergebnis herausfinden. Als Nachteil ist jedoch zu vermerken, dass er die global Beste Möglichkeit nicht immer erreicht. Er lässt sich über vier Eigenschaften beschreiben.

Für meine Anforderungen muss der Algorithmus die zielführendste Veränderung im Bild ermitteln. Damit dies funktioniert, besitzt der Algorithmus einen aktuellen Stand des Kunstwerks sowie ein Ziel, das fertige Bild. Nun muss der Algorithmus, ausgehend vom aktuellen Nagel, den nächsten Nagel auswählen. Dabei geht er alle Nägel durch und berechnet, mit welchem Nagel er mit seinem Kunstwerk am nächsten an das fertige Bild herankommt. Anschließend wählt er diesen Nagel aus und wiederholt die Berechnung.

Die erste Implementierung war sehr schnell getan, schließlich ist eine einfache Logik hinter dem Problem. Nehme den aktuellen Stand des Bildes, simuliere jede Mögliche Kombination und berechne wie stark es dem gewünschten Ziel ähnelt. Wähle dann den besten Nagel aus und wiederhole den Schritt. Allerdings kommt man dann sehr schnell an die Grenzen. Da mir direkt klar war, dass das Berechnen von 4.000 Fäden mit jeweils 100-500 Nägeln eine Anzahl von 2.000.000 Berechnungen erzeugt und das Ganze, selbst wenn eine Berechnung nur 0,1s benötigt (schließlich muss ja jedes Mal ein Bild erstellt werden und berechnet werden, welche Pixel von einer Linie getroffen werden), pro Bild zu einer ununterbrochenen Berechnungsdauer von 2,3 Tagen führt. Deshalb war meine erste Optimierung die Einführung von mehreren Tasks. Jeder einzelne Task berechnet ein einzelnes Fadenelement. So ergeben sich genau so viele Tasks wie es Nägel gibt (genauer gesagt ist es einer weniger), die alle ihre Berechnung durchführen. Dabei kann ein PC nun seine ganze CPU ausnutzen und so acht oder mehr Berechnungen gleichzeitig ausführen. Das verkürzt die Berechnungsdauer nun auf sieben Stunden.
Die nächste Optimierung ist eine, zu der ich gezwungen wurde. Da der Algorithmus mit einer größeren Auflösung bessere Ergebnisse erzeugt, ist diese nicht zu gering anzusetzen. Allerdings bin ich mit dem neuen Multitasking direkt in einen Memoryüberlauf gekommen. Meine Auflösung von 4096×4096 war zu viel für meinen PC. Schließlich muss er ja 100-500 dieser Bilder aktiv im RAM halten um diese zu berechnen und dann das beste für die nächste Runde auszuwählen. Doch warum ist das ein Problem? Ich verwendete Unitys Texture2D als Texturspeicher. Für jedes Pixel werden vier Byte gespeichert (RGBA), also eines für jede Farbe (rot, grün, blau) und ein weiteres für die Transparenz. Ein Bild mit 1024×1024 Pixeln benötigt also 4,19MB an Speicher. Geht man nun auf eine Größe von 4096 Pixeln, so sind das schon 67,11MB. Aber auch hiermit war noch keine gute Auflösung möglich. Möchte ich nun aber 500 Bilder speichern, so benötige ich knapp 33GB RAM, deutlich mehr wie mein PC besitzt.
Ich könnte nun hingehen und die Auflösung reduzieren, das macht aber keinen Sinn, da dann die Qualität sinkt. Nach einiger Zeit der Überlegung konnte ich dann die Lösung finden und sie scheint so simpel. Ich erstelle ein eigenes Bild – naja, fast. Die Idee dahinter ist, dass jedes Pixel ja eh nur Schwarz-Weiß ist. Somit würde eine Dezimalzahl ausreichen. Diese geht von 0 (weiß) bis 1 (schwarz). Dabei werden pro Pixel nur vier Byte benötigt. Ich würde also nur noch 8GB RAM benötigen.
Da ich eine RAM-Belastung von 50% auf meinem Gerät immer noch als sehr hoch empfand und wollte, dass die Anwendung auch auf schwächeren Geräten funktioniert, muss eine weitere Anpassung her. Im Endeffekt werden von diesen bis zu 500 Bilddaten aktiv nur eine Hand voll benötigt. Um hier etwas genauer zu werden ist eines davon das Ziel und für jeden aktiven Task ein weiteres, das ergibt zwischen 9 und 33 Bilddaten. Wieder konnte der benötigte RAM reduziert werden, dieses Mal auf 2,2GB. Umgesetzt wurde dies mit einem eigenen Pool an Arrays. Dieser ist zu Beginn leer und erstellt nur so viele Arrays wie benötigt werden. Am Ende eines Tasks gibt dieser das benutzte Array zurück und gibt es dadurch wieder frei. Somit konnte das Thema Speicher ein für alle mal beendet werden.
Der nächste Knackpunkt war immer noch das Thema Geschwindigkeit. Damit die Problemlösung verstanden werden kann, sollte ich hier zuerst ausholen, was ein solcher Task überhaupt macht. Grundsätzlich bekommt er die Position des aktuellen Nagels und die des nächsten Nagels sowie das aktuelle Bild und das Zielbild. Nun fängt der Task an, die Linie zu berechnen, welche der Faden nehmen würde, wenn er zwischen diesen beiden Nägeln gespannt wird. Daraus werden dann alle Pixel berechnet, welche dies darstellen würden, inklusive deren, die dies nur teilweise machen. Nun werden für alle betroffenen Pixel im aktuellen Bild verändert. Anschließend werden das aktualisierte Bild sowie das Zielbild miteinander verglichen. In jeder Berechnung der Linie befindet sich für jedes Pixel eine Wurzelberechnung, welche unter Umständen pro gespannter Faden tausende Male durchgeführt wird. Und diese tausende Male finden pro Nagel, also erneut 100-500 Mal statt, für jeden einzelnen Faden, also erneut 1.000-10.000 Mal. Das sind für ein Bild bis zu 5.000.000.000 Mal. Die Problemlösung ist deshalb sehr einfach. Da die Positionen der Nägel fix sind, ändern sich die Strecken nicht. Deshalb werden vor dem Berechnen des Greedy-Algorithmus diese Pfade berechnet. Dabei werden die Ergebnisse zwischengespeichert und müssen dann in den unzähligen Tasks einfach nur noch addiert werden. Dies ist eine Aufgabe, welche sehr schnell passiert. Anschließend muss noch der Optimierungsgrad festgestellt werden. Im Zuge dieser großen Strukturänderungen wurde zudem eine verbesserte Berechnung der Linien erstellt. Diese betrachtet nur noch die betroffenen Pixel und nicht mehr alle. Dadurch muss nicht mehr jedes Pixel geprüft werden, schließlich sind ca. 95-99% der Pixel eh nie betroffen. Insgesamt konnten mit diesen Umstrukturierungen unzählige Wurzelberechnungen und die Loops von ca. vier oder fünf auf zwei (eins für die Kombination des Pfades und eins für den Optimierungsgrad) reduziert werden.
Wozu führte das Ganze? Plötzlich konnte das Programm mehrere Fäden pro Sekunde berechnen anstelle mehrere Sekunden für die Berechnung eines Fadens zu verschwenden. Die Berechnung eines ganzen Bildes benötigt nun nur noch wenige Minuten, nicht mehr Stunden oder gar Tage.
Betrachtet man den aktuellen Code, so sind mir beim Schreiben dieses Artikels noch weitere Optimierungen gekommen. Im aktuellen Zustand wird der Pfad zu dem Bild hinzugefügt und anschließend in einem separaten Loop die Optimierung berechnet. Da sowohl das Zielbild sowie das aktuelle Bild gleich groß sind, kann eines der beiden Loops entfernt werden, indem zuerst der neue Pixelwert ermittelt wird und dann direkt im Anschluss die Übereinstimmung des aktuellen Pixels berechnet wird. Ebenso könnte der Speicherplatz optimiert werden, indem die verwendeten und vorab berechneten Pfade effizienter gespeichert werden. Hier müsste nicht mehr jeder Wert gespeichert werden, sondern nur noch diejenigen, die größer null sind.

Nachdem nun schnell Bilder erstellt werden können, gilt es nun auch diese zu präsentieren.

Grundsätzlich sind nun die Daten soweit erstellt, dass es an den Export geht. Zum Zeitpunkt des Erstellens des Projektes hielt ich es für eine gute Idee, dass ich diese Daten in eine CSV-Datei exportierte. Zuerst landen dort dann die Nagelpositionen und danach die Sequenz der Nägel. Bei einer Überarbeitung würde ich hier eher auf das Erstellen einer PDF gehen, die dann (je nach Zielgröße des Bildes) die Nagelpositionen im (Original-)Maßstab aufzeigt.

Zudem begann ich damit, das Thema zu automatisieren, sodass eine Maschine Löcher bohrt, Nägel positioniert und anschließend den Faden spannt. Dazu muss der Code die Daten in Maschinencode, den sogenannten G-Code umwandeln. Dies ist jedoch nicht fertig gestellt, da unter anderem hierfür die Maschine schon stehen sollte um die Anpassung zu verbessern.

Das Projekt hat mir sehr viel Spaß bereitet. Es zeigte erneut, dass aus einer „dummen“ Idee ein cooles Projekt entstehen kann. Ich konnte im Rahmen des Projektes mich in den Greedy-Algorithmus einarbeiten und mich sehr stark auf die Optimierung von Code sowie das Thema Multitasking konzentrieren. Eventuell schaffe ich es in der (näheren) Zukunft dieses Projekt mit anderen Bereichen (z.B. Hardware) zu verknüpfen und dann Kunst zu erstellen. Vielleicht muss ich mir aber auch erst einmal Zeit nehmen um ein Kunstwerk selbst zu erstellen. Allerdings zeigte mir die Berechnung, dass ich für das Erstellen eins 200x200mm Kunstwerkes ungefähr 600-800m Faden benötige. Dies sollte klar sein, da ich für jede Strecke quer durch den Kreis maximal 200mm Strecke habe. Würde ich hier nur den Durchmesser wählen, so wären das genau die 800m. Zudem habe ich beim Erstellen dieses Posts gemerkt, dass die Anwendung zwar funktioniert, durch verschiedene Updates aber vieles nicht mehr so sauber klappt wie es einmal war.

Nachdem ich nun wieder ein Projekt gefunden habe um es zu reparieren bzw. weiter zu bringen, geht es erneut an den StringArt-Generator. Zuerst mache ich mir Gedanken über das Thema Auflösung. Die aktuelle Auflösung wird vom Bild bestimmt. Ein Überschreiten dieses Limits würde wenig Sinn ergeben. Betrachtet man verschiedene Kameraauflösungen, so ist schnell erkennbar, was eventuelle Limits sind. Eine 8MP Kamera erstellt ein 4k Bild (3840×2160 Pixel). Mit 12MP ist man bei einer Auflösung von 4000×3000 Pixeln. Profikameras können auch 102MP erreichen. Dann sind wir bei 13000×8000 Pixeln. 102MP sind weit fern der Realität und würden 11,6GB pro Bild benötigen. Rechnen wir mit einer maximalen Auflösung von 44MP, so sind das 7680 auf 5760 Pixel. Ein solches Bild mit vier Byte Farblayer zu speichern, würde immer noch 5GB RAM benötigen. Aber selbst wenn RAM kein Thema wäre, würde jeder Millimeter eines Bildes mit den Maßen 2x2m immer noch fast 4 Pixel repräsentieren. Da die Auflösung eines StringArt-Bildes durch die Fäden nicht annähernd 0,25mm genau ist, kann hier eine Optimierung eingebaut werden.
Diese Optimierung ähnelt der Thematik dpi (Dots per Inch) aus dem Digitaldruck. Dort ist ein Wert von 300dpi Standard, gerade für hochwertige Dateien. Für mein System würde ich hier auf eine Auslösung von 10dpcm (Dots per cm) gehen. Die Bildauflösung ist somit nicht mehr fix, sondern abhängig von der Größe des Endproduktes. Ein Bild mit 2mx2m würde somit nur noch 2000×2000 Pixel benötigen, das währen 0,4GB Speicher und eine ausreichende Auflösung. Bei Bedarf wäre eine Anpassung sogar möglich.

Die zweite Anpassung behandelt vor allem die Nutzerfreundlichkeit. Bilder sollen nach der Auswahl rotiert oder gespiegelt werden können. Ebenso sollen die Farben des String-Bildes invertiert werden können.

Als vierte Optimierung findet eine Überarbeitung des Exports der Ergebnisse statt. Diese sollen nun nicht mehr in einer CSV-Datei exportiert werden, sondern in einer anderen Form. Diese muss ich mir noch überlegen, da sie ebenfalls als Datenbank für das Programm dienen muss. Der Export dient hier als Speichermöglichkeit. Die weiteren Funktionen (Tools & G-Code) können also fertig erstellte Images laden. Ich habe mich nach einiger Überlegungen für eine Kombination entschieden. Einerseits wird das Bild exportiert, welches erstellt wurde. Andererseits werden die Metadaten als JSON-Datei gespeichert. Zusätzlich wird die Anleitung als Word-Datei erstellt und exportiert. Somit sind die einzelnen Dateien voneinander getrennt und können getrennt optimiert werden.

Da mit der Erhöhung der Nägel sowie der erhöhten Pixelanzahl bei großen Bildern die Berechnung der Pfade immer länger benötigt, muss auch hier eine Umstrukturierung stattfinden. Neben der Implementierung von Multitasking geht es hier vor allem um das verhindern von Dopplungen. Grundsätzlich ist es egal, ob der Pfad von Nagel 5 zu 205 betrachtet wird, oder von 205 zu 5. Die Strecke und somit auch die betroffenen Pixel sind identisch. Das bedeutet wiederum, dass bei einer Nagelanzahl von 500 die Anzahl an Verbindungen, welche berechnet werden müssen, um 50% (125.000 Stück) verringert werden. Der dabei gewonnene Speicherplatz sind 0,5GB, darauf sollte aber nicht der Fokus liegen. Die Geschwindigkeit der Berechnungen liegt mit 150 Pfaden pro Sekunde schon hoch, aber bei einer Anzahl von 120.000 ist die Dauer doch sehr lange. Deshalb müssen weitere Optimierungen stattfinden. Zuerst habe ich den Prozess abgeändert. Ich arbeite nun nicht mehr mit Tasks, sondern mit Parallel.For, genauer gesagt mir vorab bestimmten Paaren und Parallel.Foreach. Hierdurch konnte die Geschwindigkeit gut erhöht werden. Ebenso reduzierte ich die Rechenleistung, indem ich Umrechnungen von mm in Pixelpositionen aus dem Loop herausgezogen habe. Diese werden somit nur noch einmal durchgeführt und nicht mehr 100.000 mal. Selbiges gilt der Berechnung des Zentrums. Auch die Berechnung der Pfade wurde abgeändert. Ich verwende nicht mehr ein Struct für die Bestimmung des Punktes, sondern direkte Werte. Aber auch der Algorithmus wurde optimiert. In der Berechnung wie stark ein Pixel betroffen ist, wurde mehrfach die Wurzel berechnet. Diese Berechnungen wurden durch ein Nachschauen in einer Lookup-Tabelle ersetzt. Ebenso wurden nicht Pixel für Pixel überprüft und gespeichert, sondern alle Pixel gemeinsam gesendet. Dadurch konnte ich die Anzahl der Überprüfung der Leseberechtigung im ConcurrentDictionary stark reduzieren. Dies führte zu einer Geschwindigkeit von 10.000 Pfaden pro Sekunde. Eine weitere Verbesserung entstand aus der Entfernung von ConcurrentDictionaries. Da ich diese einmal erstelle und dann mit jedem Thread einen Pfad ändere und sich keine Speicherpfade kreuzen, konnte ich diese gleich wieder entfernen. Somit konnte ich viele TryAdd() entfernen und nebenbei ganze Dictionaries verwenden und einfügen. All dies führte dazu, dass ich nun 600.000 Pfade innerhalb von 25s berechnen kann, ein wichtiger Schritt zur Optimierung. Durch diese Änderung wurde zudem die Zeit vor dem eigentlichen Pfadberechnen drastisch reduziert.