Alte standarde de compresie

Alte standarde de compresie
O tehnica folosita pentru compresia imaginilor este codarea run length. Intr-o versiune comuna a codarii run length, secventa elementelor imaginii de pe o linie, este impachetata intr-o secventa de perechi (c,l) unde c reprezinta o intensitate sau culoare si l lungimea de run(secventa de pixeli cu intensitati egale).
Presupunand ca valorile culorilor unui sir oarecare de pixeli consecutivi este de forma: 'abcbdddddddaaaaacbc', dupa codificarea RLE, sirul respectiv va deveni: 'abcbd7a5cbc'.
Aceasta metoda este eficienta pentru imagini ce contin mari suprafete de aceeasi culoare. Pentru imaginile precum harti meteo, codarea run length poate salva un numar semnificativ de biti peste secventa elementelor imaginii.
Alta tehnica de compresie a datelor, specifica imaginilor, este difference mapping, in care imaginea este reprezentata sub forma unui vector de diferente (de luminozitate sau culoare) intre pixeli adiacenti. Aceasta tehnica a fost folosita pentru a coda fotografiile facute planetei Uranus transmise de Voyager2.
Cei 8 biti per pixel necesari pentru a reprezenta 256 nivele de luminozitate, au fost redusi la o medie de 3 biti per pixel cand au fost transmise diferentele de valori. In aplicatiile spatiale, fidelitatea imaginii are un interes major, avand in vedere efectul cauzat de distanta spatiu-pamant in ceea ce priveste transmiterea datelor. Tehnica difference mapping a fost combinata cu coduri de corectare a erorilor pentru a obtine compresia si integritatea datelor.

Tehnicile de compresie cu pierderi obtin rate mult mai mari de compresie, cu dezavantajul pierderii de informatie grafica, deci a scaderii relative a calitatii imaginii obtinute. Algoritmii aplicati sunt mai complecsi, fiind compusi din diverse transformari, cum ar fi transformata cosinus discreta Prin DCT am prescurtat denumirea din limba engleza Discrete Cosine Transform care tradusa in romaneste ar putea insemna transformare cosinus discreta. Practic prin intermediul acestei transformari, un vector continand date despre intensitate este transpus intr-un vector care contine date despre "cat de repede variaza' intensitatea. Pentru imagini cu mai multe componente (ca de exemplu in cazul tripletului YCbCr) DCT este aplicata separat pentru blocuri de 8 x 8 pixeli pentru fiecare componenta. Pentru cazul in care se aplica subesantionarea, vor fi mai multe blocuri de date privind unele componente decat date privind alte componente. Pentru un patrat de 2 x 2 pixeli vom avea patru blocuri de Y pentru fiecare bloc de Cb sau Cr. Punctele imaginii in fiecare bloc sunt numerotate de la (0,0) la (7,7), cu f(x,y) am notat valoarea pixelului aflat in punctul de coordonate (x,y). DCT va produce un nou bloc de 8 x 8 continand date transformate prin folosirea formulei:

 

unde : C(z) = 1/1,41 daca z=0 si C(z) = 1 daca z este diferit de 0.

Rezultatul DCT este un set de frecvente F(u,v) care, in mare vorbind, indica in ce grad se schimba valorile de intrare la o anumita rata de esantionare. Prin F(0,0) se noteaza valoarea ce indica la ce grad, valorile nu se schimba deloc - este media celor 64 valori de intrare si este cunoscut ca fiind coeficientul DC. Restul valorilor reprezinta asa numitii coeficienti AC. De exemplu F(1,0) indica gradul de variatie (la frecventa joasa) pe directia orizontala si arata ca nu exista variatie pe directia verticala. Facand interpretarea in acelasi mod, F(7,7) indica gradul in care valorile se schimba cel mai repede in ambele directii (frecventa inalta).

DCT este in principiu reversibila, in acest scop folosindu-se formula:

