AlcidesRC

INTRODUCCION

Un fotomosaico es una composición de imagenes genéricas que, manipuladas de un modo particular, permiten representar una imagen determinada. Así pues, podríamos decir que un fotomosaico es una versión pixelada de una imagen, cuyos pixeles son, a su vez, otras imagenes.

Ayuda Para obtener más información puedes consultar la entrada de Fotomosaicos en la Wikipedia.

TIPOS DE COMPOSICIONES

Existen varios tipos de fotomosaicos y, además, algunos tipos de composiciones que no son fotomosaicos. Veamos las diferencias:

FOTOMONTAJES

Este tipo de composiciones consiguen un resultado bastante preciso, aunque no deberían considerarse fotomosaicos, pues el proceso de generación no respeta las imagenes originales, ya que aplica efectos de coloreado a conveniencia para simplificar el proceso.

Así pues, estas composiciones se generan del siguiente modo:

1. Preparar el grid, resultado de dividir la imagen original en una cuadrícula de NxM.
2. Distribuir las imagenes de nuestra base de datos de manera aleatoria en el grid.
3. Para cada celda de la cuadrícula, detectar el color representativo de esa región en la imágen original y colorear la imagen en miniatura con dicho color.

EJEMPLO

Uno de los ejemplos más espectaculares es el cartel del musical This Is It, de Michael Jackson.

Si haces zoom en la imagen verás, cómo cada imagen del grid ha sido coloreada para que, independientemente de los colores originales de la misma, esta imagen encaje a la perfección en la composición global.

Porción del cartel	Detalle ampliado

FOTOMOSAICOS

Este tipo de composiciones son considerablemente más complejas ya que el resultado final se ha generado respetando los colores de cada imagen de nuestra selección, por lo que se deben aplicar algoritmos específicos para la selección más idónea de las imágenes para cada región del grid.

Para crear un fotomosaico, generalmente, se realizan las siguientes fases:

1. Preparar la base de datos de imagenes, que no es más que una colección de fotos que servirá para componer nuestro fotomosaico.
2. Preparar el grid, resultado de dividir la imagen original en una cuadrícula de NxM.
3. Para cada región del grid, buscar en nuestra base de datos la imagen que más se parezca al color representativo de esa región en la imagen original.

EJEMPLO

El artista gráfico Robert Silvers, inventor del proceso de creación de fotomosaicos, presenta en su sitio web galería de fotomosaicos muy completa, a la par que compleja.

Como puedes apreciar, cada imagen del grid ha sido escalada al tamaño de la región respetando en todo momento los colores originales de la misma.

Porción de la imagen	Detalle ampliado

HERRAMIENTAS EXISTENTES

Existe una gran variedad de herramientas diseñadas específicamene para la creación de fotomosaicos, aplicaciones que simplifican total o parcialmente alguna fase o bien, permiten optimizar los recursos necesarios para la realización de este proceso. Algunas de estas herramientas son:

• Metapixel, una herramienta de línea de comandos que permite realizar el proceso en sistemas operativos Linux.
• Mosaickr, una aplicación web que permite componer fotomosaicos con las fotos alojadas en tu cuenta de Flickr.

DESMONTANDO A LOS FOTOMOSAICOS

PREAMBULO

Para entender cómo manipular imagenes, primero debemos conocer un poco sobre la teoría de colores y su representación numérica:

COLORES REPRESENTATIVOS

En una imagen pueden existir infinidad de colores y/o tonalidades pero ¿cual es el color que identifica mejor una imagen? ¿existe un único color representativo?

Para reducir una imagen con múltiples colores, a un único color representativo, se puede hacer uso de alguno de los siguienes criterios:

EJEMPLOS

• Color Dominante: El color dominante es aquel que más abunda en la imagen, es decir, aquel con mayor número de apariciones.
• Color Mediano: El color mediano es aquel que ocupa la posición central de la lista de colores ordenada por número de apariciones.
• Color Medio: El color medio o color promedio, es aquel resultante de calcular el valor medio de cada canal (rojo, verde y azul).
• Etc.

Color	RGB	Hex Base 16	Dec Base 10	Dominante	Mediano	Medio
	(0,128,255)	#0080FF	33023	33023	33023	33023
	(255,128,0)	#FF8000	16744448	16744448	16744448	16744448
	(128,255,128)	#80FF80	8454016	8454016	8454016	8454016

REQUISITOS

Para generar nuestros propios fotomosaicos necesitaremos:

• Entorno con un lenguaje de programación del lado del servidor, en este caso usaremos PHP.
• Tener instalada las librerías gráficas GD.
• Una selección de nuestras fotos favoritas, a modo de base de datos de imágenes.

