Dithering Floyd-Steinberg - Floyd–Steinberg dithering
Floyd – Steinberg dithering é um algoritmo de dithering de imagem publicado pela primeira vez em 1976 por Robert W. Floyd e Louis Steinberg . É comumente usado por software de manipulação de imagens, por exemplo, quando uma imagem é convertida para o formato GIF restrito a um máximo de 256 cores.
O algoritmo alcança o pontilhamento usando difusão de erro , o que significa que ele empurra (adiciona) o erro de quantização residual de um pixel em seus pixels vizinhos, para ser tratado posteriormente. Ele distribui a dívida de acordo com a distribuição (mostrada como um mapa dos pixels vizinhos):
O pixel indicado com uma estrela (*) indica o pixel que está sendo escaneado, e os pixels em branco são os pixels escaneados anteriormente. O algoritmo varre a imagem da esquerda para a direita, de cima para baixo, quantizando os valores dos pixels um por um. Cada vez que o erro de quantização é transferido para os pixels vizinhos, não afeta os pixels já quantizados. Portanto, se um número de pixels foi arredondado para baixo, torna-se mais provável que o próximo pixel seja arredondado para cima, de modo que, em média, o erro de quantização seja próximo a zero.
Os coeficientes de difusão têm a propriedade de que, se os valores de pixel originais estiverem exatamente na metade entre as cores disponíveis mais próximas, o resultado pontilhado será um padrão quadriculado. Por exemplo, dados em cinza 50% podem ser pontilhados como um padrão quadriculado em preto e branco. Para um pontilhamento ideal, a contagem de erros de quantização deve ter precisão suficiente para evitar que erros de arredondamento afetem o resultado.
Em algumas implementações, a direção horizontal da varredura alterna entre as linhas; isso é chamado de "varredura serpentina" ou pontilhamento por transformação do boustrophedon .
No seguinte pseudocódigo , podemos ver o algoritmo descrito acima. Isso funciona para qualquer codificação aproximadamente linear de valores de pixel, como inteiros de 8 bits, inteiros de 16 bits ou números reais no intervalo [0,1].
for each y from top to bottom do
for each x from left to right do
oldpixel := pixels[x][y]
newpixel := find_closest_palette_color(oldpixel)
pixels[x][y] := newpixel
quant_error := oldpixel - newpixel
pixels[x + 1][y ] := pixels[x + 1][y ] + quant_error × 7 / 16
pixels[x - 1][y + 1] := pixels[x - 1][y + 1] + quant_error × 3 / 16
pixels[x ][y + 1] := pixels[x ][y + 1] + quant_error × 5 / 16
pixels[x + 1][y + 1] := pixels[x + 1][y + 1] + quant_error × 1 / 16
Ao converter valores de pixel em escala de cinza de uma profundidade de bits alta para baixa (por exemplo, escala de cinza de 8 bits para preto e branco de 1 bit), find_closest_palette_color()pode realizar apenas um arredondamento simples, por exemplo:
find_closest_palette_color(oldpixel) = round(oldpixel / 255)
O pseudocódigo pode resultar em valores de pixel que excedem os valores válidos (como mais de 255 em imagens em escala de cinza de 8 bits). Idealmente, esses valores devem ser recortados pela find_closest_palette_color()função, em vez de recortar os valores intermediários, uma vez que um erro subsequente pode trazer o valor de volta ao intervalo. No entanto, se números inteiros de largura fixa forem usados, o agrupamento de valores intermediários pode causar a inversão de preto e branco e, portanto, deve ser evitado.
O find_closest_palette_colornão é trivial para uma paleta que não está distribuída uniformemente. Nesse caso, é necessária uma pesquisa do vizinho mais próximo em 3D.
Referências
- Floyd – Steinberg Dithering (projeto do curso de artes gráficas, Visgraf lab, Brasil)
- RW Floyd, L. Steinberg, Um algoritmo adaptativo para escala de cinza espacial . Proceedings of the Society of Information Display 17 , 75–77 (1976).