Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus...
8 views
Skip to first unread message
Jörg "Yadgar" Bleimann
Feb 11, 2017, 7:00:03 PM2/11/17
to
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:
http://www.rock-o-data.de/fotos/Yadgar.png
... und das hier:
http://www.rock-o-data.de/fotos/Yadgar_monochrome.png
ist die schwarzweiße gerasterte Version!
Bis bald im Khyberspace!
Yadgar
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:
http://www.rock-o-data.de/fotos/Yadgar.png
... und das hier:
http://www.rock-o-data.de/fotos/Yadgar_monochrome.png
ist die schwarzweiße gerasterte Version!
Bis bald im Khyberspace!
Yadgar
Stefan Reuther
Feb 12, 2017, 5:10:08 AM2/12/17
to
Am 11.02.2017 um 14:52 schrieb 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));
> }
[...]
> 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));
> }
> 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:
> 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!
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
Feb 12, 2017, 4:40:03 PM2/12/17
to
Am 12.02.2017 um 11:00 schrieb 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
> Da "meine" RGB-Klassen eigentlich immer uint8_t-Member haben, vermute
> ich in dem oben zitierten Code sowas wie unsigned-Überläufe.
char) umgestellt - am Ergebnis ändert sich leider nichts!
Jörg "Yadgar" Bleimann
Feb 12, 2017, 4:40:04 PM2/12/17
to
Hi(gh)!
Am 12.02.2017 um 11:00 schrieb Stefan Reuther:
struct rgb // global!
{
int red;
int green;
int blue;
};
>
> 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?
> 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?
> per Hand nachrechnen. Debuggen halt... Und nicht vergessen, das Ergebnis
> hinterher als Unittest abzuspeichern :)
Das leuchtet ein...
Am 12.02.2017 um 11:00 schrieb Stefan Reuther:
> Am 11.02.2017 um 14:52 schrieb Jörg "Yadgar" Bleimann:
> Das war jetzt ziemlich viel Code, aber ein entscheidender Teil fehlt:
> wie ist denn die rgb-Klasse definiert?
rgb ist keine Klasse, sondern eine (globale) structure:
> Das war jetzt ziemlich viel Code, aber ein entscheidender Teil fehlt:
> wie ist denn die rgb-Klasse definiert?
struct rgb // global!
{
int red;
int green;
int blue;
};
>
> Da "meine" RGB-Klassen eigentlich immer uint8_t-Member haben, vermute
> ich in dem oben zitierten Code sowas wie unsigned-Überläufe.
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?
> Ansonsten: kleines Bild (3x3?) nehmen, Code großräumig verprinten und
Kontroll-Ausgaben einfügen?
> per Hand nachrechnen. Debuggen halt... Und nicht vergessen, das Ergebnis
> hinterher als Unittest abzuspeichern :)
Markus Schaaf
Feb 14, 2017, 4:10:05 AM2/14/17
to
Am 11.02.2017 um 14:52 schrieb 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
> 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:
> [...]
> 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:
> 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 -
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
Feb 14, 2017, 6:50:03 AM2/14/17
to
Hi(gh)!
On 14.02.2017 01:03, Markus Schaaf wrote:
> "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:
http://www.rock-o-data.de/fotos/Yadgar_monochrome_correct.png) 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)
On 14.02.2017 01:03, Markus Schaaf wrote:
> "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".
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:
http://www.rock-o-data.de/fotos/Yadgar_monochrome_correct.png) 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
0 new messages