31
1 MIC 4220, Traitement numérique des signaux Mounir Boukadoum, Michaël Ménard et sources sur Internet 1 Compression de signaux numériques Basé sur L. Tan, le standard G.726 de l’UIT et plusieurs sources sur Internet MIC 4220, Traitement numérique des signaux Mounir Boukadoum, Michaël Ménard et sources sur Internet 2 Objectifs d’apprentissage Après ce cours vous serez en mesure: D’expliquer le principe de la compression de données De comprendre l’usage de particularités de la perception sensorielle humaine dans le processus d’encodage D’expliquer les algorithmes de compression μ-law, MIC, MICD, MP3 et JPEG D’implémenter plusieurs techniques de compression

Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

1

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 1

Compression de signaux numériques

Basé sur L. Tan, le standard G.726 de l’UIT et plusieurs sources sur Internet

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 2

Objectifs d’apprentissage

Après ce cours vous serez en mesure:

• D’expliquer le principe de la compression de données

• De comprendre l’usage de particularités de la perception sensorielle humaine dans le processus d’encodage

• D’expliquer les algorithmes de compression µ-law, MIC, MICD, MP3 et JPEG

• D’implémenter plusieurs techniques de compression

Page 2: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

2

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 3

Introduction

• Normalement, la qualité de représentation d’un signal numérique dépend de la taille de mot utilisée – Utiliser moins de bits augmente le bruit de quantification

• Cependant, on peut réduire le nombre de bits pour une qualité donnée en changeant leur signification par encodage.– Peut être interprété comme du filtrage algorithmique

• Avantages d’utiliser moins de bits:– Moins de mémoire pour emmagasiner les données

– Moins de bande passante pour transmettre les données

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 4

Quantification

12minmax

N

VV

• Rappels

• Les arrondis dus au processus de quantification peuvent être modelés par un signal de bruit d’amplitude entre +/2 et -/2 ajouté au signal

Page 3: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

3

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 5

Impact du bruit de quantification• Évalué par le rapport signal-sur-bruit

(signal-to-noise ratio ou SNR)

• Pour un signal sinusoïdal et un bruit de quantification gaussien :

10.79 20 ∆

• Le SNR diminue si estréduitdans

• On peut mitiger l’effet en diminuant aussi

– Possible si on peut « compresser » le contenu informationnel du signal

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 6

Compresser comment ?

• On peut : – Réduire la gamme dynamique ou le nombre de valeurs

du signal d’entrée par une transformation appropriée

– Exploiter la redondance de données (ex. les flux audio et vidéo, incluant les passages silencieux, le texte, etc.)

– Exploiter les particularités de la perception humaine

– Exploiter la corrélation entre données voisines dans un objet spatial ou temporel

Page 4: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

4

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 7

Types de compression

• Sans pertes– Le signal original peut être récupéré du signal

compressé

– Exploite uniquement la redondance des données ou utilise une transformation réversible

• Avec pertes– Le signal original ne peut être récupéré du signal

compressé

– Exploite la redondance des données et la perception humaine

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 8

Entropie 101

• Un évènement ou symbole qui survient avec

probabilité p possède une information

• L’entropie H est la quantité moyenne d’information dans chaque élément d’une ensemble de M symboles, chacun contribuant bits d’information : ∑– Donne le nombre moyen de bits requis pour représenter

chaque symbole

– Pour H donné, on peut modifier le nombre de bits de chaque symbole si les sont différents

Page 5: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

5

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 9

Encodage de Huffman

• Exemple de codage entropique

• Attribue moins de bits aux symboles fréquents et plus de bits à ceux qui apparaissent plus rarement

• Construit une table de codage (codebook) à partir de chaque ensemble de symboles et de leurs probabilités d’occurrence

• Efficace lorsque les probabilités d’occurrence varient beaucoup

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 10

Exemple d’encodage de Huffman• Chaine de caractères à encoder : « un sujet barbant »

