105
Compression de données texte, son, image Pierre Jouvelot Centre de recherche en informatique Ecole des mines de Paris (C) M.S. HEC/Mines MSIT - 2006

Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

  • Upload
    others

  • View
    2

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Compression de données texte, son, image

Pierre Jouvelot

Centre de recherche en informatiqueEcole des mines de Paris

(C) M.S. HEC/Mines MSIT - 2006

Page 2: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot 2

Vers le tout numérique ...Le nouveau credo « 3A »:

« Anything Anytime Anywhere »

Internet, ou la mémoire immanente (anytime) et omniprésente (anywhere)Du monde réel analogique ... au monde virtuel numérique« De digitalis representatio rerum » (anything) ☺

Page 3: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot 3

Plan1. Introduction2. Théorie de l’information3. Compression de texte :

1. Codage entropique 2. Substitution textuelle

4. Compression du son :1. Codage2. Quantification3. Prédiction linéaire4. MPEG

Page 4: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot 4

Plan (fin)

5. Compression des images :1. Codage2. Fax3. JPEG4. MPEG

6. Conclusion

Page 5: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Introduction 5

IntroductionTypes de données :

analogiques (son, image)digitales (texte)

Codage en caractères dans un alphabet :compression : D vers C (< D)décompression : C vers (une approximation de) D

Digitalisation/échantillonage/numérisationApplications : stockage, communicationsCompromis : coût/compression

Page 6: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Introduction 6

Volumes et débits

Images fixes :1 Mo (576(l) x 720(p) x 25i/s)10 Mo (image film 35 mm)1 Go (film de 1h30)

Images mobiles :TV analogique (140 Mb/s)MPEG (5 Mb/s, qualité VHS)

Page 7: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Introduction 7

Types de compressionSans perte (lossless) :

textetraitement d’images (médecine)

Avec perte (lossy), pour données analogiques échantillonnées :

parole, musiqueimages

Performance :2:1 sans pertejusqu’à 1000:1 avec perte (fractal)

Page 8: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Introduction 8

Standards

ISO – IEC – CCITT/UITInteropérabilité accrueDiminution des coûts Implémentations logicielle/VLSIConvergence TPH/TV/InternetEtude de cas : fax CCITT G3

Page 9: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 9

L’information

Emetteur (ou source)CanalRécepteurMessage (ou suite de caractères)Référentiel (alphabet)... Surprise du message !

Page 10: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 10

Source

Modèle stochastique de sourceAlphabet A = {c1, ... cn} Chaine s = séquence finie de caractères émispi : probabilité d’émission de ci

Exemples : constante, p0 = 1, pi≠0 = 0aléatoire, pi = 1/n

Page 11: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 11

Ordre

Prise en compte du contexte :ordre 0 : probabilités indépendantesordre supérieur

Probabilité de « u » ?1% dans un modèle d’ordre 095% à l’ordre 1, après « q »

Page 12: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 12

Mesure d’information

Claude Shannon (Bell Labs, 1940) :

Plus de surprise, plus d’incertitude, plus d’information, plus de « bits »

Test de lecture (Shannon, 1950) : 1 caractère anglais sur 2 est inutile !Application : sources constante et aléatoire

Page 13: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 13

Entropie et codageSource S d’ordre 0, en bits :

H(S) = - Σ pi log2(pi)Application : sources contante et aléatoireThéorème du codage :

Coder un caractère de S nécessite, en moyenne, H(S) nombres binaires

Codage optimal : atteindre l’entropie pour des chaînes infiniment grandes

Page 14: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 14

Exemple de codage optimal

Source S sur A = {a, b, c}Loi de probabilité : ½, ¼, ¼ Codage « à la ASCII » : 00, 01, 10Entropie : H(S) = 1.5Codage optimal : 0, 10, 11Séquence « type » :

symboles : abac (biaisé)codes : 010011 (aléatoire)

Page 15: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Théorie 15

Du codage à la compression

Texte

Texte ASCII

CodeCodage

Codageéquiprobable

Compression

