cap3 tehnici de compresie -...

Teletransmisii de date Cap. 3 Tehnici de compresie a datelor

11

3 TEHNICI DE COMPRESIE A DATELOR

3.1 Introducere Cele mai multe surse de informaţie conţin informaţie redundantă sau aduce prea puţină informaţie pentru spaţiul ocupat. Un astfel de exemplu este cel al unui dreptunghi memorat ca o imagine de tip bitmap:

000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000 000000000011111111111111111111111111000000000 000000000010000000000000000000000001000000000 000000000010000000000000000000000001000000000 000000000010000000000000000000000001000000000 000000000010000000000000000000000001000000000 000000000010000000000000000000000001000000000 000000000011111111111111111111111111000000000 000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

Aceeaşi secvenţă poate fi memorată prin coordonatele colţului stânga sus 11,4 şi lungimea şi lăţimea 26, 7 în format metafile, sau prin compresarea secvenţelor lungi cu aceeaşi valoare:

0,45 ; 45 biţi de „0” 0,45 ; 45 biţi de „0” 0,45 ; 45 biţi de „0” 0,10 1,26 0,9 ; 10 biţi de „0”, 26 de „1” şi 9 de „0” 0,10 1,1 0,24 1,1 0,9 ; 10 biţi de „0”, 1 de “1”, 24 de “0”, 1 de “1”, 9 de “0” 0,10 1,1 0,24 1,1 0,9 ; 10 biţi de „0”, 1 de “1”, 24 de “0”, 1 de “1”, 9 de “0” 0,10 1,1 0,24 1,1 0,9 ; 10 biţi de „0”, 1 de “1”, 24 de “0”, 1 de “1”, 9 de “0” 0,10 1,1 0,24 1,1 0,9 ; 10 biţi de „0”, 1 de “1”, 24 de “0”, 1 de “1”, 9 de “0” 0,10 1,1 0,24 1,1 0,9 ; 10 biţi de „0”, 1 de “1”, 24 de “0”, 1 de “1”, 9 de “0” 0,10 1,26 0,9 ; 10 biţi de „0”, 26 de „1” şi 9 de „0” 0,45 ; 45 biţi de „0” 0,45 ; 45 biţi de „0”

Compresia datelor devine un subiect important în transmiterea şi stocarea informaţiei din ce în ce mai voluminoasă. Cele mai multe sisteme de transmisie au o rată de transmisie sau de stocare limitată. De exemplu un CD-ROM poate stoca circa 30 de secunde de semnal video necompresat


12

(648 MB de date). În concluzie compresia datelor implică şi analiza informaţiei pentru a determina datele redundante.

3.2. Metode de compresie Atunci când se doreşte compresia datelor trebuie ţinut cont de tipul datelor şi de cum sunt interpretate ele. De exemplu pixel-ii dintr-o imagine pot fi distorsionaţi dar să conţină încă informaţia utilă. Uneori un singur bit greşit poate crea probleme deosebite. Semnalele video şi audio sunt de regulă compresate cu pierdere de informaţie, în timp ce datele digitale sunt compresate fără pierdere. Aceste două variante pot fi detaliate astfel:

• compresie fără pierdere – informaţia obţinută după decompresare este identică cu cea inţială. Pentru programe sau fişiere, orice pierdere va duce la un fişier corupt.

• compresia cu pierderi – informaţia compresată nu se poate extrage în întregime la decompresie. Acest gen de compresie necesită analiza datelor mai întâi şi aflarea datelor care au cel mai redus efect asupra datelor (diferenţa între o imagine cu 24 biţi de culoare este mică faţă de o imagine cu 10 biţi). Compresia unei imagini înseamnă şi reducerea rezoluţiei.

3.3. Probabilitatea de apariţie a caracterelor Oricare ar fi limba în care este exprimat un text există un grad mare de redundanţă şi diferitele caractere au probabilităţi de apariţie diferite. Astfel vocalele au probabilitate de apariţie mai mare decât consoanele. De exemplu pentru paragraful 3.2. frecvenţele de apariţie a caracterelor sunt: Tabelul 3.1 a ă â b c d e f g h i î j k l m n o p q r s ş t ţ u v x y w z 65 19 2 7 37 38 126 15 12 0 86 7 0 0 26 29 44 43 30 0 65 31 8 51 14 36 3 3 0 0 2

Frecvenţa cea mai mare o are litera "e", urmată de "i" şi "a", iar "h", "j", "k", "q", "w" şi "y" nu au nici o apariţie. În tabelul 3.2 literele sunt ordonate în ordinea scăzătoare a frecvenţei de apariţie, iar pe linia a treia sunt probabilităţile de apariţie la 1000 de caractere. Tabelul 3.2 e i a r t n o d c u s p m l ă f ţ g ş b î v x â z h j k q w y

126 86 65 65 51 44 43 38 37 36 31 30 29 26 19 15 14 12 8 7 7 3 3 2 2 0 0 0 0 0 0 156 107 81 81 63 55 53 47 46 45 38 37 36 32 24 19 17 15 10 9 9 4 4 2 2 0 0 0 0 0 0

3.4. Metode de codare Separat faţă de compresia cu pierdere sau fără pierdere, codarea datelor este clasificată în mod normal în două tipuri principale: codarea entropică şi codarea sursei.

• codarea entropică nu ţine cont de caracteristicile datelor şi le tratează în acelaşi fel. Tipic se foloseşte codarea statistică (se codează cu


13

număr mai mare sau mai mic de biţi fiecare caracter funcţie de probabilitatea sa de apariţie) sau suprimarea secvenţelor lungi (secvenţele lungi de 1 sau 0 se înlocuiesc cu secvenţe speciale – carcaterul plus numărul de repetări).

• codarea sursei ia în calcul caracteristicile informaţiei. De exemplu imaginile conţin multe secvenţe care se repetă, sau pentru video schimbările de la un cadru la altul sunt reduse. În scopul reducerii cantităţii de informaţie secvenţele ce se repetă se codează cu secvenţe speciale, iar pentru video se memorează doar schimbările faţă de cadrul anterior.

3.4.1. Codarea statistică Codarea statistică este o tehnică entropică care identifică mai întâi anumite secvenţe în şirul de date. Secvenţele mai frecvente se codează cu un număr mai mic de biţi, iar secvenţele mai rare cu un număr mai mare de biţi. De exemplu codul Morse este un mod de codare statistică. El foloseşte puncte (zero) şi linii (unu) pentru a coda caractere. Tabelul 3.3 ilustreaza codul Morse în comparaţie cu un cod simplu. Se observă că semnele cele mai frecvente sunt codate cu un singur bit, iar cele mai puţin probabile sunt codate cu mai mulţi biţi. Tabelul 3.3

Caracterul Cod

simplu Cod Morse a 00000 01 b 00001 1000 c 00010 1010 d 00011 100 e 00100 0 f 00101 0010 g 00110 110 h 00111 0000 i 01000 00 j 01001 0111 k 01010 101 l 01011 0100 m 01100 11 n 01101 10 o 01110 111 p 01111 0110 q 10000 1101 r 10001 010 s 10010 000 t 10011 1 u 10100 001


14

v 10101 0001 w 10110 011 x 10111 1001 y 11000 1011 z 11001 1100

SP 11010 0011