Erorile de rotunjire nu produc diferentieri foarte mari ale valorilor calculate fata de valorile originale. Pentru blocurile de 8 x 8 pixeli, termenii rezultati ca urmare a aplicarii DCT vor avea nevoie de patru biti in plus fata de valorile originale. Astfel, daca valoarea pixelilor, adica f(x,y), are nevoie de 8 biti atunci dupa transformarea cosinus discreta vom avea nevoie de 12 biti pentru F(u,v). Deci, prin aplicarea DCT nu se face o comprimare.

Aceasta discutie despre tehnici ale compresiilor de date reprezinta o mostra limitata a unui foarte bogat obiect de cercetare. Aceste metode si altele de natura asemanatoare, sunt interesante si de mare valoare in domeniile din care fac parte. Trebuie notat ca mare parte din eficienta castigata cu ajutorul tehnicilor semantice dependente, poate fi obtinuta prin metode mult mai generale, de exemplu compresia Huffman sau Lempel-Ziv.

Erori

Canalele care nu sunt afectate de noise, sunt din pacate, un model nu foarte realistic al unui sistem de comunicare. Sistemele actuale de transmisii de date suporta doua tipuri de erori:

■ erori de faza, in care un simbol cod este pierdut sau castigat;

■ erori de amplitudine, in care un simbol cod este corupt.

Gradul in care erorile de canale degradeaza transmisia este un parametru important in alegerea metodei de compresie a datelor. Susceptibilitatea la eroare a unui algoritm de codare depinde foarte mult daca metoda este statica sau dinamica.

Codurile statice

Se stie despre codarea Huffman ca tinde sa se corecteze pe sine, adica o eroare de transmisie tinde a nu se propaga prea departe. Cuvantul cheie in care are loc eroarea este incorect primit si este de asteptat ca putine cuvinte cheie sa fie interpretate gresit, dar, inainte de a fi prea tarziu, receiverul se sincronizeaza din nou cu senderul.

Intr-un cod static, sincronizarea inseamna ca ambii senderul si receiverul, identifica inceputurile cuvintelor cheie in acelasi fel. Concluziile care pot fi trase sunt: atat timp cat pentru codurile Huffman este obisnuit sa se sincronizeze, acest fapt nu este garantat; si cand sincronizarea este asigurata, nu exista nici o limita in propagarea erorii.

O dificultate in plus este aceea ca sincronizarea nu ofera nici o indicatie daca s-a produs vreo eroare.

Codurile adaptive

Codurile adaptive sunt mult mai nefavorabil afectate de erorile de transmisie decat codurile statice. De exemplu, in cazul codului Huffman adaptiv, desi receiverul se poate resincroniza cu senderul (adica sa localizeze corect inceputul cuvantului cheie), informatia pierduta reprezinta mai mult decat cativa biti sau cateva caractere ale ansamblului sursa. Faptul ca senderul si receiverul redefinesc dinamic codul, indica faptul ca in timp ce sincronizarea este refacuta, ei pot avea reprezentari radical diferite ale codului. Sincronizarea definita la metodele statice, se refera la sincronizarea fluxului de biti, care nu este suficienta pentru metodele adaptive. Ceea ce este necesar este sincronizarea codului, adica, sincronizarea fluxului de biti si a structurilor de date dinamice care reprezinta impachetarea curenta a codului.

Nu exista nici o dovada ca metodele adaptive se pot sincroniza. Ziv si Limpel recunosc ca dezavantajul major al algoritmului lor este susceptibilitatea la propagarea erorilor, iar Welch sugereaza ca intregul ansamblu sa fie introdus intr-un cod detector de erori. Nici metodele aritmetice statice si nici cele adaptive de codare nu au abilitatea de a tolera erorile.

Compresia datelor este un subiect de mare importanta in multe aplicatii. Metodele de compresie a datelor au fost studiate de aproape cinci decenii. Prezenta lucrare a oferit o privire asupra metodelor de utilitate generala. Algoritmii au fost evaluati in termeni care privesc volumul de compresie produs, eficienta algoritmilor si susceptibilitatea la eroare. In timp ce eficienta algoritmilor si erorile produse sunt relativ independente de caracteristicile ansamblului sursa, calitatea compresiei obtinute depinde de caracteristicile sursei.