« Compression de données/Le format JPEG 2000 » : différence entre les versions

diverses 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. Un des problèmes les plus connus du JPEG est l'apparition d'un effet de mosaiquemosaïque quand les taux de compression deviennent importants (voir l'article [[:w:Compression JPEG|Compression JPEG]]).
 
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 sinusoidalessinusoïdales.
 
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'ancestraleancestral [[:w:PCX|PCX]]. D'autres transformations et conversions sont appliquées sur les blocs pour améliorer la compression, elles sont à l'origine d'une série de dégradations comme la désaturation exagérée des couleurs.
 
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 qui est utilisée pour le traitement des signaux ([[:w:sismologie|sismologie]], [[:w:acoustique|acoustique]], [[:w:physique|physique]],...). Les recherches étant plutôt actives dans ce domaine depuis une vingtaine d'années, les méthodes de compression se sont peu à peu améliorées et on pouvait espérer dépasser les taux de compression offerts par le JPEG. C'est du moins ce que l'on peut affirmer en ce qui concerne les images. Le cas de la vidéo est plus problématique, les ondelettes sont difficiles à mettre en oeuvreœuvre si l'on reprend les principes qui ont fait le succès du [[:w:Moving Picture Experts Group|MPEG]] (estimation du mouvement, frames intermédiaires calculées à partir de frames complètes). Avant l'arrivée du [[:w:DivX|DivX]], plusieurs ''codecs'' vidéosvidéo basés sur des ondelettes offraient des taux compétitifs. On peut notamment citer le codec Indeo 5 d'Intel, VDOWave ou encore Tarkin qui a été stoppé au profit du codec [[:w:Theora|Theora]] de la [[:w:Xiph.org|fondation Xiph]]. Celle-ci est plus connue pour son projet [[:w:Ogg|Ogg Vorbis]]. La disparition assez rapide de ces formats n'est pas totalement anodine et montre bien qu'il y a encore du travail à fournir. Les codecs les plus populaires (XviD, DivX, [[:w:Windows Media Video|WMV]], [[:w:RealVideo|RealVideo]], [[:w:Quicktime|Quicktime]]) sont tous dérivés du MPEG et donc du lointain cousin qu'est le JPEG.
 
Il faut encore noter que, sans grande surprise, plusieurs patentes concernant les ondelettes freinent la recherche et réduisent la marge de manoeuvremanœuvre des spécialistes. Le comité JPEG a d'ailleurs du signer plusieurs accords avec différentes entreprises (Ricoh, Luratech). Cette question n'a pas encore été complètement élucidée puisque le format est absent des navigateurs comme [[:w:Firefox|Firefox]] et même [[:w:Internet Explorer|Internet Explorer]], ; les raisons invoquées sont d'ordre juridique mais elles pénalisent très fortement la diffusion du format chez le grand public.
 
== 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 obtenirretrouver le signal original (certaines contraintes sur la nature du signal doivent être remplies). Le principal défaut de cette méthode, c'est qu'elle ne permet pas de dire à quel moment une fréquence apparaît, on sait tout au plus qu'une fréquence précise est présente dans le signal original. Le spectre ne capture par les modifications locales. On peut ainsi avoir deux spectres similaires qui ne correspondent pas du tout au même signal. Pour corriger en partie ce problème, on peut découper le signal en petits morceaux (fenêtres). Malheureusement, cette technique n'est pas très flexible et selon le type de signal à analyser, il est difficile d'établir la longueur optimale pour une fenêtre. Cette technique que l'on appelle ''Short Time Fourier Transform'' (STFT) n'est donc pas la panacée universelle pour les images.
 
== 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 disposedisposera de plus d'informations sur le signal et l'appréciation de la fréquence sera améliorée au détriment de la résolution dans le temps. Ces problèmes sont inhérents à la définition d'un signal et on ne peut pas totalement les éviter ([[:w:Principe d'incertitude|incertitude d'Heisenberg]]).
 
Une autre grande différence entre les ondelettes et la famille Fourier est l'utilisation d'autresde fonctions queautres desque sinusoidalessinusoïdales. Le terme d'ondelette se réfère en fait à la fonction qui est utilisée pour décomposer le signal. Dans le cas du Fourier, l'ondelette est un sinus. Le JPEG2000 utilise une ondelette de type Daubechies, nous y reviendrons plus tard.
 
[[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 manquerontmanquerons certains échantillons. Au contraire, un zoom plus faible nous permettra d'examiner des zones plus grandes (basse fréquence = grosse particule) et nous pourrons avancer de quelques centimètres à chaque étape. C'est exactement ce principe qui est utilisé pour analyser le signal. Pour les basses fréquences, nous utiliserons une grande échelle. Pour les hautes fréquences, l'échelle sera petite. Pour résumer, l'échelle est inversement proportionnelle aux fréquences considérées et correspond au déplacement autorisé pour le microscope. Pour revenir à la notion d'incertitude, si notre particule est très petite, nous pourrons déduire avec précision son emplacement sur notre table. Par contre, si elle s'étale sur une grande surface, nous ne pourrons pas lui donner une position précise, tout au plus une approximation.
 
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.,5</math>. Le coefficient de détail pour cette partie correspond à <math>(12-9.,5) = 2.,5</math>. Nous remplaçons les termes présents dans la partie gauche de S1 par ceux que nous venons de calculer. OnNous obtientobtenons ainsi <math>S2 = [9.,5, 2.,5, -11, 2]</math> constitué d'un coefficient d'approximation et de 3 coefficients de détails. Nous ne pouvons pas décomposer plus en avantdavantage la partie basse fréquence car elle se réduit maintenant à un seul terme.
 
Tentons une reconstitution du signal S depuis S2. Nous commençons à partir du coefficient d'approximation qui vaut 9.,5. Grâce aux informations de détails qui suivent ce coefficient, nous pouvons aisément retrouver les éléments de S1 : <math>(9.,5+2.,5)</math> et <math>(9.,5-2.,5)</math>. Nous avons bien <math>[12, 7]</math>. En appliquant la transformation pour passer de S1 à S comme décrit précédemment, onnous retrouveretrouvons le signal sans dégradation.
 
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 permerpermet d'isoler plus facilement les niveaux de détails.
 
== 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 impliquéeconsacrée dansà ce domaine. Les résultats de ses recherches ont été utilisés, mis à part le Jpeg2000, pour le système de stockage des empreintes digitales du [[:w:Federal Bureau of Investigation|FBI]]. Une méthode fut spécialement développée pour tenir compte des caractéristiques des empreintes.
 
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. ParEn contrerevanche, les changements de teintes ont moins d'impact sur la vision, deux teintes très proches peuvent être remplacées par la même valeur. Le RVB (rouge, vert, bleu) n'est pas du tout adapté car il ne sépare pas la luminosité et les composantes chromatiques. Les espaces qui permettent ces manipulations sont le YCbCr (pour la compression avec perte) et le YUV (compression sans perte). Dans la terminologie du JPEG 2000, on parle de ICT ou RCT (''irreversible/reversible component transformation''), ces deux espaces sont des approximations du [[:w:YCbCr|YCbCr]] et du [[:w:YUV|YUV]]. Grâce à une telle transformation, on obtient trois plans. Le Y correspond à un canal de lumière (on pourrait l'assimiler à la version en niveaux de gris de l'image) alors que le Cb et Cr sont dédiés à la couleur. Le Y est le plus significatif et doit subir le moins de pertepertes possible. Les plans Cb et Cr peuvent paren contrerevanche subir des dégradations plus poussées.
 
Un algorithme utilisé également dans le JPEG consiste à réduire la taille des plans d'images grâce à un sous-échantillonageéchantillonnage (''subsampling'' ou décimation). Par exemple, si notre image fait 320x200, le plan Y fera 320x200 pixels alors que les plans Cb et Cr feront 160x100 pixels (rapport de type 4:2:0). Lors de la reconstitution de l'image, on agrandit les plans pour que les tailles correspondent. Dans le JPEG standard, on utilise un rapport 4:2:2 qui signifie que pour 4 blocs provenant d'un plan Y, on aura 2 blocs horizontaux pour Cb et 2 blocs horizontaux pour Cr. On rencontre parfois des rapports 4:2:0, cette description correspond à 4 blocs Y accompagnés d'un bloc pour Cb et un autre bloc pour Cr (on réduit la taille du plan par un facteur de deux horizontalement et ensuite verticalement).
 
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. ).