Compression

Co p ess o d’images
d ages
format JPEG

„1) Introduction (système de compression, les normes)

„2) Formats des images (les couleurs, formats [Link] …, QCIF … )

„3) JPEG (schéma de codage, modes de fonctionnement)

1
1) Introduction
„ Contexte : codage ou compression des images
numériques
éi

„ Pourquoi : réduction de la quantité d ’éléments

binaires représentant l ’information « image »
=> codage de source
Qté d' info.
info ima.
ima originale [bit]
Taux de comp. =
Qté d' info. ima. compressée [bit]

„ Finalité : archivage
g ou transmission
2
1.1) Système de compression

„ Codage de canal :
adaptation signal / canal, taux d ’erreur
’ ffaible
„ Codage de source, 2 types :
‹ Codage sans perte (« entropique »)
Ex. : Huffman, Lempel-Ziv, Arithmétique, …
=> taux de compression faible (1.5 à 2)
3
 ‹ Codage avec pertes (« irréversible ») :
Suppression des redondances
cad de l ’information inutile car :
) prévisible

) invisible par système visuel humain (SVH)

=> Taux de compression élevés (>10)

„ Exemple :
‹ image = « matrice de pixels »
‹ pixel = « picture element »
‹ pixel codé sur un octet
)8 bits => 256 niveaux de gris 28 = 256
) « 0 » => noir
i
) « 255 » => blanc 4
‹ image transmise en la balayant
(« Zigzag scan »)

A B
C X

‹ constat : le niveau de gris d ’un pixel dépend

souvent de celui de ses voisins
‹ idée : prédire X en utilisant A, B ou C
la base du codage MICD
(Modulation d ’Impulsions Codées Différentielles)
=> une phase
h d ’analyse
’ l d l ’image
de ’i
5
1.2) Les normes
„ Pourquoi : enjeux économiques pour les industriels
(Impositiond ’un standart, manipulation de mêmes données,
conception
ti d de « chips
hi »))

„ Par qui : organismes de normalisation

‹ UIT (Union Internationales de Télécom.)
ISO (International Standart Organisation)
CCITT (Comité Consultatif International Télégraphique et Téléphonique)
CCIR (Comité Consultatif International pour la Radiodiffusion),
) …
‹ Groupes de travail réunissant des :
administrations (France serics, UK-DFI, Germany-DBPT, ITAlIA, ...)
opérateurs (France Telecom, NTL, TERACOM Scandinavia, …)
i d t i l (Thomson, Philips, Grunding, Sony, Nokia, …))
industriels
diffuseurs (RTL, TF1, RAI-ARD, BBC-RTVE, SDT Sweden, …) 6
„ Comment :
‹ analyse
l d
du b besoin
i
‹ appels d ’offres
=> compétitions
étiti entre
t iindustriels
d t i l ett llaboratoires
b t i
‹ analyse des résultats par les commissions
=> sélection + décision
‹ Ex. calendrier pour MPEG2 :

7
 Historique Il y a, au fur et à mesure, complémentarité
entre les normes et complexification

„ Image fixe
‹ 1980 : Recommandation pour le fac similé
‹ 1992 : JPEG
)« Joint Photographic Expert Group »
) images couleurs et N&B (Ex : satellite
satellite, médicales
médicales, …))
) plusieurs modes (Ex : séquentiel, sans perte,
progressif,
p g , hiérarchique)
q )
) format image < (768x576)

) débits : de 8 M bit/s à 40 M bit/s

‹ 2000 : JPEG 2000

(débits inférieurs, haute robustesse aux erreurs de transmission,
description basé contenu, large gamme d ’images, interface avec
8
MPEG4, …)
„ Vidéo : visiophonie
‹ 1990 : H261
) téléphonie visuelle sur le RNIS [« ISDN »]
(Réseau Numérique
q à Intégration
g de Services,, 64 k bit/s)
) formats image CIF (« Common Intermediate Format ») et
QCIF (« Quarter CIF »)
) débits : px64 k bit/s (p : de 1 à 30)

