Algoritmos de cuantización de color - Reducción de colores con Median Cut y k-means
Qué es la cuantización de color
La cuantización de color reduce el número de colores en una imagen. Las imágenes de 24 bits pueden representar hasta 16,77 millones de colores, pero el formato GIF solo admite 256 colores y algunos dispositivos tienen paletas limitadas. Los algoritmos de cuantización reducen la cantidad de colores a un número especificado manteniendo la calidad visual tanto como sea posible.
Por qué se necesita la cuantización:
- Creación de animaciones GIF: Los colores deben limitarse a 256 como máximo
- Extracción de colores dominantes: Extraer colores representativos de imágenes para diseño
- Optimización de tamaño de archivo: Reducir colores disminuye significativamente el tamaño de archivos PNG
- Efectos artísticos: Procesamiento estilizado como posterización de color
El desafío central de la cuantización:
Seleccionar los N colores más representativos de millones de colores, de modo que la imagen cuantizada sea visualmente lo más cercana posible a la original. Esto es esencialmente un problema de optimización, y diferentes algoritmos hacen distintas compensaciones entre velocidad, calidad y uso de memoria.
La evaluación de la calidad de cuantización típicamente usa el error cuadrático medio (MSE) o la relación señal-ruido pico (PSNR), pero la percepción humana de las diferencias de color no es uniforme, por lo que las métricas de error en espacios de color perceptuales (como CIELAB) reflejan mejor la calidad visual real.
Median Cut - División recursiva del espacio de color
Median Cut fue propuesto por Paul Heckbert en 1982 y divide recursivamente el espacio de color RGB para determinar colores representativos. A pesar de su simplicidad, produce resultados de alta calidad y se usa ampliamente en bibliotecas de procesamiento de imágenes.
Pasos del algoritmo:
- Colocar todos los píxeles de la imagen en un cubo (box) que contiene todo el espacio RGB
- Encontrar el eje con mayor rango de distribución de color (R, G o B)
- Dividir el cubo en dos por la posición de la mediana a lo largo de ese eje
- Repetir los pasos 2-3 para cada subcubo hasta alcanzar el número objetivo de colores
- El color promedio de todos los píxeles dentro de cada cubo se convierte en el color representativo de esa región
Ventajas:
- Implementación simple, poco código
- Velocidad de cálculo rápida, adecuado para procesamiento en tiempo real
- Resultados estables, no afectados por valores iniciales
- Asigna naturalmente más colores representativos a regiones con alta densidad de color
Limitaciones:
- Las direcciones de división se limitan a las direcciones de los ejes coordenados
- Puede producir resultados subóptimos para imágenes con distribución de color no uniforme
- No considera las diferencias de sensibilidad del ojo humano a diferentes regiones de color
Variantes mejoradas:
El Median Cut ponderado pondera las decisiones de división según la cantidad de píxeles, dando una cuantización más fina a las regiones con alta densidad de color. La división por máxima varianza selecciona el eje con mayor varianza para dividir, en lugar del simple eje de mayor rango.
Generación de paleta óptima con k-means
El agrupamiento k-means divide los píxeles del espacio de color en k grupos, usando el centroide de cada grupo como color representativo. Mediante optimización iterativa minimiza el error de cuantización (distancia total entre píxeles y sus colores representativos), generando teóricamente la paleta óptima.
Flujo del algoritmo:
- Seleccionar aleatoriamente k centroides iniciales (o usar inicialización k-means++)
- Asignar cada píxel al grupo del centroide más cercano
- Recalcular el centroide de cada grupo (color promedio de todos los píxeles del grupo)
- Repetir los pasos 2-3 hasta que los centroides no cambien o se alcance el máximo de iteraciones
Comparación con Median Cut:
- Calidad: k-means generalmente produce menor error de cuantización
- Velocidad: k-means requiere múltiples iteraciones, más lento que Median Cut
- Estabilidad: Los resultados dependen de los valores iniciales, múltiples ejecuciones pueden dar resultados diferentes
- Aplicabilidad: Adecuado para escenarios con altos requisitos de calidad y requisitos de velocidad no estrictos
Técnicas de optimización:
- Usar inicialización k-means++ para evitar óptimos locales
- Usar el resultado de Median Cut como centroides iniciales para acelerar la convergencia
- Submuestrear la imagen antes del agrupamiento para reducir drásticamente el cómputo
- Realizar el agrupamiento en el espacio de color CIELAB para que la métrica de distancia se ajuste mejor a la percepción humana
Método octree y otros algoritmos de cuantización
Además de Median Cut y k-means, existen varios algoritmos de cuantización. Seleccionar el método óptimo según los requisitos y restricciones es importante para obtener los mejores resultados en cada escenario de aplicación.
Cuantización octree:
El octree representa el espacio de color RGB como una estructura de árbol con profundidad máxima de 8. Cada nodo representa un subespacio de color, y los nodos hoja almacenan información estadística de píxeles de esa región. Se reduce el número de colores fusionando nodos hoja.
- Ventajas: Alta eficiencia de memoria, construcción incremental, adecuado para procesamiento en flujo
- Características: Preserva naturalmente más detalle en regiones de color de alta frecuencia
- Aplicaciones: Comúnmente usado en escenarios que requieren ajuste dinámico del número de colores
Cuantización uniforme:
Divide cada eje RGB uniformemente en un número fijo de intervalos. La implementación más simple pero la peor calidad, ya que no considera la distribución real de colores. Adecuada para escenarios con bajos requisitos de calidad pero necesidad de velocidad extrema.
Cuantización por red neuronal (NeuQuant):
Usa una red neuronal de mapas autoorganizados (SOM) para aprender la distribución de colores de la imagen. Los pesos de la red entrenada son la paleta óptima. Excelente calidad pero alto costo computacional, adecuado para procesamiento por lotes fuera de línea.
Guía de selección de algoritmo:
- Procesamiento en tiempo real, frontend web: Median Cut
- Máxima calidad, procesamiento fuera de línea: k-means (espacio CIELAB)
- Procesamiento en flujo, memoria limitada: Octree
- Integrado en codificadores GIF: Generalmente Median Cut mejorado u octree
Combinación con dithering - Mejora de la calidad visual
Las imágenes cuantizadas pueden mostrar bandas (patrones de franjas tipo contorno) debido a la pérdida de gradación tonal por la limitación de colores. Combinar con dithering permite reproducir perceptualmente gradientes suaves incluso con un número limitado de colores.
Principio del dithering:
El dithering alterna diferentes colores entre píxeles adyacentes, aprovechando la característica de mezcla espacial del ojo humano para simular tonos intermedios. Similar a la técnica de medios tonos en impresión.
Principales algoritmos de dithering:
- Dithering Floyd-Steinberg: Representante del método de difusión de error, distribuye el error de cuantización proporcionalmente a los píxeles adyacentes. Alta calidad pero con artefactos direccionales
- Dithering ordenado (matriz Bayer): Usa una matriz de umbrales predefinida, permite procesamiento paralelo. Produce un patrón de puntos regular
- Dithering aleatorio: Añade ruido aleatorio antes de cuantizar. El más simple pero la menor calidad
- Dithering Sierra: Versión mejorada de Floyd-Steinberg con mayor rango de difusión de error y menos artefactos
Control de intensidad del dithering:
Una intensidad de dithering demasiado alta produce ruido visible, mientras que demasiado baja deja las bandas visibles. Generalmente se establece el coeficiente de difusión de error entre 0.7-1.0, ajustando según el contenido de la imagen y el número de colores objetivo. Las imágenes fotográficas se benefician de un dithering más fuerte, mientras que los iconos y elementos de UI deben reducirlo o desactivarlo.
Consideraciones en aplicaciones web:
Los navegadores modernos aplican automáticamente dithering al mostrar imágenes en dispositivos de baja profundidad de color. Sin embargo, al generar manualmente GIF o PNG-8, es necesario elegir explícitamente el algoritmo y la intensidad de dithering para equilibrar el tamaño del archivo y la calidad visual.
Aplicaciones prácticas - Conversión GIF y extracción de color dominante
Las aplicaciones prácticas de los algoritmos de cuantización de color incluyen la creación de animaciones GIF y la extracción de colores dominantes. Estas técnicas se usan frecuentemente en desarrollo web y herramientas de diseño.
Flujo de trabajo de conversión GIF:
- Analizar todos los fotogramas del video/animación para construir una paleta global
- Usar un algoritmo de cuantización para reducir los colores a 256 o menos
- Aplicar procesamiento de dithering para mejorar la calidad visual
- Optimizar las diferencias entre fotogramas, codificando solo las regiones que cambian para reducir el tamaño del archivo
Paleta global vs paleta local:
- Paleta global: Todos los fotogramas comparten una paleta de 256 colores. Archivo más pequeño pero expresividad de color limitada
- Paleta local: Paleta independiente por fotograma. Colores más ricos pero archivo significativamente más grande
- Estrategia mixta: Fotogramas clave usan paleta local, el resto usa paleta global
Aplicaciones de extracción de color dominante:
- Color de fondo de marcador de posición: Mostrar el color dominante como fondo antes de que la imagen cargue
- Temas de UI adaptativos: Generar automáticamente esquemas de color basados en imágenes subidas por el usuario
- Búsqueda y clasificación de imágenes: Recuperación de imágenes similares basada en colores dominantes
- Visualización de datos: Visualizar la distribución de colores de la imagen como rueda de color o gráfico de barras
Ejemplo de implementación en JavaScript:
Después de obtener los datos de píxeles usando la Canvas API, aplica Median Cut para extraer 5-8 colores dominantes. Para escenarios sensibles al rendimiento, escala primero la imagen a 50x50 píxeles antes del análisis, completando el procesamiento en milisegundos sin afectar notablemente la calidad del resultado.