Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (GNU/Linux, *NIX, *BSD und Co) » Floyd-Steinberg-Rasterung: seltsame Artefakte, Teil 1

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
23.01.2018, 21:26 Uhr
Yadgar



Hi(gh)!

Seit Monaten rechne ich meine selbst gerenderten oder per Digitalkamera gefilmten Videos in Atari ST-Monochrome-Modus (zunächst einmal nur in visueller Hinsicht, die Konvertierung in ein vom Atari ST lesbares Datenformat erfolgt später) um, und zwar ohne und mit Floyd-Steinberg-Rasterung. Die Routine für diese Rasterung habe ich gemäß der englischsprachigen Wikipedia-Seite zum Stichwort "Floyd-Steinberg dithering" implementiert, hier der Funktions-Code:


C++:
void floydsteinberg(vector<vector<pixel> > &img, vector<rgb> &pal) // Funktion bekommt Referenzen auf gesamtes Bild und verwendete Farbpalette übergeben
{
  unsigned short h = img.size(); // Bildhöhe
  unsigned short w = img[0].size(); // Bildbreite
  unsigned short r, c, i; // Bildzeile, Bildspalte, Zähler
  unsigned short p = pal.size(); // Anzahl der Farben in der verwendeten Palette
  rgb t0, t1, t2, t3, t4, closest=pal.at(0); // Aktuelles Pixel und rechts, links unten, unten und rechts unten angrenzende Pixel
  rgb triple, dist; // Puffer-Objekt für Pixel, Farbabstands-Tripel (im RGB-Farbraum)
  float newred, newgreen, newblue; // neue Farbwerte nach Fehlerdiffusion
  
  for (r=0; r<h; r++)
  {
    for (c=0; c<w; c++)
    {
      t0 = {-1, -1, -1}; // = triple
      t1 = {-1, -1, -1};
      t2 = {-1, -1, -1};
      t3 = {-1, -1, -1};
      t4 = {-1, -1, -1};
      t0.red = img[r].at(c).get_red();
      t0.green = img[r].at(c).get_green();
      t0.blue = img[r].at(c).get_blue();
      if (c < w-1) // falls Zeilenende noch nicht erreicht
      {
    t1.red = img[r].at(c+1).get_red();
    t1.green = img[r].at(c+1).get_green();
    t1.blue = img[r].at(c+1).get_blue();
      }
      if (c > 0 && r < h-1) // falls Pixel weder am linken noch am unteren Bildrand
      {
    t2.red = img[r+1].at(c-1).get_red();
    t2.green = img[r+1].at(c-1).get_green();            
    t2.blue = img[r+1].at(c-1).get_blue();            
      }
      if (r < h-1 ) // falls Pixel nicht am unteren Bildrand
      {
    t3.red = img[r+1].at(c).get_red();
    t3.green = img[r+1].at(c).get_green();
    t3.blue = img[r+1].at(c).get_blue();
      }
      if (c < w-1 && r < h-1 ) // falls Pixel weder am rechten noch am unteren Bildrand
      {
    t4.red = img[r+1].at(c+1).get_red();
    t4.green = img[r+1].at(c+1).get_green();
    t4.blue = img[r+1].at(c+1).get_blue();
      }          
      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));
      }
    }
  }
}



Zur Sicherheit auch noch die Rundungs-Routine mround():


C++:
int mround(double cv)
{
  int c;
  if (cv-floor(cv) < 0.5)
    c = floor(cv);
  else c = ceil(cv);
  
  return c;
}




Konkret kam es beim Umrechnen dieses Videos in Monochrom-Floyd-Steinberg und Atari ST-Auflösung (hier 533 x 400 Pixel) immer beim Überfliegen von Meeren oder größeren Binnenseen (normalerweise dunkelblau) zu vom Horizont "herunterlappenden" heller gerasterten Bereichen, die es dort den Originalfarben nach nicht geben dürfte:



Das Originalbild als PNG (mein in der Entwicklung befindliches Konsolen-Bildbearbeitungsprogramm "yip" kann nur unkomprimierte TGAs verarbeiten, daher hier noch der Link auf die TGA-Version)



Ist die Dokumentation des Floyd-Steinberg-Algorithmus in der Wikipedia unvollständig - oder habe ich beim Programmieren etwas übersehen?

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Dieser Post wurde am 23.01.2018 um 22:17 Uhr von Yadgar editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
24.01.2018, 13:37 Uhr
Yadgar



Hi(gh)!

