Procesarea Audio

Cap.7. Compresarea Informaiei Transmisia informaiei i depozitarea ei cost bani. Cu ct mai mult informaie ai de aface, cu att mai mult cost. n ciuda acestui fapt, cele mai multe informaii digitale nu sunt coninute n forma cea mai compact. Mai degrab, ele sunt coninute n orice mod ce o face uor de folosit, ca de exemplu: textul ASCII de la procesoarele de texte, codul binar care poate s fie executat pe un calculator, mostre independente de la un sistem de achiziie de date etc. Caracteristic, aceste metode de codificare uor-de-folosit necesit fiiere de mrime dubl pentru reprezentarea informaiei .Comprimarea datelor este termenul general pentru diveri algoritmi i programe elaborate pentru soluionarea acestei probleme. Un program de comprimare se ntrebuineaz n transformarea informaiei ntr-un format optimizat cu caracter compact. Analogic, un program de decomprimare se foloseste pentru ntoarcerea informaiei la formatul ei original. n acest capitol vom examina cinci tehnici pentru comprimarea datelor. Primele trei metode de codificare se numesc: (runlength), Huffman, i delta codificare. Ultimile dou au elaborat proceduri care au fost stabilite ca standarde de industrie: LZW i JPEG.

Strategiile Compresrii Informaiei.

Tabelul 7-1 arat dou moduri diferite dup care algoritmii de comprimare a datelor pot fi clasificai. n (a) metodele au fost clasificate dup principiul fr pierderi sau cu pierderi. Tehnicile fr pierderi subneleg, c fiierul de informaie restaurat este identic cu cel original. Aceasta este absolut necesar pentru diverse tipuri de informaii, de exemplu: Codul de main, fisiere de prelucrare a textelor, introducerea numerelor n tabele, etc. n aa caz nu ne putem permite s aezm greit nici chiar un singur bit de acest tip de informaie. Pentru comparaie, fisierele de date care reprezint imagini i alte semnale obinute, nu trebuie s urmeze strict aceast condiie la depozitare sau transmisie. Toate msurrile reale conin o cantitate sigur de zgomot. Dac schimbrile fcute asupra acestor semnale amintesc o cantitate mic de zgomot adiional, nici un ru nu este fcut. Tehnicile de comprimare care permit acest tip de degradare se numesc tehnici cu pierderi. Aceast deosebire este important deoarece tehnicile cu pierderi sunt mult mai eficace la comprimare dect metodele fr pierderi .Cu ct coeficientul de compresie este mai superior, cu att mai mult zgomot se adaug la informaie.Tabelul 7.1

Clasificrile comprimrii. Metodele comprimrii datelor pot fi mprite n dou moduri. n (a) tehnicile snt clasificate ca fr pierderi sau cu pierderi. Metoda fr pierderi restaureaz informaia compresat exact n aceli format original, n timp ce metodele cu pierderi numai genereaz o aproximaie. n( b) snt clasificate ca metode acordate la fix sau o dimensiune variabil de grup luat din fiierul original i nscris n fiierul compresat.

Imaginile transmise prin reeaua mondial Internet, este un exemplu excellent pentru a nelege ct de important este comprimarea datelor. Presupunem c noi avem nevoie s descrcm o fotografie digitala colorat pe un calculator cu modem 33.6 kbps. Dac imaginea nu este compresat (un fiier TIFF, de exemplu), el va conine aproximativ 600 kbytes de informaii. Dac ea a fost compresat cu ajutorul metodei fr pierderi (ca de exemplu n formatul GIF), ea va avea aproximativ jumtatedin aceast dimensiune, sau 300 kbytes. Dac a fost folosit compresarea cu pierderi (ca de exemplu un fiier JPEG), el va avea aproximativ 50 kbytes. Punctul de descrcarea planificat pentru aceste trei fiiere echivalente este 142 secunde, 71 secunde, i respectiv 12 secunde. Ce diferen mare! JPEG este alegerea cea mai bun pentru trecerea in format digital a fotografiei, n timp ce GIF se ntrebuineaz cu imaginile extinse, ca de exemplu logo-urile companiilor care au suprafeele mari in nuana unei singure culoari.

Al doilea mod de clasificare a metodelor de comprimare a datelor este artat n Tabelul 7.1b. Cele mai multe programme de comprimare a datelor funcionez, lund un grup de date de la fiierul original, compresndu-l ntr-un anumit mod, i dup aceea salvnd grupul compresat la fiierul rezultat. De exemplu, una din tehnici n acest tabel este CS&Q, comod pentru discretizarei/sau cuantificare. Presupunem c noi compresm o und (semnal) digitzat, ca de exemplu un semnal audio care a fost transformat digital la 12 biti. Noi putem citi dou mostre alturate din fiierul original (24 bii), putem nltura una dintre mostre n ntregime, putem nltura 4 cifre binare mai puin semnificative de la alt mostr, i dup aceea s salvm cei 8 bii rmai n fiierul de ieire. Cu 24 bii la intrare i 8 bii la ieire, noi am implementat coeficientul de compresie 3:1 folosind un algoritm cu pierderi. Cu toate c aceasta este o metod crud, ea este foarte eficace cnd e folosit cu o tehnic numit comprimare transformant. Despre aceasta vom discuta mai tirziu, aceasta fiind baza JPEG.

Tabelul 27-1b arat CS& Q pentru a fi o schema cu intrrea fix si iesirea fix. n aa mod, un numr fix de bii este citit de la fiierul de intrare i un numr mai mic fix de bii este nscris n fiierul rezultat. Alte metode de comprimare permit numrul de bii variabil pentu citire sau nscriere. La descrierea fiecrei metode de comprimare, ne vom referi acest tabel pentru a nelege cum acestea se ncadreaz n aceast schem de clasificare

De ce JPEG i MPEG nu snt artate n acest tabel? Aceti sunt algoritmi complicai care combineaz multe alte tehnici. Ele sunt prea sofisticate pentru a fi clasificai n aceste categorii simple.

Codificarea Run-Length rularea-lungimii.

