domingo, 24 de mayo de 2020

Restaurando pixel art con R y k-means

Seguramente k-means sea el algoritmo de clustering más conocido a nivel académico, pero poco usado en aplicaciones del mundo real por su carácter impredecible y poca robustez en general frente a distribuciones complejas. Aquí veremos un caso de uso en el que k-means resulta efectivo por los motivos que comentaremos luego.

Se trata de "restaurar" imágenes pixel art que podamos encontrar en la Red para devolverles su estado nativo original:
  • Cada píxel de la imagen final corresponderá a un solo píxel nativo del pixel art primitivo (es decir serán imágenes reducidas a tamaño icono con muy pocos píxeles por lado).
  • La paleta de colores original también se tratará de restaurar, reduciéndola a un conjunto mínimo de colores básicos (típicamente del orden de 10 como máximo).

Partimos de la siguiente imagen pixel art deteriorada, en este caso por los artefactos derivados de la compresión JPEG. Nunca se debe guardar en este formato nada que no sea una fotografía pero se hace constantemente.



Por la compresión del formato el color en las celdas no es uniforme, y aunque perceptualmente podemos distinguir sin problema los colores compartidos, numéricamente son todos diferentes debido al ruido:



El tamaño nativo del pixel art lo obtenemos simplemente contando "píxeles": en este caso 38x43 (ancho x alto). A continuación recorremos la imagen promediando el color en cada uno de estos "píxeles". Hacerlo por mediana es más conveniente que usar la media para ser más robustos frente a outliers (contaminación cerca de los bordes de las celdas o píxeles con ruido espúreo).

Además solo usamos la parte central de cada celda, aplicando una guarda configurable para descartar los bordes. En el ejemplo este margen resulta recomendable para evitar que la cuadrícula negra original participe en el promediado de mediana.



Calculada la mediana en cada una de las celdas reducimos la paleta de color pero lejos todavía de la paleta mínima a la que aspiramos. A k-means le debemos suministrar el número de clústers (colores o combinaciones RGB) en que debe segmentar la imagen. Podríamos tratar de contar colores sobre la imagen original, pero resulta mucho más sencillo analizar la imagen en el espacio RGB y limitarnos a "contar clústers":



Como puede verse los clústers se hacen muy evidentes porque el ruido que contienen supone una dispersión muy controlada. Corresponderían a una paleta base de exactamente 15 colores distintos. Aplicando una segmentación con k=15 segmentos tenemos el pixel art final restaurado en una imagen de 38x43 píxeles totales y una paleta de 15 colores únicos:



El reparto de píxeles por clúster lo podemos ver en el siguiente histograma:


~~~

Repetimos el proceso con otros casos de uso. La imagen original es una fotografía del dibujo de un Pokémon en papel:



Tras corregir la perspectiva en Photoshop para traer la imagen al universo cartesiano repetimos el proceso. Aquí el resultado una vez calculamos la mediana del color en cada celda, las diferencias de tonalidad son visibles a simple vista fruto de las irregularidades de la fotografia original:



Basta mirar la imagen para intuir los 4 colores básicos que la componen, corroborados por el scatter de color. En este caso los clústers son mucho menos compactos que con Boba Fett pero por estar situados en puntos tan alejados entre sí en el espacio RGB, siguen siendo inequívocamente identificables. Se superponen con cierta transparencia los centroides generados en la segmentación con k=4:



Y aquí la reconstrucción del pixel art original:


~~~

Vamos con ejemplos que se lo ponen un poco más difícil a k-means. Este Octocat, la mascota de GitHub, proviene de un GIF animado que encontré aquí:



Por si sientes curiosidad el Octocat no es exactamente un gato sino gato y pulpo a la vez, y es hembra. El apéndice alzado no es una cola sino una de sus patas de pulpo con ventosas.



Cuando promediamos por mediana y dibujamos el scatter nos encontramos con 9 clústers definitorios. Aunque sutiles, se puede notar que hay dos tonos de gris próximos y lo mismo ocurre con otros dos tonos crema. Estas diferencias casi se notan más a simple vista que en el gráfico (hacer clic sobre la imagen para verla en más detalle):



La imagen restaurada queda así con los 9 colores únicos:


~~~

Y pasamos de un gatopulpo a un erizo, Sonic!



Calculando el scatter queda cristalino que la imagen se define con 14 colores, incluyendo tres tonalidades de azul, cuatro gamas de gris (incluídos el blanco y el negro) y dos de rojo:



