Compresión fractal

2 triángulos, ejemplo para mostrar cómo funciona la compresión fractal

La compresión fractal es un método de compresión con pérdida de imágenes digitales , basado en fractales . El método es más adecuado para texturas e imágenes naturales, ya que se basa 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.

Sistemas de funciones iteradas

Artículo principal: sistema de funciones iteradas

La representación de imágenes fractales puede describirse matemáticamente como un sistema de funciones iteradas (IFS). ^[2]

Para imágenes binarias

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

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

De acuerdo con estas funciones de mapeo, el IFS describe un conjunto bidimensional 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}.}$

Es decir, H es una asignación de operador conjuntos a los conjuntos, y S es el conjunto único que satisface H ( S ) = S . La idea es construir el IFS de manera que este conjunto S sea ​​la imagen binaria de entrada. El conjunto S puede ser recuperado de los IFS por método del punto fijo : para cualquier no vacío compacto conjunto inicial A ₀ , la iteración A _{k +1}  = H ( A _k ) converge a S .

El conjunto S es auto-similar porque H ( S ) = S implica que S es una unión de copias mapeadas de sí mismo:

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

Así vemos el IFS es una representación del fractal de S .

Extensión a escala de grises

La representación IFS se puede ampliar a una imagen en escala de grises si se considera 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, similar al caso binario, S es descrito por un IFS usando un conjunto de mapeos de contracción ƒ ₁ , ..., ƒ _N , pero en ,${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$

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

Codificación

Un problema desafiante de la investigación en curso sobre la representación de imágenes fractales es cómo elegir ƒ ₁ , ..., ƒ _{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):

1. Divida el dominio de la imagen en bloques de rango R _i de tamaño s × s .
2. Para cada R _i , buscar la imagen para encontrar un bloque D _i de tamaño 2 s × 2 s que es muy similar a R _i .
3. Seleccione las funciones de mapeo tales que H ( D _i ) = R _i para cada i .

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 un número suficiente de bloques candidatos para D _i . Por otro lado, una búsqueda grande considerando 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 representación de imágenes basada en DCT y ondículas .

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 de coincidencia lo suficientemente cercano para cada bloque de rango en lugar de la búsqueda por fuerza bruta, como los algoritmos de estimación de movimiento rápido ; diferentes formas de codificar el mapeo 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 compresión de video fractal que incluyen compensación de movimiento y sistemas de funciones iteradas tridimensionales. ^{[4] [5]}

La compresión de imágenes fractal tiene muchas similitudes con la compresión de imágenes por cuantificación vectorial . ^[6]

Características

Con la compresión fractal, la codificación es extremadamente costosa desde el punto de vista computacional debido a la búsqueda utilizada para encontrar las auto-similitudes. La decodificación, sin embargo, es bastante rápida. Si bien esta asimetría hasta ahora ha hecho que no sea práctico 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] A altas relaciones de compresión, la compresión fractal puede ofrecer una calidad superior. Para las imágenes de satélite, 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 segundos / cuadro). ^[11]

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

Independencia de resolución y escala fractal

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 escalan indefinidamente. Esta propiedad de escala indefinida de un fractal se conoce como "escala fractal".

Interpolación fractal

La independencia de resolución de una imagen codificada fractal 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 de muestreo ascendente en la que se han utilizado sistemas de funciones iteradas como interpolante . ^[13] 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 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 afinando la imagen agregando detalles aleatorios en lugar de significativos. No se puede, por ejemplo, ampliar una imagen de una multitud en la que el rostro de cada persona tiene uno o dos píxeles y esperar identificarlos.

Historia

Michael Barnsley dirigió el desarrollo de la compresión fractal en 1987 y se le concedieron varias patentes sobre la tecnología. ^[17] El algoritmo práctico de compresión fractal más conocido fue inventado por Barnsley y Alan Sloan. El estudiante graduado de Barnsley, Arnaud Jacquin, implementó el primer algoritmo automático en software en 1992. ^{[18] [19]} 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. ^[20] en 1987, que recibió 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 fue el caso en la experimentación temprana con la tecnología de compresión fractal. En 1992, Iterated Systems Inc. recibió una subvención del gobierno de 2,1 millones de dólares ^[21] para desarrollar un prototipo de chip de descompresión y almacenamiento de imágenes digitales utilizando tecnología de compresión de imágenes por transformación fractal.

La compresión de imágenes fractal se ha utilizado en varias aplicaciones comerciales: onOne Software , desarrollado bajo licencia de Iterated Systems Inc., Genuine Fractals 5 ^[22], 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 aún fractales lo ha realizado Microsoft en su enciclopedia multimedia Encarta , ^[23] también bajo licencia.

Iterated Systems Inc. suministró un codificador shareware (Fractal Imager), un descodificador independiente, un descodificador de complemento de Netscape y un paquete de desarrollo para usar en Windows. A medida que los métodos de compresión de imágenes basados ​​en ondas mejoraron y los proveedores de software comerciales obtuvieron licencias con mayor facilidad, la adopción del formato de imagen fractal no pudo evolucionar. ^{[ cita requerida ]} La redistribución de la "DLL descompresora" proporcionada por el SDK de ColorBox III se regía por regímenes de licencias restrictivos por disco o año por año para los proveedores de software propietario y por un esquema discrecional que implicaba la promoción de los sistemas iterados productos para determinadas clases de otros usuarios. ^[24]

Durante la década de 1990, Iterated Systems Inc. y sus socios gastaron recursos considerables para llevar la compresión fractal al video. Si bien los resultados de la compresión eran prometedores, el hardware de la computadora de esa época carecía de la potencia de procesamiento para que la compresión de video fractal fuera práctica más allá de unos pocos usos selectos. Se requirieron hasta 15 horas para comprimir un solo minuto de video.

ClearVideo, también conocido como RealVideo (Fractal), y SoftVideo fueron los primeros productos de compresión de video fractal. ClearFusion fue el complemento de transmisión de video distribuido libremente de Iterated para navegadores web. En 1994, SoftVideo obtuvo la licencia de Spectrum Holobyte para su uso en sus juegos en CD-ROM , incluidos Falcon Gold y Star Trek: The Next Generation A Final Unity . ^[25]

En 1996, Iterated Systems Inc. anunció ^[26] una alianza con Mitsubishi Corporation para comercializar ClearVideo entre sus clientes japoneses. El controlador del decodificador ClearVideo 1.2 original todavía es compatible ^[27] por Microsoft en el Reproductor de Windows Media, 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 un producto funcional. La base tecnológica parece ser las patentes estadounidenses 8639053 y 8351509 de Dimension, que se han analizado considerablemente. ^[28] En resumen, es un simple sistema de copia de bloques de cuatro árboles 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 estaba abandonando por completo la tecnología basada en fractales.

Se han publicado numerosos artículos de investigación durante los últimos años en los que se discuten posibles soluciones para mejorar los algoritmos fractales y el hardware de codificación. ^{[29] [30] [31] [32] [33] [34] [35] [36] [37]}

Implementaciones

Ullrich Hafner creó una biblioteca llamada Fiasco . En 2001, Fiasco fue cubierto en Linux Journal .^[38] Según el manual Fiasco 2000-04 , Fiasco se puede utilizar para la compresión de vídeo.^[39] La biblioteca Netpbm incluye la biblioteca Fiasco .^{[40] [41]}

Femtosoft desarrolló una implementación de compresión de imágenes fractales en Object Pascal y Java .^[42]

Ver también

• Sistema de funciones iteradas
• Compresión de imagen
• Wavelet

Notas

1. Mayo, Mike (1996). "Compresión de imagen fractal". Científico estadounidense . 84 (5): 442–451. Código Bibliográfico : 1996AmSci..84..442M . JSTOR  29775747 . ProQuest 215266230 . 
2. Fischer, Yuval (12 de agosto de 1992). Przemyslaw Prusinkiewicz (ed.). Notas del curso SIGGRAPH'92 - Compresión de imágenes fractal (PDF) . SIGGRAPH . Fractales: del arte popular a la hiperrealidad. ACM SIGGRAPH .
3. Saupe, Dietmar; Hamzaoui, Raouf (noviembre de 1994). "Una revisión de la literatura sobre compresión de imágenes fractales". Gráficos por computadora ACM SIGGRAPH . 28 (4): 268-276. doi : 10.1145 / 193234.193246 . S2CID 10489445 . 
4. Lacroix, Bruno (1999). Compresión de imagen fractal (Tesis). doi : 10.22215 / etd / 1999-04159 . OCLC 1103597126 . ProQuest 304520711 .  
5. Fisher, Yuval (2012). Compresión de imágenes fractal: teoría y aplicación . Springer Science & Business Media. pag. 300. ISBN 978-1-4612-2472-3.
6. Henry Xiao. "Compresión fractal" . 2004.
7. John R. Jensen, "Libros de texto de percepción remota" , Alternativas de compresión de imágenes y consideraciones de almacenamiento de medios (referencia al tiempo de compresión / descompresión) , Universidad de Carolina del Sur , archivado desde el original el 3 de marzo de 2008
8. Steve Heath (23 de agosto de 1999). Tecnología multimedia y de comunicaciones . Prensa Focal. págs. 120-123. ISBN 978-0-240-51529-8. Enlace de prensa focal
9. Sayood, Khalid (2006). Introducción a la compresión de datos . Elsevier. págs. 560–569. ISBN 978-0-12-620862-7.
10. Wee Meng Woon; Anthony Tung Shuen Ho; Tao Yu; Siu Chung Tam; Siong Chai Tan; Lian Teck Yap (2000). "Lograr una alta compresión de datos de imágenes de satélite auto-similares utilizando fractal". IGARSS 2000. Simposio Internacional de Geociencias y Percepción Remota IEEE 2000. Tomando el pulso del planeta: el papel de la teledetección en la gestión del medio ambiente. Procedimientos (Cat. No.00CH37120) . 2 . págs. 609–611. doi : 10.1109 / IGARSS.2000.861646 . ISBN 0-7803-6359-0. S2CID  14516581 .
11. Fisher, Y. (julio de 1995). Codificación fractal de secuencias de video . Codificación y análisis de imágenes fractales. Trondheim. INIST : 1.572.685 .
12. Walking, Talking Web Archivado el 6 de enero de 2008 en el artículo de Wayback Machine Byte Magazine sobre la independencia de la resolución / compresión fractal
13. Él, Chuan-jiang; Li, Gao-ping; Shen, Xiao-na (mayo de 2007). "Método de decodificación por interpolación con parámetros variables para la compresión de imágenes fractales". Caos, solitones y fractales . 32 (4): 1429–1439. Código bibliográfico : 2007CSF .... 32.1429H . doi : 10.1016 / j.chaos.2005.11.058 .
14. Navascués, MA; Sebastián, MV (2006). "Interpolación fractal suave". Revista de Desigualdades y Aplicaciones . 2006 : 1–20. doi : 10.1155 / JIA / 2006/78734 . S2CID 20352406 . 
15. Uemura, Satoshi; Haseyama, Miki; Kitajima, Hideo (28 de enero de 2003). "EFIF を 用 い た 自己 ア フ ィ ン フ ラ ク タ ル 図 形 の 拡 大 処理 に 関 す る 考察" [Una nota sobre la técnica de expansión para objetos fractales autoafinados usando funciones de interpolación fractal extendidas]. Informe técnico del IEICE (en japonés). 102 (630): 95-100. doi : 10.11485 / itetr.27.9.0_95 . NAID 110003171506 . 
16. Kuroda, Hideo; Hu, Xiaotong; Fujimura, Makoto (1 de febrero de 2003). "フ ラ ク タ ル 画像 符号 化 に お け る ス ケ ー リ ン グ フ ァ ク タ に 関 す る 考察" [Estudios sobre el factor de escala para la codificación de imágenes fractales]. Transacciones del Instituto de Ingenieros en Electrónica, Información y Comunicación (en japonés). 86 (2): 359–363. NAID 110003170896 . 
17. Patente de EE  . UU . 4.941.193 : primerapatente de sistema de función iterada de Barnsley y Sloan, presentada en octubre de 1987
18. Uso de la codificación fractal para indexar el contenido de la imagen para un informe técnico de la biblioteca digital
19. Jacquin, AE (1992). "Codificación de imágenes basada en una teoría fractal de transformaciones de imágenes contractivas iteradas". Transacciones IEEE sobre procesamiento de imágenes . 1 (1): 18–30. Código Bibliográfico : 1992ITIP .... 1 ... 18J . CiteSeerX 10.1.1.456.1530 . doi : 10.1109 / 83.128028 . PMID 18296137 .  
20. Iterated Systems Inc. cambió su nombre a MediaBin Inc. Inc. en 2001 y, a su vez, fue comprada por Interwoven, Inc. en 2003)
21. NIST SP950-3, "Captura e integración de información sanitaria del paciente para mejorar la accesibilidad"; consulte la página 36, ​​"Tecnología basada en fractal de MediaBin para comprimir archivos de imágenes digitales" Archivado el 23 de septiembre de 2015 en Wayback Machine.
22. Revisión del producto Genuine Fractals
23. "MAW 1998: ensayo del tema" . www.mathaware.org . Archivado desde el original el 31 de agosto de 2016 . Consultado el 18 de abril de 2018 .
24. Aitken, William (mayo de 1994). "El gran apretón". Mundo de la computadora personal .
25. 1994 Manual especificando en la página 11 SoftVideo bajo licencia a Spectrum Holobyte
26. "Acuerdo de tintas de Mitsubishi Corporation con sistemas iterados" (Comunicado de prensa). Sistemas iterados. 29 de octubre de 1996. Archivado desde el original el 8 de julio de 2012.
27. "Reproductor de Windows Media para códecs compatibles con Windows XP" . 31 de octubre de 2003. Archivado desde el original el 28 de octubre de 2004.
28. "Abril de 2014 - estudio de diligencia debida de la tecnología de vídeo fractal" . paulschlessinger.wordpress.com . Consultado el 18 de abril de 2018 .
29. Kominek, John (1 de junio de 1997). "Avances en compresión fractal para aplicaciones multimedia". Sistemas multimedia . 5 (4): 255–270. CiteSeerX 10.1.1.47.3709 . doi : 10.1007 / s005300050059 . S2CID 6016583 .  
30. Harada, Masaki; Kimoto, Tadahiko; Fujii, Toshiaki; Tanimoto, Masayuki (2000). "Cálculo rápido de parámetros IFS para codificación de imágenes fractales". En Ngan, King N; Sikora, Thomas; Sun, Ming-Ting (eds.). Comunicaciones visuales y procesamiento de imágenes 2000 . 4067 . pag. 457–464. Código Bibliográfico : 2000SPIE.4067..457H . doi : 10.1117 / 12.386580 . S2CID 30148845 . INIST : 1.380.599 . 
31. Rajkumar, Wathap Sapankumar; Kulkarni, MV; Dhore, ML; Malí, SN (2006). "Síntesis de rendimiento de compresión de imagen fractal a través de particiones HV". 2006 Conferencia Internacional sobre Computación y Comunicaciones Avanzadas . págs. 636–637. doi : 10.1109 / ADCOM.2006.4289976 . ISBN 978-1-4244-0715-6. S2CID  15370862 .
32. Circuitos, señales y sistemas de compresión de imágenes fractal simples y rápidos - 2003
33. Wu, Ming-Sheng; Jeng, Jyh-Horng; Hsieh, Jer-Guang (junio de 2007). "Esquema de algoritmo genético para la compresión de imágenes fractales". Aplicaciones de ingeniería de la inteligencia artificial . 20 (4): 531–538. doi : 10.1016 / j.engappai.2006.08.005 .
34. Wu, Xianwei; Jackson, David Jeff; Chen, Hui-Chuan (septiembre de 2005). "Un método de codificación de imágenes fractal rápido basado en la búsqueda inteligente de desviación estándar". Computación e Ingeniería Eléctrica . 31 (6): 402–421. doi : 10.1016 / j.compeleceng.2005.02.003 .
35. Wu, Xianwei; Jackson, David Jeff; Chen, Hui-Chuan (2005). "Nuevo algoritmo de codificación de imágenes fractales basado en un sistema de función iterada sin búsqueda de árbol binario completo". Ingeniería óptica . 44 (10): 107002. Código Bibliográfico : 2005OptEn..44j7002W . doi : 10.1117 / 1.2076828 .
36. Truong, Trieu-Kien; Jeng, Jyh H. (2000). "Método de clasificación rápido para la compresión de imágenes fractales". En Schmalz, Mark S (ed.). Matemáticas y aplicaciones de codificación, compresión y encriptación de datos / imágenes III . Matemáticas y aplicaciones de codificación de datos / imágenes . 4122 . págs. 190-193. Código Bibliográfico : 2000SPIE.4122..190T . doi : 10.1117 / 12.409247 . S2CID 120032052 . 
37. Erra, Ugo (2005). "Hacia la compresión de imágenes fractal en tiempo real mediante hardware de gráficos". Avances en Computación Visual . Apuntes de conferencias en Ciencias de la Computación. 3804 . págs. 723–728. doi : 10.1007 / 11595755_92 . ISBN 978-3-540-30750-1.
38. Hafner, Ullrich (2001). "FIASCO - una imagen fractal de código abierto y un códec de secuencia" . Revista de Linux (81) . Consultado el 19 de febrero de 2013 .
39. "Manpage of fiasco" . castor.am.gdynia.pl . Archivado desde el original el 9 de marzo de 2012 . Consultado el 18 de abril de 2018 .
40. "Manual de usuario de Pnmtofiasco" . netpbm.sourceforge.net . Consultado el 18 de abril de 2018 .
41. "Manual de usuario de Fiascotopnm" . netpbm.sourceforge.net . Consultado el 18 de abril de 2018 .
42. "Copia archivada" . Archivado desde el original el 23 de octubre de 2010 . Consultado el 10 de julio de 2010 .

enlaces externos

• Compresor de Pulcini y Verrando
• El M.Sc. de 1993 de Keith Howell disertación Compresión de imágenes fractal para transputadoras espaciales
• My Main Squeeze: Fractal Compression , noviembre de 1993, cableado.
• Descripción de Fractal Basics en FileFormat.Info
• Sitio web de superfractals dedicado a los fractales por el inventor de la compresión fractal