Farbtiefe von 24Bit zu 16Bit

rapso

LinkeT schrieb:

waarum sollen verfälschungen im Weisbereich auftretten?

Hustbaer schrieb:

Wenn man allerdings vorher über ne fixe Matrix (oder auch Zufallszahlen) Werte von 0-7 draufrechnet, dann erweitert man den Wertebereich ja von 0-255 auf 0-262.

somit erhaelst du von 248 bis 262 den werte >=31.

hellihjb

habs errechnet ist "nur" faktor 4

wie das?

hustbaer

Also.

Wie ich auf *31/255 komme?
Da 255 nach Draufaddieren der Matrix 255-262 sein kann, 254 -> 254-261, 253 -> 253-260 etc. reicht es wenn nur 255 auf 31 abgebildet wird, alles andere auf <= 30, daher hab ich damals einfach *31/255 verwendet. Hat halbwegs richtig ausgehesen, ich hab nicht weiter darüber nachgedacht, deswegen bin ich bis jetzt dabei geblieben. Die ursprüngliche Forderung wird auch erfüllt, der grobe Fehler im Weissbereich ist weg, aber siehe 2)
Bin jetzt aber draufgekommen (nachdem ich mir das alles noch etwas genauer angesehen habe), dass es sowieso nicht optimal ist zuerst die dither-Werte drauf zu addieren, und dann zu multiplizieren/dividieren -- man sollte es umgekehrt machen. Wenn man zuerst addiert und dann multipliziert/dividiert erhält man unregelmässiges "banding" (die Abstände zwischen den Bändern sind mal 39 Werte, dann wieder 31 etc.). Besser wäre wohl:

v' = ((v * 249 + 124) / 256 + DITHER[x&3, y&3]) / 8

Wenn man so rechnet ist der Abstand zwischen den Bändern immer 34 oder 35, vor dem ersten Band liegen 17 Werte und nach dem letzten nochmal 17 - schöner könnte es nicht sein.
Also vorher den Bereich 0-255 auf 0-248 zusammenstauchen (da entsteht dann Banding, dafür regelmässig), und dann erst dithern (wo dann kein Banding mehr entsteht).

Das Rummultiplizieren/Dividieren ist kein Problem, da man es einfach durch einen Table-Lookup ersetzt

v' = ((v * 249 + 124) / 256 + DITHER[x&3, y&3]) / 8
wird also zu 
    v' = (LUT[v] + DITHER[x&3, y&3]) >> 3

Das ist die Beste Umrechnung die ich bis jetzt gefunden habe.

rapso

wenn man es schnell haben moechte

r_new = (r>>3) ^ ( ((r&7)+ DITHER[x&3, y&3])>>3 );

hellihjb

der nutzen der lut ist fragwuerdig.
tu' die dither-matrix doch fixedpoint, raeum' die 124 mit rein und shifte einmal am ende:

(v*249 + dither[][]) >> 11;

passt dann auch ganz gut in mmx.

hustbaer

hellihjb schrieb:

der nutzen der lut ist fragwuerdig.
tu' die dither-matrix doch fixedpoint, raeum' die 124 mit rein und shifte einmal am ende:
(v*249 + dither[][]) >> 11;
passt dann auch ganz gut in mmx.

Ok, die Multiplikation tut sicher nicht sooo weh.

xmarvel

Hi,

melde mich mal wieder nachdem ich einige Sachen mir durchgelesen und probiert habe.
Also die Sache sieht jetzt inmoment so das ich versuche den Floyd Steinberg Dithering Algorithmus zu implementieren.

Es sieht erstmal wie folgt aus:

#define IMAGEBUFFER 128 // image buffer size: 128*3Bytes(RGB) = 384 Bytes

typedef struct
{
	uint8_t B, G, R;
}RGBTriple;

typedef struct
{
	uint32_t width;
	uint32_t height;
	RGBTriple* pixels;
}BMPImage;

void writeBMPImage(uint8_t x, uint8_t y, uint16_t imageAddr);
void floydDithering(BMPImage* image);

IMAGEBUFFER ist deswegen da weil ich nicht genügend RAM zur Verfügung habe und ich das Bild in teilen laden muss eben in 384 Byte Stückchen.
so und jetzt wird es hässlich:

Floyd Steinberg Dithering exemplarisch angewendet auf Rot:

void floydDithering(BMPImage* image)
{
	int i=0, errorDiff=0;

	for (i=0; i<IMAGEBUFFER; i++)
	{
	//RED
		errorDiff = image->pixels[i].R - (image->pixels[i].R & 0xF8);

		if (i+1 < IMAGEBUFFER)
			image->pixels[i+1].R += (errorDiff*7) >> 4; // right (7/16)
		if (i-1+image->width < IMAGEBUFFER)
			image->pixels[i-1+image->width].R += (errorDiff*3) >> 4; // buttom-left (3/16)
		if (i+image->width < IMAGEBUFFER)
			image->pixels[i+image->width].R += (errorDiff*5) >> 4; // buttom (5/16)
		if (i+1+image->width < IMAGEBUFFER)
			image->pixels[i+1+image->width].R += (errorDiff*1) >> 4; // buttom-right (1/16)
	}
}

Problem ich weiss nicht wie die error differenz genau berechnet wird man sagt ja es soll die Differenz der Orginial Farbe und der nächst gelegende Farbe sein. Ist dann meine Error Differenz dann korrekt berechnet worden?

Dann hab ich noch eine Frage wo ich nicht weiss ob das am Algorithmus selber liegt oder vielleicht an der falschen Implentierung: Ich habe bei weissen Flächen immer ein Wechsel zwischen weiss und schwarz soll das so sein?

Ich habe am Anfang ganz vergessen zu sagen das ich das Dithering auf sehr kleine Bilder anwende ca. 96x96 Pixel gross bringen dann die Algorithmen überhaupt noch was?

Gruss,
xmarvel

hustbaer

Äh. Grundsätzlich sieht das nicht ganz verkehrt aus. Allerdings solltest du ein paar Dinge beachten und evtl. überdeknen ob du wirklich Floyd Steinberg Dithering verwenden willst wenn du so wenig Speicher zur Verfügung hast.

#1: Wenn du den Fehler durch 16 dividierst (bzw. mal 5/16tel etc. nimmst), dann solltest du beachten dass dabei Rundungsfehler entstehen -- bzw. die Kommastellen einfach weggeschnitten werden. Wenn als Ausgabe nur reines Schwarz bzw. reines Weiss zur Verfügung stehen, und das Bildmaterial welches reinkommt Werte von 0-255 hat, dann sind die Fehlerdifferenzen immer ordentlich gross, und die Rundungsfehler fallen nicht so stark auf. Wenn du dagegen von 24 Bit auf 16 Bit runterrechnest, dann sind die Fehler enstprechend klein, und "Fehler in der Fehlerberechung" fallen stärker auf.
Beispiel: soll = 17, darstellbarer Wert = 16 -> Fehler ist 1. Fehler * 7 / 16 = 0. Blöd.

Entweder du nimmst also 16 Bit integers her, und multiplizierst alles mit 16 oder gleich 32 bzw. 64 -- dann entstehen beim "Fehler aufteilen" entsprechend weniger Fehler.
Oder aber du teilst den Fehler so auf dass wenigstens die Summe stimmt, also so inetwa:

int error = ...;

    int error7 = (error * 7 + 8) / 16;
    int error5 = ((error - error7) * 5 + 4) / 9;
    int error3 = ((error - error7 - error5) * 3 + 2) / 4;
    int error1 = error - error7 - error5 - error3;

Geht natürlich langsamer, da eine Division durch 9 dabei ist. Allerdings kannst du *5 /9 auch z.B. durch *71 / 128 ersetzen -- stimmt zwar nicht 100%, sollte aber reichen.
Zumindest würde ich das mal ausprobieren, wenn die andere Option (uint16_t verwenden und mit mehr Präzision rechnen) aus irgendeinem Grund falchfällt.

#2: Du solltest "gesättigt" addieren, sollte auch klar sein. Also nicht r = r + fehler, sondern r = min(max(r + fehler, min_r_value), max_r_value).

