En d’autres termes, $ N> 0 tel que d(x_n, x_m)<e , " n>N.

III.1.3.4  L’espace metrique h(x) [bar 93]

C’est l’espace où l’on étudie la géométrie des fractals ; on travaille généralement dans quelques espaces métriques complets, (IR²,d). Mais pour traiter des images, des dessins ou des sous-ensembles noir et blanc de l’espace, il est nécessaire d’introduire l’espace H.

Définition 1 :Soit (X,d) un espace métrique complet. H(X) décrit l’espace dont les points sont les sous-ensembles compacts de X autres que l’ensemble vide.

Un sous-ensemble S est compact ssi il est fermé et borné.

La métrique utilisée dans l’espace H(X) est la distance de Haussdorf, notée h.

Définition 2 : La distance de Haussdorf entre deux ensembles A et B de H(X) est définie par : max(d(A,B),d(B,A))

où : d(A,B) = max {d(x,B), xÎ A}

et d(x,B) = min {d(x,y), yÎ B}

 III.1.4 Transformation des espaces metriques [BAR 93]

Soit X un espace. Une transformation (mapping on X) est une fonction

telle que :

 Si S Ì X alors f(S) ={f(x) :xÎ S}

‚ Si f(x) = f(y) avec x,y Î X alors x = y

ƒ f(X) = X.

f est dite inversible si et seulement si il est possible de définir une transformation  , appelée la transformation inverse de f, telle que f ^-1(y) = x, où xÎ X est le point unique vérifiant y = f(x).

III.1.4.1.1 Dans la ligne reelle (ir) 

Les transformations affines dans IR sont des transformations f : de la forme :

f(x) = ax + b " xÎ IR, a, b constantes réelles.

III.1.4.1.2 dans le plan eucledien (ir²) 

Les transformations affines dans IR² sont des transformations de la forme :

f(x,y) = (ax+by+e, cx+dy+f) " (x,y)Î IR².

Où a, b, c, d, e, et f sont des constantes réelles. F est dite transformation affine à deux dimensions.

III.1.4.2  Transformation lipschitzienne [dav95]

Soit : une transformation définie sur l’espace métrique (IR²,d), d représente la distance entre deux points de IR². La transformation W est dite lipschitzienne, avec pour facteur de lipschitz le réel s strictement positif si :

d(W(x),W(y)) £ s.d(x,y) " (x,y)Î IR².

La transformation W est dite contractante si : 0 < s < 1.

III.1.4.3  Point fixe [dav 95] 

Une transformation contractante W possède un unique point fixe x_{f Î} IR², tel que

W(x_f) = x_f. Pour tout point x élément de IR², la séquence {W⁰ⁿ(x) :n=0,1,2,...}converge vers x_f.

" x Î IR².

III.1.4.4 Transformation contractante sur l’espace h(IR²) [dav 95]

Soit une transformation contractante   définie sur l’espace métrique (IR²,d) avec le réel s pour facteur de contraction. La transformation  :

définie par :

W(B) = {W (x) : x Î B}, " B Î H(IR²),

est contractante sur ( H(IR²),h_d ), avec s pour facteur de contraction, h_d désigne la distance de Haussdorf.

III.1.4.5  Transformation finalement contractante [dav 95]

Soit une transformation lipschitzienne W. S’il existe un entier n tel que la transformation W⁰ⁿ est contractante, alors W est dite finalement contractante. L’entier n est appelé exposant de contraction.

III.1.5.1  Definition des fractales 

Une fractale est un sous-ensemble A d’un espace métrique X, tel que A est extrêmement compliqué géométriquement. Le terme " fractal " est issu du latin " fractus " qui signifie brisé, irrégulier. Un objet fractal est une structure géométrique qui se reproduit sans fin à toutes les échelles [MAS 92].

Un objet fractal se caractérise par les propriétés suivantes [FAQ 96] :

 Ses parties ont la même forme ou structure que l’objet global à la différence quelles sont à une échelle réduite et peuvent être légèrement déformées.

‚ Sa forme est soit extrêmement irrégulière, soit extrêmement interrompue ou fragmentée, et ce quelle que soit l’échelle d’examen ;

ƒ Il contient des éléments distinctifs dont les échelles sont très variées et couvrent une très large gamme.

III.1.5.2  L’auto-similarite 

