Discussion:
Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus...
(zu alt für eine Antwort)
Jörg "Yadgar" Bleimann
2017-02-11 13:52:18 UTC
Permalink
Hi(gh)!

Hi(gh)!

Mittlerweile habe ich es tatsächlich geschafft, im Rahmen meines
Kommandozeilen-Bildbearbeitungsprogramms "YIP" (Yadgar's Image Processor
- ImageMagick für Arme...) so etwas wie Floyd-Steinberg-Rasterung zu
programmieren, nach dem Artikel "Floyd-Steinberg" in der englischen
Wikipedia... in Pseudocode wird der Algorithmus dort so dargestellt:

for each y from top to bottom
for each x from left to right
oldpixel := pixel[x][y]
newpixel := find_closest_palette_color(oldpixel)
pixel[x][y] := newpixel
quant_error := oldpixel - newpixel
pixel[x + 1][y ] := pixel[x + 1][y ] + quant_error * 7 / 16
pixel[x - 1][y + 1] := pixel[x - 1][y + 1] + quant_error * 3 / 16
pixel[x ][y + 1] := pixel[x ][y + 1] + quant_error * 5 / 16
pixel[x + 1][y + 1] := pixel[x + 1][y + 1] + quant_error * 1 / 16

Bei mir in C++ sieht das so aus:

void floydsteinberg(vector<vector<pixel> > &img, vector<rgb> &pal)
{
unsigned short h = img.size();
unsigned short w = img[0].size();
unsigned short r, c, i;
unsigned short p = pal.size();
rgb t0, t1, t2, t3, t4, closest=pal.at(0);
rgb triple, dist;
float newred, newgreen, newblue;

for (r=0; r<h; r++)
{
for (c=0; c<w; c++)
{
img[r].at(c).get_all(triple);
t0 = triple;
t1 = {-1, -1, -1};
t2 = {-1, -1, -1};
t3 = {-1, -1, -1};
t4 = {-1, -1, -1};
if (c < w-1)
{
img[r].at(c+1).get_all(triple);
t1 = triple;
}
if (c > 0 && r < h-1)
{
img[r+1].at(c-1).get_all(triple);
t2 = triple;
}
if (r < h-1 )
{
img[r+1].at(c).get_all(triple);
t3 = triple;
}
if (c < w-1 && r < h-1 )
{
img[r+1].at(c+1).get_all(triple);
t4 = triple;
}
for (i=0; i<p; i++)
{
if (coldist(t0, pal.at(i)) < coldist(t0, closest))
closest = pal.at(i);
}
img[r].at(c).set_all(closest.red, closest.green, closest.blue);
dist.red = t0.red - closest.red;
dist.green = t0.green - closest.green;
dist.blue = t0.blue - closest.blue;
if (t1.red > -1)
{
img[r].at(c+1).get_all(triple);
newred = triple.red + dist.red*0.4375;
newgreen = triple.green + dist.green*0.4375;
newblue = triple.blue + dist.blue*0.4375;
img[r].at(c+1).set_all(mround(newred), mround(newgreen),
mround(newblue));
}
if (t2.red > -1)
{
img[r+1].at(c-1).get_all(triple);
newred = triple.red + dist.red*0.1875;
newgreen = triple.green + dist.green*0.1875;
newblue = triple.blue + dist.blue*0.1875;
img[r+1].at(c-1).set_all(mround(newred), mround(newgreen),
mround(newblue));
}
if (t3.red > -1)
{
img[r+1].at(c).get_all(triple);
newred = triple.red + dist.red*0.3125;
newgreen = triple.green + dist.green*0.3125;
newblue = triple.blue + dist.blue*0.3125;
img[r+1].at(c).set_all(mround(newred), mround(newgreen),
mround(newblue));
}
if (t4.red > -1)
{
img[r+1].at(c+1).get_all(triple);
newred = triple.red + dist.red*0.0625;
newgreen = triple.green + dist.green*0.0625;
newblue = triple.blue + dist.blue*0.0625;
img[r+1].at(c+1).set_all(mround(newred), mround(newgreen),
mround(newblue));
}

}
}


cout << "Floyd-Steinberg-Rasterung wird berechnet!" << endl;
}

"pixel" ist eine selbst entwickelte Klasse, "rgb" ein struct-Objekt für
Farbtripel.

