tipe-luong_hong_viet_3

5/11/2018 tipe-luong_hong_viet_3 - slidepdf.com

http://slidepdf.com/reader/full/tipe-luonghongviet3 1/40

Rapport final de TIPE

Étude de la méthode de la transformation enondelette et l’application à la compression des

images

LUONG Hông ViêtTuteur: Prof Dr NGUYÊN Thi Hoàng Lan

15 juillet 2005



Remerciements

Je voudrais tout d’abord exprimer ma profonde reconnaissance à mon profes-seur NGUYÊN Thi Hoang Lan, le tuteur, qui a dirigé mon travail, ses conseilset ses commentaires précieux m’ont permis de surmonter mes difficultés et deprogresser au cours de mes études.

Je tiens également à remercier mes camarades de la promotion X, pour leursympathie ainsi que leurs idées constructives.

1



Résumé

Les ondelettes sont des outils qui ont prouvé leur efficacité en théorie du si-

gnal depuis dizaines années. Nous montrons comment elles peuvent être utiliséesdans la compression des données. Nous allons considérer les théories d’ondelette,la transformation en ondelette, Et puis, c’est la norme JPEG2000, qui utilise latransformation en ondelette.



Table des matières

1 Introduction 51.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Organisation du rapport . . . . . . . . . . . . . . . . . . . . . . . 5

2 La transformée en ondelette 7

2.1 Ondelette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.1 Qu’est-ce que c’est une ondelette ? . . . . . . . . . . . . . 72.1.2 Introduction de l’ondelette . . . . . . . . . . . . . . . . . 7

2.2 La transformation en ondelette continue . . . . . . . . . . . . . . 82.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.2 La relation entre échelle et fréquence . . . . . . . . . . . 102.2.3 5 étapes pour la transformée en ondelette continue . . . . 10

2.3 La transformation en ondelette discrète . . . . . . . . . . . . . . . 112.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3.2 Approximation et détail . . . . . . . . . . . . . . . . . . 122.3.3 Analyse multirésolution (AMR) . . . . . . . . . . . . . . 12

2.3.4 Reconstruction d’ondelette . . . . . . . . . . . . . . . . . 142.4 Ondelettes orthogonales et biorthogonales . . . . . . . . . . . . . 16

2.4.1 Ondelettes orthogonales . . . . . . . . . . . . . . . . . . 162.4.2 Ondelettes biorthogonales . . . . . . . . . . . . . . . . . 16

3 Étude de la compression d’images de la norme JPEG2000 183.1 Introduction à la norme de JPEG2000 . . . . . . . . . . . . . . . 193.2 Les étapes de compression JPEG2000 . . . . . . . . . . . . . . . 19

3.2.1 Décomposition en tuiles . . . . . . . . . . . . . . . . . . 193.2.2 Transformation des plans couleurs . . . . . . . . . . . . . 21

3.2.3 Transformation en ondelette . . . . . . . . . . . . . . . . 213.2.4 Quantification . . . . . . . . . . . . . . . . . . . . . . . . 243.2.5 Codage entropique . . . . . . . . . . . . . . . . . . . . . 25

1



4 Implémentation et résultats expérimentaux 314.1 Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Evaluation de la qualité . . . . . . . . . . . . . . . . . . . . . . . 32

5 Conclusions 35

2



Table des figures

1.1 Les étapes de compression d’image JPEG2000 . . . . . . . . . . 5

2.1 Ondelette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Transformée de Fourier . . . . . . . . . . . . . . . . . . . . . . . 92.3 Transformée en ondelette . . . . . . . . . . . . . . . . . . . . . . 92.4 Échelle et fréquence . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.5 Étape 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.6 Étape 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.7 Étape 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.8 L’approximation et le détail . . . . . . . . . . . . . . . . . . . . . 122.9 L’abre de décomposition . . . . . . . . . . . . . . . . . . . . . . 142.10 La reconstruction d’ondelette . . . . . . . . . . . . . . . . . . . . 152.11 Le détail et l’approximation reconstruite . . . . . . . . . . . . . . 15

3.1 Les étapes de compression d’image JPEG2000 . . . . . . . . . . 203.2 Décomposition en tuiles . . . . . . . . . . . . . . . . . . . . . . 213.3 Transformation en ondelette . . . . . . . . . . . . . . . . . . . . 21

3.4 Ondelette 9/7 biorthogonale . . . . . . . . . . . . . . . . . . . . 223.5 Transformée en ondelette 2D . . . . . . . . . . . . . . . . . . . . 233.6 Ondelette biorthogonale 9/7 . . . . . . . . . . . . . . . . . . . . 243.7 Plan de bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.8 Ordre de balayage . . . . . . . . . . . . . . . . . . . . . . . . . . 263.9 Principe du code d’Elias . . . . . . . . . . . . . . . . . . . . . . 283.10 organisation des variables utilises dans le processus de codage dé-

codage des blocs . . . . . . . . . . . . . . . . . . . . . . . . . . 293.11 Principe de codage des blocs mettant en évidence l’interdépen-

dance contexte-codeur arithmétique . . . . . . . . . . . . . . . . 30

4.1 L’interface de programme . . . . . . . . . . . . . . . . . . . . . . 314.2 Image relax-orig.bmp . . . . . . . . . . . . . . . . . . . . . . . . 33

3



Liste des tableaux

2.1 Table de coefficients du filtre Daubechies 9/7 . . . . . . . . . . . 172.2 Table de coefficients du filtre LeGall 5/3 . . . . . . . . . . . . . . 17

3.1 Matrice de transformée des espaces couleur . . . . . . . . . . . . 223.2 Les contextes en fonction du type de codage . . . . . . . . . . . . 27

4.1 Les résultats d’image bagues.jp2 . . . . . . . . . . . . . . . . . . 324.2 Les résultats d’image bagues.jpg . . . . . . . . . . . . . . . . . . 324.3 JPEG2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.4 JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4



