Techniques de compression avec et sans perte : Contexte global

TECHNIQUES DE COMPRESSION AVEC ET SANS PERTE : CONTEXTE GLOBAL

Il existe deux types de compression. La compression sans perte (compression non destructive), elle utilise des algorithmes qui compressent les données sans les dégrader. Parmi les plus connues de ces méthodes figure le codage RLE [SAL08], le codage de HUFFMAN [HUF52] ou bien encore le codage LZ [ZIV77]. Elles sont utilisées pour la compression des fichiers textes ou encore les fichiers exécutables. La compression avec pertes (compression destructrice), utilise des algorithmes qui compressent les données, en introduisant des dégradations, qui peuvent être nuisibles dans certaines applications. Pour plus de détail concernant ces techniques de compression, le lecteur est prié de consulter les travaux de [ZEY12]. Il est important de signaler que le choix de compresser une donnée ne dépend pas seulement du type de méthodes de compression (avec ou sans perte), mais aussi des types d’applications à envisager. On peut citer trois principaux domaines au niveau de la compression de données :

1. la compression des signaux 1D,
2. la compression des signaux 2D;
3. la compression des signaux 3D.

La compression des signaux 1D repose sur des techniques basées sur des modèles paramétriques tels que le codage par prédiction linéaire (Linear Prediction Coding (LPC) [SUN13])), le codage par la modulation à impulsion codée (Pulse Coding Modulation (PCM) [RIV03])), et enfin le codage par des techniques hybrides (Code- Excitation Linear Prediction (CELP) [VAS07]). En plus de ces techniques, des normes de compression ont vu le jour, et sont appliquées dans diverses applications: On peut citer, par exemple : la norme MPEG-1/2 ou MP3 pour l’audio, la norme CEN/ENV 1 064 [ENV96], pour les signaux physiologiques, tels que l’ECG, la norme ASTM 1 467 [ASM94], pour les signaux EEG, EMG et PE. La norme EDF (European Data Format), pour les signaux biologiques multivoies [KEM92], et enfin la norme CCSDS 121.0-B (ISO-15887:2000) [SHE13]) pour des signaux 1D satellitaires et zip, gzip, bzip2, 7zip pour les fichiers textes [DUM13], La compression des signaux 2D ou images fixes, utilise des techniques basées sur le codage prédictif [WEI96] [XIA97], le codage par transformation [TAQ10] et des méthodes de moindres carrés pour construire des prédicateurs adaptatifs tels que les méthodes présentées dans [XIN01] et [KAU05]. Plusieurs travaux faisant intervenir ces techniques sont rencontrés dans la littérature, ce qui à conduit les experts dans ce domaine à proposer des normes de compression pour des images fixes telles que JPEG et JPEG2000 [ZEY12].

Enfin, la compression des signaux 3D, dont le fondement repose trois méthodes de compression :
❖ Méthodes par simplification de maillage, destinées à décomposer une forme par des figures géométriques (polygones, carré, triangle) puis à reconstruire  ensuite la forme par l’assemblage de figures en basant sur leur géométrie de leur connectivité [LAV05][SAN01] [GAR01] [VAL04].
❖ Méthodes de compression mono-résolution : [ISE00] [LEE02] [SZY03].
❖ Méthodes de compression multi-résolution [KAR00][KHO00].

La compression des signaux 3D est largement utilisée dans les domaines industriel, médical (norme DICOM), patrimoine culturel et jeux vidéo [NAI07] [LOR03].

Le codage Huffmann

En 1952, Huffmann a mis en évidence une méthode pour construire des codes compacts de longueur variables [HUF54]. Le codage Huffmann attribue un code de sortie à chaque symbole. Les codes de sortie pouvant être aussi courts qu’un bit, ou beaucoup plus longs que les symboles d’entrée en fonction de leurs probabilités. Le nombre de bits optimum pour chaque symbole est –log pi où pi i est la probabilité du symbole en question. Les étapes nécessaires pour générer le code Huffmann pour des symboles dont les probabilités d’occurrence sont connues et peuvent être regroupées comme suit:
❖Classer tous les symboles dans l’ordre de leur probabilité d’occurrence,
❖Fusionner les deux symboles les moins probables pour former un symbole combiné, et reclasser encore les symboles dans l’ordre de probabilité : Cela génère une arborescence dont chaque nœud représente la probabilité cumulative de tous les nœuds en dessous,
❖Tracer un chemin vers chaque feuille, en notant la direction sur chaque nœud.

