"Un-dithering" de una imagen

Hemos visto aquí uno de los esquemas más sencillos para hacer dithering de una fotografía, es decir, tomar una imagen con 256 tonos de gris, por ejemplo, y convertirla solamente a dos colores, buscando que la imagen no pierda tanta información como para que no pueda ser reconocida.

El proceso de dithering se encuentra en muchas de las cosas que hacemos con cotidianidad. Por ejemplo, los periódicos, revistas y libros, imprimen con pocas tintas y tienen que "simular" que se tienen más colores, cosa que hacen haciendo un entramado de los colores disponibles para así engañar al ojo aunque en realidad estamos engañando al cerebro, quien es el que interpreta las imágenes que perciben los ojos.

Aquí hablamos de uno de los esquemas más sencillos, el dithering al azar, el cual dado cada punto de una imagen, se genera un número al azar en el rango de 0 a 255. Si el valor al azar es mayor que el valor del pixel, entonces se pinta un punto blanco, sino, se pinta uno negro. Así de simple. Otros esquemas de dithering, de los cuales hablaremos próximamente, como en el caso del sistema de Floyd-Steinberg, usa una matriz que toma valores muy específicos y se aplican a los pixeles de cierta manera, lo que al final da como resultado una imagen ditherizada mucho mejor que la que se puede realizar con el método al azar.

Pues bien, tomemos la imagen de Lena, un clásico del proceso digital de imágenes y apliquémosle el esquema de Floyd-Steinberg. Este será el resultado:

Lena (original)

Lena (dithering Floyd-Steinberg)

Puede verse que la imagen se ve relativamente bien pero la pregunta entonces es, ¿dada una imagen ditherizada, podemos regresarla a la imagen original? La respuesta simple es NO. La razón de esto es que cuando una imagen se ditheriza, se pierde información y por ende, en principio al menos no es posible reconstruirla y regresar a la imagen original. De hecho, esto es parecido a lo que se ha intentado por años, colorizar fotografías en blanco y negro (tonos de gris). En algunos casos es posible si se tiene información externa, por ejemplo, en el caso de las fotografías de la Segunda Guerra Mundial, probablemente en algún museo se encuentren las ropas que usaban los soldados en ese momento histórico y entonces se puede tener una referencia sobre el color, el cual desde luego, se perdió en una foto en tonos de gris.

Buscando más información encontré un artículo que salió en la revista Dr. Dobbs Journal, ya desaparecida. El autor, Allen Stenger, intenta precisamente regresar a la imagen original a partir de una imagen ditherizada. El artículo puede leerse aquí.

Aunque el trabajo de Stenger no es difícil de seguir, podemos tomar dos elementos fundamentales: toma una matriz de 4x4 pixeles y le aplica una convolución, es decir, un proceso aritmético de sumas y restas entre los pixeles de interés para así lograr efectos como hacer más borrosa una imagen, o bien, hacerla con más detalles, o encontrar los bordes, entre muchos efectos posibles. La convolución de imágenes (y de señales), es un tema común y es relativamente sencillo de hacer.

Pues bien, Stenger sugiere una matriz de 4x4 pixeles para hacer un filtro "blur", el cual hace que la imagen sea más borrosa. La idea de esto es que la imagen ditherizada se convierta -en lo posible- en tonos de gris. Desde luego esto tiene sus limitaciones pero es una idea razonable. Curiosamente Stenger usa una matriz par y el punto de interés, es decir, en donde se aplica la convolución de la matriz, es el de la esquina inferior izquierda. Una vez realizada esta convolución, Stenger usa una matriz de 3x3 pixeles para usar un nuevo filtro de convolución: "sharpen", que busca que se enfaticen los detalles de la imagen.

Decidí probar la idea de Stenger y usando unas rutinas de convolución para Delphi, que pueden descargarse de este sitio, apliqué los filtros de convolución, aunque no usé como Stenger el de 4x4, sino que usé uno de 3x3. Probablemente en algún momento decida ver si el filtro de 4x4 mejora significativamente el resultado final.

He aquí las pruebas. En la primera imagen se ve la imagen de Lena, la original. La siguiente imagen es Lena ditherizada con Floyd-Steinberg. Las imágenes siguientes son el proceso inverso usando las rutinas de convolución que hallé.

Lena (convolución "blur")

Lena (convolución "blur" + "sharpen")

¿Cómo lo valora el lector? ¿Es una buena idea para tratar de recuperar la imagen original? ¿Algo así como "de lo perdido lo encontrado"?

FotoMorsaicos

En el 2001 me enfrasqué en una idea, surgida cuando vi el cartel de la película The Truman Show. Ahí se observaba el rostro de Jim Carrey armado con pequeñas fotos, todas con escenas de la película. Me quedé suspenso. ¿Cómo es que se podía hacer esto usando la computadora? porque me quedó claro desde el primer momento que no era un trabajo manual.