Chapitre 1

Introduction

1.1 Objectifs

Ce TIPE a pour but d’étudier la transformation en ondelette et l’application àla compression des images. Le terme ondelette n’est pas inconnue dans le mondede traitement de signal. Les ondelettes sont une nouvelle famille des fonctionsde base qui peuvent être employées pour rapprocher des fonctions générales. Ilscombinent les propriétés puissantes comme (bi)orthogonalité, localisation à tempset fréquence, et algorithmes rapides. Les applications d’ondelette sont apparues deplus en plus, dans la domaine traitement de la parole, compression des données,compression d’image. Dans ce TIPE, j’étudie également la compression d’imageJPEG2000, parce que, dans les étapes de compression d’image JPEG2000, il y aune étape de transformée en ondelette.

FIG . 1.1 – Les étapes de compression d’image JPEG2000

1.2 Organisation du rapport

Dans ce rapport je vais aborder l’ondelette, la transformation en ondelette, etson application dans la compression d’image JPEG2000.

Ce rapport se compose par 5 parties :

5



– Chapitre 1 : Elle contient des introductions générales sur l’ondelette et lanorme JPEG2000 et le cadre de mon travail.

– Chapitre 2 : Le but de cette partie est d’introduire la définition d’onde-lette. Dans ce chapitre, je présenterai la définition d’ondelette et l’historiqued’ondelette et aussi l’historique de développement de la transformation enondelette. Puis, c’est la transformation en ondelette dans 2 cas particuliers :transformation en ondelette continue et discrète. Je vais également présenterl’ondelette orthogonale et l’ondelette biorthogonale.

– Chapitre 3 : La norme JPEG2000. Dans ce chapitre, l’historique de lanorme JPEG2000 et les étapes de compression de JPEG2000 sont intro-duites.

– Chapitre 4 : L’application et les résultats expérimentaux : Je vais montrerquelques résultats expérimentaux et mettre en relation entre le résultat deJPEG et JPEG2000.

– Chapitre 5 : Conclusions : Quelques conclusions sur ce TIPE

6



Chapitre 2

La transformée en ondelette

La transformée en ondelette (TO) est apparue en géophysique au début des an-nées 1980 pour l’analyse des signaux sismiques, et a été formalisée plus tard par

Grossmann et Morlet (1984) et Goupillaud. C’est au sein de ces dernières com-munautés que des développements théoriques et appliqués majeurs ont eu lieuces quinze dernières années. Des avancées significatives ont notamment été faitepar Meyer, Mallat, Daubechies , Chui, Wornell et Holschneider. Ces avancées ontalors influencé d’autres domaines de recherche, dont en particulier, des applica-tions pour la compréhension des processus géophysique (Foufoula-Georgiou etKumar, 1994). Ces interactions entre développement et application favorisent en-core aujourd’hui l’évolution rapide de l’outil "ondelettes".

Avant d’attaquer la transformée en ondelette, il faut avoir une connaissance debase sur l’ondelette.

2.1 Ondelette

2.1.1 Qu’est-ce que c’est une ondelette ?

Une ondelette est une forme d’onde de la durée limitée qui a une valeur

moyenne zéro, ou les ondelettes sont des ondes localisées par temps court.

En regardant des images des ondelettes et des ondes sinusoïdales, vous pouvezvoir intuitivement que des signaux avec les changements pointus pourraient mieuxêtre analysés avec une ondelette irrégulière qu’avec un sinusoïde douce.

2.1.2 Introduction de l’ondelette

D’un point de vue historique, l’analyse d’ondelette est une nouvelle méthode,après la théorie de base de Joseph Fourier au dix-neuvième siècle. Fourier a créé

7



FIG . 2.1 – Ondelette

les bases avec ses théories d’analyse de fréquence, qui se sont avérées énormémentimportantes et influentes.

L’attention des chercheurs a graduellement tourné de l’analyse basée fréquenceà l’analyse basée échelle quand elle a commencé à apparaître clairement que lesfluctuations moyennes de mesure d’une approche à différentes échelles pourraient

prouver moins sensible au bruit.La mention d’abord enregistrée de ce que nous appelons maintenant une "on-delette" semble avoir lieu en 1909, dans la thèse de Alfred Haar.

Jean Morlet et l’équipe au Centre de théorique Physique à Marseille sous AlexGrossmann en France a proposé la première fois le concept des ondelettes sous saforme théorique actuelle.

Les méthodes d’analyse d’ondelette ont été développées principalement parY. Meyer et ses collègues. L’algorithme principal remonte au travail de StephaneMallat en 1988. Après cela, la recherche sur des ondelettes est devenue internatio-nale. Une telle recherche est particulièrement en activité aux États-Unis, où elleest attaquée par le travail des scientifiques tels que Ingrid Daubechies, Ronald

Coifman, et Victor Wickerhauser.

2.2 La transformation en ondelette continue

Pour bien comprendre la transformation en ondelette continue, on revient deconsidérer la transformation de Fourier. Le processus d’analyse de Fourier estreprésenté par :

F (ω) =

∞

−∞

f (t)e− jωtdt

Les résultats de la transformation sont des coefficients F (ω). Quand on multiplieces coefficients par un sinusoïde de fréquence ω on peut obtenir les composants designal original. Visuellement, le processus regarde est comme suivant : De même,on a une définition de la transformation en ondelette continue.

8



FIG . 2.2 – Transformée de Fourier

2.2.1 Définition

La transformation en ondelette continue (TOC) est définie comme la sommesur tout le temps du signal multiplié par des échelles :

C (échelle, position) = ∞−∞

f (t)Ψ(échelle, position, t)dt

Avec :

Ψs,τ (x) =1√s

Ψ

x− τ

s

– t est coefficient de translation de temps– s est coefficient d’échelle

FIG . 2.3 – Transformée en ondelette

