La compression fractale

 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 ω 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_ω=lim _n→∞ ω ⁿ(A₀)

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

d_H(A₀,l_ω) ≤ (1-s)^-1d_H(A₀,A₁) (1)

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

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_ω qui approche A₀ de manière satisfaisante.

Si I est l’image que nous voulons compresser, minimiser d_H(I, ω(I)) devient notre préoccupation première. Nous chercherons donc une application contractante ω 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 ω_i : A_i → B_i où A_i et B_i sont des sous ensembles de l’image et (B_i)_i=1,…,n une partition de celle-ci :

ω(I)=∪ω_i(I∩A_i)

 L’algorithme...

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

1. Créer une partition (B_i)_i=1,…,n de I
2. Pour chaque B_i, trouver une partie A_i de I et une application linéaire contractante ω_i : A_i → B_i telle que d_H(ω_i(A_i),B_i) soit minimal
3. 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 ω_i : A_i → B_i linéaire et surjective, la seule donnée de A_i détermine entièrement ω_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(ω_i(A_i),B_i) et on retiendra le couple (ω_i,A_i) qui la minimise.

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

1. Choisir une image A quelconque
2. Calculer par itération les termes de la suite u_j=ω^οj(A)
3. Stopper le processus lorsque d_H(u_j,u_j+1) est assez petit pour que l’on puisse raisonnablement dire qu’on a atteint la limite l_ω

Nous savons alors que l’attracteur l_ω 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 :

1. On se donne un carré B_i
2. 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)
3. 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-12 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=4k 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 ω_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)=a⋅x+b. La détermination des coefficients a et b optimums pour une composante ω_i se fait en annulant les dérivées partielles de d2(A_i,ω_i(A_i)) par rapport à a et b. On veillera bien entendu à conserver |a|<1 de manière à ce que ω_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 d2 à 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.

• Yuval Fisher. Fractal Image Compression, theory and application. Springer, 1996. ISBN 0-387-94211-4 (New York) et ISBN 3-540-94211-4 (Berlin)