JPEG. Algoritam kompresije

Ponovo zdravo! PronaÅ”ao sam ovu članak napisanu u maju 2019. godine. Ovo je nastavak serije članaka o WAVE i JPEG, ovde prvi. Ova objava će sadržati informacije o algoritmu kodiranja slika i o formatu u celini.

Malo istorije

KaŔika informacija iz Vikipedije:

JPEG (Joint Photographic Experts Group) je jedan od popularnih bitmap formata koji se koristi za skladiŔtenje fotografija i sličnih slika.

Ovaj standard razvila je Međunarodna grupa eksperata za fotografiju 1991. godine za efikasno kompresovanje slika.

Kakav put prolaze slike od sirovog stanja do JPEG-a

Neki smatraju da su JPEG slike kompresovani Huffmanovom metodom sirovi podaci, ali to nije tačno. Pre kontrolnog kompresovanja, podaci prolaze dug put.

Prvo, promena color modela se vrÅ”i sa RGB na YCbCr. Za to postoji specijalni algoritam — ovde. Y se ne dira, jer se brine o osvetljenju, i njena promena će biti uočljiva.

Prvo Å”to se radi sa slikom je ā€žsubsamplingā€œ (subsampling). Ovo je lako razumeti: uzima se 2x2 matrica piksela, zatim se uzimaju Cb i Cr — prosečne vrednosti svake od komponenti YCbCr ovih 4 pixela. I tako, dobijamo 6 bajtova, umesto 4 Y, 4 Cb, 4 Cr dobijamo 4 Y i iste za svaku od njih Cb i Cr (4 + 4 + 4 = 12; 4 + 1 + 1 = 6; 12 — 6 = 6). U sklopu čak 2x2 kompresija sa gubitkom koeficijenta 2:1 zvuči značajno. Ovo se primenjuje na celoj slici. I tako smo smanjili veličinu za pola. A ovu tehniku možemo iskoristiti zahvaljujući naÅ”em vidu boja. Čovek lako primeti razliku u osvetljenju, ali ne u boji, ako je prosečna u malom bloku piksela. Takođe, subsampling se može izvesti u redu, 4 piksela horizontalno i vertikalno. Prva opcija se koristi čeŔće. Ako je kvalitet slike važan, subsampling se uopÅ”te ne vrÅ”i.
Jasna ilustracija subsamplinga (Habr nije dozvolio umetanje gif-a) — https://i.ibb.co/Rg5Th9H/150953010617579181.gif

Glavni deo pripreme

DCT

Sada najteži i najvažniji deo. Cela slika se deli na blokove 8x8 (koristi se popunjavanje u slučaju da rezolucija nije deljiva sa stranicom bloka).

Sada se svaki blok primenjuje DCT (Diskretno kosinusno transformisanje). U ovom delu slike uklanjaju se svi suviÅ”ni delovi. Koristeći DCT, treba shvatiti opisuje li ovaj blok (8Ɨ8) neku monotonu povrÅ”inu slike: nebo, zid; ili sadrži kompleksnu strukturu (kose, simbole itd.). Logično je da 64 piksela slične boje mogu da budu opisani samo jednim, jer je veličina bloka već poznata. I evo kompresije: 64 prema 1.

DCT pretvara blok u spektar, i gde se očitavanja naglo menjaju, koeficijent postaje pozitivan, a Å”to je nagla promena, to će izlaz biti viÅ”i. Tamo gde je koeficijent viÅ”i, na slici su jasni prelazi u boji i svetlosti, gde je niži — slabi (gladki) prelazi komponenti YCbCr u bloku.

Kvantanizacija

Ovdje se već primenjuju postavke kompresije. Svaki od koeficijenata u svakoj od 8Ɨ8 matrica deli se sa određenim brojem. Ako nećete viÅ”e smanjivati kvalitet slike nakon svih modifikacija, delilac treba da bude jedan. Ako vam je važnija memorija koju zauzima ova fotografija, delilac će biti veći od 1, i rezultat se zaokružuje. Tako često nakon zaokruživanja dobijemo mnogo nula.

Kvantanizacija se radi kako bi se omogućila joÅ” veća kompresija. Ovako to izgleda na primeru kvantanizacije grafika y = sin(x):

JPEG. Algoritam kompresije

Kompresija

Prvo prolazimo kroz matricu u obliku zig-zag:

JPEG. Algoritam kompresije

Dobijamo jednostrani niz sa brojevima. Vidimo da u njemu ima mnogo nula, koje možemo ukloniti. Za ovo umesto niza sa mnogo nula upisujemo 1 nulu, a posle nje broj koji označava njihovu količinu u nizu. Tako možemo smanjiti na 1/3 veličine celog niza. A zatim jednostavno kompresujemo ovaj niz metodom Huffman i upisujemo ga u fajl.

Gde se koristi

Svuda. Kao i PNG, JPEG se koristi u fotoaparatima, operativnim sistemima (kao logotipi kompanija, ikone aplikacija, sličice) i u svim oblastima gde je potrebno efikasno skladiŔtenje slika.

Zaključak

Trenutno su znanja o JPEG-u vredna samo u obrazovne svrhe, jer je već svuda ugrađen i optimizovan od strane velikih grupa ljudi, ali kamen nauke je i dalje ukusan.

Izvori

Članak o YCbCr na Vikipediji
Članak o JPEG na Vikipediji
Malo o DCT-u iz posta Pikabu
Članak o DCT na Vikipediji

Izvor: habr.com

Kupite pouzdan hosting za sajtove uz zaÅ”titu od DDoS, VPS VDS servere šŸ”„ Kupite pouzdan hosting za sajtove uz zaÅ”titu od DDoS, VPS VDS servere | ProHoster