Nota Para este tutorial he utilizado las fotos que he ido publicando en Instagram. Para descargar las imagenes a mi ordenador, he usado InstaPort.Me, una aplicación que permite hacer un backup de nuestras imagenes en un fichero comprimido que podemos descargar en nuestro ordenador.

TESTSUITE

He incluído una pequeña batería de pruebas para verificar que los métodos para la detección de colores son correctos:

Batería de Pruebas

Nota Como las imágenes usadas en la batería de pruebas son planas (ya que presentar un único color), los colores representativos deberían ser exactamente los mismos.

SELECCIONEMOS LA IMAGEN PRINCIPAL

Para realizar este tutorial he seleccionado la siguiente imagen para aplicar este efecto; como podrás observar, presenta una gran disparidad de colores y multitud de tonalidades de un mismo color:

Imagen principal (Source)

PREPARANDO LA BASE DE DATOS DE IMAGENES

Este proceso permite analizar cada imagen de nuestra galería y obtener el color más representativo de cada imagen. Así pues, como puede darse el caso que algunas imágenes diferentes presenten el mismo color representativo, se ha almacenado esta información en una estructura de array multidimensional cuya clave es el color representativo y, como valor, las imágenes que tienen dicho color representativo.

Nota Como este proceso consume una cantidad de recursos considerable (puesto que tiene que realizar múltipes accesos al disco duro para analizar cada imagen), se ha cacheado el resultado de este proceso en formato JSON. De este modo, si no variamos el contenido de nuestra base de datos de imágenes, ya tendremos identificado el color representativo relacionado y evitar así tener que recalcularlo en cada iteración.

• Estructura de nuestra base de datos de imágenes:

  
  			$database = array(
  				[...]
  				colorX => array(
  					filenameA,
  					filenameN,
  					filenameR,
  				),
  				colorY => array(
  					filenameQ,
  				),
  				[...]
  			);
  		

COMPLEJIDAD ALGORITMICA

Veamos con detalle la complejidad computacional, o complejidad algorítmica, de este proceso: Debemos procesar cada imagen de nuestra base de datos para asociarle su color representativo, es decir, se debe forzosamene iterar cada elemento de la lista.

Por tanto, si consideramos constante la complejidad de obtener el color representativo de una región y, por tanto, despreciable en términos de complejidad computacional; si n es el número de imágenes de nuestra selección, el grado de complejidad es O(n)

PREPARANDO EL GRID O CUADRICULA

Esta fase crea una estructura de array multidimensional a modo de tabla. Para lograr una buena resolución, crearemos un grid con el mayor número de celdas posible.

Como cada imagen de nuestra base de datos posee un tamaño de 612x612 pixeles, haremos que nuestro grid tenga un tamaño de 51x51, donde cada una de las celdas representará una región de 12x12 pixeles.

Esta tarea se compone de dos procesos que se ejecutan en cada iteración:

DETECCION DEL COLOR REPRESENTATIVO

Este proceso recorre cada celda de esta estructura y aplica a cada celda el color representativo de esa región en la imagen principal, teniendo así una tabla con mútiples colores:

Grid con colores representativos

COMPLEJIDAD ALGORITMICA

Veamos con detalle la complejidad algorítmica de este proceso: Para cada celda del grid, debe buscar el color representativo de esa región en la imagen original.

Por tanto, si consideramos constante la complejidad de obtener el color representativo de una región y, por tanto, despreciable en términos de complejidad computacional; si m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(m * m)

BUSCANDO LA MEJOR IMAGEN

Esta fase aplica la mejor imagen para cada celda del grid. Aunque a priori parece tarea fácil, veremos que en términos computacionales es una labor muy compleja.

Para ello, se debe recorrer cada imagen de nuestra base de datos buscando aquella con menor distancia entre colores representativos, es decir, minimizando la distancia euclídea entre el color representativo de la celda actual y de las fotos que componen nuestra base de datos.

De este modo, nuestro grid resultante quedaría de la siguiente manera:

Grid con imágenes

COMPLEJIDAD ALGORITMICA

Veamos con detalle la complejidad algorítmica de este proceso: Para cada celda del grid debe recorrer cada imagen de nuestra base de datos y seleccionar aquella que mejor se ajuste; o dicho de otro modo, para poder garantizar que se escoge la que mejor se ajusta, es imperativo recorrer todas las imágenes cada vez que se analiza una región del grid.

Así pues, si consideramos constante la complejidad de calcular la distancia euclídea y, por tanto, despreciable en términos de complejidad computacional; si n es el número de imágenes de nuestra selección, m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(n * m * m)

GENERANDO LA IMAGEN FINAL (TARGET)

