Compresión fractal

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 el más apropiado 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. Los algoritmos fractales convierten estas partes en datos matemáticos llamados «códigos fractales» los cuales se usan para recrear la imagen codificada.

Sistema de funciones iteradas

Artículo principal: Sistema de funciones iteradas

Una representación de imagen fractal puede ser descrita matemáticamente como un sistema de funciones iteradas (SFI).

Para imágenes binarias

Comenzando con la representación de una imagen binaria, donde la imagen puede ser descrita como un subconjunto de ${\displaystyle \mathbb {R} ^{2}}$ . Un SFI es un conjunto de contracciones ƒ₁,...,ƒ_N,

${\displaystyle f_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}.}$ 

De acuerdo con estas funciones, el SFI describe un conjunto bi-dimensional S como el punto fijo del operador de Hutchinson

${\displaystyle H(A)=\bigcup _{i=1}^{N}f_{i}(A),\quad A\subset \mathbb {R} ^{2}.}$ 

Siendo, H un conjunto operador a conjunto, y S el único conjunto que satisface H(S) = S. La idea es construir el SFI de tal forma que el conjunto S es la imagen binaria. El conjunto S puede ser recuperado del SFI mediante el método del punto fijo: para cualquier conjunto inicial compacto no vacío A₀, la iteración A_k+1 = H(A_k) converge a S.

El conjunto S es igual a sí mismo porque H(S) = S implica que S es una unión de copias de sí mismo:

${\displaystyle S=f_{1}(S)\cup f_{2}(S)\cup \cdots \cup f_{N}(S)}$ 

Así que vemos que SFI es una representación fractal de S.

Extensión a la escala de grises

La representación SFI puede ser extendida a una imagen en escala de grises considerando la gráfica de la imagen como un subconjunto de ${\displaystyle \mathbb {R} ^{3}}$ . Para una imagen en escala de grises u(x,y), considerar el conjunto S = {(x,y,u(x,y))}. Entonces, al igual que el caso binario, S se describe por un SFI utilizando una serie de contracciones ƒ₁,...,ƒ_N, pero en ${\displaystyle \mathbb {R} ^{3}}$ ,

${\displaystyle f_{i}:\mathbb {R} ^{3}\to \mathbb {R} ^{3}.}$ 

Codificación

Un problema de la investigación sobre la representación fractal de la imagen es como elegir ƒ₁,...,ƒ_N de tal forma que su punto fijo se aproxime a la imagen de entrada, y cómo hacer esto de forma eficiente. Una simple aproximación^[1]​ para hacer esto es la siguiente:

1. Particionar la imagen en bloques R_i de tamaño s×s.
2. Para cada R_i, buscar en la imagen para encontrar un bloque D_i de tamaño 2s×2s que sea similar a R_i.
3. Seleccionar las funciones de mapeo tal que H(D_i) = R_i para cada i.

En el segundo paso, es importante encontrar un bloque similar para que el SFI represente fielmente la imagen de entrada, así que necesitan ser considerados un número suficiente de bloques candidatos para D_i. Por otro lado, una larga búsqueda considerando muchos bloques es computacionalmente costoso.

Este cuello de botella, consistente en buscar bloques similares es la razón por la que la codificación fractal es mucho más lenta que, por ejemplo, la representación de imágenes basadas en la transformada de coseno discreta y en óndula.

Características

Con la compresión fractal, la codificación es extremadamente cara a nivel computacional debido a la búsqueda de similitudes propias. Sin embargo, la decodificación es bastante rápida. Mientras que esta asimetría lo hace poco práctico para aplicaciones en tiempo real, cuando el vídeo es guardado para distribución desde un disco, la compresión fractal llega a ser más competitiva.^[2]​^[3]​

En ratios de compresión comunes, sobre 50:1, la compresión fractal proporciona resultados similares a algoritmos basados en la transformada de coseno discreta como JPEG. ^[4]​ A ratios de compresión elevados, la compresión fractal puede ofrecer una calidad superior. Para imágenes por satélite, se han utilizado ratios 170:1 con resultados aceptables.^[5]​ La compresión fractal de vídeo en ratios de 25:1 a 244:1 se han realizado en tiempos razonables (2,4 a 66 seg/imagen).^[6]​

La eficiencia en la compresión se incrementa con la complejidad de la imagen y la profundidad de color, en comparación a las simples imágenes en escala de grises.