Donc, prendre des échelles, cela signifie l’étirage ou la compression de l’on-delette. Le décalage de temps signifie le déplacement d’ondelette. Les résultats

de TOC sont des coefficients d’ondelette C qui est la fonction de l’échelle et laposition. Multiplier chaque coefficient par ondelette d’échelle.

9



2.2.2 La relation entre échelle et fréquence

Il y a une correspondance entre les échelles d’ondelette et la fréquence commeindiqué par analyse d’ondelette. Comme la figure suivante :

FIG . 2.4 – Échelle et fréquence

– Basse échelle a

⇒ondelette compressée

⇒changer détail rapidement

⇒haute fréquence ω– Haute échelle a ⇒ ondelette tirée ⇒ changer détail lentement ⇒ basse

fréquence ω

2.2.3 5 étapes pour la transformée en ondelette continue

Il y a 5 étapes pour transformer en ondelette continue.

1. Prendre une ondelette et la comparer à une section au début du signal origi-nal

2. Calculer un nombre, C, qui représente comment étroitement corrélé l’onde-

lette est avec cette section du signal. Le c plus haut est, la plus similaire. Plusprécisément, si l’énergie de signal et l’énergie de l’ondelette sont égales à1, C peut être interprété comme coefficient de corrélation. Noter que les

FIG . 2.5 – Étape 2

résultats dépendent la forme d’ondelette que vous avez choisi.

10



3. Se déplacer l’ondelette à droite et répéter les étapes 1 et 2 jusqu’à sur tousles signaux.


4. Étirer l’ondelette et répéter l’étape 1 jusqu’à 3


5. Répéter les étapes 1 à 4 pour toutes les échelles

Quand on a fini toutes les étapes ci dessus, on fera produire les coefficients àdifférentes échelles par différentes sections du signal.

2.3 La transformation en ondelette discrète

2.3.1 Définition

La transformée en ondelette continue ne peut pas réaliser sur les signaux dis-crètes. En plus, le calcul des coefficients à chaque échelle possible dans la TOC

est un nombre de travail, et il peut générer trop de données. Donc, on peut choisirun sous ensemble de échelles et positions. Une autre technique est la transforméeen ondelette discrète.

La transformée en ondelette discrète, ou TOD (en anglais : Discrete WaveletTransform, ou DWT) est une technique utilisée dans la compression de données

11



numériques avec perte. La compression est réalisée par approximation successivesl’information initiale du plus grossier au plus fin.

2.3.2 Approximation et détail

Pour beaucoup de signaux, le contenu de basse fréquence est la pièce la plusimportante. Il est ce qui donne au signal son identité. Le contenu à haute fré-quence, d’autre part, nous donne la saveur ou la nuance. Par exemple, avec la voixhumaine, si vous enlevez les composants à haute fréquence, les bruits de voix dif-férents, mais vous pouvez comprendre ce qu’il a dit. Cependant, si vous enlevezassez des composants de basse fréquence, vous entendez le baragouin.

Dans la transformation en ondelette, on dit souvent l’approximation et le dé-

tail. L’approximation est haute échelle, des composants de basse fréquence designal. Les détails sont basses échelles, des composants de hautes fréquences. Leprocessus de filtrage est comme suivant : Le signal original, S, traverse deux filtres

FIG . 2.8 – L’approximation et le détail

complémentaires et émerge comme deux signaux. Donc, nous doublons les don-nées que nous avons commencé.

2.3.3 Analyse multirésolution (AMR)

Cette partie a l’objectif de présenter la décomposition par ondelettes et l’Ana-lyse Multirésolution pour introduire la norme de compression JPEG2000. Les on-delettes permettent de représenter une image, comme le font les fonctions cosinus

dans l’analyse de Fourier. Elles autorisent une bonne localisation en temps et enfréquence, toute l’information se concentre sur très peu de coefficients. La dé-composition se fait à partir d’un ensemble d’ondelettes de base obtenu à partird’une ondelette ’mère’ notée : Ψ(x). Cette base d’ondelette est obtenue par trans-lations et dilatation. L’analyse temps-fréquence par transformation d’un signal

12



dans la base de Fourier est limitée (principe d’incertitude de Heisenberg). Il estimpossible d’avoir une bonne localisation en temps et en fréquence, même en uti-lisant des méthodes à base de fenêtres glissantes à cause de la taille de la fenêtred’analyse. L’AMR qui nous permet de s’affranchir de ces problème, le signal seraprojeté sur des fonctions d’analyses pour toutes les résolutions 2− j qui composentle signal de longueur 2 j échantillons avec j ∈ Z . En effet, comme nous le verronspar la suite, le signal d’approximation de résolution 2− j sera ensuite décomposépour la construction du signal d’approximation et de détails de résolution 2−( j+1).L’itération de ce processus conduit à un pavage temps-fréquence. L’analyse étantréversible sous certaines conditions, on peut reconstruire le niveau i d’approxi-mation à partir des sous-bandes i+1. Après plusieurs itérations le signal originalpeut-être reconstruit. L’approximation d’une fonction à une résolution 2− j est dé-terminée par des moyenne locales sur 2 j échantillons. D’une façon plus formelle,l’approximation d’une fonction à la résolution 2− j est définie comme sa projectionorthogonale sur un espace V j

⊂L2(R). L’espace V j regroupe toutes les approxi-

mations possibles à l’échelle 2 j . La projection orthogonale de f sur V j est la fonc-tion f j ∈ V j qui minimise la distance f j−f . La transformée en ondelettes offreune étude pyramidale. L’analyse se fait à partir de dilatation et de translation del’ondelette mère. Cette transformation décrit les détails d’une image pour chaqueniveau de résolution. Ces détails correspondent à la différence d’information entredeux niveaux de résolution successives.

La multirésolution

Une suite {V j} j∈Z de sous-espaces fermés {V j} j∈Z de L2(R)∗ est une suited’approximations multirésolution si elle vérifie les sous propriété suivantes :

