Compresión fractal

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.

Contenido

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 \mathbb{R}^2. Un SFI es un conjunto de contracciones ƒ1,...,ƒN,

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

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 A0, la iteración Ak+1 = H(Ak) 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:

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 \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 ƒ1,...,ƒN, pero en \mathbb{R}^3,

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 ƒ1,...,ƒ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 Ri de tamaño s×s.
  2. Para cada Ri, buscar en la imagen para encontrar un bloque Di de tamaño 2s×2s que sea similar a Ri.
  3. Seleccionar las funciones de mapeo tal que H(Di) = Ri 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 numero suficiente de bloques candidatos para Di. Por otro lado, un 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 sólo 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 creo 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

Referencias

  1. ↑ Fischer, Y..«Fractal Image Compression», SIGGRAPH'92 course notes.
  2. ↑ Alternativas a la compresión de imagen y consideraciones sobre almacenamiento de medios 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. ↑ Walking, Talking Web 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. ↑ A Note on Expantion Technique for Self-Affine Fractal Objects Using Extended Fractal Interpolation Functions Hokkaido Univ., Graduate School of Engineering, JPN
  11. ↑ Studies on Scaling Factor for Fractal Image Coding 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 MediaBin Inc. Inc. en 2001 y fue comprada por Interwoven, Inc. en 2003)
  16. ↑ government grant
  17. ↑ Genuine Fractals Product Review
  18. ↑ Mathematics Awareness Week - April 1998 reference to Microsoft's Encarta fractal image compression
  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. ↑ http://castor.am.gdynia.pl/cgi-bin/man/man2html?3+fiasco_decoder_get_frame
  35. ↑ http://www.femtosoft.biz/fractals/fractal.html

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Compresión de imagen — El objetivo de la compresión de imagen es reducir los datos redundantes e irrelevantes de la imagen para permitir su almacenamiento o transmisión de forma eficiente. Una gráfica mostrando la calidad relativa de varias configuraciones de jpg.… …   Wikipedia Español

  • Fractal — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 16 de octubre de 2010. También puedes… …   Wikipedia Español

  • Algoritmo de compresión con pérdida — Se denomina algoritmo de compresión con pérdida a cualquier procedimiento de codificación que tenga como objetivo representar cierta cantidad de información utilizando una menor cantidad de la misma, siendo imposible una reconstrucción exacta de… …   Wikipedia Español

  • 0,9 periódico — En matemáticas, 0,999... es el número decimal periódico que se demuestra denota[1] al número 1. En otras palabras, los símbolos 0,999... y 1 son dos representaciones distintas del mismo número real. Las demostraciones matemáticas de esta igualdad …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”