Vés al contingut

Compressió de dades

De la Viquipèdia, l'enciclopèdia lliure
(S'ha redirigit des de: Algorisme de compressió)

La compressió de dades,[1] aplicada al món de la informàtica, consisteix en el procés de codificació de dades[2] utilitzant el mínim nombre possible de bits, o unitats d'informació. Això es pot aconseguir gràcies a la utilització d'esquemes de codificat o còdecs.[3] La compressió només funciona si tant l'emissor com el receptor de la informació del missatge han acordat a priori un esquema concret de codificat. Per exemple, podríem acordar que a partir d'aquesta línia de text escriurem cp en comptes de compressió, això ens estalviaria uns quants bits i faria que l'arxiu final ocupés menys. Però perquè el lector d'aquest article comprengui el significat de cp hem d'informar-lo amb anterioritat (ha de conèixer l'esquema de codificat).

Principalment, la compressió és possible gràcies al fet que al món real, les dades són molt redundants, o bé són representades en una "forma humana", és a dir, fàcils d'interpretar per tots nosaltres però no representats d'una manera òptima. La compressió és important perquè ens permet d'estalviar recursos que resultarien cars, com ara espai de disc o amplada de banda en la nostra xarxa. Per això s'han creat diversos tipus d'algorismes de compressió segons el tipus de dades que volem comprimir. Bàsicament, es podrien dividir entre els que tenen pèrdues per a imatge, so i vídeo, i els que són sense pèrdua per desar dades, programes, o informació que no pugui ser alterada.

La compressió és un cas particular de la codificació, que destaca perquè el codi resultant té menor mida que l'original.

La compressió de dades consisteix en la reducció del volum d'informació tractable (processar, transmetre o gravar). En principi, amb la compressió es pretén transportar la mateixa informació, però utilitzant la menor quantitat d'espai.

L'espai que ocupa una informació codificada (dades, senyal digital, etc.) sense compressió és el quocient entre la freqüència de mostreig i la resolució. Per tant, com més bits s'empren major serà la mida del fitxer. No obstant això, la resolució ve imposada pel sistema digital amb què es treballa i no es pot alterar el nombre de bits a voluntat, de manera que s'utilitza la compressió, per transmetre la mateixa quantitat d'informació que ocuparia una gran resolució en un nombre inferior de bits.

La compressió de dades es basa fonamentalment a buscar repeticions en sèries de dades per després emmagatzemar només la dada amb el nombre de vegades que es repeteix. Així, per exemple, si en un fitxer apareix una seqüència com "aaaaaa", ocupant 6 bytes es podria emmagatzemar simplement "6A" que ocupa només 2 bytes, en algorisme RLE.

En realitat, el procés és molt més complex, ja que rarament s'aconsegueix trobar patrons de repetició tan exactes (excepte en algunes imatges). S'utilitzen algorismes de compressió.

Algorismes de compressió

[modifica]
  • D'una banda, alguns busquen sèries llargues que després codifiquen en formes més breus.
  • D'altra banda, alguns algorismes, com l'algorisme de Huffman, examinen els caràcters més repetits per després codificar de forma més curta els que més es repeteixen.
  • Altres, com el LZW, construeixen un diccionari amb els patrons trobats, als quals es fa referència de manera posterior.
  • També aquesta una manera de comprimir que és codificant els bytes parells és molt senzill i fàcil d'entendre.

A l'hora de parlar de compressió cal tenir presents dos conceptes:

  1. Redundància: dades que són repetitives o previsibles
  2. Entropia: la informació nova o essencial que es defineix com la diferència entre la quantitat total de dades d'un missatge i la seva redundància.

La informació que transmeten les dades pot ser de tres tipus:

  1. Redundant: informació repetitiva o previsible.
  2. Irrellevant: informació que no podem apreciar i l'eliminació per tant no afecta el contingut del missatge. Per exemple, si les freqüències que és capaç de captar l'oïda humana estan entre 16/20 Hz i 16.000/20.000 Hz, serien irrellevants aquelles freqüències que estiguessin per sota o per sobre d'aquests valors.
  3. Bàsica: la rellevant. La que no és ni redundant ni irrellevant. La que ha de ser transmesa perquè es pugui reconstruir el senyal.

Tenint en compte aquests tres tipus d'informació, s'estableixen tres tipologies de compressió de la informació:

  1. Sense pèrdues reals: és a dir, transmetent tota l'entropia del missatge (tota la informació bàsica i irrellevant, però eliminant la redundant).
  2. Subjectivament sense pèrdues: és a dir, a més d'eliminar la informació redundant s'elimina també la irrellevant.
  3. Subjectivament amb pèrdues: s'elimina certa quantitat d'informació bàsica, de manera que el missatge es reconstruirà amb errors perceptibles però tolerables (per exemple: la videoconferència).

Diferències entre compressió amb pèrdua i sense

[modifica]

L'objectiu de la codificació és sempre reduir la mida de la informació, intentant que aquesta reducció de mida no afecti el contingut. No obstant això, la reducció de dades pot afectar o no a la qualitat de la informació:

  • Compressió sense pèrdua: les dades abans i després de comprimir-són exactes a la compressió sense pèrdua.[3] En el cas de la compressió sense pèrdua més compressió només implica més temps de procés. El bitrate sempre és variable a la compressió sense pèrdua. S'utilitza principalment en la compressió de text.
  • Un algorisme de compressió amb pèrdua pot eliminar dades per reduir encara més la mida, de manera que se sol reduir la qualitat.[3] A la compressió amb pèrdua el bit rate pot ser constant o variable. Cal tenir en compte que una vegada realitzada la compressió, no es pot obtenir el senyal original, encara que sí una aproximació la semblança amb l'original dependrà del tipus de compressió. S'utilitza principalment en la compressió d'imatge, vídeo i so.

Usos

[modifica]

Imatge

[modifica]
Article principal: Compressió d'imatge

