La compression Fractale.

Rapport de TIPE informatique de l'année scolaire 1997-98 sur le thème Images et géométrie. Travail réalisé par trois élèves de Math spé du Lycée Pothier d'Orléans (45) :

• Benjamin Gandon
• Vincent Larchet
• Sylvain Trimoreau

Introduction.

L'intérêt de la compression d'images n'est plus à démontrer. La limitation de la bande passante, ne serait-ce que sur Internet, nous le rappelle tous les jours. La compression fractale est une voie actuelle de recherche pour améliorer les performances. Nous l'avons mise en oeuvre et nos résultats mettent en lumière aussi bien son efficacité que ses désavantages.

L'idée de départ :

M. Barnsley fut le premier à avoir l'idée, de tirer parti du déséquilibre de complexité entre les attracteurs fractals obtenus par itération d'une fonction contractante (les IFS : Iterated Function Systems) et la méthode permettant de les calculer. En effet, les images de ces attracteurs s'obtiennent à l'aide de quelques coefficients très simple. L'idée consiste donc à changer de représentation de l'image : au lieu de la représenter à l'aide de pixels, on le fait à l'aide des coefficients qui permettent son calcul. Ces deux représentations sont équivalentes d'un point de vue du rendu visuel, mais l'une d'elles est infiniment plus concise que l'autre.

Le plus difficile est alors de s'attaquer au problème inverse : étant donné une image, comment trouver une application dont l'attracteur sera le plus proche possible de l'image à compresser ?

Une voie de recherche :

L'existence et l'unicité de l'attracteur associé à une fonction contractante est bien sûr justifiée à l'aide du théorème du point fixe. Or il s'avère que la démonstration de ce dernier nous apporte une majoration permettant de résoudre notre problème.

Nous nous intéressons ici à des images en noir et blanc. Pour les décrire mathématiquement, celles-ci seront vues comme des compacts de R².

Soit I le compact représentant l'image à compresser. Un point du plan est noir s'il appartient à I , et blanc s'il est en dehors de cet ensemble.

Par ailleurs, il nous faut être capable de quantifier la différence entre deux images. Nous choisissons donc la distance de Hausdorff, notée d_H, qui s'applique à H l'ensemble des compacts de R² et en fait un métrique complet. Pour deux éléments A et B de H, celle-ci a pour formule

d_H(A,B)=sup(E(A,B),E(B,A))

où E(A,B) est l'écart de A à B défini à partir de la distance euclidienne par

E(A,B)=sup{d₂(a,B) / aÎA}

Dès lors, si l'on se donne une application w contractante de H dans H, et A₀ un élément de H, le théorème du point fixe nous permet d'affirmer que la limite

l_w=lim _{n -> ¥} w ⁿ(A₀)

ne dépends que de w : c'est l'attracteur de w. Nous obtenons également la majoration

d_H(A₀,l_w) £ (1-s)^-1d_H(A₀,A₁) (1)

où A₁=w(A₀) et s<1 est le module de contraction de w.

Par conséquent, si l'on s'assure que 1-s est non nul et que d_H(A₀,A₁) est aussi petit que possible, nous obtiendrons un attracteur l_w qui approche A₀ de manière satisfaisante.

Si I est l'image que nous voulons compresser, minimiser d_H(I, w(I)) deviendra donc notre principal souci. Nous chercherons donc une application contractante w qui laisse au mieux l'image I invariante, selon la distance choisie, ici d_H.

Puisqu'il n'est pas raisonnable de rechercher une application contractante quelconque de R² dans R², nous nous limiterons à une catégorie d'entre elles.

Ici, nous avons choisi les applications utilisées dans les PIFS. Celles-ci qui sont l'union finie de composantes linéaires w_i : A_i -> B_i où A_i et B_i sont des sous ensembles de l'image et (B_i) une partition de celle-ci :

w(I)=Uw_i(IïA_i)

L'algorithme... :

L'algorithme de compression se présentera donc ainsi :

• Créer une partition (B_i) de I
• Pour chaque B_i, trouver une partie A_i de I et une application linéaire contractante w_i : A_i -> B_i telle que d_H(w_i(A_i),B_i) soit minimal
• Si cette distance n'est pas satisfaisante, affiner la partition et entreprendre une nouvelle recherche

On voit tout de suite que l'essentiel se situe dans la seconde étape. Il est bon de remarquer dès maintenant que puisque nous cherchons w_i : A_{i ->} B_i linéaire et surjective, la seule donnée de A_i détermine entièrement w_i. Il nous faudra essayer successivement un grand nombre d'ensembles de départ A_i tels qu'on puisse transformer A_i en B_i par une application linéaire. A chaque fois, il faudra évaluer la distance d_H(w_i(A_i),B_i) et on retiendra le couple (w_i,A_i) qui la minimise.

Par ailleurs, la décompression est fort aisée à réaliser :

• Choisir une image A quelconque
• Calculer par itération les termes de la suite u_n=w ⁿ(A)
• Stopper le processus lorsque d_H(u_n,u_n+1) est assez petit pour que l'on puisse raisonnablement dire qu'on a atteint la limite l_w

Nous savons alors que l'attracteur l_w obtenu sera proche de l'image I que nous voulions compresser grâce à la majoration (1)