Un objet fractal est dit self-similaire ou auto-similaire s’il est composé de N copies de lui même, chacune étant une réduction d’un facteur r selon toutes les coordonnées de l’objet global [MAS 92] (auxquelles des transformations affines, comme les translations ou rotations peuvent ou non être impliquées). On cite comme exemple la poupée russe qui renferme en elle une poupée plus petite, qui à son tour renferme une troisième poupée similaire et ainsi de suite.

La notion d’auto-similarité revient dans plusieurs contextes car les objets naturelles sont auto-similaires (ou presque) : " les montagnes sont formés de piques qui sont à leurs tours formés de pics plus petits ....[MAN 83] ".

Exemple :

Le triangle de Sierpinski : Ce triangle est constitué de trois triangles qui sont une réduction d’un facteur d’échelle de l’ensemble, et chacun des trois triangles est lui même constitué de trois autres triangles qui sont une réduction d’un facteur ...etc.

Figure III.1 : Triangle de Sierpinski.

En prenant en considération l’auto-similarité, on peut représenter les images (les formes redondantes) par un nombre restreint de paramètres, plutôt que de stocker les images de chaque feuille de chaque arbre, ou de chaque pic de chaque montagne, il est possible et préférable de faire appel à une fonction relativement simple qui génère n’importe quel niveau de détails. C’est le théorème de M.F.Barnsley appelé IFS (Iterated Functions System)

[BAR 93].

III.1.5.3  La dimension fractale 

La dimension fractale d’un objet traduit la manière dont il occupe l’espace, c’est un concept métrique, qui mesure le degrés d’irrégularité ou de brisure de l’objet fractal.

L’expression mathématique de la dimension fractale d’un objet A est donnée par :

D =

Où : N(A, e ) = couverture de A = plus petit entier M tel que AÌ

B(x_n,e ) :Boule centrée en x_n et de rayon e . AÎ H(X).

III.2  Theorie des ifs et compression par fractales

La compression d’images basée sur les fractales, est une méthode de compression dans laquelle les similarités au sein de la même image à différentes échelles, seront utilisées pour la compression.

La théorie des IFS est une extension de la géométrie classique. Elle utilise un ensemble de transformations affines pour exprimer des relations entre les parties d’une même image. En utilisant seulement ces relations, on peut exprimer et définir des images complexes (nuages, feuilles, arbres,...etc.).

Avec la théorie des IFS, on peut décrire aussi clairement des nuages qu’un architecte puisse décrire une maison. [BAR 93].

III.2.1 Principe de la compression par ifs 

Le principe de la méthode de compression dite par IFS ou fractale est l’exploitation des auto-similarités des images naturelles.

L’auto-similarité  désigne la propriété qui fait que certains objets peuvent être construits à partir de parties d’eux même moyennant des transformations spécifiques. Les auto-similarités dans une image peuvent être considérées comme un type particulier de redondances.

En effet, au lieu de rechercher la corrélation entre les pixels adjacents, on s’intéresse à des corrélations entre parties plus au moins espacées dans l’image.

III.2.2 Definition d’un ifs [bar 93][bar 93a]

Un IFS (Système de Fonctions Iterées) W de facteur de contraction S est un ensemble de n transformations contractantes linéaires : w₁ , w₂ , ..., w_n définies dans un espace métrique

(X,d) avec :

S = Max ( S_{i ,} i =1,..., n)

Où :

X : espace des images ; d : une mesure de distance .

On le note :{X ; w_i, i=1,2,...,n}.

Les transformations w_i composants un IFS sont des transformations affines.

Soit A un sous ensemble d’un plan, considérons A comme une image, le collage obtenu par l’application de N contractions à A et l’assemblage du résultat peut être exprimé par :

Les w_i peuvent être décrites comme une combinaison de rotation, de réduction d’échelle et de translation de coordonnées des axes dans un espace à n-dimension(s).

Où : a, b, c, d, e, et f représentent des nombres réels ( paramètres de transformation ) .

On peut générer les valeurs des transformations comme suit :

a = r cosq , b = -s sinj , c = r sinq , d = s cosj

Où : r : est le facteur de réduction sur x

s : est le facteur de réduction sur y

q : est l’angle de rotation sur x

j : est l’angle de rotation sur y

e : est la translation en x

