Soutenance mémoire
Techniques de la compression
Introduction
La compression est le procédé utilisé pour réduire la taille d’un bloc d’information. En compressant les données, on peut placer plus d’informations dans le même espace de stockage et utiliser moins de temps pour le transfert à travers un réseau télécommunication. Généralement les signaux occupent une place importante et la compression est devenue parti intégrante des données. On rencontre souvent la compression de données comme étant une partie de l’encodage de données au même titre que le cryptage de données et la transmission des données.
Ce chapitre est divisé en trois parties essentielles :
– La première concerne les critères d’évaluation d’un algorithme de compressions.
– La seconde partie concerne les différentes techniques de compression des signaux sans perte.
– La troisième partie concerne les différentes techniques de compression des signaux avec perte, comme les méthodes de compression par transformation sinusoïdales, transformé en ondelette.
Définition de la compression
La compression de données ou codage de source est l’opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations en utilisant un algorithme particulier, elle consiste à réduire la taille de données ce qui implique réduire le temps de transfert, et aussi réduire le coût du matériel [10].
La compression des données est utilisée pour :
Rentabiliser au maximum les capacités physiques de stockage en augmentant le volume apparent de données emmagasinées.
Augmenter les capacités de sauvegarde des disques durs (doublage).
Avoir un accès plus rapide aux informations stockées [11].
Pour la compression de donnée on distingue deux types de compression :
– Compression avec perte d’information,
– Compression sans perte d’information.
Méthodes de la compression
Il existe plusieurs algorithmes de compression de données utilisés pour les signaux, nous allons commencer par les méthodes sans perte d’information telle que codage.
Compression sans perte d’information
La compression est dite sans perte lorsqu’il n’y a aucune perte de données sur l’information d’origine. Il y a autant d’information après la compression qu’avant, elle est seulement réécrite d’une manière plus concise (c’est par exemple le cas de la compression Gzip pour n’importe quel type de données ou du format PNG pour des images synthétiques destinées au Web).
L’information à compresser est vue comme la sortie d’une source de symboles qui produit des textes finis selon certaines règles. Le but est de réduire la taille moyenne des signaux obtenus après la compression tout en ayant la possibilité de retrouver exactement le signal d’origine (on trouve aussi la dénomination codage de source en opposition au codage de canal qui désigne le codage correcteur d’erreurs)[13].
Pour la compression sans perte on peut distinguer plusieurs algorithmes de compression d’entre eux :
Codage RLE
Les lettres RLE signifient Run-LengthEncoding. Il s’agit d’un mode de compression parmi les plus simples : toute suite de bits ou de caractères identiques est remplacée par un couple (nombre d’occurrences ; bit ou caractère répété)[15].
Principe
L’encodage des répétitions (RLE pour Run-LengthEncoding) est l’une des méthodes les plus anciennes. Elle a l’avantage d’être des plus simples et est souvent utilisée. Le principe est d’identifier les séquences d’octets puis de les encoder en une forme plus compacte. Le codage RLE est à la fois rapide et simple à mettre en oeuvre.
Les textes ASCII se prêtent malheureusement assez mal à cette méthode, car ils contiennent rarement de très longues séquences répétitives. Les fichiers exécutables ou mieux encore les fichiers contenant des images bitmap ou des bases de données composées d’enregistrement de format fixe permettent d’obtenir un taux de compression relativement important[11].
Compression CCITT :
C’est une compression d’images utilisée pour le fax, standardisée par des recommandations de l’Union internationale des télécommunications (anciennement appelée CCITT). Elle est de type RLE (on code les suites horizontales de pixels blancs et de pixels noirs) et peut-être bidirectionnelle (on déduit une ligne de la précédente). Il existe plusieurs types de compressions (« groupes ») suivant l’algorithme utilisé et le nombre de couleurs du document (monochrome, niveau de gris, couleur)[13].
Deux compressions existent, celle du Groupe 3 (recommandation ITU T.4) et celle du Groupe 4 (recommandation ITU T.6), utilisées pour les fax :
Le Groupe 3 utilise comme indiqué une compression RLE, mais les symboles représentant les longueurs sont définis par le CCITT en fonction de leur fréquence probable et ceci pour diminuer la taille des messages à transmettre par les fax.
La compression du Groupe 4, elle, représente une ligne par les différences avec la ligne précédente. Ainsi un carré noir sur une page blanche n’aura que la première ligne du carré à transmettre, les suivantes étant simplement la « différence », c’est-à-dire rien. Et la page complète revient à envoyer 3 lignes et un symbole de « répéter la précédente » pour toutes les autres.
Codage de Huffman
L’idée qui préside au codage de Huffman est voisine de celle utilisée dans le code Morse : coder ce qui est fréquent sur peu de place, et coder en revanche sur des séquences plus longues ce qui revient rarement (entropie). En morse le « e », lettre très fréquente, est codé par un simple point, le plus bref de tous les signes.L’originalité de David A. Huffman est qu’il fournit un procédé d’agrégation objectif permettant de constituer son code dès lors qu’on possède les statistiques d’utilisation de chaque caractère.Le Macintosh d’Apple codait les textes dans un système inspiré de Huffman : les 15 lettres les plus fréquentes (dans la langue utilisée) étaient codées sur 4 bits, et la 16iem combinaison était un code d’échappement indiquant que la lettre était codée en ASCII sur les 8 bits suivants[19]. Ce système permettait une compression des textes voisine en moyenne de 30 % à une époque où la mémoire était extrêmement chère par rapport aux prix actuels (compter un facteur 1000).
Cependant, les lettres sont codées sur le premier jeu de caractère tandis que les chiffres et caractères spéciaux sur le second. Or la nature des caractères utilisés n’est pas aléatoire. En effet, lorsque l’on écrit un texte cohérent, les chiffres sont séparés des lettres et les ponctuations sont rares[13].
On peut aussi avoir aussi :
Codage LZW
Elle est introduite par Jacob Ziv et Abraham Lempel en 1977 et développée par Welch dans les années 80 mettant au point une technique de compression encore plus sophistiquée.
Codage arithmétique
Le premier avantage du codage arithmétique est que chaque caractère peut être code sur un nombre non-entier de bits. L’algorithme ne code pas les fichiers caractère par caractère mais par chaines de caractères, plus ou moins longues suivant la capacité de la machine à coder des réels plus ou moins grands.
Compression avec perte d’information
La compression est dite avec perte lorsqu’on perd des données sur l’information d’origine. Il y a autant d’information avant la compression qu’après.
Lors de la décompression on ne peut pas retrouver exactement le message d’origine donc c’est une compression irréversible. Dans ce type de compression, il existe de la distorsion sur le signal de sortie [17].
On peut distinguer trois grandes familles de compression avec perte :
par prédiction, par exemple l’ADPCM ;
par transformation. Ce sont les méthodes les plus efficaces et les plus utilisées.
compression basée sur la récurrence fractale de motifs (Compression par fractale).
Transformée discrète en sinus (DST)
La transformée en sinus discrète (DST) est une transformée de Fourier similaire à la transformée de Fourier discrète (TFD), mais en utilisant une matrice purement réelle. Il est équivalent aux parties imaginaires d’un DFT d’environ deux fois la longueur, fonctionne sur des données réelles avec symétrie impaire (depuis la transformée de Fourier d’une fonction réelle et impaire est imaginaire et impair), où, dans certaines variantes, l’entrée et / ou de sortie les données sont décalées d’une demi-échantillon [20].
|
Table des matières
Introduction Générale
Chapitre I : Généralités sur les signaux électroencéphalogrammes
I .1. Introduction
I .2. Anatomie du cerveau
I .2.1. Lobe frontal
I .2.2 Lobe pariétal
I .2.3 Lobe temporal
I . 2.4 Le lobe occipital
I .3. Unité fonctionnelle du système nerveux (le neurone)
I .4. Electroencéphalographie
I .5. Electroencéphalogramme
I .5.1. Utilité d’un EEG
I .5.2. Déroulement d’un examen EEG
I .6. Ondes cérébrales
I .6.1. Ondes delta
I .6.2. Ondes thêta
I .6.3. Ondes alpha
I .6.4 Onde béta
I .6.5 Ondes gamma
I .7. Capteurs
I .7.1 Principe
I .7.2 Différentes électrodes
I .7.3 Emplacement des électrodes
I .7.4. Différents montages ultrasons en EEG
I .8. Conclusion
Chapitre II : Techniques de la compression
II.1 Introduction
II.2Définition de la compression
II.3 Méthodes de la compression
II.3.1 Compression sans perte d’information
II.3.1.1 Codage RLE
II.3.1.2 Compression CCITT
II.3.1.3 Codage de Huffman
II.3.1.4 Code Baudot
II.3.1.5 Codage LZW
II.3.1.6 Codage arithmétique
II.3.2 Compression avec perte d’information
II.3.2.1 Méthode Directe
II.A Prédiction linéaire
II.B Interpolation polynomiale
II. 3.2.2 Méthodes par transformée
II.3.2.2.1 Transformée spectrale
II.A Transformée discrète de Fourier (TFD)
II.B Transformée discrète en cosinus (DCT)
II.C Transformée de Fourier Rapide (FFT)
II.D Transformée discrète en sinus(DST)
II.3.2.2.2 Transformée en Ondelettes
II.A Transformée en Ondelettes continue(CWT)
II.B Transformée en Ondelettes discrète (DWT)
II.4Critères de performances d’une méthode de compression
II.4.1 Le taux de compression(CR)
II.4.2 Mesure de la fidélité de la reconstruction
II.5 Conclusion
Chapitre III : compression par transformer spectrale
III.1 Introduction
III.2Présentation de la base de données
III.3 Présentation de l’algorithme de compression
III.4 Application et résultats
III.4.1 Application de la DCT
III.4.2 Application de la DST
III.4.3 Application de la FFT
III.5 Comparaison des résultats obtenus par les différentes méthodes
III.6 Discussions
III.7Conclusion
Chapitre IV : Résultats et Discussions
IV .1 Introduction
IV .2 Présentation de l’algorithme de compression
IV.3 les ondelettes utilisées
IV.3.1 Ondelette de Daubechies
IV.3.2 Ondelette de symlet
IV.3.3 Ondelette Biorthogonale
IV.4 Application et résultats
IV.5 Comparaison des Résultats
IV.6 Interface graphique
IV.6 Conclusion
Conclusion générale
Bibliographie
Télécharger le rapport complet
