Université Ferhat Abbas,Sétif

Faculté des Sciences de l’Ingénieur

Département d’électronique

Mini projet sur :

La Compression JPEG d’images fixes

Mise en œuvre sous Matlab sur une image fixe de niveau gris 8bits

Par : Azoug Seif Eddine

2éme année master réseaux et systèmes de télécommunication

Date : 01-01-2011

TABLE DES MATIERES :

I. Introduction

II. Rappel sur l’image numérique

II.1 Définition

II.2 Notions de pixel et espace de couleur

III. Rappel sur la compression des images

III.1 Compression sans pertes

III.2 Compression avec pertes

III.3 Processus général d’un codec d’images fixes

IV. Notions sur la transformé DCT

IV.1 Définition

IV .2 Variantes de la DCT

IV .2.a DCT I

IV .2.b DCT II

IV .2.c IDCT

IV.3 Propriétés de la DCT en compression d’image

IV.3.a Décorrélation

IV.3.b Concentration des coefficients

IV.3.c Symétrie, séparabilité, et orthogonalité

V. Processus général d’un codec JPEG d’images fixes

V.1 Définitions

V.2 JPEG basée sur la DCT séquentielle

V.2.1 Découpage en sous blocs

V.2.2 Décalage de niveau (Level Shifting)

V.2.3 Application de la DCT

V.2.4 Quantification

V.2.5 Codage des coefficients DC et AC

V.2.5.a Les coefficients DC

V.2.5.b Les coefficients AC

V.2.6 Codage Huffman

VI. Mise en œuvre sous Matlab

VI.1 Représentation des images sous Matlab :

VI. 2 Code final

VI.3 Résultats

VII. Conclusion

VIII. Référence

I. Introduction :

De nos jours, les images numériques sont omniprésentes dans notre

quotidien(photographie numérique, web, imagerie médicale…etc), leurs utilisations sous

format brut rendent leurs portabilités difficiles (temps de transmission long) et leurs

stockages encombrant (nécessité de plus de mémoire) ce qui revient à un cout élevé, c’est

pour cela qu’il a fallu trouver de nouvelles techniques de compression et codage d’image

adaptées.

Grâce aux progrès atteint dans la théorie du codage et de la compression des donnés, les

images peuvent maintenant être compressées en faisant enlever ce qui est redondant sur la

base d’algorithmes de compression intelligents en exploitant plusieurs aspects technique

présents sur les données de l’image (redondance psychovisuel, interpixel…..) afin de réduire

le poids de l’image, cela nous fera gagner de l’espace en mémoire et une augmentation du

débit de transmission (temps de transmission moins long). Aujourd’hui, on trouve plusieurs

algorithmes de compression d’images comme par exemple: .jpg ou .jpeg, .png, .gif, .tiff,

jpeg2000 …etc…

Dans ce projet, nous allons essayer de revoir le principe de l’algorithme de compression

« JPEG » en mode opératoire séquentielle, et enfin sa mise en œuvre pratique de base sur

une image fixe monochrome à l’aide du logiciel Matlab.

II. Rappel sur l’image nume rique :

L’acquisition d’une image se fait par moyen d’un appareil photo ou une prise d’un film sur

une caméra (suite d’images). La nature brute de l’image à la sortie des capteurs est un

signal analogique qui doit être discrétisé (numérisé) pour pouvoir l’exploité par un

processeur de données numériques.

La source peut être aussi une image artificielle, dans ce cas, le signal de l’image est d’origine

discret, comme un schéma de dessin industriel sur un logiciel CAO par exemple.

II.1 Définition :

Une image numérique est un signal bidimensionnelle (a deux dimensions, largeur plus

hauteur) fini discret (préalablement échantillonné et quantifié) qui peut être assimilé tel

vue sur un écran d’ordinateur à une matrice I [MxN] finie où chaque élément I(mi,nj) de

cette matrice représente un point ou un élément de l’image (appelé : pixel) qui appartient à

un espace de couleur fini.

Compression Décompression

II.2 Notions de pixels et espace de couleurs :

L’acronyme pixel c’est la contraction de « Picture element », il représente un point de

l’image. La clarté ou la définition de l’image est proportionnelle aux nombres de pixel, c’est

la résolution d’une image.

Pour une image de bonne qualité la résolution doit être au minimum de 300px/2.54cm

(2.54cm = 1 Pouce).Par ex le nombre de pixel dans une image de résolution 640x480 pixel:

640x480 = 307200 pixels

Chaque pixel est représenté dans un espace de couleur finis. Pour une image de niveau gris,

par exemple, chaque pixel est représentée sur une échelle de 256 niveaux de gris où

chaque niveau représente l’intensité de la luminosité du pixel. Cet espace de couleur

nécessite 8 bits pour être coder (2^8=256), c’est des images 8 bits.

Typiquement pour un espace de couleur RVB (Rouge,Vert,Bleu) ,une image chromatique

nécessite pour chaque pixel trois couches de niveaux de luminosité des trois couches de

