Extraer la paleta de colores de una imagen en Rust (color quantization)

Trabajar con imágenes siempre me pareció un tema muy interesante por varios motivos: es algo visual, es un reto de optimización, trabajas con matrices... En concreto me llamó la atención un algoritmo para resumir los colores de una imagen y extraer los más importantes: color quantization usando un octree.

Una imagen hoy día tiene millones de píxeles con muchísima información. Hay todo tipo de algoritmos de compresión con o sin pérdida (JPG, PNG, etc) que nos permiten reducir el tamaño de una imagen.

El ojo humano no es capaz de percibir las sutilezas de una imagen en formato RAW, por lo que si dos colores muy parecidos los aproximas al mismo, aunque pierdes algo de precisión a la vista de una persona los colores serán los mismos. Obviamente cuantos más colores aproximes, peor será la calidad de la imagen por lo que la clave es buscar el punto medio.

La técnica que extrae los colores más importantes de una imagen se conoce como color quantization. Encontré este artículo de 1997 (yo llevaba poco tiempo en el mundo) que habla sobre cómo calcular estos colores utilizando un octree, que consiste en trasladar los colores RGB al espacio tridimensional y con un Octree, que no deja de ser un árbol con 8 ramas, agruparlos para luego ir eliminando nodos hoja hasta quedarnos con los colores más representativos.

Realmente estamos generando una paleta de colores para luego mapear los píxeles de la imagen original utilizando esta paleta y reducir la cantidad de información.

Me apetecía continuar aprendiendo Rust y probar a implementar este algoritmo por diversión. A continuación te muestro un ejemplo del resultado de una imagen de la Alhambra para diferentes tamaños de la paleta:

Teoría del algoritmo

La idea del algoritmo es trasladar cada píxel a un espacio tridimensional. Esto se realiza mediante la siguiente técnica: dado un píxel RGB con valores en el rango [0, 255], cada valor es un entero de 8 bits. Supongamos el siguiente ejemplo #33CCFF:

• R = 33 (hex) = 51 (dec) = 00110011 (binario)
• G = CC (hex) = 204 (dec) = 11001100 (binario)
• B = FF (hex) = 255 (dec) = 11111111 (binario)

El algoritmo orginal del octree agrupa verticalmente los valores de 3bits: 011, 011, 101, 101, 001, 011, 011, 101, 101 que forman el pixel. Como cada valor es un número del 0 al 7 (8 valores), cada valor representa el índice del nodo del octree hasta llegar al nodo hoja, donde almacenamos el color.

Para obtener estos valores hay que trabajar con operadores de bits: por ejemplo puedes desplazar los bits hacia la derecha N veces con el operador >> y luego obtener el bit deseado aplicando una máscara 00000001.

Por ejemplo: (00110011 >> 7 - i) && 00000001 para i en el rango [0, depth].

Finalmente recorremos el árbol en un nivel, y agregamos los colores que hay en los nodos hoja calculando la media.

En mi caso he realizado la implementación de forma diferente, utilizando un Hash basado en la profundidad. En el ejemplo para una profundidad 4 obtengo el hash de los valores 011, 011, 101, 101 = 3355. De esta forma, en una tabla hash almaceno la suma de los colores que comparten este hash. De esta forma con la profundidad limitas los colores de la paleta en base 8. En la siguiente sección te cuento más sobre esto.

Por qué Rust

Rust es un lenguaje que no podemos negar está de moda. En mi caso hay modas que me gustan, y otras que no tanto. En este caso la idea detrás de Rust me parece interesante, y viendo la acogida de la comunidad y que surgen proyectos importantes en Rust, lo mejor es probarlo y poder opinar.

Hace un par de años comencé a estudiar Rust para probarlo en side-projects como este. La curva de aprendizaje es dura al principio ya que el famoso borrow checker te obliga a tener que pensar diferente a como trabajarías con otros lenguajes. Es un concepto interesante pero requiere tiempo.

A día de hoy me resulta cómodo trabajar con este lenguaje, además de ser muy eficiente, aunque aún hay retos más complejos que no sé qué tal sería abordarlos con este lenguaje y si realizarlos en otro como C/C++ sería más simple. Aunque empiezo a ver un movimiento en contra de los lenguajes inseguros, que no sé cómo acabará y personalmente aún no tengo una opinión formada al respecto. Lo veremos con el tiempo.

En cualquier caso es un lenguaje a bajo nivel que permite realizar código eficiente y que tiene otra serie de ventajas por las que me apetece aprenderlo. Eso sí, para scripts siempre utilizaré Python y para desarrollar código rápido y eficiente me encanta Go y sus goroutinas y canales. Pero nunca está de más aprender cómo funcionan otras herramientas.

Mi implementación

Puedes acceder al código en el repositorio de GitHub.

Implementar un Tree en Rust es un tema muy interesante, porque mezcla conceptos de las referencias y los life-times de las variables, pero esta vez se puede implementar de forma mucho más simple.

La idea es obtener el hash de un píxel con la profundidad que queramos, y utilizar un Map<String, [count, r, g, b]> para almacenar todos los píxeles que tengan el mismo hash para una profundidad determinada.

Por ejemplo el color blanco [255, 255, 255] = 7777777 (depth = 8) = 7777 (depth = 4)...

De esta forma simplificamos el proceso de crear un octree, y simplemente con el hash y limitando su tamaño a una profundidad, agregamos todos los colores de forma muy parecida a como lo haría un árbol, y así evitamos toda esta complejidad.

Para cada nivel de profundidad tenemos 8 valores, por lo que la paleta de colores será como máximo 2^(3*depth).