• On commence par établir les fréquences des caractères selon une suite ordonnée :

• u:3, n:2, t:2, b:2, a:2, espace:2, s;1, j:1, e:1, r:1

• Ensuite, on construit un arbre binaire des fréquences en partant de la droite

u,2

t,2 n,2 b,2 a,2

sp,2r,1 e,1

2

s,1 j,1

2

4

44 6

7 10

16

• Finalement, on attribue 0 à chaque branche à gauche et 1 à chaque branche à droite

• Le code de Huffman de chaque lettre est obtenu en traversant l’arbre à partir du sommet

Page 6: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

6

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 11

Encodage de longueur• Remplace les occurrence répétées d’un symbole (runs) par

une structure contenant le nombre de répétitions (run length)

• Chaque run est remplacé par un code à trois caractères {@, symbole, nombre de répétions}

Ex. : eeeeeeetnnnnnnnn donne @e7t@n8

– Si un seul symbole est répété fréquement, on peut remplacerles autres symboles par {# de répétitions, symbole différent}

p. ex. : 0,2,1,-1,0,0,1,0,1,1,0,0,1,0,0,0,-1,0,0,… 0 donne

(1,2),(0,1),(0,-1),(2,1),(1,1), (0,1),(0,1),(2,1),(3,1)

• Créé pour éviter les longues séquences de 0 dans les signaux binaires autosynchrones (pour préserver l’horloge)

• Efficace si on a des runs fréquents

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 12

Compression-extension loi µ analogue

• Appelé aussi log-PCM (standard G.711)

• Compense pour le bruit de quantification constant pour N donné alors que le signal est d’amplitude variable– Amplifie les faibles amplitudes et compresse les grandes

afin de maintenir un SNR acceptable

• Usage standard en téléphonie

Compression loi µ

Quantification linéaire

Extension loi µ

x y yq xq

Page 7: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

7

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 13

Compression loi µ analogue

ln 1

ln 1

µ = 255 en téléphonie pour SNR=48 dB

1 1

Région d’amplification

Région d’atténuation

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 14

Exemple: µ-Law

piano_c3

8 bit -1

8 bit

bitB 161/8 bitB 8

bitB 8

8

8

Page 8: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

8

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 15

Exemple loi µ analogue

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 16

Loi µ binaire• Réduit la taille d’un signal modulé par impulsions

et codage (MIC ou PCM), typiquement de 12 à 8 bits

La pente de chaque segment est ½ celle du précédent

Page 9: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

9

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 17

Compression loi µ binaire• Format du code compressé :

S XXX ABDC

* X: Valeurs homogénéisées par la division progressive de la pente par 2

Segment Intervalle de quantification

Segment Code linéaire 12 bits* Amplitude en décimale Code compressé 8 bits

0 S0000000ABCD 0 à 15 S000ABCD

1 S0000001ABCD 16 à 31 S001ABCD

2 S000001ABCDX 32 à 63 S010ABCD

3 S00001ABCDXX 64 à 127 S011ABCD

4 S0001ABCDXXX 128 à 255 S100ABCD

5 S001ABCDXXXX 256 à 511 S101ABCD

6 S01ABCDXXXXX 512 à 1023 S110ABCD

7 S1ABCDXXXXXX 1024 à 2047 S111ABCD

Signe

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 18

Extension loi µ binaire• Pour µ = 255:Code compressé 8 bits Amplitude en décimale Segment Code linéaire 12 bits

S000ABCD 0 à 15 0 S0000000ABCD

S001ABCD 16 à 31 1 S0000001ABCD

S010ABCD 32 à 47 2 S000001ABCD1

S011ABCD 48 à 63 3 S00001ABCD10

S100ABCD 64 à 79 4 S0001ABCD100

S101ABCD 80 à 95 5 S001ABCD1000

S110ABCD 96 à 111 6 S01ABCD10000

S111ABCD 112 à 127 7 S1ABCD100000

Ex: 0000 1110 1010 → 0 1001101→ 0000 1110 1100Codage avec pertes!

Page 10: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

10

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 19

Exemple loi µ binaireSignal 12 bits

Encodé 8 bits

Décodé 12 bits

Erreur

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 20

MIC différentiel (DPCM en anglais)

• Encode la différence quantifiée entre la valeur actuelle du signal et celle obtenue par prédiction– Dans la forme la plus simple, la valeur prédite est

simplement la valeur précédente

• Gamme dynamique plus petite, demandant moins de bits que MIC

Quantification

Prédiction

Encodeur

+

x[n] d[n] dq[n]

[n][n]

+

-1

Page 11: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

11

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 21

Démodulation MICD

Quantification

Prédiction

Encodeur

+

x[n] d[n] dq[n]

[n][n]

+

-1

1

Prédiction

Décodeur +dq(n)

dq(n)

(n)

(n)

• Démodulation

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 22

Modulation delta

• Comme la DPCM mais la table de quantification a seulement 2 valeurs.

0, 1 0, 0

– On peut rendre la valeur de A adaptative:• Longue séquence de valeurs identiques di sgnal : A ↑

• Les valeurs alternent: A↓

• Erreur de quantification plus grande, mais peut être compensée par une plus grande fréquence d’échantillonnage et filtrage du signal modulé– Modultation sigma-delta

Page 12: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

12

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 23

MICD adaptative• Standard G.726

• Compression pour lignes téléphoniques

Quantificationadaptative

Prédictionadaptative

Encodeur

+

+x[n] d[n] I[n]

dq[n]

-[n]

[n]

[n]

QuantificationInverse adaptative

Adaptation de la Quantification

Prédictionadaptative

+I[n] dq[n] [n]

[n]

Quantificationadaptative

inverse

Adaptation de la Quantification

Encodeur Décodeur

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 24

Exemple MICDA

Page 13: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

13

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 25

Métriques de performance

• Permettent de comparer les différentes techniques de compression

• Ratio de compression: é

• Taux de transfert:

é M : nombre de bits par symbole

fs : fréquence d’échantillonnage.

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 26

Exemple

• Signal échantillonné à 8 kHz et encodé avec 12 bits par symbole.

– Sans compression :1: 1

é 12 8000

– Loi µ : /

/1.5: 1

é 8 8000

Page 14: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

14

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 27

Exemple

– MICDA /

/3: 1

é 4 8000

• Nombre de signaux peuvant être transmis sur un lien OC-192 (données utiles : 9.621504 Gbits/s) :– Sans compression: 100 224

– Loi µ: 150 336

– MICDA: 300 672

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 28

Compression MP3• MPEG (Motion Picture Experts Group) : Standard de

compression audio et vidéo créé en 1993

• MP3 (MPeg 1 audio layer 3) est la partie audio de MPEG 1

• Compression à pertes basée sur un modèle psycho-acoustique

• Procède en plusieurs étapes :1. Séparation du signal en bandes de fréquences

2. Filtrage perceptuel

3. Quantification à pertes

4. Formatage final

Page 15: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

15

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 29

Psychoacoustique 101

• La réponse en fréquence de l’oreille humaine est à seuils et non linéaire– Pour deux sons de

fréquences voisines, celui de plus grande amplitude a tendance à masque le second

– Pour deux sons d`amplitudes voisines, celui de plus grande fréquence a tendance à masque le second

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 30

• À chaque fréquence d’amplitude donnée correspond une bande de masquage qui s’élargit progressivement

• On peut exploiter le phénomène en divisant le spectre de fréquences en bandes et en ignorant les composants dont l’amplitude est en dessous du masque

Masquage fréquentiel

Page 16: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

16

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 31

• Après un son fort, il s’écoule un certain délai, qui augmente avec la fréquence, avant que l’on puisse entendre un son plus faible

Masquage temporel

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 32

Effet net

• S’il existe un son fort dans une bande, on peut ignorer les régions avoisinantes sans perte de perception

Page 17: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

17

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 33

Algorithme MP3

1. La banque de filtres décompose le signal audio (e.g., son à 48 kHz) dans 32 bandes de fréquence (sub-band filtering)

2. Le modèle psychoacoustique détermine le masquage de chaque bande par les bandes voisines.

3. Si l’amplitude d’une bande est inférieure au seuil de masquage, elle est ignorée; sinon on détermine le nombre de bits pour représenter le coefficient avec un bruit de quantification sous le seuil de masquage.

4. Le formatage de sortie dépend du niveau de compression désiré

Banquede filtres

Masquagepsychoacoustique

Quantificateurlinéaire

Formatage desortie

Input Output

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 34

Example de masquage et quantification

• Amplitudes des 16 premières sous-bandes sur 32 à sortie du filtred’entrée :

Sous-Bande

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Amplitude 0 8 12 10 6 2 10 60 35 20 15 2 3 5 3 1

• Selon une table de perception psycho-acoustique, l’amplitude de 60 dB pour la 8e sous-bande (60 dB) donne un masquage de 12 dB dans la 7e sous-bande et 15dB dans la 9e

• L’amplitude de la 7e sous-bande est 10 dB (< 12 dB ), on l’ignore

• L’amplitude de la 9e sous-bande est 35 dB (> 15 dB ), on la garde

• Seules les amplitudes au dessus du seuil de masquage sont considérées• Au lieu d’utiliser 6 bits pour l’encodage, on peut utiliser 4 bits en moyenne,

soit deux bits d’économie (= 12 dB de gain sur SNR)(Si chaque valeur est représentée par une paire (taille en bits, valeur), alors : 10, 60, 35 (1, 0), (6, 60), (6, 35))

.

Page 18: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

18

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 35

Encodeur MP3

Banquede filtres

Sélection du facteur d’échelle

Modèle de masquage

Quantification*

FFT

0101..MUX

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 36

Quantificationinverse

Expansion

Décodeur MP3

Facteurd’échelle

Modèle de masquage

Filtrage enBanque inverse*0101..

DEMUX

*

Page 19: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

19

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 37

Couches MPEG

• Couche 1 et 2

• Couche 3

Banquede

filtres

Quantificateurlinéaire

Formatage de trame

TFR (1024 pts)

Modèle psycho-acoustique

Info sur le codage

Banquede filtres

Quantificateurnon-linéaire

Formatage de trame

TFR (1024 pts)

Modèle psycho-acoustique

Info sur le codage

TCDM (transformée en cosinus discrète

modifiée

Codage deHuffman

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 38

Transformée en cosinus discrète (TCD)

• Pour un signal à symétrie paire, la transformée de Fourier possède un composant imaginaire nul :

• On peut créer un signal à symétrie paire en dédoublant tout signal numérique de durée finie N (ce qui double ses valeurs)

Le spectre de fréquence obtenu est donné par la TCD :

dtttxdtetxjX tj cos)()()(

12,...,1,0

2

12cos

2

1

2

1 12

0

NkN

knnx

NkX

N

n

k

Page 20: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

20

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 39

Transformée en cosinus discrète modifiée

• La TCD opère sur des séquences finies– Phénomène de Gibbs

aux extrémités

• On réduit l’effet avec des séquences entrecroisées, chacune multipliée par une fenêtre .

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 40

Transformée en cosinus discrète modifiée

• TCDM:

2 cos2

0.5 /4 0.5

1cos

20.5 /4 0.5

• Noter que les deux suites sont symmétriques par rapport à N/2

fenêtre

Page 21: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

21

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 41

Codage en MPEG audio

12 échantillons

DonnéesMIC

Filtre bande 0

Filtre bande 1

Filtre bande 31

12 échantillons

12 échantillons

12 échantillons

12 échantillons

12 échantillons

12 échantillons

12 échantillons

12 échantillons

Trame couche 1

Trame couche 2 et 3

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 42

Format des trames• Couche 1

• Couche 2

• Couche 3

Entête(32)

CRC(0,16)

Allocation des bits(128-126)

Facteurs d’échelle(0-384)

Données Autreinfo

Entête(32)

CRC(0,16)

All. des bits(26-256)

Fact. d’échelle(0-1080)

Données Autreinfo

Entête(32)

CRC(0,16)

Autre info(136-256)

Données

SCFSI(0-60)

Information générale

Information sur le codage des données

Données

Optionnel

Page 22: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

22

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 43

MPEG Coding Specifics• MPEG Layer I

– Filter is applied one frame (12x32 = 384 samples) at a time. At 48 kHz, each frame carries 8ms of sound.

– Uses a 512-point FFT to get detailed spectral information about the signal. (sub-band filter). Uses equal frequency spread per band.

– Psychoacoustic model only uses frequency masking.

– Typical applications: Digital recording on tapes, hard disks, or magneto-optical disks, which can tolerate the high bit rate.

– Highest quality is achieved with a bit rate of 384k bps.

• MPEG Layer II– Use three frames in filter (before, current, next, a total of 1152 samples). At 48

kHz, each frame carries 24 ms of sound.

– Models a little bit of the temporal masking.

– Uses a 1024-point FFT for greater frequency resolution. Uses equal frequency spread per band.

– Highest quality is achieved with a bit rate of 256k bps.

– Typical applications: Audio Broadcasting, Television, Consumer and Professional Recording, and Multimedia.

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 444

MPEG Coding Specifics

• MPEG Layer III– Better critical band filter is used

– Uses non-equal frequency bands

– Psychoacoustic model includes temporal masking effects, takes into account stereo redundancy, and uses Huffman coder.

Stereo Redundancy Coding:

– Intensity stereo coding -- at upper-frequency sub-bands, encode summed signals instead of independent signals from left and right channels.

– Middle/Side (MS) stereo coding -- encode middle (sum of left and right) and side (difference of left and right) channels.

Page 23: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

23

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 454

Efficacité

*Quality factor: – 5 – perfect– 4 - just noticeable– 3 - slightly annoying– 2 – annoying– 1 - very annoying

Layer Target bit-rate

Ratio Quality* at

64 kbps

Quality at 128 kbps

Layer I 192 kbps 4:1 -- --

Layer II 128 kbps 6:1 2.1 to 2.6 4+

Layer III 64 kbps 12:1 3.6 to 3.8 4+

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 46

Encodage JPEG

• JPEG (Joint Photographic Experts Group) : Standard international pour la photographie crée en 1988

• Technique de compression à pertes qui préserve une bonne qualité d’image

• L’algorithme JPEG combine le filtrage de fréquences avec la perception psycho-visuelle – La vision humaine présente une réponse en fréquence à

seuils et non linéaire• Moins sensible au couleurs qu’à l’intensité

• Peu sensible aux hautes fréquences spatiales

Page 24: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

24

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 47

L’algorithme JPEG

RGB  YCrCb(Cr et Cb sontéchantillonnés à fy/2)

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 48

Codage JPEG

DCT

IDCT

Quantiser

Dequantiser

EntropyEncoder

EntropyDecoder

Channelor

Storage

reversezigzag

zigzag

An8x8

block

Image

8 pixels

8 p

ixel

s

• La compression subséquente du signal YCrCb est accomplie à deux niveaux : la troncation des coefficients et le codage entropique.

• Le décodage JPEG suit la procédure inverse du codage.

Page 25: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

25

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 49

Implémentation de la TCD

• Une TCD à 2D est requise

• Pour un bloc de pixels de taille NxN, on a:

• À l’instar de la TFD, la TCD décompose un signal en une série pondérée de fonctions harmoniques, dans ce cas des cosinus.

1N

0v

1N

0u

uu

N2

v1y2cos

N2

u1x2cosv,uF

2

1)y,x(f

TCD :

TCDI :

1N

0y

1N

0x

uu

N2

v1y2cos

N2

u1x2cosy,xf

2

1

N

2)v,u(F

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 50

TCD 2-D• La TCD 2-D peut être séparée en un produit de deux

TCD 1-D.– on calcule d’abors une TCD 1-D en utilisant les rangées du

bloc à transformer ; ensuite, on calcule une deuxième TCD 1-D en utilisant les colonnes du résultat.

• La même technique s’applique au calcul de la TCDI.

• 1ère TCD 1-D :

• 2ème TCD 1-D :

i, j, k, l = 0, 1, 2, …, N-1.

1N

0i

k

j N2

k1i2cosj,ix

2

1

N

2kX

1N

0jj

k

N2

l1j2coskX

2

1

N

2l,kX

Page 26: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

26

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 51

Raw Block of Pixels

Final result after DCT by columns Result after DCT by rows

128

128

125

127

127

130 128 134 130 128 128

128128130134128130

126 130 127 130 131 128 127

127127

131

131

131

129

129

128

130129

132

133131

129

126127

130

134131129

131

124 128

132

129 134134 136 136 137 134 132

132135140137138136135133

365

365

362

359

368

370

378

383

-1

-1

-3

-3

1

0

-3

-1

-4

-4

-4

-3

1

-3

-6

-6

1

1

0

0

-1

-3

0

2

-3

-3

-3

-3

1

1

-1

-1

-2

00-3

1

1

-3

-3

1

-1

-3

2

0

-2

-1

-1

3

3

1

1

-1

-2

2

-3

pixel[n]

An 8x8block

Part of a picture

Columns (256 pixels)

Row

s (2

56 p

ixel

s)

pixel[256+n]

pixel[n+1]

1024

-18

11

0

-2

-4

0

2

-4

-1

-11

-1

1

-5

2 2

1 1

-3 -3

0 -1

0 1 0

-2

-1

1 0 -1 -1 -2

0 -1 -1 -1

011-1

-3 -1 0 -2

3-2-23-3

0 1

-1

-12

0

0 -4 -6 0 1

0

2 4-22

Données brutes

DCT par lignes

Résultat final, après DCT par colonnes

TCD 2-D

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 52

Quantification des coefficients

• Chaque coefficient de la TCD obtenue est divisé par un entier entre 1 and 255 et le résultat est arrondi.– Les diviseurs sont emmagasinés dans un tableau choisi de

manière à utiliser juste la précision nécessaire (# bits) pour chaque coefficient.

• Le tableau de quantification accompagne le fichier compressé.

• La quantification est la raison principale faisant quela compression JPEG est à pertes

Page 27: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

27

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 53

Tableau des coefficients de quantification pour la luminance

Tableau des coefficients de quantification pour la chrominance

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 54

Example de quantification128 128 128 128 128 128 128 128

118 111 112 117 120 123 123 122

125 121 115 111 119 119 118 117

120 121 113 113 125 124 115 108

120 120 116 119 124 120 115 110

117 113 111 122 120 110 116 119

109 113 111 122 120 110 116 119

111 121 124 118 115 121 117 113

-80 4 -6 6 2 -2 -2 0

24 -8 8 12 0 0 0 2

10 -4 0 -12 -4 4 4 -2

8 0 -2 -6 10 4 -2 0

18 4 -4 6 -8 -4 0 0

-2 8 6 -4 0 -2 0 0

12 0 6 0 0 0 -2 -2

0 8 0 -4 -2 0 0 0

16 11 10 16 24 40 51 61

12 12 14 19 26 58 60 55

14 13 16 24 40 57 69 56

14 17 22 29 51 87 80 62

18 22 37 56 68 109 103 77

24 35 55 64 81 104 113 92

49 64 78 87 103 121 120 101

72 92 95 98 112 100 103 99

-5 0 0 0 0 0 0 0

2 -1 1 1 0 0 0 0

1 0 0 -1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

Matrice de quantification

Données brutes

Valeurs quantifiées

DCT

1

2

Division

Page 28: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

28

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 55

Arrangement en zigzag• Fait pour que les coefficients

soient ordonnés par ordre croissant des fréquences.

• Optimise l’encodage des séquences créées à l’étape de quantification.– Permet d’obtenir des

séquences de mêmes chiffres (e.g. 0), ce qui simplifie les codages RLE et Huffmansubséquents

-5 0 0 0 0 0 0 0

2 -1 1 1 0 0 0 0

1 0 0 -1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0,2,1,-1,0,0,1,0,1,1,0,0,1,0,0,0,-1,0,0,… 0

Peut être encodé en RLE sous le format {# zéros à sauter, prochaine valeur 0} :

(1,2),(0,1),(0,-1),(2,1),(1,1),(0,1),(0,1),(2,1),(3,1),EOB

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 56

Codage des coefficients La coefficients DC de blocs sucscessifs sont codés en

MICD, et les coefficients AC de chaque bloc en RLE

Pour le bloc pris en exemple, on a Séquence AC :

0,2,1,‐1,0,0,1,0,1,1,0,0,1,0,0,0,‐1,0,0,… 0

(1,2),(0,1),(0,‐1),(2,1),(1,1), (0,1),(0,1),(2,1),(3,1),EOB

Séquence DC :

À supposer que les coefficients DC des 5 premiers blocs de l’image sont 150, 155, 149, 152, 144, alors par codage MICD :

150, 155, 149, 152, 144  150, 5,‐6, 3, ‐8

Page 29: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

29

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 57

Codage entropique

Appliqué aux séquences codées DC and AC pour

plus de compression. Dans l’exemple, chaque coefficient DC codé en MICD est

représenté par une paire (taille, amplitude), où taille est le

nombre de bits pour le représenter et amplitude sa valeur :

150, 5, −6, 3, −8   (8, 10010110), (3, 101), (3, 001),     

(2, 11), (4, 0111)

Seule taille subit une codage de Huffman ; pour amplitude, 

il y a trop de variations pour un codage efficace

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 58Chap 9 Image Cpression Standards

Formatage final

Page 30: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

30

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 59

Exemple

Q=10083261 Bytes

Q=5015138 BytesQ=259553 BytesQ=104787 Bytes

Q=11523 Bytes

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 60

Sommaire• La compression permet de réduire le représenter les données avec

moins de bits tout en conservant un rapport signal-sur-bruit donné ou une perception acceptable

• Les techniques peuvent exploiter la gamme dynamique des données, leur redondance, ou la perception humaine – La loi µ permet de réduire le nombre de bits pour l’encodage en utilisant une

échelle non-linéaire.

– L’encodage de Huffman utilise des longueurs de mots variables selon la fréquence des données

– L’encodage RLE remplace les valeurs répétées par leurs comptes de répétition

– La MICD encode la différence entre le signal d’entrée et un signal prédit.

– La MICD adaptative permet de réduire encore plus le nombre de bits en ajustant la quantification et la prédiction.

– Les encodages MP3 et JPEG utilisent une combinaison de techniques

Page 31: Compression de signaux numériquesboukadoum_m/MIC4220/Notes/9... · 2014-12-03 · S XXX ABDC * X: Valeurs homogénéisées par la divi sion progressive de la pente par 2 Segment

31

MIC 4220, Traitement numérique des signaux

Mounir Boukadoum, Michaël Ménard et sources sur Internet 61

Prochain cours

• Problèmes:– 11.1, 11.5, 11.9, 11.13, 11.21, 11.29, 14.16, 14.17