Así, empecé a investigar y hallé mucha información, aunque ninguna explicaba estrictamente cómo es que se hacían este tipo de imágenes. Durante un año, aproximadamente, la idea recurría a mí y pensaba en las diferentes alternativas, hasta que un día me di cuenta de la simpleza atrás del algoritmo para crear estos mosaicos. Considérese que la imagen con la que se va a trabajar se divide en una malla, en donde cada cuadrito de la misma contendrá una foto en particular. Así, se toma la primera región (o cuadro) de la malla. Se calcula el color promedio de esa sección. Ahora se busca una imagen que coincida con ese color promedio y se sustituye en dicha malla. Y así se hace con toda la imagen. De hecho, el truco es que en lugar de poner un color sólido, que represente la región en la que se está trabajando, se usa una fotografía que -en principio- contenga ese color promedio (lo más cercano posible).

El manejo del color en las imágenes se hace a través de sus componentes de color R(ed), G(reen) y B(lue). Vía estos componentes, cada imagen de la biblioteca que se usará para crear el morsaico, puede representar un color promedio específico. Para hallar qué imagen es la más cercana a la región que estamos procesando, lo que hacemos es usar la ecuación de la distancia en el espacio euclidiano. Hallamos que sqrt((R2-R1)^2+(G2-G1)^2+(B2-B1)^2) nos dice cuál es la distancia de la región procesada a cada imagen de la biblioteca (a la cual ya le sacamos previamente sus colores promedio). De esta manera, la imagen con la mínima distancia nos indicará cuál es la más cercana. Eso, considerando los tres ejes X, Y y Z, que en este caso son R, G y B, nos muestran en realidad un espacio tridimensional, en donde las imágenes son puntos en dicho espacio y la región a procesar es otro punto. Así, se hace el cálculo de la distancia para cada imagen, y se obtiene la mejor aproximación. Cabe decir que en la mejora al software, se uso una ecuación "parchada" por Riemersma, sobre la original de la distancia euclidiana.

Cuando me di cuenta de esto, puse manos a la obra y ya no recuerdo, pero probablemente en una semana tuve un primer programa que podía hacer fotoMorsaicos. Encontré además un artículo sobre cómo el ojo discrimina colores, de un holandés de apellido Riemersma. Usé su idea para que la computadora eligiera de manera más "humana" la foto que debía poner. Curiosamente el holandés me escribió para decirme que nunca hubiese esperado que su estudio hubiese servido para usarse en la técnica de los fotomosaicos. De hecho, esto es una mejora significativa a lo que hace Silvers originalmente.

Hubo -desde luego- que resolver montones de problemas, aunque el peor fue el conseguir una buena colección de imágenes para trabajar con ellas. Así que me gasté unos 200 dólares para hacerme de unas 65000 imágenes de 24 bits de resolución, de 640x480 pixeles, aproximadamente. Agregué algunos detalles, como la posibilidad de evitar repeticiones en la imagen que se colocaba (al menos por una cantidad definida de fotos) y hallé que el reusltado era satisfactorio.

Analicé lo que hacía Robert Silvers, y encontré cómo es que le quedaban tan bien sus fotomosaicos. Aparentemente "fusionaba" la imagen original (como si fuese una imagen semitransparente) sobre la foto mosaiqueada, dándole así mucho más precisión y certeza a la imagen final. A este proceso se le llama "blending" y en photoshop se hace de manera muy rápida. Cabe señalar que Silvers indica que él no hace blending. Yo podría demostrarle que está mintiendo. Es un hecho que en muchas ocasiones resultaría muy afortunado sustituir una región de la foto original por una imagen que contuviese el color promedio de dicha región y que, además, pudiese tener algunas partes con las sombras en los mismos lugares que la región original. Quizás una o dos fotos podrán tener estas características, pero es claro que la solución más simp,e a esta dificultad es el blending (si se hace en no más de un 35% sobre la foro morsaiqueada).

Cuando terminé mi programa, escribí al Dr. Dobbs Journal para ver si les interesaba publicarlo, y en Noviembre del 2001 salió mi primer artículo en inglés en una revista especializada en programación. Hay que señalar que Silvers, cuando supo de mi artículo y de mi intención de publicar el código fuente, intentó evitarlo con la amenaza de demandar a la revista si así actuaba. Los editores de la misma me dijeron: "si quiere demandar, que lo haga. No puede ganarnos. Ya discutimos eso con nuestros abogados".

El primero fotoMorsaico fue el de Ilse (sí, la cantante de Flans). Dicho Morsaico no tiene blending, por cierto. Y eaún así el resultado final me parece bastante satisfactorio. Para una plática que di en la UNAM (en Siggraph), al respecto de este trabajo, me hice mi propio Morsaico, en un acto egocéntrico típico.

Finalmente, después de haber realizado todo este trabajo, hallé que la descripción de lo que Silvers hizo se encuentra relativamente documentado en la oficina de Patentes de los EEUU. El propio Silvers nos da el número de patente. Así que busqué y hallé la descripción completa. Para quien le interese, entre aquí.