Page 16: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 16

Compression de texte

Source EncodeurCompresseur

Canal

Récepteur DécodeurDécompresseur

c

c0/1

0/1

Page 17: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 17

Types de codage

off-lineon-linetemps réel

Page 18: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 18

Code(Fonction de) code binaire f :chaîne → (0/1)*

Exemple :a → 1001b → 10ab → 10010abbb → 1

VLC = Variable Length CodingImplémentation par dictionnaire : trie, hachage

Page 19: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 19

Code sans perte

f sans perte si f injectif : décodable de manière uniqueIntroduction de virgules :

code unaire, avec 0 comme virgulereplacer chaque c par 0c, sauf le dernier, par 1cremplacer w par :(|w|-1)*0, 1, w (en unaire)

Peu efficace !

Page 20: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 20

Codes préfixes

Aucun code n’est préfixe d’un autreDécodable de manière uniqueDifférentes implémentations :

HuffmanCodage arithmétique (brevets)

Performances voisines en pratique

Page 21: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 21

Codage d’Huffman (1952)

Hypothèses :Source d’ordre 0Loi pi connue

Algorithme gloutonExemple de construction d’arbre :A = {a, b, c, d, e}, pi = {0,5; 0,2; 0,1; 0,1; 0,1}Optimal si pi en puissance de ½

Page 22: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 22

Codage arithmétique (1980)

Optimal pour tout pi