3.4.2. Eliminarea secvenţelor repetitive Suprimarea secvenţelor lungi repetitive înseamnă înlocuirea lor cu cu un caracter special urmată de numărul de repetiţii. De exemplu în fişiere de tip text apar frecvent „spaţii” sau zerouri. Exemplele următoare ilustrează compresia unor secvenţe lungi de 0 şi „spaţii”.

8.320000000000000 → 8.32F13 Teletransmisii_ _ _ _ _de_ _ _date_ _ _ _ _ _ → Teletransmisii F5 de F3 date F6

„F” este un fanion care poate fi o succesiune de caractere (ZZ) sau un caracter de 8 biţi (FFh). Într-un fişier binar orice secvenţă de biţi poate apărea. Dacă există deja caracterul alocat fanionului atunci fanionul va avea două caractere, dacă sunt două atunci fanionul va avea trei ş.a.m.d.

Această metodă este foarte bună pentru compresia imaginilor şi fişierelor de tip text.

3.4.3. Codarea diferenţială Codarea diferenţială este o metodă de codare a sursei şi se utilizează când diferenţa dintre două valori consecutive este redusă. Această metodă se pretează pentru codarea semnalelor video şi în special a celor audio. Codarea diferenţială se foloseşte la Modularea Impulsurilor în Cod (PCM):

• Modulaţia Delta – foloseşte un singur bit pentru a reprezenta un semnal analogic. Se transmite „1” logic dacă eşantionul curent este mai mare decât precedentul şi respectiv „0” logic dacă este mai mic. Rata de eşantionare trebuie să fie mai mare decât rata Nyquist datorită ratei mici de creştere a valorii semnalului de urmărire. Rata de bit rezultă totuşi redusă.

• Modulaţia Delta Adaptivă – permite urmărirea schimbărilor rapide ale semnalului prin modificarea treptei de variaţie. Un algoritm tipic porneşte cu o treaptă redusă pe care o măreşte până ajunge la nivelul dorit. Numărul de trepte depinde de numărul de biţi de codare.

• Modulaţia PCM diferenţială – transmite doar diferenţa dintre două eşantioane consecutive pentru eliminarea redundanţei.

3.4.3. Codarea prin transformată Această codare foloseşte o transformată matematică pentru a reduce cantitatea de date de transmis sau de memorat. Cea mai răspândită transformată este transformata Fourier. Astfel coeficienţii de valoare mai


15

mare sunt codaţi cu rezoluţie superioară, iar cei de valoare redusă cu mai puţini biţi sau sunt eliminaţi. Acest gen de codare este recomandată pentru semnale audio şi imagini.

3.5. Compresia datelor - metoda Huffman/Lempel-Ziv În mod normal compresia datelor nu ţine cont de tipul datelor şi trebuie să fie fără pierderi. În aceste condiţii compresia se poate aplica fişierelor de date, documente, imagini, etc. Codarea Huffman foloseşte un cod cu lungime variabilă. Acest lucru impune analizarea informaţiei pentru a determina probabilitatea de apariţie a elementelor în pachetul de date ce va fi transmis. Cu cât probabilitatea de apariţie a unui caracter este mai mare cu atât codul corespunzător va avea lungimea mai mică. Mai întâi pachetul de date este scanat pentru a determina numărul de apariţii a caracterelor, apoi acestea sunt aranjate în ordinea descrescătoare a probabilităţii. Apoi caracterelor cele mai puţin probabile le sunt alocate „1” şi „0”. De exemplu pentru un text s-au găsit următoarele probabilităţi: ‘b’ ‘c’ ‘e’ ‘i’ ‘o’ ‘p’ 12 3 57 51 33 20 pe care le ordonăm în ordine crescătoare: ‘e’ ‘i’ ‘o’ ‘p’ ‘b’ ‘c’ 57 51 33 20 12 3 şi alocăm pentru caracterul „c” pe 0 şi pentru „b” pe 1. Se sumează numărul de apariţii ale celor două şi se trec în coloana următoare împreună cu restul de caractere (figura 3.1), dar în ordinea numărului de apariţii.

Se alocă la ultimele două 0 şi respectiv 1 în ordinea descrescătoare a numărului de apariţii. Se copie coloana, iar pentru ultimele două se adună numărul de apariţii şi se poziţionează în coloană funcţie de numărul obţinut.

‘e’ 57

‘i’ 51

‘o’ 33

‘p’ 20 [1]

15 [0]

‘e’ 57

‘i’ 51

‘o’ 33

‘p’ 20

‘b’ 12 [1]

‘c’ 3 [0]

‘e’ 57

‘i’ 51

‘o’ 33

‘p’ 20 [1]

15 [0]

‘e’ 57

‘i’ 57

35 [1]

‘o’ 33 [0]

68

‘e’ 57 [1]

‘i’ 51 [0]

108 [1]

68 [0]

Fig. 3.1. Codarea Huffman


16

Procedeul se repetă până rămân doar două linii pentru care se alocă 0 pentru ultima şi 1 pentru penultima. Codul Huffman este apoi citit de la dreapta la stânga, iar biţii se aranjează de la dreapta la stânga. Pentru exemplul de mai sus codul final va fi: 'e' 11 ; 'i' 10 ; 'o' 00 ; 'p' 011 ; 'b' 0101 ; 'c' 0100; Codul Huffman are avantajul că se pot determina caracterele indiferent de ordinea în care se trimit, chiar dacă lungimea lor este diferită. Odată cu datele trebuie trimis şi tabelul de codare (tabel generat dinamic) sau nu dacă tabelul este generat după valori statistice şi este cunoscut atât de emiţător cât şi de receptor. Codul asigură o bună compresie dar nu ţine cont de asocierile dintre caractere (grupuri de caractere care se repetă). De acest neajuns ţine cont codarea Huffman adaptivă. Un alt avantaj al codării Huffman adaptive este acela că necesită doar o singură trecere peste date şi oferă în general performanţe mai bune decât codarea Huffman statică, dar poate fi şi mai slabă uneori. Ideea de bază este folosirea pentru codarea simbolului ti+1 din mesaj, a unui arbore de codare (un dicţionar de codare sub forma unui arbore binar) construit pe baza primelor i simboluri din mesaj. După transmiterea simbolului ti+1 se va revizui arborele de codare în vederea codării simbolului ti+2. Există mai multe variante ale algoritmului Huffman dinamic (FGK, ∆) care diferă între ele prin modul de construcţie al arborelui. În continuare vom prezenta algoritmul de compresie, ilustrându-l cu exemplul din figura 3.2. Procedura generală de compresie pentru codarea Huffman adaptivă are următorul algoritm:

• Se iniţializează arborele de codare cu un nod rădăcină; • Se transmite primul simbol în clar (de exemplu codul ASCII al

simbolului); • Se construiesc încă două noduri (frunze) care pornesc din nodul

rădăcină, unul la stânga, care nu conţine nici un simbol, căruia îi ataşăm ponderea nulă (frunză goală) şi unul la dreapta care conţine simbolul apărut, ponderea acestuia devenind egală cu 1;

• Se citeşte următoarea literă din mesaj; • Dacă este deja în arbore se transmite codul lui din arbore. Codul său

din arbore se formează citind simbolurile de '0' respectiv '1' ataşate ramurilor, pornind de la nodul rădăcină până la nodul în care se află caracterul. Simbolurile de '0' respectiv '1' se ataşează ramurilor astfel: toate ramurile din dreapta vor avea ataşate simbolul '1', iar toate ramurile din stânga vor avea ataşate simbolul '0'. Apoi se trece direct la ultimul pas;

