le D-JPEG (Differential JPEG), par Xavier COUDIN Informaticien en Freelance (gsm 06 81 19 18 92)
xavier.coudin@free.fr

--------------------------------------------

Une technique permettant d'essayer d'alléger au maximum la taille en octets d'une image, dans un contexte de renouvellement continu de ces images ou "comment faire tenir dans 3 à 5 Ko une image qui prendrait normalement 10-12 Ko ?"

-----------------------------------------------

Application principale : webcam.

Cette solution m'a été soufflée par Arnaud LAPREVOTE de la société "Free&ALter Soft". Que Dieu soit bénit jusqu'à la fin des temps de m'avoir fait rencontrer ce petit (mais ô combien grand) homme un jour de mars 1999.

Cette technique est applicable EXCLUSIVEMENT dans le cas d'une caméra (webcam) PARFAITEMENT fixe (ex: fixée à un mur ou un plafond). Elle n'est absolument pas adaptée à une caméra mobile.

Cette technique de compression repose sur la constatations suivante: lors d'une prise de vue réalisée avec une caméra parfaitement fixe, le changement dans les images ne concerne souvent que 15 à 20% de la surface de l'image. Dès lors 80 à 85% de l'image contient en permanence la même information. Retransmettre sans cesse la même information consomme beaucoup de bande passante inutilement. En théorie, il suffit de transmettre seulement le "différentiel", c'est à dire le changement intervenu, soit les 20% de surface.

Dès lors, en faisant un calcul simple: 20% de 12 Ko représente environ 2.4 Ko en condition optimale.

Ainsi on peut "théoriquement" transmettre 2 images successives qui ont une taille d'environ 12 Ko chacune et ne comptant que 20% de changement l'une par rapport à l'autre en consommant finalement 12 Ko + 2.4 Ko soit un total de 14.4 Ko au lieu de 24 Ko.

La première image, est une image dite de référence. Toutes les images suivantes sont des images différentielles par rapport à l'image de référence.

Pour mettre en pratique ce concept, il suffit de savoir réaliser des additions et des soustractions:

à l'encodage:

3 - 2 = 1 (image nouvelle - image référentielle = image différentielle)

au décodage:

2 + 1 = 3 (image référentielle + image différentielle = image nouvelle)

En fait ce calcul doit être réalisé pixel par pixel de l'image.
Dans les portions où l'image n'a subi aucun changement, ont obtiendra un calcul du type:

145 - 145 = 0

Lorsque le nouveau pixel est plus claire que l'ancien, on obtiendra:

160 - 140 = 20

A l'inverse, lorsque le nouveau pixel est plus foncé que l'ancien, on obtiendra le calcul:

140 - 160 = -20

1^er obstacle: l'éventail des valeurs différentielles

Dès lors les variations possibles s'inscrivent dans un éventail de  -255 à +255, soit 511 valeurs possibles.
Le problème, c'est que l'encodage se fait sur 8 bits, donc seulement 256 valeurs possibles.
La solution retenue est de diviser cette valeur par 2 : on réduit l'éventail à des valeurs : [-128..+128].
Sur un plan purement mathématique et spectral, il y a une perte d'information. Mais elle reste largement tolérable.

Comme les valeurs de couleur sont toujours positives [0..255], on ajoute 128 à la valeur différentielle obtenue et on obtient ainsi l'éventail [0..254].
Au moment du décodage, il faudra enlever cette valeur de 128.

2^è obstacle: le bruit de fond

On observe toujours un phénomène de "bruit de fond" qui produit une non linéarité des couleurs.
Ainsi 2 pixels voisins (au sein d'une image) qui ont un même éclairage auront finalement des valeurs proches, mais non-identiques.
De même, le même pixel de 2 images successives peut connaître une légère variation de valeur, à cause de ce "bruit de fond".
Le résultat de ce bruit de fond est d'obtenir des valeurs différentielles non-nulles, mais proches de 0 (généralement comprises dans des fourchettes allant de -5 à +5), alors qu'on souhaiterait ardemment qu'elles le soient. Par exemple :

148 - 147 = 1 ou 145 - 147 = -2

Ce bruit de fond observé augmente très fortement lorsque les images sont prises dans des conditions de faible éclairage.

Et finalement, encoder-compresser une succession aléatoire de valeurs de type -2 +1 -3 -1 +3 -2 +2 .....donne au final un très mauvais ratio de compression.
Il vaut mieux encoder un succession du type -2 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1 -1.....car ainsi l'algorithme de compression peut utiliser un langage du style "passer de -2 à -1 sur une largeur de 12".

J'ai trouvé 2 solutions à ce problème :

(1) obtenir le meilleur éclairage possible (mais on ne commande pas toujours de paramètre...)

(2) essayer de limiter le bruit de fond en créant des "effets de paliers" dans la représentation RVB de l'image dans la mémoire de l'ordinateur.
Par exemple les valeurs de 0 à 4 deviennent 0, les valeurs de 5 à 8 deviennent 4 et ainsi de suite.

La taille de palier est au choix du programmeur (2,3,4,5,...,8,16,...), de même que la valeur finale. On peut choisir délibérément de donner pour résultat la valeur plafond du palier (ainsi 0 à 4 devient 4 au lieu de 0).
Ainsi un palier de 4 donne finalement 256 / 4 = 64 valeurs possible dans chaque couleur fondamentale, donc 64^3 = 262144 couleurs possibles au lieu de 16 millions.

3^è obstacle: les fondement de l'encodage JPEG

Ce 3^è obstacle est lié à l'effet de palier décrit au 2^è obstacle.

L'algorithme JPEG n'est pas du tout adapté aux fortes ruptures chromatiques entre 2 pixels voisins. Or plus la largeur d'un palier est forte (ex: 0-16 donne 0), plus le risque de rupture chromatique est fort. JPEG est adapté aux progressions douces (d'où son usage en photographie numérique). Faites donc l'essai en plaçant un carré blanc à côté d'un carré noir : vous observerez de grosses perturbations à la frontière des 2 couleurs (à moins de demander une qualité 100%...).

