Cuantización de color

En gráficos por computadora , la cuantización de color o cuantización de imagen en color es una cuantización aplicada a los espacios de color ; es un proceso que reduce la cantidad de colores distintos utilizados en una imagen , generalmente con la intención de que la nueva imagen sea lo más similar visualmente posible a la imagen original. Los algoritmos informáticos para realizar la cuantización de color en mapas de bits se han estudiado desde la década de 1970. ^{[ 1 ]} La cuantización de color es fundamental para mostrar imágenes con muchos colores en dispositivos que solo pueden mostrar una cantidad limitada de colores, generalmente debido a limitaciones de memoria, y permite una compresión eficiente de ciertos tipos de imágenes.

El término «cuantización de color» se utiliza principalmente en la literatura de investigación sobre gráficos por computadora; en las aplicaciones, se emplean términos como generación de paleta optimizada , generación de paleta óptima o disminución de la profundidad de color . Algunos de estos términos pueden resultar engañosos, ya que las paletas generadas por algoritmos estándar no son necesariamente las mejores posibles.

La mayoría de las técnicas estándar tratan la cuantización del color como un problema de agrupamiento de puntos en un espacio tridimensional, donde los puntos representan los colores de la imagen original y los tres ejes representan los tres canales de color. Casi cualquier algoritmo de agrupamiento tridimensional puede aplicarse a la cuantización del color, y viceversa. Una vez localizados los grupos, normalmente se promedian los puntos de cada grupo para obtener el color representativo al que se asignan todos los colores de ese grupo. Los tres canales de color suelen ser rojo, verde y azul , pero otra opción popular es el espacio de color Lab , en el que la distancia euclidiana es más coherente con la diferencia perceptiva.

El algoritmo más popular para la cuantificación del color, desarrollado por Paul Heckbert en su tesis de licenciatura de 1980 y publicado posteriormente en un artículo de revista en 1982, es el algoritmo de corte de mediana . ^{[ 2 ]} Se utilizan muchas variaciones de este esquema. Antes de este momento, la mayor parte de la cuantificación del color se realizaba utilizando el algoritmo de población o método de población , que esencialmente construye un histograma de rangos de igual tamaño y asigna colores a los rangos que contienen la mayor cantidad de puntos. Un método popular más moderno es la agrupación utilizando octrees , concebido por primera vez por Gervautz y Purgathofer y mejorado por el investigador de Xerox PARC Dan Bloomberg .

Si la paleta es fija, como suele ser el caso en los sistemas de cuantificación de color en tiempo real, como los que se utilizan en los sistemas operativos, la cuantificación de color se suele realizar utilizando el algoritmo de "distancia en línea recta" o "color más cercano", que simplemente toma cada color de la imagen original y encuentra la entrada de la paleta más cercana, donde la distancia se determina por la distancia entre los dos puntos correspondientes en el espacio tridimensional. En otras palabras, si los colores son${\displaystyle (r_{1},g_{1},b_{1})}$y${\displaystyle (r_{2},g_{2},b_{2})}$Queremos minimizar la distancia euclidiana :

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

Esto descompone eficazmente el cubo de color en un diagrama de Voronoi , donde las entradas de la paleta son los puntos y una celda contiene todos los colores que se corresponden con una única entrada de la paleta. Existen algoritmos eficientes de geometría computacional para calcular diagramas de Voronoi y determinar en qué región se encuentra un punto dado; en la práctica, las paletas indexadas son tan pequeñas que estos algoritmos suelen ser excesivos.

La cuantización de color se combina frecuentemente con el tramado , lo que puede eliminar artefactos indeseables como las bandas que aparecen al cuantizar gradientes suaves y dar la apariencia de una mayor cantidad de colores. Algunos métodos modernos de cuantización de color intentan combinar la selección de paleta con el tramado en una sola etapa, en lugar de realizarlos de forma independiente.

Se han inventado otros métodos mucho menos frecuentes que emplean enfoques completamente diferentes. El algoritmo K-means local, concebido por Oleg Verevka en 1995, está diseñado para su uso en sistemas de ventanas donde se fija un conjunto básico de "colores reservados" para el sistema y se pueden mostrar simultáneamente muchas imágenes con diferentes esquemas de color. Se trata de un esquema de post-agrupamiento que realiza una estimación inicial de la paleta y luego la refina iterativamente.

En los inicios de la cuantificación del color, el algoritmo de agrupamiento k-means se consideró inadecuado debido a sus elevados requisitos computacionales y su sensibilidad a la inicialización. En 2011, M. Emre Celebi volvió a investigar el rendimiento de k-means como cuantificador de color. ^{[ 3 ]} Demostró que una implementación eficiente de k-means supera a un gran número de métodos de cuantificación del color.

• Retrato de Ada Lovelace : representación fiel y varias versiones procesadas mediante cuantización de color k-means.
• 
  Original
