spirale de couleur J’ai le plaisir de vous proposer ici une page sur le fonctionnement de l’algorithme JPEG, le format d’image bien connu.

La page a entièrement été rédigée par Clément Masson, qui a dû faire une sorte de « micro-thèse » sur le format JPEG pour valider ses études (math spé). Cette page en est une version simplifiée, plus accessible.

Voilà !

image de Marcello

29 commentaires

gravatar
galex-713 a dit :

Youpi ! Mais sebsauvage avait pas déjà fait lui aussi un résumé de résumé de résumé ?

Prochaine étape : Vorbis (et Speex pourquoi pas, voir Opus) ! Et pourquoi pas des codecs vidéo aussi ?

gravatar
Sylvhem a dit :

Je viens de le lire. Cet article est vraiment très clair, bravo à son auteur ! Je ne savais absolument pas comment ça fonctionnait et j'ai quasiment tout compris :). Un grand merci pour l'explication de l'algorithme de Huffman d'ailleurs. Je me demandais depuis longtemps comment on faisait pour reconnaître des caractères dans une chaîne binaire. C'est tellement simple et logique !
Une petite question cependant. Comment choisit-on les valeurs de la matrice de quantification ?

J'ai quelques petites remarques d'ordre orthotypographique.
Premièrement, la phrase « On y trouve aussi des cônes, qui sont plus à la luminosité du rayon lumineux, et moins à sa couleur. » n'a pas de sens en l'état. Je suppose que tu voulais dire « On y trouve aussi des cônes, qui sont plus sensibles à la luminosité du rayon lumineux, et moins à sa couleur. »
Deuxièmement, la proposition « (normalement il n'y a pas d'espaces, ici ils séparent les lettres) » est incorrecte vu que dans ton exemple 110 représente un espace. Il faut donc parler de caractère plutôt que de lettre.
C'était la minute grammar nazi :).

gravatar
Kenoris a dit :

Bonjour à tous, je suis l'auteur de l'article.

@galex-713 : Oui, Sebsauvage a fait un très bon article sur le JPEG mais j'ai voulu détailler un peu plus la partie mathématique sur la DCT et ajouter les étapes dont il ne parle pas. Je n'ai pas non plus écrit de formules ou de théorèmes mais je voulais présenter la compression d'une image du début à la fin. On pourrait affiner encore en parlant de la façon dont on implémente l'algorithme en pratique, mais c'est une toute autre histoire :p
J'ai parlé du JPEG parce que j'ai travaillé dessus l'année dernière, mais je ne connais strictement rien aux algorithmes de compression audio et vidéo. Je peux essayer de me renseigner sur leur fonctionnement mais ça risque de prendre du temps (et je n'ai pas forcément les connaissances pour les comprendre).

@Sylvhem : Merci beaucoup ! Pour répondre à ta question, on peut prendre les valeurs que l'on veut, en gardant à l'esprit que les valeurs en bas à droite de la matrice doivent être plus grandes que les valeurs en haut à gauche. De toute façon, un espace est réservé dans l'en-tête du fichier pour l'écrire. C'est sur ces valeurs que l'on joue lorsque l'on choisit la qualité lors de l'enregistrement d'un fichier en JPEG (avec GIMP par exemple). Plus la qualité requise est faible, plus les valeurs de la matrice de quantification sont grandes. En général, le coefficient sur la i-ème ligne et la j-ième colonne est donné par une formule du genre i+j+1, ce qui permet d'avoir les mêmes valeurs sur une diagonale (comme dans l'exemple).
Tu as tout à fait raison dans tes deux remarques ! (Timo, pourrais-tu corriger stp ?)

Si vous avez d'autres questions n'hésitez pas :)

gravatar
galex-713 a dit :

@Kenoris : Pour l’audio et la vidéo je sais pas non plus (moyen pour le mp3, grâce à sebsauvage). L’audio doit être un poil plus simple et la vidéo pas mal plus compliquée je pense… Sinon je viens de finir l’article, et même si j’avais déjà lu pas mal de touts ces trucs sur Wikipédia, c’était très clair et super bien expliqué ! ;)

gravatar
anon a dit :

Salut,
Un projet de fin d'étude? ce serait pas un TIPE par hasard?
Merci pour ce tuto clair

gravatar
doc75 a dit :

