La compresión fractal es un método de compresión con pérdida para imágenes digitales , basado en fractales . El método es más adecuado para texturas e imágenes naturales, basándose en el hecho de que partes de una imagen a menudo se parecen a otras partes de la misma imagen. [1] Los algoritmos fractales convierten estas partes en datos matemáticos llamados "códigos fractales" que se utilizan para recrear la imagen codificada.
La representación de imágenes fractales puede describirse matemáticamente como un sistema de funciones iteradas (SFI). [2]
Comenzamos con la representación de una imagen binaria , donde la imagen puede considerarse como un subconjunto de . Un SFI es un conjunto de aplicaciones de contracción ƒ 1 ,..., ƒ N ,
De acuerdo con estas funciones de mapeo, el SFI describe un conjunto bidimensional S como el punto fijo del operador de Hutchinson.
Es decir, H es un operador que mapea conjuntos a conjuntos, y S es el único conjunto que satisface H ( S ) = S . La idea es construir el SFI de modo que este conjunto S sea la imagen binaria de entrada. El conjunto S se puede recuperar del SFI mediante iteración de punto fijo : para cualquier conjunto inicial compacto no vacío A 0 , la iteración A k +1 = H ( A k ) converge a S .
El conjunto S es autosimilar porque H ( S ) = S implica que S es una unión de copias mapeadas de sí mismo:
Así que vemos que el IFS es una representación fractal de S.
La representación IFS se puede extender a una imagen en escala de grises considerando el gráfico de la imagen como un subconjunto de . Para una imagen en escala de grises u ( x , y ), considere el conjunto S = {( x , y , u ( x , y ))}. Entonces, de manera similar al caso binario, S se describe mediante un IFS utilizando un conjunto de aplicaciones de contracción ƒ 1 ,..., ƒ N , pero en ,
Un problema desafiante de la investigación actual en la representación de imágenes fractales es cómo elegir ƒ 1 ,..., ƒ N de manera que su punto fijo se aproxime a la imagen de entrada, y cómo hacerlo de manera eficiente.
Un enfoque simple [2] para hacerlo es el siguiente sistema de funciones iteradas particionadas (PIFS):
En el segundo paso, es importante encontrar un bloque similar para que el IFS represente con precisión la imagen de entrada, por lo que se debe considerar una cantidad suficiente de bloques candidatos para D i . Por otro lado, una búsqueda grande que considere muchos bloques es computacionalmente costosa. Este cuello de botella en la búsqueda de bloques similares es la razón por la que la codificación fractal PIFS es mucho más lenta que, por ejemplo, la DCT y la representación de imágenes basada en wavelets .
El algoritmo inicial de partición cuadrada y búsqueda de fuerza bruta presentado por Jacquin proporciona un punto de partida para futuras investigaciones y extensiones en muchas direcciones posibles: diferentes formas de dividir la imagen en bloques de rango de varios tamaños y formas; técnicas rápidas para encontrar rápidamente un bloque de dominio lo suficientemente coincidente para cada bloque de rango en lugar de una búsqueda de fuerza bruta, como algoritmos de estimación de movimiento rápido ; diferentes formas de codificar la asignación del bloque de dominio al bloque de rango; etc. [3]
Otros investigadores intentan encontrar algoritmos para codificar automáticamente una imagen arbitraria como RIFS (sistemas de funciones iteradas recurrentes) o IFS global, en lugar de PIFS; y algoritmos para la compresión de video fractal que incluyan compensación de movimiento y sistemas de funciones iteradas tridimensionales. [4] [5]
La compresión de imágenes fractales tiene muchas similitudes con la compresión de imágenes por cuantificación vectorial . [6]
Con la compresión fractal, la codificación es extremadamente costosa en términos computacionales debido a la búsqueda que se utiliza para encontrar las autosimilitudes. Sin embargo, la decodificación es bastante rápida. Si bien esta asimetría hasta ahora la ha hecho poco práctica para aplicaciones en tiempo real, cuando el video se archiva para su distribución desde el almacenamiento en disco o descargas de archivos, la compresión fractal se vuelve más competitiva. [7] [8]
En relaciones de compresión comunes, hasta aproximadamente 50:1, la compresión fractal proporciona resultados similares a los algoritmos basados en DCT como JPEG . [9] En relaciones de compresión altas, la compresión fractal puede ofrecer una calidad superior. Para imágenes satelitales, se han logrado relaciones de más de 170:1 [10] con resultados aceptables. Se han logrado relaciones de compresión de video fractal de 25:1–244:1 en tiempos de compresión razonables (2,4 a 66 s/fotograma). [11]
La eficiencia de la compresión aumenta con una mayor complejidad de la imagen y profundidad del color, en comparación con las imágenes simples en escala de grises .
Una característica inherente de la compresión fractal es que las imágenes se vuelven independientes de la resolución [12] después de ser convertidas a código fractal. Esto se debe a que los sistemas de funciones iteradas en el archivo comprimido se escalan indefinidamente. Esta propiedad de escala indefinida de un fractal se conoce como "escalamiento fractal".
La independencia de la resolución de una imagen codificada fractalmente se puede utilizar para aumentar la resolución de visualización de una imagen. Este proceso también se conoce como "interpolación fractal". En la interpolación fractal, una imagen se codifica en códigos fractales mediante compresión fractal y, posteriormente, se descomprime a una resolución más alta. El resultado es una imagen sobremuestreada en la que se han utilizado sistemas de funciones iteradas como interpolante . [13] La interpolación fractal mantiene muy bien los detalles geométricos en comparación con los métodos de interpolación tradicionales, como la interpolación bilineal y la interpolación bicúbica . [14] [15] [16] Sin embargo, dado que la interpolación no puede revertir la entropía de Shannon, termina agudizando la imagen al agregar detalles aleatorios en lugar de significativos. No se puede, por ejemplo, ampliar una imagen de una multitud donde la cara de cada persona tiene uno o dos píxeles y esperar identificarlos.
Michael Barnsley dirigió el desarrollo de la compresión fractal desde 1985 en el Instituto de Tecnología de Georgia (donde tanto Barnsley como Sloan eran profesores en el departamento de matemáticas). [17] El trabajo fue patrocinado por DARPA y la Corporación de Investigación de Georgia Tech . El proyecto resultó en varias patentes a partir de 1987. [18] El estudiante de posgrado de Barnsley, Arnaud Jacquin, implementó el primer algoritmo automático en software en 1992. [19] [20] Todos los métodos se basan en la transformación fractal utilizando sistemas de funciones iteradas . Michael Barnsley y Alan Sloan formaron Iterated Systems Inc. [21] en 1987, a la que se le concedieron más de 20 patentes adicionales relacionadas con la compresión fractal.
Un gran avance para Iterated Systems Inc. fue el proceso automático de transformación fractal, que eliminó la necesidad de intervención humana durante la compresión, como era el caso en los primeros experimentos con la tecnología de compresión fractal. En 1992, Iterated Systems Inc. recibió una subvención gubernamental de 2,1 millones de dólares [22] para desarrollar un prototipo de chip de almacenamiento y descompresión de imágenes digitales utilizando la tecnología de compresión de imágenes por transformación fractal.
La compresión de imágenes fractales se ha utilizado en diversas aplicaciones comerciales: onOne Software, desarrollado bajo licencia de Iterated Systems Inc., Genuine Fractals 5 [23], que es un complemento de Photoshop capaz de guardar archivos en formato FIF (Fractal Image Format) comprimido. Hasta la fecha, el uso más exitoso de la compresión de imágenes fractales lo ha hecho Microsoft en su enciclopedia multimedia Encarta [24] , también bajo licencia.
Iterated Systems Inc. suministró un codificador shareware (Fractal Imager), un decodificador independiente, un decodificador de complemento Netscape y un paquete de desarrollo para su uso en Windows. La redistribución de la "DLL descompresora" proporcionada por el SDK ColorBox III se regía por regímenes restrictivos de licencias por disco o por año para los vendedores de software propietario y por un esquema discrecional que implicaba la promoción de los productos de Iterated Systems para determinadas clases de otros usuarios. [25]
ClearVideo (también conocido como RealVideo (Fractal)) y SoftVideo fueron los primeros productos de compresión de vídeo fractal. ClearFusion fue el complemento de streaming de vídeo distribuido gratuitamente por Iterated para navegadores web. En 1994, Spectrum Holobyte licenció SoftVideo para su uso en sus juegos en CD-ROM, incluidos Falcon Gold y Star Trek: The Next Generation A Final Unity . [26]
En 1996, Iterated Systems Inc. anunció [27] una alianza con Mitsubishi Corporation para comercializar ClearVideo a sus clientes japoneses. El controlador del decodificador ClearVideo 1.2 original todavía es compatible [28] con Microsoft en Windows Media Player , aunque el codificador ya no es compatible.
Dos empresas, Total Multimedia Inc. y Dimension, afirman poseer o tener la licencia exclusiva de la tecnología de video de Iterated, pero ninguna ha lanzado aún un producto funcional. La base tecnológica parece ser las patentes estadounidenses 8639053 y 8351509 de Dimension, que han sido analizadas considerablemente. [29] En resumen, es un sistema simple de copia de bloques de árbol cuádruple sin la eficiencia de ancho de banda ni la calidad PSNR de los códecs tradicionales basados en DCT. En enero de 2016, TMMI anunció que abandonaba por completo la tecnología basada en fractales.
Los artículos de investigación publicados entre 1997 y 2007 analizaron posibles soluciones para mejorar los algoritmos fractales y el hardware de codificación. [30] [31] [32] [33] [34] [35] [36] [37] [38]
Ullrich Hafner creó una biblioteca llamada Fiasco . En 2001, Linux Journal se ocupó de Fiasco . [39] Según el manual de Fiasco de 2000-04, Fiasco se puede utilizar para la compresión de vídeo. [40] La biblioteca Netpbm incluye la biblioteca Fiasco . [41] [42]
Femtosoft desarrolló una implementación de compresión de imágenes fractales en Object Pascal y Java . [43]