#3: Du solltest nicht clippen, sondern runden. Also statt r = r & 0xF8 heisst das dann r = min((r + 4) & 0x1F8, 0xF8). Und weils hier gleich dazupasst: du solltest mit signed integers rechnen. Das Bild selbst darf dabei ruhig als unsigned Bytes vorliegen (wenn du "geästtigt" addierst kann im Framebuffer sowieso nie was landen was "den Rahmen sprengt"), bloss der Fehler kann negativ werden, das sollte man beachten.

#4: Das grösste Problem: Du solltest die Fehler die du z.B. beim letzten Pixel in einer Zeile (wenn die Kachel schmäler ist als das ganze Bild), bzw. auch in der letzten Reihe einer "Kachel" aufteilen willst irgendwo puffern. Tust du das nicht (so wie in deinem Programm z.B. wo du den Fehler einfach "wegwirfst"), werden vermutlich auch bei "nur" 24 -> 16 Bit Dithering hässliche Streifen sichtbar werden, nämlich dort do du "den Fehler unterschlagen" hast.
Eine einfache Möglichkeit wäre immer 2 komplette Zeilen in den Speicher zu laden. Eine Zeile ditherst du (A), auf die 2. kannst du den Fehler draufrechnen (B). Bist du mit einer Zeile fertig vertauscht du die Zeiger so dass B zu A wird (oder kopierst den Inhalt von B nach A), und lädst die nächste Zeile als neues B nach. Wenn es keine Zeile mehr nachzuladen gibt (also bevor du die letzte Zeile angehst), kannst du die alten Werte einfach in B stehen lassen, und die Fehler die du beim letzten Durchgang verteilst kannst du danach einfach wegwerfen.

Sollte es nicht möglich sein immer wenigstens 2 Zeilen zu laden würde ich empfehlen nicht gerade einen Error Diffusion Dither ala Floyd Steinberg zu verwenden, sondern eher einen einfachen Ordered Dither. Sieht auch um Welten besser aus als ohne Dithering, geht schnell und einfach zu berechnen, und du musst eben nicht irgendwelche alten Fehlerwerte "aufheben", sondern kannst jeden Pixel einzeln bearbeiten. Das einzig Wichtige dabei ist dann dass du weisst wo im fertigen Bild er steht (X und Y), damit du den richtigen Wert aus der Dither Matrix auswählen kannst.

So. Das sind zwar jetzt keine 100% definitiven Wahrheiten, aber zumindest die Sachen die ich mal ausprobieren würde. Sozusagen. Quasi.

p.S.: noch was zum Thema Fehler berechnen, weil du gefragt hast:

// lesen, quantisieren, fehler ausrechnen
    int red = image[x][y].red; // der Wert im Bild + ggf. bereits akkumulierte Fehler
    int red_out = min((red + 4) & 0x1F8, 0xF8); // der Wert den ich darstellen kann
    int red_error = red - red_out; // der Fehler "original Wert - darstellbaren Wert"

    // zurückschreiben & fehler verteilen
    image[x][y].red = red_out;
    image[x+1][y].red = (red_error * 7 + 8) / 16;
    //...

xmarvel

Hi,

erstmal danke für eure Hilfe hab das leider nicht geschafft mit dem Floyd Steinberg Algorithmus zu programmieren da das etwas komplizierter wurde mit dem wenigen RAM, ich konnte zwar zwei Zeilen des Bildes jeweils noch Zwischenspeichern laden aber ich hatte ziemliche Probleme im Array Bereich zu bleiben. (Ich werd den Algorithmus aber sicherlich später nochmal testen auf ein normalen PC)
Inoment benutze ich jetzt das Ordered Dither Matrix wie hustbaer empfohlen hat.
Die unterschiede mit und ohne Dithering bei so kleinen Bilder fallen zwar nicht so gross aus wie erhofft aber es ist ok.

Gruss,
xmarvel

LinkeT

warum zu wenig ram ?

naja ... egal

aber den algorytmuss würde ich persönlich nicht bei 16 bit benutzen .. klar fällt es auf .. aber da ist der aufwand tausendmal grösser als der effekt

rapso

xmarvel schrieb:

Hi,

erstmal danke für eure Hilfe hab das leider nicht geschafft mit dem Floyd Steinberg Algorithmus zu programmieren da das etwas komplizierter wurde mit dem wenigen RAM,

dithern sollte man inplace machen, da musst du nichts extra zwischenspeichern.