@Kenoris: Il me semble que dans le paragraphe "Sous-échantillonnage de la chrominance" la première série de tableau Cb est la copie de Y alors qu'il devrait être différent. De ce fait dans la seconde série, les moyennes pour Cb sont bizarres ;-)

gravatar
alz a dit :

Par contre l'ombrage sous le texte, ça fait peut être joli, mais sur tout un texte à lire, ça rends la lecture pénible..

gravatar
tester a dit :

belle compréhension du travail/intelligence d'autrui...une question ? bah que faire de + ?

gravatar
galex-713 a dit :

@tester : Les codecs audio et vidéo ! :p

L’algo de césure de TeX aussi tant qu’on y est : là c’est plus facile et je connais déjà, c’est expliqué dans le TeXbook et on le retrouve facilement ailleurs. Il est parfait, beau et efficace cet algo… Je vais finir par le faire je pense.

gravatar
tester a dit :

oki galex ;)
En gros c'est bien de comprendre les logiciels/algo qu'on utilise même si ça n'aide en rien à leur amélioration car ça permet d'exploiter leurs mécanismes le cas échéant..j'ai right ?

:)

gravatar
Seb a dit :

merci pour ce super article !
Une petite remarque, le début du paragraphe sur YCbCr me parait bizarre. En effet il commence par "Mais l’œil ne contient pas que des bâtonnets." bâtonnets ? mais on a jamais parlé de bâtonnets jusqu'à maintenant, uniquement des cônes.

gravatar
pumbaa a dit :

Bravo pour cet article, il est clair et agréable à lire.

gravatar
tester a dit :

>merci pour ce super article !

Sans turlute ça ne vaut rien...

gravatar
galex-713 a dit :

@tester : Ouais entre autres… C’est aussi sympa de savoir comment ça fonctionne ^^ par curiosité, pour virer le coté « magique », parce que c’est beau, pour faire-son-intéressant-qui-parle-de-trucs-intéressants, etc.

Après pour l’algo de TeX par exemple c’est aussi un bon moyen de populariser un peu le logiciel libre avec un « Mhh… c’est du LibreOffice ça non ? non du Word ? Putain… Non mais parce que la césure est juste dégueulasse là, ça brûle les yeux… C’est quoi ces blancs là ! Et ces mots trop serrés là ! Et ces deux lignes sont adjacentes en plus et ça souligne encore plus la dégueulassité de ton document ! Puis ya 3000 césures au milieu de mots là c’est plus lisible… et la césure peut pas être faite correctement ? Bon je vais t’expliquer comment ça marche avec un logiciel libre presque cinquantenaire de-la-mort-qui-tue que touts les vrais pro utilisent partout dans le monde, des équations et des algorithmes, tu vas voir ça déchire la race de sa grand-mère le logiciel libre des fois ».
Puis bon c’est le genre d’algo génial qui mériterait d’être implémenté partout, partout, partout, absolument partout ! Et surtout dans Firefox !

PS : avec Blogotext on peut pas mettre de balises dans le texte d’une balise de lien ? WTF le parser…

gravatar
tester a dit :

c'est sûr...quitte à chercher des petits chinois, autant taper dans le rayon "étudiant français" hein ? Pas cher, serviable, crédule et omnibulé/angoissé par leur future réussite...quoi de mieux pour satisfaire les salopes de hyennes avides de chaires fraiches à cout 0 hein ?

Fuck l'exploitation.

gravatar
tester a dit :

Tu veux du Tex l'ami ? QUEL EST TON PRIX !

gravatar
Guenhwyvar a dit :

Hmm, eh bah c'est peut-être une version simplifiée, mais j'ai quand même plus rien compris à partir des cosinus… :x

gravatar
Grob a dit :

OK, alors moi aussi je suis en maths spé et moi aussi j'ai fait un TIPE sur le JPEG... \o/ (serais-ce mon binôme de TIPE ? :D)


Quelques commentaires comme ça :

Quand tu parles de cosinus, tu nous sort que des sinus dans tes courbes... :/

@Seb a raison, dans le paragraphe sur les batonnets, tous les mots "cônes" et "batonnets" ont été inversés

De mémoire avant d'appliquer l'algorithme Huffman il est appliqué un algorithme RLE (où globalement "00000000001110000000" devient "10*0+3*1+7*0", pour simplifier).

Sinon très bon article, j'aime beaucoup. Lors de l'explication sur la DCT je trouve qu'il est un peu mis de côté la différence discret/continu et que du coup on a de quoi s'y perdre. Tout le reste est très bien expliqué et très clair, je pense que j'en aurais pris exemple pour mon exposé de TIPE si j'avais pu :D

