Compression de données

ImageEdit

le codage D’entropie est né dans les années 1940 avec l’introduction du codage Shannon–Fano, la base du codage Huffman qui a été développé en 1950. Le codage de la transformation remonte à la fin des années 1960, avec l’introduction du codage de la Transformée de Fourier rapide (FFT) en 1968 et de la Transformée de Hadamard en 1969.

Une technique importante de compression d’image est la transformée en cosinus discrète (DCT), une technique développée au début des années 1970., DCT est la base du format JPEG, un format de compression avec perte qui a été introduit par le Joint Photographic Experts Group (JPEG) en 1992. JPEG réduit considérablement la quantité de données nécessaires pour représenter une image au prix d’une réduction relativement modeste de la qualité de l’image et est devenu le plus largement utilisé format de fichier d’image. Son algorithme de compression basé sur DCT très efficace était en grande partie responsable de la grande prolifération des images numériques et des photos numériques.

Lempel–Ziv–Welch (LZW) est un algorithme de compression sans perte développé en 1984. Il est utilisé dans le format GIF, introduit en 1987., DEFLATE, un algorithme de compression sans perte spécifié en 1996, est utilisé au format Portable Network Graphics (PNG).

La compression d’ondelettes, l’utilisation d’ondelettes dans la compression d’image, a commencé après le développement du codage DCT. La norme JPEG 2000 a été introduite en 2000. Contrairement à l’algorithme DCT utilisé par le format JPEG d’origine, JPEG 2000 utilise plutôt des algorithmes de transformation d’ondelettes discrètes (DWT). La technologie JPEG 2000, qui comprend l’extension Motion JPEG 2000, a été choisie comme norme de codage vidéo pour le cinéma numérique en 2004.,

AudioEdit

La compression de données audio, à ne pas confondre avec la compression de plage dynamique, a le potentiel de réduire la bande passante de transmission et les besoins de stockage des données audio. Les algorithmes de compression audio sont implémentés dans les logiciels en tant que codecs audio. Dans la compression avec perte et sans perte, la redondance de l’information est réduite, en utilisant des méthodes telles que le codage, la transformation de cosinus discrète de quantification et la prédiction linéaire pour réduire la quantité d’informations utilisées pour représenter les données non compressées.,

Les algorithmes de compression audio avec perte fournissent une compression plus élevée et sont utilisés dans de nombreuses applications audio, y compris Vorbis et MP3. Ces algorithmes s’appuient presque tous sur la psychoacoustique pour éliminer ou réduire la fidélité des sons moins audibles, réduisant ainsi l’espace nécessaire pour les stocker ou les transmettre.

Le compromis acceptable entre la perte de qualité audio et la taille de transmission ou de stockage dépend de l’application., Par exemple, un disque compact (CD) de 640 Mo contient environ une heure de musique haute fidélité non compressée, moins de 2 heures de musique compressée sans perte ou 7 heures de musique compressée au format MP3 à un débit binaire moyen. Un enregistreur de son numérique peut généralement stocker environ 200 heures de parole clairement intelligible en 640 Mo.

La compression audio sans perte produit une représentation des données numériques qui peuvent être décodées en une copie numérique exacte de l’original. Les taux de compression sont d’environ 50 à 60% de la taille d’origine, ce qui est similaire à ceux de la compression de données sans perte générique., Les codecs sans perte utilisent l’ajustement de courbe ou la prédiction linéaire comme base pour estimer le signal. Les paramètres décrivant l’estimation et la différence entre l’estimation et le signal réel sont codés séparément.

un certain nombre de formats de compression audio sans perte existent. Voir liste des codecs sans perte pour une liste. Certains formats sont associés à un système distinct, tel que le transfert direct de flux, utilisé dans Super Audio CD et Meridian lossless Packing, utilisé dans DVD-Audio, Dolby TrueHD, Blu-ray et HD DVD.,

