Les courbes

Introduction par un exemple simple:


- Soit le niveau 0 de la courbe, constitué d'un segment de droite.
- On dessine un triangle équilatéral dont le côté à une longueur (La longueur d’un objet représente la distance entre deux de ses extrémités, les plus éloignées possibles. Lorsque...) égale au tiers du segment initial.De plus ce triangle pointe vers le haut.
- On applique ce même procédé à chacun des segments de droite ainsi constitués (remarquons que la transformation est appliquable à l'infini).

Les images

Une image fractale (On nomme fractale ou fractal (nom masculin moins usité), une courbe ou surface de forme irrégulière ou morcelée qui se...) est caractérisée par le type de transformation qu'elle a subit, l'algoritme consiste principalement a coder celle-ci comme une suite de transformations. En effet, les données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose,...) d'une image contiennent généralement un ensemble (En théorie des ensembles, un ensemble, désigne intuitivement une collection d’objets (que l'on appelle éléments...) plus ou moins grand d'éléments redondants (partie similaire sur l'image ou auto-similarités). Etant inutile de stocker ces éléments autant de fois qu'ils sont présents, la taille de l'image décroît. Pour obtenir une compression intéressante, on influe sur l'image avec la façon dont travaille la vision humaine. En effet, notre oeil est insensible à certaines pertes d'informations (le cerveau assurant, par comparaison, la correction de l'erreur générée). Ainsi, on peut modifier l'image, raisonnablement, de manière à augmenter le nombre (Un nombre est un concept caractérisant une unité, une collection d'unités ou une fraction d'unité.) de suites redondantes. Tout ça en faisant en sorte que l'image transformée converge vers l'image initiale, qui est alors l'attracteur (Dans l'étude des systèmes dynamiques, un attracteur (ou ensemble-limite) est un ensemble, une courbe ou un espace vers...) de la transformation. Une même transformation peut donc être appliquée à des images différentes, l'attracteur étant, quand à lui différent.

Exemple de types de transformation:

La compression fractale

La compression d'une image fractale consiste à mettre en relation un modèle mathématique (Un modèle mathématique est une traduction de la réalité pour pouvoir lui appliquer les outils, les techniques et les...) avec celle-ci afin de lui appliquer un transformation contractante. Il faudra ensuite définir les auto-similarités, afin de ne les sauvegarder qu'une seule fois. Cette recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de...) correspond à une transformation afine qui se résume à une aproximation de l'image d'origine, incluant donc un taux d'erreur de l'image finale variant selon la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en...) de la transformation; c'est ce qui donne le taux de compression. Prenons le cas de l'exemple 1B, l'attracteur (image d'origine, qui est la lettre A ) de cette transformation subit la variation d'échelle. Le produit de ces transformations multiples offre une caractéristique intéressante, car les détails supplémentaires apportés à l'image transformée sont générés "automatiquement" par la méthode employée, détails qui dans certains cas sont très réalistes pour de faibles agrandissements. Cette méthode, implique un taux d'erreur +/- variable à la représentation finale de l'image d'origine, ce qui est normal puisqu'il s'agit d'une approximation mathématique.

Imaginons une photocopieuse dont le but est de recopier l'entrée trois fois en divisant par deux son échelle comme illustré sur a figure ci-dessous:


A chaque cycle de la copie, le document qui vient de sortir est remis en entrée de la photocopieuse de ce fait, après de nombreuses copies comportant les mêmes transformations (ici division par 2 de l'échelle puis recopie de la source 3 fois), la sortie convergera vers ce que l'on appelle un attracteur, c'est à dire une image qui lorqu'on la remet en entrée de cette photocopieuse donne en sortie la même image. La transformation utilisée en exemple est l'une des très nombreuses transformations possibles. Et on peut immédiatement comprendre que d'autres transformations conduiraient à d'autres attracteurs.

Indépendance de l'attracteur vis-à-vis de l'image d'origine:

Mais considérons maintenant deux images totalement différentes, et appliquons à chacune d'elles simultanément les mêmes transformations. Comme le montre la figure ci-dessous, les deux images (a et b) qui au départ étaient dissemblables donnent lieu au même attracteur (c).



En fait, plus on réalise de copies, plus l'image d'origine disparait pour ne devenir qu'un point. Mais ce point existe en plusieurs copies agencées d'une certaine manière que définit la transformation utilisée. Ainsi, un attracteur ne dépend que de la transformation utilisée. En pratique, ces transformations sont des applications affines, c'est à dire des transformations du plan dans le plan telles que chacune de ces transformations effectue au moins une des opérations suivantes:
- Etirement
- Rotation
- Translation

En pratique, l'ensemble de ces transformations est suffisant pour pouvoir donner lieu à un ensemble riche d'attracteurs.

La compression fractale consiste non pas à enregistrer les informations propres de l'image, mais plutôt les transformations nécessaires à la constitution de l'image en tant qu'attracteur. Connaissant cette suite de transformations, l'image pourra être reconstituée en partant de n'importe quelle image source (par exemple une image entièrement noire) car celle-ci devenant un point parmi d'autres.

Voyons à présent la taille nécessaire au codage d'une transformation (on verra plus tard que cela n'est pas suffisant pour coder une image quelconque complètement).
Comme il a été vu précédemment, chaque transformation est définie à partir de 6 réels qui sont codables sur 32 bits. Il suffit donc de 192 bits pour stocker une transformation.
Pour compresser l'image de la fougère ci-dessous (figure 4), comme il ne faut que 4 transformations (on ne prend pas encore en compte les transformations liées aux niveaux de gris), il suffira de 4 x 192 bits = 768 bits (96 octets) pour stocker l'image alors qu'il faut environ 12kbits pour stocker l'image avec la résolution actuelle.