Independencia de la resolución y escalado fractal

Una característica inherente de la compresión fractal es que las imágenes se vuelven independientes de la resolución^[7]​ tras ser convertidos al código fractal. Esto es así porque el sistema de función iterada en el archivo comprimido se escala indefinidamente. Esta propiedad de escalado es conocida como "escalado fractal".

Interpolación fractal

La independencia de la resolución de una imagen codificada en fractal puede utilizarse para incrementar la resolución de una imagen. Este proceso se conoce como "interpolación fractal". En la interpolación fractal, una imagen se codifica a código fractal mediante compresión fractal, y posteriormente descomprimida a una resolución superior. El resultado es una imagen en la que los sistemas de función iterada se han usado como interpolantes.^[8]​ La interpolación fractal mantiene muy bien el detalle geométrico en comparación con los métodos de interpolación tradicionales como la Interpolación bilinear y la Interpolación bicúbica.^[9]​^[10]​^[11]​

Historia

Michael Barnsley inició el desarrollo de la compresión fractal en 1987, y creó varias patentes sobre dicha tecnología.^[12]​ El algoritmo de compresión fractal práctico más ampliamente conocido fue inventado por Barnsley y Alan Sloan. El estudiante de postgrado de Barnsley, Arnaud Jacquin implementó el primer algoritmo automático en 1992.^[13]​^[14]​ Todos los métodos se basan en la transformación fractal utilizando el sistema de funciones iteradas. Michael Barnsley y Alan Sloan crearon Iterated Systems Inc.^[15]​ en 1987 donde crearon sobre 20 patentes adicionales relacionadas con la compresión fractal.

Un gran avance para Iterated Systems Inc. fue el proceso de transformación fractal automático, el cual eliminó la necesidad de intervención humana durante la compresión como era el caso en la experimentación temprana con la tecnología de compresión fractal. En 1992 Iterated Systems Inc. recibió una subvención de 2,1 millones de dólares del gobierno^[16]​ para desarrollar un prototipo de chip para almacenamiento de imágenes digitales y descompresión utilizando tecnología de compresión de imagen mediante transformación fractal.

La compresión fractal de imagen se ha añadido en varias aplicaciones comerciales: onOne Software, desarrollado bajo licencia de Iterated Systems Inc., Genuine Fractals 5^[17]​ que es un plugin de Photoshop capaz de grabar archivos en formato comprimido FIF (Fractal Image Format). Hasta la fecha, el uso más exitoso de la compresión fractal de imágenes viene de parte de Microsoft en su enciclopedia multimedia Encarta,^[18]​ también bajo licencia.

Iterated Systems Inc. proporcionó un codificador shareware (Fractal Imager), un decodificador independiente, un plugin decodificador para Netscape y un paquete de desarrollo para su uso bajo Windows. Como los métodos basados en óndula mejoraron y fueron más fácilmente licenciables por vendedores de software comercial, la adopción del formato FIF no evolucionó.

Durante la década de 1990, Iterated Systems Inc. y asociados invirtieron considerables recursos para llevar la compresión fractal al vídeo. Mientras que los resultados de la compresión eran prometedores, el hardware de la época carecía de la potencia de procesado necesaria para que la compresión de vídeo fuera práctica. Se requerían hasta 15 horas para comprimir un solo minuto de vídeo.

ClearVideo — también conocido como RealVideo (Fractal) — y SoftVideo son los primeros productos de compresión fractal de vídeo. ClearFusion era el plugin de streaming de vídeo de Iterated para navegadores web distribuido gratuitamente. En 1994, SoftVideo fue licenciado a Spectrum Holobyte para usarlo en sus juegos en CD-ROM incluyendo Falcon Gold y "Star Trek: The Next Generation A Final Unity".^[19]​

En 1996, Iterated Systems Inc. anunció^[20]​ una alianza con la Corporación Mitsubishi para comercializar ClearVideo a sus clientes japoneses. El decodificador original, ClearVideo 1.2 todavía está soportado^[21]​ por Microsoft en Windows Media Player aunque el codificador ya no está soportado.

Durante los últimos años, se han publicado numerosas discusiones sobre posibles soluciones para mejorar los algoritmos fractales y el hardware necesario para su codificación.^[22]​^[23]​^[24]​^[25]​^[26]​^[27]​^[28]​^[29]​^[30]​

Código abierto

Ullrich Hafner creó una librería llamada Fiasco y fue descrita en la revista Linux Journal.^[31]​