La codificació d'entropia es va originar a la dècada de 1940 amb la introducció de la codificació Shannon-Fano,[4] la base de la codificació Huffman que es va desenvolupar el 1950.[5] La codificació per transformada es remunta a finals de la dècada de 1960, amb la introducció de la transformada ràpida de Fourier (FFT) en 1968 i la transformada Hadamard en 1969.[6]

Una important tècnica de compressió d'imatges és la transformada de cosinus discreta (DCT), una tècnica desenvolupada a principis de la dècada de 1970.[7] La DCT és la base del JPEG, un format de compressió amb pèrdues que va ser introduït pel Joint Photographic Experts Group (JPEG) en 1992.[8] JPEG redueix en gran manera la quantitat de dades necessàries per representar una imatge a costa d'una reducció relativament petita de la qualitat de la mateixa i s'ha convertit en el format d'un fitxer d'imatge més utilitzat.[9][10] El seu algorisme de compressió altament eficient basat en la DCT va ser en gran part responsable de l'àmplia proliferació d'imatges digitals i fotos digitals.[11]

Lempel-Ziv-Welch (LZW) és un algorisme de compressió sense pèrdues desenvolupat el 1984. S'utilitza en el format GIF, introduït el 1987.[12] DEFLATE, un algorisme de compressió sense pèrdues especificat el 1996, s'utilitza en el format Portable Network Graphics (PNG).[13]

La compressió wavelet, l'ús de wavelets en la compressió d'imatges, va començar després del desenvolupament de la codificació DCT.[14] L'estàndard JPEG 2000 es va introduir l'any 2000.[15] A diferència de l'algorisme DCT utilitzat pel format JPEG original, JPEG 2000 utilitza al seu lloc algorismes de transformada d'ondeta discreta (DWT).[16][17][18] La tecnologia JPEG 2000, que inclou l'extensió Motion JPEG 2000, va ser seleccionada com l'estàndard de codificació de vídeo per al cinema digital el 2004.[19]

Àudio

[modifica]
Vegeu també: Còdec d'àudio

La compressió de dades d'àudio, que no s'ha de confondre amb la compressió de rang dinàmic, té el potencial de reduir l'amplada de banda i els requisits d'emmagatzematge de les dades d'àudio. Els algorismes de compressió d'àudio s'implementen a programari com a còdecs d'àudio. Tant en la compressió amb pèrdues com en la compressió sense pèrdues, es redueix la redundància de la informació, utilitzant mètodes com la codificació, la quantització, la transformada de cosinus discreta i la predicció lineal per reduir la quantitat d'informació utilitzada per representar les dades sense comprimir.

Els algorismes de compressió d'àudio amb pèrdues proporcionen una major compressió i s'utilitzen en nombroses aplicacions d'àudio, com ara Vorbis i MP3. Aquests algoritmes es basen gairebé tots en la psicoacústica per eliminar o reduir la fidelitat dels sons menys audibles, reduint així l'espai necessari per emmagatzemar-los o transmetre'ls.[20][21]

La compensació acceptable entre la pèrdua de qualitat d'àudio i la mida de transmissió o emmagatzematge depèn de l'aplicació. Per exemple, un disc compacte (CD) de 640 MB conté aproximadament una hora de música d'alta fidelitat sense comprimir, menys de 2 hores de música comprimida sense pèrdues o 7 hores de música comprimida en el format MP3 a una taxa de bits mitjana. Una gravadora de so digital pot emmagatzemar normalment unes 200 hores de parla clarament intel·ligible a 640 MB.[22]

La compressió d'àudio sense pèrdues produeix una representació de les dades digitals que es pot descodificar en un duplicat digital exacte de l'original. Les ràtios de compressió se situen al voltant del 50-60 % de la mida original,[23] que és similar als de la compressió genèrica de dades sense pèrdues. Els còdecs sense pèrdues utilitzen l'ajust de corbes o la predicció lineal com a base per estimar el senyal. Els paràmetres que descriuen l'estimació i la diferència entre l'estimació i el senyal real es codifiquen per separat.[24]

Hi ha diversos formats de compressió d'àudio sense pèrdues. Vegeu llista de còdecs sense pèrdues per obtenir una llista. Alguns formats estan associats a un sistema diferent, com Direct Stream Transfer, utilitzat en Super Audio CD i Meridian Lossless Packing, utilitzat en DVD-Audio, Dolby TrueHD , Blu-ray i HD DVD.

Alguns formats de fitxer d'àudio presenten una combinació d'un format amb pèrdues i una correcció sense pèrdues; això permet eliminar la correcció per obtenir fàcilment un fitxer amb pèrdues. Aquests formats inclouen MPEG-4 SLS (Scalable to Lossless), WavPack i OptimFROG DualStream.

Quan es processaran fitxers d'àudio, ja sigui per compressió posterior o per a edició, és desitjable treballar a partir d'un original inalterat (sense comprimir o comprimit sense pèrdues). El processament d'un fitxer comprimit sense pèrdues per a alguna finalitat sol produir un resultat final inferior a la creació del mateix fitxer comprimit a partir d'un original sense comprimir. A més de per a l'edició o la barreja de so, la compressió d'àudio sense pèrdues s'utilitza sovint per a l'emmagatzematge d'arxius, o com a còpies mestres.

Compressió d'àudio amb pèrdues

[modifica]
Comparació d'espectrogrames d'àudio en un format sense comprimir i en diversos formats amb pèrdues. Els espectrogrames amb pèrdues mostren bandlimiting de les freqüències més altes, una tècnica comuna associada a la compressió d'àudio amb pèrdues.