– ∀( j,k) ∈ Z 2, f (x) ∈ V j ⇔ f (t− 2 jk) ∈ V j

V j est invariant pour toute translation de longueur proportionnelle à l’échelle2− j . Il existe une grille spatiale ou temporelle sous jacente par pas de 2 j .

–∀ j ∈ Z, V j+1 ⊂ V j

Une approximation à la résolution 2− j contient toute l’information néces-saire à la construction d’une résolution plus grossière 2−( j+1), c’est une pro-priété de causalité

–∀ j ∈ Z, f (x) ∈ V j ⇔ f (x

2∈ V j+1)

La dilatation par un facteur de 2 agrandit les détail d’un facteur de 2, on abien une approximation à une résolution plus grossière. Il existe une grillefréquentielle sous-jacente en progression géométrique.

13



–

lim j→+∞

V j =

j=+∞ j=−∞

V j = 0

L’intersection des V j est réduite à 0 dans L2 Si la résolution est trop faible,c’est-à-dire que 2− j tend vers 0, on perd tous les détails. A résolution mini-male, on perd toute l’image.

– Il existe une fonction θ telle que {θ(t−n)}n∈Z soit une base de Riesz de V 0Avec la définition de multirésolution, on peut comprendre comme suivant.

Lorsqu’un cameraman effectue un zoom, il part d’une vision globale des chosespour se focaliser sur une zone d’intérêt en faisant apparaître des détails. L’analysemultirésolution formalise ce type d’approximation.

L’application directe de AMR est l’algorithme de Mallat. L’idée est de décom-poser un signal S en sa moyenne A1(approximation) et en ses détails D1 (détails).On répète ensuite l’opération en prenant pour signal A1, puis A2... On s’arrête

quand on atteint la résolution souhaitée ou quand la décomposition n’est plus pos-sible. Donc, le signal est cassé en plusieurs composants de basse résolution. C’estl’arbre de décomposition d’ondelette. L’autre partie est comment ces composants

FIG . 2.9 – L’abre de décomposition

peuvent être assemblés dans le signal original sans perte d’information. Ce pro-cessus est appelé reconstruction ou synthèse.

2.3.4 Reconstruction d’ondelette

On a déjà abordé comment la transformée en ondelette est utilisée pour ana-lyser ou décomposer des signaux ou une image. Pour synthétiser un signal, onle reconstruit à partir des coefficients d’ondelette. Où l’analyse d’ondelette inclus

14



FIG . 2.10 – La reconstruction d’ondelette

le filtrage et le sous-échantillonage, et la reconstruction contient le filtrage et lesur-échantillonage.

Le sur-échantillonage est le processus d’allonger un composant de signal parinsérer les zéros entre les échantillons. Pour reconstruire l’approximation de pre-mier niveau A1 à partir du vecteur de coefficient A1. Nous passons le vecteur A1de coefficient par le même processus que nous avons reconstruit le signal original.Cependant, au lieu de le combiner avec le détail cD1 de niveau-un, nous chargeonsun vecteur des zéros au lieu du vecteur de coefficients de détail. Le processus rendsune approximation reconstruite A1, qui a la même longueur que le signal originalS et qui est une vraie approximation de lui. De même, nous pouvons reconstruirele détail de premier niveau D1, en utilisant le processus analogue.

FIG . 2.11 – Le détail et l’approximation reconstruite

En fait, on combine les deux comme suivant :A1 + D1 = S

Parce que les coefficients de vecteur cA1 et cD1 ont été produits par sous-échantillonage et sont seulement moitié de la longueur du signal original, donc,

15



on ne peut pas directement être combiné pour reproduire le signal. Il est nécessaire

de reconstruire les approximations et les détails avant de les combiner. À partirde cela, on peut réaliser la technique synthèse à multiniveaux.

2.4 Ondelettes orthogonales et biorthogonales

2.4.1 Ondelettes orthogonales

La fonction d’échelle est une solution à une équation fonctionnelle fractal,appelée l’équation de raffinement :

φ(x) =N −1k=0

akφ(2x− k)

Ou la séquence (a0, a

1,...,a

N −

1) des entiers flottants est appelé la séquence d’échelleou le masque d’échelle. L’ondelettes exacte est obtenue par la combinaison li-néaire similaire :

ψ(x) =M −1k=0

bkφ(2x− k)

Ou la séquence (b0, b1,...,bM −1) des entiers flottants est appelé la séquence d’on-delette ou le masque d’ondelette.

Une condition nécessaire pour l’orthogonalité des ondelette est que l’ordred’échelle est orthogonal à tous ses décalages par un chiffre pair des coefficients :

n∈Z

anan+2m = 2δm,0

Dans ce cas-ci, il y a le même nombre M=N de coefficients dans la dilatationcomme dans l’ordre d’ondelette, l’ordre d’ondelette peut être déterminé commebn = (−1)naN −1−n

2.4.2 Ondelettes biorthogonales

Une autre classe des ondelettes rendus populaires par I. Daubechies sont lesondelettes biorthogonales. Elles peuvent être construites pour avoir la symétrie

temporelle. Dans ce cas-ci, il y a deux fonctions de dilatation φ,˜φ, qui peuventgénérer des différents analyses de multirésolution, et en conséquence deux fonc-

tions différentes d’ondelette φ, φ. Ainsi les nombres M, N des coefficients dans

16



les ordres de dilatation a, a peuvent être différents. La séquences de dilatationdoivent doivent satisfaire la condition suivante de biorthogonalité :

n∈Z

anan+2m = 2δm,0

Les séquences d’ondelette peuvent-être déterminés par bn = (−1)naM −1−n, n =0,...,M − 1 et bn = (−1)naM −1−n, n = 0,...,N − 1 La norme de compressionJPEG2000 emploie l’ondelette biorthogonale de Daubechies M/N=5/3 de (égale-ment appelé l’ondelette LeGall 5/3 ) pour la compression sans perte et l’ondeletteDaubechies 9/7 (également connu sous le nom de Cohen-Daubechies-Feauveau9/7 ou "CDF 9/7") pour la compression avec perte.