couleurs RVB. Cela nécessite au total 3*8 = 24bit pour codé un pixel, où chaque couleur de

pixel est représentée sur une échelle de près de 16 millions de niveaux de couleurs (2^24),

Problème : Le poids des données de l’image numérique sont proportionnelles à la

résolution de l’image.

Solution : Compresser les données de l’image numérique.

III. Rappel sur la compression des images :

La compression des données ou le codage source, permet on appliquant des algorithmes de

compression spécifiques de réduire la taille d’une image sur une mémoire ou de manière

équivalente de réduire son temps de transmission.

Image originale

Ligne de transmission

Image reconstituée

Mémoriser Demander

Figure III.1 Principe de la compression image

Mémoire

La compression peut être sans perte, l’image restera fidèle à l’image originale, soit elle sera

avec perte de qualité (fidélité) pour réduire plus la taille de l’image, dans ce cas-là, la

compression sera au prix de la dégradation autorisée, ces types de compression sont faites

grâce aux redondances des données présentes sur l’image. Ces redondances sont :

-Redondance psycho visuel : Des détails non perceptible à l’œil humain qu’on peut éliminer

(cf. caractéristiques de la vision humaine).

-Redondance inter pixel : La possible corrélation existante entre les pixels de l’image, on dit

qu’une image a une redondance inter pixel si c’est possible de prédire la valeur d’un pixel

en connaissance de la valeur des pixels voisins (suivants ou précédant), sachant que plus la

résolution de l’image est grande plus la probabilité de rencontré des redondance inter pixel

est élevée.

-Redondance de codage : séquences de répétition des bits, on rencontre cela généralement

à la fin de la compression, pendant l’étape de codage.

III.1 Compression sans perte :

Appelée aussi compression non destructrice, la qualité de l’image après décompression est

la même que celle de l’image originale, le taux de compression de ce type est limité.

Ce type de compression on le trouve beaucoup dans le domaine où la précision est majeure

comme l’imagerie médicale (IRM par ex.) ou la télédétection (imagerie satellite par ex.).Les

algorithmes de compression employés sont nombreux, les plus importants sont:

-Codage à répétition : par ex. RLC (Run Length Coding)

-Codage entropique :

basé sur le codage à longueur variable ou VLC (Variable Length Coding), par ex : le codage

de Huffman,le codage arithmétique,…etc..

-Codage dictionnaire ou codage Lempel-Ziv-Welch (LZW) :

Ce codage ne nécessite plus de connaitre les probabilités des symboles comme dans le cas

du codage entropique.

III.2 Compression avec perte :

C’est une compression destructrice, elle permet de sacrifier certains détails de l’image non

récupérable en décompression au profit de réduction de poids. Cette dégradation peut être

contrôlée selon la qualité qu’on veut obtenir en fonction du taux de compression choisie.

Canal de transmission

Décodage Canal

Décodage Source

Image reconstituée

𝑓 𝑥 𝑦

Ce type de compression on le trouve généralement dans le domaine normal pratique là où

la réduction du poids de l’images est très important, comme le domaine multimédia par

exemple (web, photographie) où la fidélité envers l’image original n’est pas très importante

et le taux de compression sera plus grand que celui d’une compression sans perte du fait

qu’on est juste limité par la qualité qu’on souhaite obtenir.

Les algorithmes de compression employés sont nombreux, on cite l’une des méthodes les

plus utilisées: Le codage par transformation.

Ce type de codage fait appel aux transformées mathématiques pour avoir une

« cartographie » des fréquences spatiales présentes dans l’image.

La transformé de cosinus discrète DCT et la transformé en ondelettes sont les transformées

les plus utilisées.

III.3 Processus général d’un codec d’images fixes :

Le schéma suivant illustre le processus général d’encodage et de décodage d’une image fixe

sur un système de communication :

Codeur

Décodeur

Figure III.2 Processus d’un codec d’images fixes

Le codec (codeur/décodeur) de source c’est le block qui nous intéresse, du fait que c’est sur

ce bloc que la compression-codage /décompression-décodage aient lieu.La présence du

codec canal a pour but contrairement au codage source d’ajouter des redondances au code

afin d’augmenter l’efficacité de la transmission en utilisant des codes détecteurs et/ou

correcteurs d’erreurs (code de parité, code de Hamming…etc…).

Image originale 𝑓 𝑥 𝑦

Codage Source

Codage Canal

Canal de transmission

Image originale 𝑓 𝑥 𝑦

décomposée en sous blocs

NxN

Codage par transformation Quantificateur Codage des

symboles Vers Codage

Canal

Le schéma général du bloc codec source d’images fixe est le suivant:

a) Codage par transformation (Transform Coding):

Après décomposition de l’image en sous-blocs NxN à cause de la non efficacité et la lenteur

des calculs d’un seul bloc entier, on applique une transformé linéaire (DFT, DCT,…etc…) qui

permet de transformer les sous blocs NxN de l’image a un format non visuel afin d’obtenir

