Descrição do Algoritmo

Descrição do Algoritmo • Medindo o Erro de Redução de Cores

Este documento descreve como o ImageMagick realiza a redução de cores em uma imagem. Para entender completamente o que se segue, você deve ter conhecimento das técnicas básicas de imagem e da estrutura de dados em árvore (tree) e sua terminologia.

Descrição do Algoritmo

Para fins de alocação de cores, uma imagem é um conjunto de n pixels, onde cada pixel é um ponto no espaço RGB. O espaço RGB é um espaço vetorial tridimensional, e cada pixel, p(i), é definido por um trio ordenado de coordenadas vermelha, verde e azul, (r(i), g(i), b(i)).

Cada componente de cor primária (vermelho, verde ou azul) representa uma intensidade que varia linearmente de 0 a um valor máximo, Cmax, que corresponde à saturação total dessa cor. A alocação de cores é definida sobre um domínio que consiste no cubo no espaço RGB com vértices opostos em (0, 0, 0) e (Cmax, Cmax, Cmax). O ImageMagick requer Cmax= 255.

O algoritmo mapeia esse domínio em uma árvore na qual cada nó representa um cubo dentro desse domínio. Na discussão a seguir, esses cubos são definidos pela coordenada de dois vértices opostos: o vértice mais próximo da origem no espaço RGB e o vértice mais distante da origem.

O nó raiz da árvore representa todo o domínio, de (0,0,0) a (Cmax, Cmax, Cmax). Cada nível inferior na árvore é gerado subdividindo o cubo de um nó em oito cubos menores de tamanho igual. Isso corresponde a bissectar o cubo pai com planos que passam pelos pontos médios de cada aresta.

O algoritmo básico opera em três fases:

1. Classificação
2. Redução
3. Atribuição

Classificação

A classificação constrói uma árvore de descrição de cores para a imagem. A redução reduz a árvore até que o número que ela representa seja, no máximo, o número de cores desejado na imagem de saída. A atribuição define o mapa de cores da imagem de saída e define a cor de cada pixel por reclassificação na árvore reduzida. Nosso objetivo é minimizar as discrepâncias numéricas entre as cores originais e as cores quantizadas. Para saber mais sobre o erro de quantização, consulte Medindo o Erro de Redução de Cores.

A classificação começa inicializando uma árvore de descrição de cores com profundidade suficiente para representar cada possível cor de entrada em uma folha. No entanto, é impraticável gerar uma árvore de descrição de cores totalmente formada na fase de classificação para valores realistas de Cmax. Se os componentes de cor na imagem de entrada forem quantizados com precisão de k bits, de modo que Cmax = 2^k-1, a árvore precisaria de k níveis abaixo do nó raiz para permitir representar cada possível cor de entrada em uma folha. Isso se torna proibitivo porque o número total de nós da árvore:

total nodes = 1+Sum(8^i), i=1,k

For k=8,
nodes = 1 + (8^1+8^2+....+8^8)
      = 1 + 8(8^8 - 1)/(8 - 1)
      = 19,173,961

Portanto, para evitar construir uma árvore totalmente preenchida, o ImageMagick:

1. inicializa as estruturas de dados para os nós apenas conforme são necessários;

2. escolhe uma profundidade máxima para a árvore em função do número desejado de cores na imagem de saída (atualmente o logaritmo na base dois de Cmax).

   For Cmax=255, maximum tree depth = log2(256) = 8

Uma árvore com essa profundidade geralmente permite a melhor representação da imagem de origem com a maior velocidade de cálculo e a menor quantidade de memória. No entanto, a profundidade padrão é inadequada para algumas imagens. Portanto, o chamador pode solicitar uma profundidade de árvore específica.

Para cada pixel na imagem de entrada, a classificação varre para baixo a partir da raiz da árvore de descrição de cores. Em cada nível da árvore, ela identifica o único nó que representa um cubo no espaço RGB contendo a cor dos pixels. Ela atualiza os seguintes dados para cada nó:

n1

número de pixels cuja cor está contida no cubo RGB que este nó representa;

n2

número de pixels cuja cor não é representada em um nó de menor profundidade na árvore; inicialmente, n2=0 para todos os nós exceto as folhas da árvore.

Sr,Sg,Sb

somas dos valores dos componentes vermelho, verde e azul para todos os pixels não classificados em uma profundidade menor. A combinação dessas somas e de n2 caracterizará, em última análise, a cor média de um conjunto de pixels representado por este nó.

