Compression d'image


doc Range Coder | doc Burrows Wheelers Transform | exe Compressor


05 Février 2006 - Packaging

Mise en forme de tous les essais dans un exe (que l'on peut downloader ici, nécessite la librairie stlport) avec possibilité de donner l'enchainement des algos utilisés pour compresser. Pour la décompression les algos sont lus à partir du fichier. Reste à faire un packer (genre tar) pour regrouper les fichiers en un seul. Ce compresseur est un compresseur sans perte, il reste encore quelques algos sans perte à essayer et débuter la compression avec perte.


24 Mai 2005 - BWT par block et tests LZSS

Sur les 10 photos (59,927,220) Delta3 + BWT + MTF + Huffman :

BLOCK | NoLimit | 512 Ko | 256 Ko | 128 Ko | 64 Ko  | 32 Ko  | 16 Ko  | 8 Ko   | 4 Ko
COMP. | 49.36%  | 49.73% | 49.96% | 50.21% | 50.48% | 50.78% | 51.13% | 51.62% | 52.35%
TEMPS | 6m05s   | 5m17s  | 4m38s  | 3m58s  | 3m19s  | 2m38s  | 1m50s  | 1m31s  | 1m29s

BWT + MTF + Huffman :

BLOCK | NoLimit | 1 Mo   | 512 Ko | 256 Ko | 128 Ko | 64 Ko  | 32 Ko  | 16 Ko  | 8 Ko   | 4 Ko
COMP. | 52.80%  | 53.82% | 55.39% | 56.82% | 59.69% | 60.83% | 63.17% | 65.68% | 68.52% | 71.88%
TEMPS | 5m56s   | 5m11s  | 4m43s  | 4m13s  | 3m42s  | 3m10s  | 2m31s  | 1m52s  | 1m38s  | 1m35s

L'algorithme de BWT est assez couteux. Il faut comparer tout cela avec un simple Delta3 + Huffman qui donne déjà un résultat de 51.53% en 22s.

On a fait aussi des tests sur le LZSS Hash+Liste chaînée
Si la position, dans le couple (position,taille) de la chaîne de caractère déjà présente est de 12 bits pour 2 caractères, 14 bits pour 3 caractères et 16 bits pour plus de 3 caractères. On le note (12,14,16)

Les tests sont fait sans limite pour le nombre de recherche :
16 bits max, temps de compression : 3m37s minimum (12,14,16) avec une compression de 62.71%
15 bits max, temps de compression : 1m50s minimum (12,14,15) avec une compression de 62.83%
14 bits max, temps de compression : 1m05s minimum (10,12,14) avec une compression de 62.39%
13 bits max, temps de compression : 0m41s minimum (10,12,13) avec une compression de 62.25%
12 bits max, temps de compression : 0m29s minimum (10,12,12) avec une compression de 62.33%
11 bits max, temps de compression : 0m22s minimum (10,11,11) avec une compression de 63.71%

Comme on peut le voir si on augmente la fenêtre de recherche cela n'améliore pas forcément la compression (car plus de bits sont pris pour décrire la taille et la position de la chaîne déjà présente). On retiendra un (10,12,12) pour une passe après Delta3, bon compromis entre performance et vitesse. Le lzss reste pour l'instant en dessous des compressions statistiques.
On va donc faire plus de recherche sur les compressions statistiques. Par exemple il serait bon de voir un peu les modèles statistiques à contexte fini.

20 Mai 2005 - Fin du Range Coder

Apperement lors de l'implémentation, il y a une erreur de précision sur les plages retrouvées lors du décodage. Celle ci n'est plus présente si l'on se dit que l'on ne code pas de 0 a 1 (ou 00000 a 10000) mais de 0 a 0.9999... sachant qu'avec une infinité de 9 cette valeur tends vers 1. On a donc mis à jour la doc sur le range coder.
10 Photos, résultats en fonction de la taille des blocks :
Delta 3 + Range Coding (32k)  : 31,912,694 (53.25%)
Delta 3 + Range Coding (65k)  : 31,227,048 (52.10%)
Delta 3 + Range Coding (128k) : 30,886,451 (51.54%)

Plutôt décevant par rapport à la complexité de mise en oeuvre.

18 Mai 2005 - Range Coder

Ecriture d'une doc simple pour le range coder. Début de son implémentation. Il reste apperement un souci de précision.

17 Mai 2005 - Huffman, début de compression statistiques

On a implémenté un compresseur de huffman statiques qui travaille sur des blocks de 32 Ko. Les probabilités sont évaluées de façon statique sur tout le block en cours de traitement.
Des tests sur des fichiers binaires montrent que un BWT+MTF+Huffman donne de très bon résultats.
Quelques tests sur le jeu de 10 photos :

Taille totale des 10 photos : 59,927,220 octets
Huffman                       : 51,405,748 (85,78% de l'original) en 0m27s
BWT + MTF + Huffman           : 31,662,484 (52.80% de l'original) en 5m56s
Delta 3 + Huffman             : 31,618,376 (52.76% de l'original) en 0m22s
Delta 3 + BWT + MTF + Huffman : 29,583,176 (49.36% de l'original) en 6m05s

On a essayé plusieurs taille de block. En effet, les probabilités des caractères (256) sont stockées non compressées avant chaque block, il y a donc une influence sur la compression si la taille du block est trop petite. De même si la taille du block est trop grande, le huffman ne sera pas assez "adaptatif" au sens ou les données en début de fichier peuvent être distribuées différement de celle en fin de fichier.
Le temps de compression des 10 images en Delta3+Huffman est de 17s et les pourcentages de compression par rapport à la taille originale sont donnés en fonction de la taille d'un block :

2 Mo   | 1 Mo   | 512 Ko | 256 Ko | 128 Ko | 64 Ko
51,62% | 51,54% | 51,53% | 51,59% | 51,76% | 52,11%

Il semble que la bonne taille soit aux alentours de 512 Ko. Ceci est corroboré par des tests effectuées sur des binaires et qui donnent des résultats à peu près identiques.
La première conclusion de tout cela est que les compresseurs statistiques semblent être de bons candidats pour la compression de photos. On ira donc dans ce sens, avec notamment l'implémentation d'un compresseur arithmétique de type range coder. Une deuxième conclusion est qu'il faut absoluement optimiser le BWT (traiter par block plus petit que la taille totale du fichier).
Delta 3 + Huffman             : 30,880,496 (51.53% de l'original) en 0m22s
Delta 3 + RLE + Huffman       : 31,252,045 (52.15% de l'original) en 0m22s
Delta 3 + RLEHead + Huffman   : 33,768,988 (56.35% de l'original) en 0m22s

15 Mai 2005 - Accélération LZSS, Hash + liste chaînées

Il semble que ce soit le plus rapide. Le principe est d'avoir une hash map pour les 2 premiers caractères et ensuite une liste chaînées des positions. Le test exhaustifs de toutes les positions dans la liste chaînées est en fait rapide car la liste est implémentée sous forme d'un tableau statique (circulaire). De plus on maintient une liste des têtes de listes chaînées et une liste des queue de listes chaînées. L'insertion et la deletion se font donc en O(1). La recherche en O(1+N) au pire des cas, mais la plupart des cas c'est O(1) + quelques essais. Il n'y a pas d'allocation mémoire, pas de structures compliquées (il n'y a que 3 tableaux de pointeurs). La grande différence avec l'implémentation avec précédente et celle avec plusieurs hashmap est que les structures sont beaucoup moins lourde et que l'on essaye pas d'insérer plusieurs chaînes de taille différente dans la table. Apperement la différence de vitesse est de l'ordre de x8 par rapport à l'implémentation "lente" avec des listes chaînées explicitement (stl list).

13 Mai 2005 - Accélération LZSS, recherche en arbre N-aire

Le jeu de test de 10 photos passe en 4 min 58 s et cela en ne prenant en compte que la derniere position d'un mot vu. L'arbre a une profondeur de 4 caractères. Avec une profondeur de 5 caractères on tombe a 6 min 35 s. Il est évident que la structure à gérer est beaucoup trop lourde. Si on veut essayer de poursuivre dans cette voie là, il faut penser à implémenter plutôt un PATRICIA trie. Mais avant essayons la version en liste chaînées

12 Mai 2005 - Accélération LZSS, Hash Map

La recherche d'une chaine de caractère est un point critique du LZSS. On l'a améliorer à l'aide d'une table de hashage qui donne un gain de vitesse d'environ x2.
L'implémentation stocke des chaines de 2, 3, 4 et 5 caractères dans une table unique dont on va faire varier la taille pour voir le temps de compression.
Le LZSS a une fenêtre de recherche de 4 Ko pour les chaines de 2 caractères et 32 Ko pour les chaines de plus de 2 caractères.
Les données sont 10 photos de 1224x1632 pour un total de 57,1 Mo. La compression n'est pas aussi bonne qu'attendue (62,6% de l'original).
Avant :
Delta 3 + LZSS 3 Maps (2,3,4 caractères) - 6 min 25 s
Après :
Delta 3 + LZSS Hash 512 Ko - 3 min 27 s
512 Ko | 256 Ko | 128 Ko | 64 Ko | 32 Ko | 16 Ko | 8 Ko  | 4 Ko  | 2 Ko | 1 Ko
3m27s  | 3m24s  | 3m23s  | 3m20s | 3m18s | 3m06s | 3m06s | 3m22s | 4m0s | 5m13s

Premières conclusions : la taille de la table ne joue pas tellement sur le temps de compression et une table grande ne signifie pas un temps de compression petit comme on aurait pu s'y attendre. Peut être que la fonction de hashage est mal choisie (JS). On a donc essayé différente fonction de hashage avec une taille de fenêtre de 12 Ko :

Delta 3 + LZSS Hash (JS) 12 Ko - 3 min 06 s
JS    | DJB   | AP    | BKDR  | RS    | ELF   | PJW   | SDBM
3m06s | 3m08s | 3m12s | 3m20s | 3m26s | 3m44s | 3m46s | 4m19s

De façon surprenante on avait choisie la meilleure fonction de hashage pour le type d'entrée donné.
Par contre sans Delta3 la différence est moins grande

LZSS Hash (JS) 12 Ko - 3 min 46 s
JS    | DJB   | AP    | BKDR
3m46s | 3m45s | 3m55s | 3m48s

Les résultats sont surprenants. On a pensé que le problème provenait du nombre de collision. On a donc implémenté une solution avec plusieurs tables de hashage et un cas spécial (sans clé de hashage) pour les chaînes de 2 caractères. Et bien cela ne change pas fondamentalement les temps. Ceci nous laisse penser que le temps pris pour manager les listes est plus grand qu'attendu. On va donc essayé uniquement avec des listes chaînées mises dans un tableau représentant les 2 premiers caractères de la chaînes à trouver. O(1) donc et ensuite recherche en N.

10 Mai 2005 - RLE seconde version

On a implémenté la seconde version (le RLE sans entête). Même si il n'a pas pour but d'être utilisé tel quel avant le LZSS on a fait un test.
RLE + LZSS : 6,160,480 (75.12% de l'original)
C'est un tout petit peu meilleur que le RLE avec entête. Ce qui n'est pas très étonnant car les 3 composantes d'une couleur ne se suivent quasiment jamais (a part pour le gris). Le RLE avec entête est moins bon quand il n'y a pas beaucoup de répétition. On a fait des tests un peu plus complet :

Delta3 +           BWT +       RLEHead + LZSS : 4,732,628 (57,71% de l'original)
Delta3 + RLEHead + BWT + MTF + RLEHead + LZSS : 4,639,172 (56,57% de l'original)
Delta3 + RLE     + BWT +       RLEHead + LZSS : 4,610,476 (56,22% de l'original)
Delta3 + RLE     + BWT + MTF + RLE     + LZSS : 4,548,820 (55,47% de l'original)
Delta3 + RLE     + BWT + MTF +           LZSS : 4,532,708 (55,27% de l'original)
Delta3 + RLEHead + BWT +       RLEHead + LZSS : 4,511,084 (55,01% de l'original)
Delta3 +           BWT +       RLE     + LZSS : 4,490,116 (54,75% de l'original)
Delta3 +           BWT                 + LZSS : 4,488,812 (54,73% de l'original)
Delta3 + RLEHead + BWT + MTF +           LZSS : 4,395,952 (53,60% de l'original)
Delta3 + RLE     + BWT +       RLE     + LZSS : 4,376,564 (53,36% de l'original)
Delta3 + RLE     + BWT +                 LZSS : 4,363,432 (53,21% de l'original)
Delta3 + RLEHead + BWT +       RLE     + LZSS : 4,328,108 (52,77% de l'original)
Delta3 + RLEHead + BWT +                 LZSS : 4,248,172 (51,80% de l'original)

Des petites conclusions : Ce n'est pas forcément le plus compliqué qui est le plus performant. Il faut adapter les données d'entrées avec les types de données produites par les transformateur. Le MTF et le RLE ne semblent pas adapté pour une entrée de LZSS, il faudra essayer avec un compresseur statistique, les résultats seront probablement meilleurs. Il va aussi falloir améliorer le LZSS et le LZW (on a pas fait beaucoup de test avec le LZW).
On a essayé ces tests sur des images de 1224x1632 de type photographie avec un grain (un peu de bruit) et on tombe a :
Delta3 + RLEHead + BWT + LZSS : 67 %
Delta3 + LZSS                 : 62,60%
C'est un peu desespérant. Mais effectivement on ne peut pas uniquement tester avec le jeu de test qui ne montre que le bon côté de notre CODEC.

09 Mai 2005 - RLE

On a vu 2 types de RLE : un dit avec entête et un sans entête.Celui avec entête a l'avantage de compresser à partir de 3 octets. Celui sans entête n'as pas d'overhead pour les zones non compressées mais ne compresse qu'à partir de 4 octets identiques. Le RLE avec entête possède comme son nom l'indique une entête d'un octet qui indique : soit un nombre d'octets répétés et après l'entête on a un octet que l'on va répeter, soit un nombre (N) d'octets non répétés et après l'entête on a N octets à écrire directement. Le RLE sans entête se sert du fait qu'il voit 2 fois le même octet pour se dire il doit y avoir une zone à compresser. Apres 2 octets identiques consécutifs, il y a un caractère qui indique le nombre de répétition.
RLEHead + LZSS : 6,209,404 (75.72% de l'original)

04 Mai 2005 - Move To Front

Ajout d'un algo de move to front, quand on doit écrire un caractère, on le cherche dans une liste des caractères récement utilisés. On écrit sa position dans la liste et on le met en tête de liste. Sur les fichiers binaires, ce type d'algo est assez bon, par contre sur notre lot d'images, on est a :
BWT+MTF+LZSS : 5,997,860 (73,14% de l'original)
On essaye d'autres combinaisons : (attention tout ca n'est pas bijectif (Delta3+MTF est différent de MTF+Delta3). On finit toujours par le LZSS puisque c'est lui qui va vraiment compresser. Les autres étapes servent surtout a diminuer l'entropie.
MTF+Delta3+LZSS     : 7,294,672 (88,95% de l'original)
BWT+MTF+LZSS        : 5,997,860 (73,14% de l'original)
Delta3+MTF+LZSS     : 5,300,796 (64,64% de l'original)
Delta3+LZSS         : 4,733,472 (57,72% de l'original)
Delta3+BWT+MTF+LZSS : 4,658,704 (56,81% de l'original)
Delta3+BWT+LZSS     : 4,488,812 (54,73% de l'original)

Une première conclusion est que les gains ne sont pas astronomiques. Il se peut que ce soit à cause du LZSS que l'on a optimiser pour des entrées en delta3. Il faut donc une optimisation adaptative pour le LZSS sous forme d'un algorithme de Huffman ou d'un codeur arithmétique. On va aussi ajouter un autre compresseur qui peut manquer : le RLE. (non ce n'est pas une blague, il peut aider, par exemple après un MTF on aura 'beaucoup' de zero consecutifs)

03 Mai 2005 - Burrows Wheeler Transform

Implémentation de cette fameuse transformation. Les premiers tests en branchant seule cette transformation sur le compresseur LZSS sont assez bon sur des fichiers binaire mais assez mauvais sur les 10 images de référence :
BWT + LZSS : 5,935,748 octets (taux : 72.38% de l'original)
On a encore beaucoup de test à faire (implémentation d'un move to front, essai avec delta, etc...)

28 Avril 2005 - Optimisation LZSS multidictionnaire

L'optimisation s'est faite en 2 temps : 1er temps, utilisation d'entier plutôt que de chaîne de caractères pour la clé des dictionnaires. Cela fait perdre un peu de place, mais gagne beaucoup en vitesse puisque c'est sur la clé du dictionnaire que se fait la recherche. 2ème temps, séparation du dictionnaire de plus gros mots (pour l'instant 4 caractères) et dictionnaire de moins gros mots (2 ou 3 caractères). Les dictionnaires de moins gros mots n'ont effectivement pas besoin d'une liste de position mais juste de la dernière position rencontrée pour un mot de taille donné. En effet, on sait que si l'on se met a chercher dans ces dictionnaires, on recherche un mot dont la taille est exactement la meme que celle du dictionnaire (car sinon on l'aurait trouvé dans un dictionnaire de plus gros mot). Cela optimise bien le temps car on passe de 15 min a 2 min pour compresser nos 10 images, sans changer les performances au niveau de la taille (toujours 57.7% ce qui est peu comparé a RAR qui fait 48,1 %). Si on veut gagner en vitesse il faut penser a l'utilisation d'une hash map et si on veut gagner en taille, il faut commencer à implémenter un huffman et une transformation de Burrows Wheelers.


27 Avril 2005 - LZSS Multi Dictionnaire

Pour accélérer le lzss avec la transformation linéaire, on a mis en place un système à plusieurs dictionnaires. Chaque dictionnaire est créé avec une taille de mot donné. On commence la recherche dans le dictionnaire ayant les mots de plus grande taille. Cette méthode est plus lente pour les fichiers qui n'ont pas subi de transformation linéaire. Il faut tester ce que cela donne sur des fichiers ayant subi cette transformation. On devra aussi optimiser la structure de donnée : tous les dictionnaires peuvent avoir une clé sous forme de tableau de taille fixe et de plus tous les dictionnaires sauf celui de plus gros mots peuvent ne stocker que la derniere position de mot rencontrée (ceci est du au fait que lorsque l'on recherche dans le dictionnaire de plus gros mots, il se peut que le mot répété soit encore plus gros que celui qui est trouvé dans le dictionnaire alors que lorsque l'on recherche dans un autre dictionnaire (de moins gros mots), on est sur que c'est uniquement la taille désirée que l'on va trouver. Il y a donc encore beaucoup d'investigation à faire dans cette voie pour rendre la compression rapide, une autre piste serait de faire une nouvelle transformation (ondelette par exemple) et une dernière piste serait de mettre en place le pipeline (différentes transformations branchées sur différents compresseurs etc...)

04 Avril 2005 - Début des transformations linéaires

La première transformation linéaire que l'on a adopté sur tout le fichier (la connaissance de la taille de l'image n'est pas des plus utile) est la suivante :
On garde tel quel les 3 premiers octets. Tout les octets suivants sont définis par rapport à ceux qui le précèdent : Pixel(n) = Pixel(n) - Pixel(n-3). Ceci fonctionne bien car les images sont en 24 bits décompréssées. A noter que pour cette transformation il faut commencer par la fin de l'image. Pour effectuer la transformée inverse, il suffit de faire Pixel(n) = Pixel(n) + Pixel(n-3). Cette transformation va créer des zéros et des valeurs de faible intensités (en positif et négatifs). Il faut noter que le LZSS est plus lent avec un flux comprenant beaucoup des mêmes 'petites' valeurs. En effet comme il essaye toutes les possibilités de 2 octets, la recherche est dans ce cas linéaire.
On ne s'y trompe pas. La compression a pris 15 min pour les 10 images (10 fois plus que sans la transformation). Par contre le taux de compression devient meilleur que zip et de loin.
zip : 5,713,320 octets (taux : 69.67% de l'original)
notre version transfo-3 + LZSS : 4,733,472 octets (taux : 57.72% de l'original)
On est encore loin du jpeg, mais on est toujours lossless.

30 Mars 2005 - Le ZIP comment ça marche

2 points lors de la lecture d'un document sur le zip :
1 - le LZSS qu'il emploie ne s'arrête pas à la fin de la sliding window.
2 - il utilise conjointement un algorithme de huffman
C'est ce que j'avais essayé de faire 'maladroitement' (de façon manuelle) en réduisant le nombre de bits pris par les code de contrôle en fonction de leur fréquence.
Nous reviendrons à une phase statistique un peu plus tard.

Intéressant à voir : un codeur arithmétique http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/compression.pdf


29 Mars 2005 - Entête de compression

Les résultats des stats ont l'air de dire que pour le couple (position,taille) indiquant la séquence à répéter, la position ne pourra pas être vraiment réduite en nombre de bits. Pour l'instant, l'ensemble des répétitions semble être réparti sur la fenêtre de façon à peu près homogène. Par contre la taille des répétitions pourra probablement être réduite. Cela tends à indiquer que ce sont de petites répétitions fréquentes, plutôt que de grandes plages de répétition. De même pour la taille des données non compressée, la moitié des tailles peut être représentée sur 2 ou 3 bits.
On a fait des statistiques complémentaires sur la possibilité de compresser même les séquences de 2 octets et 3 octets (ce que l'on ne faisait pas jusqu'à maintenant car le couple (position,taille) était sur 3 octets). Une fois ceci fait, on peut faire un code du type :
Deux premiers bits d'entête :
00 - 1 char non compressé
01 - non compressé
   0 - Taille sur 3 bits
   1 - Taille sur 7 bits
       Puis la taille sur x bits (défini précédement)
           Puis N chars non compressée (N = taille définie précédement)
10 - compressé 2 chars
   Puis 12 bits de position relative
11 - compressé > 2 chars
   0 - compression de 3 chars
       Puis 15 bits de position relative
   1 - compressé > 3 chars
      0 - Taille sur 3 bits
      1 - Taille sur 7 bits
           Puis la taille sur x bits (défini précédement)
               Puis 15 bits de position

Peut être va-t-on trop loin sans avoir au préalable formaté les données qui vont rentrées dans ce compresseur. On garde cette compression dans un coin et on va commencer les transformations linéaires. En même temps que l'on va aussi passer le LZW au bit près (cela fera 2 algos de compression un peu différent pour faire des tests aux sorties des transfosmateurs).
En tout cas les résultats sur les 10 images de tests sont un peu meilleurs : 74.46 % de l'original. On est encore loin de zip, mais c'est une compression facile à comprendre et à mettre en oeuvre.

23 Mars 2005 - Adaptation LZSS avec bitfield

Pour l'instant pas de travail sur le taille prise par les infos de position.

21 Mars 2005 - Bitfield : Gestion du flux au bit près

On va maintenant pouvoir gérer le flux de donnée compressée au bit près. Ceci va être grandement utile pour l'amélioration du LZW et du LZSS.

17 Mars 2005 - LZW version "naïve"

L'implémentation du LZW en version de base est faite. Cette version est dites naïve car les codes de sorties sont sur 16 bits et le dictionnaire une fois arrivé à 65535 entrée est bloqué avec ces entrées. On se doute que ce n'est pas très adaptatif et les résultats sur nos 10 fichiers de test s'en ressent. La compression donne au final 8,844,076 octets soit 107.84% de l'original (des originaux). Ce n'est clairement pas terrible, mais c'est un début. Avec un dictionnaire adaptatif et des codes avec un nombre de bits adaptatifs on peut espérer que le taux soit meilleur.
En pensant aux défaut du LZSS implémenté jusqu'ici, on notera que son plus gros défaut est de ne compresser qu'à partir d'un seuil de 4 octets consécutifs. On peut imaginer un code spécial pour compresser les chaînes de 2 ou 3 octets consécutifs. Avec une petite entête sur 2 bits on choisirai soit le nombre d'octets non compressé consécutifs, soit le couple utilisé jusqu'à présent sur 3 octets (position, taille), soit la nouvelle définition qui pourrait se décomposer comme suit. Le 1er bit pourrais indiquer si la chaîne est sur 2 ou 3 octets, les N bits suivant (de préférence < 13) donnerais la position relative du couple ou triplet dans le flux précédent.

16 Mars 2005 - Optimisation du LZSS

On a repris le meilleur LZSS (c'est-à-dire le min 4 octets avec une taille de fenêtre de recherche de 32Ko) et on l'a optimisé à l'aide d'un dictionnaire dynamique représentant toutes les séquences de 4 octets de la fenêtre de recherche. La clé du dictionnaire est donc cette séquence minimale de 4 octets et les informations liées à cette clé sont les positions où l'on peut trouver cette séquence de 4 octets dans la fenêtre de recherche. Le temps de compression est donc passé de 30 minutes à 30 secondes (60x moins!). C'est un peu mieux mais pas encore au top.
Il faut maintenant commencer les investigations sur le LZW et surtout les transformations linéaires qui vont aider les algorithmes de compression. Les différences sont toujours moins lourdes sur les images car d'un pixel à l'autre il y a toujours peu de différence (ou elles sont à peu près du même ordre).

15 Mars 2005 - Résultats de compression

Résultats du LZSS non optimisé sur 10 images de différentes taille, couleurs et contenus. Ces images sont en 24 bits RGB.
Ces résultats sont obtenus sans transformation préalable de l'image. Les temps de compression sont surtout là à titre indicatif (le PC est un 2Ghz), car la recherche est pour l'instant linéaire. Le paramètre "win" correspond à la taille de la fenêtre de recherche.

Taille totale en entrée : 8,200,448 octets
zip : 5,713,320 octets (taux : 69.67% de l'original)

LZSS min 9 octets (4 octets pour la position, 4 octets pour la taille)
win 32 Ko : temps : 31 min, compression : 7,502,544 octets (taux : 91.48% de l'original)
win 16 Ko : temps : 13 min, compression : 7,514,760 octets (taux : 91.63% de l'original)
win 08 Ko : temps : 07 min, compression : 7,527,730 octets (taux : 91.79% de l'original)
win 04 Ko : temps : 03 min, compression : 7,539,470 octets (taux : 91.93% de l'original)

LZSS min 5 octets (2 octets pour la position, 2 octets pour la taille)
win 32 Ko : temps : 31 min, compression : 6,966,672 octets (taux : 84.95% de l'original)
win 16 Ko : temps : 13 min, compression : 7,054,824 octets (taux : 86.02% de l'original)
win 08 Ko : temps : 07 min, compression : 7,138,972 octets (taux : 87.05% de l'original)
win 04 Ko : temps : 04 min, compression : 7,218,182 octets (taux : 88.02% de l'original)

LZSS min 4 octets (2 octets pour la position 1 octet pour la taille (taille max 255))
win 32 Ko : temps : 31 min, compression : 6,754,703 octets (taux : 82.37% de l'original)
win 16 Ko : temps : 13 min, compression : 6,868,907 octets (taux : 83.76% de l'original)
win 08 Ko : temps : 07 min, compression : 6,978,652 octets (taux : 85.10% de l'original)
win 04 Ko : temps : 04 min, compression : 7,102,464 octets (taux : 86.61% de l'original)

La conclusion est que déjà l'algorithme compresse. Même si ce n'est pas la performance d'un zip, c'est déjà ça de gagné. Il faut maintenant optimiser cet algorithme pour qu'il aille plus vite. L'optimisation portera sur la recherche dans la fenêtre. On va garder cet algorithme pour le comparer à un LZW pour voir lequel des 2 compressera le mieux le flux sortant de la transformation et quantisation.


14 Mars 2005 - Améliorations du LZSS

La première amélioration est la mise en place d'une fenêtre de recherche pour éviter d'avoir à rechercher les chaînes à travers tout le fichier. On fera des essais pour voir l'importance de la taille de la fenêtre sur le taux de compression.
La seconde amélioration est de mettre les codes de taille et position sur 16 bits. Deux entiers sur 16 bits, cela fait 4 octets. Il ne faut donc maintenant plus que 5 octets consécutifs minimum pour déclencher la compression (5 octets remplacés par les 4 octets de taille et position). La dernière optimisation est de coder la taille sur 8 bits, en effet, il est rare de dépasser des redondances de chaîne de plus de 255 octets. Ceci aura pour effet de déclencher la compression à partir de 4 octets qui se suivent.

11 mars 2005 - Commencement par la fin : LZSS

On a commencé par mettre en place une application MFC qui fait de la lecture et de l'affichage d'image. A travers les codecs de windows elle lit les jpg, bmp etc...
Paralèllement, on a commencé par la fin du compresseur à savoir le compresseur sans perte. Dans la littérature, il est fait mention de plusieurs types de compresseur : RLE (répétition d'octet), dictionnaire (répétition de chaîne d'octets(LZSS, LZW)) et entropique (statistiques sur les octets(Huffman, Arithmétique)). Ce qu'il y a de positif, c'est que l'on peut combiner les types de compresseurs entre eux, de préférence comme suit : RLE puis dictionnaire puis entropique. Il faudra voir dans la pratique les gains obtenu.
Nous avons donc commencé par l'implémentation d'un LZSS de façon naïve. Le principe est que l'on peut remplacer une chaîne d'octets par une autre, présente précédement dans le fichier (plus précisément dans le flux). Si on trouve une chaîne assez longue, on la remplace par la position et la taille de la chaîne précédente.
Cette implémentation ne donne pas de très bon résultat en terme de performance (le temps de compression est TRES long) ni en terme de taux de compression. Ceci est probablement du au fait que la position et la taille de la chaîne précédente sont codé sur 32 bits. Ce qui oblige à avoir une chaîne d'octets de plus de 8 octets consécutifs pour déclencher la compression.

08 mars 2005 - Début : Structure

Après avoir glané quelques informations sur internet, il a été décidé que le compresseur aurait la tête suivante :
1 - Transformation linéaire
2 - Quantiseur
3 - Compresseur sans perte (peut être plusieurs)
La transformation linéaire servira a ce que les informations importantes de l'image soient regroupées dans des zones qui seront faiblement quantisée. Le quantiseur apportera la compression avec perte en éliminant les informations non essentielles et peu importante pour l'image. Le ou les compresseurs sans perte serviront à réduire la taille de l'image obtenue qui sans cela aurait pu être plus grosse que l'originale. Les deux premières étapes servent pour obtenir le meilleur taux de compression de la derniere étape.