COMPRESION DE IMAGENES

Resumen

Utilizando como punto de partida el método esbozado por Barsnley en [1], se elaboró una variante factible para la compresión no reversible de imágenes en tonos de gris, utilizando la Geometría Fractal y el Teorema del Collage. Las técnicas peculiares empleadas permitieron reducir los costos en tiempo con concesiones mínimas en la calidad de la imagen resultante. Los resultados obtenidos son comparables con los expuestos en trabajos similares como [2].

Introducción

En el almacenamiento y manipulación en general de imágenes digitales, los métodos de compresión juegan un importante papel al hacer posible que éstas sean almacenadas en menor espacio sin provocar una notable degradación de la información que contienen. Uno de los más novedosos esquemas de compresión conocidos, tiene su basamento en la Geometría Fractal y en la Teoría de los Sistemas Dinámicos.

En las imágenes o figuras fractales es posible apreciar la existencia de similaridad entre porciones de las mismas y la figura en sí, esto quiere decir que dichas figuras aparecen formadas por copias de si mismas. O sea, si le es efectuada a la figura cierta transformación de escalamiento, traslación, rotación o una combinación de éstas, se obtiene como resultado una nueva figura que es semejante a determinada porción de la imagen original.

                           


Figura 1.Imágenes fractales. Triángulo de Sierpinski. Hoja de Helecho.

La propiedad anterior de este tipo de imágenes, conocida como self similarity o autoescalamiento, posibilita que las mismas sean almacenadas como una colección de transformaciones, a partir de las cuales son generadas cada una de sus porciones. De este modo se reduce en gran medida el espacio necesario para su almacenamiento, ya que las transformaciones a usar tienen solamente seis coeficientes, y con un reducido número de ellas es posible generar imágenes bastante complicadas.

Las colecciones de transformaciones definen sistemas de la forma:



Utilizando estos sistemas es muy simple generar las imágenes. Para esto se parte de un punto inicial cualquiera (x,y) y se toma aleatoriamente una de las funciones del sistema, la cual es evaluada en el punto (x,y) para obtener un nuevo punto(x¹,y¹), este punto debe ser dibujado en el plano. Este proceso se repite tomando al punto (x¹,y¹) como nuevo punto de partida y así sucesivamente hasta que se alcance el nivel de detalle deseado o que en el proceso iterativo, el sistema alcance su punto fijo o invariante. Los primeros puntos que se van obteniendo no deben ser dibujados, en espera de que el sistema se estabilice. De esta sencilla forma, pueden obtenerse figuras tan complicadas como la hoja de helecho de la figura 1.



Figura 2.Transformaciones para generar la hoja de helecho.

Las colecciones de transformaciones constituyen un modelo matemático llamado Sistema de Funciones Iteradas, y la única condición que debe cumplir cada W_i es ser contractiva. A partir de este echo, se puede asegurar que el sistema W también es contractivo, lo que permite hacer uso del Teorema del Punto Fijo de Banach para asegurar que siempre será posible obtener, a partir de W, una imagen y que ésta siempre será la misma (el atractor del sistema).

Además, un importante resultado de la Teoría de los Sistemas Dinámicos, conocido como Teorema del Collage, garantiza que se pueda obtener una imagen final arbitrariamente cercana a la que se desea.

Las ventajas en cuanto a requerimiento de espacio en disco que se obtienen al almacenar imágenes fractales como una colección de transformaciones, hacen que se intente generalizar esta idea, de manera que pueda ser aplicada a cualquier tipo de imagen, por ejemplo la imagen de una casa, un paisaje o un rostro humano.

Ampliando el Modelo

El hecho de que estas imágenes tengan color (tonos de gris), adiciona una dimensión al problema de encontrar las transformaciones adecuadas, ya que no basta saber dónde pintar. Es necesario además determinar el color que corresponde. Ahora hay que tener en cuenta la variación que va a sufrir la tonalidad de gris de cada punto involucrado en una copia, por lo que las transformaciones a usar tendrán la forma siguiente:



donde g y h van a controlar el cambio de contraste y brillo que ha de sufrir el color en la copia.

En imágenes arbitrarias no se encuentra el tipo de similitud tan evidente que se apreciaba en los fractales de la figura 1. Sin embargo es posible encontrar en ellas diferentes porciones que son similares entre sí, y que van a permitir, en analogía con el caso anterior, describirlas como copias de partes de sí misma.

Por ejemplo, sean R y D porciones cuadradas en la imagen. Entonces la expresión:



permite describir la distancia existente entre la cualquier copia de la región D y la región R. Donde d_i y r_i son los valores de color para cada punto de las regiones D y R respectivamente.

Puede ocurrir, y no es extraño que así sea, que para determinada porción R, no se encuentre una porción D, con la misma orientación de R que brinde un buen grado de parecido. Sin embargo pueden existir porciones con diferente orientación que sí lo tengan. Un ejemplo de esto se muestra en la siguiente figura:


Figura 3.Correspondencia considerando rotaciones.

Descripción del Método

Codificar una imagen significa encontrar una colección de transformaciones W tal que el punto fijo || de W esté lo suficientemente cercano de la imagen en cuestión.

Para esto debe segmentarse la imagen en porciones que la cubran totalmente y que no se superpongan entre sí. A estas regiones se les denomina rangos y en este caso son cuadradas. A cada una de ellas se le asocia otro cuadro en la imagen, que será aquel que más se le parezca según lo visto anteriormente, al que se le denomina dominio. Con estas asociaciones quedan establecidas las transformaciones que harán posible generar la imagen posteriormente. La relación de tamaño entre rangos y dominios es de 1 a 2, o sea, si los rangos son de lado q los dominios serán de lado2q.

Mientras mayor sea el tamaño de los rangos, mejores radios de compresión se lograrán, pues menor será la cantidad de rangos y por lo tanto menor será también la cantidad de transformaciones a almacenar. Sin embargo, mientras mayor sea un rango, más difícil será encontrarle un dominio realmente parecido y la degradación de la información contenida en la imagen será mucho mayor. Por tanto, el tamaño de los rangos debe ser seleccionado de acuerdo a las características de la imagen sobre la zona en que va a ser situado, de forma que se logren buenos radios de compresión y se minimice la pérdida de información.

Los tamaños de rangos usados son de 4x4, 8x8 y 16x16 pixels. Estos últimos al ser los mayores son situados (en caso de que sea posible) sobre las regiones de la imagen en las que menor cantidad de detalles exista, por ejemplo zonas uniformes en la tonalidad de color, para de esta forma garantizar menores pérdidas. El resto de la imagen es cubierta provisionalmente, con rangos de 8x8 pixels, y luego aquellos para los que no se logre una buena relación rango-dominio con ese tamaño, son divididos en cuatro nuevos rangos de 4x4 pixels.

Optimización de la Búsqueda

Un aspecto importante en el proceso de compresión es que el tiempo necesario para encontrar porciones similares no debe ser muy alto. Para lograr esto, las búsquedas se realizan de acuerdo a las particularidades de cada rango. Por ejemplo, a los rangos que cubren zonas de la imagen con bajo nivel de detalle se les trata de asociar dominios que tengan sus mismas características, limitándose así las zonas a tener en cuenta, y con ello el tiempo.

Además, es de esperar que se mantengan localmente las características de la imagen, por lo que para el resto de los rangos la búsqueda se realiza en una vecindad de sus posiciones, lográndose en la mayoría de los casos asociaciones adecuadas, y en muy poco tiempo debido al reducido tamaño del área de donde se seleccionan los dominios.

En los casos que esto no se logre, los rangos pendientes se clasifican en dos grupos: los que son atravesados por contornos de la imagen y los que no, para de esta forma limitar el espacio de búsqueda de sus dominios a aquellas zonas con sus mismas características. Por ejemplo, en la figura 4 se aprecia que para el rango R es más conveniente el dominio D que el D', y lo contrario ocurre con R'.


Figura 4.Correspondencia considerando bordes.

Por último, se ha determinado empíricamente, que para casi todos los rangos, el dominio hallado se encuentra en una vecindad del mismo. Por este motivo se introdujo una restricción del espacio de búsqueda a una vecindad de radio 25 pixeles del rango. Este paso acelera enormemente el proceso y las pérdidas por degradación se reducen a valores aceptables.

Conclusiones

Se ha obtenido un método utilizable para la compresión de imágenes en grises. La eficiencia del algoritmo debe ser mejorada aún, sin embargo los tiempos obtenidos son soportables. Comparando con otras referencias hemos obtenido menores radios de compresión, pero mejor calidad en las imágenes resultantes, por lo que continuaremos con el desarrollo de esta metodología. Los pasos siguientes deben dirigirse a acelerar aun más el proceso y a la introducción del color.

Con los resultados expuestos se construyó una aplicación de prueba que permitió evaluar el método satisfactoriamente en la práctica.

a página principal