Fiierele de date adesea conin acelai caracter repetat de mai multe ori n rnd. De exemplu, fiierele text folosesc deseori spaiile pentru a despri propoziiile, paragrafele, formetul tabelelor & diagramelor, etc. Semnalele digitizate pot de asemenea s ruleze cu aceleai valoare, indicnd semnalul neschimbat. De exemplu, o imagine a unui cer n noapte ar trebui s conin tiraje mari a caracterului ce reprezint fundalul negru. De asemenea, muzica digitizata ar fi putut conine un tiraj mare de zerouri ntre cntece. Codificarea Run-Length este o metod simpl de compresare a acestor tipuri de fiiere.

Figura 7-1 ilustreaz codificarea Run-Length pentru o succesiune de informaie ce conine rulari frecvente de zerouri. De fiecare dat cnd valorile zero se ntlnesc n informaia de intrare, dou valori sunt scrise la fiierul rezultat. Prima din aceste valori este zero, un flag pentru a indica c codificrea Run-Length starteaz. Valoarea a doua este numrul de zerouri n rulare. Dac lungimea medie a rulrii va fi mai mare dect doi, atunci comprimarea va avea loc. Pe de alt parte, multe zerouri singure n informaie ar putea s fac fiierul codificat mare dect originalul.

Multe metode de compresare Run-Length au fost dezvoltate. De exemplu, informaiile de intrare pot s fie tratate precum octei independeni, sau grupe de octei care reprezint ceva mult mai desvrit, ca de exemplu numerele reprezentate n virgul mobil. Codificarea Run-Length poate fi ntrebuinat asupra unuia din caractere (ca asupra zeroului n exemplul de mai sus), asupra ctorva caractere, sau pe toate.O schem mai general a unei rulri Run-Length este Packbits, creat pentru utilizatorii Macintosh. Fiecare octet (opt cifre binare) de la fiierul de intrare este nlocuit cu nou cifre binare n fiierul compresat. Cifra a noua binar adaugat este interpretat ca semn a numrului. n aa fel, fiecare caracter citit de la fiierul de intrare este ntre 0 la 255, n timp ce fiecare caracter scris la fiierul codificat este ntre -255 i 255. Pentru a nelege cum acesta este folosit, fie la fiierul de intrare: 1,2,3,4,2,2,2,2,4, i fiierul compresat generat cu algoritmul Packbits: 1,2,3,4,2,&3,4. Programul de comprimare pur i simplu transfer fiecare numr de la fiierul de intrare la fiierul compresat, cu excepia rulrii:2,2,2,2. Aceasta este reprezentat n fiierul compresat cu dou numere: 2,-3. Primul numr ("2") indic din ce caracter face parte rularea. Numrul al doilea("-3") indic numrul de caractere n rulare, gsit prin valoarea absolut i adugarea unitii. De exemplu, 4,-2 nseamn 4,4,4; 21,-4 nseamn 21,21,21,21,21 etc.

Figura 7-1.

Exemplu de codificrii Run-Length. Fiecare rulare de zerouri este nlocuit cu dou caractere n fiierul compresat: Un zero pentru a indica c comprimare are loc, urmat cu numrul de zerouri n rulare.

O inconvenien a metodei Packbits este c aceti nou bii ar trebuie s fie reformatai n cei opt bii standard folosii n depozitarea de calculator i transmisie. O modificare util la aceast schem poate fi fcut atunci cnd intrarea este textul ASCII. Cum e artat i n Tabela 27-2, fiecare caracter ASCII este de obicei salvat ca un octet ntreg (opt bii), dar ntr-adevr se folosesc doar apte bii, pentru a identifica caracterul. Cu alte cuvinte, valorile 127 - 255 nu sunt definite cu nici o semnificaie standardizat, i au nevoie de a fi salvate sau transmise. Aceasta permite bitului al optulea de a indica dac codificrea Run-Length are loc.

Codificarea Huffman

Aceast metod se numete n numele lui D. Huffman, care a i dezvoltat procedura n 1950. Figura 7-2 arat o histogram cu valorile bitilor de la un fiier mare ASCII. Mai mult de 96 % din acest fiier se compune din numai 31 caractere: litere mici, spaiul, virgula, perioada, i revenirea la nceputul rndului. Aceast observaie poate s se ntrebuineze, pentru a face o schem de comprimare corespunztoare pentru acest fiier. S admitem, c fiecrui din aceste 31 caractere comune se atribuie un cod de cinci biti: 00000 = "a", 00001 = "b", 00010 = "c", etc. Acest permite 96% din fiier s fie redus n dimensiune cu 5/8. Ultimul din codurile de cinci biti, 11111, va fi un flag care indic c caracterul transmis nu este unul dintre 31 caractere comune. Urmatorii 8 biti din fisier indica ce caracter corespunde codului ASCII. Aceasta aduce la faptul c 4% din caractere n fiierul de intrare necesit 5+8=13 bii. Ideea const n atribuirea caracterelor mai des folosite mai putini bii i caracterelor folosite mai rar mai muli bii. n exemplul de mai sus, numrul mediu de cifre binare necesare pentru caracterul original este: 0.965 + 0.0413 = 5.32. Cu alte cuvinte, rata compresrii completeva fi: 8 bii/5.32 bii sau aproximativ 1.5:1. Codificarea Huffman utilizeaz aceast idee pin la urma. Caractere care se ntlnesc mai mai des, aa ca spaiul i perioada, pot fi desemnai prin unul sau doi biti. Caracterele utilizate mai rar, ca de exemplu: !, #, $ i %, necesit doisprezece sau mai muli bii. n termeni matematici, situaia optim este atunci cnd numrul de biti folositi pentru fiecare caracter este proporional cu logaritmul probabilitatii apariiei caracterului. O caracteristic inteligent a compresrii Huffman este: cum codurile cu lungimea variabl pot fi npachetate mpreun. Imaginai-v c primii un curent de informaie n serie de date i zerouri.

Tabelul 7-2. Codul ASCII. Acest standard este stabilit pentru a permite mesajelor i datelor sa fie reprezentate n form binar. Fiecare caracter care poate fi tiprit este un numr desemnat ntre 32 i 127, n timp ce numerele ntre 0 i 31sunt folosite pentru aciunile de control divers. Cu toate ca 128 coduri sunt predefinite, caracterele ASCII se salveaz de obicei ca un bait ntreg (8 bii). Valorile nedefinite(128 - 255) sunt adesea folosite pentru scrisul grecesc, simbolurile din matematic, i diverse modele geometrice; dar acestea nu sunt standardizate. Multe din caracterele controlului (0 la 31) se sprijin pe reelele de comunicare mai vechi, i nu sunt aplicabile la tehnologia de calculator.

