Codage arithmétique
Le codage arithmétique est très proche de l'entropie. C'est un codage variant ou adaptatif.
Voici le pseudo-code de compression (français)
1. On prépare une table d'intervalles des probabilités de chaque caractères (basé sur sa fréquence). O(n)
Prob('lettre') = nombre d'occurence de la 'lettre'/nombre total de lettres
2. On affecte un intervalle à chaque lettre
3. Pour chaque lettre (de gauche à droite)
3.1 On calcule l'intervalle globale
3.2 On calcule la limite supérieure de probabilité du caractère
3.3 On ajoute la limite inférieur de la probabilité du caractère
Voici le pseudo-code de compression (code)
Encode(Message, BorneSupérieure, BorneInférieure) bas = 0 haut = 1 tant que pas EOF lire un symbole intervalle = (haut - bas) haut = bas + (intervalle * BorneSupérieure(car)) bas = bas + (intervalle * BorneInférieure(car)) fin Retour borne
Voici le pseudo-code de décompression (français)
Tant que le nombre est différent de 0 1. Trouver le 1er symbole en cherchant celui qui est le plus près de l'intervalle du message (le plus près) Ex. 0,2572 est le plus proche de l'intervalle 0,2 à 0,3 dans la table 2. On soustrait la Borne inférieure du symbole 3. On divise le résultat par la taille de l'intervalle du symbole
Voici le pseudo-code de décompression (code)
Décode(Nombre, BorneSupérieure, BorneInférieure) Tant que Nombre > 0 S = Symbole(Nombre) Ecrire (S) intervalle = BorneSupérieure(S) - BorneInférieure(S) Nombre = (Nombre - BorneInférieure(S)) / intervalle Fin
Exemple de table (pour le message 'Bill Gates')
Symbole Probabilité B.Inf. B.Sup. 'espace' 1/10 0,0 0,0999 'a' 1/10 0,1 0,1999 'B' 1/10 0,2 0,2999 'e' 1/10 0,3 0,3999 'G' 1/10 0,4 0,4999 'i' 1/10 0,5 0,5999 'l' 2/10 0,6 0,7999 's' 1/10 0,8 0,8999 't' 1/10 0,9 0,9999
Trace de codage
bas = 0,0. haut = 1,0. CHAR='B': intervalle = (1,0 - 0,0 ) = 1,0 . haut = 0,0 + (1,0 * 0,3) = 0,3 . bas = 0,0 + (0,0 * 0,2) = 0,2 CHAR='i': intervalle = (0,3 - 0,2 ) = 0,1 . haut = 0,2 + (0,1 * 0,6) = 0,26 . bas = 0,2 + (0,1 * 0,5) = 0,25 CHAR='l': intervalle = (0,26 - 0,25 ) = 0,01 . haut = 0,25 + (0,01 * 0,8) = 0,258 . bas = 0,25 + (0,01 * 0,6) = 0,256 CHAR='l': intervalle = (0,258- 0,256) = 0,002. haut = 0,256 + (0,002 * 0,8) = 0,2576. bas = 0,256 + (0,002 * 0,6) = 0,2572 ... bas = 0,2572167752 'B' = 0.2 à 0.3.
Trace de décodage
Nb = 0,2572167752. B. intervalle = 0,3 - 0,2 = 0,1. Nb = (0,2572167752 - 0,2) / 0,1
0,572167752 i. intervalle = 0,6 - 0,5 = 0,1. Nb = (0,572167752 - 0,5) / 0,1
0,72167752 l. intervalle = 0,8 - 0,6 = 0,2. Nb = (0,72167752 - 0,6) / 0,2
0,608376 l. intervalle = 0,8 - 0,6 = 0,2. Nb = (0,608376 - 0,6) / 0,2
0,041938 ' '.intervalle = 0,1 - 0,0 = 0,1. Nb = (0,041938 - 0,0) / 0,1
0,41938 G. intervalle = 0,5 - 0,0 = 0,1. Nb = (0,41938 - 0,4) / 0,1
0,1938 a. intervalle = 0,2 - 0,1 = 0,1. Nb = (0,1938 - 0,1) / 0,1
0,938 t. intervalle = 1,0 - 0,9 = 0,1. Nb = (0,938 - 0,9) / 0,1
0,38 e. intervalle = 0,4 - 0,3 = 0,1. Nb = (0,38 - 0,3) / 0,1
0,8 s. intervalle = 0,9 - 0,8 = 0,1. Nb = (0,8 - 0,8) / 0,1
0
Compression avec perte
Numérisation du son
Numérisation du son en onde continue en utilisant une coupe en intervalle de temps (fréquence) et un échantillonnage (quantité de point pour la hauteur des ondes) - intervalle de tension.
Notion de perte acceptable. L'oreille humaine détecte 20kHz. NyQuist dit qu'il faut doubler l'échantionnage (40kHz). On peut aussi ignorer les fréquences trop élevées ou trop basses non perçues par l'oreille humaine. Il faut éviter le phénomène d'alias (son qui est faux) où on prend des points qui ne représente pas la courbe. Le téléphone possède une basse fidélité (8kHz).
Keyword: bitrate, sampling frequency.
Compression JPEG
Image: forte compression avec perte acceptable et sans perte.
La compression avec perte acceptable utilise la modulation différentielle (différence de luminosité entre chaque pixel).
- 1- DCT (Discrete Cosine Transform). Modulation différentielle. Transforme le signal (pixels) en ne représentation de coefficients de fréquence (luminosité). (Pour le premier pixel, on compare avec le blanc). Il s'agit du principe d'entropie.
- 2- Quantifier (discrétiser ou arrondir les différence) pour avoir une perte acceptable. Identifier des parties d'informations qui peuvent être perdues sans affecter la qualité de l'image. Quantification: appliquer sur la matrice du coefficient des fréquences. Construit avec la matrice Quant(i,j). Idée: réduire le nombre de bis d'un entier (précision - perte). Discrétiser des valeurs proche de 0 permet d'obtenir beaucoup de 0 et donc de favoriser la compression sans perte.
- Compression de la matrice sans perte
Problème: ce processus est O(N^2) pour N pixels. Une solution est d'utiliser le Block Coding (algo diviser pour régner) en divisant l'image en tuile (de 8x8 par exemple). Il arrive cependant un autre problème, celui du Tile Effect. Il faut alors utiliser une autre technique pour corriger/atténuer le Tile Effect.
Codage JPEG
- Construire la représentation en valeurs relatives. Blocs adjacents se ressemblent. Diff.
- Arranger les coefficients en zig-zag
- Compression avec 2 méthodes. Séquences de 0 avec RLE et le reste avec huffman ou un codage arithmétique.
Résultat: 90% sans perte significative. 98% peu de perte significative.
Séquences Vidéo
Moving JPEG (M-JPEG: séquence de JPEG: très mauvais).
MPEG: Moving Picture Expert Group. Ajoute la compression dans la dimension du temps. Différentielle avec l'image précédente. 1ere image en JPEG. Coder la différence des images consécutives ou trop de diff. Nouveau JPEG diminuer de 15 à 20, 93 à 95%.
Frame rate: ex. 30 images/seconde.