Certains formats de fichiers audio comportent une combinaison d’un format avec perte et d’une correction sans perte; cela permet de supprimer la correction pour obtenir facilement un fichier avec perte. Ces formats incluent MPEG – 4 SLS (Scalable to Lossless), WavPack et OptimFROG DualStream.

Lorsque des fichiers audio doivent être traités, soit par compression supplémentaire, soit pour être édités, il est souhaitable de travailler à partir d’un original inchangé (non compressé ou compressé sans perte)., Le traitement d’un fichier compressé avec perte dans un but donné produit généralement un résultat final inférieur à la création du même fichier compressé à partir d’un original non compressé. En plus de l’édition sonore ou du mixage, la compression audio sans perte est souvent utilisée pour le stockage d’archives ou comme copies principales.

avec Perte audio compressionEdit

la compression audio avec perte est utilisée dans un large éventail d’applications. En plus des applications audio autonomes de lecture de fichiers dans les lecteurs MP3 ou les ordinateurs, les flux audio compressés numériquement sont utilisés dans la plupart des DVD vidéo, la télévision numérique, les médias en streaming sur Internet, la radio par satellite et par câble, et de plus en plus dans les émissions de radio terrestre., La compression avec perte permet généralement d’obtenir une compression bien supérieure à la compression sans perte, en éliminant les données moins critiques basées sur des optimisations psychoacoustiques.

la psychoacoustique reconnaît que toutes les données d’un flux audio ne peuvent pas être perçues par le système auditif humain. La compression avec perte réduit la redondance en identifiant d’abord les sons non pertinents sur le plan perceptuel, c’est-à-dire les sons très difficiles à entendre. Les exemples typiques incluent les hautes fréquences ou les sons qui se produisent en même temps que des sons plus forts. Ces sons non pertinents sont codés avec une précision réduite ou pas du tout.,

En raison de la nature des algorithmes avec perte, la qualité audio subit une perte de génération numérique lorsqu’un fichier est décompressé et recompressé. Cela rend la compression avec perte inappropriée pour stocker les résultats intermédiaires dans des applications professionnelles d’ingénierie audio, telles que l’édition sonore et l’enregistrement multipiste. Cependant, les formats avec perte tels que MP3 sont très populaires auprès des utilisateurs finaux car la taille du fichier est réduite à 5-20% de la taille d’origine et un mégaoctet peut stocker environ une minute de musique à une qualité adéquate.,

Coding methodsEdit

pour déterminer quelles informations dans un signal audio sont non pertinentes sur le plan perceptuel, la plupart des algorithmes de compression avec perte utilisent des transformations telles que la transformée en cosinus discrète modifiée (MDCT) pour convertir les formes d’onde échantillonnées dans le domaine temporel en un domaine de transformation, généralement le domaine fréquentiel. Une fois transformées, les fréquences des composants peuvent être hiérarchisées en fonction de leur niveau d’audibilité., L’audibilité des composantes spectrales est évaluée en utilisant le seuil absolu d’audition et les principes du masquage simultané—le phénomène dans lequel un signal est masqué par un autre signal séparé par la fréquence—et, dans certains cas, le masquage temporel—où un signal est masqué par un autre signal séparé par le temps. Les contours à volume égal peuvent également être utilisés pour pondérer l’importance perceptuelle des composants. Les modèles de la combinaison oreille-cerveau humain incorporant de tels effets sont souvent appelés modèles psychoacoustiques.,

D’autres types de compresseurs avec perte, tels que le codage prédictif linéaire (LPC) utilisé avec la Parole, sont des codeurs basés sur la source. LPC utilise un modèle du tractus vocal humain pour analyser les sons de la parole et déduire les paramètres utilisés par le modèle pour les produire moment par moment. Ces paramètres changeants sont transmis ou stockés et utilisés pour piloter un autre modèle dans le décodeur qui reproduit le son.

Les formats avec perte sont souvent utilisés pour la distribution de streaming audio ou de communication interactive (comme dans les réseaux de téléphonie cellulaire)., Dans de telles applications, les données doivent être décompressées au fur et à mesure des flux de données, plutôt qu’après la transmission de l’ensemble du flux de données. Tous les codecs audio ne peuvent pas être utilisés pour les applications de streaming.

la Latence introduite par les méthodes utilisées pour coder et décoder les données. Certains codecs analysent un segment plus long, appelé trame, des données pour optimiser l’efficacité, puis le codent d’une manière qui nécessite un segment de données plus important à la fois pour décoder., La latence inhérente à l’algorithme de codage peut être critique; par exemple, lorsqu’il y a une transmission bidirectionnelle de données, comme avec une conversation téléphonique, des retards importants peuvent sérieusement dégrader la qualité perçue.

contrairement à la vitesse de compression, qui est proportionnelle au nombre d’opérations requises par l’algorithme, ici temps de latence correspond au nombre d’échantillons qui doivent être analysés avant d’un bloc de audio est traité. Dans le cas minimum, la latence est de zéro échantillon (par exemple, si le codeur/décodeur réduit simplement le nombre de bits utilisés pour quantifier le signal)., Les algorithmes de domaine temporel tels que LPC ont également souvent de faibles latences, d’où leur popularité dans le codage vocal pour la téléphonie. Dans des algorithmes tels que MP3, cependant, un grand nombre d’échantillons doivent être analysés pour mettre en œuvre un modèle psychoacoustique dans le domaine fréquentiel, et la latence est de l’ordre de 23 ms (46 ms pour la communication bidirectionnelle).

Speech encodingEdit

L’encodage vocal est une catégorie importante de compression de données audio. Les modèles perceptifs utilisés pour estimer ce qu’une oreille humaine peut entendre sont généralement quelque peu différents de ceux utilisés pour la musique., La gamme de fréquences nécessaires pour transmettre les sons d’une voix humaine est normalement beaucoup plus étroite que celle nécessaire pour la musique, et le son est normalement moins complexe. En conséquence, la parole peut être codée à haute qualité en utilisant un débit binaire relativement faible.

Si les données à compresser sont analogiques (comme une tension qui varie avec le temps), la quantification est utilisée pour les numériser en nombres (normalement entiers). Cela est considéré comme un convertisseur analogique-numérique (A/D) à la conversion., Si les entiers générés par quantification sont de 8 bits chacun, alors toute la plage du signal analogique est divisée en 256 intervalles et toutes les valeurs de signal dans un intervalle sont quantifiées au même nombre. Si des entiers de 16 bits sont générés, la plage du signal analogique est divisée en 65 536 intervalles.

Cette relation illustre le compromis entre haute résolution (un grand nombre d’intervalles analogiques) et haute compression (petits entiers générés). Cette application de quantification est utilisée par plusieurs méthodes de compression vocale., Ceci est accompli, en général, par une combinaison de deux approches:

• ne codent que les sons qui pourraient être émis par une seule voix humaine.
• jeter plus de données dans le signal-en gardant juste assez pour reconstruire une voix « intelligible » plutôt que toute la gamme de fréquences de l’audition humaine.

peut-être les premiers algorithmes utilisés dans le codage de la parole (et la compression de données audio en général) étaient l’algorithme A-law et l’algorithme μ-law.,

HistoryEdit

le codage perceptuel a été utilisé pour la première fois pour la compression de codage vocal, avec le codage prédictif linéaire (LPC). Les premiers concepts de LPC remontent aux travaux de Fumitada Itakura (Université de Nagoya) et Shuzo Saito (Nippon Telegraph and Telephone) en 1966. Au cours des années 1970, Bishnu S. Atal et Manfred R., Schroeder chez Bell Labs a développé une forme de LPC appelée adaptive predictive coding (APC), un algorithme de codage perceptuel qui exploitait les propriétés de masquage de l’oreille humaine, suivi au début des années 1980 par l’algorithme de prédiction linéaire excitée par le code (CELP) qui a atteint un taux de compression important pour son époque. Le codage perceptuel est utilisé par les formats de compression audio modernes tels que MP3 et AAC.

Le premier système de compression audio d’automatisation de diffusion commerciale au monde a été développé par Oscar Bonello, professeur d’ingénierie à l’Université de Buenos Aires., En 1983, utilisant le principe psychoacoustique du masquage des bandes critiques publié pour la première fois en 1967, il a commencé à développer une application pratique basée sur L’ordinateur IBM PC récemment développé, et le système d’automatisation de la diffusion a été lancé en 1987 sous le nom D’Audicom. Vingt ans plus tard, presque toutes les stations de radio du monde utilisaient une technologie similaire fabriquée par un certain nombre d’entreprises.

un recueil de littérature pour une grande variété de systèmes de codage audio a été publié dans le Journal on Selected Areas in Communications (JSAC) de l’IEEE, en février 1988., Bien qu’il y ait eu quelques articles d’avant cette époque, cette collection a documenté toute une variété de codeurs audio finis et fonctionnels, presque tous utilisant des techniques perceptives (c.-à-d. masquage) et une sorte d’analyse de fréquence et de codage silencieux back-end. Plusieurs de ces articles ont souligné la difficulté d’obtenir un son numérique propre et de qualité à des fins de recherche. La plupart, sinon tous, des auteurs de L’édition JSAC étaient également actifs dans le Comité audio MPEG-1, qui a créé le format MP3.,

VideoEdit

la compression vidéo est une implémentation pratique du codage source dans la théorie de l’information. En pratique, la plupart des codecs vidéo sont utilisés parallèlement aux techniques de compression audio pour stocker les flux de données séparés mais complémentaires en un seul paquet combiné en utilisant des formats dits conteneurs.

La vidéo non compressée nécessite un débit de données très élevé. Bien que les codecs de compression vidéo sans perte fonctionnent avec un facteur de compression de 5 à 12, une vidéo de compression avec perte H. 264 typique a un facteur de compression entre 20 et 200.,

Les deux principales techniques de compression vidéo utilisées dans les normes de codage vidéo sont la transformée de cosinus discrète (DCT) et la compensation de mouvement (MC). La plupart des normes de codage vidéo, telles que les formats H. 26x et MPEG, utilisent généralement le codage vidéo DCT à compensation de mouvement (block motion compensation).

l’Encodage theoryEdit

les données Vidéo peuvent être représentées par une série d’images. Ces données contiennent généralement d’abondantes quantités de redondance spatiale et temporelle. Les algorithmes de compression vidéo tentent de réduire la redondance et de stocker les informations de manière plus compacte.,

La plupart des formats et codecs de compression vidéo exploitent à la fois la redondance spatiale et temporelle (par exemple grâce au codage de différence avec compensation de mouvement). Les similitudes peuvent être codées en stockant uniquement les différences entre, par exemple, des trames temporellement adjacentes (codage inter-trames) ou des pixels spatialement adjacents (codage intra-trames).La compression inter-trames (un codage delta temporel) est l’une des techniques de compression les plus puissantes. Il (re)utilise les données d’une ou plusieurs trames antérieures ou ultérieures dans une séquence pour décrire la trame actuelle., Le codage Intra-trame, d’autre part, utilise uniquement des données à partir de la trame actuelle, ce qui est effectivement une compression d’image fixe.

Une classe de formats spécialisés utilisés dans les caméscopes et le montage vidéo utilisent des schémas de compression moins complexes qui limitent leurs techniques de prédiction à la prédiction intra-trame.

habituellement, la compression vidéo utilise en outre des techniques de compression avec perte comme la quantification qui réduisent les aspects des données source qui sont (plus ou moins) sans rapport avec la perception visuelle humaine en exploitant les caractéristiques perceptives de la vision humaine., Par exemple, les petites différences de couleur sont plus difficiles à percevoir que les changements de luminosité. Les algorithmes de Compression peuvent faire la moyenne d’une couleur sur ces zones similaires pour réduire l’espace, d’une manière similaire à celles utilisées dans la compression D’image JPEG. Comme dans toute compression avec perte, il existe un compromis entre la qualité vidéo et le débit binaire, le coût de traitement de la compression et de la décompression et la configuration système requise. Une vidéo fortement compressée peut présenter des artefacts visibles ou distrayants.,

D’autres méthodes que les formats de transformation basés sur DCT répandus, tels que la compression fractale, la poursuite de correspondance et l’utilisation d’une transformée en ondelettes discrètes (DWT), ont fait l’objet de certaines recherches, mais ne sont généralement pas utilisées dans des produits pratiques (à l’exception de l’utilisation du codage en ondelettes comme codeurs L’intérêt pour la compression fractale semble diminuer, en raison d’une analyse théorique récente montrant un manque comparatif d’efficacité de telles méthodes.,

Inter-frame codingEdit

Inter-trame de codage fonctionne en comparant chaque image de la vidéo avec la précédente. Les trames individuelles d’une séquence vidéo sont comparées d’une trame à l’autre, et le codec de compression vidéo envoie uniquement les différences à la trame de référence. Si la trame contient des zones où rien n’a bougé, le système peut simplement émettre une courte commande qui copie cette partie de la trame précédente dans la suivante., Si des sections du cadre se déplacent de manière simple, le compresseur peut émettre une commande (légèrement plus longue) qui indique au décompresseur de décaler, de faire pivoter, d’éclaircir ou d’assombrir la copie. Cette commande plus longue reste encore beaucoup plus courte que la compression intraframe. Habituellement, l’encodeur transmettra également un signal de résidu qui décrit les différences plus subtiles restantes à l’imagerie de référence. En utilisant le codage d’entropie, ces signaux de résidu ont une représentation plus compacte que le signal complet., Dans les zones de vidéo avec plus de mouvement, la compression doit coder plus de données pour suivre le plus grand nombre de pixels qui changent. Généralement lors des explosions, des flammes, des troupeaux d’animaux et dans certains plans panoramiques, le détail à haute fréquence entraîne une diminution de la qualité ou une augmentation du débit binaire variable.,

Formats de transformation basés sur des blocs hybridsEdit

Aujourd’hui, presque toutes les méthodes de compression vidéo couramment utilisées (par exemple, celles des normes approuvées par l’IT-T ou ISO) partagent la même architecture de base qui remonte à H. 261 qui a été normalisée en 1988 par l’IT-T., Ils s’appuient principalement sur le DCT, appliqué à des blocs rectangulaires de pixels voisins, et la prédiction temporelle à l’aide de vecteurs de mouvement, ainsi que de nos jours également une étape de filtrage en boucle.

Au stade de la prédiction, diverses techniques de déduplication et de codage des différences sont appliquées qui aident à décorréler les données et à décrire de nouvelles données basées sur des données déjà transmises.

Ensuite, des blocs rectangulaires de données de pixels (résidus) sont transformés en domaine fréquentiel pour faciliter le ciblage des informations non pertinentes dans la quantification et pour une certaine réduction de la redondance spatiale., La transformée de cosinus discrète (DCT) qui est largement utilisée à cet égard a été introduite par N. Ahmed, T. Natarajan et K. R. Rao en 1974.

Dans la phase principale de traitement avec perte, les données sont quantifiées afin de réduire les informations non pertinentes pour la perception visuelle humaine.

Dans la dernière étape, la redondance statistique est largement éliminée par un codeur d’entropie qui applique souvent une forme de codage arithmétique.

Dans une étape supplémentaire de filtrage en boucle, divers filtres peuvent être appliqués au signal d’image reconstruit., En calculant ces filtres également à l’intérieur de la boucle de codage, ils peuvent aider à la compression, car ils peuvent être appliqués au matériel de référence avant qu’il ne soit utilisé dans le processus de prédiction et ils peuvent être guidés en utilisant le signal d’origine. L’exemple le plus populaire sont les filtres de déblocage qui brouillent les artefacts de blocage des discontinuités de quantification aux limites des blocs de transformation.

HistoryEdit

En 1967, A. H. Robinson et C., Cherry a proposé un schéma de compression de la bande passante pour la transmission de signaux de télévision analogiques. La transformation en cosinus discrète (DCT), qui est fondamentale pour la compression vidéo moderne, a été introduite par Nasir Ahmed, T. Natarajan et K. R. Rao en 1974.

H. 261, qui a fait ses débuts en 1988, a introduit commercialement l’architecture de base répandue de la technologie de compression vidéo. Ce fut le premier format de codage vidéo basé sur la compression DCT, qui deviendra par la suite la norme pour tous les principaux formats de codage vidéo qui ont suivi. H.,261 a été développé par un certain nombre de sociétés, y compris Hitachi, PictureTel, NTT, BT et Toshiba.

les normes de codage vidéo les plus populaires utilisées pour les codecs ont été les normes MPEG. MPEG-1 a été développé par le Motion Picture Experts Group (MPEG) en 1991, et il a été conçu pour compresser la vidéo de qualité VHS. Il a été remplacé en 1994 par MPEG-2 / h. 262, qui a été développé par un certain nombre de sociétés, principalement Sony, Thomson et Mitsubishi Electric. MPEG-2 est devenu le format vidéo standard pour la télévision numérique DVD et SD. En 1999, il a été suivi par MPEG-4 / H.,263, qui a été un grand bond en avant pour la technologie de compression vidéo. Il a été développé par un certain nombre de sociétés, principalement Mitsubishi Electric, Hitachi et Panasonic.

Le format de codage vidéo le plus utilisé est H. 264/MPEG-4 AVC. Il a été développé en 2003 par un certain nombre d’organisations, principalement Panasonic, Godo Kaisha IP Bridge et LG Electronics. AVC a introduit commercialement les algorithmes modernes de codage arithmétique binaire adaptatif au contexte (CABAC) et de codage à longueur variable adaptatif au contexte (CAVLC)., AVC est la principale norme d’encodage vidéo pour les disques Blu-ray, et est largement utilisé par les services Internet de streaming tels que YouTube, Netflix, Vimeo et iTunes Store, les logiciels Web tels que Adobe Flash Player et Microsoft Silverlight, et diverses émissions HDTV sur la télévision terrestre et par satellite.,

GeneticsEdit

Les algorithmes de compression génétique sont la dernière génération d’algorithmes sans perte qui compressent des données (généralement des séquences de nucléotides) en utilisant à la fois des algorithmes de compression conventionnels et des algorithmes génétiques adaptés au type de données spécifique. En 2012, une équipe de scientifiques de L’Université Johns Hopkins a publié un algorithme de compression génétique qui n’utilise pas de génome de référence pour la compression., HAPZIPPER a été conçu pour les données HapMap et réalise une compression de plus de 20 fois (réduction de 95% de la taille du fichier), offrant une compression de 2 à 4 fois meilleure et en un temps beaucoup plus rapide que les principaux utilitaires de compression à usage général. Pour cela, Chanda, Elhaik et Bader ont introduit le codage MAF (MAFE), qui réduit l’hétérogénéité de l’ensemble de données en triant les SNP par leur fréquence d’allèle mineur, homogénéisant ainsi l’ensemble de données. D’autres algorithmes en 2009 et 2013 (DNAZip et GenomeZip) ont des taux de compression allant jusqu’à 1200 fois-ce qui permet de stocker 6 milliards de génomes humains diploïdes basepair dans 2.,5 mégaoctets (par rapport à un génome de référence ou en moyenne sur de nombreux génomes). Pour une référence dans les compresseurs de données de Génétique/génomique, voir