Figura 7.2. Histogram unui text. Aceasta este o histogram valorilor ASCII dintr-un capitol a acestui curs. Cele mai multe caractere comune sunt scrisul cu litere mici,spaiul i revenirea la nceputul rndului.Dac fiecare caracter este reprezentat pe opt biti , putem direct s desprindei un caracter de urmtorul separnd cte 8 cifre binare. Acum luai n consideraie un curent de informaie comprimat prin metoda Huffman, unde fiecare caracter poate s fie un numr de biti variabil. Cum e posibil de separat un caracter de urmtorul? Rspunsul se afl n selectarea corespunztoare Huffman, care activeaz separarea corect. Urmeaz un exemplu pentru a ilutsra cum se efectueaz aceast selectare.

Figura 7-3 arat simplificat o schem de codare Huffman. Caracterele de la A la G se ntlnesc n informaia original cu probabilitile artate. ncepnd cu caracterul A care este cel mai comun, i noi l vom reprezenta printr-un singur bit de cod: 1. Caracterul urmtor cel mai comun, B, primete doi bii, codul: 01. Aceasta continu pn la caracterul minimum frecvent, G, fiind nsemnat cu ase cifre binare, 000011. Dup cum e artat n aceast desen, lungimea variabil codificat se grupeaz n grupuri de opt bii, standard pentru folosirea n calculator.

Cnd comprimarea are loc, toate gruprile de 8 bii sunt aranjate de la nceput pn la sfrit, pentru a forma un ir lung n serie de uniti i zerouri. La examinarea mai detailat a tabelului de codare din Fig. 7-3, observm c fiecare cod const din dou pri: un numr de zerouri naintea unitii, i un cod binar opional dup unitate. Aceasta permite curentului de informaie binare s fie separat n coduri fr a avea nevoie de separatoare sau alt marcator ntre coduri.

Figura 7-3. Codificarea Huffman. Tabelul codificrii desemneaz fiecarui din apte simbol folosit n acest exemplu un cod binar de o lungime de variabil, bazat pe probabilitatea de apariie a lui. Informaiile originale compuse din aceste 7 caractere este traduse cu acest tabel n codificarea Huffman. Deoarece fiecare cod Huffman are o lungime diferit, informaiile binare trebuie s fie regrupate n octeii standarzi de 8 bii pentru depozitare i transmisie. Programul de decomprimare privind ca un flux de uniti i zerouri pn cnd se formeaz un cod valid, i dup aceea pornind n cautarea caracterului urmtor. Modul n care se formeaz codurile asigur c nu va exista ambiguitate n separare.

O versiune mai sofisticat a metodei Huffman se numete aritmetica codificat. n aceast schem, succesiuni de caractere sunt reprezentate cu codurile independente, conform probabilitii lor de apariie. Acesta are un avantaj de comprimare mai bun a datelor circa 5-10%. Codificarea Run-length urmat de cea Huffman sau aritmetica au o strategie comun. Dup cum urma de ateptat, aceste tipuri de algoritmi sunt foarte complicai, i de obicei snt lsati n seama specialitilor comprimrii datelor.

Pentru a pune n aplicare codificarea Huffman sau aritmetica, algoritmii de comprimare i decomprimare trebuiesc s se combine n codul binar folosit la reprezentarea fiecrui caracter (sau grup de caractere). Acetea pot fi manipulai n unul din dou moduri. Mai simplu ar fi s folosim predefinit o tabel codificat, care ar rmne ntotdeauna aceeai, nectnd la aceea c informaia este compresat. Scheme mai comlexe folosesc codificarea optimizat pentru informaii special ntrebuinate.Aceasta cere ca tabelul codificat s fie inclus n fiierul compresat pentru folosirea cu programul de decomprimare. Ambele metode sunt comune.

Delta Codificare

n tiin, inginerie i matematic, litera greceasc delta () este folosit pentru a indica schimbarea ntr-o variabil. Termenul Delta codificare se refer la

Figura 7-4. Exemplu de delta codificare. Prima valoare din fiierul codificat este ntocmai ca prima valoarea din fiierul original. Dup aceea, fiecare exemplu din fiierul codificat este diferena ntre exemplul curent flux i ultimul exemplu din fiierul original.

cteva tehnici care salveaz informaia ca o diferen ntre mostrele succesive (sau caractere), n loc de salvarea mostrelor nsi. Figura 7-4 arat un exemplu cum se efectueaz aceast procedur. Prima valoare n fiierul delta codificat este ntocmai ca prima valoarea din informaia original. Urmtoarele valori din fiierul codificat snt egale cu diferena (delta) ntre valoarea corespondent n fiierul de intrare, i valoarea anterioar n fiierul de intrare.

Delta codificare pot fi folosit la comprimarea datelor cind valorile in informatiile originale sunt netede, adica, valorile alaturate se deosebesc neesenial. Acesta nu se refer la textul ASCII si codul de masina; oricum, el este foarte util cind fisierul reprezinta un semnal. De exemplu, Fig. 7-5a arata un segment a unui semnal audio, cifrat la 8 biti, cu fiecare mostra intre -127 si 127. Figura 7-5b arata versiunea delta codificat a acestui semnal. Caracteristica codificrii delta este c semnalul codificat are o amplitudine mult mai joasa decit semnalul original. Cu alte cuvinte, delta codificare a sporit probabilitatea c valoarea fiecrei mostre va fi apropiat de zero, i a sczut probabilitatea c ea va fi departe de zero. Aceast probabilitate accidentat este tocmai cauza, care ne sugereaz c escte necesar de a folosi comprimarea Huffman. Dac semnalul original nu se schimb, sau schimb linear, delta codificare va avea drept rezultat rularile de mostre avnd aceeai valoare.

Figura 7-5. Exemplu de delta codificare. Figura( a) este un semnal audio cifrat la 8 bii. Figura( b) arat versiunea delta codificat a acestui semnal. Delta codificare se folosete pentru comprimarea datelor dac semnalul fiind codificat varieaz ncet de la mostr-la-mostr.

