M. Barnsley a proposé une méthode de génération
d'images basée sur les IFS (Iteretated Function System), et qui
consiste a itérer plusieurs fois une transformation contractive
à une image de départ (cf [2]). En vertu du théorème
du point fixe, il y a convergence vers une image indépendante de
l'image de départ. Il utilise pour ce faire un ensemble de
transformations affines :
.
Si s est le coefficient de contraction, d la métrique utilisée, le théorème de collage affirme même que
si
alors
où
désigne l'attracteur (point fixe) de
.
Pour approximer une image par ce moyen, il faut donc trouver l'ensemble de transformations affines par lequel l'image est "presque invariante". Cette méthode, manuelle, a permi d'obtenir des images saisissantes, en particulier la célèbre fougère de Barnsley qui est obtenue avec seulement 4 transformations.
Il proposa donc d'utiliser cette méthode pour compacter des images, mais elle nécessitait l'assistance d'un opérateur humain (d'où son nom d'algorithme du graduate student, elle consistait en effet à enfermer un étudiant avec une image et une station de travail puissante afin qu'il trouve les transformations), prenait beaucoup de temps de calcul, et il fallait également énormément de temps pour décompacter les images obtenues (de l'ordre de plusieurs heures sur des ordinateurs musclés !).
C'est anecdotiquement un des étudiants de Barnsley, Jaquin, qui proposa une solution sous la forme de PIFS (Partitionned Iterated Function System), c'est à dire que les transformations affines considérées sont restreintes à des portions du plan, et il implémenta un algorithme de compression fractale qui consistait, schématiquement, à partitionner l'image en blocs de 8*8 pixels, et de trouver, pour chaque bloc, un carré de 16*16 pixels qui lui soit similaire (en autorisant les isométries du carré et une transformation affine sur les niveaux de gris). Cette méthode a l'immense mérite d'être entièrement automatique et de présenter des temps de décompactage très raisonnables. En revanche, le temps de compression est très élevé, et la plupart des recherches actuelles visent à le réduire.
Nous nous devons de consacrer ici un paragraphe au ``benchmark'' officiel de la compression d'image, la célèbre Lenna (Lena en suédois). Il s'agit de la page centrale du numéro de novembre 1972 de Playboy. Lena Sderberg (née Sjooblom) est mariée et mère de trois garçons et a été fort surprise de sa célébrité informatique, et Playboy finirait quant à lui par se plaindre de cette violation répétée de ses copyrights.