des coefficients dans un domaine fréquentiel (une représentation fréquentiel de l’image)

qui seront codés et quantifiés. Le but du codage par transformer est d’avoir un autre aspect

de la distribution des données de l’image et ainsi décelé les redondances potentiel comme

la redondance inter pixel.

b) Quantificateur (Quantizer):

Le quantificateur permet de faire une pondération des coefficients de la transformé en se

basant sur une table de quantification (une table de luminosité et une autre de

chrominance) qui a été établit sur les caractéristiques de la vision humaine, les coefficients

de cette table imposeront un seuil de qualité qui décidera des coefficients de la transformé

qu’on veut garder et ceux qu’on veut supprimer jugées non important visuellement, d’une

autre manière, cette étape permet de choisir le taux de dégradation visuel qu’on souhaite

faire à l’image (Facteur de qualité), et le but de tous cela c’est d’éliminer la redondance

psycho visuel.Cette étape se trouve seulement dans les compressions avec perte.

c) Codage des symboles (Symbols coding) :

Cette étape permet de réduire la redondance de codage en utilisant des codes VLC ou

autres.

Le décodage source : c’est les mêmes blocs des schémas précédents mais dans le sens

inverse et chaque bloc effectue l’opération inverse de celle au codage.

IV. Notions sur la DCT :

Nous allons parler seulement de certains aspects importants à connaitre pour l’achèvement

de l’objet de ce travail qui est la compression d’images sans entrer dans les démonstrations

mathématiques.

Fig III.3 Codage source d’images fixes

IV.1.Définition :

La DCT ou Discret Cosine Transform, c’est une transformé linéaire qui a été appliquée la

1ére fois dans la publication des professeurs [N. Ahmed, T. Natarajan, and K. R. Rao,

"Discrete Cosine Transform", IEEE Trans. Computers, 90-93, Jan 1974].

C’est une variante de la transformé de Fourier discrète, qui permet de garder seulement les

cosinus et d’éliminer les Sinus, c’est-à-dire, obtenir une représentation fréquentiel

purement réel. Cette transformé est très largement utilisée dans la compression audio et la

compression image comme JPEG et MPEG.

IV.2.Variantes de la DCT :

Il existe 8 variante de la DCT, ceux les plus connus sont DCT I,la DCT 2D ou DCT II et sa

transformé inverse IDCT ou DCT III, nous allons voir la définition de la DCT I,DCT II et DCT III

qui sont la base de la compression JPEG.

IV.2.1DCT I :

Pour une séquence d’éléments discrets N, la DCT I s’exprime par :

∑ 𝑓 𝑥 ⌈

⌉

{

√

√

}

IV.2.2 DCT II :

C’est une extension directe de la DCT I dans deux dimensions 2D,NxN, qui seras notre

image, sa formule mathématique est donnée par :

∑ ∑ 𝑓 𝑥 𝑦 ⌈

⌉ ⌈

⌉

𝑓

On remarque si : ⇒

∑ 𝑓 𝑥 𝑦

Ce coefficient représente le coefficient DC, et le reste des coefficients représente les

coefficients AC, nous allons voir après ce que cela signifie en compression JPEG.

IV.2.3 IDCT:

Ou DCT III, elle est l’inverse de la DCT II, sa formule est donnée par :

𝑓 𝑥 𝑦 ∑ ∑ ⌈ 𝑥

⌉ ⌈

𝑦

⌉

IV.3 Propriétés importantes de la DCT en compression d’image :

IV.3.1 Décorrélation :

La DCT permet de réduire ou d’éliminer la redondance inter pixel,les pixels sont

décorrolés afin de réduire la variance des pixel voisins dans l’image ce qui permet une

compression efficace on codant chaque pixel indépendamment.

IV.3.2 Concentration des coefficients :

La DCT est très efficace pour des images fortement corrolée du fait qu’elle permet de

compacté les coefficients qui représente les basses fréquences dans une seule partition de

la matrice image, cela permet la séparation des fréquences basses des fréquences hautes,

et si c’est une image faiblement corrolée, les coefficients sont concentrés dans plusieurs

différentes partitions de la matrice image.

IV.3.3 Symétrie, séparabilité, et orthogonalité :

La DCT II peut être séparée comme suit :

∑ ⌈ 𝑥

⌉ ∑ 𝑓 𝑥 𝑦 ⌈

𝑦

⌉

De on peut sortir la propriété de symétrie qui va nous conduire à une expression

simplifiée du calcul de la DCT:

𝑓

𝑓 𝑥 𝑓

∑ ⌈

⌉ ∑ ⌈

⌉

A ce stade, on peut conclure avec la propriété d’orthogonalité :

va nous permettre d’avoir l’IDCT de la forme suivante :

𝑓 𝑓 𝑓

On remarque qu’on obtient la matrice image originale au final. Ces propriétés réduisent

considérablement les calculs dans les algorithmes de compression d’image du fait que ces

éléments seront déjà calculés à l’avance (calcul de la matrice C).

V. Processus ge ne ral d’un codec JPEG d’images fixes :