Le codage par transformation

Le codage par transformation de domaine est principalement utilisé dans la réduction de redondance spatiale sur les images, en mappant les pixels dans un domaine de transformée. La puissance de ces techniques réside dans le fait que l’énergie des échantillons d’une image naturelle est concentrée dans la région de basses fréquences; donc dans une région contenant peu de coefficients. Ces coefficients par la suite peuvent être quantifiés tout en négligeant les coefficients insignifiants, sans pour autant dégrader la qualité de l’image. Le processus de quantification est pourtant avec perte, dans lequel les valeurs originales ne sont pas préservées. La transformée en cosinus discrète (DCT) est considérée comme le meilleur choix de transformée pour le codage des images par transformation [GHA03], car elle est caractérisée par des vecteurs de base bien définis qui varient doucement. Cela correspond bien aux changements d’intensité de la plupart des images naturelles [JAI89]. Un autre aspect important de la DCT, c’est qu’il existe une version rapide pour des applications basées software [CHE79].

Quantification des coefficients de la DCT

En réalité, la transformation des pixels en domaine DCT n’aboutit pas à une compression. Un bloc de taille 64 pixels est transformé en 64 coefficients. En raison de l’orthonormalité de la DCT, l’énergie dans les deux domaines ne change pas, donc il n’y a pas de compression effectuée. Toutefois, la transformation entraîne la concentration de l’énergie sur les composantes de basses fréquences. La majorité des coefficients qui en restent représentent une faible énergie. C’est l’étape de quantification et le codage entropique qui réduisent le débit binaire. De plus, en exploitant les caractéristiques du système visuel humain [LUK06] [KUN99] qui est moins sensible aux distorsions présentes sur les hautes fréquences, on peut employer une quantification grossière pour les coefficients appartenant aux hautes fréquences. Le quantificateur utilisé dans tous les codecs standards de l’image et de la vidéo s’articule autour du quantificateur à seuil uniforme (UTQ5).

PLACE DES STANDARDS DANS LA COMPRESSION DES DONNEES

Nécessité d’une norme ou standard

Les normes sont des ensembles de règles approuvées par des instances officielles en charge de la normalisation. Elles offrent une certaine garantie de stabilité et de pérennité [CHA00]. Le standard est assimilé à un processus réactif de consensus du monde économique ou du monde technique [CHA00]. La langue anglaise n’a qu’un seul terme, celui de standard. Par contre au niveau de la langue française, celle-ci utilise les deux termes norme et standard pour désigner une publication finale résultante d’un accord consensuel.

Processus d’organisation des normes

Pour de nombreux organismes de normalisation mis en place tels que International Organization for Standardization (ISO), Commission Electrotechnique Internationale (CEI), International Telecommunication Union (ITU), la finalité est le développement facile des activités économiques. Toute norme internationale est développée par un comité technique de l’ISO (TC) ou un sous-comité (SC). Le processus d’élaboration de cette norme intègre 6 étapes:
1. Étape de proposition (avec l’engagement minimum de 5 membres du TC concerné).
2. Étape préparatoire: élaboration d’un document de travail « working draft » recueillant le consensus des membres du groupe de travail.
3. Étape Comité: le document doit être approuvé par les membres du TC/SC concerné. Le texte après vote a le statut de « Draft International Standard » (DIS).
4. Étape d’enquête probatoire : le DIS est distribué à tous les membres de l’ISO pour voter et commenter (cela dure 5 mois). Selon des conditions précises, il est accepté ou non comme « Final Draft International Standard » (FDIS)
5. Étape d’approbation finale: vote final pendant une période de 2 mois.
6. Étape de publication finale: faite par le secrétariat central de l’ISO.

Toute norme internationale est réexaminée au moins une fois tous les 5 ans.

Table des matières