Voici, c’est la table des coefficients d’analyse de Daubechies 9/7

Coefficients des filtres d’analyse Coefficients des filtres de synthèsei Filtre passe-bas Filtre passe-haut Filtre passe-bas Filtre passe-haut0 0.6029490182364 1.1150870524570 1.1150870524570 0.6029490182364±1 0.2668641184429 -0.5912717631142 0.5912717631142 -0.2668641184429±2 -0.0782232665290 -0.0575435262285 -0.0575435262285 -0.0782232665290±3 -0.0168641184287 0.0912717631142 -0.0912717631142 0.0168641184287±4 0.0267487574108 0.0267487574108

TAB . 2.1 – Table de coefficients du filtre Daubechies 9/7

Coefficients des filtres d’analyse Coefficients des filtres de synthèse

i Filtre passe-bas Filtre passe-haut Filtre passe-bas Filtre passe-haut0 6/8 1 1 6/8±1 2/8 -1/2 1/2 -2/8±2 -1/8 -1/8

TAB . 2.2 – Table de coefficients du filtre LeGall 5/3

17



Chapitre 3

Étude de la compression d’imagesde la norme JPEG2000

La compression est un processus qui crée une représentation de données com-pacte pour des buts de stockage et de transmission. Ainsi, la compression d’imagedoit non seulement réduire les conditions nécessaires de stockage et de largeurde bande, mais permet également d’extraire pour éditer, traiter, et viser les dispo-sitifs et les applications particuliers. Depuis longtemps, JPEG est la norme pourl’image sur l’Internet et partout dans les autres domaines d’informatique. Pour-tant, la norme JPEG actuelle présente un certain nombre d’inconvénients :

– L’efficacité de codage est limitée.– Le codage par blocs de 8x8 pixels génère un effet de mosaïque à bas débit

très gênant visuellement– La transmission d’images codées est très peu robuste en environnement

bruité– Les applications liées à l’image sont de plus en plus spécifiques et néces-

sitent de nouvelles fonctionnalités non résolues par JPEG.Le système de compression de l’image JPEG2000 a un avantage de taux de

distorsion plus que JPEG original. Plus important, il laisse également l’extractionde différentes résolutions, les fidélités de pixel, les régions d’intérêt, les compo-sants, et plus, tout vient d’un flux de bit compressé simple. Ceci permet à uneapplication de manipuler ou transmettre seulement l’information essentielle pourn’importe quel dispositif de cible de n’importe quelle image de source compresséede JPEG 2000.

18



3.1 Introduction à la norme de JPEG2000

Au début des années 90, un certain nombre de nouveaux algorithmes de com-pression d’image, comme CREW (compression with reversible embedded wave-lets) et EZW (embedded zerotree wavelet), émergé pour fournir non seulementperformance supérieure de compression, mais également un nouvel ensemble decaractéristiques invisibles avant. Basé sur une demande industrielle, le projet deJPEG 2000 a été approuvé comme nouvel article de travail en 1996. Un appelpour des contributions techniques a été publié en mars 1997. La première éva-luation est réalisée en novembre 1997 à Sydney, Australie, où 24 algorithmes ontété soumis et évalués. Basé sur l’évaluation, on l’a décidé de créer un JPEG 2000modèle de vérification (VM) qui mènerait à une exécution de référence pour leprocessus standard suivant. Le premier VM (VM0) est basé sur l’algorithme de laquantification codé par ondelette/treillis (WTCQ) soumis par SAIC et l’universitéde l’Arizona (SAIC/UA). Lors de la réunion de novembre 1998, l’algorithme EB-

COT (embedded block coding with optimized truncation) a été adopté dans VM3et le logiciel de VM entier a réimplanté d’une façon orientée objet. Le documentdécrivant le décodeur de base de JPEG 2000 (la partie I) a atteint "Committeedraft" (CD) statut le décembre 1999. Le JPEG 2000 est finalement devenu unStandard International (IS) au décembre 2000.

3.2 Les étapes de compression JPEG2000

Dans ce chapitre, on considère seulement le processus de compression. Leprocessus de décompression est inverse.

L’algorithme typique de codage JPEG2000 se divise essentiellement en 5 mo-dules : transformée couleur, transformée en ondelettes discrète, quantification, co-dage entropique et allocation de débit.

3.2.1 Décomposition en tuiles

Dans quelques situations, une image peut être tout à fait grande par rapport àla quantité de mémoire disponible de codec. En conséquence, elle n’est pas tou-

jours faisable pour coder l’image entière comme unité atomique simple. Plus spé-cifiquement, une image est divisée en un ou plusieurs des régions rectangulairesséparées appelées les tuiles. Sur chaque tuile, on considère comme une imageindépendante et traite sur celle.

19



FIG . 3.1 – Les étapes de compression d’image JPEG2000

20



FIG . 3.2 – Décomposition en tuiles

3.2.2 Transformation des plans couleurs

Au début, des images doivent être transformées (de l’espace de couleur deRVB) à l’espace de couleur YCbCr ou à l’espace de RCT (reversible componenttransform) à trois composants. Dans le mode avec perte, une approximation ré-versible de cette conversion de l’espace de couleur est employée. Cette étape estappelée la transformée de multi-composants. Le standard supporte deux transfor-mation de composants, c’est la transformation irréversible de composants(ICT)qui est utilisé pour le codage avec pertes ou sans perte et l’autre c’est la transfor-

mation réversible des composants (RCT) qui est utilisé seulement pour le codageavec perte.

3.2.3 Transformation en ondelette

FIG . 3.3 – Transformation en ondelette

Le filtre d’ondelette défaut utilisé dans JPEG 2000 est l’ondelette biorthogo-