f : est la translation en y

Comment peut-on trouver une transformation affine W qui produit un effet désiré ? .

Voyons comment trouver la transformation affine qui transforme une grande feuille en une petite (voir figure III.2), i.e. trouver les paramètres a, b, c, d, e et f pour lesquels la transformation W a la propriété suivante :[BAR 93A]

W(grande feuille) » petite feuille.

Figure III.2 :transformation d’une grande feuille en une petite feuille.

La procédure à suivre est :

 Introduire des axes x et y.

Marquer trois points sur la grande feuille et déterminer leurs coordonnées (x₁,y₁), (x₂,y₂), (x₃,y₃).

‚ Marquer les trois points correspondants sur la petite feuille et déterminer leurs coordonnées (a ₁,b ₁), (a ₂,b ₂), (a ₃,b ₃) respectivement.

ƒ Déterminer les valeurs des coefficients a, b et e par la résolution du système des trois équations suivant :

„ Déterminer c, d, et f de la même manière par le système des trois équations suivant :

Chacune des transformations w_i doit avoir une probabilité Pi, avec une importance relative aux autres transformations.

La somme des probabilités est égale à 1.

Association des probabilites [bar93]

On associe à chaque transformation affine w_i d’une image A une probabilité Pi calculée par l’expression suivante :

Pi(w_i) » Où :

Pour i = 1,2,...,n.

Remarque : Si un des nombres Pi est nul, il faudra le remplacer par une petite valeur positive (0.001 par exemple) et ajuster les autres probabilités de façon à ce que leur somme soit égale 1.

Soit un IFS {IR² ;w₁,w₂,w₃ }composé des transformations affines suivantes :

Son facteur de contraction est égal à 1/4.

Toutes les transformations réduisent l’objet initial par 0.5 (dans chaque direction). Le point fixe de cet IFS est appelé " triangle de Sierpinski " (Figure III.3)

Figure III.3 :construction de triangle de Sierpinski.

Le carré initial centré à l’origine et de cotés de longueur 2x₀, 2y₀ est transformé en trois carrés homothétiques par les transformations w₁,w₂,w₃. Ce processus est en suite itéré.

III.2.3 Attracteur d’un ifs [dav95]

Soit un IFS {IR² ;w_i, i=1,2,...,n}. L’opérateur W : défini par :

W(B) = w_i(B), " BÎ H(IR²)

est contractant et a pour facteur de contraction celui de l’IFS. L’opérateur W possède un unique point fixe At donné par :

At = W(At) = w^on(x), " xÎ H(IR²).

L’objet At est appelé attracteur de l’IFS et il est égal à l’union de n copies de lui même transformées par w₁,w₂,...,w_n.

III.2.4  Theoreme de collage [bar 93a]

Soit l’espace métrique complet (X , d). Soit un point A Î H(X) et un IFS

{X ;w_i, i=1,2,...,n} avec le réel s, 0 £ s < 1 pour facteur de contraction.

On vérifie la relation :

