algorithme de compression : les limites
SCIENCES ET TECHNIQUES
+ DE 2 ANS
Le 26/07/2005 à 12h39
144 vues
Question d'origine :
Bonjour.
Y-a-t-il ds limites théoriques, posées par les mathéciens, à la compression numérique ?
Ou bien est-il possible un jour de trouver la formule mathématique miracle qui permettra de compresser des quantités énormes de connaissances dans quelques kilo-octets de données ?
A bientôt.
Merci
Réponse du Guichet
bml_sci
- Département : Sciences et Techniques
Le 29/07/2005 à 11h04
- l'entropie par symbole ;
- le nombre de symboles différents ;
- l'algorithme utilisé ;
- la réversibilité de la méthode ;
- les propriétés des canaux de transmission ;
...
- Concernant
l'entropie par symbole , il s'agit de laquantité moyenne d’information nécessaire pour coder un symbole . Cette entropie est fonction du logiciel utilisé et peut être améliorée en fonction de la fréquence d'utilisation dudit symbole. L'entropie par symbole est néanmoins déjà très optimisée par les algorithmes utilisés actuellement dans la compression des données. - Le taux de compression va dépendre aussi du nombre de symboles différents utilisés ainsi que de la taille du fichier initial. Cela paraît logique.
- L'algorithme utilisé : il en existe plusieurs et ce n'est sans doute pas fini (algorithme de Huffman adaptatif, l'algorithme de Shanon-Fano, l'algorithme de Lempel-Ziv,...). les chercheurs poursuivent plusieurs objectifs pour optimiser les algorithmes ou en inventer d'autres : créer un algorithme utilisant le codage universel, i.e. ne présupposant rien du type de fichier à compresser,
présupposer la qualité du symbole suivant à compresser. - la réversibilité de la méthode utilisée : en effet, la compression peut-être accentuée quitte à perdre une partie des données jugées peu pertinentes. C'est la méthode utilisée dans la compression d'images de type JPEG.
- les propriétés des canaux de transmission des données agissent aussi sur la qualité de la compression. Aussi dans l'intérêt de l'efficacité de la transmission et de la compression à la fois, on doit tenir compte des propriétés des canaux de transmission pendant le développement des méthodes de compression. L'inverse est également vrai : les protocoles de transmission - les conventions qui déterminent les règles de trafic sur le réseau - doivent être adaptés à la transmission des images comprimées.
La compression est réalisée en réduisant toutes les formes possibles de redondance qu’une image peut présenter :
- Redondance spatiale : tous les pixels sont identiques à l’intérieur d’une plage de l’image uniforme. Il suffit d’en coder un pour caractériser la plage considérée. La technique de la Transformée en Cosinus Discrète (DCT) utilisée dans l’algorithme JPEG, met en évidence cette redondance spatiale à l’intérieur de chaque image.
- Redondance statistique : certaines données se répètent beaucoup plus fréquemment que d’autres. La compression sera réalisée en attribuant des codes d’autant plus courts que la fréquence est élevée.
- Redondance subjective, mise à profit dans la compression non conservatrice : elle découle des imperfections de l‘œil humain. Des pixels présentant des caractéristiques assez proches pour être perçus de manière identique peuvent être traités comme des pixels identiques.
On peut noter que l’œil est beaucoup plus sensible aux variations d’intensité lumineuse (luminance) qu‘à celles de la couleur (chrominance) : les informations sur la couleur peuvent donc être davantage compressées que celles sur la luminance. De même, des pixels trop proches pour être distingués par l‘œil peuvent être regroupés (il suffit de 520 lignes sur un téléviseur pour donner une image assez correcte).
sources :
- TIPE : Travail d'Initiative Personnel Encadré, réalisé dans les classes préparatoires
- Cours de Nicolas Sendrier à l'Ecole Polytechnique
- La tour des ruses - Ressources en informatique
- Thèse sur la quantification vectorielle et compression d'image
- Centre National de Documentation Pédagogique
N'étant ni chercheurs en mathématique-informatique, ni devins [cela ne fait pas encore partie du bagage (compressé ou non) obligatoire du bibliothécaire], nous n'en savons rien.
DANS NOS COLLECTIONS :
Ça pourrait vous intéresser :
Commentaires 0
Connectez-vous pour pouvoir commenter.
Se connecter