V.1 Définition :

JPEG: Joint Photographic Experts Group.

C’est un algorithme standard de compression avec perte d’image fixe établit en 1991 basé

sur le codage par la transformé en cosinus discrète DCT, et il existe plusieurs modes

opératoires de compression JPEG établies selon la rapidité du codec et le besoin

-Codage basé sur la DCT séquentielle

-Codage basé sur la DCT progressive

-Codage sans perte

-Codage hiérarchique

V.2 JPEG basée sur la DCT séquentielle :

Celui que nous allons aborder sur ce travail c’est celui basé sur la DCT séquentielle, où

l’image est traitée de gauche à droite et de haut en bas, la figure Figure V.1 montre le

processus d’un codec Source JPEG.

⇒

Codeur Source

Décodeur Source

Figure V.1 Codec Source JPEG

V.2.1 Découpage en sous blocs :

L’image au début elle est découpée en sous-bloc de 8x8 (ou 16x16), chaque sous-

bloc seras traiter individuellement, si c’est une image couleur il faut avant tout faire une

transformation couleur ensuite un sous échantillonnage, nous n’allons pas s’étaler sur ce

sujet.

Image originale

Divisision de l'image en sous-bloc 8x8

(ou 16x16)

DCT 2D 8x8

(ou 16x16) Quantificateur

Coéfficients DC: Codage prédéctive

DPCM

Coéffcients AC: scan Zig-Zag +

codage RLC

Codage entropique:

Huffman

Canal de transmission

Décodage entropique: Huffman

Coéffcients AC: décodage RLC+

scan Zig Zag inverse

Coéffcients DC: inverse DPCM

Quantificateur inverse

IDCT 8x8

(ou 16x16)

Fusion des sous blocs 8x8

(ou16x16)

Image décompressée

𝑓 𝑥 𝑦

Table de

quantification

Table de quantification Table codage Huffman

Offset

Offset

V.2.2 Décalage de niveau (Level Shifting) :

Deuxième étape, préréglage (offset), en effectuant un décalage de niveaux, en

anglais « Level shifting » (pour une image monochrome, c’est les niveaux du gris codés sur

8bits), où chaque élément de chaque sous blocs doit être amené à l’intervalle *-128,127],

pour faire cela, on soustrait à chaque élément un scalaire 128, cela va permettre

d’augmenter la tolérance de précision des coefficients de la DCT.

V.2.3 Application de la DCT :

L’étape suivante, Appliquer à chaque sous bloc la transformé DCT 2D ( DCT II ) N = 8

(ou N=16) ,le résultat une matrice de 8x8 fréquences (ou 16x16),cette transformé va

permettre de séparer les hautes fréquences des basses fréquences, on aura 64 coefficients

(ou 256), le premier coefficient de la matrice représente le coefficient continue DC ou le

fondamental du sous bloc de l’image, c’est le coefficient de la fréquence nulle dont

l’amplitude est la plus élevée et le reste des coefficients ce sont des coefficients AC

décroissant si on tend vers les hautes fréquences.

Le fait de séparer les fréquences hautes et les fréquences basses va ainsi permettre la

décorrélation des pixels de chaque sous bloc de l’image et ainsi réduire la redondance inter

pixel, sachant que la transformation seul sans quantification et codage n’est pas une

compression, ce n’est juste qu’une étape post-compression !

V.2.4 Quantification :

