Standarde de compresie

Standarde de compresie

In foarte multe cazuri practice, reprezentarile diferitelor imagini ajung la dimensiuni foarte mari. Din aceasta cauza s-a conturat necesitatea stocarii datelor in formate comprimate.

Compresia reprezinta procesul de folosire a unor functii recursive pentru a crea fisiere de dimensiuni mai mici prin eliminarea redundantei(a repetitiilor).

Metodele de compresie utilizate pot fi impartite in doua categorii: cu, si fara pierdere de informatie. In cazul tehnicilor de compresie fara pierdere de informatie, imaginea poate fi reconstituita in intregime din cea initiala.

Un domeniu in care compresia de date este de foarte mare importanta , este reprezentarea de imagini. Exista doua motive majore pentru aceasta afirmatie. Primul motiv este dat de faptul ca imaginile digitale au un continut foarte mare de redundanta locala. O imagine este de obicei realizata sub forma unui vector de pixeli, pe cata vreme metodele care exploateaza tendinta pixelilor ale caror culori si intensitate stau impreuna, pot fi mai eficiente. Al doilea motiv pentru care s-au realizat foarte multe cercetari in acest domeniu, este volumul. Imaginile digitale, in mod normal, necesita un numar foarte mare de biti, si multe dintre utilizarile imaginilor digitale, implica colectii mari de imagini.

In aceasta sectiune un cod este definit ca fiind o impachetare a unui alfabet sursa, intr-un alfabet cod. Procesul de transformare a sursei in mesaj codat se numeste codare . Algoritmul care construieste impachetarea si o foloseste pentru a transforma sursa se numeste encoder. Decoderul realizeaza operatia inversa, prin aducerea mesajului codat la forma sa initiala.

In intregul capitol se va folosi ca exemplu urmatorul ansamblu:

EXAMPLE aa bbb cccc ddddd eeeeee fffffffgggggggg

Deci codul reprezinta impachetarea mesajelor sursa (cuvinte din alfabetul sursa alpha) in cuvinte cheie (cuvinte ale alfabetului cod beta). Mesajele sursa sunt unitati de baza in care este impartit sirul de caractere care trebuie reprezentat.

Pentru exemplul nostru EXAMPLE, alpha = . Din motive lesne de inteles vom lua beta =.

In completarea categoriilor de standarde de compresie ale datelor privind mesajul si lungimea codurilor, aceste metode sunt clasificate in:

■ metode statice sau

■ metode dinamice.

O metoda statica este aceea in care impachetarea de la setul de mesaje, la setul de cuvinte cheie, este fixata inainte de a incepe transmisia, astfel incat , un mesaj dat este reprezentat de acelasi cod la fiecare aparitie a sa din mesajul initial. Schema statica clasica este reprezentata de compresia Huffman.

In compresia Huffman asignarea cuvintelor codate la mesajul sursa este bazata pe probabilitatea cu care apare mesajul sursa in intreg setul de mesaje. Mesajele care apar mai frecvent sunt reprezentate de coduri scurte; mesajele cu probabilitati mai mici de aparitie sunt impachetate in coduri mai lungi. Aceste probabilitati sunt determinate inainte de a incepe transmisia.

Mesaj sursa probabilitate cod

a 2/40 1001
b 3/40 1000
c 4/40 011
d 5/40 010
e 6/40 111
f 7/40 110
g 8/40 00
space 5/40 101

Codul Huffman pentru mesajul EXAMPLE (lungimea codului=117).
EXAMPLE = aa bbb cccc ddddd eeeeee fffffffgggggggg.
alpha

Un cod este dinamic daca impachetarea de la setul de mesaje la setul de coduri se schimba dupa un anumit timp.
De exemplu codarea Huffman dinamica implica o aproximare a probabilitatilor de aparitie a mesajului, in timp ce ansamblul de date este transmis. Asignarea de coduri mesajelor, se bazeaza pe valorile frecventelor relative de aparitie la fiecare moment de timp. Un mesaj x poate fi reprezentat de o secventa de cod scurta la un moment dat al transmisiei, daca apare frecvent la inceputul ansamblului, desi probabilitatea sa de aparitie in intregul ansamblu este scazuta. Mai tarziu, cand devine mai probabil ca alte mesaje sa apara cu o frecventa mai mare, secventa scurta de cod va fi folosita pentru impachetarea unuia dintre aceste mesaje care au probabilitatea mai mare de aparitie, si mesajul x va fi impachetat de o secventa mai lunga de cod.
Tabelul de mai jos prezinta codarea dinamica Huffman corespunzatoare prefixului aa bbb din exemplu. Desi frecventa elementului space din intregul mesaj este mai mare decat cea a lui b, la acest moment din timp b are frecventa mai mare si deci este impachetat cu codul mai scurt.
Mesaj sursa probabilitate cod
a 2/6 10
b 3/6 0
space 1/6 11

Codurile dinamice se regasesc in literatura si sub denumirea de coduri adaptive , pentru ca se adapteaza la schimbarile caracteristicilor ansamblului in timp.
Toate metodele adaptive sunt metode one-pass pentru ca este nevoie doar de o singura scanare a ansamblului. Codarea statica Huffman necesita doi pasi: un pas sa calculeze probabilitatile si sa determine impachetarea, si al doilea pas pentru transmisie. Cu toate acestea, atat timp cat timpul de codare, respectiv decodare al unei metode adaptive nu este substantial mare fata de al unei metode statice, faptul ca o scanare initiala nu este necesara, cauzeaza o imbunatatire a vitezei in cazul adaptiv. In plus, impachetarea determinata in primul pas al unei codari statice trebuie transmisa de encoder la decoder. Impachetarea poate prefata fiecare transmisie (fiecare fisier trimis) sau o singura impachetare poate fi stabilita si folosita pentru transmisii multiple.
In metodele one-pass encoderul defineste si redefineste impachetarea dinamica, in timpul transmisiei.
Un algoritm poate fi deasemenea hibrid, nici in totalitate static, nici dinamic.

Intr-o schema simpla hibrid, senderul si receiverul mentin carti de coduri identice, care contin k coduri statice. Pentru fiecare transmisie, senderul trebuie sa aleaga unul dintre cele k coduri, si sa informeze receiverul in legatura cu alegerea sa (prin trimiterea "numelui" sau a numarului codului ales).

In compresia de date scopul este de a reduce redundanta, lasand doar continutul informational. Masura informatiei unui mesaj sursa x (in biti) este -log p(x) (unde log reprezinta logaritmul in baza 2).
Cea mai comuna notiune pentru a defini un cod "bun", este aceea de optim, adica sa aiba redundanta minima. Redundanta poate fi definita astfel:
sum p(a(i)) l(i) - sum [-p(a(i)) log p(a(i))] ,
unde:
l(i) - este lungimea codului care reprezinta mesajul a(i).
sum, p(a(i)), l(i) - reprezinta media lungimii codurilor.
sum [-p(a(i)) log p(a(i))] - reprezinta media continutului de informatie.