‹ 1996 : H263
) débitsinférieurs car pour réseau LAN (28.8 k bit/s)
) formats image
g SQCIF,
Q , 4CIF,, 16CIF

30 images/s

9
„ Vidéo : archivage et diffusion
‹ 1988 : fondement de MPEG
)« Moving Picture Coding Experts Group »
) 3 parties : Vidéo,
Vidéo Audio et Système (le « stream »)
‹ 1993 : MPG1
) but: la qualité VHS sur un CD
CD-ROM
ROM (=> stockage)
débit bas de 1.5 M bit/s (ima. 352x288 + audio)
) un accès aléatoire au sein de la séquence

‹ 1994 : MPEG2
) but: diffusion de la vidéo (=> application télévisuelle)
) adaptation aux formats (« scalabilité »)
• taille image 4/3 16/9
• entrelacé ou non, formats [Link], [Link], [Link], compatibilité entre
niveaux de qualité (normale<-> HDTV) ….
) MPEG3, originellement prévu pour la HDTV (TV Haute
10
définition) est inclus dans MPEG2
MPEG2

‹ 1998 : MPEG4
) décomposition de la scène en éléments VOP
• VOP « Video Object Plane »
• chaque élément = une composante audio + une comp. Vidéo
• éléments réels ou de synthèse,
y , forme arbitraire,, …
• scalabilité
• une « boîte à outils de compression» pour les VOP
) débits : 5 k bit/s à 5 M bit/s pour la vidéo
2 k bit/s à 64 k bit/s pour l ’audio
‹ 2000 : MPEG7 pour le multimédia (… jusqu ’à la
description sémantique de la scène) 11
2) Les formats image
(représentations des images)
2 1) Echantillonnage et quantification
2.1)
„ Echantillonnage

‹ un signal continu
‹ diviser l ’axe des temps en intervalles réguliers
((discrétisation))
‹ échantillonnage uniforme => Te constante
12
„ Théorème de Nyquist (échantillonnage) :

‹ Période
Pé i d
d ’échantillonnage
trop grande
=> « aliasing »

‹
T
Te ≤
2
Fe ≥ 2 × F

13
„ Quantification :

‹ discrétisation de l ’axe vertical

‹ quantification uniforme :
d intervalles
des i t ll éégaux

‹ quantification non-uniforme
non uniforme ...
14
 2.2) Les modèles des couleurs
„ Bases :
‹ spectre
t de
d la
l llumière
iè visible
i ibl : 400 -700
700 nm
‹ oeil = une caméra
‹ excitation des neurones par :
) les batonnets (la luminosité)
) les cones (la couleur)

‹3types
yp de cones : 3 domaines de fréquences
q
=> 3 couleurs suffises
pour reproduire tout le spectre visible
=> 3 couleurs primaires

15
„ Modèles pour les images :
‹ RGB (« Red, Green, Blue »)
=> les couleurs primaires additives
‹ CMY (« Cyan, Magenta, Yellow »)
=> les couleurs p
primaires soustractives

„ Modèles ppour la vidéo,,

par transformation des RGB :
‹ YUV :
)Y : la luminance (image N&B)
) U,
U V : les chrominances (la différence entre
une couleur et un « blanc » de référence)
‹ YCbCr
‹ YIQ …. 16
2.3) Les types d ’images (fixes)
‹ binaire ou monochrome :
pixel codé sur « 0 » ou « 1 »
‹ couleur 24 bits :
pixel sur 3 octets (Ex. RGB)
256x256x256 couleurs possibles
‹ couleur 8 bits
256 couleurs possibles
=> tables de conversion des couleurs
(LUT « Look-Up Table)
‹ formats : GIF (couleur 8 bits, compression sans perte, animée),
JPEG (tous types, compression avec pertes)
TIFF (tous types, compression sans pertes)
P t i t (sans compression)
Postscript
BMP (par Microsoft, couleur 24 bits) 17
2.4) Les types de signaux vidéo
‹3 ttypes de
d signaux
i vidéo,
idé lles 3 composantes
t sontt :
) soit séparées
=>
> large
l b
bande
d + synchronisation
h i ti
) soit mixées (vidéo composite) => interférences

) S-VHS
S VHS ((mixage
i que d
des chrominances)
h i ) => compromis
i
‹ Vidéo analogique :
) NTSC
• 525 lignes/image dont 20 lignes de contrôle (TV ~320 lignes)
• image
i entrelacée
t l é
• 30 images/s, modèle YIQ
) PAL
• 625 lignes/image
• 25 images/s
g
• image entrelacée, modèle YUV
18
 ‹ Vidéo numérique
) sous-échantillonnage
sous échantillonnage de la chrominance :
• [Link] : pas d ’échant.
• [Link] : échant. horizontal
d ’un facteur 2
• [Link] : échant. horizontal
d ’un
’ n facte
facteurr 4
• [Link] :
– échant. horizontal et
vertical d ’un facteur 4
– positionnement du pixel
de chrominance