En ejecuciones de k-means con k=14, el clúster de tonos amarillos no se generaba. Sin embargo parametrizando un valor muy alto de nstart (90.000) el clúster sí aparece y sin necesidad de aumentar k. Esto da idea de lo poco previsible y sensible que es el algoritmo: aquí sabíamos que el clúster existía e "íbamos a por él", pero qué pasa cuando tienes un conjunto de datos enorme y no tienes ni idea de cómo ayudar a k-means?


~~~

Para terminar un caso que, requiriendo algo de proceso manual (en concreto corregir la perspectiva y eliminar el fondo de la fotografía original, que hemos sustituido por color verde en el archivo TIFF), presenta una dificultad considerable:



El scatter de la imagen deja claro que la tarea no estará exenta de algún fallo, pero veremos qué tal lo hace k-means. Al provenir de una fotografía, como ya nos pasó en el Pokémon los clústers tienen mucha más dispersión, pero aquí el problema es mayor por ser superior la gama de colores (hacer clic sobre la imagen para verla en alta resolución):



A la vista de las agrupaciones presumimos unos 10-11 colores reales únicos, que más el verde sintético supondrían 11-12 clústers como mínimo. Sin embargo para diferenciar el color rojizo de las orejeras necesitamos un clúster adicional y subir de forma considerable nstart, así que segmentamos con k=13 resultando estos centroides:



Despojado el fondo del color verde, el resultado aunque no es perfecto (sobre todo en las gamas de marrones), es muy bueno si tenemos en cuenta que partimos de la fotografía de un pixel art físico. La mediana además ha absorbido muy bien el efecto del punto central oscuro que encontramos en cada cuadrícula, valores que pueden considerarse outliers:



Podemos refinar fusionando manualmente los dos clústers ocre, que por ser tan parecidos (centroides muy próximos) introducen diferencias ficticias indeseables:


    > centers[7,]=(centers[7,]+centers[10,])/2
    > centers[10,]=centers[7,]


El resultado ya no tiene diferenciación de color donde no debe, y es perfecto a falta de un muy pequeño número de píxeles puntuales que no fueron clasificados en su color correcto (en general píxeles que deberían haber sido grises pero acabaron marcados como marrón oscuro):



Si se crearon dos clústers verdes segmentando con k=13, y hemos fusionado dos de los clústers de color, eso significa que la porción de personaje en la imagen final se forma finalmente con 13 - 2 - 1 = 10 colores únicos.

~~~

Y aquí un resumen final de todos los ejemplos comparando con la fuente:


~~~

Hablemos de por qué k-means ha tenido éxito en este tipo de aplicación, y dónde podría fallar.

k-means ha funcionado bien básicamente... porque lo tenía fácil. A la vista de los scatters 3D es fácil darse cuenta de que tras el promedio de mediana, la dispersión alrededor de los centroides en los pixel art es siempre muy baja, como era esperable, definiendo perfectamente los clústers y no existiendo en ningún caso outliers.

Por otro lado aunque en k-means puntos muy alejados del centroide penalizan mucho, lo que incentiva la creación de clústers exclusivos para píxeles de colores muy aislados, si un elemento es muy minoritario no sería difícil que k-means lo obviase como nos pasó al principio con los píxeles amarillos de las deportivas de Sonic.

El siguiente ejemplo tiene visualmente dos clústers, gris y amarillo, o eso podríamos encontrar en un pixel art afectado por ruido. Se trata de una imagen de 30x30 píxeles con un único píxel amarillo y los demás repartidos a partes iguales en tonos grises muy cercanos:



Tras una segmentación con k=2 los dos clústers creados se corresponden con dos tonos de gris, quedando asignado el píxel amarillo al clúster menos oscuro (la influencia del píxel amarillo en el cálculo del centroide la vemos en la ligera desviación de éste respecto a los valores R=G=B=35):

    > kmeansfit$centers*255
             R        G        B
    1 20.00000 20.00000 20.00000
    2 35.47672 35.47672 34.92239


El error medido como distancia euclídea entre el píxel amarillo y su centroide, pese a ser muy grande, pesa menos en el cómputo que la suma de todos los errores que se tendrían debidos a los píxeles grises si hubiese un solo clúster de tono gris para ellos. Para que el píxel amarillo tenga su propio clúster no hay más remedio que aumentar a k=3 el número de segmentos.

~~~

Repositorio con el código R y archivos auxiliares: GitHub.

No hay comentarios:

Publicar un comentario

Por claridad del blog, por favor trata de utilizar una sintaxis lo más correcta posible y no abusar del uso de emoticonos, mayúsculas y similares.