« Compression de données/Le format JPEG 2000 » : différence entre les versions
Compression de données/Le format JPEG 2000 (modifier)
Version du 4 septembre 2006 à 23:18
, il y a 17 ansdiverses petites corrections
Contenu supprimé Contenu ajouté
→Introduction : petites corrections |
diverses petites corrections |
||
Ligne 29 :
== Les problèmes liés au JPEG ==
Pour pallier les défauts inhérents au format JPEG, les chercheurs se sont penchés ces dernières années sur un nouveau standard pour la compression d'images.
L'image est en effet segmentée en blocs de 8x8 [[:w:pixel|pixels]] sur lesquels est appliquée une série de transformations dont la [[:w:Transformée en cosinus discrète|DCT]] (''discrete cosine transform'' ou transformée en cosinus discrète). Une image étant composée d'une superposition de [[:w:Signal sinusoïdal|signaux sinusoidaux]] sur deux dimensions et d'une composante continue, cette étape fournit un spectre des fréquences présentes dans le bloc. On peut ainsi facilement éliminer les fréquences "inutiles". En écartant un trop grand nombre de fréquences, on privilégie la composante continue (la moyenne du bloc) et les pixels ne présentent plus que quelques variations, on parle alors de "blocking".
[[Image:Gibbs phenomenon 50.jpg|thumb|right|Phénomène de Gibbs avec des oscillations sur les flancs montants et descendants]]
Le signal reconstruit à partir d'une [[:w:Analyse spectrale|représentation spectrale]] n'est jamais parfait et des oscillations parasites s'accumulent à ses extrémités. Il s'agit de l'effet de ''ringing'' ([[:w:Série de Fourier#Phénomène de Gibbs|phénomène de Gibbs]]) qui rend difficile la représentation d'un signal carré avec une somme de
Ceci est particulièrement frappant avec les images qui présentent des zones délimitées de façon nette (texte, "cliparts"), domaine dans lequel il est un piètre candidat face aux formats non-destructifs comme le [[:w:Portable Network Graphics|PNG]], le [[:w:Graphics Interchange Format|GIF]] ou même l'
Le JPEG 2000 utilise une autre approche basée sur les [[:w:Compression par ondelettes|ondelettes]] (''wavelets''). Sous ce terme se cache en fait une théorie mathématique
Il faut encore noter que, sans grande surprise, plusieurs patentes concernant les ondelettes freinent la recherche et réduisent la marge de
== La transformée de Fourier ==
Ligne 46 :
Il existe plusieurs moyens pour analyser un signal. La plus connue est la [[:w:Transformée de Fourier|transformée de Fourier]] et sa version optimisée, la [[:w:Transformée de Fourier rapide|transformée de Fourier rapide]] (FFT). La DCT que nous avons évoquée précédemment est assez similaire.
Cette transformation permet de décomposer un signal en un ensemble de [[:w:sinus|sinus]] et [[:w:cosinus|cosinus]] avec des amplitudes et des fréquences différentes, on obtient alors une représentation sous forme spectrale (domaine fréquentiel). En additionnant les ondes provenant du spectre, on peut en théorie
== Du STFT vers les ondelettes ==
Ligne 52 :
En améliorant le concept de découpage du signal déjà présent dans la STFT, les ondelettes offrent une alternative séduisante. Contrairement au STFT, les ondelettes permettent de travailler avec des segments de tailles différentes, on parle alors plutôt d'échelle. En variant l'échelle utilisée pour analyser le signal, on pourra se concentrer sur une bande bien précise de fréquences. Ce type d'analyse propose un compromis entre la précision temporelle et fréquentielle.
Par exemple, une haute fréquence pourra facilement être localisée dans le temps mais il sera difficile d'établir sa fréquence exacte. Avec un signal basse fréquence, c'est exactement l'inverse. Nous pourrons déterminer avec une assez grande précision la valeur de la fréquence mais nous ne pourrons pas très bien la situer dans le temps. Ceci est assez logique, un signal à haute fréquence effectue une période sur un laps de temps très court. On peut ainsi facilement détecter un "pic" mais comme sa longueur est limitée, la précision pour résoudre la fréquence est faible. Une basse fréquence s'étalera sur une plus longue période. Comme la fenêtre considérée est plus longue, on
Une autre grande différence entre les ondelettes et la famille Fourier est l'utilisation
[[Image:Signal bruit et fourier.png|thumb|right|Transformée de Fourier sur plusieurs types de signaux]]
Les ondelettes sont calculées à partir d'une fonction initiale appelée "fonction mère" ou "ondelette mère". En contractant et transposant la fonction mère, on génère des fonctions "filles" dont la forme varie selon la résolution désirée. La transposition permet de se déplacer dans le temps tandis que la contraction permet de passer d'une échelle à une autre. On pourrait comparer ceci à un microscope qui devrait analyser des échantillons posés sur une table, le microscope fait office d'ondelette mère. En le déplaçant sur la table, nous effectuons une transposition. En modifiant l'agrandissement, nous agissons sur un paramètre similaire à la contraction. Si l'agrandissement est très grand (haute fréquence = petite particule), nous ne pourrons déplacer le microscope que de quelques millimètres à chaque fois sinon nous
Pour en savoir plus : [[:w:Lifting en ondelettes|Lifting en ondelettes]]
Ligne 76 :
Quel est l'intéret d'une telle transformation ? Un signal transformé se compressera mieux que le signal brut, on parle de compression d'énergie. Les coefficients de détails ont souvent une magnitude inférieure aux échantillons du signal original. On a donc besoin de moins de bits pour coder ces informations et nous pouvons réduire leur précision. Si nous reconstruisons le signal comme nous l'avons fait précédemment à partir de <math>[12,7, -8, 0]</math>, nous obtenons <math>[4, 20, 7, 7]</math>. Le signal est dégradé mais encore fidèle à l'original.
Nous venons d'effectuer une première passe de l'algorithme. Nous allons maintenant affiner l'analyse en diminuant l'échelle. Nous reprenons la séquence issue de la première transformation, soit <math>S1 = [12, 7, -11, 2]</math>. Nous avons vu que la première partie correspond aux coefficients "basses fréquences" et la deuxième partie aux coefficients de détails. Nous allons maintenant appliquer l'algorithme récursivement sur la partie de gauche (basse fréquence). A partir de S1, nous prenons <math>[12, 7]</math> et trouvons la moyenne suivante : <math>(12+7)/2 = 9
Tentons une reconstitution du signal S depuis S2. Nous commençons à partir du coefficient d'approximation qui vaut 9
Il s'agit d'une transformation de Haar qui n'est pas normalisée. Pour améliorer la qualité et pour des critères mathématiques qui dépassent le cadre de cet article, on cherche à avoir des ondelettes normalisées. Avec une Haar normalisée, tous les coefficients sont divisés par racine de 2 au lieu de 2.
Ligne 86 :
Prenons une image de 64x64 pixels. Nous isolons les 64 lignes de l'image et appliquons une transformation de Haar complète sur chacune d'entre elles. Pour chaque ligne, le résultat est composé d'un coefficient d'approximation suivi de 63 coefficients de détails. Les lignes transformées sont assemblées pour former une nouvelle image et il s'ensuit une transformation de Haar verticale, cette fois-ci sur les colonnes. A la fin, le premier élément de la matrice en haut à gauche correspond au coefficient d'approximation pour toute l'image (l'intensité moyenne de l'image). Le reste de la matrice correspond aux coefficients de détails pour différentes échelles. On procède de la manière inverse pour reconstituer l'image avec une transformation inverse complète sur les colonnes suivie de la transformation inverse complète sur les lignes.
Cette transformation est dite "rectangulaire". Il existe un autre moyen, la transformation "carrée", on applique une seule étape sur les lignes suivie immédiatement par une étape sur les colonnes. On obtient ainsi quatre zones. On recommence de manière récursive sur la zone en haut à gauche. Pour le Jpeg2000, on utilise cette transformation "carrée" car elle demande moins de calculs et
== Les ondelettes du Jpeg2000 ==
[[Image:Daubechies4-functions.png|thumb|Ondelette de type Daubechies-4]]
La transformation de Haar n'est guère satisfaisante car elle fait apparaître des blocs après une quantification excessive et les taux de compression sont faibles. Tous ces problèmes sont surtout liés au fait que l'ondelette de Haar n'est pas continue. Pour améliorer cette situation, une autre famille d'ondelettes est employée : les ondelettes de Daubechies. On les doit à une mathématicienne belge, [[:w:Ingrid Daubechies|Ingrid Daubechies]], qui dès le début des années 80 s'est activement
Dans le Jpeg2000, une ondelette de type Daubechies 9/7 est utilisée pour la compression avec perte. Pour la compression sans perte, on utilise une LeGall 5/3. Les coefficients obtenus avec l'ondelette de LeGall sont rationnels, cette particularité est nécessaire pour assurer une reconstitution parfaite du signal original. Ces ondelettes n'ont pas été choisies au hasard, elles remplissent plusieurs critères mathématiques qui permettent d'obtenir de bons résultats sur les images. Il faut savoir que selon le type de signal à analyser, les ondelettes utilisées ne seront pas les mêmes. Nous avons vu que la décomposition de Haar agit comme une succession de filtres passe-haut / passe-bas basiques. Le filtrage avec une "9/7" revient à multiplier les valeurs provenant de l'échantillon avec les coefficients du filtre passe-bas (9 valeurs) et passe-haut (7 coefficients). On additionne les valeurs pour chaque banque de filtres et on obtient un coefficient de moyenne accompagné d'un coefficient de détail.
Ligne 101 :
On peut ensuite convertir l'image de l'[[:w:Rouge vert bleu|espace RVB]] (rouge, vert, bleu) vers un espace plus approprié pour la compression. Ce processus est optionnel selon la description du standard (et inutile dans le cas d'une image en niveaux de gris).
L'oeil humain est très sensible aux changements d'intensité lumineuse.
Un algorithme utilisé également dans le JPEG consiste à réduire la taille des plans d'images grâce à un sous-
L'étape suivante consiste à découper l'image en petits morceaux appelés ''tiles'' (tuiles). Outre la plus grande flexibilité, cette approche ouvre la porte à une parallélisation du processus (plusieurs tuiles pourraient être décodées en même temps) et une gestion de la mémoire plus fine pour les systèmes embarqués (appareils photos, caméras, etc. ).
|