Hallo Besucher, der Thread wurde 14k mal aufgerufen und enthält 77 Antworten

letzter Beitrag von sparhawk am

Grafikprogrammierung (aus: "Heute so gecodet")

    Zitat von Hoogo

    Den Beispielbildern nach erlaubt auch dieses Tool, in Lab oder RGB zu rechnen?

    Da kenn ich mich zuwenig aus. Das sagt mir nichts. Ich gehe nur nach "sieht gut für mich aus" oder eben nicht. :D

    Zitat

    Vor-/Nachteile, so im Sinne von "Wissen, was man tut", kenne ich nur wenig aus Diskussionen.

    Damals ging es noch rein um Octree/MedianCut in RGB, und da war die Erfahrung, dass Octree besser für grafische Sachen, MedianCut besser für Photos wäre. Lab als Farbraum zur Farbreduzierung ist erst durch die Diskussion in Photoline eingefügt worden.

    Das mit den Octree habe ich auch gelesen, allerdings keine Referenzimplementierung gefunden. Eigentlich will ich das ja nur benutzen und mich nicht unbedingt zu tief damit beschäftigen, deshalb habe ich dann weiter gesucht und eben dieses Repo gefunden.

    Zitat

    PNN scheint mir nach einer Google-Suche ähnlich kMeans zu sein, mathematisch aber besser vorhersehbar zu sein.

    "Clusteranalyse" ist wohl ein echt großes Gebiet für viele Anwendungen, die Englische Wikipedia geht dazu richtig ab.

    Habe ich gesehen. Die Algorithmen sind ja nichtmal unbedingt auf Farbquantisierung eingeschränkt, die kann man wohl auch für andere Dinge benutzen. Zumindest wenn man die Mathemathik dahinter versteht. :whistling:

    Zitat

    SPA wird in "Spatial Color" heißen. Soll laut Xi sehr gut für kleine Paletten (16 Farben oder weniger) funktionieren, weil Palette und Dither-Muster zusammen bestimmt werden. Bekomme immer Hinweise, dass es sehr lange dauern kann - Ist schon echt irre.

    Kann auch sein, dass es für die Farbmenge nicht passt. Jedenfalls habe ich das nach etlichen Minuten abgebrochen. Ich habe halt alle ausprobiert und PNN hatte halt den Vorteil dass es gefühlt schnell war (nicht gemessen) und das es dann eben auch noch eine beliebige Anzahl an Farben bestimmen kann, was ich ja ursprünglich wollte. Median Cut scheint bei 256 Schluss zu sein, aber wenn ich mich nicht einschränken muss, nehme ich lieber das was besser konfigurierbar ist.

    Zitat

    Zu Neuquant gibt es noch einen Kommentar auf der XiMagic-Seite, "Method using Kohonen self organizing maps. Usually the best one according to RMSE."

    So auf den ersten Blick habe ich keinen wesentlichen Unterschied gesehen zu den anderen, aber gefühlt war es etwas langsamer. Da ich das auch auf dem Amiga compileren können will, wollte ich auch eine Implementierung bei der ich weitgehend auf floats und komplizierte Formeln verzichten kann.

    Wobei ich mittlerweile nicht mehr so überzeugt bin ob es jemals Leute geben wird, die das wirklich auf einem Amiga native laufen lassen wollen, weil da shalt schon deutlich lahmer ist als auf dem PC. Aber ich finde es trotzdem cool wenn man das Tool unter Windows, Linux UND Amiga verwenden kann. :)

    Zitat

    => Imho bleibt es einfach dabei, dass man ausprobiert, was am besten aussieht. Kannst ja mal Mikes Testbild mit 240 Farben hochladen.

    Ja, das verwende ich jetzt immer zum Vergleichen. Das meines etwas sehr einseitig ist, war mir zwar klar, aber dass der Effekt so Schlimm ist, damit hätte ich nicht gerechnet. Meine erste Version war ja eigentlich unbrauchbar.

    Zitat von sparhawk

    Das sagt mir nichts. Ich gehe nur nach "sieht gut für mich aus" oder eben nicht.

    Ein Problem beim Einschätzen des Ergebnisses hast du allerdings zuvor genannt:

    Zitat von sparhawk

    Das sehe ich dummerweise nicht, weil ich farbenblind bin.

    Das kann die Beurteilung natürlich etwas einschränken, je nachdem, wie stark die Farbenblindheit ausgeprägt ist.


    Zitat von sparhawk

    Ja, das verwende ich jetzt immer zum Vergleichen. Das meines etwas sehr einseitig ist, war mir zwar klar, aber dass der Effekt so Schlimm ist, damit hätte ich nicht gerechnet.

    Als wir unseren C64-Grafikkonverter Gracon entwickelten, haben wir mit sehr vielen Testbildern gearbeitet – weil eines alleine nie alle Herausforderungen beleuchten kann. Du solltest dir ein kleines Set an Bildern zusammenstellen. Darunter welche mit Landschaft, Haut (Portrait/Akt), Technik (z.B. Autos), Strichzeichnungen (z.B. Comic) usw. Am Besten Bilder mit vielen (unterschiedlich stark vorkommenden) Farben, weil es dann besonders schwierig für Algorithmen wird, daraus eine sehr kleine Untermenge auszuwählen.


    Und ich würde dazu raten, vornehmlich mit niedrigauflösenden Bildern (nahe den Zielrechner-Bildschirmdarstellungen) zu arbeiten, dann da erkennt man auch so manche Problematik.


    Wenn du die Ergebnisse selbst nicht gut unterscheiden/beurteilen kannst, dann vertrau ruhig der Schwarm-Intelligenz, also uns. ;)

    Zitat von Retrofan

    Ein Problem beim Einschätzen des Ergebnisses hast du allerdings zuvor genannt:

    Das kann die Beurteilung natürlich etwas einschränken, je nachdem, wie stark die Farbenblindheit ausgeprägt ist.

    Das stimmt. Wenn ich im Zweifel bin, frage ich meine Frau oder Kinder. :D

    Zitat

    Als wir unseren C64-Grafikkonverter Gracon entwickelten, haben wir mit sehr vielen Testbildern gearbeitet – weil eines alleine nie alle Herausforderungen beleuchten kann. Du solltest dir ein kleines Set an Bildern zusammenstellen. Darunter welche mit Landschaft, Haut (Portrait/Akt), Technik (z.B. Autos), Strichzeichnungen (z.B. Comic) usw. Am Besten Bilder mit vielen (unterschiedlich stark vorkommenden) Farben, weil es dann besonders schwierig für Algorithmen wird, daraus eine sehr kleine Untermenge auszuwählen.

    Ich habe ja die Hoffnung, dass der fertige Algorithmus auch funktioniert (weil ich den halt nicht selbst entwicklen will). :D Aber du hast recht, ich muss mal schauen das ich da eine Auswahl bekomme.

    Zitat

    Wenn du die Ergebnisse selbst nicht gut unterscheiden/beurteilen kannst, dann vertrau ruhig der Schwarm-Intelligenz, also uns. ;)

    Ja, das mache ich auf jeden Fall. Meine Frau und Kinder die sehen auch nicht alles. Das mit der grünen Haut ist ihnen auch erst nicht aufgefallen.

    Mittlerweile habe ich den Algorithmus portiert. Hat ziemlich lange gedauert, was aber nicht unbedingt daran lag dass es so kompliziert wäre, sondern eher eine Kombination aus wenig Motivation im Moment, Wetter, spielen wollen, zu wenig Zeit, etc. :)


    Hier jetzt mal zum Vergleich:


    Das Original:


    Konvertiert durch meine Version (Nearest Neighbour):


    Bin ja gespannt ob euch da was auffällt oder ob ich das dann so lassen kann, also her mit dem Feedback. :) Mit dem Algorithus kann ich jedenfalls frei einstellen zwischen 2-65535 Farben.


    Meine Ursprüngliche Idee war ja dass so zu schreiben dass es auch nativ auf dem Amiga läuft. Das habe ich zwar erreicht, aber ich frage mich ob jemand wirklich einen Amiga verwenden würde, denn das ist schon DEUTLICH langsamer (zumindest auf meinem A1000). Und dann sind da natürlich auch die Speicherbeschränkungen. Das werde ich dann als nächstes testen und auch um zu sehen ob es keine Memoryleaks gibt.

    Das reduzieren der Farben funktioniert jetzt einwandfrei. Ich wollte aber gerne noch ein weiteres Feature eingebaut haben, nämlich dass man eine Palette vorgeben kann und das Bild dann an diese angepasst wird. Da ist mir absolut noch nicht klar wie das gehen könnte. Der Algorithmus berechnet ein Histogramm und dann diese "bins" mit denen er die Farben clustered. Aber die Farben kommen eben aus dem Bild und nicht von aussen.

    Hat jemand eine Idee, wie man das bewerkstelligen kann?

    Ich denke, die meisten Algorithmen dürften in 2 Schritten ablaufen.

    - Palette bestimmen

    - Die Pixel umfärben.

    100%ig sicher bin ich aber nicht, die Praxis fehlt,.. Bei manchen Algorithmen kann ich mir auch gut vorstellen, dass das Umfärben der Pixel nicht einfach nur auf dem Abstand zu den Farben der Palette basiert.


    Probier mal das Primitivste aus:

    - Alle Pixel der Reihe nach durchlaufen.

    - Mit Phytagoras den Abstand zu allen Farben der Palette bestimmen, kürzesten Abstand merken.

    - Der gemerkte Paletteneintrag mit dem kürzesten Abstand ist dann der passende.


    Das kenne ich unter dem Namen "beste Farbe" oder "nearest neighbor".

    Vielleicht taugt das für Deinen Zweck schon, oder es hilft Dir, vergleichbares in den anderen Quelltexten zu finden.


    "Fehlerstreuung" wäre dann das nächste Experiment: Die Differenz zwischen eigentlich gebrauchter Farbe und der tatsächlich verwendeten wird gespeichert und auf dem nächsten/den nächsten Pixeln verrechnet. Ab da wird es dann aber interessant, wie genau dieser Fehler verteilt wird. Aber probier einfach erstmal das simple aus.

    Das hatte ich schon mal undd as gibt bei besitmmten Abständen dann falsche Ergebnisse.


    z.B. Wenn ich in der Palette zwei Farben habe wie:

    R1 = 200, G1 = 10, B1 = 10

    R2 = 10, G2 = 10, B2 = 200

    Dann wäre der Abstand gleich und es ist quasi Zufall was genommen wird. Offensichtlich ist das Ergebniss dann aber schlecht, weil die eine Farbe ein starkes Rot hat und die andere Blau ist. Man müsste da also die Anteile gewichten, damit beim Abstand dann auch wirklich die passende Farbe ausgesucht wird. Da habe ich noch keine Lösung dafür.

    Da gab es doch diese lustigen Faktoren aus der DOS-VGA-Zeit, zur Grauwert-Bestimmung aus RGB. Das wäre eine andere Variante, die man verwenden könnte.


    Letztendlich kommt es auch auf den Inhalt des Bildes drauf an, ein Algo, der für ein Typ Bild gut ist, kann beim anderen wieder schlecht laufen.

    Du hast einen Farbwert Rx,Gx,Bx aus einem Bild, zu dem du den am besten passenden Farbwert aus einer Palette R1,G1,B1; R2,G2,B2; ... suchst.

    Wenn jetzt der Farbwert von jedem Wert der Palette subtrahiert wird: (Rx1,Gx1,Bx1) = (R1,G1,B1) - (Rx,Gx,Bx)

    Und dann die Länge dieses Vektors berechnet wird: L1 = | Rx1,Gx1,Bx1 |

    Dann müsste die Palettenfarbe, die die kleinste Länge geliefert hat, die Farbe sein, die (rein rechnerisch) am besten passt.

    Wäre L = 0, dann wären die Farben identisch.

    Zitat von sparhawk

    Das reduzieren der Farben funktioniert jetzt einwandfrei. Ich wollte aber gerne noch ein weiteres Feature eingebaut haben, nämlich dass man eine Palette vorgeben kann und das Bild dann an diese angepasst wird. Da ist mir absolut noch nicht klar wie das gehen könnte. Der Algorithmus berechnet ein Histogramm und dann diese "bins" mit denen er die Farben clustered. Aber die Farben kommen eben aus dem Bild und nicht von aussen.

    Hat jemand eine Idee, wie man das bewerkstelligen kann?

    was Du suchst ist, wie schon oben geschrieben, ein Dithering-Verfahren. Solche sorgen dafür, dass der Fehler bei der Quantisierung auf wenige Farben (in der Palette) im Bildraum verteilt wird. Die menschliche Wahrnehmung ist bei hochfrequenten Farbfehlern recht "tolerant", daher funktioniert das gut -- ok, bei der Pixelgröße einer C64-Auflösung "bedingt gut" :-)


    Eine, auf den ersten Blick nette, Beschreibung von Floyd-Steinberg Dithering (ein Klassiker) inklusive Beispielbildern findest Du hier: https://shihn.ca/posts/2020/dithering/

    Also ich mag ja ordered dither. Für Fotos in der Regel nicht so gut, aber für Grafik oder Animationen taugt es mehr.

    Hab diese Seite gefunden, mit vielen Vergleichsbildern und Code dazu.


    Für Grausfufenbilder mit 1 Farbkanal leuchtet das Prinzip schnell ein, einfach nach festem Muster was auf die Helligkeit addieren/abziehen und dann die passendste Farbe suchen. Wie "einfach daraufaddieren" bei 3 Farbkanälen aussehen soll leuchtet mir aber noch nicht ein... Muss ich mal genauer lesen, wie da die Idee ist.

    Zitat von alx

    Vergleiche NIE Farben in RGB!

    Nimm mindestens YUV.

    Weiß nicht...

    Solche Farbräume können ja aus dem RGB-Würfel per Matrix umgerechnet werden. Also nur ein anderes Koordinatensystem im gleichen Farbraum.
    In YCbCr sind die 3 Vektoren nicht nur rechtwinklig, sondern auch noch gleich lang. Der Abstand zweier Farben ist also in beiden Systemen vergleichbar.
    ES SEI DENN, man packt noch einen Faktor auf die beiden Farbwerte. Ich hab's nicht nachgerechnet, scheint bei YUV so zu sein.
    In dem Fall würde ich aber YCbCr nehmen und den Faktor einstellbar machen.

    Der Faktor müsste sich dann als "mehr Helligkeits-Treue" (kleiner Faktor) bis "mehr Farb-Treue" (großer Faktor) auswirken.

    Zitat von Hoogo

    Hab diese Seite gefunden, mit vielen Vergleichsbildern und Code dazu.

    die habe ich vorhin gesucht -- das dort beschriebene, (ehemals?) patentierte Verfahren funktioniert hervorragend -- damit habe ich auch schon für den C64 experimentiert!


    Zitat von Hoogo

    Solche Farbräume können ja aus dem RGB-Würfel per Matrix umgerechnet werden. Also nur ein anderes Koordinatensystem im gleichen Farbraum.
    In YCbCr sind die 3 Vektoren nicht nur rechtwinklig, sondern auch noch gleich lang. Der Abstand zweier Farben ist also in beiden Systemen vergleichbar.
    ES SEI DENN, man packt noch einen Faktor auf die beiden Farbwerte. Ich hab's nicht nachgerechnet, scheint bei YUV so zu sein.
    In dem Fall würde ich aber YCbCr nehmen und den Faktor einstellbar machen.

    Der Faktor müsste sich dann als "mehr Helligkeits-Treue" (kleiner Faktor) bis "mehr Farb-Treue" (großer Faktor) auswirken.

    Farbmodelle gibt es gefühlt unendlich viele. Im Endeffekt sollte man einen nehmen, bei dem euklidische Abstände der Tristimulus-Vektoren dem wahrgenommenen Farbunterschied entsprechen. Das ist z.B. für CIE Lab der Fall, bei YUV kann man zumindest Luminanz und Chrominanz separat gewichten (ich glaube Projekt One macht das). Die Unterschiede sind aber bei nur 16 Farben nicht gewaltig (trotzdem schadet es nicht).

    Nach etwas Recherche habe ich jetzt etwas gefunden, das ich ausprobieren werde und mein Problem lösen sollte. Vektoren sind da schon ein guter Hinweis. :) Allerdings berechne ich nicht nur die Distanz, sondern erstmal den Winkel. Die Distanz ist ja in bestimmten Fällen gleich, obwohl die Farbe total falsch liegen kann, aber mit dem Winkel sollte das eigentlich passen.

    Habe jetzt die letzten Tage jede Menge rmprobiert. Das Ergebniss war immer Mist, obwohl ich es mit YUV, RGB nd GrayScale versucht hatte. Irgendwann bin ich draufgekommen, dass nicht der Algorithmus falsh war, sondern ich habe auf Grund der internen Sortierung der Farben einfach einen falschen Index zurückgeliefert. 8|

    Nachdem mir dass dann endlich aufgefallen ist, waren die Ergebnisse deutlich besser. :D Ich habe dann nochmal alle Varianten durchprobiert. GrayScale hat überhapt nicht funktioniert. RGB war ganz ok, aber YUV hat tatsächlich das beste Ergebniss geliefert.

    Das mit den Winkel habe ich wieder rausgeschmissen. Ohne funktioniert es deutclih besser, was mich etwas überrascht hat, aber Empieri siegt über Theorie. :D

    Super! Jetzt habe ich ein bequemes Commandzeilentool, mit dem ich Bilder vom PC auf den Amiga (oder andere Rechner) konvertieren kann und bei dem ich Bilder mit einer vorgegebenen Palette angleichen kann. Ich dachte der Teil wird mir zu schwierig und wollte das gar nicht so richtig anfangen, aber jetzt ist es komplett.