Donc il faut se résoudre à utiliser des paliers nuls, ou faibles. Mais dans ce cas, on redevient très sensible au bruit, donc à un mauvais ratio de compression.

Pour ma part, après de nombreuses expérimentations, j'ai trouvé qu'une largeur de palier de 4 était un bon compromis entre la réduction du bruit et les effets de rupture chromatique.

Remarque : grâce à l'usage de ce palier, on obtient une image différentielle qui elle-même contient des paliers de largeur 4. On peut ainsi diviser la valeur obtenue par cette même largeur de palier, puis ensuite y ajouter la valeur 128.

Exemple: valeur différentielles obtenues +120 +124 +120 +128 -4 -16 0

on divise par 4 +30 +31 +30 +32 -1 -4 0

on ajoute 128 +158 +159 +158 +160 +127 +124 +128

on obtient ainsi un resserrement de l'éventail autour de la valeur centrale 128 qui permet ainsi d'obtenir de bons résultats à la compression JPEG.

Conclusion:

Voila, les jalons sont posés, il n'y a plus qu'à réaliser les applications logicielles autour de ce concept.

- création d'un encodeur D-JPEG en langage C, en utilisant la libjpeg

(1) chargement de l'image référentielle JPEG -> RVB

(2) chargement de l'image nouvelle JPEG -> RVB

(3) filtrage du bruit (palier de largeur 4)

(4) calcul de l'image différentielle RVB

(5) division par la largeur du palier (ici 4)

(6) centrage autour de 128

(7) encodage RVB -> JPEG et écriture du fichier de l'image différentielle "diff.jpg"

Cet encodeur est lancé plusieurs fois par seconde dans le cadre d'une boucle sans fin (script shell ou php ou tout autre langage)

- création d'un décodeur D-JPEG : applet java utilisée par un navigateur (Netscape, IE, ...)

(1) chargement de l'image référentielle JPEG -> RVB

(2) boucle éternelle

(2.1) chargement de l'image différentielle JPEG -> RVB

(2.2) décentrage (enlever 128)

(2.3) multiplication par la largeur du palier

(2.4) reconstitution de l'image nouvelle référentielle + différentielle = nouvelle

(2.5) affichage de l'image

Note :

(1) l'encodage JPEG est un encodage avec perte de qualité. Il y a perte de qualité pour les 2 images (référentielle et différentielle). Le meilleur compromis obtenu entre la perte de qualité est avec une qualité de 92% environ.

(2) cette distortion de qualité s'est traduite parfois par un dépassement de la valeur maximale 255 à la reconstitution. Ainsi, des zones très éclairées devenaient subitement sombres, car après 255 on repart à 0, et réciproquement dans les zones sombres. Il a fallu ajouter un filtre dans l'applet java pour borner les valeurs (ex : si valeur > 255 alors valeur=255).

(3) le code source de l'encodeur sera prochainement rendu public, sous licence GPL, bien entendu, car j'ai intégré du code GPL lors du développement de l'application.
Le code source java de l'applet sera également publié sous licence GPL.

Je pense sincèrement que ces 2 programmes peuvent être améliorés. Notamment l'applet Java, qui a un fonctionnement trop séquentiel et qui pourrait sans doute fonctionner avec du parallélisme entre la procédure de calcul-affichage d'une image et la procédure de chargement de l'image suivante. on gagnerait ainsi en fluidité dans le rendu côté navigateur.

(4) amélioration possible (mais ce n'est pas une certitude) : utiliser les compléments (arithmétique binaire) pour éviter d'avoir à resserrer l'éventail [-255...+255] issu du calcul du différentiel.

Résultat statistique:

image référentielle : env 11 Ko

image différentielle: env. 3.9 Ko

Prochaine piste à creuser:

création d'un programme de streaming MPEG qui se lance comme un script CGI.

Intérêt : ne pas avoir à développer un serveur de streaming MPEG.