gravatar
Kenoris a dit :

@anon : Oui, c'était un TIPE.


@Seb : Anéfé. Je devais pas être très réveillé quand je me suis relu.




@Grob : J'ai fait mon TIPE tout seul, c'est pas moi !
Effectivement dans l'exemple de la fonction créneau la décomposition en série de Fourier ne fait apparaitre que des sinus, mais l'idée est là :p
J'en ai parlé juste avant le paragraphe sur Huffman, sans en donner le nom.
Oui, j'ai préféré ne pas en parler, tout simplement parce que j'ai pas bien compris pourquoi on a le droit de faire une transformée de Fourier sur un ensemble discret (y'a une justification mais c'est au-dessus de mes compétences).

gravatar
Grob' a dit :

@Kenoris : Oui Timo donne ton nom en haut de cette page et... c'est pas ceui de mon binôme (qui soit dit-en passant m'a fait découvrir ce blog)

Dans le beau monde du continu, tu as du voir que toute fonction continue sur un segment peut être approché par une suite de fonction polynômiales (théorème de Weierstrass)

Tu as du voir aussi qu'une fonction définie sur un segment (ou périodique de période la longueur de ce segment, au fond c'est pareil), peut être approché par une suite de polynomes trigonomériques (avec toute la théorie de Fourier qui permet en plus d'en donner des formules).

Au fond, donc, les polynômes et les polynômes trigonométriques ont pas mal de points communs.


Maintenant, si on passe dans le monde discret, il est possible d'interpoler un nombre de fini de n +1 points par un polynôme (normal) de degré n (voir la technique de Lagrange que tu as du voir cette année et/ou l'année dernière), on peut même en donner une formule.

Eh bien il en est de même avec des polynômes trigonométriques, et la formule de la transformée de Fourier discrète n'est que la formule qui te permet de donner les fonctions qui interpolent tes points.


Après le fait qu'on soit dans le monde du discret simplifie pas mal de choses : en soi il n'y a rien qui empêche de faire une bête interpolation, là où il y a pas mal de galères dans le continu pour approcher des fonctions (avec toutes ces histoires de droit de le faire ou pas).


'fin je te dis ça du point de vue où j'ai cru le comprendre, je ne dit pas avoir la science infuse dans le domaine :)

En fait ce qui me gênais c'est que t'expliques assez vite fait ce qu'est une transformée de Fourier continue puis tu dis que c'est comme ça qu'on fait en discret (alors qu'au fond discret et continu 'est pas non plus la même chose).

Bref ça simplifierais je pense si dans tes schémas tu prenais des points et tu disais qu'on peut trouver une somme de cosinus qui passe par ces points, en la représentant, au lieu d'approximer des fonctions ce qui n'as pas tant à voir que ça je trouve.

gravatar
Limule a dit :

Il n’est pas trop mal cet article, mais il manque tout de même pas mal de choses :
- le sous-échantillonnage chroma peut porter sur des surfaces plus étendues (jusqu'à 4x4)
- curieusement il montre des valeurs entières dans ses tables YCbCr alors que la transformation RVB vers YCbCr produit des réels
- la FDCT est en fait appliquée sur des données recentrées autour de zéro (level shift)
- on ne peut techniquement plus parler de « pixels » pour les carrés de 8x8 surtout après un sous-échantillonnage
- on utilise généralement des tables de quantifications distinctes pour Y et CbCr
- il n’y aucune distinction de faite entre les coefficients DC et AC (seul la différence par rapport au précédent coefficient DC est encodée)
- le zigzag n’est parcouru en entier que dans le cas d’un JPEG séquentiel pour un JPEG progressif il est découpé en bandes spectrales
- on peut utiliser une variante du codage arithmétique à la place du codage de Huffman, c’est d’ailleurs plus efficace

Pour voir ce qu'il se passe lorsque les dimensions de l’image ne sont pas des multiples de 8 (ou 16… selon sous échantillonnage) il y a cette vidéo en français :
http://www.youtube.com/watch?v=V7LvgXqsh60

Pour plus d‘informations sur les JPEG progressifs il y a quelques données de fond et des exemples ici :
http://encode.ru/threads/1800-JSK-JPEG-Scan-Killer-progressive-JPEG-explained-in-slowmo

Les commentaires sont fermés pour cet article