Aceasta este ceea de ce are nevoie comprimarea run-length. Att delta codificare urmat de Huffman i run-length au o strategie comun pentru compresarea semnalelor.

Ideea folosit la delta codificare poate fi extins ntr-o tehnic mult mai complicat numit Linear Predictive Coding, sau LPC. Pentru a nelege LPC, imaginai-v c primele 99 mostre de la semnalul de intrare au fost codificate, i noi suntem pe punctul de a manipula mostra cu numrul 100. Dup aceea ne ntrebm pe noi nine: bazndune pe primele 99 mostre, ce valoare este mai acceptabil pentru mostra 100? n delta codificare, rspunsul este c cea mai acceptabil valoarea pentru mostra 100 este ntocmai ca valoarea anterioar, mostra 99. Aceast valoare ateptat este folosit ca referin pentru a codifica mostra 100. Astfel, diferena ntre mostra i perspectiva este plasat n fiierul codificat. LPC se oprete detaliat la aceasta fcnd presupunerea care este cea mai bun valoare probabil . Aceasta tine de ultimele cteva mostre , mai degrab dect tocmai ultima mostr. Algoritmii folosii cu LPC sunt filtrele asemntoare cu cele recursive, folosite de z-transformare i de alte tehnici matematice.Compresarea Lzw

Comprimarea LZW se numete n cinstea programatorilor A. Lempel i J. Ziv, cu modificri ulterioare fcute de ctre Terry A. Welch. Aceasta este tehnica principal pentru comprimarea datelor de uz general datorit simplitii i aplicrii multilaterale. Caracteristic, dvs putei s aplicai LZW pentru a compresa textul, codul de main, i fiiere de date n jumtate dect dimensiunea lor original. LZW de asemenea execut bine cnd sunt procesate fiiere de informaie inutile, ca de exemplutabele de date, codul surs al calculatoarelor i semnale achiziionate. Coeficientul de compresie de 5: 1 este comun pentru aceste cazuri. LZW este baza ctorva algoritmi de prelucrare a datelor n calculatoarele personale care permit "dublarea capacitatea unitii hard" .Comprimarea LZW este ntotdeauna folosit n fiierele de imagine GIF, i este oferit ca opiune n TIFF i Postscript. Comprimarea LZW este protejat de patenta U.S. cu numrul 4,558,302, a oferit n Decembrie 10, 1985 pentru Sperry Corporation (acum Unisys Corporation). Pentru informaia de liceniere comercial: Welch Licensing Department, Law Department, M SC2SW1, Unisys Corporation, Blue Bell, Pennsylvania, 19424-0001. Comprimarea LZW folosete un tabel de cod, ilustrat n Fig. 27-6. O alegere comun trebuie s furnizeze 4096 intrri n tabel. n acest caz, informaia codificat LZW const completamente din coduri pe 12 bii, fiecare referindu-se la una dintre intrrile n tabelul de cod. Decomprimare este realizat, lund fiecare cod din fiierul compresat, i traducndu-l prin tabelul de cod pentru a gsi ce caracter sau caracterele pe care le reprezint. Codurile 0-255 n tabelul de cod sunt ntotdeauna reprezentai printr-un singur octet al fiierului de intrare. De exemplu, dac numai aceste prime 256 coduri s-au ntrebuinat, atunci fiecare octet din fiierul original s-a transformat n 12 bii n fiierul codificat LZW , avnd drept rezultat 50 % dimensiune de fiier mai mare dect fiierul original. n timpul decomprimrii, fiecare cod de12 bii ar fi fost tradus prin tabelul de cod napoi n octeii singuri. Desigur, aceasta nu nu este o situaie folositoare.

FIGURA 27-6. Exemplu de comprimarea a tabelului de cod. Aceast este baza metoda comprimrii populare LZW. Codificarea se produce prin identificarea succesiuni de octei n fiierul original care exist n tabelul de cod. Codul pe 12 bii reprezint succesiunea identificat i se amplaseaz n fiierul compresat n loc de succesiunea identificat. Primele 256 intrri n tabel corespund LZW valorilor de octei, de la 0 la 255, n timp ce intrrile rmase corespond succesiunilor de octei. Algoritmul LZW este un mod eficient de a genera tabelul de cod, bazat pe informaiile speciale compresate.(Tabelul de cod n aceast figur este un exemplu simplificat). Metoda LZW realizeaz comprimarea folosind codurile de la 256 pn la 4095 pentru a reprezenta succesiuni de octei. De exemplu, codificarea 523 reprezint succesiunea de trei octei: 231 124 234. De fiecare dat cnd algoritmul de comprimare ntlnete aceast succesiune n fiierul de intrare, codul 523 este nscris n fiierul codificat. n timpul decomprimrii, codul 523 este tradus prin tabelul de cod pentru a se recrea succesiunea de 3 octeti adevrai. O succesiune mai lung atribuit unui singur cod, i cu ct succesiunea este mai des repetat, este atins un grad de comprimare mai superior.

Dei aceasta este o metod simpl, exist dou obstacolele majore care trebui s fie eliminate: (1) Cum putem determina ce succesiuni ar trebui s fie n tabelul de cod, i (2) cum putem furniza programului de decomprimare acela tabel de cod care a fost folosit de programul de comprimare. Algoritmul LZW rezolv ambele aceste probleme.

Cnd programul LZW pornete s codifice un fiier, tabelul de cod conine numai primele 256 de intrri, restul tabelului fiind gol. Aceasta seamna c primele coduri nscrise n fiierul compresat sunt pur i simplu octeii fiierului de intrare fiind transformai la 12 bii. La continuarea comprimrii, algoritmul LZW identific succesiunile repetate n informaii, i le adaug n tabelul de cod. Comprimare pornete din a doua oar, cnd este ntlnit succesiunea. Punctul cheie este c o succesiune de la fiierul de intrare nu este adugat la codul tabelul , pn cnd ea a fost deja numit n fiierul compresat cu caracterele independente (coduri de la 0 la 255). Aceasta este important pentru c permite programului de decomprimare pentru a reconstrui tabelul de cod direct de la informaiile compresate, fr necesitatea de a transmite tabelul de cod separat.