• Dacă nu este în arbore atunci transmit codul nodului terminal care nu conţine nici un simbol (frunză goală) urmat de codul în clar(ASCII) al


17

literei. Codul nodului fără nici o literă se formează ca şi în cazul nodului care conţine o literă;

Arbore iniţial

0 1

1

Arbore după „a”

3

11 2 0 0 1

3

0 20 1

a 2 a 1

Arbore după al doilea „a”

3

1 2 0 1

4 a 3

Arbore după „_”

0 10 1

3 5

1 2

Nr de ordine al nodului Nod frunză

corespunzător unui caracter din mesaj

Pondere nod: numarul de apariţii

ale caracterului pentru noduri

frunză sau suma ponderilor pentru noduri derivate

4

2 2 0 1

6 a 5

Arbore după „b”

1 1 0 1

7

3 4

0 1 0 1

1 2 b

4

2 30 1

6 a 5

Arbore după al doilea „b”

1 20 1

7

3 4

0 10 1

1 2

b

6

3 30 1

6 b 5

Arbore după al treilea „b”

1 2

0 1

7

3 4

0 10 1

1 2

a

Interschimbare noduri

Arbore după al doilea „_”

7

3 4 0 1

6 b 5

2 2

0 1

7

3 4

0 20 1

1 2

a

Arbore după al doilea „c”

8

3 50 1

6 b 5

2 3

0 1

7

3 4

1 20 1

1 2

a

0 10 1

1 2 c

Fig. 3.2. Algoritmul de codare Huffman adaptivă (aa_bbb_c)


18

• reactualizez arborele; dacă mesajul s-a terminat, atunci codarea este terminată, iar în caz contrar reluăm procedeul începând cu pasul al 4-lea.

Observaţie: Diferitele variante de codare dinamică diferă doar prin modul de reactualizare al arborelui (tabelei de decodare).

Procedura generală de decompresie pentru codarea Huffman adaptivă are următorul algoritm:

• se iniţializează arborele de codare cu un nod rădăcină; • se citeşte primul simbol transmis în clar (codul ASCII al

simbolului); • se transmite litera la ieşire; • se construiesc încă două noduri care pornesc din nodul rădăcină,

unul la stânga, care nu conţine nici un simbol, căruia îi ataşăm ponderea nulă şi unul la dreapta care conţine simbolul apărut, ponderea acestuia devenind egală cu 1;

• se citeşte codul transmis (bit cu bit) până când codul se află în arbore, adică până când am ajuns la un nod frunză; nod frunză = nod care se află în arbore pe ultimul nivel de ierarhie;

• dacă nodul ataşat codului citit este un nod care nu conţine nici un simbol se citeşte litera transmisă în clar, apoi se trece direct la pasul 8;

• dacă nodul ataşat codului citit conţine un simbol atunci decodez codul ataşat lui prin litera pe care o conţine;

• se reactualizează arborele; dacă mesajul s-a terminat, atunci decodarea este terminată, în caz contrar se reia procedeul de la pasul 5.

Pentru varianta dinamică există doi algoritmi performanţi: FGK (Faller, Gallager, Knuth) şi V (Vitter). Aceştia au în comun faptul că arborele se construieşte dinamic pe măsură ce o sursă de informaţie generează simboluri, deci este necesară o singură parcurgere a şirului simbolurilor şi nu este necesară stocarea lor.

Metoda de compresie Lempel-Ziv a fost implementată pentru prima dată de către Abraham Lempel şi Jacob Ziv în anul 1977, de unde şi denumirea LZ77. Ulterior au mai apărut şi alte variante (LZ78, LZW, LZSS).