Y+Cr+Cb :

Cr+Cb :

Y : 19
) Normes pour la vidéo numérique
p q p par le CCIR
(« Consultative Committee for International Radio »)

progressif
if
• débit : ~165 M bits/s pour CCIR 601 (NTSC)
• CIF ~ qualité
q VHS
• format 4/3
20
) Normes pour la TV numérique
p q p par le ATSC
(« Advance Television Systems Comittee »)

1995 : la norme pour la HDTV ( « High Definition TV » )

21
3) JPEG
3.1) schéma général

22
3.2) DCT
„ Notion de fréquences :
‹ 1D
crêtes

‹ 2D

) horizontales

) verticales

) diagonales
23
„ DCT (« Discrete Cosine Transformation »)
‹ Transformation
Discrète en Cosinus
‹ changement de l ’espace de représentation :
passage du domaine spatial au domaine fréquentiel

64 pixels 64 coefficients
24
 „ DCT (suite), définitions
‹ DCT
A(u ) × A(v) 7 7 ⎛ (2 × i + 1) × u × π ⎞ ⎛ (2 × j + 1) × v × π ⎞
F (u , v) = × ∑∑ cos⎜ ⎟ × cos⎜ ⎟ × f (i, j )
4 i =0 j =0 ⎝ 16 ⎠ ⎝ 16 ⎠
⎧⎪ 1 si α = 0
A(α ) = ⎨ 2
⎪⎩1 sinon

‹ DCT iinverse

1 7 7
⎛ (2 × i + 1) × u × π ⎞ ⎛ (2 × j + 1) × v × π ⎞
fˆ (i, j ) = × ∑∑ A(u ) × A(v) × cos⎜ ⎟ × cos⎜ ⎟ × F (u , v)
4 u =0 v =0 ⎝ 16 ⎠ ⎝ 16 ⎠
⎧⎪ 1 si α = 0
A(α ) = ⎨ 2
⎪⎩1 sinon

25
„ DCT (suite)
‹ une décomposition sur
64 fonctions de base
( sous-images
(ou i d
de b
base))

bloc sous-images

26
„ DCT (suite)
‹ implémentation
) des algorithmes rapides de calcul
) transformation 2D ~~> 2 x transformations 1D

27
 3.3) Quantification
„ Pourquoi : SVH moins sensible aux hautes fréq.
„ Idée : moins de bits pour les coeff coeff. relatifs à ces fréq
fréq.
„ Quantification : F ' (u, v ) = ent [F (u, v ) / q(u, v )]
„ Reconstruction : F ' ' (u, v ) = F ' (u, v ) × q(u, v )
„ Ex. F (u, v ) = 45 [décimal] = 101101 [binaire] => 6 bits
‹ q(u, v ) = 4

‹ F ' (u, v ) = ent [45 / 4] = ent [11.25] = 11 [décimal] = 1011 [binaire] => 4 bits

‹ F ' ' (u , v ) = 11× 4 = 44 [décimal] => F" (u, v) ≈ F(u, v)

Une erreur de quantification existe

(cf. codage avec pertes) 28
„ Quantification uniforme : tous les q(u,v) égaux
„ Quantification non-uniforme : tables des q(u,v)
Vers les htes. Fréq.