nale 9/7. Les données originales x0, x1, . . ,x8 sont entrées de la droite. Supposeque la longueur des données originales est infinie, pour réaliser la transformée enondelette, nous appliquons d’abord la première étape "lifting", qui met à jour les

21



RCT

CodageY = R+2G+B

4

U = R−G

V = B −G

DécodageY = R+2G+B

4U = R−G

V = B −G

ICT

Codage

Y

U

V

=

0.299 0.587 0.114−0.16875 −0.33126 0.5

0.5 −0.41869 −0.08131

R

V

B

Décodage

R

V

B

=

1.0 0 1.402

1.0 −0.34413 −0.714141.0 1.772 0

Y

U

V

TAB

. 3.1 – Matrice de transformée des espaces couleur

données qui ont l’index impair x1, x3, .. comme suivant :

x2n+1 = x2n+1 + a ∗ (x2n + x2n+2)

Ou a et x2n+1 est le premier paramètre "lifting" et résultat. Après calculer, onva réaliser la deuxième étape "lifting"

FIG . 3.4 – Ondelette 9/7 biorthogonale

x2n = x2n + b ∗ (x2n−1 + x2n+1)

La troisième et quatrième étape sont similaires :

H n = x2n+1 + c ∗ (x2n + x2n + 2)

22



Ln = x2n + d ∗ (H n−1 + H n)

Ou H n et Ln sont les hauts et bas coefficients résultants de passage.

La transformée en ondelette 2 dimensionnelles

FIG . 3.5 – Transformée en ondelette 2D

Pour appliquer la transformée en ondelette à une tableau 2D, telle qu’uneimage, et on peut appliquer la transformée en ondelette dans la direction hori-zontale et verticale séparément.

La tableau 2D de données de l’image est d’abord filtre dans la direction ho-rizontale, qui a résulté deux sous-bandes, - une basse et haute horizontale sous-

bande passage. Chaque sous-bande passe un filtre vertical d’ondelette. L’image estainsi décomposée en quatre sous-bandes, - la sous-bande LL (filtre passe bas hori-zontal et vertical), LH (filtre passe bas vertical et passe haut horizontal), HL (filtrepasse haut vertical et passe bas horizontal) et le HH (filtre passe haut horizontal etvertical).

Et voilà les étapes sont représentés comme la figure suivante :– Étape 1. Initialisation de Phase 0 Trois lignes des coefficients x0, x1etx2

sont lues. Deux lignes des opérations de "lifting" sont exécutées, et les ré-sultats x1etx”0 sont générés.

– Étape 2. Initialisation de phase 2. Deux lignes additionnelles des coeffi-cients x3 et x4 sont lues. Quatre lignes des opérations de "lifting" sont

exécutées. Les résultats d’intermédiaire x3 et x”4, et la première ligne decoefficients de passe bas et haut sont L0 et H 0.

– Étape 3. Traitement répété. Pendant l’opération normale, la ligne modulebasé sur "lifting" lu dedans deux lignes des coefficients, fabrique quatre

23



FIG . 3.6 – Ondelette biorthogonale 9/7

lignes des opérations de "lifting", et génère une ligne de coefficients passebas et haut.

– Étape 4. "Flushing". Quand le fond de l’image est atteint, l’extension sy-métrique de frontière est de nouveau exécutée pour produire correctementdes bas et hauts coefficients finals de passage.

3.2.4 Quantification

Lors du codage avec pertes, la précision sur les coefficients d’ondelettes estréduite par quantification scalaire uniforme. Cette étape permet, d’une part, demettre à zéro les coefficients de faibles amplitudes (influant peu la qualité del’image) mais fixe aussi le taux de compression minimal de l’image (i.e lorsquel’information quantifiée est intégralement incluse dans le codestream). Après latransformée en ondelette, tous les coefficients d’ondelette sont uniformément quan-tifiés par suite :

wm,n = sign(sm,n)sm,n

δ

où sm,n sont les coefficients transformés, wm,n est le résultat quantifié, δ est le pasde quantification, sign(x) renvoie le signe du coefficient x.

Le processus de quantification convertit les coefficients d’ondelette du nombre

flottant en nombre entier. Dans le codage de JPEG, le processus de quantificationdétermine la distorsion permise de transformée de coefficients.Les coefficients quantifiés sont divisés en des paquets. Chaque sous-bande est

divisée en rectangles non-recouverts de taille égale. Trois rectangles correspon-dant au même endroit de l’espace à trois sous-bandes directionnelles HL,LH,HH

24



de chaque résolution de niveau comprenant un paquet.Les paquets sont encore divisés en rectangulaires non-recouverts bloc de code,

qui sont les entités fondamentales dans l’opération de codage entropique.Dans la compression de JPEG2000, il y a deux modes : cela dépend la trans-

formée en ondelette précédente. Si on utilise la TO 5/3(mode entier), la taille dupas de la quantification est fixée et égale à 1. Dans ce cas, c’est le codage sansperte. Si on utilise la transformée en ondelette 9/7(mode réel),

3.2.5 Codage entropique

Après la quantification, c’est l’étape de codage entropique. Les coefficientsquantifiés pour chaque sous-bande sont divisés en les blocs de code. La taille debloc est un nombre entier de puissance de 2 et le produit de largeur et hauteur nedépasse pas 4096. Après diviser une sous-bande en blocs de code, chaque blocsde code est codé indépendamment. Le codage est exécuté en utilisant le codeur de

plan de bit.La technique de codage de plan de bit est assez similaire à celles de EZW(Embedded

Zerotree Wavelet) ou SPIHT(Set Partionning in Hierachical Tree). Les différencesprincipales sont :

– Pas de inter-bandes dépendantes sont exploitées.– Il y a trois passes de plan de bit au lieu de deux.Ici, le plan de bit est un tableau binaire de bits de coefficients, même niveau

signifiant. Un bit est dit signifiant si le bit de même coefficient dans le plan supé-rieur est codé et vaut ’1’. Cette technique s’appelle EBCOT ( Embedded BitplaneCoding by Truncation).

