[Compression d'images] : TIPE : Compression Fractale

INTRO : Si on considère une image fractale telle que le triangle de Sierpinski, on se rend compte qu'il existe deux manières de la coder : soit on enregistre tous les pixels qui la compose (mais jusqu'à quel niveau de détail, puisque la résolution de la fractale est infinie - c'est à dire on peut grossir l'image sanbs limite) ou alors se contenter d'encoder la transformation affine qui engendre l'image, comme le montre le schéma suivant :

On montrera par la suite qu'il suffit de connaitre une transformation affine contractante qui laisse l'image invariante pour retrouver l'image. Ojn se propose donc dans cet algorithme de trouver cette transformation, puis de la substituer à l'image à compresser.

Cette méthode utilise en fait les redondances et similarités de l'image pour compresser. En effet, comme on le voit ci-desous, la plupart des photos en possèdent :

Une image complexe peut être encodée à l'aide d'une application relativement simple. Il suffit de regarder l'exemple du triangle de Sierpinski pour s'en convaincre.

De plus, on a thèoriquement un niveau de détail infini une fois l'image décompressée. En réalité, compte tenu des approximations faits, il est illusoire penser retrouver en "zoomant" des détails qui n'étaient pas sur la photo originale. En revanche, on peut grossir sans qu'il y ait "pixelisation" (effet de mosaique sur l'mage). L'algorithme reitere la transformation affine pour obtenir plus de détails, au lieu de grossir la taille des pixels.

Il y a surtout un intêret théorique, puisque l'algorithme se détache nettement des deux précédents ( DCT, Ondelettes) vu qu'il ne s'agit plus d'un simple changement de base.

On peut la résumer ainsi :

W doit être choisie comme la composée des applications suivantes :

- similitudes ()
- affinités
- reflexions
- variation du contraste, de la luminosité

W s'écrit donc de la manière suivante :

x et y sont les coordonées du point considéré; z la valeur de l'intensité lumineuse en ce point. Pour que la transformation soit contractante, il faut . Il y a une autre condition sur le contraste (il doit être inférieur à 1). Pour les quatres premières cases, il s'agit du produit de matrices de rotation, de matrices d'affinités et de matrices de symétries, plus un décalage du à la translation. S représente le coefficient de contraste [on multiplie] et g la variation de luminosité [on décale].

Tout le problême se ramène alors à construire l'application W. Comme le problême dans son ensemble est très compliqué, on décompose le problême en sous problêmes, ce qui dans ce cas consiste à faire une partition de l'image à compresser, puis à traiter chaque élément de la partition séparément. La partition est établie de manière quelconque. Dans la pratique, le programme teste un grand nombre de partitions avent de trouver celle qui est idéale [d'où des temps de compression très longs]. Ici est représenté un exemple [méthode des QuadTrees, c'est-à-dire des carrés]

La partition de l'image est : A = U Ai.Pour chaque Ai, on trouve une partie Bi de l'image ainsi que la transformation Wi contractante telle que quel que soit i, l'image de Bi par Wi soit Ai. Pour trouver ces Bi, on procède en regardant tous les antécédants possibles de Ai. Il sera parfois nécessaire de faire des approximations. Si la recherceh échoue, il faut choisir une partition plus sérrée, mais la transformation W qui en résultera prendra plus de place. On pose alors W = U Wi.

W vérifie les propriétés souhaitées, puisque W(A) = A et W est contractante.

Voici la séqence de décompression d'une image (réalisée avec ce logiciel) :

Pour avoir des informations plus techniques :

http://kadchakib.ifrance.com

Je met également à votre disposition un logiciel, IFSearch pour tester la compression fractale :

Le logiciel

l'aide

Guillem PRATX - Mail : mon nom de famille @stanford.edu