La librería Netpbm incluye una librería Fiasco. ^[32]​ ^[33]​

Hay una librería para compresión fractal de vídeo. ^[34]​

Hay otro ejemplo de implementación de Femtosoft. ^[35]​

Véase también

• Sistema de funciones iteradas
• Compresión de imagen
• Óndula

Referencias

1. Fischer, Y. (1992). «Fractal Image Compression». SIGGRAPH'92 course notes. 
2. Alternativas a la compresión de imagen y consideraciones sobre almacenamiento de medios el 3 de marzo de 2008 en Wayback Machine. Georgia Institute of Technology reference to compression/decompression time.
3. Heath, Steve (1999). Multimedia and Communications Technology. Focal Press. pp. 120-123. ISBN 0240515293. 
4. Sayood, Khalid (2005). Introducción a la Compresión de Datos, Tercera Edición. Morgan Kaufmann. pp. 560-569. ISBN 012620862X. 
5. Geoscience and Remote Sensing Symposium paper Achieving high data compression of self-similar satellite images using fractal.
6. Codificación fractal de secuencias de vídeo
7. Byte Magazine article on fractal compression/resolution independence
8. Método de decodificación por interpolación con parámetros variables para compresión de imagen fractal Colegio de Matemáticas y Física, Universidad UChongqing, China
9. Smooth fractal interpolation Departamento de Matemáticas, Universidad de Zaragoza, Campus Plaza de San Francisco, Zaragoza, Spain
10. Hokkaido Univ., Graduate School of Engineering, JPN
11. Nagasaki University, Faculty of Engineering
12. Patente USPTO n.º 4941193 – La primera patente del sistema de funciones iteradas de Barnsley y Sloan, en octubre de 1987
13. Uso de Codificación Fractal para Indexar Contenido de Imagen para una Biblioteca Digital Tech report
14. Arnaud E. Jacquin. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations. IEEE Transactions on Image Processing, 1(1), 1992.
15. Iterated Systems Inc. cambia su nombre a en 2001 y fue comprada por Interwoven, Inc. en 2003)
17. Genuine Fractals Product Review
18. . Archivado desde el original el 31 de agosto de 2016. Consultado el 21 de junio de 2011. 
19. 1994 Manual specifying on page 11 SoftVideo under license to Spectrum Holobyte
20. Mitsubishi Corporation ClearVideo press release
21. Microsoft ClearVideo support
22. Avances en la compresión fractal para aplicaciones multimedia
23. Cálculo rápido de los parámetros SFI para codificación de imagen fractal
24. Fractal image compression performance synthesis through HV partitioning
25. Simple y rápida compresión de imagen fractal Circuitos, Señales, y sistemas - 2003
26. Esquema de algoritmo genetico para compresión fractal de imagen Departamento de Ingeniería Eléctrica, Universidad National Sun Yet-Sen, Kaohsiung, Taiwan
27. Un método rápido de codificación de imagen fractal basado en la búsqueda inteligente de desviación estándar Departamento de Ingeniería Eléctrica y Computacional, Universidad de Alabama
28. Novel fractal image-encoding algorithm based on a full-binary-tree searchless iterated function system Department of Electrical and Computer Engineering, The University of Alabama
29. Método de clásificación rápido para compresión fractal de imagen Proc. SPIE Vol. 4122, p. 190-193, Matemáticas y Aplicaciones de codificación de Datos/imagen, Compresión, y Encryption III, Mark S. Schmalz; Ed
30. Hacia la Compresión Fractal de Imagen en Tiempo Real Usando Hardware para Gráficos Dipartimento di Informatica e Applicazioni, Università degli Studi di Salerno
31. http://www.linuxjournal.com/article/4367
32. http://netpbm.sourceforge.net/doc/pnmtofiasco.html
33. http://netpbm.sourceforge.net/doc/fiascotopnm.html
34. . Archivado desde el original el 9 de marzo de 2012. Consultado el 21 de junio de 2011. 

Enlaces externos

• Compresor de Pulcini y Verrando
• Proyecto de codificación fractal Waterloo
• Keith Howell's 1993 M.Sc. dissertation
• My Main Squeeze: Fractal Compression, Nov 1993, Wired.
• Fractal Basics descripción en FileFormat.Info
• Superfractals website dedicada a los fractales por el inventor de la compresión fractal

•   Datos: Q2872