INTRODUCTION GÉNÉRALE
Chapitre 01 : ÉTUDE COMPARATIVE DE MÉTHODES DE COMPRESSION DE DONNÉESET PLACE DES STANDARDS DANS LE CONTEXTE DE LA COMPRESSION
1 ÉTUDE COMPARATIVE DE MÉTHODES DE COMPRESSION DE DONNÉES ET PLACE DES STANDARDS DANS LE CONTEXTE DE LA COMPRESSION
1.1 Introduction
1.2 Techniques de compression avec et sans perte : Contexte global
1.2.1 Aperçu sur les techniques de compression sans perte
1.2.1.1 L’entropie de l’information
1.2.1.2 Le codage Huffmann
1.2.1.3 Le codage arithmétique : Principe et méthodologie
1.2.1.4 Le codage prédictif
1.2.2 Aperçu sur les techniques de compression avec perte
1.2.2.1 Réduction de la redondance spatiale.
1.2.2.1.1 Transformation en espace couleur YCbCr
1.2.2.2 Le codage par transformation
1.2.2.3 Quantification des coefficients de la DCT
1.3 Place des standards dans la compression des données
1.3.1 Nécessité d’une norme ou standard
1.3.2 Processus d’organisation des normes
1.3.3 Normes retenues pour compresser les images fixes
1.4 Techniques de compression des images fixes avec JPEG\JPEG 2000
1.4.1 La compression sans perte avec JPEG Lossless (JPEG–LS)
1.4.2 La compression avec perte du JPEG
1.4.3 Compression avec le standard JPEG 2000
1.4.3.1 Pré-traitement
1.4.3.2 Codage fondamental
1.4.3.2.1 Transformée en ondelette discrète (DWT)
1.4.3.2.2 Quantification
1.4.3.2.3 Codage entropique
1.4.3.3 Post-traitement
1.5 Artéfacts générés par JPEG et JPEG2000
1.6 Méthodes de réduction des artefacts pour jpeg et jpeg2000
Conclusion
Chapitre 02 : LES MÉTRIQUES PERCEPTUELLES EN COMPRESSION D’IMAGES
2 LES MÉTRIQUES PERCEPTUELLES EN COMPRESSION D’IMAGES
2.1 Évaluation subjective basée sur les propriétés et modélisation du (SVH)
2.1.1 Caractéristiques clés du SVH
2.1.2 Métriques perceptuelles basées sur le SVH
2.1.2.1 Métriques subjectives destinées à l’évaluation de la qualité visuelle des images fixes
2.1.2.1.1 Modèle basé sur les tests psychophysiques
2.1.2.1.2 Le modèle de Nill
2.1.2.1.3 Le modèle PQS
2.1.2.2 Métriques subjectives destinées à l’évaluation de la qualité visuelle des images
animées
2.2 Métriques perceptuelles basées sur des critères mathématiques : Mesures objectives
2.2.1 Méthodes avec référence complète
2.2.1.1 Erreur quadratique moyenne (MSE)
2.2.1.2 Rapport crête signal sur bruit (PSNR)
2.2.1.3 Rapport signal sur bruit (SNR)
2.2.1.4 Indice de similarité structurelle (SSIM)
2.2.1.5 Similitude structurale à base de gradient
2.2.1.6 Indice de la région d’intérêt (VroiWQI)
2.3 Limites des métriques présentées
2.4 Métrique proposée
Conclusion
Chapitre 03 : TECHNIQUES PROPOSÉES POUR L’AMÉLIORATION DE LA QUALITÉVISUELLE DES IMAGES COMPRESSÉES JPEG2000
3.1 Aperçu sur les méthodes de prétraitement
3.1.1 Méthodes basées sur l’amélioration de la qualité visuelle des images
3.1.2 Méthodes basées sur la restauration de l’image
3.2 Prétraitements proposés
3.2.1 Prétraitement basé sur la Décomposition Modale Empirique Bidimensionnelle (BEMD) et le modèle du Masque flou « sharpenning »
3.2.1.1 Décomposition modale empirique bidimensionnelle
3.2.1.2 Le schéma adopté de la méthode proposée
3.2.2 Amélioration basée sur le filtrage par moyenne temporelle
3.2.2.1 Prétraitement proposé
3.2.3 Méthode basée sur le filtrage morphologique
3.2.3.1 Principe de la méthode
3.2.3.2 Morphologie mathématique appliquée aux images en niveau de gris (NG)
3.2.3.2.1 Opérateurs morphologiques
3.2.3.2.2 Filtrage non linéaire
3.2.3.2.3 Filtrage par reconstruction morphologique
3.2.3.2.4 Fonctionnement de la méthode proposée
Conclusion
Chapitre 04 APPLICATION DE LA MÉTHODE PROPOSÉE DANS LE DOMAINE DE LA TÉLÉMÉDECINE
4.1 Introduction
4.2 Transmission par mail
4.3 Modélisation de la chaine de transmission sans fil
4.3.1 Le canal à Bruit Blanc Additif Gaussien
4.3.2 Transmission selon l’architecture TCP/IP adoptée
Conclusion
CONCLUSION GÉNÉRALE

Lire le rapport complet