Das Programm kompiliert problemlos (bis auf ein paar Warnungen wegen nur
in C++11 verfügbarer Funktionen), es gibt auch keinen Laufzeitfehler...
aber wenn ich mir die gerasterte Bilddatei (von RGB nach
1-bit-Schwarzweiß) ansehe, frage ich mich, was da falsch gelaufen ist -
wie Floyd-Steinberg-Schwarzweiß z. B. in GIMP sieht es nämlich nicht aus!

Hier das Original:
Loading Image...
... und das hier:
Loading Image...
ist die schwarzweiße gerasterte Version!

Bis bald im Khyberspace!

Yadgar
Stefan Reuther
2017-02-12 10:00:01 UTC
Permalink
Post by Jörg "Yadgar" Bleimann
dist.red = t0.red - closest.red;
dist.green = t0.green - closest.green;
dist.blue = t0.blue - closest.blue;
if (t1.red > -1)
{
img[r].at(c+1).get_all(triple);
newred = triple.red + dist.red*0.4375;
newgreen = triple.green + dist.green*0.4375;
newblue = triple.blue + dist.blue*0.4375;
img[r].at(c+1).set_all(mround(newred), mround(newgreen),
mround(newblue));
}
[...]
Post by Jörg "Yadgar" Bleimann
Das Programm kompiliert problemlos (bis auf ein paar Warnungen wegen nur
in C++11 verfügbarer Funktionen), es gibt auch keinen Laufzeitfehler...
aber wenn ich mir die gerasterte Bilddatei (von RGB nach
1-bit-Schwarzweiß) ansehe, frage ich mich, was da falsch gelaufen ist -
wie Floyd-Steinberg-Schwarzweiß z. B. in GIMP sieht es nämlich nicht aus!
Das war jetzt ziemlich viel Code, aber ein entscheidender Teil fehlt:
wie ist denn die rgb-Klasse definiert?

Da "meine" RGB-Klassen eigentlich immer uint8_t-Member haben, vermute
ich in dem oben zitierten Code sowas wie unsigned-Überläufe.

Ansonsten: kleines Bild (3x3?) nehmen, Code großräumig verprinten und
per Hand nachrechnen. Debuggen halt... Und nicht vergessen, das Ergebnis
hinterher als Unittest abzuspeichern :)


Stefan
Jörg "Yadgar" Bleimann
2017-02-12 20:43:11 UTC
Permalink
Post by Stefan Reuther
Da "meine" RGB-Klassen eigentlich immer uint8_t-Member haben, vermute
ich in dem oben zitierten Code sowas wie unsigned-Überläufe.
Ich habe jetzt die pixel-Klasse komplett auf short int (statt unsigned
char) umgestellt - am Ergebnis ändert sich leider nichts!

Bis bald im Khyberspace!

Yadgar
Jörg "Yadgar" Bleimann
2017-02-12 19:34:27 UTC
Permalink
Hi(gh)!
Post by Stefan Reuther
wie ist denn die rgb-Klasse definiert?
rgb ist keine Klasse, sondern eine (globale) structure:

struct rgb // global!
{
int red;
int green;
int blue;
};
Post by Stefan Reuther
Da "meine" RGB-Klassen eigentlich immer uint8_t-Member haben, vermute
ich in dem oben zitierten Code sowas wie unsigned-Überläufe.
Du meinst wahrscheinlich die "pixel"-Klasse... dort habe ich tatsächlich
unsigned char-Elemente verwendet, um Speicherplatz zu sparen:

class pixel
{
public:
pixel(); // Standard-Konstruktor
pixel (int, int, int); // Allgemeiner Konstruktor
~pixel(); // Destruktor
void set_all(int, int, int);
void set_all(unsigned char, unsigned char, unsigned char);
void set_red(int);
void set_red(unsigned char);
void set_green(int);
void set_green(unsigned char);
void set_blue(int);
void set_blue(unsigned char);
// void get_all(rgb&);
void get_all(rgb&);
unsigned char get_red();
unsigned char get_green();
unsigned char get_blue();
void invert();
void rgb2grey();
void rgb2grey(float, float, float);
float getvalue();
private:
unsigned char r;
unsigned char g;
unsigned char b;
unsigned char round(float);
};