La compressió d'àudio amb pèrdues s'utilitza en una àmplia gamma d'aplicacions. A més de les aplicacions independents de reproducció d'arxius en reproductors MP3 o ordinadors, els fluxos d'àudio comprimits digitalment s'utilitzen a la majoria dels DVD de vídeo, la televisió digital, els mitjans de transmissió a Internet, la ràdio per satèl·lit i per cable, i cada vegada més a les emissions de ràdio terrestre. La compressió amb pèrdues sol aconseguir una compressió molt més gran que la compressió sense pèrdues, en descartar les dades menys crítiques basant-se en optimitzacions psicoacústiques.[25]

La psicoacústica reconeix que no totes les dades d'un flux d'àudio poden ser percebudes pel sistema auditiu humà. La major part de la compressió amb pèrdues redueix la redundància identificant primer els sons perceptualment irrellevants, és a dir, els sons molt difícils de sentir. Exemples típics són les freqüències altes o els sons que es produeixen alhora que els sons més forts. Aquests sons irrellevants es codifiquen amb menor precisió o no es codifiquen en absolut.

A causa de la naturalesa dels algorismes amb pèrdues, la qualitat de l'àudio pateix una pèrdua de generació digital quan es descomprimeix i recomprimeix un fitxer. Això fa que la compressió amb pèrdues sigui inadequada per emmagatzemar els resultats intermedis en aplicacions professionals d'enginyeria d'àudio, com l'edició de so i la gravació multipista. No obstant això, els formats amb pèrdues, com el MP3, són molt populars entre els usuaris finals, ja que la mida del fitxer es redueix al 5-20 % de la mida original i un megabyte pot emmagatzemar aproximadament un minut de música amb la qualitat adequada.

Mètodes de codificació
[modifica]

Per determinar quina informació d'un senyal d'àudio és irrellevant des del punt de vista perceptiu, la majoria dels algorismes de compressió amb pèrdues utilitzen transformacions com la transformada de cosinus discreta (MDCT) per convertir les formes d'ona mostrades al domini del temps en un domini de transformació, normalment el domini de la freqüència. Un cop transformades, les freqüències dels components es poden prioritzar segons la seva audibilitat. L'audibilitat dels components espectrals s'avalua utilitzant el llindar absolut d'audició i els principis d'emmascarament simultani -el fenomen en què un senyal és emmascarat per un altre senyal separat per la freqüència- i, en alguns casos, emmascarament temporal –en què un senyal és emmascarat per un altre senyal separat pel temps. També es poden utilitzar els contorns d'igual sonoritat per ponderar la importància perceptiva dels components. Els models de la combinació oïda-cervell humà que incorporen aquests efectes solen denominar-se model psicoacústic.[26]

Altres tipus de compressors amb pèrdues, com la codificació predictiva lineal utilitzada amb la parla, són codificadors basats en la font. La LPC utilitza un model del tracte vocal humà per analitzar els sons de la parla i inferir els paràmetres utilitzats pel model per produir-los moment a moment. Aquests paràmetres canviants es transmeten o emmagatzemen i s'utilitzen per impulsar un altre model al descodificador que reprodueix el so.

Els formats amb pèrdues s'utilitzen sovint per a la distribució d'àudio en streaming o la comunicació interactiva (com a les xarxes de telefonia mòbil). En aquestes aplicacions, les dades s'han de descomprimir a mesura que flueixen, en lloc de fer-ho després que s'hagi transmès tot el flux de dades. No tots els còdecs d'àudio es poden utilitzar per a aplicacions de streaming.[25]

La Latència és introduïda pels mètodes utilitzats per a codificar i descodificar les dades. Alguns còdecs analitzen un segment més llarg, anomenat trama, de les dades per optimitzar l'eficiència, i després el codifiquen de manera que es requereixi un segment més gran de dades alhora per descodificar. La latència inherent a l'algorisme de codificació pot ser crítica; per exemple, quan hi ha una transmissió bidireccional de dades, com en una conversa telefònica, els retards significatius poden degradar seriosament la qualitat percebuda.

A diferència de la velocitat de compressió, que és proporcional al nombre d'operacions que requereix l'algorisme, aquí la latència fa referència al nombre de mostres que cal analitzar abans de processar un bloc d'àudio. En el cas mínim, la latència és de zero mostres (per exemple, si el codificador/decodificador simplement redueix el nombre de bits utilitzats per quantificar el senyal). Els algorismes del domini del temps, com el LPC, també solen tenir latències baixes, per això la seva popularitat en la codificació de la parla per a la telefonia. Tanmateix, en algoritmes com el MP3, cal analitzar un gran nombre de mostres per implementar un model psicoacústic en el domini de la freqüència, i la latència és de l'ordre de 23 ms.

Codificació de la parla
[modifica]

La codificació de la parla és una categoria important de la compressió de dades d'àudio. Els models perceptius utilitzats per estimar quins aspectes de la parla pot escoltar l'oïda humana solen ser una mica diferents dels utilitzats per a la música. El rang de freqüències necessari per transmetre els sons d'una veu humana és normalment molt més estret que el necessari per a la música, i el so normalment és menys complex. Per això, la veu es pot codificar amb alta qualitat utilitzant una taxa de bits relativament baixa.

Això s'aconsegueix, en general, mitjançant una combinació de dos enfocaments:

  • Codificar només els sons que podria emetre una sola veu humana.
  • Rebutjar la major part de les dades del senyal, conservant només prou per reconstruir una veu "intel·ligible" en lloc de tota la gamma de freqüències de l'oïda humana.

