Ouvrir le menu principal

Le format JPEG 2000

Différence entre le JPEG et le JPEG 2000 pour un fichier de même taille.

Sections

AperçuModifier

Le format JPEG figure en tête du hit-parade des formats d'images, accompagné par l'équivalent non destructif, le PNG. Malgré sa grande popularité, il n'est pas exempt de défauts et les spécialistes se sont penchés sur ses problèmes pour concevoir son successeur : le JPEG 2000. Cet article devrait vous permettre de mieux cerner les algorithmes utilisés par ce format récent. Il doit encore s'imposer sur le web grâce aux navigateurs populaires qui ne l'intègrent pas encore. L'utilisation par le grand public reste donc marginale malgré un nombre croissant d'applications qui permettent de travailler avec ce format.

IntroductionModifier

Le comité Joint Photographic Experts Group (JPEG) fut créé en 1986 ; cet organisme de standardisation avait pour but de définir diverses spécifications concernant les images et les applications graphiques. C'est à lui que revint la lourde tâche de trouver un format adéquat pour la transmission d'images. Des travaux à ce sujet avaient toutefois débuté auparavant et la création de ce comité assura la coopération entre différents groupes de spécialistes. Le format JPEG (.jpg) correspond en fait au JFIF (JPEG File Interchange Format). Pour simplifier, nous utiliserons le terme JPEG pour le format .jpg que nous connaissons tous.

D'autres formats portent le label du comité JPEG et le dernier en date est le JPEG 2000, l'extension standard qui lui est attribuée est le .jp2. La norme du JPEG 2000 comporte douze parties.

Les différentes parties du standard JPEG 2000Modifier