E

a distância ao quadrado no espaço RGB entre cada pixel contido em um nó e o centro do nó. Isso representa o erro de quantização para um nó.

Redução

A redução poda repetidamente a árvore até que o número de nós com n2 > 0 seja menor ou igual ao número máximo de cores permitido na imagem de saída. Em qualquer iteração sobre a árvore, ela seleciona para poda os nós cujo valor de E é mínimo e mescla suas estatísticas de cor para cima. Ela usa um limiar de poda, Ep, para governar a seleção de nós da seguinte forma:

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
   prune all nodes such that E <= Ep
   Set Ep  to minimum E in remaining nodes

Isso tem o efeito de minimizar qualquer erro de quantização ao mesclar dois nós.

Quando um nó a ser podado tem descendentes, o procedimento de poda invoca a si mesmo recursivamente para podar a árvore das folhas para cima. Os valores de n2, Sr, Sg e Sb em um nó sendo podado são sempre adicionados aos dados correspondentes no nó pai. Isso retém as características de cor do nó podado para a média posterior.

Para cada nó, existem n2 pixels para os quais aquele nó representa o menor volume no espaço RGB contendo as cores desses pixels. Quando n2 > 0, o nó definirá de forma única uma cor na imagem de saída. No início da redução, n2 = 0 para todos os nós exceto as folhas da árvore que representam as cores presentes na imagem de entrada.

A outra contagem de pixels, n1, indica o número total de cores dentro do volume cúbico que o nó representa. Isso inclui n1 - n2 pixels cujas cores devem ser definidas por nós em um nível inferior na árvore.

Atribuição

A atribuição gera a imagem de saída a partir da árvore podada. A imagem de saída consiste em duas partes:

1. Um mapa de cores, que é um array de descrições de cores (trios RGB) para cada cor presente na imagem de saída.
2. Um array de pixels, que representa cada pixel como um índice no array do mapa de cores.

Primeiro, a fase de atribuição faz uma passagem sobre a árvore de descrição de cores podada para estabelecer o mapa de cores da imagem. Para cada nó com n2 > 0, ela divide Sr, Sg e Sb por n2. Isso produz a cor média de todos os pixels que não se classificam abaixo deste nó. Cada uma dessas cores se torna uma entrada no mapa de cores.

Por fim, a fase de atribuição reclassifica cada pixel na árvore podada para identificar o nó mais profundo que contém a cor do pixel. O valor do pixel no array de pixels se torna o índice da cor média deste nó no mapa de cores.

Evidências empíricas sugerem que as distâncias em espaços de cor como YUV ou YIQ correspondem mais de perto às diferenças perceptuais de cor do que as distâncias no espaço RGB. Esses espaços de cor podem dar melhores resultados ao reduzir as cores de uma imagem. Aqui o algoritmo é como descrito, exceto que cada pixel é um ponto no espaço de cor alternativo. Por conveniência, os componentes de cor são normalizados para o intervalo de 0 a um valor máximo, Cmax. A redução de cores pode então prosseguir como descrito.

Medindo o Erro de Redução de Cores

Dependendo da imagem, o erro de redução de cores pode ser óbvio ou invisível. Imagens com altas frequências espaciais (como cabelo ou grama) mostrarão o erro muito menos do que imagens com grandes áreas suavemente sombreadas (como rostos). Isso porque as bordas de contorno de alta frequência introduzidas pelo processo de redução de cores são mascaradas pelas altas frequências na imagem.

Para medir a diferença entre as imagens original e com cores reduzidas (o erro total de redução de cores), o ImageMagick soma, sobre todos os pixels de uma imagem, a distância ao quadrado no espaço RGB entre cada valor de pixel original e seu valor com cores reduzidas. O ImageMagick imprime várias medições de erro, incluindo o erro médio por pixel, o erro médio normalizado e o erro máximo normalizado.

A medição de erro normalizado pode ser usada para comparar imagens. Em geral, quanto mais próximo de zero estiver o erro médio, mais a imagem quantizada se assemelha à imagem de origem. Idealmente, o erro deveria ser baseado na percepção, já que o olho humano é o juiz final da qualidade da quantização.

Esses erros são medidos e impressos quando as opções -colors e -verbose são especificadas na linha de comando do magick: