Implementación y evaluación de algoritmos para la compresión fractal en bloques

Abstract

Ante el aumento incesante de la resolución de las imágenes y de la utilización masiva de multimedios, día a día el espacio disponible en los dispositivos de almacenamiento se va reduciendo. Del mismo modo, cada vez es mayor la cantidad de imágenes a transmitir a través de las redes y un tamaño excesivo de éstas harían que los costos sean inaceptables. La Compresión Fractal por Bloques (CFB) es relativamente nueva, pero ha evidenciado grandes progresos y concitado el interés de investigadores de todo el ámbito tecnológico y académico. Los buenos resultados obtenidos han hecho que importantes empresas ya la estén utilizando. A modo de ejemplo puede citarse a la Enciclopedia Encarta©, de Microsoft©, cuyas imágenes fueron almacenadas utilizando la tecnología brindada por la compresión fractal.

Existen varios métodos de compresión de imágenes, pero la Compresión Fractal posee caracteríaticas únicas. Éste método se encuentra entre los que codifican la imagen con pérdida de información. De todos modos, el error puede llegar a ser muy bajo y como beneficios obtenemos una muy reducida cantidad de bits para caracterizar a la imagen original. El método general de la CFB es muy sencillo ya que se basa en la presunción de que existe redundancia aprovechable en toda imagen. Para ésto la imagen es desarmada en bloques rango y se busca, para cada rango, una transformación de un bloque dominio mayor tal que el dominio tranformado se vea similar al rango. La aproximación fractal de la imagen es construida iterando estos mapas sobre una imagen inicial arbitraria. La búsqueda de correspondencia entre los bloques y la evaluación del error cometido, sin embargo, presenta muchas posibles alternativas desde la búsqueda por fuerza bruta hasta la utilización de algoritms de optimización diseñados para los métodos numéricos.

No todas las alternativas han sido exhaustivamente exploradas, y la CFB exhive una gran sensibilidad a cualquier incremento de la eficiencia, produciendo mejores resultados en menor tiempo, o relaciones de compromiso costo-calidad-tiempo más adecuadas. En este trabajo evalúan implementaciones alternativas del método para conocer y comparar sus características principales. La CFB exhibe en algunos casos una buena relación de compromiso entre la compresión, la calidad de la imagen codificada, y el tiempo de compresión y descompresión. Se muestran ejemplos de relaciones de compresión de hasta 100:1 con resultados visualmente aceptables, obtenidos por medio de adecuados ajustes a parámetros del algoritmo.