Tabel 27-3 furnizeaz pasul-cu-pas detaliile pentru un fiier de intrare de exemplu compus din din 45 octei, textul ASCII: the/rain/in/Spain/falls/mainly/on/the/plain. (Ploaia n Spania cade n special pe vi). Cnd noi spunem c algoritmul LZW citete caracterul "a" de la fiierul de intrare, noi avem n vedere c citete valoarea: 01100001 ( 97 exprimat n 8 bii), unde 97 este"a" n ASCII. Cnd noi spunem s scrie caracterul "a" la fiierul cifrat, noi avem n vedere scrierile: 0000011000 (97 exprimat n 12 bii).

TABELA 7-3. Exemplul de LZW. Aceasta arat comprimarea expresiei: the/rain/in/Spain/falls/mainly/on/the/plain/. (Ploaia n Spania cade n special pe vi.)

Algoritmul de comprimare folosete dou variabile: CHAR i STRING. Variabile, CHAR, ine de un singur caracter, un octet cu valoarea ntre 0 i 255. Variabil, STRING, este un ir unei lungimii variabil, un grup de una sau mai multe caractere , cu fiecare caracter fiind un octet singur. n caseta 1 din Fig. 27-7, Programul pornete s ia primul octet de la fiierul de intrare, i numindu-l n variabil, STRING. Tabel 27-3 arat aceast aciune n linia 1.

Acesta este urmat cu ciclul de algoritm pentru fiecare octet adiional n fiierul de intrare, teleghidat n schema procesului tehnologic cu caseta 8. De fiecare dat un octet este o lectur de la fiierul de intrare( boxa 2), el este coninut n variabila, CHAR. Tabelul de informaie este dup aceea cutat s determine dac concatenarea dou variabile, STRING+ CHAR, are deja s fie un cod desemnat( boxa 3).

Dac starea n tabelul de cod nu a gsit trei aciuni sunt luate, pe msura ce casetele conduse nuntru 4, 5 & 6.

n caseta 4, codul pe 12 bii corespunde coninutul variabil, STRING, scris n fiierul compresat. n caseta 5, un cod nou este creat n tabel pentru concatenare de STRING+ CHAR. n caseta 6, variabila, STRING, ia valoarea variabile, CHAR. Un exemplu de aceste aciuni este artat n liniile 2-10 n Table 27-3, pentru primii 10 octei a fiierul din exemplu.

Cnd starea n tabelul de cod este gsita in (boxa 3), concatenarea de STRING+ CHAR este coninut n variabila, STRING, fr nici o alt aciune avnd loc( boxa 7).

In asa fel , dac succesiunea corespunzatoare este gasita in tabel,nici o aciune nu ar trebui s fie determinata nainte succesiune ,dac este o alta succesiune mult mai lunga de asemenea in tabel. Un exemplu de acest fel este aratat in linia 11, unde succesiunea: STRING+ CHAR = in, este identificata ca un cod in tabel. In linia 12, caracterul urmator de la fisierul de intrare, /,este adaugat la succesiune , si tabelul de cod este cautat in /.Dupa cum aceasta este o succesiunea mai lunga nu se gaseste in tabel, programul adauga aceasta la tabelul, codul rezultat pentru succesiunea de schita care este in tabel,codul rezultat pentru succesiunea mai scurta care se geseste in tabel( codificarea 262), si porneste in cautarea pentru succesiuni incepin cu caracterul,/. Acest debit de evenimente este continuate pina cind acolo nu sunt nici un caracter in fisierul de intrare. Programul este impachetat cu valoarea de cod corespondenta cu curenta de STRING pentru a fi scrisa la fisierul compresat( pe masura ce e ilustrat in caseta 9 de Fig. 27-7 si linia 45 de Table 27-3). O schema de proces algoritmul decomprimarii LZW este aratat in Fig. 27-8. Fiecare cod este citit de la fisierul compresat i e comparat cu tabelul de cod pentru a furniza traducerea. Dup cum fiecare cod este prelucrat n acest stil, tabelul de cod este actualizat aa ca el continuu s egaleaz cu acela folosit n timpul comprimrii. Oricum, se afl o complicaie mic n rutina de comprimare. Exist combinaiile sigure de informaii care au drept rezultat algoritmul de comprimare primind un cod care nu exist nc n tabelul de cod a lui. Aceast eventualitate este manipulat n casetele 4, 5 & 6. Doar o duzin de linii sint necesare pentru programele cele mai elementare LZW. Dificultatea real se gsete n conducerea codului tabelului eficient. Accesul de for de animal are drept rezultat cerinele de memorie mari i execuia unui program lent. Cteva trucuri se ntrebuineaz n programele comerciale LZW pentru a mbunti realizarea lor. De exemplu, problema de memorie ridic pentru c el nu tie nainte cum ct timp va fi fiecare iruri de caractere pentru fiecare cod

Cel mai LZW programeaz mner acest utiliznd natura codului tabelului inutil. De exemplu, privii la linie 29 in Tabelul 27-3, unde codificatia 278 este definit pentru a fi ainl . In locul pastrarii acestor 4 octeti, codificarea 278 ar fi putut fi salvat ca: codificarea 269+1 , unde codificarea 269 sa fie anterior definita precum ain in linia17 .De asemenea, codificarea 269 ar fi fost salvata precum: Codificarea 261 +n unde codificarea 261 a fost anterior definit precum aiin din linia 7. Acest model intotdeauna este bazat: Fiecare cod poate sa fie exprimat ca codul anterior plus un caracter nou.

Timpul de executarea a algoritmul de comprimare este limitat cautind tabelul de cod pentru a determina daca un chibrit este prezent. Ca asemanare, imaginati-va ca dvs vreti sa gasiti daca numele prietenului dvs este in lista cartii de telefon. Folosul este,unica carte de telefon,pe care dvs o aveti ,este aranjata din cifre de telefon,in ordine alfabetica.. Aceasta necesita ca dvs sa cautati pagina dupa pagina ,pentru a gsi numele cautat de dvs . Aceasta ineficienta situatie este exact ca cautarea in toate codurile 4096 pentru un chibrit la un sir de caractere specific.

Sirul de caractere. Rspuns: Organizati tabelul de cod astfel ca ceea ce dvs cautati var spune unde sa priviti ( cum partial o carte de telefoane este aranjata in ordine alfabetica). Altfel formulat, sa nu desemnati 4096 de coduri la amplasarile secventiale in memorie. Mai degrab, impartiti memoria in parti,bazat pe aceea ca orice succesiuni vor fi salvate acolo. De exemplu , presupuneti ca noi vrem sa gasim daca succesiunea: Codificarea 329 + x, este in tabelul de cod.

