Quantização de cores

Na computação gráfica, quantização de cores ou quantização de imagem colorida é quantização aplicada em espaço de cores; Esse é um processo que reduz o número de cores distintas usadas em uma imagem, normalmente com a intenção de que a nova imagem possivelmente deva ficar visualmente similar à imagem original. Algoritmos computacionais para performar quantização de cores em bitmaps tem sido estudados desde os anos 70. Quantização de cores é essencial para reproduzir imagens com muitas cores em dispositivos que só podem exibir uma quantidade limitada de cores, normalmente associado a limitações de memória, e habilitar compressão eficiente de certos tipos de imagens.

Um exemplo de imagem em modo de cores RGB 24-bit

A mesma imagem com paleta de 16 cores especificamente escolhida que melhor representa ela; a paleta selecionada é mostrada nos quadrados abaixo

O nome quantização de cores é usado principalmente em pesquisas de computação gráfica; em aplicativos, termos como geração de paleta otimizada, ou diminuir profundidade de cor são utilizados.

Algoritmos

Muitas técnicas tratam quantização de cores como um problema de agrupamento de pontos em um espaço tridimensional, onde os pontos que representam cores encontrados na imagem original e os três eixos representam os três canais de cores.

Quase todo algoritmo de agrupamento de pontos em três dimensões pode ser aplicado em quantização de cores, e vice e versa. Depois que as cores são localizadas no espaço tridimensional e agrupadas, são calculados as médias dos pontos em cada grupo de cores. Os três canais de cores são normalmente vermelho, verde, e azul, mas outra escolha comum é o espaço de cores Lab, a qual a distância euclidiana é mais consistente com a diferença visual.

O algoritmo mais popular para quantização de cores, inventado por Paul Heckbert em 1979, é o algoritmo median cut. Muitas variações deste esquema estão em uso. Antes dessa época, a quantização de cores mais popular foi feita usando o algoritmo de população ou Método de população a qual essencialmente constrói um histograma de mesmo espectro e assinala cores para os espectros que mais contém pontos. Um método mais popular e moderno é agrupamento usando octrees, inicialmente conceitualizado por Gervautz e Purgathofer e aperfeiçoado pelo pesquisador Dan Bloomberg da área de pesquisa da Xerox, a Xerox PARC.

Uma fotografia que teve seu canal de cores azul removido. Isso significa que todos as cores dos pixels tendem em um plano de duas dimensões apenas no cubo de cores.

O espaço de cores da fotografia ao lado, com sua paleta otimizada em 16 cores, produzida no Photoshop As regiões Voronoi de cada entrada da paleta são mostradas.

Se a paleta é fixa, como costuma ser o caso em sistemas de quantização de cores em tempo real, como os usados em sistemas operacionais, a quantização de cores geralmente é feita usando o algoritmo "distância em linha reta" ou "cor mais próxima", que simplesmente usa cada cor na imagem original e encontra a entrada da paleta mais próxima, onde a distância é determinada pela distância entre os dois pontos correspondentes no espaço tridimensional. Em outras palavras, se as cores são $(r_{1},g_{1},b_{1})$ e $(r_{2},g_{2},b_{2})$, queremos minimizar a distância euclidiana :

${\sqrt {(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}}}.$

Isso decompõe efetivamente o cubo de cores em um diagrama Voronoi, onde as entradas da paleta são os pontos e uma célula contém todas as cores mapeadas para uma única entrada. Existem algoritmos eficientes da geometria computacional para calcular os diagramas de Voronoi e determinar em que região um determinado ponto se enquadra; na prática, as paletas indexadas são tão pequenas que geralmente são um exagero.

Uma imagem colorida reduzida para 4 cores utilizando a quantização espacial de cores.

A quantização de cores é freqüentemente combinada com o pontilhamento, o que pode eliminar artefatos desagradáveis, como faixas que aparecem ao quantificar gradientes suaves e dar a aparência de uma quantidade maior de cores. Alguns esquemas modernos de quantização de cores tentam combinar a seleção de paletas com o pontilhamento em um estágio, em vez de executá-las independentemente.

Foram inventados vários outros métodos que funcionam de forma diferente, mas foram usados com muita pouca frequência. O algoritmo Local K-means, concebido por Oleg Verevka em 1995, foi projetado para ser usado em sistemas de janelas onde um conjunto principal de "cores reservadas" é setado para uso pelo sistema e muitas imagens com esquemas de cores diferentes podem ser exibidas simultaneamente. É um esquema pós-agrupamento que faz uma estimativa inicial da paleta e a redefine frequentemente.

No começo da quantização de cores, o algoritmo de agrupamento k-means foi considerado inadequado por causa de seus altos requisitos computacionais e a sensibilidade à inicialização. Em 2011, M. Emre Celebi reinvestigou o desempenho do k-means como um quantizador de cores. Ele demonstrou que uma implementação eficiente do k-means supera um grande número de métodos de quantização de cores.

De alta qualidade, mas lento, o algoritmo NeuQuant reduz as imagens para 256 cores treinando uma rede neural Kohonen "que se auto-organiza aprendendo a combinar com a distribuição das cores em uma imagem inserida. Usando a posição no espaço RGB de cada neurônio fornece um mapa de cores de alta qualidade, no qual as cores adjacentes são similares." É particularmente vantajoso para imagens com gradientes.