El último paso del proceso es generar una imagen con la estructura e imágenes que presenta el grid. Así pues, el resultado final es:

Resultado del Fotomosaico

COMPLEJIDAD ALGORITMICA

Veamos con detalle la complejidad algorítmica de este proceso: Para componer la imagen final, se debe escalar la imagen de cada región del grid y componerla en la imagen resultante.

Así pues, si m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(m * m)

ANALISIS DEL RESULTADO

¿A qué se debe que la imagen resultante sea tan poco aproximada a nivel visual? Este algoritmo depende varios factores, entre los que destaca la calidad de las imágenes; no sólo en términos de resolución, sino también en términos de diversidad de colores, tonalidades...

Si nuestra base de datos está compuesta por imágenes con poca diversidad (por ejemplo, muchas en escala de grises o tonos sepia) y queremos hacer un fotomosaico en color, el resultado no será el esperado.

En este caso, como mi base de datos de imágenes es bastane pobre en cantidad y calidad cromática, los resultados obtenidos no son demasiado precisos...

COMPLEJIDAD ALGORITMICA GENERAL

Teniendo en cuenta las complejidades algorítmicas de cada subproceso, el grado de complejidad representativo de esta aplicación es O(n * m * m)

---

MEJORANDO EL ALGORITMO

Podemos aplicar una serie de mejoras a nuestro algoritmo para reducir considerablemene la complejidad del mismo. Dado que el cuello de botella lo tenemos en el proceso de buscar la mejor imagen, podemos hacer uso de algunas técnicas para reducir la complejidad con cierta facilidad:

ARBOLES ESPACIALES: QUADTREE, OCTREE...

Podemos mejorar significativamente el rendimiento de este algoritmo si usamos la búsqueda mediante árboles espaciales: quadtree, octree... Estructuras de datos que permiten realizar operaciones sobre índices espaciales, detección de colisiones, etc.

Si almacenamos las imágenes en este tipo de estructuras clasificadas por sus canales, es decir, mediante sus valores RGB, podríamos realizar búsquedas espaciales dentro del mapa de colores... pero esta parte sería ya contenido de un artículo mucho más avanzado.

COMPLEJIDAD ALGORITMICA

Analicemos las complejidades algorítmicas por cada fase del proceso:

• Preparación de la base de datos. Con esta técnica esta tarea se reduce a insertar cada imagen en el árbol; por tanto, si n es el número de imágenes de nuestra base de datos, el grado de complejidad algorítmica es: O(n * log(n))
• Seleccionar la mejor imagen. La complejidad algorítmica de encontrar la mejor imagen, n es el número de imágenes de nuestra base de datos y m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(m * m * log(n))
• Generando la imagen final. Si m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(m * m)

Por tanto, el grado de complejidad algorítmica con esta técnica es O(m * m * log(n))

PERCEPTUAL HASHES

Podemos aplicar perceptual hash a cada imagen de nuestra base de datos, aplicando así una huella digital única que representa a la imagen con una cadena alfanumérica.

A diferencia de otras funciones criptográficas de hash, que se basan en discriminar cambios entre sus elementos, el perceptual hash se basa en discriminar la similitud de los mismos.

De este modo, el proceso de selección de la mejor imagen para cada región del grid se reduce a devolver una de las entradas que tienen el mismo perceptual hash. Al ser un método heurístico, no devuelve la mejor imagen para cada region, pero sí una de las imágenes que mejor encaja.

COMPLEJIDAD ALGORITMICA

Analicemos las complejidades algorítmicas por cada fase del proceso:

• Preparación de la base de datos. Con esta técnica esta tarea se reduce a calcular el hash de cada imagen; por tanto, si n es el número de imágenes de nuestra base de datos, el grado de complejidad algorítmica es: O(n)
• Seleccionar la mejor imagen. La complejidad algorítmica de encontrar un hash es 1 y, si m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(1 * m * m)
• Generando la imagen final. Si m es el número de divisiones del grid (es decir, 51), el grado de complejidad es O(m * m)

Por tanto, el grado de complejidad algorítmica con esta técnica es O(m * m)

---

AGRADECIMIENTOS

Quisiera agradecer a Alberto Planas, su inestimable ayuda y participación en la conceptualización de este artículo y, más concretamente, sus recomendaciones y sugerencias sobre la optimización de este proceso usando pHash, árboles Quadtree, Octree...

---

DESCARGAR LOS FICHEROS

Si quieres descargarte los ficheros para incluirlos en tu proyecto o bien, realizar modificaciones, hazlo usando el siguiente enlace:

VER LA DEMOSTRACION » DESCARGAR LOS FICHEROS »