Processus de compression

L'idée de base de ce procédé de compression d'images est de trouver l'attracteur de l'image à compresser, au sens mathématique du terme si l'on modélise une image comme une application de {1,...,N}*{1,...,N} vers {0,...2p-1} ou N est le côté de cette image en nombre de pixels et p est le nombre de bits que l'on utilise pour coder cette image (pour p bits, on obtient un nombre de couleurs différentes utilisables de 2 exposant (Exposant peut signifier:) p).

C'est parce qu'une manière de définir une fractale en mathématiques est de décrire une fractale comme l'unique point fixe d'un attracteur. Nous allons donc tenter d'expliquer comment fonctionne ce type de compression, mais dans les grandes lignes.

Tout comme pour la compression Jpeg, l'algorithme découpe l'image en blocs-parents carrés de 16 pixels de côtés, eux-mêmes subdivisés en 4 blocs-fils carrés de 8 pixels de côté. Le travail principal de l'algorithme de compression est de calculer, pour chacun de ces blocs-parent et de ces blocs-fils, l'attracteur qui lui est associé. On ne trouve généralement jamais exactement l'attracteur exact associé à un bloc mais le travail consiste à en trouver un le plus fidèle possible. Chaque attracteur spécifique à un seul bloc décrit ce bloc de la manière suivante.

Considérons un bloc et son attracteur associé: si, par la suite, l'on prend n'importe quel autre bloc de la même taille mais dont le rendu n'a rien a voir avec ce dernier, et que l'on fait l'image de ce bloc par l'attracteur considéré, on se rapproche chaque fois plus du premier bloc. C'est la propriété de contractance de l'attracteur, via un théorème appelé théorème du "collage" qui garantisent cette convergence (Le terme de convergence est utilisé dans de nombreux domaines :).

De cette manière, il semble exister une bijection entre tout bloc et son attracteur associé. Et comme l'espace physique (La physique (du grec φυσικη) est étymologiquement la science de la nature. Son champ...) que prend l'attracteur, par rapport à celui que prend le bloc, est bien inférieure le gain en espace physique de l'image qui n'est rien d'autre qu'un assemblage disjoint de ces blocs s'en trouve diminué; c'est le passage de la description d'un bloc par son attracteur qui constitue l'étape de compression de ce processus. En effet, cet attracteur peut-être décrit approximativement par deux paires de fonctions, une de réajustement, l'autre d'intensité qui sont codées sur peu d'espace physique.

Il s'agit d'une approximation car si l'on désirait calculer précisément l'attracteur de chaque bloc, il faudrait bien plus que deux paires de fonctions pour le décrire, mais plutôt 2n fonctions telles que n serait d'autant plus grand que la précision requise serait importante. Dans la pratique, il est possible de décrire chaque bloc assez précisément à l'aide d'un attracteur simple constitué de deux paires de fonctions. Pour déterminer les fonctions qui décrivent cet attracteur, on doit utiliser la méthode des moindres carrés qui, utilisée intensivement, est coûteuse en temps de calcul, ce qui ralentit le processus de compression.

Ce procédé de compression d'images est non conservatif puisque cette correspondance évoquée précédemment ne sera pas parfaite. Cela va donc introduire des infidélités entre l'image originale et l'information que détient l'image compressée.

Le fichier compressé contient donc les informations sur les attracteurs des blocs-parents (à savoir: la paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) de fonctions d'intensité, la paire de fonctions de réajustement étant fixée et stockée au début de l'en-tête), puis celles concernant les différents blocs. D'autres informations telles celles qui concernent la taille de l'image sont contenues dans l'en-tête.

Les avantages:
- La compression fractale permet un puissant zoom fractal pour agrandir une image sans effet de pixellisation.
- Son taux de compression est très avantageux, tout en conservant un aperçu fidèle.
- Un effet de lissage flou disponible en traitement d'images.

Les inconvénients:
- Ce type de compression n'a pas encore fait l'objet de l'édition d'une norme.
- La compression reste lente malgré toutes les améliorations.
- La compression produit un flou dans l'image.