Sujet
On se propose de réaliser, par étapes successives, un logiciel de (dé)compression basé sur la le standard CCITT qui permet de coder et décoder des images noir et blanc à des fins de transmission sur des lignes à bas débit..
Le codage de Huffman modifié
Le principe du codage de Huffman modifié est d’obtenir à partir d’une suite de 0 et 1 (blanc et noir) supposée contenir des répétitions consécutives de mêmes valeurs, une suite de codes chacun représentant la couleur et la longueur de la suite de même couleur.
Comme pour un encodage de Huffman, les codes employés sont de longueurs variables. Les codes les plus longs étant réservés aux longueurs de sous-suites les plus rares.
Dans cet encodage, chaque ligne est considérée comme commençant par une suite de blancs (si ce n’est pas le cas, c’est que la suite est de longueur nulle). Et chaque fin de ligne est encodée.
Le tableau suivant contient la liste des codes employés:
| Longueur | Blanc | Noir | Longueur | Blanc | Noir |
|---|---|---|---|---|---|
| 0 | 00110101 | 0000110111 | 32 | 00011011 | 000001101010 |
| 1 | 000111 | 010 | 33 | 00010010 | 000001101011 |
| 2 | 0111 | 11 | 34 | 00010011 | 000011010010 |
| 3 | 1000 | 10 | 35 | 00010100 | 000011010011 |
| 4 | 1011 | 011 | 36 | 00010101 | 000011010100 |
| 5 | 1100 | 0011 | 37 | 00010110 | 000011010101 |
| 6 | 1110 | 0010 | 38 | 00010111 | 000011010110 |
| 7 | 1111 | 00011 | 39 | 00101000 | 000011010111 |
| 8 | 10011 | 000101 | 40 | 00101001 | 000001101100 |
| 9 | 10100 | 000100 | 41 | 00101010 | 000001101101 |
| 10 | 00111 | 0000100 | 42 | 00101011 | 000011011010 |
| 11 | 01000 | 0000101 | 43 | 00101100 | 000011011011 |
| 12 | 001000 | 0000111 | 44 | 00101101 | 000001010100 |
| 13 | 000011 | 00000100 | 45 | 00000100 | 000001010101 |
| 14 | 110100 | 00000111 | 46 | 00000101 | 000001010110 |
| 15 | 110101 | 000011000 | 47 | 00001010 | 000001010111 |
| 16 | 101010 | 0000010111 | 48 | 00001011 | 000001100100 |
| 17 | 101011 | 0000011000 | 49 | 01010010 | 000001100101 |
| 18 | 0100111 | 0000001000 | 50 | 01010011 | 000001010010 |
| 19 | 0001100 | 00001100111 | 51 | 01010100 | 000001010011 |
| 20 | 0001000 | 00001101000 | 52 | 01010101 | 000000100100 |
| 21 | 0010111 | 00001101100 | 53 | 00100100 | 000000110111 |
| 22 | 0000011 | 00000110111 | 54 | 00100101 | 000000111000 |
| 23 | 0000100 | 00000101000 | 55 | 01011000 | 000000100111 |
| 24 | 0101000 | 00000010111 | 56 | 01011001 | 000000101000 |
| 25 | 0101011 | 00000011000 | 57 | 01011010 | 000001011000 |
| 26 | 0010011 | 000011001010 | 58 | 01011011 | 000001011001 |
| 27 | 0100100 | 000011001011 | 59 | 01001010 | 000000101011 |
| 28 | 0011000 | 000011001100 | 60 | 01001011 | 000000101100 |
| 29 | 00000010 | 000011001101 | 61 | 00110010 | 000001011010 |
| 30 | 00000011 | 000001101000 | 62 | 00110011 | 000001100110 |
| 31 | 00011010 | 000001101001 | 63 | 00110100 | 000001100111 |
Le tableau suivant contient les codes associés aux longueurs, peu fréquentes, mais plus grandes que 62. Pour une longueur comme 298, il suffit de prendre le code de la longueur 256 que l’on fait suivre par le code de 298-256=42.
| 64 | 11011 | 0000001111 |
| 128 | 10010 | 000011001000 |
| 192 | 010111 | 000011001001 |
| 256 | 0110111 | 000001011011 |
| 320 | 00110110 | 000000110011 |
| 384 | 00110111 | 000000110100 |
| 448 | 01100100 | 000000110101 |
| 512 | 01100101 | 0000001101100 |
| 576 | 01101000 | 0000001101101 |
| 640 | 01100111 | 0000001001010 |
| 704 | 011001100 | 0000001001011 |
| 768 | 011001101 | 0000001001100 |
| 832 | 011010010 | 0000001001101 |
| 896 | 011010011 | 0000001110010 |
| 960 | 011010100 | 0000001110011 |
| 1024 | 011010101 | 0000001110100 |
| 1088 | 011010110 | 0000001110101 |
| 1152 | 011010111 | 0000001110110 |
| 1216 | 011011000 | 0000001110111 |
| 1280 | 011011001 | 0000001010010 |
| 1344 | 011011010 | 0000001010011 |
| 1408 | 011011011 | 0000001010100 |
| 1472 | 010011000 | 0000001010101 |
| 1536 | 010011001 | 0000001011010 |
| 1600 | 010011010 | 0000001011011 |
| 1664 | 011000 | 0000001100100 |
| 1728 | 010011011 | 0000001100101 |
| 1792 | 00000001000 | 00000001000 |
| 1856 | 00000001100 | 00000001100 |
| 1920 | 00000001101 | 00000001101 |
| 1984 | 000000010010 | 000000010010 |
| 2048 | 000000010011 | 000000010011 |
| 2112 | 000000010100 | 000000010100 |
| 2170 | 000000010101 | 000000010101 |
| 2240 | 000000010110 | 000000010110 |
| 2304 | 000000010111 | 000000010111 |
| 2368 | 000000011100 | 000000011100 |
| 2432 | 000000011101 | 000000011101 |
| 2496 | 000000011110 | 000000011110 |
| 2560 | 000000011111 | 000000011111 |
| EOL | 000000000001 | 000000000001 |
La suite 110000001110000000000<EOL> (de longueur 21) sera encodée par 001101011111101000111000000000001 (de longueur 33).
1. Il est demandé de réaliser dans un langage de programmation de votre choix (de préférence C, C++ ou Java, pour les autres demander à l’enseignant) un programme d’encodage et de décodage CCITT (basé sur le principe précédent). Ce programme devra permettre d’encoder tout fichier donné en entrée et produire en sortie un fichier dont le nom sera étendu en .fax. Ce programme devra en outre produire en sortie le taux de compression obtenu.
2. On testera ce programme sur une variété de fichiers dont les suivants: une image de taille A4 toute blanche et scannée en 200ppp, une image (à télécharger ici) qui est au format PGM, puis une image de son choix.
Le TP devra être rédigé (sous la forme de documents HTML) et rendu avec les codes sources des programmes; ce au plus une semaine après la séance.