Chaîne = sous-intervalle de [0,1[A = {a, b, c}, pi = {0,2; 0,3; 0,5} :a → [0; 0,2[b → [0,2; 0,5[c → [0,5; 1[ac → [0,1; 0,2[bc → [0,35; 0,5[aca → [0,1; 0,12[ (envoyer 1, renormaliser)acaa → [0,0; 0,4[

Page 23: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 23

Codage d’ordre supérieur

Méthodes :opérer par blocs de k éléments de Sprobabilités conditionnelles (statistiques d’ordre k)

Mémoire importante : |S|k

Souvent utilisé pour Huffman (zip, par blocs : étage 2)

Page 24: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 24

Codage adaptatif

Source Encodeur/Compresseur

Canal

Récepteur Décodeur/Décompresseur

Modifieur demodèle

Page 25: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 25

Huffman adaptatif

Algorithme dynamique :Initialisation : caractères équiprobablesGestion d’une table de fréquencesReconstruction du dictionnaire

Codage optimal (à l’infini)Synchronisation ?Extension à l’ordre supérieur adaptatif (context modelling)

Page 26: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 26

Codage RLE

Run-Length Encodingn caractères identiques → (n, c)Applications :

fichier core (Unix)souvent utilisé (fax, JPEG)

Page 27: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 27

Substitution textuelleFamille d’algorithmesAlgorithme général :

D = init( A ) ;while not( eof()) do {s = input( D ) ; // plus longue chaîneoutput( code( s, D )) ;update( D, s ) ;

}

Politiques de gestion de D

Page 28: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 28

Dictionnaire glissant (LZ77)Lempel-Ziv (1977) Dictionnaire = input déjà analysécode( s, D ) = (d, l) :d = déplacement arrièrel = longueur reconnue maximum

init( A ) ?Optimal au sens de l’entropieUtilisations : zip (étage 1), PNG (Portable Network Graphics), Stacker, QIC (Quarter Inch Cartridge)

Page 29: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 29

Dictionnaire dynamique (LZ78)

Lempel-Ziv (1978)Dictionnaire = chaîne → intinit( A ) = {a→1 ; b →2}code( s, D ) = D(s)update( D, s ) ::= D + (s+premier caractère non reconnu, |D|+1)Optimal au sens de l’entropieApplications : man pages (Unix), V.42bis, GIF (Graphical Interface Format, LZW)

Page 30: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 30

Anticipation (lookahead)

Compression = parsingApproche greedy non optimaleExemple :D = {a, b, ab, bn }, input = abn

greedy : ab, n-1 fois boptimal : a, bn

Solutions : borner le lookahead, programmation dynamique

Page 31: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Texte 31

Résultats comparatifs

Codages entropiques voisinsApproches par substitution textuelle similairesAnticipation peu utile (qq. %)

Page 32: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 32

Codage du son

Son analogique = flux continu de données≠ MIDICodage discret :

Temps (échantillonage), en HzIntensité (quantification), en bits

Minimisation de la perte de codage

Page 33: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 33

TempsPlage audible : 20 Hz – 20 kHzThéorème Nyquist-Shannon :

Echantillonner au double de la fréquence maximum (fs = 2fmax)

Problème de l’aliasing :Repliement du spectre : f, fs+f, fs-fSawtooth (fs = 22.05 kHz) : 440, 880, 1760Oversampling, filtrage passe-bas

Page 34: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 34

Intensité

Echantillonage linéaire de tensionApplications (par seconde) :

parole 96kb : 8k samples, 12 bitsmusique CD : 44.1k paires, 16 bits

6 dB (= 10log10(S/N)) par bit Fréquence plus importante que la résolution

Page 35: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 35

Codage PCMPulse Code Modulation : di

Differential PCM : di-di-1

Adaptative DPCM :Donnée 16 bits d vers code 4 bits c di-di-1 ~ step*value[ c ] « step » adaptatifStandards CCITT bas débit (G.721-3)Fichiers WAV (Microsoft), téléphones DECT

« Bunny », PCM, 8 kHz, 16b, 128kbps « Bunny », ADPCM, 32kbps

Page 36: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 36

QuantificationQuantizationSource essentielle de compressionPartitionnement de l’espace de représentation R des données :

Ensemble de classes {c}Représentant de c : cookbookR( c )

Problème d’optimisation de codage : Trouver R tel d ~ cookbookR( c ) en minimisant la distorsion

Page 37: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 37

Quantifications scalaires

Linéaire : c = ⎣d/step⎦, d’ = c*stepLogarithmique : μ-Law, A-Law

Sensibilité non-linéaire de l’ouieMeilleure quantification à faible niveau, signaux plus probablesUtilisation PABX (96kb → 64 kb)« CQ », μ-Law, 64 kbps

Page 38: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 38

A-Law

12 bits vers 8 bits :SignePosition du bit de poids fort dans les 7 premiers 11 bits de magnitude4 bits suivants

Exemples :s1wxyzabcdefg → s111wxyzs01wxyzabcdef → s110wxyzs0000001wxyza → s001wxyz

Page 39: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 39

Quantification vectorielle

VQ, Vector QuantizationVaste choix d’approches :

quantification scalaire par composanteapprentissage : Linde-Buzo-Gray, réseaux de neuronesclustering (quadtree, ...)MCP

Page 40: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 40

Représentation de la voixLPC (Linear Predictive Coding)Voice coder : source un et filtreModélisation du signal sn :sn = Gun – Σk=1,p aksn-k

Codage par trame dn :Déterminer sn ~ dn minisant la distorsionAlgorithme de Durbin (1960)Coder/quantifier G, u, p, {ak}Quantifier le résiduel {sn-dn}

Page 41: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 41

Normes de compressionLPC bien adapté aux faibles débits LPC-10 (DoD) : 2.4 kbps, p = 10, un = bruit blancCELP (Code Excited LP) : 4.8 kbps, un = indice, MPEG-4GSM (Global System for Mobile) :

Données : 8 kHz, 13 bits PCMDébit 13 kbps, taux 8RTE-LTP (Regular Pulse Excitation – Long Term Prediction, 6 MIPS)

Page 42: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 42

MPEG-Audio

Motion Picture Expert GroupISO/IEC JTC1/SC29/WG11Norme audio IS 11172-3 (1991)3 niveaux (layers) de compression :

I – 192 à 384 kb/s/canal (DCC)II – 128 (DAB)III – variable de 32 à 128 (.mp3)

Page 43: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 43

Hypothèses de codage

Assymétrie : décodage aiséRetard de codage borné (<60ms)Performance croissante (I à III) : PCM, 705 kb/s/canal à MP3, 32 kb/sComplexité croissante : taux ~ 1:7 sans perte discernableCodeur non spécifié : MP3, ou une norme de représentation !

Page 44: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 44

Psychoacoustique

Perceptual CodingEffet de masquage fréquentielExemple :

1000 Hz + 1100 (-18 dB) ~ 10001000 + 2000 (-18 dB) 1000 + 2000 (-45 dB) ~ 1000

Page 45: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 45

Structure du codeur MP3

Filtrage

#bits/bruitallocation

quantificationHuffman

Formatage

Psycho-acoustique

Donnéesauxiliaires

Flux PCM

.mp3

Page 46: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 46

Pré-traitement

Trames de 1152 samples (.mp3)Découpage fréquentiel :

20 Hz à 20 kHzSubband Coding en 32 bandesLargeurs identiques (≠ AC3)ChevauchementPolyphase Quadrature Filter passe-bande unique

Page 47: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 47

Masquage psychoacoustique (1)

Modèle perceptuel empirique :

Si (∀ bande de fréquence B,bruit_de_quantification(B) < seuil_de_masquage(B))

alors compression « sans perte »

Détermination expérimentale des seuils : prise en compte de la sensibilité auditive

Page 48: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 48

Masquage psychoacoustique (2)

FréquentielTemporel (intensité > 40 dB) : pré (2 ms), post (100 ms)Tonalité : analyse des formantsCouplage entre canaux : (L,R), (L+R,L-R), (L+R, échelles)Adaptativité

Page 49: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 49

Codage .mp3

Adaptative Spectral Perceptual Entropy Coding1 trame = [g, {fi }] : gain, 32 facteurs d’échelleCalcul itératif fonction du débit:

Noise Control Loop (quantification)Rate Loop (codage d’Huffman)

Watchdog ou adaptation du modèle

Page 50: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 50

MPEG-2IS 13818-3 (1994)Plus de fonctionalités :

Fréquences de 8 à 96 kHzIntervalle de débits plus large (Low Sample Rate : 8 kbps)5.1 canauxCanaux multilingues~ 2 fois plus efficace (astuces de codage)

Compatible MPEG-1 + Advanced Audio Coding

Page 51: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 51

MPEG-4

Approche toolbox sonore (1998) :naturelle (voix, musique)synthétique

Profils spécifiques : Speech, Synthesis, Scalable, Main

Page 52: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 52

Sons naturels

Débits : 1.2 à 64 kb/sVoix :

HVXC (< 4 kb/s) CELP (< 24 kb/s)

Audio (et voix à haut débit) :TwinVQ (NTT)AAC

Page 53: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 53

Sons synthétiquesText-to-Speech (200 b/s à 1.2 kb/s)Structured Audio :

Synthèse (WAV, FM, physique)SA Orchestra Language (~ CSound)SA Score Language

Fonctionnalités :vitesse (à hauteur constante)hauteur (à vitesse constante)effets (réverb, spatialisation, ...)

Scalabilité

Page 54: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Son 54

Normes industrielles

AC-3 (Dolby) :Algorithme et codage propriétairesCompression psychoacoustiqueAdaptation : • bandes (#, largeur)• fenêtre temporelle d’analyse

Utilisation dans la norme DVD US

ATRAC (Sony), dans MiniDisk

Page 55: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 55

Codage des images

Picture element (pixel, pel)Espaces de représentation :

N&B binaire niveau de gris 8/16 bits couleur : vraie, palette (quantification), dithering

Image = tableau de pixels, carré ou non (pel aspect ratio, e.g. 4:3)

Page 56: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 56

Espaces de couleur

Normalisation CIERGB, YIQ, YUV, LAB, YC1C2, ...Découplage achromatique (1) et chromatique (2)

Facteur de transparence α

Page 57: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 57

RGB

3 composantes additives : terminal vidéoI = k Vγ (γ ~ 2.3)Peu adapté à lacompression

Page 58: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 58

YUV

Luminance (Yellow) Chrominance (U, V)TV PAL et JPEG(RGB) = M.(YUV)Clipping (<235 en Y)Forte corrélation

(U,V) avec Y = 0.5

Page 59: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Introduction 59

Y

V

U

YUV

Page 60: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 60

CCIR 601 (ITU-R BT.601)

Codage numérique qualité studio de signaux TV analogiquesCompatibilité TV actuelle :

US : 525 l/59.94 HzEu : 625 l/50 Hz

Echantillonage luminance 13.5 MHz

Page 61: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 61

Paramètres CCIR 601

Couleur :Chrominance Subsampling 4/2/1YUV 4:2:2 (Y1.Y2.Cb.Cr)8 bits par pel (216 Mb/s)

Débits :US : 480 l x 720 pel,

60 field/s (30 i/s non entrelacé)Eu : 576 l x 720 pel, 50 field/s (25 i/s)

Page 62: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 62

Fax Groupe 3/4

Norme CCITT/SG XIV ITU-T.4 (1980)Transmission numérique (G1/G2 analogiques) sur ligne TPHReprésentation :

Format A4, N&BNumérisation 200 dpi, 1188 lDébit 4.8 kb/s

Extensions : A3, 2D, vitesse

Page 63: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 63

Compression 1D

Codage d’Huffman statique d’un codage RLE unidimensionnelTables expérimentales l → (b, n) :

0 → (00110101, 0000110111)3 → (1000,10)63 → (00110100, 000001100111)

Découpage en blocs de taille 64Taux : 5 à 15 en pratique

Page 64: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 64

Option 2D

Prise en compte de ligne précédenteModified READ (Relative Element Address Designate) : codage des transitionsExemple du mode « pass » :

Code 001, avec a0 → a’0 (~ b2)

. . . . . . . . .

.a0

b1

a’0

b2

Page 65: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 65

JPEGJoint Photographic Expert GroupISO JTC1/SC29/WG1ITU-T.81 et ISO/IEC 10928 (1992)Objectifs :

Images fixes (gris, couleur)Utilisation humaineState of the art, general purposeParamétrable (format et non algorithme)Peu coûteux

Page 66: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 66

Codage

Indépendant de l’espace de couleurTraitement par canalImage f(x,y) : 0 ≤ x,y ≤ N-1Modes :

séquentielprogressifhiérarchique, pyramidal(sans perte)

Page 67: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 67

Performances

Adapté aux images réellesMeilleur que GIF (sauf dessin)Compression moyenne de 10 à 50Taux de référence (16 b/p) :

0.08 b/p (reconnaissable)0.25 b/p (moyen)0.75 b/p (excellent)2.25 b/p (quasi identique)

Page 68: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image ... et son ! 68

Spectre (clarinette, Sib)

Temps f(x) Fréquence F(a)

Page 69: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 69

Discrete Cosine Transformf(x,y) → spectre F(a,b), 0 ≤ a,b ≤ N-1Intérêts de la DCT :

Proche de l’optimum (KLT)Moins de discontinuités :DCT(f) = DFT(f+miroir(f))Calculs en réels, avec mode Fast DCT Inverse DCTConversion sans perte

Algorithme non spécifié dans la norme25% du temps de codage JPEG !

Page 70: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 70

Définition de la DCT

F(a,b) = C(a)C(b)/4 ∑x=0,N-1 ∑y=0,N-1

f(x,y)cos((2x+1)πa/2N)cos((2y+1)πb/2N)

avec :C(0) = 2/√NC(s) = 2√(2/N)

Page 71: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 71

Définition de l’IDCT

f(x,y) = ∑a=0,N-1 ∑b=0,N-1

C(a)C(b)/4F(a,b)cos((2x+1)πa/2N)

cos((2y+1)πb/2N)

Décomposition sur une base cos(x)cos(y)

Page 72: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 72

Base de la DCT (N = 8):cos((2x+1)πa/16)cos((2y+1)πb/16)

a

b

Page 73: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 73

Exemple de DCTImage 8x8(shift –128)

DCT 8x8(arrondi)

Page 74: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 74

Quantification

DCT par blocs de taille 8x8 :Localisation des effets de QRéduction de complexité

Matrice de coefficients : DC, 63 ACF(a,b), avec 3 bits de plus que f(x,y)Table Q(a,b), paramètre de quantification vectorielle

Page 75: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 75

Exemple de quantification

Q(a,b) typique

F(a,b)/Q(a,b)

Page 76: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 76

Codage des coefficients

DC : DPCM (signe+|difference|)AC :

Parcours « zig-zag »RLE adaptatif (# zéros, taille en bits du chiffre suivant)Huffman statique (table en paramètre)

Page 77: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 77

Chaîne JPEG

Découpage 8x8

DCT

Q

Codageentropique

.bmp

.jpg

tables

Page 78: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 78

Modes

progressif :sélection spectrale (basses fréquences)résolution (n MSB bits seulement)

hiérarchiquesans perte :

Pas de DCTPrédiction / contexte adaptatifCodage entropique de la différence

Page 79: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 79

OriginalDCDC, 1 ACDC, 2ACsDC, 3ACs7 MSB DC+5 MSB AC+6 MSB AC+7 MSB AC

JPEGprogressif

Page 80: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 80

Formats pseudo-standards

Pas spécifié dans la normeJPEG File Interchange Format (.jpg)TIFF/JPEGStill-Picture Interchange File Format

Standard ISO/IUTMulti-formats

Page 81: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 81

Evolution de JPEGJPEG-2 : inspiration MPEG-2 JPEG-3 : informations de DRMJPEG-LS :

LOw COmplexity LOssless COmpressionPrédictif avec contexte adaptatifCode de Golomb : (⎣x/m⎦, x mod m)Codage : (unaire, 0, binaire log2(m))

JPEG-2000 :Standard ISO/IEC/ITU (déc. 2000)Fondé sur la décomposition en ondelettes

Page 82: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 82

JPEG vs. JPEG-2000 : Lena

Original24 bpp

JPEG-20000.95 bpp

JPEG0.94 bpp

Page 83: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 83

MPEG

Motion Picture Expert GroupISO/IEC IS 11172 (août 1993)Indépendant des applicationsApproche toolkitMultimédia : Audio, Video, System, TestingNorme de format, pas d’algorithme

Page 84: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 84

Spécifications

Accès direct aux imagesFast Forward/ReversePlayback arrièreRobustesse aux erreursTemps-réelSéquences éditables

Page 85: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 85

Principes

Opportunités de compression :espace : transformation DCTtemps : compensation de mouvement

Incompatibilités :fort taux de compression (⇒ inter)accès direct (⇒ intra)

Page 86: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 86

Compression temporelle

Motion Compensation Prediction3 types de trames :

intra (I), key frameprédit (P), DPCM par rapport à (I,P)bidirectionnel (B), interpolé

Impact sur les performances :1.2 b/p intra (Motion JPEG)0.3 b/p inter

Page 87: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 87

IBP

Ordonnancement des trames

Impact sur la taille des buffers :Constrained Parameters BitstreamUne trame I toutes les 12 trames

Page 88: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 88

Prédiction temporelle (P)

Estimation de mouvement Block matchingMacroblocs 16x16 de prédiction (Y)Coûteux en temps de calcul :

Minimisation de la distortionPréfiltrage passe-basAlgorithme non défini par MPEG

Page 89: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 89

t-1 t

Vecteurs demouvement(t-1 → t)

Page 90: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 90

Interpolation temporelle (B)I0 → B1 → I2

Types d’interpolation B1 :intra = 128Forward_Predictedv(x) = I0(x+v)Backward_Predictedv(x) = I2(x+v)Averagevv’ = (FPv+BPv’)/2

Très fort taux de compressionRéduction du bruit (moyennage)Multirésolution temporelle

Complexité (calcul, mémoire)

Page 91: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 91

Image « I » résiduelle (P/B)

Page 92: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 92

Compression spatiale

DCTQuantification vectorielle :

Blocs 8x8Matrice de pas adaptative (par bloc)Distinction I et (P,B)

Zig-zag scanningCodage RLECodage entropique (tables uniques)

Page 93: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 93

Structure

6 couches fonctionnelles :séquence : accès SMPTEGOP : I...Iimage : unité de codageslice : resynchronisationmacrobloc : MCPbloc : DCT

Page 94: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 94

MPEG-2

IS 13818 (novembre 1994)Vidéo et audio 3-15 Mb/sDu« VHS » au « LaserDisc »CCIR-601 complet, entrelacementCompatible MPEG-1

Page 95: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 95

... De petites améliorations

MCP en ½ pel (interpolation)Modes multiples de scanning (entrelacement)Précision variable des DCQuantification non-linéaire des MBsParamétrage des tables entropiquesImages D (Y uniquement) : FFMeilleure gestion des buffers

Page 96: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 96

Scalability

Plusieurs couches de prioritéAdaptation à la puissance du récepteur (simulcasting)Quatre modes :

spatial, ou multirésolutiondata partitioning ~ progressifrapport S/N ~ hiérarchiquetemporel, avec taux de trames différent (e.g., gauche/droite avec prédication L/R)

Page 97: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 97

Profils et niveauxProfil :

Sous-ensemble de caractéristiquesSimple, Main (B), Main+, Next

Niveau (level):Contraintes sur les paramètresLow, Main, High 1440, HighMain : 720x480, 15 Mb/s, CCIR-601

Combinaisons : Profile x LevelApplications : Téléconf, CATV, HDTV, DBS

Page 98: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 98

Extensions MPEG-2

DSM-CC :Digital Storage Media – Control Commands Commandes interactivesIndépendance du support

Audio Non Backward CompatibleVidéo studio 10 bits/plan

Page 99: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 99

MPEG-3

Objectif : HDTV à 20-40 Mb/sRemplacé par ... MPEG-2

Page 100: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 100

MPEG-4

Ensemble de technologiesProduction, distribution et accès :TV numérique, synthèse, InternetTrois groupes visés :

auteurs : DRMISP : QoS, Delivery Multimedia Integration Framework (~ ftp)utilisateurs : interactivité, mobilité

Page 101: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 101

CaractéristiquesStandard IS 14496 (février 1999)Bande large : 5 kb/s – 4 Mb/sVidéophones, multimédia, VR, ...Profils vidéo :

naturel : Simple, Core, Main, ...synthèse : Facial Animation, Scalable Texture. Hybrid, ...

Techniques agressives : fractals, morphologie, ondelettes, ...

Page 102: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 102

Nouveaux conceptsObjets média :

Naturels vs. synthétiquesTêtes parlantes

Description hiérarchique de scènes : spatiale, temporelle, sprites (fond), ...QoS : bit rate, taux d’erreur, prioritéMultiplexage : FlexMux, TransMuxUtilisateurs : position, déplacement d’objets, langues

Page 103: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Image 103

Compression(s)Elements multiples : vidéo, mailles 2D/3D, textures, variations...Compression « classique » :

MPEG-2 (+ AVC = DivX)ondelettes

Objets synthétiques :Facial Definition ParameterFacial Animation ParameterBody AnimationPrédiction de mouvement des objets

Page 104: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Conclusion 104

Conclusion :Le futur de la compressionUne perpétuelle recherche d’améliorations :

Texte :Modélisation des sources (langage naturel)Pattern-MatchingBurrows-Wheeler Transform

Son : Sans perte (Apple Lossless, Shorten)

Compression d’images :JBIG, Fax JPEGMéthodes fractales

Page 105: Compression de données: texte, son, imagepj/Teaching/Compression/compression.pdf · Pierre Jouvelot Son 41 Normes de compression LPC bien adapté aux faibles débits LPC-10 (DoD)

Pierre Jouvelot Conclusion 105

Un exemple : La compression fractale

Transformation affinecontractante fPoint-fixe par itération de fSimilaritésPartitioned IteratedFunction Systems(1988)Trouver f ?