Compressió fractal

2 triangles, exemple per mostrar com funciona la compressió fractal

La compressió fractal és un mètode de compressió amb pèrdues per a imatges digitals, basat en fractals. El mètode és més adequat per a textures i imatges naturals, basant-se en el fet que les parts d'una imatge sovint s'assemblen a altres parts de la mateixa imatge. Els algorismes fractals converteixen aquestes parts en dades matemàtiques anomenades "codis fractals" que s'utilitzen per recrear la imatge codificada.

Sistemes de funcions iterades

La representació d'imatges fractals es pot descriure matemàticament com un sistema de funcions iterades (IFS).

Per a imatges binàries

Comencem amb la representació d'una imatge binària, on la imatge es pot considerar com un subconjunt de $\mathbb {R} ^{2}$. Un IFS és un conjunt de mapes de contracció ƒ ₁ ,... , ƒ _N ,

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

Segons aquestes funcions de mapeig, l'IFS descriu un conjunt bidimensional S com el punt fix de l'operador Hutchinson

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

Extensió a escala de grisos

La representació IFS es pot estendre a una imatge en escala de grisos considerant el gràfic de la imatge com un subconjunt de $\mathbb {R} ^{3}$ . Per a una imatge en escala de grisos u (x, y ), considereu el conjunt S = {( x, y, u (x, y ))}. Aleshores, de manera similar al cas binari, un IFS descriu S utilitzant un conjunt de mapes de contracció ƒ ₁ ,... , ƒ _N, però en $\mathbb {R} ^{3}$ ,

Codificació

Un problema desafiant de la investigació en curs en la representació d'imatges fractals és com triar el ƒ ₁ ,... , ƒ _N tal que el seu punt fix s'aproximi a la imatge d'entrada i com fer-ho de manera eficient.

Un enfocament senzill per fer-ho és el següent sistema de funcions iterades particionades (PIFS):

1. Particioneu el domini de la imatge en blocs d'interval R _i de mida s × s.
2. Per a cada R_i, cerqueu la imatge per trobar un bloc D_i de mida 2 s × 2 s que sigui molt semblant a R_i.
3. Seleccioneu les funcions de mapeig de manera que H(D_i ) = R _i per a cada i.

En el segon pas, és important trobar un bloc similar perquè l'IFS representi amb precisió la imatge d'entrada, de manera que cal tenir en compte un nombre suficient de blocs candidats per a D_i. D'altra banda, una cerca gran tenint en compte molts blocs és costosa computacionalment. Aquest coll d'ampolla de cerca de blocs similars és per això que la codificació fractal PIFS és molt més lenta que, per exemple, la representació d'imatges basada en DCT i wavelet.

L'algoritme de cerca de força bruta i de partició quadrada inicial presentat per Jacquin proporciona un punt de partida per a més investigacions i extensions en moltes direccions possibles: diferents maneres de dividir la imatge en blocs de rang de diferents mides i formes; tècniques ràpides per trobar ràpidament un bloc de domini que coincideixi prou a prop per a cada bloc d'interval en lloc de cercar amb força bruta, com ara algorismes d'estimació de moviment ràpid; diferents maneres de codificar el mapeig des del bloc de domini fins al bloc de rang; etc.