...Et son adaptation à nos machines :

Ici interviennent quelques restriction pour adapter cette méthode à nos ordinateurs.

• Les images seront carrées avec 2^k pixels de coté
• La partition sera une division en quadtree
• Les applications linéaires transformeront un carré en un carré de côté deux fois moindre

Ici, nous transformons un carré A en un autre de coté deux fois moindre B, donc il n'existe que huit transformations possibles obtenues par rotation, par symétrie ou par composée des deux.

Dès lors, l'algorithme de recherche de l'application se présente ainsi :

• On se donne un carré B_i
• Pour tous les carrés A_i de côté double, et pour chacune des huit orientations, calculer le transformé A'_i de A_i et calculer d_H(A'_i,B_i)
• Stocker B_i et l'orientation choisie qui minimisent cette distance

On voit donc qu'il n'est nullement besoin de se préoccuper de fonctions : Il suffit d'effectuer des comparaisons de morceaux d'images.

Les images en niveaux de gris :

Pour cette présentation de l'algorithme, nous avons considéré des images noir et blanc représentées par de compacts du plan.

Dans le cadre d'images en niveaux de gris, une image est représentée par une application de {0,..,2^k-1}² dans {0,255}, et le métrique devient L₂, car cette distance est à la fois simple à manipuler et proche de l'appréciation visuelle de l'homme.

Puisque dans nos ordinateurs, les images sont discrètes, la distance s'apparentera à la distance euclidienne d₂ de R^(4k). Si N=4^k et A=(a_i)_i=1..N , B=(b_i)_i=1..N sont deux images, on aura

d₂(A,B)={(a₁-b₁)²+...+(a_N-b_N)²}^1/2

Le principe est alors le même, à ceci près que les applications w_i sont linéaires en coordonnées spatiales et sur la composante de gris. Celles-ci intégreront donc réglage de contraste et de luminosité, qui correspond à une fonction affine f : R -> R décrite par f(x)=ax+b. La détermination des coefficients a et b optimums pour une composante w_i se fait en annulant les dérivées partielles de d₂(A_i,w_i(A_i)) par rapport à a et b. On veillera bien entendu à conserver |a|<1 de manière à ce que w_i soit bien contractante.

Les images couleurs :

Pour manipuler une image couleur, il est possible de la décomposer en trois composantes que l'on traite chacune comme une image en niveaux de gris. La décomposition en niveaux de rouge, de vert et de bleu est la première qui vient à l'esprit, mais c'est aussi la moins efficace.

Puisque l'homme conçoit plutôt les couleurs à travers leur luminosité, leur teinte, et leur saturation, on utilise cette décomposition.

L'avantage de celle-ci réside dans le fait que parmi ces trois composantes, la première est bien plus importante au rendu visuel. On pourra donc fortement compresser les deux autres sans beaucoup perdre en qualité.

Nos expérimentations et nos résultats :

Nous avons implémenté la méthode par quadtree pour des images couleurs. Notre petite touche finale a été la création d'un format d'images à part entière pour stocker nos images sans laisser un seul bit inutilisé !

Dès lors, nous avons été à même de rivaliser avec les standards de compression d'image, tels que le format JPEG. Notre compression est d'ailleurs meilleure que ce dernier si l'on quantifie toutefois la qualité d'une image à l'aide de la distance d₂ à travers le PSNR (Peak Signal Noise Ratio) défini par

PSNR=20*log(255/d₂(A,B))

où A et B sont l'image d'origine et l'image compressée.

Cependant, même si le calcul du couple (PSNR,taux de compression) est à l'avantage de notre compression, on ne peut pas affirmer avoir surpassé le format JPEG, car il n'existe pas de moyen de calculer réellement les pertes visuellement ressenties par l'oeil humain. Ainsi, un test psycho-sensoriel serait au désavantage de notre méthode.

De plus, si la décompression est assez rapide, les temps de calculs sont incroyablement élevés lors de la compression. La complexité de la recherche est explosive : certaines images relativement grandes (128 par 128) ont nécessité plusieurs jours de calcul. Il faut savoir qu'un compresseur commercial au format FIF donne lieu à de meilleurs résultats en quelques dizaines de secondes !

Conclusion :

Notre implémentation de cette technique de compression a atteint ses objectifs en termes de compression et de qualité. Nous sommes en effet très contents d'avoir pu rivaliser avec le standard JPEG.

Pour finir, il serait bon de mentionner l'existence de méthodes permettant d'accélérer le processus de compression sans trop perdre en efficacité. Il s'agit en général de choisir convenablement un ensemble restreint de A_i susceptibles de donner de meilleurs résultats.

Bibliographie :

Elle est assez restreinte puisque ce livre explore en profondeur notre propos. De plus, de tels livres ne sont pas légion. Fractal Image Compression, theory and application. de Yuval Fisher (Springer, 1996)

Auteur : Benjamin Gandon (Stabylo/the Removers)

Texte destiné à la diffusion sur le site WEB des Removers (http://removers.atari.org/)

Sommaire du magazine

[Entrée du site] [Presentation du groupe] [Nos articles] [Nos logiciels] [Téléchargement] [Nos liens] [Contacts] [Nouveautés du site]

[Main page] [Presentation of the group] [Our products] [Download] [Links] [Contacts] [What's new]