FIG . 3.7 – Plan de bits

25



Le bloc de code est divisé en une bande horizontale, chaque bande a une hau-teur de 4. Si la hauteur de bloc de code n’est pas un multiple de 4, la hauteur dedernière bande est inférieure à 4.

FIG . 3.8 – Ordre de balayage

Ordre de balayage :– Verticalement 4 par 4– De gauche à droite– Du plan de bits MSB vers le plan de bits LSB

Un plan de bits ne sera parcouru et codé en une fois(une passe) mais en troispasses de codage :

1. La première passe dans un nouveau plan de bit s’appelle le passage depropagation de signification. Un bit est codé dans ce passage si sa locationn’est pas signifiante, mais au moins un de ses voisins huit-connectés estsignifiant afin de codage de sous séquence de bit dans le courant et sousséquence de plan de bit. Un bit est nouvellement signifiant si un bit est à ’1’et vient d’être codé dans la passe en cours.

2. La deuxième passe est le passage d’amélioration de magnitude. Dans cepasse, tous les bits de location qui sont devenus significatifs dans un plan debit précédent sont codés.

3. La dernière passe est la passe de netoyage pour vérifier les bits qui ne sontpas codés dans les deux premières passes.

Trois passes de codage par plan de bits vont permettre de mieux décorrélerles bits entre eux. A chaque passe seront associés des contextes différents. Uncontexte est une façon de tenir compte des voisins et chaque passe.

26



CtxContexte signifiance 0

12345678

Contexte signe 910111213

Contexte raffinement 141516

Contexte UNIFORM 17Contexte RUN-LENGTH 18

TAB . 3.2 – Les contextes en fonction du type de codage

Les contextes dépendent type de sous-bande(LL,LH,HL,HH) afin de tenir comptede la répartition statistique différente des coefficients suivant le type de filtrage.Chaque bit codé sera associé un contexte. Le couple donnée-contexte(D,Cx) seraenvoyé au codage arithmétique.

Codeur arithmétique

Le principe d’un codeur arithmétique est la subdivision d’intervalles corres-pondant à la probabilité du symbole LPS utilisé dans le code d’Elias. A chaquebit D, l’intervalle est divisé. A fin de garder une précision de calcul suffisante surl’intervalle, un ajustement est fait à chaque fois que l’intervalle sort des bornes.Les bornes de l’intervalle[0.75..1.5] permettent de faire l’approximation suivante :

1. Pour le sous-intervalle MPS : A-(QexA) devient A - Qe2. Et pour le sous-intervalle LPS : A-Qe devient Qe

Le codeur arithmétique permet en plus d’adapter l’estimation de probabilitépour chaque contexte Qe(I(Cb)), valeur Qe pointe par l’index "I" correspondant

27



FIG

. 3.9 – Principe du code d’Elias

au contexte Cb du symbole D à coder.Chaque contexte pointe sur un index d’une table d’estimation de probabilité.

Dans JPEG2000, cette table comprend 46 états différents ce qui permet au codeurde pourvoir adapter de façon plus rapide la probabilité d’apparition du symbole leplus probable pour chaque contexte. Un contexte est une famille regroupant tousles bits ayant des propriétés statistiques identiques. A chaque contexte est associéun index I ; qui pointe sur une table comportant les éléments suivants :

1. une estimation de probabilité Que(I),

2. la valeur du symbole le plus probable (0 ou 1) MPS(I),3. le numéro du prochain index pour le codage d’un LPS (symbole le moins

probable) NLPS,

4. et l’index suivant pour le MPS (symbole le plus probable) NMPS.

Les tables du codeur et du dé-codeur sont identiques et fixes.

28



FIG . 3.10 – organisation des variables utilises dans le processus de codage déco-dage des blocs

29



FIG . 3.11 – Principe de codage des blocs mettant en évidence l’interdépendance

contexte-codeur arithmétique

30



Chapitre 4

Implémentation et résultatsexpérimentaux

4.1 Programme

J’ai écrit un programme en utilisant la bibliothèque JasPer. C’est une biblio-thèque libre(voir l’annexe). Le programme est écrit en QT. QT n’a pas supportéJPEG2000, il a supporté les normes comme JPEG, GIF, BMP. Donc, j’écris pourcomparer les normes JPEG et JPEG2000. Et voilà c’est l’interface principale deprogramme.

FIG . 4.1 – L’interface de programme

31



4.2 Evaluation de la qualité

Pour évaluer la qualité, on peut mesurer la distorsion par le rapport ErreurQuadratique Moyenne(EQM). L’erreur quadratique moyenne notée EQM permetde mesurer de façon objective la dégradation entre une image X origine et une imageX comprime de coordonnées (n,m) et de dimensions M,N.

EQM =1

M.N .

N n=1

M m=1

(X origine(n,m) −X comprime(n,m))2

D’abord pour tester, j’ai utilisé l’image de niveau de gris (256 niveau de gris) avecla taille 256*256.

Taux de compression(bpp) EQM Temps de calcul0.454987 0.000397 0.04s

0.298615 0.998123 0.04s0.19841 2.854279 0.03s0.049286 49.87 0.02s0.039169 74.80 0.03s0.029663 117.56 0.03s0.019806 208.39 0.02s0.009323 594.28 0.02s

TAB . 4.1 – Les résultats d’image bagues.jp2

Taux de compression(bpp) EQM Temps de calcul0.571121 0.064 0.010.241287 4.720596 0.010.168076 11.070862 0.020.136139 17.355164 0.010.103073 27.746902 0.010.064148 59.20694 0.010.032669 202.316528 0.01

TAB . 4.2 – Les résultats d’image bagues.jpg

Avec l’image de couleur, par exemple : l’image relax-orig.bmp de taille 400x300on obtient les résultats suivants :

Donc on a les résultats suivants :

32



