fast Hilbert Dithering

Dithering mit der Hilbert-Kurve

1. Warum überhaupt Dithern?

Auch wenn es inzwischen zum Standard für PC’s geworden ist hat nicht jeder Computer die maximale Farbtiefe von 24 Bit (also 16 Millionen unterschiedliche Farben) zur Auswahl. In Zeiten, in denen viele Aufgaben immer mehr auf spezialisierte - billige und damit leistungsschwache - Kleinstrechner übertragen werden kann es auch wieder häufiger passieren, das man mit einer limitierten Auswahl an Farben auskommen muss.
Wenn man nun Bilder mit sehr vielen Farben (z.B. als Webbrowser oder Multimediaanwendung) auf einem Gerät mit weniger Farben darstellen will hat man wenig Auswahl - besonders wenn man sehr schnell arbeiten will. Die schnellste Methode ist in der Regel ein “GetNearestColor”-Blit, den jedes bessere Betriebsystem (BeOS, Windows, ...) standardmäßig nutzt und jeden Farbpunkt beim Kopieren der Grafik in den Bildschirmspeicher durch eine Farbe ersetzt, die in der derzeitigen Palette vorhanden ist und dem Ursprungspunkt am nächsten kommt. Das ist schnell, sieht aber auch oft nicht so gut aus:

ein Bild mit 16 Millionen Farben...

...das gleiche Bild mit GetNearestColor
in den 16 Standard-Windows Farben

Auch wenn man zunächst nicht davon ausgehen muss, das der zukünftige Anwender mit weniger als 16 Millionen Farben arbeiten wird ist es in vielen Fällen professioneller auch bei schlechten Farbtiefen noch einigermassen gut auszusehen. Ein Beispiel von dieser Professionalität ist der Be Taskmanager an dem wir gearbeitet haben und der das Dithering nur für den Blur und Alpha-Effekt in seiner About-Box eingebaut hat (selbstverständlich war auch die interessante Implementierung des Hilbert-Ditherns ein ausschlaggebender Grund für dieses Feature).

Die Möglichkeit, die Qualität des Bildes unter dieser Farblimitierung zu verbessern ist Dithern. Grundsätzlich versucht ein Ditheralgorithmus den Fehler, der bei jedem Punkt bei GetNearestColor autritt auf seine umliegenden Punkte weiterzugeben, und damit den Fehler annähernd auszugleichen - wobei dann ein typisches Punktemuster entsteht. Das ist normalerweise nicht besonders schnell, da ja nicht nur ein Punkt sondern für jeden Punkt gleich ein ganzer Haufen anderer Punkte verarbeitet werden müssen.

Eine schnelle - und deswegen häufig benutzte Methode ist das “ordered Dither”. Für jede der 256 möglichen Werte einer Farbkomponente (die da wären: Rot, Grün und Blau) liegt ein Muster in einer Tabelle vor, das insgesamt diesen Farbwert auf die vorhandene Palette dithert. Da diese Tabelle alle paar Punkte wiederholt wird sind die Muster im Ergebnissbild sehr regelmäßig.

die 16 Standard-Windows Farben
und ordered Dither

Das beste Ergebniss allerdings bekommt man mit “error diffusion”, dessen bekanntester Vertreter der Floyd-Steinberg Algorithmus ist. Dieser - gegenüber den anderen vorgestellten Verfahren - in der Regel langsame Algorithmus verteilt die Fehler der einzelnen Punkte korrekt und liefert ein bestmögliches Bild.

die 16 Standard-Windows Farben
und error-diffusion

2. Die Hilbert-Kurve

Die Hilbert-Kurve ist ein flächenfüllendes Fraktal, das in einem quadratischen Bild mit einer Seitenlänge einer Quadratzahl jeden Punkt einmal besucht. Sie ist das Trumm der Wahl, das unseren Dither-Algorithmus durchs Bild schickt, damit er die Fehler möglichst diffus an die nächsten Punkte weitergibt. Das bedeutet, das eine Hilbert-Kurve nur Flächen der Größe 2x2, 4x4, 8x8 etc ausfüllen kann - was natürlich zunächst ein Problem aufwirft!
Die Generierung der Hilbert-Kurfe ist ein rekursiver Algorithmus. Das heisst: jede grosse Kurve wird aus vielen kleinen Kurven zusammengebaut, die wiederum letztendlich aus kleinen Elementar-Kurven bestehen. Die Elementar-Kurven werden von Vektoren “zusammengeklebt” und werden so immer größer. Ein solcher Vektor geht immer nur nach oben, nach unten, links oder rechts.

Eine Elementarkurve füllt einen 2x2 Raum und wird bei größeren Kurven mit Vektoren aneinandergehängt. Die Regeln für das aneinanderhängen sieht man im unteren Bild:

Regeln für das aneinanderhängen
von ElementarKurven

Entsprechende Hilbert Kurven sehen dann so aus:

Level 2 Hilbert Kurve

Level 3 Hilbert Kurve