Metoda de compresie LZ ţine cont de repetiţia unor silabe, cuvinte în mesaj. Se foloseşte un fanion pentru a semnala partea codată. Un exemplu ar fi trimiterea mesajului „Acest receptor necesită o confirmare a recepţiei care este trimisă automat atunci când este recepţionat mesajul”. În mesaj există secvenţa „recep” care se repetă de trei ori. Codarea se face cu fanioane şi două numere care reprezintă distanţa până la poziţia primei apariţii a secvenţei şi lungimea secvenţei (#m#n). Astfel mesajul codat arată astfel: „Acest receptor necesită o confirmare a #33#5ţiei care este trimisă


19

automat atunci când este #86#5ţionat mesajul”. Dacă secvenţa este scurtă, atunci acest gen de codare poate duce la dimensiuni mai mari ale mesajului.

Algoritmul LZ77 este foarte simplu. La început avem un şir T care conţine n simboluri iniţializate cu primul simbol din alfabetul sursei de informaţie. Se păstrează primele LS simboluri generate de sursa de informaţie pe ultimele poziţii ale şirului şi se transmit către receptor. La pasul următor avem un şir w de lungime 0. Atâta timp cât şirul w se regăseşte în şirul T, acesta este concatenat cu următorul simbol generat de sursa de informaţie. Notăm cu wi şirul format din primele i simboluri ale lui w. Fie i lungimea lui w când acesta nu se mai regăseşte în şirul T. Aceasta înseamnă că şirul wi-1 este cel mai lung şir generat de de sursa de informaţie care se află în T începând cu poziţia p. Către receptor se trimite p , numărul i-1 şi simbolul de pe ultima poziţie a şirului w. Şirul T se deplasează la stânga cu i poziţii, iar ultimele i poziţii se completează cu simbolurile şirului w. Acest pas se repetă până sursa nu mai generează simboluri. Figura următoare ilustrează modul în care se realizează compresia unui şir de simboluri.

Algoritmul de decompresie constă în interpretarea şirului de simboluri. Se citesc LS simboluri care se stochează pe ultimele poziţii ale şirului T de lungime n. Apoi se recepţionează la fiecare pas câte un triplet (p, i, c), se extrag i simboluri din T începând cu poziţia p, apoi se extrage simbolul c. Se deplasează T la stânga cu i+1 poziţii şi se completează şirul cu cele i+1 simboluri recepţionate.

Algoritmul de compresie LZSS aduce următoarea îmbunătăţire: dacă avem de codificat un singur simbol se transmite bitul 0 urmat de simbol, iar dacă avem de transmis un şir mai lung se transmite bitul 1 urmat de perechea (p, i).

Şirul T este denumit fereastră mobilă, iar dicţionarul este constituit

Alfabetul {a,b,c,d} S=”abbaabbaababbaacdaabaaba

T=”aaaaaaa”; n’8; LS=4 Pasul T w Ieşire (p, i, c)

0 aaaaabba abba abba 1 aaaaabba abbaa (4,4,”a”) 2 bbaabbaa bab (1,2,”b”) 3 abbaabab baac (2,3,”c”) 4 ababbaac d (0,0, „d”) 5 babbaacd aab (4,2,”b”) 6 baacdaab aaba (5,3,”a”)

Figura 3.3. Algoritmul LZ77


20

chiar de fereastra mobilă. Din acest motiv, algoritmul LZ77 nu este optim. Un an mai târziu Lempel şi Ziv au renunţat la fereastra mobilă, iar dicţionarul este constituit de şirurile de simboluri recepţionate anterior. Acest cod se numeşte LZ78. Iniţial lista de elemente T are lungime 1 şi conţine şirul nul pe poziţia 0. La fiecare pas se consideră lista simbolurilor de la pasul anterior şi se citeşte cel mai scurt şir w care nu este în lista elementelor din T. În listă se adaugă şirul w şi se transmite o pereche formată din numărul de ordine al primei apariţii a şirului format din w fără ultimul caracter şi caracterul eliminat. Figura următoare prezintă un exemplu de compresie LZ78.

Şi algoritmul LZ78 are o deficienţă pe care a observat-o Welch în 1984. El a ajuns la concluzia că nu este necesar să transmiţi o pereche formată dintr-un indice şi un simbol, ci doar un singur cod. Algoritmul compresiei LZW este următorul:

- lista T se iniţializează cu simbolurile alfabetului - la fiecare pas şirul w este iniţializat cu ultimul simbol al şirului w

anterior, iar în listă se adaugă cel mai scurt şir w ce urmează dar care nu există în lista T.

- se transmite un singur cod care reprezintă numărul de ordine al apariţiei w din care se extrage ultimul simbol.

Algoritmii LZ78 şi LZW sunt utilizaţi în programele comerciale cu amendamentul că lista T trebuie limitată la cantităţi mici de şiruri. LZW se

Alfabetul {a,b,c,d} S=”abbaabbaababbaacdaabaaba

T=” ” Pasul w indice

element din T

Ieşire (i, c)

1 a 1 (0,”a”) 2 b 2 (0,”b”) 3 ba 3 (2,”c”) 4 ab 4 (1, „b”) 5 baa 5 (3,”a”) 6 bab 6 (3,”b”) 7 baac 7 (5,”c”) 8 d 8 (0,”d”) 9 aa 9 (1,”a”)

10 baab 10 (5,”b”) 11 a 11 (0,”a”)

Figura 3.4. Algoritmul LZ78


21

foloseşte la compresia GIF, şi uneori TIFF şi în Adobe Acrobat.

3.6. Compresia datelor cu pierdere de informaţii Compresia de date cu pierdere de informaţie se aplică în special

pentru date multimedia cum ar fi sunete, imagini şi secvenţe video.

3.6.1 Prelucrarea sunetelor Există multe persoane care şi-au pus întrebarea "Cum sunt stocate

sunetele în cadrul unui fişier?". În continuare vă vom prezenta transformările prin care trece un sunet de la generarea lui de către un dispozitiv sau o persoană până în momentul scrierii lui într-un fişier.

Sunetele generate de dispozitive sau persoane sunt captate de dispozitive de captare a sunetelor, cum ar fi microfonul. Principiul de funcţionare al acestuia este similar modului de funcţionare a urechii umane, prin urmare, sunetele care ajung la microfon interacţionează cu membrana acestuia care le transformă în semnale electrice (amplitudine funcţie de timp). În continuare, semnalele electrice generate de microfon sunt transformate în şiruri de numere cu convertoare analog numerice (ADC Analog Digital Convertor) care primeşte la intrare o tensiune electrică şi generează la ieşire un cod binar. Pentru reprezentarea unui semnal în formă digitală, acesta trebuie eşantionat. Prin eşantionare, dintr-un semnal se extrag cadre la intervale de timp echidistante în timp ∆T. Se obţin astfel valori ale semnalului la momente le eşantionării. Datorită faptului că reprezentarea numerică este un şir finit de biţi, apare eroarea de cuantizare. Calitatea sunetului digital care se doreşte a fi obţinută depinde de numărul de biţi folosiţi pentru a reprezenta un cadru şi de intervalul de timp dintre cadre. Calitatea sunetului creşte cu numărul de biţi şi cu scăderea intervalului de timp dintre două cadre.

De exemplu, pentru sistemul telefonic, cadrele sunt reprezentate folosindu-se 7 sau 8 biţi, intervalul dintre cadre este 1/8000 secunde (8000 cadre/sec) şi se pierd toate sunetele cu frecvenţe mai mari de 4 kHz. Un alt exemplu îl constituie CD-urile audio. Pe un CD-audio sunetele sunt înregistrate folosindu-se 16 biţi pentru a reprezenta un cadru şi intervalul dintre cadre este 1/44.100 (44.100 cadre/sec).

3.6.2. Compresia digitală a sunetelor Datorită faptului că pentru a transmite la distanţă sunete cu o calitate

foarte bună (de calitatea CD-urilor audio) sunt necesari 1,411 Mbps pentru semnale audio stereo şi 705,6 Kbps pentru semnale audio mono. Aceste numere sunt foarte mari şi s-a pus problema compresiei sunetelor.

Cei mai importanţi algoritmi utilizaţi în procesul de compresie a sunetelor sunt codificarea formei de undă şi codificarea perceptivă. Prin


22

codificarea formei de undă, semnalul este transformat cu ajutorul transformatei Fourier în componentele sale în frecvenţă (reprezentarea amplitudinilor în funcţie de timp). După aplicarea transformatei, amplitudinea fiecărei componente este codificată minimal, folosind cât mai puţini biţi. Transformata Fourier duce la pierdere de informaţie.

Şirul de biţi obţinuţi se comprimă folosind unul dintre algoritmii prezentaţi în episoadele anterioare ale compresiilor de date. Scopul este de a reproduce exact forma de undă, la celălalt capăt folosind cât mai puţini biţi.

Codificarea perceptivă constă în a transforma sunetul digital, astfel încât un ascultător uman să nu poată face diferenţa între un sunet transformat şi unul netransformat. La baza acestui tip de codificare stă psihoacustica. Psihoacustica este ştiinţa care se ocupă de modul în care sunetele sunt percepute de către om. Proprietatea de bază a codificării perceptive este constituită de faptul că unele sunete pot masca alte sunete, astfel încât acestea din urmă nu se vor mai auzi atâta timp cât primele continuă să fie prezente. Pe baza acestei proprietăţi, sunetele care nu vor putea fi auzite de ascultătorii umani vor fi eliminate.

În realitate, dacă generăm un sunet cu frecvenţa de 1 KHz la un volum de 60 dB şi un alt sunet cu frecvenţa de 1.1 KHz şi un volum de 40 dB, nu vom auzi cel de-al doilea sunet. Acest fenomen poartă numele de mascarea frecvenţei. Sunetele care se aud poartă numele de sunete mască. Un alt fenomen care are loc în realitate este acela că, dacă un sunet maschează un alt sunet, urechea umană este adaptată să audă numai sunetele mască. În cazul în care sunetele mască de la un moment dat dispar, celelalte sunete nu vor putea fi auzite decât după un interval de timp, care reprezintă timpul în care urechea umană se reglează pentru a le putea percepe. Acest fenomen poartă numele de mascare temporară.

Prin urmare, o aplicaţie de compresie a sunetelor care se bazează pe psihoacustică va elimina pe baza unor relaţii sunetele care nu vor putea fi auzite de către om. După eliminarea sunetelor care nu pot fi percepute, asupra rezultatului se aplică unul dintre algoritmii de compresie fără pierdere de informaţie. Se observă în acest caz că pierderea de informaţie este dată de eliminarea sunetelor care nu pot fi auzite de către om. Raportul calitate sunet/dimensiune fişier de ieşire este mai mare dacă se aplică aceste reguli decât în cazul în care se încearcă compresia sunetelor fără a elimina sunetele care nu se aud.

Compresia vocală Practica a arătat că sunt necesari 12 biţi pentru a coda semnalul vocal.

Dacă convertorul AD este liniar, atunci treptele de cuantizare sunt egale, şi zgomotele de cuantizare vor afecta puternic semnalele de amplitudine


23

redusă care se apropie ca amplitudine de rezoluţia convertorului. Astfel ideea este de a utiliza nivele diferite de cuantizare funcţie de valoarea eşantionului. Aceasta se poate realiza cu o conversie AD neliniară după o lege neliniară. Cele mai utilizate, implementate şi în procesoarele numerice de semnal (DSP) sunt legile A (Europa), şi µ (SUA) (A-law şi µ-law). Legile acestea sunt similare şi comprimă 12 biţi la 8 biţi. Curba de compresie se poate vedea în figura 3.5. Vorbirea normală foloseşte µ=255 deoarece această caracteristică se suprapune peste caracteristica urechii umane. Legea A se suprapune peste o caracteristică logaritmică:

⎪⎪⎩

⎪⎪⎨

⎧

≤≤+

+

≤≤+=

11,log1

)log(1

10,log1

xAA

AxA

xA

Ax

y (3.1)

unde A este un întreg pozitiv. În urma compresării un semnal sinusoidal cu amplitudine de 1V sau de 0.1V arată ca în figura 3.4. Se poate lesne observa că comprimarea amplifică semnalele de amplitudine mică mai mult decît pe cele de amplitudine mare. Astfel sunetele slabe vor fi accentuate în comparaţie cu cele puternice. Forma de undă rezultă distorsionată. Pentru calitate audio ridicată (Hi-Fi) banda semnalului este limitată la 20 KHz. Frecvenţa de eşantionare este de 44.1 KHz. Dacă fiecare eşantion este reprezentat pe 16 biţi atunci rata de bit (numărul de biţi pe secundă pentru transmisie serială) este:

Rata de transmisie digitală = 44.1⋅16kbps = 705.6kbps Pentru varianta stereo rata este dublă 1.4112 bps. În plus se mai adaugă biţi suplimentari pentru corecţie de erori şi pentru sicronizarea cadrelor.

Intrare Intrare

Ieşire Ieşire

A=100

A=1 µ=1

µ=50

µ=255

0 1 0.5

1

0 1 0.5

0.5 0.5

1

Figura 3.5. Caracteristicile legilor A şi µ


24

Există mai multe standarde de transmisie funcţie de aplicaţie: - pentru transmisie audio digitală se utilizează o rată de eşantionare de 32 KHz (bandă audio de 15KHz); - înregistrare profesională cu frecvenţă de eşantionare de 48 KHz şi rezoluţie de 16 sau 20 de biţi. - înregistrare pe compact disc cu frecvenţă de eşantionare de 44.1 KHz (CD/EIAJ/RDAT) cu 14 sau 16 biţi rezoluţie. Sistemul CD audio este un exemplu de folosire a tehnicilor digitale în sistemele audio. Figura 3.7 prezintă modul de înregistrare a informaţiei pe CD. Datele sunt înregistrate serial, bit cu bit, şi sunt stocate pe o spirală continuă de la exterior către interior. Valoarea bitului se stabileşte funcţie de starea zonei corespunzătoare (reflectă sau nu reflectă). Zonele ce memorează un biţii au o lungime de 1.6 µm şi sunt separate de zone de 0.5 µm inactive.

Sinus 1VVV compresat Sinus 1VVV necompresat

Sinus 0.1VVV compresat Sinus 0.1VVV necompresat

Figura 3.6. Semnale compresate după legea A

Reflectă sau nu reflectă înseamnă 1 sau 0

0.5 µm

1.6 µm

120 mm Figura 3.6. Înregistrarea pe CD


25

Rezoluţia de 16 biţi permite 655536 de nivele, adică o gamă dinamică de 96.32 dB şi un raport semnal zgomot de 98.08 dB. Deoarece suprafaţa este sensibilă la zgârieturi şi amprente (adică erorile vor apărea în şarje), organizarea datelor se face întreţesut pe 4 coloane şi 5 rânduri. Un bloc de 20 de eşantioane va fi aranjat logic astfel:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

care vor fi stocate pe disc astfel: 1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 1, 8, 22, 3, 7, 11, 15, 19, 23, 4, 8, 12, 16, 20, 24.

Figura următoare prezintă modul de codare a datelor pe disc. Iniţial cuvântul de 16 biţi este împărţit în doi octeţi, care sunt ”modulaţi” în cadrul unui proces numit „modulare 8 la 14 biţi” (EFM). Un cuvânt de 8 biţi devine unul de 14 biţi printr-un tabel (look-up table), în scopul reducerii sensibilităţii la toleranţele optice. După aceasta se mai adaugă 3 biţi de subcod. Aceştia conţin informaţia de sincronizare. Codul de 17 biţi este stocat pe disc: două eşantioane ale canalului stâng şi apoi două ale canalului drept. La sfârşitul fiecărui bloc se adaugă un cod corector de erori.

Modularea EFM asigură evitarea secvenţelor mai lungi de 11 de zero. Deoarece CD ROM-ul putea iniţial să extragă datele cu doar 1.5Mbiţi/secundă, iar rata pentru semnalul audio stereo era de 2x16x44.1KHz=1.411200Mbps, iar pentru a reda şi video şi audio era necesară o rată mai mare, s-a ajuns la nevoia de a compresa informaţia audio şi video. S-au dezvoltat mai multe standarde dintre care cele mai cunoscute

Eşantion canal stâng

8 biţi 8 biţi

Biţi subcod

14 biţi 3 biţi

LU LL RU RL LU LL P Q

Cod pentru corecţia erorilor

Biţi subcod

14 biţi 3 biţi

Fig. 3.7. Codarea datelor pe CD


26

sunt MPEG şi Dolby AC3. Ambele formate folosesc modelul psiho-acustic, model care exploatează caracteristicile urechii umane. Astfel urechea umană nu poate percepe componente sub un anumit nivel, componente care pot fi eliminate fără a afecta calitatea audio. Efectul utilizat este cel de mascare. Un sunet puternic va masca un sunet mai slab apropiat ca frecvenţă pentru creierul uman. În aceste condiţii nu are rost ca acel sunet să mai ocupe memorie.

Codarea MPEG audio rupe semnalul în segmente (cadre) egale ce conţin un anumit număr de eşantioane. Aceste cadre sunt apoi filtrate cu filtre digitale pe sub-benzi. În mod normal sunt 32 de benzi. Eşantioanele din sub-benzi sunt apoi scalate cu un factor de scală pentru a reduce gama dinamică a fiecărei sub-benzi. Rezultă astfel un număr de coeficienţi pentru fiecare sub-bandă, pentru fiecare perioadă. În acelaşi timp se calculează şi pragul de mascare pentru fiecare sub-bandă pe baza unui model psiho-perceptual. Există 3 nivele de codare MPEG audio:

• MPEG audio I – foloseşte modelul psiho-acustic pentru a masca şi reduce numărul eşantioanelor. Are o calitate ce e foarte apropiată de a standardului CD-audio. Principalul avantaj este că permite construcţia simplă a codoarelor şi decodoarelor cu performanţe medii cu rate de lucru de până la 192 sau 256 kbps.

• MPEG audio II – este similar cu primul, doar că este optimizat pentru rate de 96 – 128 kbps pe canal.

• MPEG audio III – ajunge la 64 kbps pe canal, dar calitatea este foarte apropiată de a CD audio, superioară MPEG II la aceeaşi rată. Cele trei nivele MPEG sunt compatibile în sensul că nivelul III le poate decoda pe celelalte două. Nivelul II este cel mai folosit, iar nivelul I este cel mai simplu în timp ce nivelul III asigură cea mai mare compresie dar cere şi cele mai multe calcule. În cele ce urmează vor fi prezentate în detaliu cele 3 nivele de odare MPEG.

A

f

A

f

Spectrul audio

Spectrul audio

perceput

Nivel de mascare

Fig. 3.8 Efectul de mascare


27

Nivelul MPEG I A fost utilizat pentru prima dată de către Philips pentru înregistrarea digitală pe casete (Digital Compact Cassette – DCC). Asigură rate de 128 kbps pe canal. Şirul audio este prelucrat în domeniul frecvenţă, după ce a fost supus unei transformate Fourier rapide. Informaţia este împărţită în 32 de subbenzi prin filtrare digitală. Frecvenţa de eşantionare de 44.1 kHz duce la o subbandă de 689.0625 Hz. Astfel se poate prelucra fiecare bandă folosind modele acustice uşor modificate pentru o codare mai bună. Fiecare subbandă este apoi procesată utilizând modelul psihoacustic. Se folosesc două modele 1 şi 2, primul fiind utilizat de nivelele I şi II, iar modelul 2 este folosit de nivelul III. Modelul 1 procesează cîte 512 eşantioane odată. Pentru codare, se folosesc cîte 32 de eşantioane din fiecare subbandă. Rezultă astfel cadre de 384 de eşantioane care sunt centrate în mijlocul cadrului de 512.

Nivelul MPEG II Acesta asigură aceeaşi rată de 128 kbps, tot modelul 1 şi o compresie uşor mai bună ca nivelul I. Numărul de eşantioane creşte de la 384 la 1152, iar fereastra la 1024. Aceasta nu este suficient de mare ca să le includă pe toate, astfel încât sunt necesare două analize. Prima analiză preia primele 576 de eşantioane şi le centrează într-o fereastră de 1024, iar a două repetă procesul cu celelalte 576. Se obţine astfel un raport semnal zgomot superior deoarece se selectează eşantioanele care maschează cel mai bine zgomotul.

Nivelul MPEG III Nivelul acesta asigură o rată de 64 kbps şi o compresie uşor superioară nivelului anterior. Procesul de codare este acelaşi ca la nivelul II. Creşterea compresiei se obţine cu utilizarea modelului 2 cu câteva importante diferenţe.

Formatul MPEG-1 Specificaţia MPEG-1 permite două canale stereo la rate de eşantionare de: 32kHz (comunicaţii), 44.1 kHz (CD audio) sau 48 kHz (audio profesional). Tabelul următor prezintă câteva dintre caracteristicile acestui format: Tabelul 3.4. 32 kHz 44.1 kHz 48 kHz Bandă audio 15 kHz 20.6 kHz 22.5 kHz Durata cadrului – nivelul I (384 eşantioane) 12 ms 8.7 ms 8 ms Durata cadrului – nivelul II (1152 eşantioane) 36 ms 26.25 ms 24 ms Durata cadrului – nivelul III (1152 eşantioane) 36 ms 26.25 ms 24 ms Subbenzi 32 32 32 Eşantionare subbenzi (FS/32) 1 kHz 1.378 kHz 1.5 kHz


28

Bandă subbenzi (FS/64) 500 Hz 689.06 Hz 750 Hz Rata de bit (Nivelul 2 stereo) 192 kbps 256 kbps 256 kbps Rata de bit (Nivelul 2 , 5 canale) 256 kbps 384 kbps 384 kbps

MPEG-1 exploatează irelevanţa stereofonică. Metoda se numeşte codare stereo după intensitate. Din informaţia audio stereo se elimină redundanţa prin reţinerea doar a anvelopei energetice a canalului drept şi a celui stâng doar la frecvenţe înalte. După codare un cadru tipic include un header, un cod de corecţie a erorilor, date audio şi date auxiliare.

Formatul MPEG-2 Acesta este o extensie a primului şi este complet compatibil. El aduce următoarele îmbunătăţiri:

• Trei noi frecvenţe de eşantionare (16, 22.05 şi 24 kHz) • până la 4 canale, permiţând sunet surround • suportă efecte pentru frecvenţe joase • suport separat pentru materialul audio: transmisie multilingvă, dialog

separat, sau comentarii. MPEG-2 furnizează sunet stereo cu 256kbps. Compatibilitatea cu MPEG-1 este asigurată prin ascunderea datelor suplimentare cu un câmp auxiliar de date, ignorat de decodorul MPEG-1. Tabelul următor prezintă principalii parametri ai formatului MPEG-2. Tabelul 3.5. 16 kHz

22.05kHz 24 kHz

32 kHz 44.1 kHz 48 kHz

Bandă audio 7.5 kHz 10.3 kHz 15 kHz 15 kHz 20.6 kHz 22.5 kHz Durata cadrului – nivelul I (384 eşantioane)

24 ms 17.4 ms 12 ms 12 ms 8.7 ms 8 ms

Durata cadrului – nivelul II (1152 eşantioane)

72 ms 52.5 ms 36 ms 36 ms 26.25 ms 24 ms

Durata cadrului – nivelul III (1152 eşantioane)

72 ms 52.5 ms 36 ms 36 ms 26.25 ms 24 ms

Subbenzi 32 32 32 32 32 32 Eşantionare subbenzi (FS/32)

500 Hz 689.0625 Hz

750 kHz 1 kHz 1.378 kHz

1.5 kHz

Bandă subbenzi (FS/64)

250 Hz 344.5313 Hz

375 Hz 500 Hz 689.06 Hz

750 Hz

Rata de bit (Nivelul 2 stereo)

96 kbps 128 kbps 128 kbps 192 kbps 256 kbps 256 kbps

Rata de bit (Nivelul 2 , 5 canale)

128 kbps 192 kbps 192 kbps 256 kbps 384 kbps 384 kbps


29

3.6.3. Compresia digitală a imaginilor Comunicaţiile implică tot mai mult transmisia de imagini (telefonia mobilă 3G, Ipagini Web, telefonia prin Internet). Imaginile sunt fie statice, fie în mişcare. Compresia acestora într-un format standard poate minimiza spaţiul ocupat şi viteza de transmitere. Tabelul 3.6.

Tip Compresie Rezoluţie maximă sau

culori

Detalii

TIFF Huffman RLE sau LZW

culori pe 48 biţi TIFF=Tagged Image File Format – se foloseşte pentru transferul fişierelor grafice de pe un PC pe altul. Permite rezoluţii ridicate şi culori până la 48 biţi (câte 16 biţi pentru fiecare culoare)

PCX RLE 65536x65536, culori pe 24 biţi

Format grafic ce foloseşte compresia RLE (Run Lebgth Encoding) care suprimă secvenţele lungi cu acelaşi caracter. Nu memorează tabele pentru corecţia culorilor.

GIF LZW 65536x65536, culori pe 24 biţi, dar 256 afişabile

GIF= Graphic Interchange Format - format grafic standardizat ce poate fi citit aproape de orice program grafic. Similar cu PCX, dar permite imagini multiple într-un singur fişier şi grafică întreţesută.

JPG JPEG (DCT, cuantizare şi Huffman)

depinde de compresie

JPEG=Joint Photographic Expert Group. Asigură o compresie excelentă cu pierdere.

Principalii parametri ai unei imagini sunt: • Rezoluţia imaginii. Aceasta este definită de numărul de pixeli pe

orizontală şi pe verticală. • Numărul de culori pe pixel. Dacă se folosesc N biţi, atunci numărul

total de culori afişabil e 2N. De exemplu pentru 8 biţi se pot afişa 256 culori, iar 24 biţi asigură 224=16.7 milioane de culori. Calculatoarele moderne permit 32 de biţi, adică peste 4 milioane de culori.

• Dimensiunea paletei. Unele sisteme reduc numărul de biţi pentru culoare reducând numărul de culori pentru o paletă dată.

Formatul GIF Formatul GIF a fost patentat de firma CompuServe Incorporated. Popularitatea sa a crescut doarte mult datorită folosirii largi pe Internet. CompuServe a permis utilizarea liberă, dar cu specificarea proprietăţii. Cele mai folosite versiuni sunt 87a şi 89a. Un fişier GIF are structura următoare:

• un header cu numele GIF


30

• un bloc de descriere logică care defineşte dimensiunea, aspectul prin raportul H/V, şi adâncimea culorilor

• tabelul de culori • blocuri de date cu magini bitmap şi cu posibilitatea întreţeserii

textelor • imagini multiple, cu secvenţiere sau întreţesere. Acest proces se

defineşte într-un bloc de redare (rendering). • imagini bitmap compresate LZW.

Tabelele de culori memorează culorile unei imagini din GIF (local) sau ale întregului fişier (global). Blocurile pot fi clasificate în 3 grupuri: blocuri de control, blocuri de interpretare grafică şi blocuri cu destinaţie specială. Blocurile de control conţin informaţie despre controlul datelor sau informaţii despre setările unor parametri hardware. Ele includ: • Header GIF –versiunea de GIF şi semnătura; • Descriptor logic al ecranului – dimensiunea ecranului activ (înălţime şi

lungime) şi aspectul • Tabelul global de culori – conţine pînă la 256 culori dintr-o paletă de

16.7 M • Blocuri de date – conţin datele imaginii compresate • Descrierea imaginii – conţine tabel de culori local, dimensiunile imaginii

şi coordonatele colţului stânga sus • Tabelul local de culori – este un bloc opţional ce conţine informaţii de

culoare locale unei imagini, similar celui global • Date tabelate ale imaginii– date compresate ale imaginii • Extensie de control grafic – un bloc opţional cu infomaţie extra pentru

redare (timing şi transparenţă) • Comentarii – informaţie de tip comentariu ce este ignorată de decodor • Extensie de tip text – bloc opţional cu text • Extensie de aplicaţie – conţine date specifice aplicaţiei. Se poate folosi

pentru a adăuga extra informaţie în fişier. • Trailer – defineşte sfârşitul unui bloc de date Header-ul foloseşte 6 octeţi (semnătura GIF) şi versiunea: 3 octeţi cu literele „G”, „I”, „F”, şi 3 octeţi pentru versiune: 2 octeţi pentru an urmată de litera „a” sau „b”. Descriptorul logic al ecranului este localizat imediat după header şi are următorul format: - 2 octeţi cu lăţimea ecranului - 2 octeţi cu înălţimea ecranului


31

- 1 octet pentru împachetarea câmpului cu 1 bit pentru fanionul tabelului de culori global şi 3 biţi pentru rezoluţia culorii, 1 bit pentru fanionul de sortare (setat înseamnă că tabelul este sortat în ordine descrescătoare a importanţei) şi 3 biţi pentru numărul de culori din tabelul global de culori (nr. de culori=2nr. de culori+1) - 1 octet pentru indexul hârtiei - 1 octet aspectul pixelului (dacă este 0 atunci nu este dată o valoare, iar dacă este diferit de 0 atunci acesta se calculează cu:

6415pixelului aspectulaspectul +

=

unde aspectul pixelului este raportul dintre lăţimea şi înălţimea acestuia. Tabelul global de culori conţine până la 256 de culori. Fiecare culoare este definită ca o culoare de 24 de biţi (8 biţi pentru roşu, 8 biţi pentu verde şi 8 biţi pentru albastru). Numărul de octeţi pe care îl conţine tabelul este 3x2dimensiunea tabelului+1. Tabelul conţine culoare cu culoare, cei 3 octeţi (R, G, B). Corespondenţa culorilor este prezentată în tabelul 3.7. Tabelul 3.7.

Culoarea Codul Culoarea Codul Alb FFFFFFh Roşu închis C91F16h

Roşu deschis DC640Dh Portocaliu F1A60Ah Galben FCE503h Verde deschis BED20Fh

Verde închis 088343h Albastru deschis 009DBEh Albastu închis 0D3981h Purpuriu 3A0B59h

Roz F3D7E3h Aproape negru 434343h Gro închis 777777h gri A7A7A7h Gri deschis D4D4D4h Negru 000000h

Descriptorul imaginii conţine: - 1 octet pentru separatorul de imagini (2Ch) - 2 octeţi pentru poziţionarea pe orizontală a imaginii - 2 octeţi pentru poziţionarea pe verticală a imaginii - 2 octeţi pentru lăţimea imaginii - 2 octeţi pentru înălţimea imaginii - 1 octet pentru împachetarea câmpului: 1 bit pentru tabelul de culori local, 1 bit pentru fanionul de întreţesere, 1 bit pentru fanionul de sortare, 2 biţi rezervaţi şi 3 biţi pentru dimensiunea tabelului de culori local. Tabelul de culori local este similar cu tabelul de culori global şi este un bloc opţional care defineşte culorile imaginii pe care o precede. Datele tabelate ale imaginii conţin date compresate în subblocuri de câte maxim 255 de octeţi. Datele sunt indexuri către tabelul global sau local de culori pentru fiecare pixel de imagine. Formatul tabelului este următorul:


32

- 1 octet pentru codul LZW minim, care este numărul iniţial de biţi folosiţi în codarea LZW. - N octeţi cu date compresate LZW. Primul bloc este precedat de lungimea sa. Extensia pentru controlul grafic este opţională şi conţine informaţie despre redarea imaginii următoare. Formatul său este: - 1 octet pentru identificatorul de extensie (21h) - 1 octet cu eticheta de control grafic (F9h) - 1 octet cu dimensiunea blocului - 1 octet în care: 3 biţi sunt rezervaţi, 3 biţi definesc metoda de dispunere, 1 bit pentru fanionul de intrare a utilizatorului, şi 1 bit pentru fanionul de transparenţă a culorii. - 2 octeţi pentru întârzierea la decodare (în sutimi de secundă) - 1 octet cu indexul de transparenţă a culorii - 1 octet pentru terminatorul de bloc (00h) Extensia pentru comentarii este opţională şi onţine informaţie ce va fi ignorată de către decodor: - 1 octet pentru identificatorul blocului (21h) - 1 octet pentru eticheta de comentariu (FEh) - N octeţi cu comentarii -1 octet pentru terminator (00h) Extensia pentru text este de asemenea opţională: - 1 octet pentru identificator (21h) - 1 octet pentru eticheta de text (01h) - 1 octet cu dimensiunea blocului (are valoarea 12) - 2 octeţi cu alinierea la stânga a textului - 2 octeţi cu alinierea textului în partea de sus - 2 octeţi cu lăţimea textului - 2 octeţi cu înălţimea textului - 1 octet cu lăţimea caracterului - 1 octet cu înălţimea caracterului - 1 octet cu culoarea textului Extensia pentru aplicaţie este opţională şi conţine informaţii pentru programele aplicaţie: - 1 octet pentru identificator (21h) - 1 octet pentru eticheta de aplicaţie (FFh) - 1 octet pentru dimensiunea blocului (are valoare 11) - 8 octeţi pentru identificatorul aplicaţiei - 3 octeţi pentru autentificarea codului aplicaţie - N octeţi pentru datele aplicaţie - 1 octet pentru terminatorul de bloc (00h)


33

Trailerul are valoarea 3Bh şi indică sfârşitul fişierului GIF.

Formatul JPEG JPEG utilizează o tehnică de compresie cu pierdere excelentă (deşi într-un mod este fără pierdere). Acest standard este pe lângă GIF unul din cele maifolosite compresoare de imagini. A fost enunţat de către Joint Photographic Expert Group, un subcomitet al ISO/IEC: tehnică de compresie pentru imagini alb nergu sau color ce foloseşte o combinaţie de transformată cosinus, cuantizare, codare RLE şi codare Huffman. Prima parte a algoritmului de codare separă culorile (roşu, verde şi albastru) în termeni de luminanţă (strălucire) şi crominanţă. Standardul JPEG permite pierderi mai mari în crominanţă decât în luminozitate deoarece ochiul uman este mai sensibil la luminozitate decât la schimbarea de culoare. În plus culoarea verde are un efect mai puternic asupra strălucirii decât albastrul. Imaginea este memorată sub formă de pixeli, dar spre display este trimisă sub format RGB. Conversia RGB în luminanţă şi culori se face cu relaţiile:

Y=0.299R+0.587G+0.114B Cb=0.1687R–0.3313G+0.5B (1) Cr=0.5R–0.4187G+0.0813B

Y este strălucirea (în care verdele are cea mai mare pondere), în Cr roşu are ponderea cea mai mare, iar în Cb albastrul are ponderea cea mai mare şi verdele cea mai mică. Componentele Y, Cr şi Cb sunt cunoscute sub numele de complexul YUV. Acestea sunt apoi subeşantionate, câte un eşantion din Cr şi Cb la 4 eşantioane ale lui Y. Header-ul JPEG conţine toate informaţiile pentru decodare. Transformata cosinus discretă converteşte intensitatea în frecvenţă (cât de rapidă este variaţia de intensitate). Este similară cu transformata Fourier dar lucrează doar cu numere reale. Imaginea este segmentată în dreptunghiuri de 8x8 pixeli. Dacă imaginea conţine câteva componente (R, G, B sau Y, Cb, Cr), atunci fiecare componentă este prelucrată separat. Dacă imaginea este subeşantionată vor fi mai multe blocuri dintr-o componentă decât din celelalte. Datele din blocurile de 8x8 încep cu dreapta sus (0,0)şi se termină cu punctul din stânga jos (7,7). Transformata cosinus produce un nou bloc 8x8 pe baza relaţiei:

⎥⎦

⎤⎢⎣

⎡ ++= ∑∑

= =

7

0

7

0 16)12(cos

16)12(cos),()()(

41),(

x y

vyuxyxfvCuCvuF ππ (2)


34

unde 0z dacă 2

1)( ==zC

sau 0z dacă 1)( ≠=zC Fiecare valoare este pe 12 biţi (gamă dinamică 0 ...1024). Rezultatul este o matrice în spaţiul frecvenţă F(u,v) care conţine informaţie despre rata de schimbare în punctul respectiv:

• F(0,0) dă valoarea medie a matricii 8x8 • F(1,0) dă gradul de schimbare cel mai lent (frecvenţe joase) • F(7,7) dă gradul de schimbare cel mai rapid (frecvenţe înalte)

Cele mai semnificative valori sunt situate în colţul din stânga sus al matricii. Restul termenilor sunt apropiaţi de 0, iar la trunchiere devin 0. Astfel de secvenţe lungi de 0 pot fi comprimate cu RLE sau cu codarea Huffman. Următorul pas este cuantizarea . Fiecare valoare dată de DCT este împărţită cu un factor de cuantizare şi apoi este rotunjit la cel mai apropiat întreg. Cuantizare se face folosind o matrice 8x8 cu factori de cuantizare, care fie este stocată în fişier, fie este una standard. Atunci când imaginea este descompusă în componente multiple (de ex. Y, Cb, Cr) atunci fiecare componentă poate avea matricea ei de cuantizare. În general componentele de frecvenţă joasă au factori mici de cuantizare, iar componentele de frecvenţă mare au factori mari de cuantizare. După cuantizare componentele diferite de 0 rămân doar cele din colţul din stânga sus. Exemplul din figura următoare ilustrează acest lucru.

Pentru a obţine o compresie, prima valoare (valoarea medie sau DC) este memorată ca diferenţa faţă de blocul anterior, deoarece acestea tind să rămână constante. Restul componentelor sunt stocate în zig-zag începând

144 139 149 155 153 155 155 155 151 151 151 159 156 156 156 158 151 156 160 162 159 151 151 151 158 163 161 160 160 160 160 161 158 160 161 162 160 155 155 156 161 161 161 161 160 157 157 157 162 162 161 160 161 157 157 157 162 162 161 160 163 157 158 154

5 3 4 4 4 3 5 4 4 4 5 5 5 6 7 12 8 7 7 7 7 15 11 11 9 12 13 15 18 18 17 15

20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

1257.9 2.3 -9.7 -4.1 3.9 0.6 -2.1 0.7 -21.0 -15.3 -4.3 -2.7 2.3 3.5 2.1 -3.1 -11.2 -7.6 -0.9 4.1 2.0 3.4 1.4 0.9 -4.9 -5.8 1.8 1.1 1.6 2.7 2.8 -0.7 0.1 -3.8 0.5 1.3 -1.4 0.7 1.0 0.9 0.9 -1.6 0.9 -0.3 -1.8 -0.3 1.4 0.8 -4.4 2.7 -4.4 -1.5 -0.1 1.1 0.4 1.9 -6.4 3.8 -5.0 -2.6 1.6 0.6 0.1 1.5

251 0 -2 -1 0 0 0 0 -5 -3 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Fig. 3.9. DCT şi cuantizarea unei matrici 8x8


35

din colţul din stânga sus. Astfel componentele de joasă frecvenţă vor fi primele şi apoi cele de frecvenţă înaltă care sunt zero. Acestea vor fi eliminate la compresia finală.

Ultima operaţie este compresia finală. Aceasta foloseşte fie codarea Huffman modificată sau codarea aritmetică. Valorile stocate sunt diferenţele faţă de valoarea anterioară. O valoare pozitivă este stocată ca echivalentul său binar, iar o valoare negativă cu toţi biţii inversaţi (complement faţă de 1): 5 → 010; -5 → 010; 10 → 1010; -10 → 0101; 1 → 1; -1 → 0; 23 → 10111; -23 → 01000. Diferenţa este precedată de o valoare pe 4 biţi care defineşte numărul de biţi ai diferenţei. Valoarea 0 este memorată doar pe 4 biţi (0000).

Componentele, aşa-zisele armonici, sunt stocate sub formă de cod Huffman de 8 biţi.

Data: 12, 10, 11, 11, 11 Diferenţa: 12, -2, 1, 0 ,0

0100 1010 0010 0001 0000 0000 01 1

1

Valoarea are 4 biţi

Valoarea are 2 biţi

Valoarea are 1 bit

Valoarea are 0 bit

Valoarea are 0 bit

12 -2

Fig. 3.10. Stocarea sub formă de cod cu lungime variabilă.

cap3 tehnici de compresie -...

Documents