Dithering

Wenn einerseits die beiden ''Farben'' Schwarz und Weiß zur Färbung der Objekte nicht ausreichen, andererseits der Bildschirm aber nur schwarze Pixel darstellen kann, wird wieder zu einem Trick gegriffen, bei dem das menschliche Auge betrogen wird.
Das Auge kann bei normalen Lichtverhältnissen Details unterscheiden, die mindestens eine Bogenminute ($1/60$ Grad) auseinander liegen. Wenn man in eine weiße Fläche eine Anzahl $a$ von nicht benachbarten schwarzen Punkten hineinzeichnet und diese Fläche dann aus grösserer Entfernung betrachtet, dann ist das Auge nicht mehr in der Lage, die einzelnen Punkte voneinander zu unterscheiden. Die schwarzen und weißen Bereiche werden vom Auge integriert und dadurch entsteht der Eindruck einer grauen Fläche. Je größer $a$ ist, desto dunkler wirkt die Fläche. Damit die Fläche gleichmäßig gefärbt erscheint, wird versucht die Punkte möglichst gleichmäßig zu verteilen. Eine Möglichkeit dies zu tun, ist das Dithering.

Eine $n \times n$-Dithermatrix $D$ ist mit den $n^2$ Zahlen zwischen $0$ und $n^{2} - 1$ besetzt. Zum Färben einer Fläche mit Grauwert $k,0 \leq k \leq n^{2}$ werden alle Pixel $(i, j)$ gesetzt mit $D[i~ \bmod ~ n, j~ \bmod ~ n] < k$. Abbildung 4.8 zeigt das Füllmuster zum Schwellwert 7.

Die $n^2$ Zahlen können auf verschiedene Weisen auf die Matrix verteilt werden. Wir werden die Matrix nach dem Schema des ordered dithering füllen. Dabei wird die Matrix $D_n$ rekursiv aus der Matrix $D_{n-1}$ gebildet:

$$D_n = \left ( \begin{array}{cc} 4 \cdot D_{n-1} & 4 \cdot D... ...cdot U_{n-1}& 4 \cdot D_{n-1} + U_{n-1} \end{array} \right )$$

Dabei bezeichnet $U_n$ eine $n \times n$-Einheitsmatrix; d.h. alle Elemente der Hauptdiagonalen enthalten eine 1 und die restlichen Elemente sind 0.

Es ergeben sich:

$$D_0 = (0);\quad D_1 = \left ( \begin{array}{cc} 0 & 2\\ ... ...\\ 3 & 11 & 1 & 9 \\ 15 & 7 & 13 & 5 \end{array} \right )$$

Abbildung 4.8: Zum Schwellwert 7 gehörender Grauwert

public class DitherMatrix extends NxNMatrix{

  /**
   * Gibt eine DitherMatrix zurueck, die mit Ditherwerten gefuellt ist.
   * @param n die Matrix ist (2 hoch n)x(2 hoch n) Elemente gross und
   * enthaelt die (2 hoch 2n) Ditherwerte von 0 bis (2 hoch 2n) - 1.
   */
  public DitherMatrix(int n) {
    super((int)Math.pow(2,n), 0.0);              // mit Nullen fuellen

    if(n != 0) {                                 // bei n==0 ist man fertig
      DitherMatrix dd = new DitherMatrix(n-1);   // 1/4 grosse DitherMatrix
                                                 // besorgen und die
      fill(0, 0, 0, dd);                         // Quadranten fuellen: ul
      fill(1, 1, 1, dd);                         // lr
      fill(1, 0, 2, dd);                         // ur
      fill(0, 1, 3, dd);                         // ll
    }
  }

  private void fill(int s, int z, int add, DitherMatrix dd) {
    int size = dd.size();                        // Ausmasse besorgen
    for(int i=0; i < size; i++) {                // passenden Quadranten 
      for(int j=0; j < size; j++) {              // fuellen
        val[size*z+i][size*s+j]=4*dd.val[i][j] + add;
      }
    }
  }

  /**
   * Liefert zurueck, ob die Abbildung des uebergebenen Punktes in die
   * Matrix auf ein Matrixelement trifft, das kleiner als die uebergebene 
   * Schwelle ist.
   * @param x, y  der zu testende Punkt
   * @param schwelle der Schwellwert
   */
  public boolean kleinerSchwelle(int x, int y, int schwelle) {
    if((x < 0) || (y < 0)) {                     // Wert(e) sinnvoll?
      return false;                              // Falls nicht: Abbruch
    }
    else {                                       // Sonst: Werte mit Modulo
      return (val[x%n][y%n] < schwelle);         // in Matrix abbilden und
    }                                            // Ergebnis zurueck
  }
}