La prochaine étape, la quantification, on fait une division euclidienne ( entre les

blocs DCT et une table de quantification déjà calculée sur la base d’un facteur de qualité

(50% par ex.)

[

]

Cela a pour but d’éliminer les coefficients haute fréquence dont l’œil humain est peu

sensible, seulement ceux présent en dessous du seuil définis par la table de quantification

auront des amplitudes très faibles (éliminatoire), ces coefficients seront arrondis à l’entier

prêt qui est souvent 0, d’ailleurs, si on prend par exemple la table de quantification de

luminosité normalisée standard JPEG suivante calculé sur un facteur de qualité FQ = 5:

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

On remarque que les coefficients en hautes fréquences seront divisés sur un nombre élevée

(en rouge), et ceux en basses fréquences seront diviser sur un nombre moins élevé (noir).

V.2.5 Codage des coefficients DC et AC :

Maintenant qu’on a les coefficients DCT quantifiés et arrondis, les coefficients AC et

coefficients DC auront deux codages différents avant de subir le codage entropique de

Huffman.

V.2.5.a Les coefficients DC :

Ils seront codés par un codage prédictif DPCM par ex., ce type de codage

permet de prédire la valeur du coefficient DC de chaque sous bloc selon la connaissance de

la valeur du coefficient du bloc précédant ou des blocs précédents.

Par exemple, si on a la suite des coefficients DC de chaque sous blocs suivante:

555558888899999, son codage prédictif sera : 50000300001000.

Ce codage nous permet d’avantage de réduire la redondance inter pixel, et pour des raisons

de simplicité et de ce qu’il nous a été demandé de faire, nous allons négliger cette étape

dans notre manipulation Matlab.

V.2.5.b Les coefficients AC :

Figure V.3 Scan zig-zag

Les coefficients AC seront récupérer sur un vecteur par un scan en zig-zag de la

matrice de chaque sous bloc afin de mettre les coefficients élevées en premier et les

zéros en fin comme illustré dans la figure V.3.Ensuite, ces coefficients seront codés

par le codage RLC (Run Length Coding) où les suites de coefficients AC qui se suivent

de même valeurs sont codées par leurs nombre de redondance sur la séquence par

ex :

Zig-zag :

-25 2 2 2 2 1 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 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0

RLC : -25 @ 5 2 1 0 1 @ 5 0 -1 EOB

EOB (End Of Block) veut dire le reste des coefficients de la matrice sont à zéros, et @ suivis

du nombre de redondance de la valeur qui suit, par exemple : @ 5 0 veut dire que c’est une

suite de cinq 0.

Enfin, les deux vecteurs DC et AC seront réunis sur un même vecteur pour le codage

entropique Huffman.

V.2.6 Codage Huffman

L’étape finale, c’est le codage Huffman, qui va compresser le vecteur RLC à la limite de la

compression sans perte (VLC).Le codage Huffman se déroule en deux étapes :

1ére étape : Construire l’arbre de Huffman en classant les probabilités de chaque symbole

de haut en bas, et on additionnant les probabilités faibles pour obtenir un autre symbole et

ainsi de suite jusqu’à il en reste que deux probabilités.

Coefficient DC

2éme étapes : consiste en l’encodage des symboles en partant de l’inverse où on s’est

arrêté on assignant des 0 et 1 à chaque symbole jusqu’à construire la table de codage de

chaque symbole, par ex :

-25 [0,1,1,1]

-3 [0,1,1,0]

-1 [0,0,0,1]

0 [1,0]

1 [0,1,0]

2 [0,0,0,0]

5 [0,0,1,1]

EOB [0,0,1,0]

@ [1,1]

En général cela est basé sur une table Huffman standard au JPEG déjà prête, mais dans

notre cas, on va calculer nos tables de codage. Au final nous auront un vecteur de suite de 1

et 0 qui représente l’image compressée JPEG.

Img_comp = [0 1 1 1 0 1 1 … 0] ;

Dans le processus de décodage, c’est l’inverse de toutes les étapes précédente en

commençant par le décodage Huffman jusqu’à la DCT inverse (IDCT) pour reconstituer

finalement l’image.

VI. Mise en œuvre sous Matlab :

J’ai utilisé la boite à outils de traitement d’images (Image Processing Toolbox) de Matlab

pour l’opération de lecture, conversion et affichage des graphiques.

VI.1 Représentation d’images sous Matlab :

Dans la boite à outils (Image Processing Toolbox) de Matlab,ils existent quatre type de base

d’images qu’on peut manipuler.

II.1.a Image Binaire (Binary):

C’est une image interprété par une matrice logique I de dimension MxN où chaque

élément ou pixel de l’image peut prendre uniquement la valeur 1 (Blanc) ou la valeur 0

(Noir).

II.1.b Image de niveaux gris (Grayscale):

Elle est interprétée par une matrice I[MxN] où chaque élément de la matrice I donne

le niveau d’intensité sur une échelle de niveau de gris selon le type de la matrice,

pratiquement, c’est le type préféré en traitement d’image non chromatiques (uint8 en

général la structure des données utilisée).

II.1.c Image de couleur réel ou RVB (Truecolor RGB)

Cette image est interprété par une matrice multidimensionnelle I[MxNx3] chaque

pixel I(mi,nj) en a des composantes en couleurs RVB non indexées comme suit :

R : I(mi,nj,1) V : I(mi,nj,2) B : I(mi,nj,3)

Ce type peut être décomposé en trois couches d’image de niveaux de gris où chaque

couche est traitée comme une matrice distincte.

II.1.d Image indexée

C’est une image interprétée par une matrice I * MxN+ qui contient l’indices des pixels

de l’image et une matrice K* Mx3+ qui contient la palette des couleurs de l’image

(colormap).Chaque ligne de K donne le niveau d’intensité du Rouge, du Vert, et du Bleu, de

chaque pixel pour reconstituer sa couleur unique. Ce type peut être converti en RVB(RGB)

réel ou en niveau de gris (Grayscale) par les fonctions prêtes de la boite à outils image de

Matlab : ind2rgb et ind2gray

VI.2 Le code Matlab final :

Ce programme est modulaire, composé d’un script d’exécution principale : codec_jpeg.m et

des scripts suivants : init_jpeg.m init_indices_zigzag.m codage_jpeg.m decodage_jpeg.m .

codec_jpeg.m

% \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ % Programme basique sur la compression JPEG d'image fixe monochrome

% Version : 1.0 % Par: Azoug SeifEddine % http://dynelectrons.net76.net % dynelectrons@dynelectrons.net76.net % Fait le: 01/01/2011 % \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ clear % Chargement de la matrice image monochrome sur Matlab qui seras sous format entier

uint8 % et la convertir en double pour les calcul img_originale = double(imread('zohrap.bmp'));

% Si Image a un espace de couleur RVB ou autre que monochrome,elle doit étre convertie % img_originale = rgb2gray(img_originale);

dim_bloc = 8; %dimension 8x8 des sous blocs init_jpeg; % Déclaration et initialisation des variables nécéssaires (voir:

init_jpeg.m)

%Décodage et décompression (Voir: codage_jpeg.m) codage_jpeg

%Décodage et décompression (Voir: decodage_jpeg.m) decodage_jpeg

%Affichage de l'image originale,de sa DCT,et de l'image décompressé. figure(1) subplot(1,3,1) imshow(uint8(img_originale)) title('Image Originale'); subplot(1,3,2) imshow(jpeg) title('DCT'); subplot(1,3,3) imshow(uint8(img_decompresse)) title('Image décompressée'); figure(2) subplot(2,2,1) imshow(uint8(img_originale(112:120,120:128))) title('Sous bloc de l''mage Originale'); subplot(2,2,2) imshow(uint8(img_decompresse(112:120,120:128))) title('Sous bloc de l''mage Compressée');

%Evalutation du Taux de compression for i=1:8:m for j=1:8:n eval([ sprintf('taille_img_compresser = taille_img_compresser +

numel(hcode_%d_%d);',i ,j)]); end end

taille_originale = dim_img taille_img_compresser taux_compression = taille_originale / taille_img_compresser

%Evaluation de l'erreur quandratique moyenne EQM somme=0; for(i=1:m) for(j=1:n) somme=somme + ((img_originale(i,j) - img_decompresse(i,j))^2); end end EQM=somme/(m*n)

%Calcul de la valeur créte du rapport signal sur bruit Peak to noise ratio PSNR bit=8; PSNR=10*log10(((2^bit-1)^2)/EQM) %Calcul des bits par pixel Bpp. bpp = taille_img_compresser / dim_img % Fichier image compressé / nombre de pixels

init_jpeg.m

% Déclaration des variables et initialisation des constantes jpeg = ones(size(img_originale)); % Matrice JPEG qui va contenir l'image compressée jpeg_deco = ones(size(jpeg)); % Matrice qui va contenir l'image décompressé offset = ones(dim_bloc,dim_bloc)*128; %Matrice 8x8 pour "Level Shifting". DCT = dctmtx(dim_bloc); % Matrice C pour le calcul de F

% récupération des dimensions de l'image. [m,n] = size(img_originale); dim_img = m*n;

%Matrice ou table de quantification Q (Standard JPEG) quantizer =... [... 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 ... ];

%Vecteur du scan Zigzag zigzag = ones([1 dim_img]); %Fonction de récupération des indices du scan zigzag (voir init_indices_zigzag.m) [col lig] = init_indices_zigzag(dim_bloc); %Vecteur du codage/décodage RLE et codage/décodage Huffman rle = []; rle_deco = []; huff_deco = [];

% Constantes utiles taux_compression = 0; taille_img_compresser = 0; dec_l = 0; dec_c = 0; redondance = 0; col_rle_p = 1; k = 1; z =1; d=0;

init_indices_zigzag.m

%Cette fonction permet de créer deux matrices %Une matrice ligne lig et une matrice colone "col" %Chaque matrice va contenir respectivement indices ligne et colonnes %Ces indices vont aidé a faire le scan zig zag pour un sous bloc 8x8. function [col,lig]=init_indices_zigzag(dim_bloc) col = ones([1 (dim_bloc * dim_bloc)]); lig = ones([1 (dim_bloc * dim_bloc)]); lig(1) = 1; k=2; r=1; for x=3:2:dim_bloc for j=1:x lig(k) = j; k = k + 1; end for j=x-1:-1:1

lig(k) = j; k = k + 1; end

for j=1:x-1 col(r) = j; r = r + 1; end for j=x-2:-1:1 col(r) = j; r = r + 1; end

if(x == 7 ), x = x+1; for j=1:x lig(k) = j; k = k + 1; col(r) = j; r = r + 1; end

for j=x-1:-1:1 col(r) = j; r = r + 1; end

for z=2:2:x for j=x:-1:z+1 lig(k) = j; k = k + 1; end for j=z:x lig(k) = j; k = k + 1; end for j=z:x col(r) = j; r = r + 1; end if(z ~= dim_bloc) for j=x:-1:z+1 col(r) = j; r = r + 1; end end

end

end

end;

codage_jpeg.m

%Boucle général qui va parcourir l'image en sous bloc 8x8 for i=1:dim_bloc:m dec_l = i-1; %Décalage vertical des sous blocs

for j=1:dim_bloc:n dec_c = j-1; %Décalage vertical des sous blocs jpeg(i:i+7,j:j+7) = img_originale(i:i+7,j:j+7) - offset; % Effectuer le "Level

Shifting". jpeg(i:i+7,j:j+7) = DCT * jpeg(i:i+7,j:j+7) * DCT'; % Appliquer DCT

(cf.[7]).

jpeg(i:i+7,j:j+7) = jpeg(i:i+7,j:j+7) ./ quantizer; % Division par la table

Q. jpeg(i:i+7,j:j+7) = round(jpeg(i:i+7,j:j+7)); % Arrondir à l'entier

le plus prés.

for q =1:64 zigzag(k) = jpeg(lig(q)+dec_l,col(q)+dec_c); % Effectuer un scan

ZigZag. k = k + 1; end

d = k - 64; q = 1; while(q <= 64) % Boucle While qui effectue un codage RLC sur chaque

sous bloc if (d < dim_img) && (zigzag(d) ~= zigzag(d+1)) rle(z) = zigzag(d); d = d + 1; q = q + 1; z = z + 1; elseif (d < dim_img) && (zigzag(d) == zigzag(d+1)) &&

(zigzag(d+1) ~= zigzag(d+2)) rle(z) = zigzag(d); rle(z+1) = zigzag(d+1); d = d + 2; q = q + 2; z = z + 2; elseif (d < dim_img) && (zigzag(d) == zigzag(d+1)) &&

(zigzag(d+1) == zigzag(d+2))&& (zigzag(d+2) ~= zigzag(d+3)) rle(z) = zigzag(d); rle(z+1) = zigzag(d+1); rle(z+2) = zigzag(d+2); d = d + 3; q = q + 3; z = z + 3; elseif (d < dim_img) && (zigzag(d) == zigzag(d+1)) &&

(zigzag(d+1) == zigzag(d+2))&& (zigzag(d+2) == zigzag(d+3)) redondance = 4; rle(z) = 257; rle(z+1) = redondance; rle(z+2) = zigzag(d); d = d + 3; q = q + 4;

while (q <= 64) && (d < dim_img) && (zigzag(d) == zigzag(d+1)) redondance = redondance + 1; q = q + 1; d = d + 1; end rle(z+1) = redondance; d = d + 1; z = z + 3; end if(q == 64) q = q+1; end end

% Début du codage Entropique de Huffman. col_rle = z-1; %Extraction des symboles uniques présent dans le vecteur %RLC. symboles = unique(rle(col_rle_p:col_rle)); nbr_symboles = numel(symboles); taille_block = numel(rle(col_rle_p:col_rle));

%Calcul des probabilités de chaque symboles. table_p = ones(1,nbr_symboles); for q = 1:nbr_symboles itter = 0;

for r = col_rle_p:col_rle if(rle(r) == symboles(q)) itter = itter + 1; end end table_p(q) = itter / taille_block; end %Dressage de l'arbre de huffman et codage de chaque %symbole de chaque sous bloc. eval([ sprintf('dico_%d_%d = huffmandict(symboles,table_p);', i ,j)]);

eval([ sprintf('hcode_%d_%d = huffmanenco(rle(col_rle_p:col_rle),dico_%d_%d);', i ,j,i

,j)]); col_rle_p = col_rle+1;

end

end

decodage_jpeg.m

%Décodage Huffman for i=1:dim_bloc:m for j=1:dim_bloc:n eval([ sprintf('huff_deco = [huff_deco huffmandeco(hcode_%d_%d,dico_%d_%d)];', i

,j,i ,j)]); end end %Décodage RLE i = 1; k = 1; while(k <= numel(huff_deco))

if(huff_deco(k) == 257) rle_deco(i:(i-1+huff_deco(k+1))) = huff_deco(k+2); i = i + huff_deco(k+1); k = k +3; else rle_deco(i) = huff_deco(k); i = i +1; k = k +1; end end k=1; for i=1:dim_bloc:m dec_l = i-1; for j=1:dim_bloc:n dec_c = j-1; %Scan zigzag inverse for q =1:64 img_decompresse(lig(q)+dec_l,col(q)+dec_c) = rle_deco(k); k = k + 1; end %quantification inverse + IDCT + Remises des niveaux (Inverse %Level Shifting) img_decompresse(i:i+7,j:j+7) = img_decompresse(i:i+7,j:j+7) .* quantizer; img_decompresse(i:i+7,j:j+7) = DCT' * img_decompresse(i:i+7,j:j+7) * DCT; img_decompresse(i:i+7,j:j+7) = img_decompresse(i:i+7,j:j+7) + offset; end

end

VI.3 Résultats :

Voici les résultats pour cette image de niveau de gris 8bit 232x256 pixels de format

BMP (volumineux) et de taille 59392 bits :

FigureVI.1 Compression JPEG

taille_originale = 59392bits

taille_img_compresser = 47453bits

taux_compression = 1.2516

EQM = 25.6932 PSNR = 34.0326 bpp = 0.7990

On remarque que la taille de l’image a été compressé avec un taux de compression de 1.25

ce qui est acceptable on aurait pu avoir plus si on aurait pris une image plus corrolée que

celle-ci. On remarque aussi que la DCT dans chaque sous blocs elle fait une concentration

des coefficients basses fréquences (en blanc).

L’image n’a pas perdu de sa fidélité apparente, cela étant seulement visuellement

apparent, parce que l’erreur quadratique moyenne n’est pas nulle et égale à EQM = 25.69

cela veut dire qu’il y’a une erreur d’une différence moyenne de 25.7 environs entre les

éléments des deux matrices images mais elle n’est notable seulement à l’échelle d’un sous

bloc 8x8, où on peut remarquer cette différence sur la figure

FigureVI.2 Comparaison des sous bloc 8x8 de l’image originale et l’image compressée

Certains pixel ne sont pas les mêmes dans les deux sous blocs et non pas le même niveau

de gris, cela est due au fait que l’étape de la quantification est une étape avec perte, où on

a arrondit a l’entier pré après avoir divisé sur la table Q.

Le rapport crête signal sur bruit 34 dB est acceptable ,ce qui montre qu’on a fait une

compression efficace en matière de taille/qualité. Le nombre de bit par pixel a été réduit à

0.799 cela nous a fait perdre du poids au fichier image. Si on veut aller plus loin, on ajoute

la fonction suivante qui va générer d’autres tables de quantification en fonction de FQ:

function quantizer = quantificateur (FQ,dim_bloc)

for i=1:dim_bloc

for j=1:dim_bloc

quantizer(i,j) = 1 + ((1 + i + j)*FQ);

end

end

Nous obtiendrons les résultats suivants pour différents facteur qualité :

Pour : FQ = 10

taille_img_compresser =20820bits

taux_compression = 2.8526

EQM = 65.7042 PSNR = 29.9549 dB bpp = 0.3506

Pour : FQ = 50

taille_img_compresser = 8978bits

taux_compression = 6.6153

EQM =240.4954 PSNR = 24.3197 dB bpp = 0.1512

Pour : FQ = 100 (maximum)

taille_img_compresser = 7716bits

taux_compression =7.6973

EQM = 435.2725 PSNR =21.7432 dB bpp = 0.1299

FigureVI.3 Compression JPEG avec un FQ=10,50,100

On remarque que plus on choisis un facteur de qualité grand, plus le taux de compression

est meilleur du fait qu’on augmente le seuil de la table Q mais EQM augmente aussi ce qui

va influer l’efficacité de la compression constaté visuellement et aussi au vue du rapport

PSNR médiocre du fait qu’on a perdus beaucoup de données pendant l’étape de

quantification et cela est devenue très visible, ce qui rend l’image exploitable à certaines

limites.

VII. Conclusion

La compression JPEG pour qu’elle soit efficace doit être effectuée de façon optimale afin de

ne pas perdre trop en qualité de l’image et en parallèle réduire le poids de l’image, c’est-à-

dire trouver un compromis rapport taille/qualité qu’est le standard JPEG.

La compression JPEG en mode codage DCT séquentielle est une compression avec perte

non adapté aux besoins de précision, mais serait le format le mieux adapté pour les

mémoires (grace aux JPEG que les appareils photo numérique ont fait leurs apparition) ou

pour le web (rapidité de transmission ),cela dit,un format nouveau a été développer pour

les applications qui demande une fidélité maximum de l’image traité à l’image réel,comme

l’imagerie médicale, c’est le format JPEG2000 qui a les mêmes avantage du JPEG mais basé

sur une compression sans perte en utilisant une nouvelle transformé appelée la transformé

en ondelettes.

VIII. Références :

-Gérard Blanchet et Maurice Charbit, « Signaux et images sous Matlab »,Hermes

science publications,2001

-Aide du logiciel Mathworks Matlab R2010

-Syed Ali Khayam,” The Discrete Cosine Transform (DCT): Theory and Application

http://www.egr.msu.edu/waves/people/Ali_files/DCT_TR802.pdf

-Pascal Getreuer,Image Processing with Matlab

http://www.math.ucla.edu/~getreuer/matlabimaging.html

-P-O Östberg, Umeå University,Compression

http://www8.cs.umu.se/kurser/TDBC30/VT05/material/lecture8.pdf

-JPEG Image Compression,Rahul Garg, Varun Gulshan

http://www.cs.washington.edu/homes/rahul/data/JPEG.pdf

-VIDEO & IMAGE COMPRESSION TECHNIQUES

http://videocodecs.blogspot.com/2007/05/image-coding-fundamentals_08.html

-Wikipedia

http://fr.wikipedia.org/wiki/JPEG

-Institut des Systèmes Intelligents et de Robotique

http://www.isir.upmc.fr/UserFiles/File/clady_homepage/EPU/matlab_ti.pdf

-Girod: Image and Video Compression

http://www.icg.isy.liu.se/courses/tsbk01/material/slides/TransformCoding_ee392c_Girod.pdf

-Compression d’image,E. LE PENNEC

http://www.math.jussieu.fr/~lepennec/papers/Image2006LePennec.pdf