h_d(A,At) £ h_d(A, ,   " AÎ H(X).

Ce théorème fournit une borne supérieure à la distance de Hausdorff h_d entre un point A inclus dans H(X) et l’attracteur At d’un IFS.

Il indique que s’il est possible de transformer un objet A de manière à vérifier

tout en s’assurant que W est contractante, alors le point fixe At de l’opérateur W est proche de A.

III.2.5  Theoreme de collage generalise [dav95]

Considérons l’opérateur W finalement contractant, avec pour exposant de contraction l’entier n ; il existe alors un unique point fixe x_f Î X, tel que :

x_f = W(x_f) = w^on(x), " xÎ H(X).

Dans ce cas :

h_d(A,At) £ h_d(A, ,

Où a est le facteur de Lipschitz de W et s est le facteur de contraction de W.

III.2.6  Probleme inverse 

Jusqu’ici, on a vu que les IFS permettent la génération d’images totalement auto-similaires en utilisant un nombre restreint de transformations. Seulement, dans le cadre de l’application de la géométrie fractale pour la compression d’images et étant donnée une image initiale (image fractale), il est important de trouver le bon IFS de telle sorte que l’attracteur de l’IFS est l’image à coder. La recherche de cet IFS permettant d’approximer une image donnée est un problème inverse difficile à résoudre. Barnsley montre qu’à l’aide du théorème de collage on peut résoudre ce problème. Toutefois, ce théorème ne fournit aucune méthode pour trouver l’IFS. Cette image approximée reste quasiment invariante et on obtient des taux de compression trop élevés, puisque la mémorisation des coefficients de la transformation fractale W nécessite " moins d’informations " que la mémorisation de l’image originale. Dans ce cas, on dit que la compression d’image par fractale est une méthode de compression avec perte du fait que l’attracteur ne constitue qu’une approximation de l’image originale.

L’approximation de l’image à partir d’elle même n’est pas facile à réaliser lorsque celle- ci n’est pas auto-similaire.

III.2.7  La limite des ifs 

Les IFS ont montré leur bonne performance en compression (des taux très élevés), ce qui est très important, cependant, deux aspects montrent leur insuffisance :

 les images compressées sont des figures typiquement fractales (similarité à tous les niveaux), alors que les images du monde réel tel que le visage d’un homme ou une maison ne sont pas tout à fait fractals (auto-similarité par régions).

‚ Ce sont des images à deux niveaux : noir et blanc, alors qu’on veut coder les images à plusieurs niveaux de gris.

Pour surmonter ce problème, on fait appel aux PIFS (Partitionned Iterated Function System) qui constituent une extension des IFS et qui peuvent donc coder n’importe quelle image.

III.3  Compression d’images basee sur les pifs

Pour pouvoir exploiter la similarité entre les régions d’une image quelconque, on va utiliser une méthode qui complémente la méthode des IFS et qui introduit le partitionnement et la génération des niveaux de gris, c’est la méthode des PIFS.

On introduira les méthodes de base permettant d’associer à une image naturelle une transformation finalement contractante W ayant pour attracteur une approximation de l’image elle-même.

III.3.1  Auto-similarite dans les images 

les images réelles ne contiennent pas le même type d’auto-similarité que celui des fractales tel que le triangle de Sierpinski ou la fougère de Barnsley, où l’image est constituée de l’union des répliques réduites de l’image entière. En effet, l’image réelle est formée de copies des parties d’elle-même. On le voit clairement sur l’image de LENA (Fig.III.4), où un échantillon de régions sont similaires à différentes échelles : une portion de son épaule chevauche (ou repose sur ) une région qui lui est presque identique, et la portion de reflet du chapeau dans le miroir est similaire(après transformations) à une partie de son chapeau. On devra alors, tolérer quelques erreurs, lors du codage de l’image comme un ensemble de transformations. L’image codée ne sera pas donc une copie identique de l’image originale mais plutôt une approximation d’elle-même.

III.3.2 Point fixe du pifs [fis94][pei92]

Dans ce cas, le théorème du point fixe reste valable. Ainsi, pour toute image initiale f₀, la séquence :

converge vers une image f qui vérifie

L’image f, notée |W|, est appelée le point fixe ou l’attracteur de la transformation W.

III.3.3 Transformation de l’image 

La compression d’une image par fractales repose sur une transformation que nous appelons transformation fractale et qui consiste à transformer l’image à l’aide d’un opérateur finalement contractant, de manière à ce que son aspect visuel reste quasiment inchangé. Pour cela, la transformation de l’image est composée de n sous-transformations élémentaires, chacune opérant sur un bloc de l’image, de la manière suivante (voir Figure III.5) :

L’image A (du départ) est partitionnée en n blocs r_n appelés blocs destination (ou blocs range). Elle s’ecrit : A=

Cette partiton du support de l’image en blocs destination est appelée partition R.

figure III.5 : Blocs destination r_i et blocs source d_i

Chaque bloc destination est ensuite mis en correspondance avec un autre bloc transformé w_i(d_i) lui " ressemblant " au sens d’une mesure d’erreur sur les niveaux de gris. Le bloc d_i, appelé bloc source est recherché au travers d’une librairie composée de Q blocs appartenant à l’image. Les Q blocs ne forment pas nécessairement une partition de l’image mais sont représentatifs de toute l’image. La géométrie de la région d_i doit être proche de celle de bloc r_i , de façon à limiter les temps de calcul lors des comparaisons inter-blocs, puisque ceux-ci sont liés à la complexité de la transformation spatiale utilisée.

Une seconde contrainte impose que les blocs source soient en moyenne de surface supérieure à celle des blocs destination.

La transformation W de l’image A est formulée à l’aide de l’équation suivante :

W(A) = w_i(d_i) =

Où est l’approximation du bloc destination r_i obtenue en transformant le bloc source d_i par w_i (l’opération permettant d’obtenir le bloc à partir du bloc d_i est appelée opération de collage).

Chaque transformation w_i s’écrit sous la forme :

Où i = 1,...,n.

On peut l’écrire aussi :

w_i(A) = w_i( x,y,f(x,y)), f(x,y) = niveau de gris.

Le niveau de gris constitue ici la troisième dimension, s_i contrôle le contraste et l_i la luminance.

Pour que le codage par fractales soit efficace, il doit y avoir suffisamment de similarités locales à diverses échelles entre les blocs de la partition R et les blocs source d_i . Lorsque ceux-ci sont recherchés dans toute l’image, la condition est généralement vérifiée. Si la recherche se fait dans une partition contenant un nombre restreint de blocs, le codage n’est plus optimale, mais plus rapide. Le but est de trouver le meilleur compromis entre le nombre de blocs source disponibles pour les recherches de similarités, et la ressemblance entre les blocs de la partition R et les blocs d_{i .}

Bien que dans la pratique, il est plus facile d’utiliser des blocs carrés, il est toujours possible d’utiliser d’autres formes telles que les rectangles, triangles, polygones,...etc.

Les conditions de base pour la conception d’un système de codage d’image digital basé sur les fractales sont :

 Le choix de partitionnement de l’image ;

‚ Le choix de la mesure de distorsion ;

ƒ Le choix des transformations fractales.

III.3.3.1 Partitionnement de l’image [dav 96][tab 96]

Pour minimiser le nombre de blocs à coder et de là, le nombre de transformations locales, différents modèles de partitionnement d’images pour la compression par fractales ont été étudiés, nous citerons :

Partitionnement carré : uniforme ou à deux niveaux, très utilisé de fait qu’il est facile à réaliser, il a été adopté dans la méthode de Jacquin.

Partitionnement quadtree : Vu l’utilisation de blocs de taille fixe dans le partitionnement carré, ce qui constitue un lourd inconvénient (existence de régions contenants beaucoup de détails), une généralisation de ce dernier est l’utilisation d’un partitionnement quadtree.

Réalisé par un découpage récursif en blocs carrés (quatre quadrants de même dimension), ce processus est représenté par un arbre de degré quatre (à chaque noeud interne, correspond quatre fils), la racine correspond à l’image entière.

Partitionnement rectangulaire : Il est semi-rigide dans le sens où les arêtes des blocs demeurent obligatoirement soit horizontales, soit verticales : la géométrie des blocs est à orientation définie.

Partitionnement HV (Horizontal Vertical) : L’image est partitionnée horizontalement et verticalement avec récursivité pour former deux nouveaux rectangles. Il est flexible car la position de la partition est variable.

Partitionnement à base de polygones : L’image est partitionnée adaptativement en polygones (processus récursif). Cette technique permet une meilleure représentation des objets formant l’image. Il est flexible car la position de la partition est variable et permet de représenter les régions avec beaucoup de détails.

Partitionnement triangulaire : Il est souple car il est calculé sur un ensemble de points pouvant être positionnés à peu prés n’importe où sur le support de l’image.

III.3.3.2 La mesure de distorsion 

On a vu précédemment la métrique de Haussdorf, qui est une mesure de distance entre deux sous-ensembles de IRⁿ. Dans le cas des images, on définit la distance comme une mesure de degré de proximité ou de ressemblance entre deux images. Plusieurs métriques existent dans l’espace des images, on site :

 La métrique SUP définie par :

d(f,g) = SUP | f(x,y) - g(x,y) |

(x,y)Î I²

f(x,y)Î [0,n] = I ; g(x,y)Î [0,n] = I. (En considérant les images f et g comme des images carrées de taille nÎ n).

Cette métrique recherche la position (x,y) où les deux images f et g diffèrent le plus, et considère cette différence comme étant la différence entre elles. Elle est plus utilisée en théorie. [KOM 95].

En pratique, on a :

‚ L₂ DISTANCE (distance quadratique moyenne) :

dL₂ (f,g) = L₂ distance (f,g) =

ƒ L₁ DISTANCE :

dL₁ (f,g) = L₁ distance (f,g) =

„ La distance RMS (Root Mean Squared) :

Ces trois distances sont très utilisées car elles sont faciles à calculer et donnent une bonne indication sur le degré de ressemblance entre deux images.

iii.3.4 methode de jacquin [dav 95]

L’approche de A. Jacquin [JAC 92] est fondée sur une partition R à géométrie carrée. L’image est partitionnée en blocs destination (ou blocs parents) carrées de taille fixe égale à B*B pixels (B = 8). L’algorithme recherche, pour chacun des blocs destination r_i ,le bloc source d_i de taille D*D (D = 2B) qui minimise l’erreur d(r_i,), où est l’approximation de r_i calculée à partir du bloc source d_i. La mesure d’erreur d est donnée par :

d(r_i , ) =

où et sont respectivement les valeurs des pixels d’indice j à l’intérieur du bloc original r_i et du bloc collé .

L’opération de collage d’un bloc source d_i sur un bloc destination r_i, réalisée par la transformation w_i, se décompose en deux parties :

La transformation spatiale (géométrique) : Elle ramène le bloc source d_i de taille D*D à l’échelle et au-dessus du bloc destination r_i de taille B*B. Le bloc ainsi transformé, noté b₂⁽ⁱ⁾, est obtenu par décimation des pixels du bloc source : un pixel de coordonnées (x_i , y_j) dans b₂⁽ⁱ⁾ est donné par l’équation suivante :

b₂⁽ⁱ⁾(x_i , y_j) =

dans laquelle (x_k , y_l) sont les coordonnées d’un pixel de niveau de gris noté t_i à l’interieur du bloc d_i.

La transformation massique :

Elle agit sur la luminance des pixels du bloc b₂⁽ⁱ⁾ pour approximer le bloc destination r_i.

Les transformations massiques utilisées appartiennent à deux classes :

1^ere classe : Elles agissent seulement sur les valeurs des pixels :

 Absorption par g₀ : La valeur du pixel (i , j) est affectée (forcée) par la valeur de g₀.

M₀(b₂⁽ⁱ⁾)_i,j = g₀, g₀ Î {0,...,255}.

‚ Translation de luminance : On ajoute à la valeur de pixel (i , j) une constante D g.

M₁(b₂⁽ⁱ⁾)_i,j = b₂⁽ⁱ⁾_i,j + D g, D g Î {-255,...,0,...,255}

ƒ Echelonnage par a ou modification de contraste (contrast scaling) :

M₂(b₂⁽ⁱ⁾)_i,j = a b₂⁽ⁱ⁾_i,j , a Î [0,1].

„ Inverse de couleurs : On inverse la couleur du pixel (i , j) en la substituant à la valeur maximale des niveaux de gris g_max [TAB 96].

M₃(b₂⁽ⁱ⁾)_i,j = g_max – b₂⁽ⁱ⁾_i,j

Où M_k (b₂⁽ⁱ⁾)_i,j  est la transformation massique numéro k.

2^eme classe : Elles ne modifient pas les valeurs des pixels, mais les mélangent ou les déplacent  dans les blocs, elles sont appelées les isométries, elles sont au nombre de huit :

1°) Identité :

ISO₀(b₂⁽ⁱ⁾)_i,j = b₂⁽ⁱ⁾_i,j.

2°) Réflexion orthogonale par rapport à l’axe de symétrie horizontal (i =(B-1)/2) :

ISO₁(b₂⁽ⁱ⁾)_i,j = b₂⁽ⁱ⁾_B-1-i,j.

3°) Réflexion orthogonale par rapport à l’axe de symétrie vertical (j =(B-1)/2) :

ISO₂(b₂⁽ⁱ⁾)_i,j = b₂⁽ⁱ⁾_i,B-1-j.

4°) Réflexion orthogonale par rapport à la première diagonale (i = j) :

ISO₃(b₂⁽ⁱ⁾)_i,j = b₂⁽ⁱ⁾_j,i.

5°) Réflexion orthogonale par rapport à la seconde diagonale (i+j =B-1) :

ISO₄(b₂⁽ⁱ⁾)_i,j = b₂⁽ⁱ⁾_{B-1-j, B-1-i.}