Tabelul de cod ar trebui sa fie organizat astfel ca x sa indice unde la pornire privirii. Exista multe scheme pentru acest tip de conducere de tabel de cod, si ele pot deveni complet complicate.Aceasta ridica sus ultimul comentariu la LZW si schemelor de comprimare asemanatoare: Aceasta este foarte concurabila zona. In timp ce datele comprimate de baza sunt relativ simple, tipurile programelor vindute precum produsele comerciale sunt extrem de sofisticate

Companile fac banii vinzind dvs, programeaza care executa comprimarea, si gelos protejeaza comertul secretelelor prin patente etc. Nu asteaptati sa realizeze acelasi nivel de realizare pe masura ce aceste programe sunt intr-o munc de citeva ore.

Jpeg (Transform Compression)

Multe metode de comprimarea componentei de circuit cu pierderi au fost dezvoltate; Oricum, o familie de tehnici au chemat sa transforme comprimare are dovedita cea mai multa valoroasa. Cel mai bun Exemplul de transformari comprimate este ntruchipat n standardul popular JPEG de imagine cifrat. JPEG se numete din originea lui, Grupele ntrunite De Fotografi Experi. Noi vom descrie funcionarea JPEG pentru a ilustra cum lucreaz comprimarea cu pierderi .

Noi am discutat deja o metod simp de comprimare a datelor componentei de circuit cu pierderi, preluarea de date statistice mai aspre i cuantificarea sau( CS& Q n Table 27-1). Aceasta implic s reduc numrul de cifre binare n mostr sau complet s dea la o parte unele dintre mostre. Ambele aceste proceduri au efectul dorit: Fiierul de informaie devine mai mic pe seama calitaii semnalului.

Dvs putei s v ateptai, c aceste simple metode nu lucreaz foarte bine.

Figura 27-9.

Divizia de imagine jpeg. JPEG transform pornirile de comprimare stricnd imaginea n 88 grupe, fiecare coninnd 64 puncte. Trei de aceste 88 grupe sunt mrite n aceast figur, artnd valorile punctelor independente, o unic valoare de octet ntre 0 i 255.

Transformai comprimarea,se sprijin pe o premis simpl: Cnd semnalul este transmis prin Fourier( sau alt) transform, rezultatul valorilor informaiilor mai mult nu va fi egal n informaia lor ducnd rolurile. n special ,componentele de frecven joas sunt mai importante dect componentele de frecven nalt. tergnd 50% de cifre binare de la componentele de frecven nalt pot s tearg, s zicem, doar 5% de informaie cifrat.

Cum este artat n Fig. 27-9, Comprimarea JPEG pornete s sparg imaginea n 88 grupe de puncte. Algoritmul plin JPEG poate s accepte o gam mare de bii n pixel, incluznd folosirea de informaie color. n acest exemplu, fiecare punct este un octet singur, o valoare a luminoyiii este ntre 0 i 255. Aceste 88 grupe cerceteaz octetul independent n timpul comprimrii. m aa mod, fiecare grup este iniial reprezentat cu 64 octei. Dup ce transformnd i tergnd informaii, grupul de fiecare este reprezentat cu comprimarea 2 la 20 octei.

n timpul comprimrii, inversa transformaiei ia din 2 la 20 octei pentru a crea o aproximaie originale a grupului 8x8.Aceste grupuri aproximative sunt dup aceea potrivite mpreun pentru a forma imaginea compresat. De ce folosi grupurile de 8x8 n loc de ca de exemplu,16x16? s-a sprijinit pe dimensiunea maxim care a reunit tehnologia de circuit ar putea s manipuleze la n momentul standard a fost dezvoltat. n oricare caz, lucrarea de 8x8 dimensiune e bine, i s-ar putea s nu fie schimbat n viitor.

Multi cercettori au fost anchetati pentru comprimarea datelor, unii dintre ei au inventat n mod special pentru acest scop. De exemplu, Karhunen-loeve transform s furnizeze coeficientul de compresie cel mai bun posibil, dar este dificil pentru a pune n aplicare. Fourier transform s fie uor de folosit, dar nu furnizeaz comprimarea adecvat. Dup multe competiii, ctigtorul este relativ Fourier transform, Discrete Cosine Transform( DCT).

Aa cum Fourier transform sinusul de folosire i valurile de cosinus pentru a reprezenta un semnal, DCT numai folosete valurile de cosinus. Exist cteva versiuni DCT, cu diferenele nensemnate n matematica lor. Ca exemplu de o versiune, imaginai-v 129 un semnal de punct, rulnd de la mostra 0 la mostra 128. Acum, facei acest 256 un semnal de punct copiind mostre 1 prin 127 i de calcul ei precum mostrele 255 la 130. Care este: 0, 1, 2, , 127, 128, 127, , 2, 1. Lund Fourier transformnd acest 256 semnal de punct are drept rezultat un spectru de frecven de 129 puncte, ntinse ntre 0 i 128. Dup cum semnalul domeniului de timp a fost obligat pentru a fi simetric, partea de spectrului imaginar va fi construit de toate zerouri. n alte cuvinte, noi am pornit cu 129 un semnal de domeniu de timp de punct, i s-a sfrit cu un spectru prii 129 puncte, de frecven undei cosinus . Iat, DCT!

Cnd DCT este luat din grupul 8x8 aceasta aduce la spectrul 8x8.n alte cuvinte, 64 numere sunt trecute la o alt treapt de vitez n alte 64 numere.

Toate aceste valori sunt reale; aici nu e nici o matematic complex Aa cum n analiza Fourier, fiecare valoare n spectru nu este amploarea unei funcia de baz. Figura 27-10 arat c 6 din 64 funciile de bazei folosite n 8x8 DCT, conform ,unde amplituda st n spectrul. 8x8 a funciilor sde baz DCT este dat cu

Ecuaie 27-1.

Funciile de baz DCT. Variabilele x & y sunt indecii n domeniul spaial, i u & v suntei indecii n spectrul de frecven. Acest este pentru 8x8 DCT, facnd rularea de index de la 0 la 7.

Prile de frecven joas sunt plasate in colul stnga sus a spectrului , n timp ce frecvenele nalte sunt plasate n dreapta jos .Componenta DC este 0, 0, de sus-stng valoarea cea mai mare. Funcia de baz pentru 0, 1 este o jumtate din ciclul undei de cosinus ntr-o direcie, i o valoare constant n alt. Funcia de baz pentru 1, 0 este asemntoare, tocmai rotit cu 90E.

Figura 27-10.

Funciile de baz DCT . Spectrul DCT se compune din matricea 8x8, cu fiecare element n matrice fiind o amploare de unele dintre 64 funcii de baz. ase din aceste funcii de baz sunt artate aici , referitoare la amplituda corespunztoare .

DCT calculeaz spectrul corelnd grupa de pixeli 8x8 cu fiecare funcie de baz. n aa fel, fiecare valoare spectral, este gsit, nmulind funcia de baz corespunztoare cu grupul de pixeli 8x8 i dup aceea adunnd produsele. Atunci este nevoie de dou reglri ca s termine calculul DCT( aa cum cu Fourier se transform). Mai nti mprii 15 valori spectarle n rnd 0 i coloan 0 cu dou.

ntr-al doilea rnd, mprii toate 64 valori n spectru cu 16. Inversul DCT este calculat desemnnd fiecare amplitudine n spectru la funcia de baz corespunztoare, i adunnd s recreeze domeniul spaial. Ali pai adugtori nu sunt necesari. Acetia sunt exact aceleai concepte pe msura ce n analiza Fourier, tocmai cu funciile de baz diferite.

Figura 27-11 ilustreaz JPEG codificarea pentu trei grupe 8x 8 identificate n Fig. 27-9. Coloana stng, Figura a, b& c, arat valorile originale a pixelilor.

Coloana central, Figura d, e & f , arat spectrul DCT a cestor grupe...

.FIGURE 27-11

Ilustreaz JPEG codificare.Coloana stng arat trei grupe 8x8 pixeli, artatte n Fig 27-9.Coloana central arat spectrul DCT pentru aceste grupe.A treia coloana arat greeala in decompresarea pixelilor, din urmtorii bii folosii pentru a reprezenta spectrul.

Coloana dreapt Fig g,h i i arat efectul de a reduce numrul de bii folosii pentru reprezentarea fiecarei componente n spectrul de frecven. De exemplu,( g) este format prin trunchierea fiecarei mostre n( d) la zece bii, lund inversa DCT, i dup aceea scznd imaginea reconstruit de la original. De asemenea,( h) i( i) sunt formai prin trunchierea fiecarei mostre n spectru la opt bii i respectiv cinci.La fel de ateptat e eroarea sporit n reconstrucie ,cum de folosit mai puini bii pentru a reprezenta informaia.

Ca exemplu de aceast trunchierea de bii, arat coloana de centru reprezentat cu 8 cifre binare pe valoarea spectral, aranjat ca 0 la 255 pentru componenta DC, i -127 la 127 pentru alte valori.

Metoda a doua de a compresa domeniul de frecven trebuie sa se lipseasc de cteva din 64 valori spectrale. Dup cum snt artate spectrele n Fig. 27-11, aproape tot semnal este coninut n componentele de frecven joas. Aceasta nseamn cel mai mare divizor comun a componente de frecven poate s fie eliminat, numai c va nruti intr-o mic cantitate semnalul.

Figura 27-12 arat un exemplu contorsiunea de imaginii care se ntmpl cnd numerele diverselor componentelor de frecven nalt sunt terse.Grupul 8x8 de folosit n acest exemplu este imaginea de ochi de Fig. 27-10. Figura( d) arat folosirea corect a reconstruciei folosind toate 64 valori spectale.Figurile rmase arat reconstrucia folosind numrul indicat de cei mai sczui coeficieni de frecven. Dup cum e ilustrat n( c), chiar i tergnd trei ptrimi din cel mai mare divizor comun ,componenta de frecven d o eroarea n reconstrucie. Chiar i mai bine, eroarea care se ntmpl se aseamana foarte mult cu un zgomot ntmpltor.

JPEG e un exemplu bun pentru a vedea cum cteva scheme de comprimare datelor pot fi combinate pentru eficacitate. Procedura ntreag JPEG este schiat n urmtorii pai. Mai nti, din imagine se scot 8x8 grupuri . ntr-al doilea rnd, DCT este luat din fiecare grup.n al treilea rnd ,fiecare 8x8 spectre este compresat cu metodele de mai sus: Reducnd numul de cifre binare i eliminnd unele dintre componente. Aceasta are loc ntr-un singur pas, cu care coordoneaz un tabel de cuantificare.

Dou exemple de tabelele de cuantificare sunt artate n Fig. 27-13.Fiecare valoarea n spectru este mprit n egal valoarea n tabelul de cuantificare, i rezultatul e rotunjit la cea mai aproape valoare ntreag.. De exemplu, partea de sus-stngaa tabelului de cuantificare este one

Figura27-12.

Exemplu de reconstrucia JPEG.Grupul de pixeli 8x8 de folosit n acest exemplu este ochiul n Fig. 27-9. Dup cum e artat, mai puin dect 1/4 64values sunt necesari pentru realizarea unei aproximaii bune la imaginea corect.

FIGURE 27-13.

Tabelele de cuantificare jpeg. Aceste sunt dou exemple cu tabelele de cuantificare care pot fi ntrebuinate n timpul comprimrii. Fiecare valoare n spectrul DCT este mprit valoarea corespondent n tabelul de cuantificare, i rezultatul e rotunjit la cea mai mic valoare ntreag.

Avnd drept rezultat valoarea DC fiind stng neschimbat. n comparaie, lsai n jos-dreapta intrarea n(b) este 16, nsemnnd acel domeniul original de -127 pentru 127 redus numai la -7 spre 7. n alte cuvinte, valoarea a fost redus n precizie de la opt bii la patru bii. ntr-un caz mai mult exagerat, lsai n jos-dreapta intrarea n( b) este 256, n ntregime eliminnd valoarea spectral..

