Entroptymisator Image 1
Avant hier un ami m’a filé un lien sur wikipedia expliquant la compression JPEG. J’ai trouvé ça plutôt amusant, et je me suis dit que ça serait rigolo de faire un format de compression d’images. Alors j’ai cherché un concept à appliquer, et puis je me suis souvenu d’un truc que j’avais pensé entre deux baillements pendant un cour de signal : admettons qu’on veuille stocker 15 valeurs comprises entre 1000000 et 1000100. Soit on stocke bêtement les chiffres, ce qui demande un entier de 16 bits pour chaque valeur, soit prend en compte le fait que toutes les valeurs sont supérieures à 1000000, et qu’on aura que 100 valeurs différentes au maximum. Donc il suffit de dire au début qu’on a un offset de 1000000 (donc là un entier de 16 bits), puis on peut stocker le reste avec du 8 bits. Donc pour nos 15 valeurs, on aurait 15 * 16 = 240 bits, ou alors 16 + 15*8 = 136. On a vite fait de voir qu’il y a un gros gain de place.
Donc je me suis dit qu’on pouvait appliquer un peu le même principe aux images : on découpe l’image en carrés de 8 pixels de côté, on passe l’image en HSV, puis on regarde le minimum et le maximum de chaque composante. Ensuite pour chaque pixel on calcule le pourcentage de chaque composante entre le min et le max : par exemple si on a une teinte entre 130 et 140, et que la valeur du pixel c’est 133, alors ça nous donne 30%. Ce pourcentage on peut l’encoder sur 3 bits (2 bits pour la saturation), ce qui permet de rentrer les 3 composantes sur 1 octet. Si on a de la chance et que l’écart entre le min et le max est faible, alors on peut restituer une couleur assez fidèle (sinon on a un bel artefact).
Avec cette technique, on a une moyenne de 1,2 octet/pixel, ce qui reste 10 fois plus que le JPEG, mais bon…
Pour ceux que ça intéresse, voici les “specs” du format de fichier, c’est complètement à l’arrache, comprendra celui qui pourra 
Trame du fichier 3 octets : "im1" 1 octet : version du standard n octets : données insignifiantes 2 octets : 2x caractère nul 4 octets : taille x ( nombre de blocs b(x) = int((x+7)/8) ) 4 octets : taille y ( nombre de blocs b(y) = int((y+7)/8) ) 6+64 octets : bloc [b(x)⋅b(y)] 1 octet : hue min 1 octet : hue max 1 octet : saturation min 1 octet : saturation max 1 octet : value min 1 octet : value max 1 octet : pixel [8⋅8] 3 bits : scaled hue 2 bits : scaled saturation 3 bits : scaled value
Note : pour ce qui est des blocs au bord de l’image, ils ne font pas 8×8 mais s’arrêtent au bord (ce qui influe sur la taille du bloc).
Et puis comme je suis sympa j’ai même fait un programme qui permet de créer/voir/exporter des images au format im1 (abrégé de entroptymisator image 1), que vous pouvez télécharger en cliquant là, mais je vois préviens : c’est la première fois que je fais du C++, et c’est développé vite et à l’arrache, donc le code est assez ignoble et pas toujours commenté. J’ai fait une tentative d’indépendance au boutisme, mais j’ai eu la flemme d’aller jusqu’au bout, alors pour l’instant les images petitboutistes marcheront pas sur les systèmes grandboutiste et inversement, mais ça changera peut être un jour. Question librairies utilisées, c’est GD et SDL, donc ça devrai se compiler sans soucis sous windows, même si je n’ai testé que sous linux. D’ailleurs voici le fichier binaire pour linux 32 bits.
Et puis quand même, ce que vous attendez tous, c’est à dire un joli comparatif :
Add comment August 29th, 2008