Neste artigo vou apresentar alguns algoritmos de halftone e as características de cada um.
O termo halftone diz respeito a uma técnica de simulação de tons contínuos de cor usando apenas duas cores, geralmente as cores branca e preta para simular tons de cinza. Essa técnica pode ser aplicada a qualquer dispositivo gráfico binário (onde cada pixel só pode apresentar dois valores, tal como um LED aceso ou apagado). Há também aplicações em que uma imagem colorida pode ser representada utilizando-se apenas LEDs RGB. Nesse caso, aplica-se a técnica de halftone para cada uma das componentes da imagem.
Um pouco mais de teoria
Os algoritmos de halftone tem a capacidade converter uma imagem qualquer para uma imagem composta de apenas dois valores, de forma a gerar a menor
distorção possível para o olho humano. As primeiras aplicações foram utilizadas na indústria gráfica para imprimir imagens em jornais, de forma que os tons de cinza eram representados por círculos de tinta preta. Se a região da imagem fosse mais escura, os círculos eram maiores, se fosse mais clara, menores.
Digitalmente, tudo o que podemos fazer é decidir se um determinado pixel será pintado ou não. Para isso, existem vários algoritmos de halftone, cada um com diferentes características.
O primeiro algoritmo que vou apresentar é o mais simples possível: decisão por threshold. Este algoritmo é tão simples que dificilmente será aplicado na prática, mas vou mostrar o seu efeito para tornar este artigo mais didático.
Basicamente, o que a função halftone abaixo faz é pintar o pixel de branco se este for maior que 127 ou pintar de preto caso contrário.
Basicamente, o que a função halftone abaixo faz é pintar o pixel de branco se este for maior que 127 ou pintar de preto caso contrário.
void halftone1(uint8_t *img, size_t w, size_t h)
{
size_t l;
size_t c;
size_t i;
for (l = 0; l < h; l++) {
for (c = 0; c < w; c++) {
i = (l * w) + c;
if (img[i] > 127)
img[i] = 255;
else
img[i] = 0;
}
}
}
Poderíamos melhorar um pouco esta técnica fazendo com que a análise seja realizada em um conjunto de quatro pixels por vez. Dessa forma, a decisão de como pintar os pixels será tomada baseada em um número maior de intervalos, nesse caso 5 intervalos possíveis. A soma dos valores dos pixels originais fará com que um dos padrões apresentados na figura abaixo seja escolhido.
Este método foi implementado na função halftone2 no código abaixo.
void halftone2(uint8_t *img, size_t w, size_t h)
{
uint32_t l;
uint32_t c;
uint32_t i;
int32_t val;
for (l = 0; l < h - 1; l += 2) {
for (c = 0; c < w - 1; c += 2) {
i = (l * w) + c;
val = (int32_t) img[i];
val += (int32_t) img[i + 1];
val += (int32_t) img[i + w];
val += (int32_t) img[i + w + 1];
if (val > (1 * 1024) / 8)
img[i] = 255;
else
img[i] = 0;
if (val > (3 * 1024) / 8)
img[i + w + 1] = 255;
else
img[i + w + 1] = 0;
if (val > (5 * 1024) / 8)
img[i + w] = 255;
else
img[i + w] = 0;
if (val > (7 * 1024) / 8)
img[i + 1] = 255;
else
img[i + 1] = 0;
}
}
}
Porém, estes métodos apresentados resultarão em erros de quantização. Digamos que um pixel recebe o valor 255 e o valor na imagem original em escala de cinza era 200. Então houve um erro de 55, e isso afetará a qualidade final da imagem.
O algoritmo de error diffusion faz com que o erro de quantização geral na imagem seja nulo. Isso é possível pois para cada pixel processado, o erro gerado é acumulado para o pixel seguinte. A função halftone3 mostra a implementação básica de um algoritmo de error diffusion.
void halftone3(uint8_t *img, size_t w, size_t h)
{
uint32_t l;
uint32_t c;
uint32_t i;
int32_t pe; /* propagated error */
int32_t te; /* total error */
pe = 0;
te = 0;
for (l = 1; l < h; l++) {
for (c = 1; c < w; c++) {
i = (l * w) + c;
te = (int32_t) img[i] + pe;
if (te > 127)
img[i] = 255;
else
img[i] = 0;
pe = te - img[i];
}
}
}
Como todo método simples, este algoritmo também possui uma versão um pouco mais sofisticada. Imagine que, ao processar um determinado pixel, o erro no processo de quantização seja distribuído para os pixels vizinhos e não apenas acumulado no pixel seguinte. Essa distribuição do erro é feita de acordo com uma matriz de distribuição. Para exemplificar o método utilizei a matriz de Floyd e Steinberg.
O código do algoritmo é o seguinte:
void halftone4(int16_t *img, size_t w, size_t h)
{
uint32_t l;
uint32_t c;
uint32_t i;
int pe; /* propagated error */
int oldp;
int newp;
for (l = 1; l < h - 1; l++) {
for (c = 1; c < w - 1; c++) {
i = (l * w) + c;
oldp = img[i];
if (oldp > 127)
newp = 255;
else
newp = 0;
img[i] = (int16_t) newp;
pe = oldp - newp;
img[i + 1] = (int16_t) ((int) img[i + 1] + (7 * pe) / 16);
img[i + w - 1] = (int16_t) ((int) img[i + w - 1] + (3 * pe) / 16);
img[i + w] = (int16_t) ((int) img[i + w] + (5 * pe) / 16);
img[i + w + 1] = (int16_t) ((int) img[i + w + 1] + (1 * pe) / 16);
}
}
}
Há uma diferença importante entre a função halftone4 e as demais. Nesse último caso, o erro gerado em cada pixel será somado nos pixels da vizinhança. Como as imagens que estou trabalhando possuem resolução de 8 bits (uint8_t), pode acontecer de o valor do pixel somado aos erros extrapolarem os limites da variável. Por isso, a função halftone4 recebe a imagem como int16_t, a qual deve ser convertida antes da chamada dessa função.
Resultados
Para mostrar o efeito de cada algoritmo, utilizei os programas disponibilizados neste artigo para aplicar estas funções a imagens quaisquer.
Abaixo está o efeito de cada algoritmo aplicado a uma imagem de rampa de tons de cinza.
rampa de tons de cinza
halftone1: threshold
halftone2: célula de threshold
halftone3: error diffusion
halftone4: matriz de Floyd e Steinberg
Para ter uma ideia mais prática, apliquei também estes
algoritmos no R2D2 e gerei as imagens abaixo:
imagem original colorida
halftone1: threshold
halftone2: célula de threshold
halftone3: error diffusion
halftone4: matriz de Floyd e Steinberg
Conclusão
Se você precisa transformar uma imagem em zeros e uns, qualquer um desses algoritmos funciona. Se você precisa de qualidade na imagem final apenas aplicar o threshold não será o suficiente. Já a célula de threshold pode dar um efeito bom, mas quanto maior for a célula usada (nesse caso usei 4 pixels), menor ficará a resolução aparente da imagem. Os algoritmos de error diffusion irão manter a luminosidade aparente da imagem. O error diffusion simples causa mais granulosidade. Para obter o melhor resultado a recomendação é aplicar uma matriz de distribuição como na função halftone4, mas vai demandar mais linhas de código e mais tempo para processar.