La pasul patru codificarea JPEG , spectrul modificat este transformat din 8x8 ntr-o succesiune liniar. Modelul erpuit artat n Figura 27-14 se ntrebuineaz pentru acest pas, transfernd toate componentele de frecven nalt mpreun la sfritul succesiunii liniare. Aceasta grupeaz zerourile de la componentele eliminate n tirajele mari. Pasul al cincilea compreseaz aceste rulri de zerouri cu codificarea rulare-lungime.

n al aselea pas, succesiunea este cifrat cu Huffman sau cu codificarea aritmetica ca s formeze fiierul final compresat.

Cantitatea de comprimare, i rezultatul pierderii de calitatea a imaginii, poate fi selectat cnd programul de comprimare JPEG este rulat. Figura 27-15 arat tipul de contorsiunea de imagine rezultnd din coeficienii de compresie nali. Cu 45: 1 este artat coeficientului de compresie , fiecare 8x8 grup este reprezentat doar aproximativ 12 bii.

nchiderea inspeciei acestei imagini arat c ase din cele mai sczute funcii de baz de frecven sunt reprezentate la cteva graduri.

Figur 27-14.

Ttransformarea serial JPEG. Un model erpuit obinuit s transforme 8x8 Spectrul DCT ntr-o succesiune liniar de 64 valori. Aceasta pune toate componentelor de frecven nalt mpreun, unde zerourile mulimii s poat fi eficient compresate cu codificarea rulare-lungimea.

FIGURE 27-15.

Exemplu de contorsiunea JPEG. Figura( a)arat imaginea original, n timp ce( b) i( c) arat folosirea coeficienilor de compresie din imagine restaurai of10:1 i 45: 1, respectiv. Coeficientul de compresie nalt folosit n( c) are drept rezultat fiecare 8x8 grup de pixeli fiind reprezentat cu mai puin dect 12 bits.

De ce DCT e mai bun dect transformarea Fourier pentru comprimarea imaginii? Motivul principal este c DCT are o jumtate din funciile de baz de ciclu, adica. S[0,1] si S [1,0]. Dup cum e artat n Fig. 27-10, acetea cu grij se nclin de la o parte matricii la alta.Comparativ cu cele mai sczute frecvene n Fourier pentru transformarea zonecomplete cycle Imaginea aproape ntotdeauna conine regiunile unde strlucirea schimb treptat o regiune. Folosind o baz funcionnd acele chibrite acest un model de model de baz permite pentru totdeauna comprimarea.

Mpeg

MPEG este un standard de comprimare pentru succesiunile de videoclip digitale, ca de exemplu folosite n videoclipul de calculator i televiziunea reelelor digitale. n plus, MPEG de asemenea ntreine comprimarea pistei sonore asociate cu video. Numele vine de la organizaia, Moving Pictures Experts Group. Dac dvs credei c JPEG este complicat, MPEG este un comar! MPEG este ceva ce dvs cumprai, nu ncercai s scriei dvs niv.

Viitorul acestei tehnologii urmeaz s codifice comprimarea i algoritmii decomprimare direct n rscheme de circuite. Poteniale de MPEG snt imense. Gndii-v la miilee de canalele naturale video puse pe o singur fibr optic ntlnit n casa dvs. Aceasta este o tehnologie chee a secolului 21.

n plus pentru a reduce ritmul de informaie, MPEG are cteva caracteristici importante. Filmul poate s fie jucat nainte sau invers, i la vitey normal sau rapid.

Informaia cifrat este accesat aleator, adic, orice cadru independent n succesiune poate fi cu uurin afiat ca imagine staionar. Acestea mpreun formnd filmul editable, nsemnnd acele segmente scurte a filmului s poat fi cifrat numai n legtur cu ei nii, succesiunea ntreag. MPEG nu este proiectat s fie robust la erori. Ultimul lucru, dvs vrei s nlocuiasc o eroare de bii pentru a cauza o separare a filmului.

Accesul folosit de MPEG poate fi mprit n dou tipuri de comprimare: n-cadrul i ntre-cadre, n-cadrul comprimarea nseamn c succesiunile de cadru independente video sunt cifrate ca i cum ele au fost imagini staionare obinuite. Aceast comprimare este folosit de tablele stindardului JPEG, cu variaiile corecte de afew. n terminologia MPEG, structura care a fost codificat n aa mod se numete intra-codificate sau I-picture.

Cei mai muli pixeli ntr-o succesiune video se schimbe foarte puin de la un cadru la urmtorul. Cu excepia aparatului de fotografiat, multe fotografii snt formate din fundal care rmine constant peste duzinele de cadre. MPEG utilizeaz aceasta cu un formular sofisticat de delta codificare s compreseze informaia inutil ntre cadre. Dup ce compresnd unele dintre cadre ca I-picture, MPEG cifreaz cadrele succesive pe msura ce profetice-codificate sau Ppictures.n aa mod, doar punctele care s-au schimbat ncepnd cu I-picture sunt incluse n P-picture.

n timp ce aceste duo schme de comprimare formeaz baza MPEG, real este mult mai sofisticat dect e descris aici. De exemplu, la P-picture poate fi facut referin de la I-picture care a fost schimbat, justificnd micare de obiecte n succesiunea de imagine. Exist de asemenea bidirecionala predictve-cod sau B-pictures. Acestea sunt referitoare la ambele anterioare i viitoare I-picture.

Aceasta s erefer la regiunile din imagine care treptat i schimb mult din structur. Cadrele independente pot fi de asemenea coninute n afara-de-ordine n informaiile compresate ca s uureze succesiunea corespunztoare I, P, i B-pictures. Adugarea de culoare i sunet face acest tot mult mai complicat.

Contorsiunea principal asociat cu MPEG se ntmpl cnd prile imaginii se schimb repede. n efect, o exlotare a informaie e necesar, pentru ca s nu rmn n urma schimbrii rapeide a secnelor. Dac norma informaiei e fixat, apectatorii pot vizualiza" blocky" modele cnd are loc schimbarea de la o scen la urmtoarea. Aceasta poate fi minimizat n reele care transmit canalele naturale de videoclip multiple simultan, ca de exemplu cablu de televiziune. Exlpozia neateptat de informaie ar fi trebuit sa in schimbarea rapid a scenelor n unul din video canalul natural, este mediu cu cerinele modeste relativ de scenele statice n alte canale naturale.

PAGE 58