Das Problem ist nun, das unsere Eingangs-Bilder nicht immer quadratisch sind und die Seitenlänge nur selten einer Quadratzahl entspricht. Um das Problem zu lösen sollte man wissen, das die Hilbertkurve symmetrisch zu ihrer Vertikalen sind, was heisst, das wenn die Kurve oben links anfängt hört sie garantiert rechts oben auf!
Um eine Kurve zu erzeugen die jeden beliebigen Raum mit Hilbert-Kurven füllt habe ich einen HilbertController geschrieben, der (teilweise um 90 Grad gedrehte) Hilbert-Kurven so aneinanderhaengt, das der gesamte Raum ausgefüllt wird - zwei Beispiele finden sie hier:

Der HilbertController hat 4 wesentliche Funktionen.

versucht er die grösstmöglichste Hilbert-Kurve zu finden und nutzt sie als Start für weitere Aktionen

füllt er den rechten Bereich - so, das der Ende des Pfades unten rechts neben der grossen Hilbert-Kurve ist. Die cyanen Hilbert-Kurven im Bild gehen statt von oben-links/oben-rechts nach unten-rechts/unten links. In diesem Beispiel werden die Enden durch Elementar-Kurven (rot) verbunden, die von oben-links/unten-links gehen.

der Bereich unten rechts wird ausgefüllt. Dabei versucht der Algorithmus von oben links nach unten links zu kommen. Nicht immer kann das erreicht werden. Manchmal muss ganz zum Schluss (wie in diesem Beispiel) noch eine Reihe Elementarkurven gezogen werden.

Unten links wird ausgefüllt. Nun geht es von unten/rechts nach unten/links ...
Voila !!

Hier ist noch ein Beispiel. Gut zu sehen: die rote Hilbert-Kurve (oben/links - unten/links) wird genutzt den der rechte Rest-Bereich zufällig einer Quadratzahl entspricht.

Gefunden habe ich die Hilbert-Kurve zum ersten Mal bei

http://ourworld.compuserve.com/homepages/compuphase/hilbert.htm oder
http://www.compuphase.com/hilbert.htm , in dem auch weiterführende Referenzen zu einem Buch “Algorithms + Data structures = Programs”, 1976 von Niklaus Wirth zu finden sind.

Hier ist ein C++ Code-Snipped den ich so zur Generierung einer Standard-Hilbert Kurve verwende. Sie ist leicht optimiert worden. Unter Windows würde die Calling-Convention __fastcall noch etwas an Geschwindigkeit bringen!

/* die normale Hilbert-Kurve.

         Start: Top-Left  Ende: Top-Right */
void CFBitmap::hilbertTLTR(int level,int direction)

                                                    { level--;

        if (!level)

        { switch(direction)
    { case LEFT:
        moveRIGHT();

                                                            moveDOWN();
        moveLEFT();
        break;

                                                          case RIGHT:
        moveLEFT();
        moveUP();

                                                            moveRIGHT();
        break;
      case UP:

                                                            moveDOWN();
        moveRIGHT();
        moveUP();

                                                            break;
      case DOWN:
        moveUP();

                                                            moveLEFT();
        moveDOWN();
        break;
    }

                                                      } else {
    if (level==1) // little Optimisation
    { switch(direction)
      { case LEFT:

                                                               moveDOWN();
           moveRIGHT();

                                                               moveUP();
          moveRIGHT();

                                                               moveRIGHT();
           moveDOWN();

                                                               moveLEFT();
          moveDOWN();

                                                               moveRIGHT();
           moveDOWN();

                                                               moveLEFT();
          moveLEFT();

                                                               moveUP();
           moveLEFT();

                                                               moveDOWN();
          break;
        case RIGHT:
                                                    
           moveUP();
           moveLEFT();

                                                               moveDOWN();
          moveLEFT();

                                                               moveLEFT();
           moveUP();

                                                               moveRIGHT();
          moveUP();

                                                               moveLEFT();
           moveUP();

                                                               moveRIGHT();
          moveRIGHT();

                                                               moveDOWN();
           moveRIGHT();

                                                               moveUP();
          break;
        case UP:

                                                               moveRIGHT();  
           moveDOWN();

                                                               moveLEFT();
          moveDOWN();

                                                               moveDOWN();
           moveRIGHT();

                                                               moveUP();
          moveRIGHT();

                                                               moveDOWN();
           moveRIGHT();

                                                               moveUP();
          moveUP();

                                                               moveLEFT();
           moveUP();

                                                               moveRIGHT();
          break;
        case DOWN:
                                                    
           moveLEFT();
           moveUP();

                                                               moveRIGHT();
          moveUP();

                                                               moveUP();
           moveLEFT();

                                                               moveDOWN();
          moveLEFT();

                                                               moveUP();
           moveLEFT();

                                                               moveDOWN();
          moveDOWN();


                                                               moveRIGHT();
           moveDOWN();

                                                               moveLEFT();
          break;      

                                                          } // /switch
    } else {
      switch(direction)
      { case LEFT:

                                                              hilbertTLTR(level,UP);
          moveRIGHT();

                                                              hilbertTLTR(level,LEFT);
          moveDOWN();

                                                              hilbertTLTR(level,LEFT);
          moveLEFT();

                                                              hilbertTLTR(level,DOWN);
          break;

                                                            case RIGHT:
          hilbertTLTR(level,DOWN);

                                                              moveLEFT();
          hilbertTLTR(level,RIGHT);

                                                              moveUP();
          hilbertTLTR(level,RIGHT);

                                                              moveRIGHT();
          hilbertTLTR(level,UP);

                                                              break;
        case UP:

                                                              hilbertTLTR(level,LEFT);
          moveDOWN();

                                                              hilbertTLTR(level,UP);
          moveRIGHT();

                                                              hilbertTLTR(level,UP);
          moveUP();

                                                              hilbertTLTR(level,RIGHT);
          break;

                                                            case DOWN:
          hilbertTLTR(level,RIGHT);

                                                              moveUP();
          hilbertTLTR(level,DOWN);

                                                              moveLEFT();
          hilbertTLTR(level,DOWN);

                                                              moveDOWN();
          hilbertTLTR(level,LEFT);

                                                              break;      
      } // /switch
    }
  }
}