Ich hatte beim Extrahieren der Einzelbilder aus der Floyd-Steinberg-gerasterten Version des Videos nicht daran gedacht, dass aufgrund einer Besonderheit (Bug?) von ffmpeg (Einzelbilder werden immer mit 25 fps extrahiert, egal, welchen Wert man für die Framerate angibt) die Floyd-Steinberg-Version gegenüber der farbigen Original-Version leicht beschleunigt ist (24 statt 25 fps), so dass die Framenummern nicht mehr zueinander passen (und natürlich auch manche Frames gar nicht vorkommen, da sie übersprungen werden). Hier jetzt zwei Frames, die wirklich einander entsprechen:

Original:



bzw. als auf 533 x 400 Pixel verkleinertes TGA, wie es von der Floyd-Steinberg-Routine in yip entgegengenommen wurde: Link

...und das, was diese Funktion dann daraus gemacht hat:



Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Dieser Post wurde am 24.01.2018 um 14:15 Uhr von Yadgar editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
24.01.2018, 16:38 Uhr
TOSHMAX



Hi Yadgar,

aus welchen Typen und Wertebereichen besteht denn ein pixel oder rgb? Könnte es sein, dass set_all die übergebenen Werte auf diesen Wertebereich zuschneidet? Dadurch würden im Verlauf des Algorithmus viele Informationen über die Fehler verloren gehen, was den weißen Bereich erklären könnte.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
24.01.2018, 19:44 Uhr
Yadgar




Zitat von TOSHMAX:
Hi Yadgar,

aus welchen Typen und Wertebereichen besteht denn ein pixel oder rgb? Könnte es sein, dass set_all die übergebenen Werte auf diesen Wertebereich zuschneidet? Dadurch würden im Verlauf des Algorithmus viele Informationen über die Fehler verloren gehen, was den weißen Bereich erklären könnte.


Die Klasse pixel:


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



...und die Struktur(!) rgb:


C++:
struct rgb // global!
{
  short red;
  short green;
  short blue;
};



Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
25.01.2018, 22:04 Uhr
TOSHMAX



Da ich mich in letzter Zeit selbst oft mit Bildverarbeitung beschäftige, habe ich mir das Ganze noch einmal etwas genauer angesehen.

Mit meiner Implementierung erhalte ich sehr ähnliche Ergebnisse, vor allem aber auch den weißen Bereich. Ich denke also, dass unsere Algorithmen grundsätzlich richtig sind.

Nach etwas herumspielen, z. B. mit einer Limitierung der Fehlerwerte bzw. hier mit einer vorherigen Konvertierung der Pixel in Graustufen konnte ich noch ein etwas besseres Bild erzeugen:


Verglichen mit GIMP ist da zwar noch viel Luft nach oben, vor allem im Bereich des Texts, aber deren Implementierung scheint auch weit über einfaches Floyd-Steinberg dithering hinaus zu gehen:
https://github.com/GNOME/gimp/blob/master/app/core/gimpimage-convert-indexed.c#L3908

Für den Text könnte es noch helfen die rote Farbe vorher in Weiß zu ändern. Dann sollte man zumindest das besser lesen können.

Dieser Post wurde am 25.01.2018 um 22:04 Uhr von TOSHMAX editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
28.01.2018, 11:26 Uhr
Yadgar



Hi(gh)!


Zitat von TOSHMAX:
Da ich mich in letzter Zeit selbst oft mit Bildverarbeitung beschäftige, habe ich mir das Nach etwas herumspielen, z. B. mit einer Limitierung der Fehlerwerte bzw. hier mit einer vorherigen Konvertierung der Pixel in Graustufen konnte ich noch ein etwas besseres Bild erzeugen:



Etwas besseres Bild? Das ist nahezu perfekt! Jedenfalls für schwarz-weißes Floyd-Steinberg-Dithering... verwende ich Floyd-Steinberg allerdings mit bunten Paletten ab 2 Farben, habe ich wieder das gleiche Problem, nämlich weitreichendes "Überschwappen" (mit ähnlich bogenförmigen Grenzen wie hier) bestimmter Farben in Bildregionen, wo sie definitiv nichts zu suchen haben... ich werde das bei Gelegenheit (wenn meine aktuelle Videoberechnung durchgelaufen ist - das dauert bei einem 40 Minuten langen Originalvideo insgesamt mehrere Tage!) mal hier posten!

Umrechnung in Graustufen hatte ich schon vor längerer Zeit in yip implementiert, so dass der neuerliche Programmieraufwand nicht groß sein dürfte...


Zitat von TOSHMAX:

Verglichen mit GIMP ist da zwar noch viel Luft nach oben, vor allem im Bereich des Texts, aber deren Implementierung scheint auch weit über einfaches Floyd-Steinberg dithering hinaus zu gehen:
https://github.com/GNOME/gimp/blob/master/app/core/gimpimage-convert-indexed.c#L3908



Ich staune... mittelfristig will ich allerdings auch noch andere Rasterverfahren wie z. B. Ordered Dither implementieren, da gibt eine schöne Seite zum Thema: www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/


Zitat von TOSHMAX:

Für den Text könnte es noch helfen die rote Farbe vorher in Weiß zu ändern. Dann sollte man zumindest das besser lesen können.


Das beträfe allerdings das ursprüngliche Rendering des Original-Videos mit POV-Ray und hat nichts mehr mit der Implementierung von Floyd-Steinberg zu tun - jedenfalls eine gute Idee für Earthflight 0.3 (wenn ich erst das Speicherproblem mit den Höhendaten-Meshes gelöst habe - aber das ist eine andere Baustelle!)!

Jedenfalls danke für deine Tips! Rechne schonmal damit, demnächst im Khyberspace (Afghatopia-2050-Modus) von den virtuellen Afghanen als segenbringender Sufi-Heiliger verehrt zu werden und Namensgeber für die eine oder andere kleine bis mittelgroße Moschee zu sein... Masjid-e Toshmax, das wäre doch was!

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Dieser Post wurde am 28.01.2018 um 11:30 Uhr von Yadgar editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
28.01.2018, 22:42 Uhr
Yadgar



Hi(gh)!


Zitat von TOSHMAX:

Nach etwas herumspielen, z. B. mit einer Limitierung der Fehlerwerte


Wie hast du die Fehlerwerte limitiert?

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
29.01.2018, 17:52 Uhr
TOSHMAX




Zitat von Yadgar:
Jedenfalls danke für deine Tips! Rechne schonmal damit, demnächst im Khyberspace (Afghatopia-2050-Modus) von den virtuellen Afghanen als segenbringender Sufi-Heiliger verehrt zu werden und Namensgeber für die eine oder andere kleine bis mittelgroße Moschee zu sein... Masjid-e Toshmax, das wäre doch was!

Na, schon mal danke dafür! Aber da hätte ich mir dann doch einen besseren Nutzernamen überlegen sollen .


Zitat von Yadgar:
Wie hast du die Fehlerwerte limitiert?

Bei mir ist das sehr einfach, da ich die Fehler unabhängig von den Pixeldaten in einem Array addiere. Eine Begrenzung auf +/- 255 hat dann recht gut funktioniert.

Das müsstest du wahrscheinlich so ähnlich machen, um zu wissen wie hoch genau der Fehler für ein bestimmtes Pixel ist. Aktuell addierst du die Fehler direkt zu den Pixeldaten. Das heißt ohne die Original-Daten lässt sich nicht mehr herausfinden wie hoch der Fehler ist und dementsprechend auch nichts mehr limitieren.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
20.02.2018, 00:05 Uhr
Yadgar



Hi(gh)!

Jetzt habe ich endlich eine "Earthflight 0.1"-Version mit der modifizierten Floyd-Steinberg-Funktion (mit vorherigem Umrechnen in Graustufen) fertiggstellt - und es sieht - auch ohne Fehler-Limitierung! - gut aus: https://www.youtube.com/watch?v=P6b0Zr40-kc

Nochmal danke für den Tipp, Toshmax!

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Dieser Post wurde am 20.02.2018 um 00:16 Uhr von Yadgar editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
21.02.2018, 10:01 Uhr
Yadgar



Hi(gh)!

Durch die von Toshmax' empfohlene vorherige Konvertierung der Frames in Graustufen verschwanden nicht nur die "Einlappungen" falscher Helligkeitsstufen, sondern auch jene merkwürdigen schwarzen und weißen "Blasen" im Bild, die seit dem Beginn meiner Videoexperimente immer wieder aufgetaucht waren:

POV-Ray-Beschleunigungstest, farbiges Original:
https://www.youtube.com/watch?v=E1_bq484eto

POV-Ray-Beschleunigungstest, Atari ST monochrom, Floyd-Steinberg-Rasterung mit Blasen-Artefakten:
https://www.youtube.com/watch?v=47DY2BeT5ic

POV-Ray-Beschleunigungstest, Atari ST monochrom, Floyd-Steinberg-Rasterung, verbesserte Version:
https://www.youtube.com/watch?v=Ax0SHQ5W1xo

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (GNU/Linux, *NIX, *BSD und Co) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: