Fehlerkorrekturverfahren

Durch die Quantisierung der Farbwerte und durch das Dithering (insbesondere bei einer Dithermatrix mit $n=1$) entstehen Fehler, die man jedoch weitgehend ausgleichen kann, wobei allerdings Einbußen beim Kontrast hingenommen werden müssen.

Man unterscheidet:

• Fehlerverteilungsverfahren
• Fehlerdiffusionsverfahren

Fehlerverteilungsverfahren

Idee: (nach Floyd-Steinberg) Der Fehler, der bei der Quantisierung bei einem Pixel entsteht, wird auf einige Nachbarpixel gewichtet verteilt, die noch nicht dargestellt worden sind.

Sei $C_{org}$ Farb/Grau-Wert eines Pixels des Originalbild und $C_{qua}$ der quantisierte Wert. Der zu verteilende Fehler berechnet sich zu:

$$\Delta C = \omega\cdot(C_{org}-C_{qua})$$

wobei $\omega\in[0,1]$ ein zusätzlicher Gewichtsfaktor ist.

Wir wollen keine Formeln schreiben, sondern die Fehlerverteilung anhand vom Grafiken veranschaulichen:

Um den Fehler auch am Ende einer Zeile verteilen zu können, läuft man abwechselnd von links nach rechts und dann von rechts nach links.

Eigenschaften:

• es können (bei feinen Strukturen) ``Geisterbilder'' entstehen
• inhärent sequentiell, d.h. nicht parallelisierbar

Fehlerdiffusionsverfahren

Idee: (nach Knuth) Kachele das Bild mit einer Diffusionsmatrix und verteile den Fehler bei der Quantisierung des Wertes eines Pixels auf alle Nachbarpixel mit größerem Eintrag in der Diffusionsmatrix.

Beispiele für Diffusionsmatrizen:

$$\left(\begin{array}{cccccccc} 34 & 48 & 40 & 32 & 29 & 15 ... ... \\ 17 & 9 & 5 & 19 & 27 & 49 & 41 & 37 \end{array}\right)$$

Einträge ohne größeren Nachbarn nennt man Barone, solche mit nur einem größeren Nachbarn Fastbarone.

Bei der Diffusion des Fehlers auf die Nachbarn wird eine Gewichtung vorgenommen (siehe hierzu Literatur).

Eine weitere Verbesserung erreicht man durch eine Kantenverstärkung mithilfe folgender Operation:

$$I^{\prime}(x,y) = \alpha\cdot I(x,y)+(1-\alpha)\cdot\bar I(x,y)$$

wobei $\bar I$ durch eine diskrete Konvolution des Orginalbildes entsteht:

$$\begin{eqnarray*} \bar I(x,y) &=& (I\star K)(x,y) \\ &=& \sum_{u=-d}^{d}\sum_{v=-d}^{v=d} I(x+u,x+v)\cdot K(d-u,d-v) \end{eqnarray*}$$

Eine einfache Konvolutionsmatrix zur Kantenverstärkung mit $d=1$ ist:

$$K=\left(\begin{array}{ccc}1/9 & 1/9 & 1/9\\ 1/9 & 1/9 & 1/9\\ 1/9 & 1/9 & 1/9\end{array}\right)$$

d.h. $\bar I(x,y)$ ist der Mittelwert von $I(x,y)$ mit allen seinen 8 Nachbarpixeln.

Eigenschaften:

• bei geringer Auflösung (Monitore) geringfügig schlechtere Qualität als Fehlerverteilungsverfahren
• bei hoher Auflösung (Drucker) deutlich bessere Qualität als Fehlerverteilungsverfahren
• gut parallelisierbar

optimale Auswahl

hierbei sind:

• $N$ Anzahl der Pixel des Bildes
• $\cal N$ Nachbarschaft (Filtergröße)
• $w_{ij}$ Filterkoeffizienten (positioniert an $i$ und betrachtet an Nachbarschaftsstelle $j$)
• $M_{jv}$ Entscheidungsmatrizen (d.h. nur an einer Stelle hat eine Matrix eine 1 sonst alles 0)
• $K$ Anzahl der Farben
• $y_v$ Farbwert aus einer $K$-großen Tabelle
• $x_i$ original Farbwerte

mache Farbdiskretisierung und Farbzuordnung mit einem Optimierungsverfahren (siehe hierzu Bildverarbeitung, Signaltheorie, Optimierungstheorie), d.h. minimiere $H(M,Y)$