FIG . 4.2 – Image relax-orig.bmp

Taux de compression(bpp) EQM Temps de calcul1.199008 1.067475 0.26s0.899817 2.585369 0.21s

0.599867 7.530753 0.18s0.319458 31.009453 0.17s0.279675 35.185356 0.17s0.239858 41.714481 0.15s0.197533 49.065203 0.16s0.179458 58.500564 0.14s0.149983 70.904197 0.130.118058 88.525589 0.13s0.088125 114.438278 0.12s0.059858 151.436781 0.12

0.029792 224.520661 0.12

TAB . 4.3 – JPEG2000

33



Taux de compression(bpp) EQM Temps de calcul0.40065 39.5 0.2s

0.271917 61.2 0.20.2149 76.78 0.2

0.180058 89.56 0.20.157325 99.98 0.20.135808 111.74 0.10.114075 127.85 0.10.088517 157.29 0.10.056967 231.67 0.010.048775 61.249 0.010.028667 562.86 0.02

TAB . 4.4 – JPEG

Avec deux cas différent comme ci-dessus, l’image à niveau de gris et l’imagecouleur, on contaste que, la norme JPEG-2000, toujours nous donne la meilleurqualité, si les deux images reconstruites ont même taux de compression. Cepen-dant, le temp de calcul(c’est le temps de décodage) de l’image JPEG-2000 est plusélevé.

Normalement, on voit que dans l’image JPEG(avec le taux de compressionbas :<0.02), il y a de petits blocs. La raison principale, c’est que la norme JPEGutilise les blocs 8x8 pour traiter. Tandis que la norme JPEG-2000, utilse les tuiles,et dans la transformée en ondelette, on a gardé les résolutions dans 4 sous-bandes.Donc, on peut reconstruire l’image sans effet comme image JPEG.

Image JPEG Image JPEG-2000

34



Chapitre 5

Conclusions

Dans ce rapport, j’ai introduit la théorie d’ondelette. Les théories d’ondelettesont appliquées dans plusieurs domaines. Par exemple :

– Compression de données(signal,Compression d’image JPEG2000). Spé-cialement, nouveau standard de MPEG, c’est DivX.– Suppression de bruit(dans le domaine de traitement de la parole)– Extraction des caractéristiques.(Détection de discontinuité)– Analyse de données (données biologiques, données financières)En plus, l’application d’ondelette dans le cas particulier, c’est la compression

d’image JPEG2000. Avec plusieurs caractéristiques, la norme JPEG-2000 a desavantages suivants :

– Le premier avantage souvent est une meilleure qualité pour une taille iden-tique. Cela n’est malheureusement vrai que pour les très fortes compres-sions : Avec JPEG classique l’image sera absolument mauvaise (avec les ar-

tefacts bien connus comme l’apparition de blocs visibles), Mais avec JPEG2000de même taille sera largement plus acceptable. Par contre, pour les imagesde hautes qualités (donc faiblement compressée), l’avantage de JPEG2000est plus faible, même s’il existe.

– Un autre avantage de JPEG2000 est que l’organisation naturelle de des don-nées qui permet un affichage progressif d’assez bonne qualité avec une trèspetite portion du fichier original.

– Comme dans la partie technique, JPEG2000 supporte 2 mode, compressionavec perte et compression sans perte.

Cependant, la norme JPEG-2000 a encore des inconvénients :

– Effectivement, un inconvénient est qu’il nécessite plus de puissance de cal-cul(2 à 6 fois plus de calculs que JPEG), ce qui n’est pas un problème pourun PC, mais qui en est un pour un appareil aux ressources limitées commeles autres dispositif comme téléphone portable.

– L’autre inconvénient est que JPEG2000 n’est pas encore utilisé par assez

35



de constructeurs. Adobe en n’inclut pas de base le support de JPEG2000dans photoshop 7 a d’ailleurs contribué à ralentir l’adoption de ce nouveaustandard par l’industrie.

– Par rapport la norme JPEG, la norme JPEG-2000 est vraiment meilleure siavec l’image de taux de compression inférieur à 0.02. On a déjà vu dans lechapitre précédent.

Alors, la norme JPEG2000 jusqu’à maintenant, n’est pas populaire commeJPEG dans le monde entier. Pour remplacer la norme JPEG, je pense qu’il fautavoir de temps.

En faisant le TIPE, j’ai compris la théorie d’ondelette et la théorie de compres-sion d’image. Mais ce qui est le plus important c’est que j’ai appris la méthodo-logie de recherche avec un esprit critique et la façon de travail sérieux de niveauMaster en Informatique avec ce sujet.

36



Bibliographie

[1] Manuel de Matlab - Wavelet Toolbox

[2] Lucas QUARTA -Une introduction (élémentaire) à la théorie des ondelettes

- 22 novembre 2001

[3] Titus ZAHARIA Transformée en ondelettes pour la compression d’images

5 mars 2003

[4] M. W. Marcellin, M. Gormish, A. Bilgin, M. P. Boliek, -"An Overview of JPEG2000"- Proc. of the Data Compression Conference, Snowbird, Utah,March 2000, pp. 523-544.

[5] Michael D. Adams -The JPEG-2000 Still Image Compression Standard - 25-decembre 2002

[6] Jin Li -a Image Compression - the Mechanics of the JPEG 2000 25-octobre2002

[7] Ph. Ravier - L’enseignement des ondelettes : une ouverture sur l’industrie

par la norme JPEG2000 2-septembre 2001

[8] ISO/IEC JTC1/SC29/WG1/N1646R, JPEG 2000 Part I Final CommitteeDraft Version 1.0, Mar. 2000, http ://www.jpeg.org/public/fcd15444-1.pdf

[9] A. Skodras, C. Christopulos, T. Ebrahimi, The JPEG 2000 Still Image Com-

pression Standard, IEEE Signal Processing Magazine, pp. 36-60, September2001

37

Documents

tipe-luong_hong_viet_3