Descripción del algoritmo de reducción de color

Descripción del algoritmo • Medición del error de reducción de color

Este documento describe cómo ImageMagick realiza la reducción de color de una imagen. Para comprender plenamente lo que sigue, debe tener conocimientos sobre técnicas básicas de procesamiento de imágenes y sobre la estructura de datos de árbol (tree) y su terminología.

Descripción del algoritmo

A efectos de la asignación de color, una imagen es un conjunto de n píxeles, donde cada píxel es un punto en el espacio RGB. El espacio RGB es un espacio vectorial tridimensional, y cada píxel, p(i), se define mediante una terna ordenada de coordenadas roja, verde y azul, (r(i), g(i), b(i)).

Cada componente de color primario (rojo, verde o azul) representa una intensidad que varía linealmente desde 0 hasta un valor máximo, Cmax, que corresponde a la saturación plena de ese color. La asignación de color se define sobre un dominio que consiste en el cubo del espacio RGB con vértices opuestos en (0, 0, 0) y (Cmax, Cmax, Cmax). ImageMagick requiere Cmax= 255.

El algoritmo mapea este dominio sobre un árbol en el que cada nodo representa un cubo dentro de ese dominio. En la siguiente exposición, estos cubos se definen mediante las coordenadas de dos vértices opuestos: el vértice más cercano al origen en el espacio RGB y el vértice más alejado del origen.

El nodo raíz del árbol representa el dominio completo, desde (0,0,0) hasta (Cmax, Cmax, Cmax). Cada nivel inferior del árbol se genera subdividiendo el cubo de un nodo en ocho cubos más pequeños de igual tamaño. Esto corresponde a bisecar el cubo padre con planos que pasan por los puntos medios de cada arista.

El algoritmo básico opera en tres fases:

1. Clasificación
2. Reducción
3. Asignación

Clasificación

La clasificación construye un árbol de descripción de color para la imagen. La reducción colapsa el árbol hasta que el número que representa sea, como máximo, el número de colores deseados en la imagen de salida. La asignación define el mapa de color de la imagen de salida y establece el color de cada píxel mediante reclasificación en el árbol reducido. Nuestro objetivo es minimizar las discrepancias numéricas entre los colores originales y los colores cuantizados. Para saber más sobre el error de cuantización, consulte Medición del error de reducción de color.

La clasificación comienza inicializando un árbol de descripción de color de profundidad suficiente para representar en una hoja cada posible color de entrada. Sin embargo, no es práctico generar un árbol de descripción de color completamente formado en la fase de clasificación para valores realistas de Cmax. Si los componentes de color de la imagen de entrada se cuantizan con precisión de k bits, de modo que Cmax = 2^k-1, el árbol necesitaría k niveles por debajo del nodo raíz para poder representar en una hoja cada posible color de entrada. Esto resulta prohibitivo porque el número total de nodos del árbol:

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

Por lo tanto, para evitar construir un árbol completamente poblado, ImageMagick:

1. inicializa las estructuras de datos de los nodos solo a medida que se necesitan;

2. elige una profundidad máxima para el árbol en función del número de colores deseados en la imagen de salida (actualmente el logaritmo en base dos de Cmax).

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

Un árbol de esta profundidad generalmente permite la mejor representación de la imagen de origen con la mayor velocidad de cálculo y la menor cantidad de memoria. Sin embargo, la profundidad predeterminada es inapropiada para algunas imágenes. Por ello, el llamador puede solicitar una profundidad de árbol específica.

Para cada píxel de la imagen de entrada, la clasificación recorre hacia abajo desde la raíz del árbol de descripción de color. En cada nivel del árbol, identifica el único nodo que representa un cubo del espacio RGB que contiene el color del píxel. Actualiza los siguientes datos de cada uno de esos nodos:

n1

número de píxeles cuyo color está contenido en el cubo RGB que este nodo representa;

n2

número de píxeles cuyo color no está representado en un nodo de profundidad inferior del árbol; inicialmente, n2=0 para todos los nodos excepto las hojas del árbol.

Sr,Sg,Sb

sumas de los valores de los componentes rojo, verde y azul de todos los píxeles no clasificados a una profundidad inferior. La combinación de estas sumas y n2 caracterizará en última instancia el color medio de un conjunto de píxeles representado por este nodo.

E

