ALGORITEM STISKANJA PRI PNG

Poizvedi, kako stiskamo PNG datoteke in kakšen algoritem stiskanja je pri tem uporabljen.

Proces stiskanja pri PNG je brez izgub, kar pomeni, da algoritem stiskanja zmanjša velikost datoteke tako, da pri tem ne izgubimo nobenih podatkov. Torej lahko nazaj iz stisnjene datoteke rekonstruiramo izvorno datoteko (Fox, b.d.).

Proces stiskanja pri PNG poteka v dveh fazah (McAnlis, 2016):

  • prva je faza FILTRIRANJA
  • druga pa faza STISKANJA

1. FILTRIRANJE

Filtriranje je postopek transformacije podatkov neke slike, tako da algoritem stiskanja/kodiranja deluje bolj učinkovito. S predhodnim filtriranjem tako PNG format skuša ustvariti enake podatke iz različnih podatkov.

Podatke lahko filtriramo na pet različnih načinov. Prav tako lahko za vsako vrstico slikovnih točk (pikslov) uporabimo drug filter. Za to poskrbi algoritem v PNG, ki mora ugotoviti, kateri filter je najboljši za katero vrstico, da dobimo čim več enakih podatkov. Načini filtriranja so predstavljeni v spodnji tabeli (Chapter 9. Compression and Filtering, b.d.; McAnlis, 2016):

FILTER OPIS
NONEVsak bajt je nespremenjen.
SUBVsak bajt se nadomesti z razliko med njim in bajtom na njegovi levi (upošteva se bajt pred filtriranjem).
UPVsak bajt se nadomesti z razliko med njim in bajtom nad njim (upošteva se bajt pred filtriranjem).
AVERAGEVsak bajt se nadomesti z razliko med njim in povprečno vrednostjo bajtov levo in nad njim (upoštevata se bajta pred filtriranjem).
PAETHPosebna metoda, kjer se vsak bajt nadomesti z razliko med njim in ustreznim »napovednim bajtom«, ki pa ga dobimo iz bajta na njegovi levi, na njegovi zgornji levi ter nad njim (upoštevajo se bajti pred filtriranjem).

Metoda Paeth potrebuje malo več pojasnitve. Najprej moramo  izračunati osnovno vrednost. Dobimo jo tako, da najprej izračunamo vsoto bajtov levo ter nad njim, nato pa odštejemo bajt levo zgoraj. Potem izračunamo razlike med osnovno vrednostjo in vsakim od teh treh bajtov. Bajt, s katerim dobimo najmanjšo absolutno razliko, predstavlja »napovedni bajt«.

Kaj pa, če bajt levo, zgoraj ali pa zgoraj levo ne obstaja? Potem ta manjkajoči bajt obravnavamo, kot da je enak 0.

PREVERI SVOJE ZNANJE

Najpomembnejše pri filtriranju je to, da filtriranje deluje na bajte in ne na slikovne točke. Pri slikah s slikovnimi točkami, manjšimi od osmih bitov, to pomeni, da filtriranje deluje na več kot eno slikovno točko hkrati (Chapter 9. Compression and Filtering, b.d.; McAnlis, 2016).

Za lažje razumevanje procesa filtriranja si poglej posnetek na desni, kjer je prikazano filtriranje druge vrstice slikovnih točk z vsemi petimi načini filtriranja.

PREVERI SVOJE ZNANJE

Uporabi vseh 5 filtrov na spodnjem primeru. Filtriraj samo 2. vrstico. Pravilne odgovore poišči spodaj med vsemi danimi odgovori.

 

52   63   57   48   60

75   59   64   80   113

2. ALGORITEM STISKANJA

Algoritem stiskanja pri PNG se imenuje DEFLATE algoritem, ki pa je kombinacija Huffmanovega kodiranja in LZ77 kodiranja. Značilnosti tega algoritma so visoka zanesljivost, dobra kompresija, hitro kodiranje ter še hitrejše dekodiranje. Oblika stisnjenih podatkov je sestavljena iz niza blokov, vsak blok pa je stisnjen s kombinacijo LZ77 algoritma in Huffmanovega kodiranja (Erdmann, 2017; Kirthi, Oswal in Singh, 2016).

HUFFMANOVO KODIRANJE

