!Compression de données
!!Intro Inflation des données → une des solutions: augmenter la capacité d’archivage et de transmission
!!Plan Compression des images *Méthodes sans pertes *Méthodes avec perte *Format JPEG *Format MPEG *Autres formats
Numérisation des images *Modes d’acquisition *Résolution *Restitution
Compression du son *Généralités *Numérisation du son *Formats de compression *Restitution
Applications *Internet *??CD|Compact Disc??-??ROM|Read-only Memory?? *TV numérique
Conclusion *Données économiques *Travaux de recherche
!!Environnement de communication Nouveaux systèmes qui intègrent du multimédia: Internet, TV numérique
Multimédia: Communiquer des idées, Rechercher de l’information, Développer de nouveaux concepts
!!!Transmission des données Signaux électrique: base de tous les systèmes de communication actuels
2 modes: *numérique *analogique
Plusieurs types de supports: câbles métalliques, satellites, fibre optique, ondes hertziennes
!!Volume croissant de l’information Couverture satellitaire de la planète
*télécommunication : mondialisation *photographie : géoressources *météorologie : prévisions
!!Comment éviter les bouchons
!!Compression de l’information !!!Généralités Comprimer pour augmenter l’efficacité d’un procédé en gagnant du temps et de l’espace
Exemples de compression au quotidient *apocope: ciné, métro, info, etc. *aphérèse: bus, car, etc. *abréviation: ??PC??, ??TV|Télévision??, ??HTML??
En informatique et dans le mutlimédia
Objectif: réduire la qté de symboles utilisés pour _optimiser les flux et l’archivage_
Plus le volume est grand, plus la compression s’avère incontournable *TV numérique: multitudes de chaînes et programmes interactifs *Rechercher et télédétection: NASA a multiplié par 10 le nombre de photos transmises
!!Méthodes de compression !!!Principe #Analyse du fichier à traiter #Détecter des régularités #*langue française: mot en “eur”, en “oir”, en “ité” #coder le fichier en exploitant des régularités
Types de données: *exactes: ne tolérant pas de perte d’information *sensorielles : images, son, vidéo tolèrent une perte d’information
*compressibles *incompressibles (suites aléatoires comme certaines séquences génétiques)
2 types de méthodes: *méthodes conservatives *méthodes destructives
Méthodes conservatives *??RLE|Run Length Encoding?? *Statistiques *à dictionnaire (à substitution de facteurs)
Taux de compression (en %) = (poids initial - poids compressé)/poids initial*100
!!!Exemple de ??RLE?? *repérage des répétitions consécutives *indication du nombre de répétitions
tagada tagada voilà les Dalton tagada tagada voilà les Dalton
donne
[[tagada]2 voilà les Dalton]2
Existe une limite, dans certains cas, le fichier compressé est plus lourd que le fichier initial
Utilisé dans certains formats graphiques comme ??TGA?? et ??TIF??. Bons résultats dans le cas des images à aplats de couleurs
!!!Méthodes statistiques Principe: coder les symboles qui apparaissent plus fréquemment avec des chaînes binaires plus courtes et inversement *le compresseur lit le fichier à traiter *détermine les fréquences relatives de chaque symbole *attribue des chaînes binaires inversement proportionnelles aux fréquences d’apparition des symboles
Entropie: -1*somme(Pi*log(Pi)2) (Pi = fréquence relative d’un symbole)
Méthode utilisée dans le codage Huffman
!!!Méthodes à dictionnaires
Principe: constituer un dictionnaire où l’on stocke les chaînes de caractères répétées et à l’aide d’un pointeur on enregistre leurs emplacements dans le fichier traité
Algorithme à fenêtre coulissante
Méthode LZW (algos LZ77 et LZ78 par Abraham Lempel et Jacob Zeev). En 1984, Terry Welch améliora la performance de la LZ78.
De nombreux compresseurs performants ont été créés sur la base de ces méthodes: ARJ, GZIP, WinZip, GIF, etc.
Liens connexes *[http://www.alphabeta-net.com/LZW.html] *[http://www.commentcamarche.net/video/compimg.php3] *[http://crteknologies.free.fr/projets/tpe_compression_graphique/]
Méthodes *conservatives: RLE, Statistiques, LZW *destructives: JPEG, MPEG, Fractales, Ondelettes (Wavelets)
!!Méthodes destructives
!!!JPEG Joint Photographic Expert Group Historique: *1978-1984: début des travaux du groupe *1992: Adoption de la norme
Outil mathématique utilisé est la DCT (Discrete Cosine Tranform) mise au point en 1974 par K.R. RAO (Texas).
Mis à part la partie du codage statique breveté par IBM, le reste est libre d’utilisation.
Principe: repose sur le fait que l’oeil fonctionne comme un filtre passe-bas pour les fréquences spatiales.
opérations en 5 étapes: #découpage de l’image en blocs de 8×8 pixels donc des matrices de 64 valeurs d’intensité lumineuse. On obtient des matrices d’amplitudes. #transposition amplitudes→fréquences par la DCT. En fait, avant, les valeurs RVB sont transformées en YUV (ou YCrCb) avec Y=59%V+30%R+11%B #*Y=luminance, Cr=Crominance en R, Cb=Crominance en B #*On accorde plus de poids à la luminance qu’à la chrominance #Quantification(filtrage). #*But: Diminuer ou supprimer les fréquences élevés non perceptibles par l’oeil. #*Opération: La matrice issue de la DCT est divisée par une matrice de quantification #Mise en ordre des valeurs de la mtrice quantifiée. Les valeurs sont classées par ordre croissant. #Codage statistique de type Huffman → compression conservative #*Codage des valeurs les moins fréquentes avec une chaine binaire (nb bits) plus longues que pour les valeurs les moins fréquentes
Décompression: Les même opérations mais à l’envers
Cette méthode est symétrique: le temps de calcul est le même dans la phase de compression que dans la phase de décompression.
!Compression d’images animées: norme ??MPEG|Moving Picture Expert Group??
*Historique: 1992=MPEG1, 1994=MPEG2(HDTV) *Objectif: permettre la fluidité des images en réduisant l’espace de stockage et le taux de transfert sur les réseaux *Constituants: 2 couches couche système couche de compression *compression vidéo *compression audio *Compression spatiale (JPEG) *Compression temporelle *Compression audio *Evolution de la norme
!!Compression temporelle
Hiérarchie de données (du plus haut niveau au plus bas niveau)
*Séquence Entête 1 ou plusieurs groupes d’images Fin de séquence *Groupe contient une ou plusieurs images *Image: 1 matrice en YUV découpée en plusieurs tranches *Tranche (slice): découpées en macroblocs Correction d’erreur à ce niveau Macrobloc: Dimension de 16×16 pixels *Bloc: 8x8px = 3 matrices (Y,U,V) MPEG spécifie 3 types d’images: *images de références = images clés = Intra pictures = I-pictures Elles servent à créer les images prédites Elles sont compresssées indépendamment de leur contexte avec un faible taux de compression *Images prédites (predicted pictures, P-pictures) Elles sont créés à partir des images précédentes Elles utilisent la compensation de mouvement Elles propagent les erreurs 3)
*images bidirectionnelles (bidirectional pictures, B-pitures) sont créés à la fin par les images précédentes et suivantes elles ne servent pas à la création d’autres images: pas de propagation d’erreur. 4)
Le flux vidéo comporte des images clés dont la fréquence peut être choisie en fonction du contenun par exemple un image clé toute les 1/2 secondes.
Le nombre d’images P entre 2 images clés est paramétrable.
Le codeur optimise le flus pour faciliter le travail au décodeur en réarrangeant l’ordre des images.
!!Compensation de mouvement Repose sur 2 paramètres: *Vecteur de déplacement, spécifie la distance entre le bloc de référence et le bloc qui va être codé *différence de contenu entre le bloc de référence est le bloc qui va être codé.
!!Compression spatiale *compression appliquée aux images de référence Compression JPEG *Découpage en 8×8 pix de l’image I *Transformer la matrice RVB en YUV *Appliquer la DCT *Quantifier la matrice après DCT *Ordonner les valeurs quantifiées *Appliquer un codage entropique (Huffman) !!Compression temporelle Flux optimisé pour le décodeur Rôle de la couche système *contient l’horloge: valeurs transmises au décodeur *marquage temporel: valeurs indiquant à quel moment une image doit être affichée Rôle fondamental dans la synchronisation des flux vidéos et audio. !!Evolutions de la norme *MPEG 2 → HDTV, TV numérique supporte les images entrelacées taux de transfert jusqu’à 15 Mb/s possibilité de choix de fréquences d’échantillonnage de images i algorithmes codant différemment la compensation du mouvement choix variables par l’échantillonnage YUV *MPEG 4: analyse et codage du contenu vidéo deviennent cruciaux analyse: *rendre l’utilisateur actif au lieu de rester passif *augmenter les possibilités d’intéractions approche du type objet avec une forte notion d’intégration *mélange d’objets naturels et de synthèse *objets 2D et 3D *sons mono et stéréo vise la convergence entre la TV, les télécoms et l’informatique notion de ??VOP|Video Object Plan?? ??VOP|Video Object Plan?? décrit et code sous forme de plusieurs couches (??VOL|Video Object Layers??) *couche décrivant la forme *couche décrivant la texture *couche décrivant le mouvement le contenu est finement codé, ainsi, on peut intéragir et modifier tel ou tel aspect graphique ou acoustique ce codage offre une souplesse quant à l’accès aléatoire
!!Compression audio dans ??MPEG|Moving Picture Expert Group??
!!Compression du son *Définition: le son est une onde vibratoire qui naît d’une variation rapide de la pression de l’aire; il est perçu par nos organes auditifs. *Propriétés: réflexion: existence de l’écho réfraction: on entend à travers les murs interférence: deux sources qui émettent en phase et avec les mêmes fréquences font naître un renforcemetn ou une annulation des intensités sonores. vitesse de propagation: *se propage dans les gaz, les liquides et les solides dans les gaz et les liquides: @@v = f(T,P)@@ *dans l’air: v=331 m/s à O°C *dans l’eau à 20°C: 1450 m/s dans les solides, v est fonction de la densité et de l’élasticité du milieu *Paramètres caractéristiques: intensité: dB (avec >120: seuil douloureux) hauteur: fréquence: Hz, KHz (oreille humaine: 20Hz –> 20 KHz) timbre: présence d’harmoniques (hautes fréquences) *Sources sonores: naturelles: *bruits d’animaux *phénomènes atmosphériques (tonnerre) *phénomènes géologiques (explosions de volcans) artificielles: *activités humaines
L’étendue dépasse les fréquences audibles: *infrasons: fréquences trop basses pour l’oreille (claquement de porte) *ultrasons: fréquences trop hautes pour l’oreille (certains insectes émettent à plus de 40KHz)
ex: [Explosion du Krakatoa|http://fr.wikipedia.org/wiki/Krakatoa|FR|article relatif] en 1883 a fait baisser le mercure à Paris à cause des infrasons émis.
!!Echantillonnage d’un son analogique
f=44,1 KHz (~ 2 x 22 KHz) La limite supérieure de la sensibilité de l’oreille humaine: ~ 20KHz codage à 16 bits/échantillon
*Cd-audio: 44100 échantillons/seconde
*Volume occupé dans un cd-audio: son stéréo: 44100 x 16 x 3600 x 2 ~650Mo
!!Compression d’un son *Compressions sans perte: LZW, statistique taux faibles car les sons sont rarement purs *Compressions avec pertes diminuer la fréquence d’échantillonnage de moitié: 22KHz au lieu de 44KHz _→ gain: 50%_ diminuer la résolution la résolution: ex: 12 au lieu de 16 bits _→ gain: 25%_ compression MPEG ***tient compte des caractéristiques psycho-acoustiques de l’oreille Mais très mauvais résultats avec les deux premières méthodes, car l’oreille est très sensible à la dégradation d’un son
!!!Compression MPEG #Seuls les sons de niveau L(f) se trouvant dans la zone audible sont pris en compte #Elimination des sons masqués Après filtrage et quantification, on applique un codage de type statistique.
Couches audios (MPEG) comporte 3 sous-couches (MP3) *layer 1 *layer 2 *layer 3
!!!Schéma de la compression audio MPEG 6)
Mis à jour le 28 Décembre
[PartielFC2004] Sujet du partiel