pour la Luminance pour les Chrominances

‹ q(u,v) grand => quantification grossière
‹ tables ppeuvent-être transmises dans
l ’en-tête (« header ») de l ’image 29
3.4) Balayage en zig-zag (du bloc) Coeff. DC

Coeff. AC
des
Basses fréq.

„ Intérêt : former un vecteur

où
ù lles coeff.
ff
relatifs aux basses fréq.
sontt regroupésé
30
3.5) Codage DPCM des Coeff. DC
„ Méthode :
‹ regroupement
g p
des coeff. DC
‹ balayage
y g sous-image g :
gche->dte, haut->bas
‹ X : valeur à prédire
p
P(X) : prédiction de X
Ex. P(X)=A (cas le plus simple,
mode de base)
P(X)=(A+C)/2 …
‹ transmission de X-P(X)

„ Pourquoi
q : niveau de g
gris des p
pixels voisins sont
souvent proches 31
3.6) Codage des coefficients AC
„ Constat : apparition de longues plages de 0
après quantification

„ Méthode : codage
g de ces p
plages
g («Run Length g )
g Coding»

‹ un ensemble de p paires ((Coeff.,, Nb. de 0))

‹ fin d ’un bloc : paire (0, 0) :

32
3.7) Codage entropique

„ Principe :

‹ codeur « classique » :
un alphabet de mots de code de même longueur
(Ex. pour 8 symboles : 000, 001, 010, 011, 100, 101, 110, 111)

‹ codeur entropique :
) un alphabet de mots de code de longueurs différentes
(Ex. 00, 01, 10, 110, 010, 111, …)
) attribuer aux symboles les plus probables, les mots de
code les plus courts
) effet : réduction du coût moyen (débit [en bit])
de la transmission
33
Codage entropique avec JPEG
„ C ff DC :
Coeff.
‹ mise en correspondance :
valeurs coeff
coeff. /
taille du mot représentant [bit]
‹ Ex. : si DC=-9 => 4 bits
‹ transmission de la paire :
(Taille, Valeur)

„ Coeff. AC :
codage
d d
de H
Huffman
ff d
des paires
i (C
(Coeff.,
ff NbNb. d
de 0)

„ Table de Huffman (cad l ’alphabet

alphabet des mots de code ) :
‹pré-existante ou
‹construite (transmission dans l ’entête)
entête)
34
3.9) Les 4 modes d ’utilisation de JPEG

„ Mode séquentiel :
‹ lemode de base
‹ chaque plan est codé directement par un balayage
(gche->dt, haut->bas)

„ Mode sans p
perte :
‹ un codage sans perte
‹ utilisation d ’un
un prédicteur pour coder les coefficients
‹ taux de compression de 1,5 à 2

35
Les 4 modes d ’utilisation de JPEG
„ Mode progressif :
‹ idée : transmettre d ’abord une image de basse
qualité, puis l ’améliorer par des ajouts
j successifs
‹ 2 façons :
) sélection spectrale : transmettre d ’abord les coeff. DC
ett quelques
l coeff.
ff AC,
AC puisi d ’autres
’ t coeff.
ff AC
) approximations successives : transmettre d ’abord des
coeff. g
grossièrement q quantifiés,, p
puis les q
quantifier p
plus
finement et transmettre cette nouvelle information
„ Mode hiérarchique :
‹ répond aux besoins de « scalabilité » de certains
décodeurs (dans un même flot binaire : plusieurs
résolutions plusieurs modes
résolutions, modes, …))
‹ par l ’imbrication d ’opérations d’échantillonnages /
codages / décodages / interpolations

36
3.10) Exemples : 1
Image originale (300 Ko) Image compressée (10 ko)

Problème = effets
ff de blocs

37
3.10) Exemples : 2
Image originale Image compressée Image compressée
(193 Ko) QF 100 (56 ko) QF 75 (12 ko)

Image
Image
compressée
compressée
QF 50
QF 20
(8 ko)
((5 ko))
38