Compresión fractal

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

Compresión fractal es un método de compresión con pérdidas para 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. 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

La representación de imágenes fractales se puede describir matemáticamente como un sistema de funciones iteradas (IFS).

Para imágenes binarias

Comenzamos con la representación de una imagen binaria, donde la imagen puede ser considerada como un subconjunto de ${displaystyle mathbb {R} {2}}$. Un IFS es un conjunto de mapas de contracción .₁,...._N,

${displaystyle "Mathbb" {R} {2}to mathbb {R} ^{2}$

Según 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 Asubset mathbb {R} ^{2}$

Es decir, H es un operador que asigna conjuntos a conjuntos, y S es el único conjunto que satisface H(S< /i>) = S. La idea es construir el IFS de manera que este conjunto S sea la imagen binaria de entrada. El conjunto S se puede recuperar del IFS mediante una iteración de 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 autosimilar 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)}$

Entonces vemos que el IFS es una representación fractal de S.

Extensión a escala de grises

La representación de IFS se puede extender a una imagen a escala gris considerando el gráfico de la imagen como subconjunto de ${displaystyle mathbb {R} {} {}}}$. Para una imagen a escala gris u()x,Sí.), considerar el conjunto S *x,Sí.,u()x,Sí.)}. Entonces similar al caso binario, S es descrito por un IFS usando un conjunto de mapas de contracción .₁,...._N, pero dentro ${displaystyle mathbb {R} {} {}}}$,

${displaystyle "Mathbb" {R} ^{3}to mathbb {R} ^{3}$

Codificación

Un problema desafiante de la investigación en curso en la representación de imágenes fractales es cómo elegir el ƒ₁,...,ƒ_N tal que su punto fijo se aproxima a la imagen de entrada, y cómo hacerlo de manera eficiente.

Un enfoque simple para hacerlo es el siguiente sistema de funciones iteradas particionadas (PIFS):

1. Partición del dominio de la imagen en bloques de rango R_i de tamaño s×s.
2. Para cada uno R_i, buscar la imagen para encontrar un bloque D_i de tamaño 2s× 2s que es muy similar a R_i.
3. Seleccione las funciones de mapeo tales que H()D_i) R_i para cada uno 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 un número suficiente de bloques candidatos para D_i necesita ser considerado. Por otro lado, una búsqueda grande considerando muchos bloques es computacionalmente costosa. Este cuello de botella de buscar 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 wavelet.

El algoritmo de búsqueda de fuerza bruta y partición cuadrada inicial 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 coincidente lo suficientemente cercano para cada bloque de rango en lugar de una búsqueda de 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.

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 incluyen compensación de movimiento y sistemas de funciones iteradas tridimensionales.

La compresión de imágenes fractales tiene muchas similitudes con la compresión de imágenes de cuantización vectorial.

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 autosimilitudes. La decodificación, sin embargo, es bastante rápida. Si bien esta asimetría hasta ahora lo ha hecho poco práctico para las 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.

Con relaciones de compresión comunes, hasta aproximadamente 50:1, la compresión fractal brinda resultados similares a los algoritmos basados en DCT, como JPEG. Con relaciones de compresión altas, la compresión fractal puede ofrecer una calidad superior. Para imágenes satelitales, se han logrado proporciones de más de 170:1 con resultados aceptables. Se han logrado relaciones de compresión de video fractal de 25:1 a 244:1 en tiempos de compresión razonables (2,4 a 66 segundos/fotograma).

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

Independencia de 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 después de convertirse a código fractal. Esto se debe a que los sistemas de funciones iteradas en el archivo comprimido escalan indefinidamente. Esta propiedad de escalado indefinido de un fractal se conoce como "escalado fractal".

Interpolación fractal

La independencia de resolución de una imagen con codificación 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 a través de la compresión fractal y, posteriormente, se descomprime a una resolución más alta. El resultado es una imagen muestreada en la que se han utilizado sistemas de funciones iteradas como interpolante. 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. 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. Uno no puede, por ejemplo, agrandar una imagen de una multitud donde la cara de cada persona es uno o dos píxeles y esperar identificarlos.

Historia

Michael Barnsley lideró el desarrollo de la compresión fractal en 1987 y obtuvo varias patentes sobre la tecnología. 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. 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. 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 ocurría en los primeros experimentos 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 estadounidenses para desarrollar un prototipo de chip de descompresión y almacenamiento de imágenes digitales utilizando tecnología de compresión de imágenes de transformación fractal.

La compresión de imágenes fractales se ha utilizado en varias aplicaciones comerciales: onOne Software, desarrollado bajo licencia de Iterated Systems Inc., Genuine Fractals 5, que es un complemento de Photoshop capaz de guardar archivos en formato FIF (formato de imagen fractal) comprimido. Hasta la fecha, el uso más exitoso de la compresión de imágenes fijas fractales es el de Microsoft en su enciclopedia multimedia Encarta, también bajo licencia.

Iterated Systems Inc. suministró un codificador shareware (Fractal Imager), un decodificador independiente, un decodificador de complemento de Netscape y un paquete de desarrollo para usar bajo Windows. A medida que los métodos de compresión de imágenes basados en ondículas mejoraron y los proveedores de software comercial obtuvieron licencias más fácilmente, la adopción del formato de imagen Fractal no evolucionó. La redistribución de la "DLL del descompresor" proporcionado por ColorBox III SDK se rige por regímenes de licencia restrictivos por disco o año por año para proveedores de software propietario y por un esquema discrecional que implica la promoción de los productos de Iterated Systems para ciertas clases de otros usuarios.

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 fueron 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 seleccionados. Se requerían 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 de Iterated distribuido libremente para navegadores web. En 1994, SoftVideo obtuvo la licencia de Spectrum Holobyte para su uso en sus juegos de CD-ROM, incluidos Falcon Gold y Star Trek: The Next Generation A Final Unity.

En 1996, Iterated Systems Inc. anunció una alianza con Mitsubishi Corporation para comercializar ClearVideo entre sus clientes japoneses. Microsoft aún admite el controlador del decodificador ClearVideo 1.2 original 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 se han analizado considerablemente. En resumen, es un sistema simple de copia de bloques quadtree 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 abandonaría por completo la tecnología basada en fractales.

Los trabajos de investigación entre 1997 y 2007 discutieron posibles soluciones para mejorar los algoritmos fractales y el hardware de codificación.

Implementaciones

Ullrich Hafner creó una biblioteca llamada Fiasco. En 2001, Fiasco se cubrió en el Linux Journal. De acuerdo con el manual de Fiasco 2000-04, Fiasco se puede utilizar para la compresión de vídeo. La biblioteca Netpbm incluye la biblioteca Fiasco.

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