• 
  2 colores
• 
  5 colores
• 
  10 colores
• 
  15 colores
• 
  100 colores

El algoritmo NeuQuant, de alta calidad pero lento, reduce las imágenes a 256 colores mediante el entrenamiento de una red neuronal de Kohonen , que se autoorganiza aprendiendo a igualar la distribución de colores en una imagen de entrada. Al tomar la posición en el espacio RGB de cada neurona, se obtiene un mapa de color de alta calidad en el que los colores adyacentes son similares. ^{[ 4 ]} Resulta particularmente ventajoso para imágenes con gradientes.

Finalmente, uno de los métodos más recientes es la cuantización espacial del color , concebida por Puzicha, Held, Ketterer, Buhmann y Fellner de la Universidad de Bonn , que combina el tramado con la generación de paletas y un modelo simplificado de percepción humana para producir resultados visualmente impresionantes incluso con un número muy reducido de colores. No trata la selección de paletas estrictamente como un problema de agrupamiento, ya que los colores de los píxeles cercanos en la imagen original también afectan al color de un píxel. Véanse las imágenes de ejemplo .

En los inicios de los PC, era común que los adaptadores de vídeo solo admitieran 2, 4, 16 o (eventualmente) 256 colores debido a las limitaciones de la memoria de vídeo; preferían dedicar la memoria de vídeo a tener más píxeles (mayor resolución) en lugar de más colores. La cuantización del color ayudó a justificar esta compensación, ya que permitió mostrar muchas imágenes con alta gama de colores en modos de 16 y 256 colores con una degradación visual mínima. Muchos sistemas operativos realizan automáticamente la cuantización y el tramado al visualizar imágenes con alta gama de colores en un modo de vídeo de 256 colores, lo cual era importante cuando predominaban los dispositivos de vídeo limitados a modos de 256 colores. Los ordenadores modernos ahora pueden mostrar millones de colores a la vez, muchos más de los que puede distinguir el ojo humano, lo que limita esta aplicación principalmente a dispositivos móviles y hardware antiguo.

Actualmente, la cuantización de color se utiliza principalmente en imágenes GIF y PNG . GIF, durante mucho tiempo el formato de mapa de bits animado y sin pérdidas más popular en la World Wide Web , solo admite hasta 256 colores, lo que requiere cuantización para muchas imágenes. Algunos navegadores web antiguos limitaban las imágenes al uso de una paleta específica conocida como colores web , lo que provocaba una grave degradación de la calidad en comparación con las paletas optimizadas. Las imágenes PNG admiten color de 24 bits, pero a menudo se puede reducir considerablemente su tamaño de archivo sin una degradación visual significativa mediante la aplicación de la cuantización de color, ya que los archivos PNG utilizan menos bits por píxel para imágenes con paleta.

La cantidad infinita de colores disponibles a través del objetivo de una cámara es imposible de mostrar en una pantalla de ordenador; por lo tanto, convertir cualquier fotografía a una representación digital implica necesariamente cierta cuantificación. En la práctica, el color de 24 bits es suficientemente rico como para representar casi todos los colores perceptibles por el ser humano con un margen de error suficientemente pequeño como para ser visualmente idénticos (si se presentan fielmente) dentro del espacio de color disponible . Sin embargo, la digitalización del color, ya sea en un detector de cámara o en una pantalla, limita necesariamente el espacio de color disponible. En consecuencia, hay muchos colores que pueden ser imposibles de reproducir, independientemente de la cantidad de bits que se utilicen para representar el color. Por ejemplo, es imposible en los espacios de color RGB típicos (comunes en los monitores de ordenador) reproducir toda la gama de verdes que el ojo humano es capaz de percibir.

Debido a la escasez de colores en los primeros ordenadores, los diferentes algoritmos de cuantificación producían imágenes de salida con apariencias muy distintas. Por consiguiente, se dedicó mucho tiempo a desarrollar algoritmos sofisticados para lograr imágenes más realistas.

• Color indexado
• Paleta (informática)
• Lista de paletas de software — Sección de paletas adaptativas .
• vacilación
• Cuantización (procesamiento de imágenes)
• Segmentación de imágenes

• Paul S. Heckbert. Cuantización de imágenes en color para visualización en búfer de fotogramas . Actas de ACM SIGGRAPH '82. Primera publicación del algoritmo de corte mediano.
• Dan Bloomberg. Cuantización del color mediante octrees . Leptonica.
• Oleg Verevka. Cuantización de imágenes en color en sistemas Windows con algoritmo K-means local . Actas del Simposio Occidental de Gráficos por Computadora '95.
• J. Puzicha, M. Held, J. Ketterer, J.M. Buhmann y D. Fellner. Sobre la cuantificación espacial de imágenes en color . ( Texto completo .ps.gz ) Informe técnico IAI-TR-98-1, Universidad de Bonn. 1998.