Compresión fractal

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 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}.}$

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.

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}.}$

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.

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".

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]