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

aucun résumé des modifications
Contenu supprimé Contenu ajouté
création, mise en page, en cours
 
Aucun résumé des modifications
Ligne 33 :
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 sinusoidales.
 
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'ancestrale [[: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 JpegJPEG 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 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éos 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, Wmv[[: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 manoeuvre 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 ==
 
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 "transormée[[:w:Transformée de Fourier rapide"|transformée de Fourier rapide]] (FFT),. laLa DCT que nous avons évoquéé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 obtenir 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 ==
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 dispose 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'autres fonctions que des sinusoidales. 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.
 
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 manqueront 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]]
 
== Décomposition selon la base de Haar ==
En [[:w:1909|1909]], [[:w:Alfred Haar|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 : <math>S = [1, 23, 9, 5]</math>. 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 : <math>\frac{1+23}{2} = 12</math> et
<math>\frac{9+5}{2} = 7</math>. 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é.
 
Prenons un signal S comportant 4 valeurs : S = [1, 23, 9, 5]. 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 : (1+23)/2 = 12 et (9+5)/2 = 7. 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 <math>(9-7) = +2</math>. Il ne nous reste plus qu'à créer un nouveau signal commençant avec les moyennes suivies par les différences : <math>S1 = [12, 7, -11, 2]</math>, il est essentiel ici de conserver le signe 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 : <math>12 + (-11) = 1</math>. Nous soustrayons ce même coefficient pour obtenir la deuxième valeur du signal : <math>12 - (-11) = 23</math>.
 
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>\frac{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. On obtient 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 avant 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, on retrouve 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.
163

modifications