Hätte ich besser short int genommen?
Post by Stefan Reuther
Ansonsten: kleines Bild (3x3?) nehmen, Code großräumig verprinten und
Großräumig verprinten? Also an möglichst vielen Stellen
Kontroll-Ausgaben einfügen?
Post by Stefan Reuther
per Hand nachrechnen. Debuggen halt... Und nicht vergessen, das Ergebnis
hinterher als Unittest abzuspeichern :)
Das leuchtet ein...

Bis bald im Khyberspace!

Yadgar
Markus Schaaf
2017-02-14 00:03:41 UTC
Permalink
Post by Jörg "Yadgar" Bleimann
Mittlerweile habe ich es tatsächlich geschafft, im Rahmen meines
Kommandozeilen-Bildbearbeitungsprogramms "YIP" (Yadgar's Image Processor
- ImageMagick für Arme...) so etwas wie Floyd-Steinberg-Rasterung zu
programmieren, nach dem Artikel "Floyd-Steinberg" in der englischen
for each y from top to bottom
for each x from left to right
oldpixel := pixel[x][y]
newpixel := find_closest_palette_color(oldpixel)
pixel[x][y] := newpixel
quant_error := oldpixel - newpixel
pixel[x + 1][y ] := pixel[x + 1][y ] + quant_error * 7 / 16
pixel[x - 1][y + 1] := pixel[x - 1][y + 1] + quant_error * 3 / 16
pixel[x ][y + 1] := pixel[x ][y + 1] + quant_error * 5 / 16
pixel[x + 1][y + 1] := pixel[x + 1][y + 1] + quant_error * 1 / 16
[...]
Das Programm kompiliert problemlos (bis auf ein paar Warnungen wegen nur
in C++11 verfügbarer Funktionen), es gibt auch keinen Laufzeitfehler...
aber wenn ich mir die gerasterte Bilddatei (von RGB nach
1-bit-Schwarzweiß) ansehe, frage ich mich, was da falsch gelaufen ist -
Aus Deiner Unterhaltung mit Stefan entnehme ich, dass das Problem
wahrscheinlich folgendes ist: (Zitat Wikipedia)

"For optimal dithering, the counting of quantization errors should be in
sufficient accuracy to prevent rounding errors from affecting the result."

Ich würde also dazu raten, für pixel(x+1,y) und die Zeile
pixel(left..right+1,y+1) temporären Speicher mit Fließkommapräzision
vorzusehen, oder ein Festkommaformat mit Skalierungsfaktor 16. Man könnte
den Algorithmus auch abwandeln und statt "nach vorn zu speichern", "nach
hinten schauen".

MfG
Jörg "Yadgar" Bleimann
2017-02-14 10:36:47 UTC
Permalink
Hi(gh)!
Post by Markus Schaaf
"For optimal dithering, the counting of quantization errors should be in
sufficient accuracy to prevent rounding errors from affecting the result."
Ich würde also dazu raten, für pixel(x+1,y) und die Zeile
pixel(left..right+1,y+1) temporären Speicher mit Fließkommapräzision
vorzusehen, oder ein Festkommaformat mit Skalierungsfaktor 16. Man könnte
den Algorithmus auch abwandeln und statt "nach vorn zu speichern", "nach
hinten schauen".
Das hat sich dann auch als Ursache für die Artefakte herausgestellt -
allerdings reichte es, die Klasse "pixel" von unsigned char auf short
int (16 bit) umzustellen, die Farbfehler dürften auf Überläufe
zurückzuführen sein.

Jetzt (Link:
Loading Image...) sieht es
annehmbar aus, wenn es auch nicht bitgleich zu dem ist, was die
Floyd-Steinberg-Funktion von GIMP fabriziert... eventuell könnte es
daran liegen, dass ich nur von links nach rechts, nicht ochsenwendig
abtaste!

Als Nächstes kommt eine Funktion zum horizontalen und vertikalen
Spiegeln von Bildern, da die Ladefunktion von TGAs mit
Koordinatenursprung oben links ausgeht... (fragt mich nicht nach anderen
Grafikformaten! Unkomprimiertes TGA ist das einzige, was ich bis jetzt
begriffen habe!)

Bis bald im Khyberspace!

Yadgar

Now playing: Slaughter on Tenth Avenue (Synergy)

Lesen Sie weiter auf narkive:
Loading...