Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.comp.lang.iso-c++ > #2018 > unrolled thread

Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus...

Started byJörg "Yadgar" Bleimann <yazdegird@gmx.de>
First post2017-02-11 14:52 +0100
Last post2017-02-14 11:36 +0100
Articles 6 — 3 participants

Back to article view | Back to de.comp.lang.iso-c++

Contents

  Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus... Jörg "Yadgar" Bleimann <yazdegird@gmx.de> - 2017-02-11 14:52 +0100
    Re: Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus... Stefan Reuther <stefan.news@arcor.de> - 2017-02-12 11:00 +0100
      Re: Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus... Jörg "Yadgar" Bleimann <yazdegird@gmx.de> - 2017-02-12 21:43 +0100
      Re: Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus... Jörg "Yadgar" Bleimann <yazdegird@gmx.de> - 2017-02-12 20:34 +0100
    Re: Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus... Markus Schaaf <mschaaf@elaboris.de> - 2017-02-14 01:03 +0100
      Re: Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus... Jörg "Yadgar" Bleimann <yazdegird@gmx.de> - 2017-02-14 11:36 +0100

#2018 — Selbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus...

FromJörg "Yadgar" Bleimann <yazdegird@gmx.de>
Date2017-02-11 14:52 +0100
SubjectSelbstgestrickter Floyd-Steinberg-Filter sieht seltsam aus...
Message-ID<o7n4v0$emd$1@news.albasani.net>
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

[toc] | [next] | [standalone]

#2019

FromStefan Reuther <stefan.news@arcor.de>
Date2017-02-12 11:00 +0100
Message-ID<o7pf7i.4f8.1@stefan.msgid.phost.de>
In reply to#2018
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));
>       }
[...]
> 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

[toc] | [prev] | [next] | [standalone]

#2020

FromJörg "Yadgar" Bleimann <yazdegird@gmx.de>
Date2017-02-12 21:43 +0100
Message-ID<o7qhd0$4n8$1@news.albasani.net>
In reply to#2019
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 
char) umgestellt - am Ergebnis ändert sich leider nichts!

Bis bald im Khyberspace!

Yadgar

[toc] | [prev] | [next] | [standalone]

#2021

FromJörg "Yadgar" Bleimann <yazdegird@gmx.de>
Date2017-02-12 20:34 +0100
Message-ID<o7qdd5$ccr$1@news.albasani.net>
In reply to#2019
Hi(gh)!

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:

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...

Bis bald im Khyberspace!

Yadgar

[toc] | [prev] | [next] | [standalone]

#2022

FromMarkus Schaaf <mschaaf@elaboris.de>
Date2017-02-14 01:03 +0100
Message-ID<o7thdg$qt2$1@dont-email.me>
In reply to#2018
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:
> [...]

> 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

[toc] | [prev] | [next] | [standalone]

#2023

FromJörg "Yadgar" Bleimann <yazdegird@gmx.de>
Date2017-02-14 11:36 +0100
Message-ID<o7umkr$d2o$1@news.albasani.net>
In reply to#2022
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)

[toc] | [prev] | [standalone]

Back to top | Article view | de.comp.lang.iso-c++

csiph-web