Hello, Guest the thread was viewed18k times and contains 77 replies

last post from sparhawk at the

Grafikprogrammierung (aus: "Heute so gecodet")

    Mittlerweile funktioniert mein Tool schon soweit dass ich ein PNG File laden kann, die Farben reduzieren und dann wieder als RGB oder Palettenfile speichern kann. Man kann also eine Grafik laden und angeben auf wieviele Farben es reduziert werden soll (bei RGB kann man die Anzahl beliebig reduzieren, bei PNG Palettenformat kann man sowieso nur maximal 256 Farben speichern).

    Nur die Berechnung der besten Farbe funktioniert noch nicht ganz richtig, da gibts noch Artefakte wo eine falsche Farbe ausgewählt wird, weil mein erster Ansatz zu naiv ist (aber dafür einfach zu implementieren).

    Falls jemand eine Idee hat, wie man das richtig macht, hätte ich nichts gegen ein paar Tips.

    Im Wesentlichen ist das Problem folgendes:

    Ich habe ein Bild mit (z.B. 8000) Farben. Um die auf 256 zu reduzieren, wähle ich die 256 häufigsten Farben aus damit diese erhalten bleiben. Jede der überzähligen Farben sollte dann so angepasst werden, dass aus den 256 erhaltenen Farben, diejenige ausgewählt wird, welche am "ähnlichsten" ist, und genau da hakt es noch ein wenig. Wie kann ich am Besten beurteilen welche Farbe am ähnlichsten ist?

    Im Moment mache ich das einfach so dass ich jeweils für R/G/B die Differenz bilde. Also (R0-R1) + (G0-G1) + (B0-B1). Das ist quasi die Distanz zwischen den beiden Farben. Diejenige mit der geringsten Distanz wird dann genommen. Das Problem dabei ist, dass diese Distanz bei zwei verschiedenen Farben zufällig gleich sein kann, obwohl die eine Farbe besser passt als die andere. Man muss das also irgendwie noch gewichten.

    Imho müsstest Du den Farbabstand nach Pythagoras berechnen, also alle 3 quadrieren, addieren, Wurzel ziehen.


    Ximagic Quantizer ist ein hübsches PS-Plugin für Frickler auf diesem Gebiet. Die Homepage liefert auch einige hilfreiche Links zu den Algorithmen.


    Manchmal bringt Lab bessere Ergebnisse als RGB oder YCbCr, ist aber sehr vom Bild abhängig. Keine Ahnung, ob es eine einfachere Umrechnung von einem RGB-Farbraum nach Lab gibt oder ob es da die ganze Farmanagement-Sachen für braucht.

    Quote from sparhawk

    Ich habe ein Bild mit (z.B. 8000) Farben. Um die auf 256 zu reduzieren, wähle ich die 256 häufigsten Farben aus damit diese erhalten bleiben.

    Uh... mit der Methode kannst Du aber ganz heftig auf die Nase fallen. Dieser statistische Ansatz ist wirklich ungünstig.


    Was machst Du z.B., wenn sich die häufigsten 256 "Farben" in einem ganz kleinen Cluster gruppieren, es aber durchaus noch "Inseln" mit komplett anderer Farbgebung im Rest des Bildes gibt. Nur so als Beispiel: dieser Cluster könnte in einem Foto das verrauschte "Weiß" eines Blatt Papiers mit Text sein. Da stehen die Chancen dann so, daß dann das Schwarz der Schrift nicht mehr unter die ersten 256 kommt, und damit ist die Schrift weg.


    Eine gute Heuristik für eine Palette liefert z.B. der Heckbert-Median-Cut - den kann man z.B. auch so implementieren, daß er das ganze Bild als Statistikquelle für die Farbblöcke nutzt.


    Üblicherweise nimmt man dann als Abstandsfunktion, mit R, G, B als Pixelfarbe und R[i], G[i], B[i] als i-te Palettefarbe die Funktion:


    d = 0,299 * (R - R[i])^2 + 0,587 * (G - G[i])^2 + 0,114 * (B - B[i])^2 -> Minimum


    und minimiert die. Damit 'teilst' den Farbraum in Zellen auf und weist den nächstgelegenen Palettenpunkt zu. Eine Differnz im Grünanteil wird stärker gewichtet als Rot oder Blau.


    Wichtig, wenn Du dann noch Error-Diffusion machst: dann müssen die Bildpixel und Palettenwerte mit linearer Intensität (d.h. mit gamma=1) in den Farbkomponenten vorliegen. Das ist bei dem Ausgangs-Bildmaterial bzw. auch bei den Palettenregistern üblicherweise nicht der Fall, die sind dann mit gamma=1,8 .. 2,2 kodiert. Ohne vorherige Korrektur stimmt die Farbbalance bei gering gesättigten Bereichen (also, ungefähre Grauwerte) nicht, und dunkle Teile des Bildes werden durch Streupixel stark 'aufgehellt'.


    Aber gerade letzteres hat sich auch in den letzten 20 Jahren noch nicht so wirklich rumgesprochen. Selbst so profane Werkzeuge wie die Thumbnail-Anzeige von Bildern in Windows 10 Dateiordnern kriegen das mit dem gamma noch nicht hin (man muß es nämlich generell bei Filtern und Größenänderungen auch berücksichtigen!).


    Edit: (auch Hoogo) die nicht-Berücksichtigung von gamma hat einen größeren Einfluß auf die Bildqualität als die Wahl des Farbraums (also, Lab oder YUV anstelle von (s)RGB).


    Quote from Hoogo

    [...] Wurzel ziehen

    Braucht man nicht.


    Erstens ist die Wurzel *extrem* teuer. Zweitens gilt bei positiven Werten stets: Ist a² > b², dann ist a > b.


    Und diese Information reicht aus, um den Paletteneintrag mit dem geringsten Abstand zu finden.

    Quote from Mike

    Edit: (auch Hoogo) die nicht-Berücksichtigung von gamma hat einen größeren Einfluß auf die Bildqualität als die Wahl des Farbraums (also, Lab oder YUV anstelle von (s)RGB).

    Bin skeptisch...

    Gerne linear, wenn es um physikalische Sachen geht.

    Gerne auch beim Rotieren oder Skalieren, wo man "Lichtteilchen" neu abzählen und neu auf Pixel verteilen will.


    Andere Sachen haben aber weniger mit Physik als mit Wahrnehmung zu tun.

    Sättigung erhöhen, Farbräume konvertieren, ähnliche Farben bestimmen, und das Quantisieren zähle ich da auch zu.

    Da sollte es dann besser mit Zahlen funktionieren, die an die Wahrnehmung angepasst sind.

    Auch die 0,299 / 0,587 / 0,114 sind ja so eine Anpassung an die Wahrnehmung.


    Mit meinen Tools bekomme ich aber keine nennenswerten Unterschiede zwischen linear und Gamma 2.2 hin. Kann aber sein, dass die zu schlau sind und den Farbraum erkennen.

    Quote from Mike

    Erstens ist die Wurzel *extrem* teuer. Zweitens gilt bei positiven Werten stets: Ist a² > b², dann ist a > b.

    Sehe ich ein, die Wurzel kann man sich schenken.

    Die Deltas vor dem zusammenzählen Quadrieren reicht, sollte man aber machen.

    Quote from Mike

    Erstens ist die Wurzel *extrem* teuer.

    Kommt drauf an, wie genau die sein muss. Wenn man bei der Genauigkeit Abstriche machen kann, ist die Wurzel relativ fix aus einer LUT geholt, die man an Anfang vorberechnen kann.

    Quote from Hoogo

    Imho müsstest Du den Farbabstand nach Pythagoras berechnen, also alle 3 quadrieren, addieren, Wurzel ziehen.


    Ximagic Quantizer ist ein hübsches PS-Plugin für Frickler auf diesem Gebiet. Die Homepage liefert auch einige hilfreiche Links zu den Algorithmen.

    Danke! Das werde ich mir mal ansehen. Das mit der Wurzel klingt halt ziemlich teuer. Ursprünglich sollte das Tool auch native auf de Amiga laufen können, aber ich vermute das wird wohl eh nicht sehr realistisch, weil es jetzt schon recht lange braucht. :) Allerdings funktioniert es zumindes trotzdem, wenn es jemand wirklich native laufen lassen will. :)

    Quote from Mike

    Was machst Du z.B., wenn sich die häufigsten 256 "Farben" in einem ganz kleinen Cluster gruppieren, es aber durchaus noch "Inseln" mit komplett anderer Farbgebung im Rest des Bildes gibt. Nur so als Beispiel: dieser Cluster könnte in einem Foto das verrauschte "Weiß" eines Blatt Papiers mit Text sein. Da stehen die Chancen dann so, daß dann das Schwarz der Schrift nicht mehr unter die ersten 256 kommt, und damit ist die Schrift weg.

    Wenn die Farben häufiger vorkommen, dann sollten die es doch auch in die Palette schaffen. Mein Beispielbild, it dem ich gerrade arbeite, hat z.B. sehr viele Farbwerte die jeweils nur einmal vorkommen. Also gibt es nur ein Pixel mit dieser Farbe. Sowas kann also problemlos verschwinden. Wenn es "Inseln" dann sollten diese doch in der Häufigkeit auch entsprechend stärker vertreten werden. Das man bei der Reduktion von 16Mio auf 256 grosse Verluste hat, ist aber klar. :)

    Quote

    Eine gute Heuristik für eine Palette liefert z.B. der Heckbert-Median-Cut - den kann man z.B. auch so implementieren, daß er das ganze Bild als Statistikquelle für die Farbblöcke nutzt.

    Werde ich mir auf jeden Fall mal ansehen. Danke für den Tip!

    Quote

    Üblicherweise nimmt man dann als Abstandsfunktion, mit R, G, B als Pixelfarbe und R[i], G[i], B[i] als i-te Palettefarbe die Funktion:


    d = 0,299 * (R - R[i])^2 + 0,587 * (G - G[i])^2 + 0,114 * (B - B[i])^2 -> Minimum


    und minimiert die. Damit 'teilst' den Farbraum in Zellen auf und weist den nächstgelegenen Palettenpunkt zu. Eine Differnz im Grünanteil wird stärker gewichtet als Rot oder Blau.

    Aber wie baut man diese Palette auf? Mit dem oben erwähnten Algorithmus?

    Quote

    Aber gerade letzteres hat sich auch in den letzten 20 Jahren noch nicht so wirklich rumgesprochen. Selbst so profane Werkzeuge wie die Thumbnail-Anzeige von Bildern in Windows 10 Dateiordnern kriegen das mit dem gamma noch nicht hin (man muß es nämlich generell bei Filtern und Größenänderungen auch berücksichtigen!).

    Das wird dann aber wesentlich aufwendiger. Eigentlich dachte ich mir, jemand der ein Bild für den Amiga, C64 oder andere konvertieren will, der wird das sowieso erstmal in einem Grafikprogramm vorbereiten. Mein Tool wäre primär dafür gedacht die Farben anzupassen. Also eben runterrechnen auf die reduzierte Palette, oder man gibt halt eine Palette per Textfile vor und lässt sich dann seine Bilder auf die vorgegebene Palette ummappen.

    Quote

    Erstens ist die Wurzel *extrem* teuer. Zweitens gilt bei positiven Werten stets: Ist a² > b², dann ist a > b.

    Und diese Information reicht aus, um den Paletteneintrag mit dem geringsten Abstand zu finden.

    Eben. Die genauen Werte werden ja sowieso nicht benötigt, sondern nur die relative Informaiton.


    Auf jeden Fall war das schon mal sehr hilfreich. Eventuell sollte man diese Diskussion in einen eigenen Thread auslagern. Weiss nur nicht ob das besser in einem Grafik oder Programmierbereich aufgehoben wäre.

    Quote from sparhawk

    Aber wie baut man diese Palette auf? Mit dem oben erwähnten Algorithmus?

    Ja. Das Zwischenergebnis sind erstmal N Quader im Farbraum, welche jeweils eine gewisse Anzahl an Farben aus dem Originalbild umfassen. Dann mittelst Du sämtliche Farbeinträge aus diesen Quadern (unter Berücksichtigung auch mehrfacher Einträge!) und bekommst daraus den jeweiligen Paletteneintrag.


    Quote from sparhawk

    Eventuell sollte man diese Diskussion in einen eigenen Thread auslagern. Weiss nur nicht ob das besser in einem Grafik oder Programmierbereich aufgehoben wäre.

    Würde vorschlagen, in der Programmierecke des Grafikbereichs. ;)

    Danke!


    Ich habe jetzt erstmal den Pythagoras ausprobiert und die Ergebnisse sind schon deutlich besser. Muss das mal aber auch mit anderen Bildern ausprobieren, da mein Testbild nicht unbedingt repräsentativ ist. :)

    Auf den Pythagoras hätte ich eigentlich auch selbst kommen können, aber manchmal sieht man den Wald vor lautr Bäumen nicht. :D

    Die sqrt() habe ich übrigens weggelassen. Habs auch mit ausprobiert, aber das Ergebniss ist das Gleiche (was ich auch erwartet hatte).

    Den Heckbert Median Cut habe ich mal kurz überflogen. Klingt jedenfalls aufwändiger zu implementieren, muss mal schauen ob ich da etwas fertiges finde. Die eine Seite die ich beim ersten Versuch gefunden hatte, war etwas blöd, weil da der Code aus lauter Screenshots bestand, was nicht gerade hilfreich ist.

    Das hier. Wie gesagt, ist zum Testen nicht die Beste Wahl, aber das wollte ich eigentlich für ein kleines Demo verwenden.

    Habe auch noch das zweite gepostet, welches reduziert wurde.

    Wäre mal interessant wie deines dann ausshieht im Vergleich.

    Dafür dass das mein erstes Grafikkonvertierungstool ist, finde ich das Ergebniss jedenfalls nicht so schlecht. :)

    Aber ich werde mal probeweise auch andere konvertierun und schauen wie die dann abschneiden.

    Weniger Aufwand beim Programmieren (aber nicht wirklich bei der Laufzeit im Vergleich zu Heckbert, daher vl. nicht, was Du suchst) wäre bspw. ein Clustering-Ansatz basierend auf k-means (einer der ersten Treffer bei Google: https://scikit-learn.org/stabl…t_color_quantization.html, aber k-means ist wirklich einfach)


    Farbräume sind ein Thema für sich (fängt bekanntermaßen schon damit an, dass RGB nicht gleich RGB ist) und bei ein paar Tests, die ich mit Farbreduktion auf die C64-Palette gemacht habe, haben unterschiedliche Farbräume _subjektiv_ besser und schlechter funktioniert. Nur eins: die Länge eines Differenzvektors macht bei CIE Lab oder LUV (und anderen perzeptuell motivierten Farbräumen) prinzipiell mehr Sinn, als in RGB, XYZ etc., da das Ziel eben war, dass die Distanz zweier Farbvektoren dem wahrgenommenen Farbunterschied entspricht. Ein gutes Buch dazu ist Color Imaging von Reinhard et al. und natürlich hier ;-)

    Quote from sparhawk

    Das hier.

    O.K. - hab's gerade mal durchlaufen lassen:


    austria_mk_nodither.png (nicht gedithert)


    austria_mk_dither.png (gedithert)


    Mit bloßem Auge ist kein Unterschied erkennbar. Tatsächlich sind es in beiden Fällen 'nur' 251 Farben - die restlichen 5 Paletteneinträge wurden nach der Mittelwertbildung durch die Abstandsminimierung keinem Originalfarbwert mehr zugeordnet und fielen so unter den Tisch. Das kommt schon mal vor.


    Das Wappen ist ansonsten jetzt auch nicht ein so schwieriges Motiv für einen Farbquantisierer - z.B. auf Farbtonfehler im orangen und hellblauen Bereich reagiert das System Auge/Gehirn am empfindlichsten. Kein Wunder, daß die analogen TV-Standards bereits daraufhin schon optimiert wurden. ;)


    Quote from Frenetic

    ein Clustering-Ansatz basierend auf k-means

    Den hab' ich auch parat. :D

    Auf den kleinen Bildern ist da etwas schwer zu erkennen, aber ich habe den Eindruck dass bei deinen Konvertierungen die Strukturen besser erhalten bleiben. Zumindest bei den Beinen unten, sieht dieses Muster viel besser aus. :)

    Mit welchem Tool hast du das gemacht? Kann man damit auch die Farben in den Paletten austauschen? Was mein Tool halt auch kann (bzw. können wird) ist, dass man eine Palette vorgibt über eine Textdatei und das Bild dann angepasst wird.

    Als Beispiel habe ich z.B. die Palette vom C64 erstellt, aber man kann halt jede beliebige andere auch erstellen, auch die Anzahl der Farben ist frei wählbar und nicht begrenzt.

    Und was mir dabei halt auch wichtig war ist das die Library keinerlei externe Abhängigkeiten hat. Man kann es also bauen ohne dass man 15 andere libs suchen und bauen muss.

    Quote from sparhawk

    Auf den kleinen Bildern ist da etwas schwer zu erkennen, aber ich habe den Eindruck dass bei deinen Konvertierungen die Strukturen besser erhalten bleiben

    Wie hast Du denn die Palette erstellt, noch nach reiner Häufigkeit der Farben?

    Du hast da ungeheuer viele Graustufen in der Palette, aber kaum was aus dem Gelb-Dunkelgelben Bereich. Die zZeichnung in den Füßen sieht zwar fürs Auge sehr Grau aus, aber reingezoomt ist es doch eher Gelb.


    Der Xi-Filter hat auch einen Algo "Popularity", was dem wohl entsprechen dürfte. Allerdings fragt er noch nach "significant bits" und geht da nur bis 5. Dort werden also viele Farben mit einem einfachen AND vor dem Zählen noch über einen Kamm geschoren, dann bleibt auch was Gelb-Graues übrig.

    Quote from Mike

    Edit: (auch Hoogo) die nicht-Berücksichtigung von gamma hat einen größeren Einfluß auf die Bildqualität als die Wahl des Farbraums (also, Lab oder YUV anstelle von (s)RGB).

    Das hab ich auch nochmal überschlafen.

    Die Fehlerstreuung ist genau so ein Punkt, den ich "Lichtteilchen" neu abzählen und neu auf Pixel verteilen nennen würde.

    Das Bestimmen einer Palette ist weiter etwas, was ich der Wahrnehmung zuordnen würde.


    Dass "Median cut" und andere Algos ziemlich gleiche ergebnisse liefern ist auf den 2. Blick logisch: Zwar sind die Zahlen ganz andere, die Mitte zwischen heller und dunkler Hälfte hat auch eine andere Nummer, aber letztlich hat sie doch die gleiche Helligkeit.


    Xi liefert mit "Popularity" deutlich andere Ergebnisse, aber das einfach AND macht die Bilder deutlich zu dunkel. Ist imho ein Fehler. Das macht bei linearem Farbraum gar nicht so viel aus, macht aber die Ergebnisse kaum vergleichbar. Ich experimentiere noch.

    Quote from sparhawk

    Mit welchem Tool hast du das gemacht?

    Das ist eine komplett selbst geschriebene Bibiliothek in C zur Bildverarbeitung.


    Als Grundlage dient ein Set von zwei Headerdateien und einer Quellcode-Datei, welches Pixelzugriffsmakros für Graustufen, RGB und *Float*-Bilder im Speicher und Funktionen für Dateizugriff bereitstellt. Als Dateiformat habe ich auf *.pgm und *.ppm aus der Unix-Welt gesetzt. Mit IrfanView wandele ich zwischen diesen und anderen Bildformaten um.

    Quote from sparhawk

    Kann man damit auch die Farben in den Paletten austauschen?

    Palettenbehaftete Bilder baut die Toolsammlung nur indirekt: ich schreibe ein Graustufenbild als Indexbild weg, sowie ein einzeiliges Bild, welches die Palette enthält. Ein weiteres Tool aus der Suite wandelt das Palettenbild in eine *.PAL-Datei um, welche IrfanView dann importieren kann.

    Quote from sparhawk

    Was mein Tool halt auch kann (bzw. können wird) ist, dass man eine Palette vorgibt über eine Textdatei und das Bild dann angepasst wird.

    Das geht auch problemlos. Dann lasse ich die Palette eben nicht vorher mit Heckbert erzeugen (und ggfs. über k-Means noch optimieren) sondern stelle stattdessen die gewünschte fixe Palette zur Verfügung, mit oder ohne Dithern.


    ...


    Im Anhang mal ein Beispiel, welches ich mit der Bibliothek geschrieben habe: ein Bildkonverter für den VC-20, für Bilder mit 320x200 Pixeln. 'image.c', 'image.h' und 'matrix.h' sind der "Kern" der Bibliothek, 'ppm2cga.c', 'dither.c' und 'dither.h' kommen für die Anwendung dazu.


    Das Anzeigeprogramm für den VC-20 braucht eine RAM-Erweiterung mit +35K. Dann einfach "BOOT" laden, im Prompt "RESULT.SEQ" eingeben und dann mit den Cursor-Tasten im gezoomten Bild umherscrollen. :D

    Quote from Hoogo

    Wie hast Du denn die Palette erstellt, noch nach reiner Häufigkeit der Farben?

    Bei meinen, ja. Ich gehe halt davon aus, dass Farben die häufig benutzt werden auch einen grösseren Anteil am Gesamtbild haben müssten.

    Quote

    Du hast da ungeheuer viele Graustufen in der Palette, aber kaum was aus dem Gelb-Dunkelgelben Bereich. Die zZeichnung in den Füßen sieht zwar fürs Auge sehr Grau aus, aber reingezoomt ist es doch eher Gelb.

    Na, ja. Bei dem Beispielbild sind halt diese Farben im Vordergrund. Die gelben Segmente sind halt eher klein.


    Werde erstmal implementieren dass ich die Palette laden kann, und dann probiere ich mal aus wie das Bild aussieht, wenn ich eine C64 Palette vorgebe.

    So habe ich das gemacht ...

    Quote from peiselulli

    So habe ich das gemacht ...

    Die Palette und die Bilddaten liegen vermutlich im sRGB-Raum, also mit gamma != 1 kodiert.


    Die Wandlung RGB -> YUV entspricht im wesentlichen einer linearen Matrizenmultiplikation, die Du hier aber mit den falschen Eingangsdaten (sowohl für die Paletteneinträge, also auch für das eigentliche Bildpixel) fütterst.


    Solange Du nicht ditherst, fällt das erstmal kaum auf - nur ein paar "Wände" im RGB- (oder YUV-) "Schaum-Bad" die den Farbraum "auftrennen" liegen leicht anders. Sobald Du aber ditherst, gibt's o.g. Überraschung mit fehlender Farbbalance und aufgehellten dunklen Bereichen.


    In meinem oben angehängten Source behandle ich die Palette und den Eingangspixel vorher mit gamma = 2.0 - das ist zwar verglichen mit sRGB auch noch nicht 100% korrekt, aber wesentlich genauer als fälschlicherweise gamma = 1.0 für Palette/Pixel anzunehmen.

    Hier mal als Referenz eine kleine Hilfe, mit der man einfach feststellen kann, welches gamma die eigene Anzeige hat:


    gamma.png


    Da, wo das Graustufen-Rechteck "verschwindet" kann man den gamma-Exponenten ablesen. Wichtig ist, daß die Pixel 1:1 darstellt werden, sonst funktioniert es nicht.


    Bei 1.0 hat das Rechteck den Grauwert 128 - zumindest auf meinem Display sieht es aber erheblich dunkler aus, als das Schachbrettmuster, welches ja die halbe Intensität von Weiß haben sollte ...