Algoritem vsakemu simbolu dodeli vozlišče binarnega drevesa. Ta vozlišča so razporejena glede na število pojavitev nekega simbola. Struktura drevesa je rezultat dodajanja vozlišč po korakih, dokler niso vsa vdelana v drevo. Veje drevesa predstavljajo binarni vrednosti 0 in 1, pot od vrha drevesa do željenega vozlišča določa posamezno kodno besedo. Algoritem pri Huffmanovem kodiranju vzame dve vozlišči, ki sta najnižje v drevesu (najnižja frekvenca pojavitev simbolov), in ju združi. Nova vozlišča dobijo vsoto frekvenc teh dveh vozlišč (Kirthi, Oswal in Singh, 2016).

2.1 ALGORITEM LZ77

Algoritem, ki temelji na slovarju in poskuša najti ponavljajoča se zaporedja podatkov/simbolov. Vsi podatki so kodirani v isti obliki – trojica [razdalja, dolžina, prvi odstopajoči simbol]. Razdalja pove, koliko korakov nazaj se ujemajoče zaporedje simbolov nahaja, dolžina, kako dolgo je to zaporedje, prvi odstopajoči simbol pa je prvi simbol v nizu podatkov, ki ga še nimamo v slovarju. Ko v nizu podatkov naletimo na nek nov simbol, zapišemo trojico [0, 0, »nov simbol«] (Kirthi, Oswal in Singh, 2016).

V tabeli spodaj je predstavljen primer, kako iz niza ABRAKADABRAA dobimo trojice, s katerimi potem zapišemo ta niz, oziroma na splošno, s katerimi so kodirani podatki datoteke.

Za lažje razumevanje lahko pritisneš gumbe v tabeli in pokazala se bo razlaga primera. 

Trojice: [0, 0, A], [0, 0, B], [0, 0, R], [3, 1, K], [2, 1, D], [7, 4, A].

Ker je vsako zaporedje bajtov podaljšano z novim simbolom, ki se razlikuje od prejšnjih, se nabor že uporabljenih simbolov nenehno povečuje.

Pa se vrnimo nazaj k DEFLATE algoritmu.

Algoritem Deflate poskuša najti ponavljajoča se zaporedja podatkov. Če algoritem naleti na zaporedje podatkov, ki se je že pojavilo, ga nadomesti s sklicem na prvo zaporedje v obliki para (razdalja, dolžina). Razdalja pove, koliko korakov nazaj se to zaporedje nahaja, dolžina pa kako dolgo je. Razdalje so omejene na 32 kB, dolžine pa na 256 B.

Dolžine ujemajočega zaporedja podatkov so stisnjene z enim Huffmanovim drevesom, razdalje zaporedja pa z drugim. Drevesa so shranjena na začetku vsakega bloka. Posamezen blok se zaključi, ko Deflate algoritem presodi, da bi bilo koristno začeti nov blok z novimi drevesi.

Podvojena zaporedja najdemo s pomočjo »hash« tabele. Vsa vhodna zaporedja dolžine 3 so vstavljena v »hash« tabelo. Izračuna se »hash« indeks za naslednje tri bajte. Če niz »hash« za ta indeks ni prazen, se vsa zaporedja v nizu primerjajo z vhodnim zaporedjem in je izbrano najdaljše zaporedje ujemanj. Ti nizi se iščejo začenši z nazadnje dodanimi, da pa se prednost manjšim razdaljam in tako se izkoristi Huffmanovo kodiranje. Vsi »hash« nizi so med seboj povezani. Iz teh nizov se nič ne briše, algoritem preprosto zavrže ujemanja, ki so prestara.

Deflate algoritem se prav tako podredi izbiri ujemanj s tako imenovanim »lenim ocenjevalnim mehanizmom«. Ko najde ujemanje dolžine N, začne z iskanjem daljšega ujemanja z naslednjim bajtom. Če ga najde, se dolžina prejšnjega ujemanja zmanjša za 1 in proces »lenega ocenjevanja« se ponovno začne. V nasprotnem primeru se obdrži prvotno ujemanje, naslednje iskanje ujemanja pa se izvede N korakov za tem.

Deflate algoritem pa tukaj poskrbi tudi za čas iskanja. Če je trenutno ujemanje dovolj dolgo, algoritem zmanjša iskanje daljšega ujemanja, kar pospeši celoten postopek stiskanja. Seveda, če je razmerje stiskanja pomembnejše od hitrosti, se algoritem loti celotnega drugega iskanja, tudi če je prvo ujemanje že dovolj dolgo (Kirthi, Oswal in Singh, 2016).

VIRI