Dithering — Parte III — Dithering com Difusão de Erro e o algoritmo de Floyd-Steinberg

Dithering (pontilhado) com difusão de erro é uma técnica de halftone que procura distribuir a diferença entre o valor exato de cada pixel e seu valor aproximado a um conjunto de pixels adjacentes. Diversas técnicas foram desenvolvidas com esta proposta, sendo o algoritmo de Floyd-Steinberg o primeiro desenvolvido utilizando esta abordagem.

Tal algoritmo pode ser apresentada a partir da seguinte implementação:

def floyd_steinberg(originalImage):
    ''' Floyd-Steinberg Dithering Algorithm.
 
    dithered = floyd_steinberg(originalImage)
 
    Parameters
    ----------
    originalImage: numpy ndarray, original image
 
    Return
    ----------
    dithered: numpy ndarray, dithered image
 
    References
    ----------
    http://en.wikipedia.org/wiki/Floyd-Steinberg
 
    Written by Pedro Garcia Freitas [sawp@sawp.com.br]
    Copyright 2010 by Pedro Garcia Freitas
 
    see: http://www.sawp.com.br
    '''
    (M, N) = originalImage.shape
    threshold = 127.5
    tmp = originalImage.copy()
    dithered = zeros((M, N))
    (M, N) = (M - 1, N - 1)
    error = 0
 
    for row in xrange(M):
        dithered[row, 0] = 255 * int(tmp[row, 0] >= threshold)
        error = - dithered[row, 0] + tmp[row, 0]
        tmp[row, 1] = 0.4375 * error + tmp[row, 1]
        tmp[row + 1, 1] = 0.0625 * error + tmp[row + 1, 1]
        tmp[row + 1, 0] = 0.3125 * error + tmp[row + 1, 0]
 
        for col in xrange(1, N):
            dithered[row, col] = 255.0 * int(tmp[row, col] >= threshold)
            error = - dithered[row, col] + tmp[row, col]
            tmp[row, col + 1] = 0.4375 * error + tmp[row, col + 1]
            tmp[row + 1, col + 1] = 0.0625 * error + tmp[row + 1, col + 1]
            tmp[row + 1, col] = 0.3125 * error + tmp[row + 1, col]
            tmp[row + 1, col - 1] = 0.1875 * error + tmp[row + 1, col - 1]
 
        dithered[row, N] = 255 * int(tmp[row, N] >= threshold)
        error = - dithered[row, N] + tmp[row, N]
        tmp[row + 1, N] = 0.3125 * error + tmp[row + 1, N]
        tmp[row + 1, N - 1] = 0.1875 * error + tmp[row + 1, N - 1]
 
    dithered[row, 0] = 255 * int(tmp[row, 0] >= threshold)
    error = - dithered[row, 0] + tmp[row, 0]
    tmp[row, 1] = 0.4375 * error + tmp[row, 1]
 
    for col in xrange(1, N):
        dithered[row, col] = 255 * (tmp[row, col] >= threshold)
        error = - dithered[row, col] + tmp[row, col]
        tmp[row, col + 1] = 0.4375 * error + tmp[row, col + 1]
 
    dithered[row, N] = 255 * (tmp[row, N] >= threshold)
    return dithered

Devemos notar que os valores multiplicados ao erro são pesos que formam a distribuição característica desse algoritmo. Esta forma de distribuição de erro é ilustrada na seguinte matriz:


\(
\begin{array}{| c | c | c | }
\hline
0 & 0 & 0 \\ \hline
0 & f(x,y) & 7/16 \\ \hline
3/16 & 5/16 & 1/16 \\
\hline
\end{array}
\)

O resultado da aplicação desta técnica de pontilhado pode ser vista nas imagens abaixo:

Original (entrada) Halftoned (saída)

A partir dos resultados acima, podemos notar o efeito de “respingo” que a imagem binária apresenta. Isso ocorre porque a ordem na qual a imagem é percorrida pode produzir resultados diferentes no processo de meio-tom. A varredura da esquerda para a direita que foi implementada pode gerar padrões indesejados, tais como os observados. Para evitar tais efeitos, uma opção é alternar a direção de varredura a cada linha.

Uma outra abordagem utiliza curvas de preenchimento do espaço para distribuir o erro de quantização da imagem. A curva de Hilbert possui características desejáveis para geração de imagens de halftoning.