Els primers algorismes utilitzats en la codificació de la parla (i en la compressió de dades d'àudio en general) van ser l'algorisme A-law i l'algorisme μ-law.

Història

[modifica]
Solidyne 922: La primera targeta de so comercial de compressió de bits d'àudio per a PC, 1990

Les primeres investigacions sobre àudio es van realitzar als Laboratoris Bell. Allà, el 1950, C. Chapin Cutler va presentar la patent de la modulació diferencial per codi d'impulsos (DPCM).[27] El 1973, P. Cummiskey, Nikil S. Jayant i James L. Flanagan van introduir la DPCM adaptativa (ADPCM).[28][29]

La codificació perceptiva es va utilitzar per primera vegada per a la compressió de la codificació de la parla, amb la codificació predictiva lineal (LPC).[30] Els conceptes inicials de LPC es remunten als treballs de Fumitada Itakura (Universitat de Nagoya) i Shuzo Saito (Nippon Telegraph and Telephone) el 1966.[31] Durant la dècada de 1970, Bishnu S. Atal i Manfred R. Schroeder a Bell Labs van desenvolupar una forma de LPC anomenada codificació predictiva adaptativa (APC), un algorisme de codificació perceptiva que explotava les propietats d'emmascarament de l'oïda humana, seguit a principis dels anys vuitanta amb l'algorisme de predicció lineal excitada per codi (CELP), que va aconseguir una relació de compressió significativa per a la seva època.[30] La codificació perceptual és utilitzada pels formats moderns de compressió d'àudio com el MP3[30] i l'AAC.

La transformada de cosinus discreta (DCT), desenvolupada per Nasir Ahmed, T. Natarajan i K. R. Rao en 1974,[32] va proporcionar la base per a la transformada discreta del cosinus modificada (MDCT) utilitzada pels formats moderns de compressió d'àudio com el MP3,[33] Dolby Digital,[34][35] i AAC.[36] El MDCT va ser proposat per J. P. Princen, A. W. Johnson i A. B. Bradley en 1987,[37] després d'un treball anterior de Princen i Bradley a 1986.[38][32]

El primer sistema comercial d'automatització d'emissions d'àudio del món va ser desenvolupat per Oscar Bonello, un professor d'enginyeria de la Universitat de Buenos Aires.[39][40] El 1983, utilitzant el principi psicoacústic de l'emmascarament de les bandes crítiques publicat per primera vegada el 1967,[41] va començar a desenvolupar una aplicació pràctica basada en el recentment desenvolupat ordinador IBM PC, i el sistema d'automatització de la radiodifusió va ser llançat en 1987 sota el nom d'Audicom. Vint anys després, gairebé totes les emissores de ràdio del món feien servir una tecnologia similar fabricada per diverses empreses.

El febrer de 1988 es va publicar un compendi bibliogràfic sobre una gran varietat de sistemes de codificació d'àudio al Journal on Selected Areas in Communications (JSAC) de l'IEEE. Encara que hi havia alguns articles d'abans, aquesta col·lecció documentava tota una varietat de codificadors d'àudio acabats i en funcionament, gairebé tots utilitzant tècniques perceptives i algun tipus d'anàlisi de freqüència i codificació sense soroll de fons.[42]

Vídeo

[modifica]
Vegeu també: Còdec de vídeo

El vídeo sense comprimir requereix una taxa de dades molt alta. Encara que els còdecs mitjançant compressió de vídeo sense pèrdues funcionen amb un factor de compressió de 5 a 12, un vídeo típic de compressió amb pèrdues H.264 té un factor de compressió d'entre 20 i 200.[43]

Les dues tècniques clau de compressió de vídeo utilitzades en els estàndards de codificació de vídeo són la transformada de cosinus discreta (DCT) i la compensació de moviment (MC). La majoria dels estàndards de codificació de vídeo, com els formats H.26x i MPEG, solen utilitzar la codificació de vídeo DCT amb compensació de moviment (compensació de moviment en bloc).[44][45]

La majoria dels còdecs de vídeo s'utilitzen juntament amb les tècniques de compressió d'àudio per emmagatzemar els fluxos de dades separats però complementaris com un paquet combinat utilitzant els anomenats formats contenidors.[46]

Teoria de la codificació

[modifica]

Les dades de vídeo es poden representar com una sèrie de fotogrames d'imatges fixes. Aquestes dades solen contenir abundants quantitats de redundància espacial i temporal. Els algorismes de compressió de vídeo intenten reduir la redundància i emmagatzemar la informació de manera més compacta.

La majoria dels formats de compressió de vídeo i còdecs de vídeo exploten la redundància espacial i temporal (per exemple, mitjançant la codificació de diferències amb compensació de moviment). Les similituds poden codificar-se emmagatzemant només les diferències entre, per exemple, fotogrames temporalment adjacents (codificació interquadre) o píxels espacialment adjacents (codificació intraquadre). La compressió Inter-frame (una codificació delta temporal) (re)utilitza les dades d'un o més fotogrames anteriors o posteriors d'una seqüència per descriure el fotograma actual. La codificació intraquadre, per contra, utilitza només dades del quadre actual, sent en realitat una compressió d'imatge.[26]

Els formats de codificació de vídeo entre fotogrames utilitzats a les càmeres de vídeo i en l'edició de vídeo empren una compressió més simple que utilitza només la predicció intra-frame. Això simplifica el programari dedició de vídeo, ja que evita que un fotograma comprimit es refereixi a dades que l'editor ha eliminat.

Normalment, la compressió de vídeo empra a més tècniques de compressió amb pèrdues com la quantització que redueixen aspectes de les dades d'origen que són (més o menys) irrellevants per a la percepció visual humana explotant característiques perceptives de la visió humana. Per exemple, les petites diferències de color són més difícils de percebre que els canvis de brillantor. Els algorismes de compressió poden fer una mitjana d'un color a través d'aquestes àrees similars d'una manera similar als utilitzats en la compressió d'imatges JPEG.[47] Com en tota compressió amb pèrdues, hi ha un compromís entre la qualitat de vídeo i la taxa de bits, el cost de processar la compressió i la descompressió, i els requisits del sistema. Els vídeos molt comprimits poden presentar artefactes de compressió visibles o molestos.

Altres mètodes diferents dels formats de transformació basats en la DCT, com la compressió fractal, la recerca de coincidències i l'ús d'una transformada wavelet discreta (DWT), han estat objecte d'algunes investigacions, però no se solen utilitzar en productes pràctics. La compressió wavelet s'utilitza en codificadors d'imatges fixes i de vídeo sense compensació de moviment. L'interès per la compressió fractal sembla estar disminuint, a causa de les anàlisis teòriques recents que mostren una manca d'eficàcia comparativa d'aquests mètodes.[26]

Codificació entre fotogrames
[modifica]
Vegeu també: Compensació de moviment

En la codificació entre fotogrames, es comparen els fotogrames individuals d'una seqüència de vídeo d'un fotograma a un altre i el còdec de compressió de vídeo registra les diferències respecte del fotograma de referència. Si el fotograma conté àrees en què no s'ha mogut res, el sistema pot simplement emetre una breu ordre que copiï aquesta part del fotograma anterior al següent. Si hi ha seccions del fotograma que es mouen de forma senzilla, el compressor pot emetre una ordre (lleugerament més llarg) que indiqui al descompressor que desplaci, trenqui, aclareixi o enfosqueixi la còpia. Aquesta comanda més llarga continua sent molt més curta que les dades generades per la compressió intraquadre. Normalment, el codificador també transmet un senyal de residu que descriu les altres diferències més subtils respecte a les imatges de referència. Utilitzant la codificació d'entropia, aquests senyals de residu tenen una representació més compacta que el senyal complet. A les zones de vídeo amb més moviment, la compressió ha de codificar més dades per mantenir el ritme del nombre més gran de píxels que canvien. Normalment, durant les explosions, les flames, els esbarts d'animals i en algunes preses panoràmiques, el detall d'alta freqüència provoca una disminució de la qualitat o un augment de la taxa de bits variable.

Formats de transformació híbrids basats en blocs

[modifica]
Etapes de processament d'un codificador de vídeo típic.

En l'actualitat, gairebé tots els mètodes de compressió de vídeo més utilitzats (per exemple, els que figuren a les normes aprovades per la UIT-T o la ISO) comparteixen la mateixa arquitectura bàsica que es remunta a la norma H.261, estandarditzada el 1988 per la UIT-T. Es basen principalment en la DCT, aplicada a blocs rectangulars de píxels veïns, i en la predicció temporal mitjançant vectors de moviment, així com, actualment, en una etapa de filtratge en bucle.

A l'etapa de predicció, s'apliquen diverses tècniques de deduplicació de dades i de codificació de diferències que ajuden a decorrelacionar les dades i a descriure les noves dades basant-se en les ja transmeses.

A continuació, els blocs rectangulars de dades de píxels restants es transformen en el domini de la freqüència. A la principal etapa de processament amb pèrdues, les dades del domini de la freqüència es quantifiquen per reduir la informació que és irrellevant per a la percepció visual humana.

En la darrera etapa, la redundància estadística s'elimina en gran manera mitjançant un codificador d'entropia que sol aplicar alguna forma de codificació aritmètica.

En una etapa addicional de filtratge en bucle es poden aplicar diversos filtres al senyal d'imatge reconstruït. En computar aquests filtres també dins del bucle de codificació poden ajudar a la compressió perquè es poden aplicar al material de referència abans que s'utilitzi en el procés de predicció i es poden guiar utilitzant el senyal original. L'exemple més popular són els filtres de desbloqueig que eliminen els artefactes de bloqueig de les discontinuïtats de quantificació als límits dels blocs de transformació.

Història

[modifica]

El 1967, A.H. Robinson i C. Cherry van proposar un esquema de compressió d'ample de banda de codificació de longitud de carrera per a la transmissió de senyals de televisió analògics.[48] La transformada de cosinus discreta (DCT), que és fonamental per a la compressió de vídeo moderna,[49] va ser introduïda per Nasir Ahmed, T. Natarajan i K. R. Rao a 1974.[32][50]

H.261, que va debutar el 1988, va introduir comercialment l'arquitectura bàsica prevalent de la tecnologia de compressió de vídeo.[51] Va ser el primer format de codificació de vídeo basat en la compressió DCT.[49] H.261 va ser desenvolupat per diverses empreses, entre les quals hi ha Hitachi, PictureTel, NTT, BT i Toshiba.[52]

Els estàndards de codificació de vídeo més populars utilitzats per als còdecs han estat els estàndards MPEG. MPEG-1 va ser desenvolupat pel Motion Picture Experts Group (MPEG) en 1991, i va ser dissenyat per comprimir vídeo de qualitat VHS. Va ser succeït el 1994 per MPEG-2/H.262,[51] que va ser desenvolupat per diverses empreses, principalment Sony, Thomson i Mitsubishi Electric.[53] MPEG-2 es va convertir en el format de vídeo estàndard per a DVD i televisió digital SD.[51] El 1999, el va seguir MPEG-4/H.263.[51] També va ser desenvolupat per diverses empreses, principalment Mitsubishi Electric, Hitachi i Panasonic.[54]

H.264/MPEG-4 AVC va ser desenvolupat el 2003 per diverses organitzacions, principalment Panasonic, Godo Kaisha IP Bridge i LG Electronics.[55] AVC va introduir comercialment els moderns algorismes de codificació aritmètica binària adaptable al context (CABAC) i codificació de longitud variable adaptable al context (CAVLC). AVC és el principal estàndard de codificació de vídeo per als discos Blu-ray, i és àmpliament utilitzat pels llocs web per compartir vídeos i els serveis de transmissió per Internet com YouTube, Netflix , Vimeo i iTunes Store, el programari web com Adobe Flash Player i Microsoft Silverlight, i diverses emissions de HDTV per televisió terrestre i per satèl·lit.

Genètica

[modifica]

Els algorismes de compressió genòmica són la darrera generació d'algoritmes sense pèrdues que comprimeixen dades (normalment seqüències de nucleòtids) utilitzant tant algorismes de compressió convencionals com algorismes genètics adaptats al tipus de dades específic. El 2012, un equip de científics de la Universitat Johns Hopkins va publicar un algorisme de compressió genètica que no utilitza un genoma de referència per a la compressió. HAPZIPPER es va adaptar a les dades del HapMap i aconsegueix una compressió de més de 20 vegades (95 % de reducció de la mida del fitxer), proporcionant una compressió de 2 a 4 vegades millor i és menys intensiva des del punt de vista computacional que les utilitats principals de compressió d'ús general. Per això, Chanda, Elhaik i Bader van introduir la codificació basada en MAF (MAFE), que redueix l'heterogeneïtat del conjunt de dades classificant els SNP per la seva freqüència al·lèlica menor, homogeneïtzant així el conjunt de dades.[56] Altres algorismes desenvolupats el 2009 i 2013 (DNAZip i GenomeZip) tenen ràtios de compressió de fins a 1200 vegades, cosa que permet emmagatzemar 6.000 milions de parells de bases de genomes humans diploides en 2,5 megabytes (en relació amb un genoma de referència o mitjana entre molts genomes).[57][58][59]

Hipòtesi

[modifica]

El treball de recerca científica de Boris Weisler se centrava en una línia àrida de la matemàtica: la teoria de grups algebraics. El vocable “grup” s'utilitza per designar el conjunt de simetries d'un objecte i la manera com interactuen. Òbviament, el grup dependrà de la geometria de l'objecte en qüestió. Ara bé, l'abstracció matemàtica permet definir la noció de grup sense un objecte subjacent, i a partir de la seva estructura interna reconstruir aquest objecte. La rellevància d'aquest procés és que ha permès descobrir de manera abstracta noves i insospitades geometries. En bregar directament amb grups s'utilitzen mètodes algebraics de gran formalitat. D'alguna manera, es treballa només amb variables i incògnites pensant sempre que hi ha un objecte per darrere, però sense aferrar-s'hi mai. Si mitjançant aquests mètodes s'aconsegueix establir un resultat, aleshores aquest tindrà conseqüències –de vegades insospitades– sobre aquests objectes “nebulosos” i la seva geometria. El seu Gran Teorema, espectacular, es pot llegir de la manera següent: “tot subgrup del grup de matrius d'entrades senceres i determinant 1 que és dens a la topologia Zarisky és gairebé dens a la topologia de congruències”. Encara que sembla un embarbussament, la veritat és que aquest resultat de 1984 és una veritable joia de la matemàtica, i va trigar anys a ser completament comprès i assimilat per la comunitat acadèmica.

D'aquest, de difícil comprensió, se'n deduiria un nou diferent concepte de "compressió sense compressió" basat, en principis "matemàtics-semàntics". Un terreny encara molt poc explorat. Si som capaços de comprendre la informació a “comprimir” com un mer llenguatge convencional, que consta de significat, però que s'expressa com a significant, i som capaços de traduir aquests significants a números, nombres susceptibles d'operacions matemàtiques, la "compressió" de la informació, deixa d'entendre's com a tal passant a ser, senzillament, la reducció d'un nombre (que pot ser extraordinàriament gran), una fórmula, o clau numèrica resultant d'operacions matemàtiques sobre l′"objecte-informació" a reduir (comprimir, en el llenguatge habitual).

L'exemple a què es recorre com a demostració sol ser del tipus següent: Si es tradueix una informació, un text, un llibre amb 100.000 paraules. Es converteix al seu equivalent numèric binari, però per entendre millor l'exemple es torna a convertir-lo al seu equivalent decimal. Ens queda aleshores, un nombre enorme, amb una determinada terminació, seqüència numèrica. Triem, d'aquestes originals 100.000 paraules (ara representades com a nombres decimals) les darreres 5.000 (l'elecció és convencional, i d'acord amb les necessitats prefixades). Prenem aquestes 5.000 paraules finals del text-número com a "patró". I les restem n vegades, fins a arribar a obtenir un nombre menor que el patró utilitzat. L'anomenarem, convencionalment, “resta”. Així, també ens queden dues claus. Els anomenarem, "claus de reconstrucció de la informació inicial". Simplement, caldrà agafar després aquesta resta i sumar n vegades el patró triat, fins que comprovem que aquest patró coincideix amb el final de la informació inicial o totalitat. I d'aquestes dues claus haurem reconstruït el total de la informació. Per descomptat, aquest és només un exemple model molt simplificat. Amb la base dels principis explicats aquí, i les eines matemàtiques i informàtiques disponibles es pot avançar més enllà dels límits aparents. Tingueu en compte que ni tan sols ens hem referit a recursos com la recursivitat, també aplicable a aquest mètode i perfectament tractable informàticament.

Referències

[modifica]
  1. ↑ Wade, Graham. Signal coding and processing (en anglès). 2a ed.. Cambridge University Press, 1994, p. 34. ISBN 978-0-521-42336-6. 
  2. ↑ «Teoria de Codis». grup de recerca CRISES. URV. [Consulta: 13 desembre 2021].
  3. ↑ 3,0 3,1 3,2 Talukdar, Asoke K. Mobile Computing (en anglès). 2a. Tata McGraw-Hill Education, 2010, p. 509. ISBN 0070144575. 
  4. ↑ «A Mathematical Theory of Communication». Bell System Technical Journal, vol. 27, 3–4, 1948, pàg. 379–423, 623–656. DOI: 10.1002/j.1538-7305.1948.tb01338.x.
  5. ↑ David Albert Huffman (September 1952), "A method for the construction of minimum-redundancy codes", Proceedings of the IRE 40 (9): 1098–1101, doi:10.1109/JRPROC.1952.273898, <http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf>
  6. ↑ Pratt, W.K.; Kane, J.; Andrews, H.C. «Hadamard transform image coding». Proceedings of the IEEE, vol. 57, 1969, pàg. 58–68. DOI: 10.1109/PROC.1969.6869.
  7. ↑ Ahmed, Nasir «How I Came Up With the Discrete Cosine Transform». Digital Signal Processing, vol. 1, 1, 1-1991, pàg. 4–5. DOI: 10.1016/1051-2004(91)90086-Z.
  8. ↑ «T.81 - COMPRESIÓN DIGITAL Y CODIFICACIÓN DE IMÁGENES FIJAS DE TONO CONTINUO - REQUISITOS Y DIRECTRICES». CCITT, 01-09-1992. [Consulta: 12 juliol 2019].
  9. ↑ «El formato de imagen JPEG explicado». BT.com, 31-05-2018. Arxivat de l'original el 5 de agosto de 2019. [Consulta: 5 agost 2019].
  10. ↑ BBC «Las protecciones de copia podrían llegar a los JPEG». BBC News. BBC, 15-10-2015.
  11. ↑ «¿Qué es un JPEG? El objeto invisible que ves todos los días». The Atlantic, 24-09-2013. [Consulta: 13 setembre 2019].
  12. ↑ «La controversia del GIF: A Software Developer's Perspective». [Consulta: 26 maig 2015].
  13. ↑ L. Peter Deutsch (Mayo 1996), DEFLATE Compressed Data Format Specification version 1.3, IETF, p. 1. sec. Abstract, RFC 1951, doi:10.17487/RFC1951, <https://datatracker.ietf.org/doc/html/rfc1951#section-Abstract>. Consulta: 23 abril 2014
  14. ↑ Hoffman, Roy. Data Compression in Digital Systems. Springer Science & Business Media, 2012, p. 124. ISBN 9781461560319. «Basically, wavelet coding is a variant on DCT-based transform coding that reduces or eliminates some of its limitations. (...) Another advantage is that rather than working with 8 × 8 blocks of pixels, as do JPEG and other block-based DCT techniques, wavelet coding can simultaneously compress the entire image.» 
  15. ↑ Taubman, David; Marcellin, Michael. Fundamentos, estándares y práctica de la compresión de imágenes JPEG2000: Fundamentos, normas y práctica de la compresión de imágenes. Springer Science & Business Media, 2012. ISBN 9781461507994. 
  16. ↑ Unser, M.; Blu, T. «Mathematical properties of the JPEG2000 wavelet filters». IEEE Transactions on Image Processing, vol. 12, 9, 2003, pàg. 1080–1090. Bibcode: 2003ITIP...12.1080U. DOI: 10.1109/TIP.2003.812329. PMID: 18237979.
  17. ↑ Sullivan, Gary. «Características generales y consideraciones de diseño para la codificación de vídeo de subbanda temporal». UIT-T. Video Coding Experts Group, 8-12 diciembre 2003. [Consulta: 13 setembre 2019].
  18. ↑ Bovik, Alan C. La guía esencial del procesamiento de vídeo. Academic Press, 2009, p. 355. ISBN 9780080922508. 
  19. ↑ Swartz, Charles S. Understanding Digital Cinema: A Professional Handbook. Taylor & Francis, 2005, p. 147. ISBN 9780240806174. 
  20. ↑ Mahdi, O.A. «Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique». International Journal of Computer Science Issues, vol. 9, 6, No. 3, 11-2012, pàg. 53–59. Arxivat 2018-12-28 a Wayback Machine.
  21. ↑ Cunningham, Stuart; McGregor, Iain «Evaluación subjetiva de la música comprimida con el códec ACER en comparación con AAC, MP3 y PCM sin comprimir» (en anglès). International Journal of Digital Multimedia Broadcasting, vol. 2019, 2019, pàg. 1-16. DOI: 10.1155/2019/8265301.
  22. ↑ The Olympus WS-120 digital speech recorder, according to its manual, can store about 178 hours of speech-quality audio in .WMA format in 500 MB of flash memory.
  23. ↑ Coalson, Josh. «FLAC Comparison». [Consulta: 23 agost 2020].
  24. ↑ «Format overview». [Consulta: 23 agost 2020].
  25. ↑ 25,0 25,1 Jaiswal, R.C.. Audio-Video Engineering. Pune, Maharashtra: Nirali Prakashan, 2009, p. 3.41. ISBN 9788190639675. 
  26. ↑ 26,0 26,1 26,2 Faxin Yu. Three-Dimensional Model Analysis and Processing. Berlin: Springer, 2010, p. 47. ISBN 9783642126512. 
  27. ↑ Compressió de dades a l'USPTO (anglès)
  28. ↑ Cummiskey, P.; Jayant, N. S.; Flanagan, J. L. «Cuantización adaptativa en la codificación PCM diferencial del habla». Bell System Technical Journal, 7, 1973. DOI: 10.1002/j.1538-7305.1973.tb02007.x.
  29. ↑ Cummiskey, P.; Jayant, Nikil S.; Flanagan, J. L. «Cuantización adaptativa en la codificación PCM diferencial del habla». The Bell System Technical Journal, vol. 52, 7, 1973, pàg. 1105-1118. DOI: 10.1002/j.1538-7305.1973.tb02007.x. ISSN: 0005-8580.
  30. ↑ 30,0 30,1 30,2 Schroeder, Manfred R. Acústica, información y comunicación: Volumen conmemorativo en honor de Manfred R. Schroeder. Springer, 2014. ISBN 9783319056609. 
  31. ↑ Gray, Robert M. «A History of Realtime Digital Speech on Packet Networks: Parte II de la Codificación Predictiva Lineal y el Protocolo de Internet». Found. Trends Signal Process., vol. 3, 4, 2010, pàg. 203-303. DOI: 10.1561/2000000036. ISSN: 1932-8346.
  32. ↑ 32,0 32,1 32,2 «Discrete Cosine Transform». IEEE Transactions on Computers, vol. C-23, 1, 1-1974, pàg. 90–93. DOI: 10.1109/T-C.1974.223784.
  33. ↑ Guckert, John. «math.utah.edu/~gustafso/s2012/2270/web-projects/Guckert-audio-compression-svd-mdct-MP3.pdf El uso de la FFT y la MDCT en la compresión de audio MP3». Universidad de Utah, Primavera 2012. [Consulta: 14 juliol 2019].
  34. ↑ Luo, Fa-Long. Normas de difusión multimedia móvil: Tecnología y práctica. Springer Science & Business Media, 2008, p. 590. ISBN 9780387782638. 
  35. ↑ Britanak, V. «Sobre propiedades, relaciones e implementación simplificada de bancos de filtros en los estándares de codificación de audio Dolby Digital (Plus) AC-3». IEEE Transactions on Audio, Speech, and Language Processing, vol. 19, 5, 2011, pàg. 1231-1241. DOI: 10.1109/TASL.2010.2087755.
  36. ↑ Brandenburg, Karlheinz. «Explicación de MP3 y AAC», 1999. Arxivat de l'original el 14 de febrero de 2017. [Consulta: 21 novembre 2022].
  37. ↑ Princen, J.; Johnson, A.; Bradley, A. ICASSP '87. IEEE International Conference on Acoustics, Speech, and Signal Processing. 12, 1987, p. 2161-2164. DOI 10.1109/ICASSP.1987.1169405. 
  38. ↑ Princen, J.; Bradley, A. «Diseño de banco de filtros de análisis/síntesis basado en la cancelación de aliasing en el dominio del tiempo». IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 34, 5, 1986, pàg. 1153-1161. DOI: 10.1109/TASSP.1986.1164954.
  39. ↑ «Summary of some of Solidyne's contributions to Broadcast Engineering». Brief History of Solidyne. Buenos Aires: Solidyne. Arxivat de l'original el 2013-03-08. [Consulta: 6 març 2013].Plantilla:Sps
  40. ↑ Esta fuente autopublicada no es lo suficientemente buena como para verificar esta significativa primicia. Octubre 2021,
  41. ↑ Zwicker, Eberhard. The Ear As A Communication Receiver. Melville, NY: Acoustical Society of America, 1967.  Arxivat 2000-09-14 a Wayback Machine.
  42. ↑ «File Compression Possibilities». A Brief guide to compress a file in 4 different ways, 17-02-2017.
  43. ↑ Dmitriy Vatolin (March 2007). Lossless Video Codecs Comparison '2007. Moscow State University. 
  44. ↑ Chen, Jie; Koc, Ut-Va; Liu, KJ Ray. Diseño de sistemas de codificación de vídeo digital: Un enfoque completo de dominio comprimido. CRC Press, 2001. ISBN 9780203904183. 
  45. ↑ Li, Jian Ping. Proceedings of the International Computer Conference 2006 on Wavelet Active Media Technology and Information Processing: Chongqing, China, 29-31 de agosto de 2006. World Scientific, 2006, p. 847. ISBN 9789812709998. 
  46. ↑ «Video Coding». CSIP website. Center for Signal and Information Processing, Georgia Institute of Technology. Arxivat de l'original el 23 May 2013. [Consulta: 6 març 2013].
  47. ↑ Lane, Tom. «JPEG Image Compression FAQ, Part 1». Internet FAQ Archives. Independent JPEG Group. [Consulta: 6 març 2013].
  48. ↑ «Resultados de un prototipo de esquema de compresión de ancho de banda de televisión». Proceedings of the IEEE. DOI: 10.1109/PROC.1967.5493.
  49. ↑ 49,0 49,1 Ghanbari, Mohammed. Standard Codecs: De la compresión de imágenes a la codificación de vídeo avanzada. Institución de Ingeniería y Tecnología, 2003, p. 1–2. ISBN 9780852967102. 
  50. ↑ Reader, Cliff (2016-08-31). "Patent landscape for royalty-free video coding". 9971: 99711B, San Diego, California: Society of Photo-Optical Instrumentation Engineers. DOI:10.1117/12.2239493 
  51. ↑ 51,0 51,1 51,2 51,3 «Infografía sobre la historia de los formatos de archivo de vídeo - RealPlayer», 22-04-2012. Arxivat de l'original el 2013-07-17. [Consulta: 12 abril 2024].
  52. ↑ «Declaración de patente registrada como H261-07». [Consulta: 11 juliol 2019].
  53. ↑ «Lista de patentes de MPEG-2». MPEG LA. [Consulta: 7 juliol 2019].
  54. ↑ «MPEG-4 Visual - Lista de patentes». MPEG LA. [Consulta: 6 juliol 2019].
  55. ↑ «AVC/H.264 - Lista de patentes». MPEG LA. [Consulta: 6 juliol 2019].
  56. ↑ Chanda P, Bader JS, Elhaik E «HapZipper: sharing HapMap populations just got easier». Nucleic Acids Research, vol. 40, 20, 27-07-2012, pàg. e159. DOI: 10.1093/nar/gks709. PMC: 3488212. PMID: 22844100.
  57. ↑ Christley S, Lu Y, Li C, Xie X «Human genomes as email attachments». Bioinformatics, vol. 25, 2, 15-01-2009, pàg. 274–5. DOI: 10.1093/bioinformatics/btn582. PMID: 18996942.
  58. ↑ Pavlichin DS, Weissman T, Yona G «The human genome contracts again». Bioinformatics, vol. 29, 17, 9-2013, pàg. 2199–202. DOI: 10.1093/bioinformatics/btt362. PMID: 23793748.
  59. ↑ Hosseini, Morteza; Pratas, Diogo; Pinho, Armando «A Survey on Data Compression Methods for Biological Sequences». Information, vol. 7, 4, 2016, pàg. 56. DOI: 10.3390/info7040056.

Vegeu també

[modifica]

Enllaços externs

[modifica]
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Compressió de dades
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Compressió_de_dades&oldid=34027927»