3. Dithern mit der Hilbert-Kurve

Das schöne am Dithern mit der Hilbert-Kurve ist das die Kurve schnell aufgebaut werden kann - der eigentliche Dither-Algorithmus jedoch auf eine Dimension runtergebrochen wird. Dadurch wird das Dithern sehr schnell - bei einer Qualität, die dem Floyd-Steinberg Algorithmus ziemlich nahekommt.

Bild im Original in TrueColor

Bild mit einer festen BeOS Palette
und einer Hilbert-Kurve gedithered

Ein guter Ditheralgorithmus verteilt nicht nur den Fehler in die umliegenden Punkte, sondern lässt den Fehler mit dem größerwerdenden Abstand zum Ursprungspixel linear verschwinden.
Eine bessere Beschreibung dazu gibt es bei http://ourworld.compuserve.com/homepages/compuphase/riemer.htm

Mein Algorithmus arbeitet ein bischen unsauberer. Er überträgt den Fehler immer auf den nächsten Pixel - nur der Über- oder Unterlauf wird halbiert. Das Ergebniss sehen Sie links.

Code-Snipped einer 256-Farb Dither Routine, die von einem Move-Teil der Hilbert-Kurve aufgerufen werden. CFBitmap::color ist der Return-Wert des letzten Pixels. Die Routine kann noch optimiert werden - dieses Beispiel verrichtet aber schon schön schnell seine Arbeit.

/* 8-Bit BeOS Dither */

                                            CFBitmap::color CFBitmap::Dither256(

                                              CFBitmap::color coloraddin

                                                                                          )

                                            { int16 r=((*(srcbuffer)  )+coloraddin.r;

                                              int16 g=((*(srcbuffer+1))+coloraddin.g;

                                              int16 b=((*(srcbuffer+2))+coloraddin.b;
                                                                                        

                                              uint8 rt,gt,bt; 

                                              if (r>0xFF) { rt=0xFF; r=(r-0xFF)/2+0xFF; } 

                                                else if (r<0) { rt=0; r=r/2; } else {rt=r;}

                                                                                          if (g>0xFF) { gt=0xFF; g=(g-0xFF)/2+0xFF; } 

                                                else if (g<0) { gt=0; g=g/2; } else {gt=g;}

                                                                                          if (b>0xFF) { bt=0xFF; b=(b-0xFF)/2+0xFF; } 

                                                else if (b<0) { bt=0; b=b/2; } else {bt=b;}

                                                                                          uint8 tmp=screen->IndexForColor(rt,gt,bt);

                                              rgb_color bestFit = cm->color_list[*target=tmp];

                                              coloraddin.r=(int16)r-bestFit.red;
                                                                                        

                                              coloraddin.g=(int16)g-bestFit.green;

                                              coloraddin.b=(int16)b-bestFit.blue;  

                                              return coloraddin;

                                            }

OriginalBild in TrueColor

in 256-Farben gedithered unter der BeOS-StandardPalette

4. Links

Riemersma Dither - Artikel, der in der C/C++ User’s Journal stand
The Hilber Curve - mit dem Riemersma Artikel zusammenhängend
Be Taskmanager Seite - Implementierung des Hilbert-Ditherns in der About-Box

5. Zukunft

Es gibt eine rekursionsfreie Variante des Hilbert - Ditherers, die etwas schneller sein könnte als das hier vorgestellte Verfahren. Zudem habe ich eine Variante unter Windows geschaffen, die auf Paletten eingehen kann, dies alles werde ich mal dokumentieren und auf www.3rd-evolution.de als Artikel und Source bereitstellen wenn ich mal wieder Zeit habe.

Top