Predavanja VISOKA TEHNIČKA ŠKOLA NIŠ Prof. Mr. Srđan Jovković. - презентация

1 Predavanja VISOKA TEHNIČKA ŠKOLA NIŠ Prof. Mr. Srđan Jovković

2 UVOD zKompresija je redukcija (smanjenje) količine podataka tako da je potrebno manje memorijskog prostora (npr. na disku) za čuvanje i manje propusnog opsega (kapaciteta) u kanalima za prenos informacija. Kompresija se primenjuje svuda, u svim oblastima informatike, telekomunikacija i internet tehnologija. zKompresija telefonskih signala povećava kapacitet zauzetih iznajmljenih linija, dok se kompresijom fajlova (podataka, tekstova, slika) smanjuje zauzeti prostor na diskovima za arhiviranje. zPostoje dva osnovna koncepta kompresije podataka: kompresije bez gubitaka (na engl. lossless); kompresije sa gubicima (na engl. lossy). Kompresija signala i podataka

3 Multipleksiranje signala zKod frekvencijskog multipleksa (Frequencz Division Multiplex - FDM) signali se raspoređuju po frekvencijama tako da svaki signal zauzima svoj opseg frekvencija. Frekvencijski multipleks se primenjuje isključivo na analogne signale. zVremenski multipleks (Time Division Multiplex - TDM) je postupak vremenske raspodele provodnika više signala koji se prenose tim provodnikom, tj. svaki signal dobija svoj kvant vremena i tako u krug. Vremenski multipleks je karakteristika digitalnih signala. Kompresija signala i podataka

4 Kompresija kao ekvivalent neuniformnog kvantovanja zKvantovanje je postupak koji predhodi kodovanju, jer kvantovanjem neizbrojiv skup trenutnih vrednosti svodimo na izbrojiv. zNeuniformno kvantovanje može se ostvariti na tri tehnički prihvatljiva načina: trenutnom kompresijom; digitalnom kompresijom; nelinearnim kodovanjem. Kompresija signala i podataka

5 Trenutna kompresija Kompresija signala i podataka

6 Zakoni trenutne kompresije zPostoje dva kriterijuma za izbor matematičkog zakona koji bi opisao najoptimalniju karakteristiku kompresije za određene telekomunikacione signale: kriterijum konstantnosti odnosa signal – šum kvantovanja bez obzira na statičke osobine signala; kriterijum maksimiranja odnosa signal – šum kvantovanja za zadatu statistiku signala. Kompresija signala i podataka

7 Zakoni trenutne kompresije zPostoje dve dobre modifikacije logaritamskog zakona kompresije: semilogaritamski zakon; kvazilogaritamski zakon. Kvazilogaritamska karakteristika kompresije Semilogaritamska karakteristika kompresije Prava logaritamska karakteristika kompresije Kompresija signala i podataka

8 Princip digitalnog kompandovanja Primer jedne kodne reči na ulazu u digitalni kompresor Princip digitalnog kompandovanja Kompresija signala i podataka Cilj kompandovanja je da se obezbedi fino kvantovanje malih trenutnih vrednosti signala, dopuštajući grubo kvantovanje velikih a retkih trenutnih vrednosti.

9 Hafmanov kod zHafmanov algoritam nastao je kao rezultat seminarskog rada diplomca Masačusetskog instituta tehnologije (MIT) Davida Huffmana. z Hafmanov kod se bazira na redudansi po kojoj se određeni karakteri češće javljaju od ostalih. Kompresija se bazira na: koriste se kraći uzorci bitova za češće korišćena slova i duži za ona koja se ne koriste često. zU okviru prenosa uvek znamo gde se jedan karakter završava i gde sledeći počinje. Hafmanovi kodovi poznati su kao no – prefix, a to znači da kod jednog karaktera nikada ne može da se koristi kao prefiks drugog koda. zHafmanovi kodovi redukuju broj bitova koji se šalju, ali je kod njih neophodno znati vrednost učestanosti pojavljivanja. Kompresija signala i podataka

10 Run – Length kodiranje zRun – length kodiranje koristi jednostavan i očigledan koncept: niz bitova se analizira da bi se pronašli dugački nizovi nula ili jedinica. Umesto svih bitova, šalje se samo njihov broj u nizu. Nizovi istog bita Ovaj pristup podrazumeva slanje dužine svakog niza u vidu binarno izraženog celog broja fiksne dužine. Prijemni uređaj prihvata dužinu svakog niza i generiše odgovarajući broj bitova u nizu, umećući drugi bit između tih nizova zNizovi sa različitim karakterima U slučajevima kada postoje nizovi različitih bitova ili karaktera šalje se konkretni karakter zajedno sa dužinom njegovog niza. Kompresija signala i podataka

11 Relativno kodiranje zTipični televizijski signal šalje 30 slika u sekundi. Utvrđuju se razlike u svakom sledećem kadru u odnosu na predhodni. Kodiranje tih informacija i njihovo slanje ima potencijala kada su razlike male. Ovaj metod naziva se relativno ili diferencijalno kodiranje. zPoenta je u tome da poslati okvir sadrži dugačke nizove 0, tako da predstavlja dobrog kandidata za primenu run – length kodiranja. Kompresija signala i podataka

12 Lempel – Ziv kompresija zMetod Lempel – Ziv kompresije traži stringove koji se često ponavljaju i smešta ih samo jednom. Ovo je jedan od osnovnih principa za upravljanje bazama podataka: jedan deo informacija se smešta samo na jednom mestu i referencira se kroz specijalne kodove. zKod dužeg teksta i većeg broja ponavljanja kompresija se poboljšava. Značajna karakteristika ovog metoda je da ne postoje nikakve predpostavke kako izgleda string koji se ponavlja, što algoritam čini robusnim i dinamičnim. Kompresija signala i podataka

13 Kompresija slika zIako prenos slika na prvi pogled može da deluje kao samo mali korak u odnosu na prenos reči i rečenica, multimedijalne aplikacije jednostavno ne bi bile izvodljive bez nekih veoma sofisticiranih algoritama kompresije. zSlike, bilo da je reč o fotografijama ili slikama generisanim na kompjuterskom ekranu, sačinjene su od velikog broja veoma malih tačaka. Ove tačke se nazivaju još i elementi slike ili piksel. zVideo tehnologija se zasniva na činjenici da se svaka boja ljudskom oku može predstaviti pomoću prikladne kombinacije osnovnih boja crvene, zelene i plave (RGB). Kompresija signala i podataka

14 JPEG kompresija Kod JPEG kompresije postoje gubici: slika koja se dobija nakon dekompresije ne mora da bude identična originalnoj. zDCT je funkcija koja uzima dvodimenzionalni niz sa osam redova i kolona i kreira drugi dvodimenzionalni niz, takođe sa osam redova i kolona. zOna definiše još jedan dvodimenzionalni niz (neka se zove Q) koji se dobija deljenjem vrednosti niza T nekim brojem, pa zaokruživanjem na najbliži celi broj. zKompresija se izvodi u fazi kodiranja. Sa svim nulama koje se javljaju, možemo da koristimo run – length kodiranje. Tri faze JPEG kompresije Kompresija signala i podataka

15 MPEG zGrupa koja definiše standarde za video kompresiju je Moving Pictures Expert Group (MPEG). zMPEG – 1 bio je dizajniran za video i rane direktne satelitske sisteme za emitovanje. zMPEG – 2 korišćen je za složenije aplikacije, kao što su multimedijalna okruženja i high – definition televizija (HDTV), a usvojen je i u satelitskim prenosima. zMPEG – 4 namenjen je za video konferencije preko kanala sa niskim opsegom. zMPEG – 7 je standard koji treba da podrži široki spektar aplikacija, a zasniva se na pretpostavci da bi multimedijalni podaci mogli da zauzmu sve veći deo propusnog opsega signala u toku ovog veka. Kompresija signala i podataka

16 MP3 zMP3 je protokol za kompresovanje audio zapisa. zMP3 je usvojen kao standard godine. zNajveći deo onoga što je dizajnirano u MP3 zasniva se na psihoakustičnom modelu. zOsnovna ideja na kojoj se MP3 zasniva je da se hvata audio signal, utvrđuje se šta ne može da se čuje, uklanjaju se te komponente iz audio zapisa i vrši se digitalizacija preostalog dela signala, odnosno uklanja se sve što ne može da se čuje. Kompresija signala i podataka MP3 kodiranje

17 ZAKLJUČAK zKompresija se primenjuje svuda, u svim oblastima informatike, telekomunikacija i internet tehnologija. Postoje dva osnovna koncepta kompresije podataka: - kompresije bez gubitaka (na engl. lossless); - kompresije sa gubicima (na engl. lossy). zIdealna karakteristika kompresije mora da bude prilagođena da sve trenutne vrednosti kompromitovanog signala postanu podjednako verovatne u celom amplitudskom opsegu uniformnog kvantizera. zKod run – length kodiranja kompresija se postiže traženjem dugačkih nizova istog karaktera ili bita. zOsnovna ideja na kojoj se MP3 zasniva je da se hvata audio signal, utvrđuje se šta ne može da se čuje, uklanjaju se te komponente iz audio zapisa i vrši se digitalizacija preostalog dela signala, odnosno uklanja se sve što ne može da se čuje. Kompresija signala i podataka