Certaines parties ne sont toujours pas publiées (pour plus d'informations, consulter http://www.jpeg.org/jpeg2000). D'autres encore en sont toujours à un stade de recherche (partie 10).

  1. Encodage / décodage, description du format .jp2 (présence de brevets)
  2. Extensions / métadonnées
  3. Motion Jpeg 2000 (une succession d'images de type .jp2 pour former une vidéo)
  4. Tests et procédures pour assurer la conformité avec le format
  5. Implémentations de référence (JJ2000 et Jasper)
  6. Format JPM (format "compound" pour intégrer du texte, des images, ...)
  7. Spécifications pour appareils à puissance limitée (partie abandonnée et non publiée)
  8. Sécurité, intégrité, authenticité et cryptage (JPSEC)
  9. Protocole client-serveur JPIP (utilisation du format dans un réseau)
  10. JP3D, extension pour des données basées sur des voxels (images en 3D)
  11. JPWL (Jpeg Wireless), transmission et correction d'erreurs
  12. ISO Base Media File Format (architecture basée sur le QuickTime)

Les problèmes liés au JPEGModifier

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 mosaïque quand les taux de compression deviennent importants (voir l'article Compression JPEG).

L'image est en effet segmentée en blocs de 8x8 pixels sur lesquels est appliquée une série de transformations dont la DCT (discrete cosine transform ou transformée en cosinus discrète). Une image étant composée d'une superposition de 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 d'"effet de bloc".

 
Phénomène de Gibbs avec des oscillations sur les flancs montants et descendants

Le signal reconstruit à partir d'une 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 (phénomène de Gibbs) qui rend difficile la représentation d'un signal carré avec une somme de sinusoïdes.

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 PNG, le GIF ou même l'ancestral 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 ondelettes (wavelets). Sous ce terme se cache en fait une théorie mathématique utilisée pour le traitement des signaux (sismologie, acoustique, 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 œuvre si l'on reprend les principes qui ont fait le succès du MPEG (estimation du mouvement, frames intermédiaires calculées à partir de frames complètes). Avant l'arrivée du DivX, plusieurs codecs vidé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 Theora de la fondation Xiph. Celle-ci est plus connue pour son projet 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, WMV, RealVideo, 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 brevets concernant les ondelettes freinent la recherche et réduisent la marge de manœuvre des spécialistes. Le comité JPEG a d'ailleurs dû 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 Firefox et même 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 FourierModifier

Il existe plusieurs moyens pour analyser un signal. La plus connue est la transformée de Fourier et sa version optimisée, la 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 sinus et 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 retrouver le signal original (certaines contraintes sur la nature du signal doivent être remplies). Le principal défaut de cette méthode 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 pour les images.

Du STFT vers les ondelettesModifier

 
Exemple de STFT sur un signal sonore. La fenêtre a une durée de 125 ms, on voit clairement les cassures dans le spectre lors du passage entre les fenêtres.

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 disposera 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 (incertitude d'Heisenberg).

Une autre grande différence entre les ondelettes et la famille Fourier est l'utilisation de fonctions autres que sinusoïdales. Le terme d'ondelette se réfère en fait à la fonction 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.

 
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 manquerons 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 : Lifting en ondelettes

Décomposition selon la base de HaarModifier

 
Décomposition du signal en une série de coefficients

En 1909, Alfred Haar propose ce que l'on considère comme la première ondelette même si ce terme apparaît bien plus tard. L'ondelette de Haar est la plus simple à comprendre et à implémenter.

Prenons un signal S comportant 4 valeurs :  . Nous pouvons appliquer une première décomposition en isolant les éléments deux par deux et en calculant leur moyenne. Avec notre signal, nous trouvons :   et  . Nous avons ainsi réduit la résolution du signal original, cette moyenne agit en fait comme un filtre passe-bas, le signal se retrouve lissé.

Comment retrouver les détails ? Il suffit de regarder la différence entre les moyennes obtenues et les valeurs originales du signal. Le premier couple d'éléments (1,23) a une moyenne de 12. La différence entre 1 et 12 est de -11, entre 12 et 23, elle se monte à 11. Bien entendu, les différences sont simplement opposées et il n'est pas nécessaire de conserver les deux valeurs car l'une est négative, l'autre positive, on ne conserve ainsi que la première valeur. En répétant cette opération avec le deuxième couple (9,5), nous obtenons une différence de  . Il ne nous reste plus qu'à créer un nouveau signal commençant avec les moyennes suivies par les différences :  , il est essentiel ici de conserver le signe des coefficients.

 
Reconstruction du signal à partir des coefficients

Pour retrouver le signal original, il suffit de prendre un coefficient représentant une moyenne et d'y ajouter/soustraire la différence respective. Dans le cas de notre signal, nous prenons la moyenne qui vaut 12, nous y ajoutons son coefficient de détail qui vaut -11 pour obtenir la première valeur du signal initial :  . Nous soustrayons ce même coefficient pour obtenir la deuxième valeur du signal :  .

Quel est l'intérêt 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  , nous obtenons  . 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  . 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). À partir de S1, nous prenons   et trouvons la moyenne suivante :  . Le coefficient de détail pour cette partie correspond à  . Nous remplaçons les termes présents dans la partie gauche de S1 par ceux que nous venons de calculer. Nous obtenons ainsi   constitué d'un coefficient d'approximation et de 3 coefficients de détails. Nous ne pouvons pas décomposer davantage 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 :   et  . Nous avons bien  . En appliquant la transformation pour passer de S1 à S comme décrit précédemment, nous retrouvons 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.

La transformation de Haar sur une imageModifier

 
À gauche, une transformation rectangulaire. À droite, une transformation carrée ou dyadique.

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. À 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 permet d'isoler plus facilement les niveaux de détails.

Les ondelettes du Jpeg2000Modifier

 
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, Ingrid Daubechies, qui dès le début des années 1980 s'est activement consacrée à 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 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.

Étapes de la compression du JPEG 2000Modifier

 
Résultat de la quantification avec une transformée de Haar. L'image est dégradée, mais le signal reste relativement fidèle à l'original malgré la perte de coefficients.

Préparation de l'image et découpage en tuilesModifier

Avant d'appliquer une décomposition par ondelettes sur l'image, il faut la préparer pour cette opération. La première étape consiste à faire en sorte que l'image possède des dimensions correctes, les filtres ne peuvent pas travailler sur des longueurs quelconques. Les pixels supplémentaires peuvent être ajoutés en recopiant les pixels déjà existants.

On peut ensuite convertir l'image de l'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'œil humain est très sensible aux changements d'intensité lumineuse. En revanche, 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 YCbCr et du 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 pertes possible. Les plans Cb et Cr peuvent en revanche 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-é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.).

QuantificationModifier

Après une transformation avec des ondelettes, nous nous retrouvons avec un tableau de tuiles et des coefficients pour plusieurs niveaux de détails dans chaque tuile. Pour le choix des coefficients et l'élaboration d'un algorithme de quantification, on fait normalement appel aux études psychovisuelles qui permettent de mieux estimer les limites de la vision. On sait que, lors de la restitution d'une image, les hautes fréquences sont moins importantes que les basses fréquences. Dans le cas du JPEG 2000, plusieurs méthodes ont été envisagées, mais seule la quantification linéaire a été retenue, c'est aussi la plus simple et la plus rapide car elle revient à diviser les coefficients par une constante et à arrondir le résultat. Dans le cas d'une compression sans perte, aucune quantification n'est appliquée. Le JPEG 2000 supporte un autre mode de compression avec des tuiles non quantifiées. C'est au moment de réaliser le flux de données que certains coefficients seront tout simplement éliminés. On attribue une priorité selon le niveau de détails, les coefficients correspondant aux hautes fréquences auront une importance plus faible que ceux des basses fréquences. Lors de l'écriture du fichier, on donne une taille à ne pas dépasser et les données sont sauvées selon leur importance jusqu'à atteindre le quota alloué.

Compression et codage arithmétiqueModifier

 
Résumé des étapes de la création d'un fichier JPEG 2000

Pour chaque tuile, nous possédons plusieurs bandes quantifiées qui correspondent à des fréquences différentes. Les bandes sont à leur tour subdivisées en sous-blocs rectangulaires. Ceux-ci vont être encodés, compressés grâce à un codage arithmétique et sauvés dans le fichier. Pour coder un bloc, on travaille avec des plans de bits. Le premier plan significatif (présence d'un '1') voit son index stocké dans une entête qui précède le flux de bits.

L'encodage dans le JPEG 2000 se voit complexifié par l'ajout de trois traitements successifs qui suivent le principe du schéma EBCOT (Embedded Bitplane Coding by Truncation). Chaque bit provenant d'un plan de bits sera écrit par l'une de ces trois opérations (significance propagation, magnitude propagation et cleanup pass). Ces étapes permettent d'attribuer plus ou moins d'importance à un bit selon son contexte (les bits des coefficients qui l'entourent). Des travaux concernant l'ajout de codes correcteurs (dont les codes de Reed-Solomon [1]) ont été menés, mais n'ont pas été intégrés à la version de base du Jpeg. Ils pourraient toutefois apparaître dans les spécifications du JPWL (JPEG 2000 Wireless), un format défini dans la partie 11 du standard.

On obtient au final un flux de bits que l'on peut sauver sur le disque avec les entêtes, des métadonnées et un support compatible avec les profils ICC. Ces spécificités sont nouvelles par rapport au JPEG qui proposait un début de solution grâce à la norme EXIF.

ConclusionModifier

Le Jpeg2000 est un standard complexe. Il est de ce fait impossible d'examiner toutes ses propriétés en quelques pages, mais nous espérons que cet article vous aura permis de mieux comprendre son fonctionnement. Il existe plusieurs implémentations libres qui peuvent être incorporées dans vos projets. Citons par exemple JasPer (http://www.ece.uvic.ca/~mdadams/jasper/) ou l'implémentation Java du Jpeg2000 (http://jpeg2000.epfl.ch/). Vous pouvez également manipuler le Jpeg2000 avec ImageMagick (http://www.imagemagick.org/). Nous ne pouvons qu'espérer que sa diffusion soit plus large et qu'il soit rapidement intégré au sein des logiciels phares du monde libre comme The Gimp ou encore Firefox.

NotesModifier

  1. http://perso-etis.ensea.fr/~poulliat/research/publications/CENov03.pdf#search=%22jpeg2000%20reed%22
À propos de ce document

Article initialement paru dans le défunt magazine LOGIN. L'auteur, Kévin Drapel, cède le contenu de l'article sous la licence GFDL.