Finalmente, um dos métodos mais recentes é a quantização espacial de cores, concebida por Puzicha, Held, Ketterer, Buhmann e Fellner, da Universidade de Bonn, que combina o pontilhamento com a geração de paletas e um modelo simplificado da percepção humana para produzir resultados visualmente impressionantes, mesmo para muito pequeno número de cores. Ele não trata a seleção de paleta precisamente como um problema de agrupamento, pois as cores dos pixels próximos na imagem original também afetam a cor de um pixel. Veja imagens de exemplo .

História e usos

Nos começo da história dos computadores pessoais, era muito comum os adaptadores de vídeo suportarem somente 2, 4, 16 ou (ocasionalmente) 256 cores devido a limitações de memória de vídeo; eles preferencialmente dedicavam a memória de vídeo para se ter mais pixels (maior resolução) do que mais cores. Quantização de cores ajudou a justificar esta troca por possibilitar exibir muitas imagens com modos em 16 e 256 cores com degradação visual limitada. Muitos sistemas operacionais automaticamente performam quantização e pontilhamento quando rodam imagens high color em modo de vídeo de 256 cores, a qual foi importante quando aparelhos limitados a modos de 256 cores eram populares e comuns. Agora, computadores modernos podem exibir milhões de cores de uma vez, muito mais do que o olho humano pode distinguir, essa quantidade de cores é limitada principalmente em aparelhos móveis e hardwares antigos.

Nos dias atuais, quantização de cores é usada principalmente em imagens GIF e PNG. GIF, por muito tempo foi o formato de bitmap animado e sem perdas mais popular na World Wide Web, que só suportava até 256 cores, necessitando de quantização para muitas imagens. Alguns navegadores antigos restringiam as imagens para usarem uma paleta específica, conhecida como tripleto hexadecimal, resultando em perda de qualidade severa comparado às paletas otimizadas. Imagens PNG suportam cores em 24 bits, mas os arquivos podem frequentemente serem muito menores sem muita perda visual por aplicar a quantização de cores, sendo que arquivos PNG com cores paletizadas usam menos bits por pixel.

O número infinito de cores disponíveis que uma lente de uma câmera pode transmitir, é impossível de exibí-las em um monitor de computador; ao mesmo tempo que convertendo qualquer fotografia para uma representação digital necessariamente envolve alguma quantização. Praticamente, cores em 24 bits são suficientes para representar quase todas as cores visíveis por humanos com um pequeno erro de ser visualmente idêntico (se exibido fielmente) dentro do espaço de cor disponível. Entretanto, a digitalização de cor, ou em um sensor de câmera ou em uma tela, necessariamente limita o espaço de cores disponível. Consequentemente, há muitas cores que podem ser impossíveis de reproduzir, independentemente de quantos bits são usados para representar a cor. Por exemplo, é impossível no espaço de cores RGB (comum em monitores de computador) ser reproduzido a vasta gama de tons de verde que o olho humano é capaz de enxergar.

Com as poucas cores disponíveis nos computadores antigos, diferentes algoritmos de quantização produziam imagens com aparências diferentes. Como resultado, foi gasto muito tempo em desenvolvimento de algoritmos para serem mais realistas.

Suporte ao editor

Muitos editores de imagens bitmap contém suporte embutido de quantização de cores, e irá desempenhar automaticamente ela quando converte uma imagem com muitas cores para um formato de imagem com menos cores. A maioria destas implementações permitem que o usuário sete exatamente o número de cores desejadas. Exemplos deste suporte incluem:

• Photoshop: Função de cores indexadas fornece uma quantidade de algoritmos de quantização desde o sistema de cores fixo do sistema operacional Windows e paletas Web para algoritmos proprietários locais e globais para gerar paletas adequadas para uma imagem em particular ou imagens.
• Paint Shop Pro: Em Cores → Reduzir profundidade de cor, existem três algoritmos de quantização de cor padrão: Median-cut, octree, e a paleta padrão ''web safe''.
• No GIMP 2.8, a opção Converter imagem para cores indexadas, permite gerar uma paleta otimizada com a possibilidade de 2 a 256 cores, a opção de usar uma paleta otimizada para a web, e usar uma paleta preto e branco (1 bit). Ele permite que cores não utilizadas sejam removidas da paleta e então oferece uma variedade de pontilhamentos: Nenhum, Floyd-Steinberg (normal), Floyd Steinberg (vazamento de cores reduzido) e Posicionado com a abilidade de ativar pontilhamento de transparência.

Quantização de cores é também utilizado para criar efeitos de posterização, apesar que a posterização tem um diferente propósito de minimizar o número de cores utilizado dentro do mesmo espaço de cor, e tipicamente usa uma paleta fixa.

Muitos editores de gráfico vetoriais também utiliza quantização de cores, especialmente para uso em técnicas pixel-para-vector (do inglês raster-to-vector) que cria traços das imagens bitmap com a ajuda do detector de bordas.

Ligações externas

• Paul S. Heckbert. Color Image Quantization for Frame Buffer Display. ACM SIGGRAPH '82 Proceedings. First publication of the median cut algorithm. (Em inglês)
• Dan Bloomberg. Color quantization using octrees. Leptonica. (Em inglês)
• Oleg Verevka. Color Image Quantization in Windows Systems with Local K-means Algorithm. Proceedings of the Western Computer Graphics Symposium '95. (Em inglês)
• J. Puzicha, M. Held, J. Ketterer, J. M. Buhmann, and D. Fellner. On Spatial Quantization of Color Images. (Em inglês) (full text .ps.gz) Technical Report IAI-TR-98-1, University of Bonn. 1998. (Em inglês)