la distancia al cuadrado en el espacio RGB entre cada píxel contenido dentro de un nodo y el centro del nodo. Esto representa el error de cuantización de un nodo.

Reducción

La reducción poda repetidamente el árbol hasta que el número de nodos con n2 > 0 sea menor o igual que el número máximo de colores permitidos en la imagen de salida. En cualquier iteración dada sobre el árbol, selecciona para la poda aquellos nodos cuyo valor E es mínimo y fusiona sus estadísticas de color hacia arriba. Utiliza un umbral de poda, Ep, para regir la selección de nodos de la siguiente manera:

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

Esto tiene el efecto de minimizar cualquier error de cuantización al fusionar dos nodos.

Cuando un nodo que debe podarse tiene descendientes, el procedimiento de poda se invoca a sí mismo recursivamente para podar el árbol desde las hojas hacia arriba. Los valores de n2, Sr, Sg y Sb de un nodo que se está podando se suman siempre a los datos correspondientes del padre de ese nodo. Esto conserva las características de color del nodo podado para su posterior promediado.

Para cada nodo, existen n2 píxeles para los cuales ese nodo representa el menor volumen del espacio RGB que contiene los colores de esos píxeles. Cuando n2 > 0, el nodo definirá de forma única un color en la imagen de salida. Al comienzo de la reducción, n2 = 0 para todos los nodos excepto las hojas del árbol, que representan colores presentes en la imagen de entrada.

El otro recuento de píxeles, n1, indica el número total de colores dentro del volumen cúbico que el nodo representa. Esto incluye n1 - n2 píxeles cuyos colores deberían ser definidos por nodos de un nivel inferior del árbol.

Asignación

La asignación genera la imagen de salida a partir del árbol podado. La imagen de salida consta de dos partes:

1. Un mapa de color, que es una matriz de descripciones de color (ternas RGB) para cada color presente en la imagen de salida.
2. Una matriz de píxeles, que representa cada píxel como un índice en la matriz del mapa de color.

En primer lugar, la fase de asignación realiza una pasada sobre el árbol de descripción de color podado para establecer el mapa de color de la imagen. Para cada nodo con n2 > 0, divide Sr, Sg y Sb entre n2. Esto produce el color medio de todos los píxeles que no se clasifican por debajo de este nodo. Cada uno de estos colores se convierte en una entrada del mapa de color.

Por último, la fase de asignación reclasifica cada píxel en el árbol podado para identificar el nodo más profundo que contiene el color del píxel. El valor del píxel en la matriz de píxeles pasa a ser el índice del color medio de este nodo en el mapa de color.

La evidencia empírica sugiere que las distancias en espacios de color como YUV o YIQ se corresponden con las diferencias de color perceptuales con más precisión que las distancias en el espacio RGB. Estos espacios de color pueden dar mejores resultados al reducir el color de una imagen. Aquí el algoritmo es tal como se describe, salvo que cada píxel es un punto en el espacio de color alternativo. Por conveniencia, los componentes de color se normalizan al rango de 0 a un valor máximo, Cmax. La reducción de color puede entonces proceder tal como se describe.

Medición del error de reducción de color

Según la imagen, el error de reducción de color puede ser evidente o invisible. Las imágenes con frecuencias espaciales altas (como cabello o hierba) mostrarán mucho menos el error que las imágenes con grandes áreas de sombreado suave (como rostros). Esto se debe a que los bordes de contorno de alta frecuencia introducidos por el proceso de reducción de color quedan enmascarados por las frecuencias altas de la imagen.

Para medir la diferencia entre la imagen original y la de color reducido (el error total de reducción de color), ImageMagick suma, sobre todos los píxeles de una imagen, la distancia al cuadrado en el espacio RGB entre el valor de cada píxel original y su valor de color reducido. ImageMagick imprime varias mediciones de error, incluidos el error medio por píxel, el error medio normalizado y el error máximo normalizado.

La medición del error normalizado puede usarse para comparar imágenes. En general, cuanto más cerca de cero esté el error medio, más se asemeja la imagen cuantizada a la imagen de origen. Idealmente, el error debería basarse en la percepción, ya que el ojo humano es el juez final de la calidad de la cuantización.

Estos errores se miden e imprimen cuando se especifican las opciones -colors y -verbose en la línea de comandos de magick: