Lako je izračunati da će nekomprimirana slika u punoj boji veličine 2000 * 1000 piksela imati veličinu od oko 6 megabajta. Ako govorimo o slikama dobivenim profesionalnim kamerama ili skenerima visoka rezolucija, onda njihova veličina može biti čak i veća. Unatoč brzom rastu kapaciteta uređaja za pohranu podataka, različiti algoritmi za kompresiju slike i dalje su vrlo relevantni.
Svi postojeći algoritmi mogu se podijeliti u dvije velike klase:
- Algoritmi kompresije bez gubitaka;
- Algoritmi kompresije s gubitkom.
Algoritmi kompresije bez gubitaka
RLE algoritam
Svi algoritmi serije RLE temelje se na vrlo jednostavnoj ideji: grupe elemenata koje se ponavljaju zamjenjuju se parom (broj ponavljanja, element koji se ponavlja). Razmotrimo ovaj algoritam na primjeru niza bitova. Ovaj niz će izmjenjivati grupe nula i jedinica. Štoviše, grupe će često imati više od jednog elementa. Tada će niz 11111 000000 11111111 00 odgovarati sljedećem skupu brojeva 5 6 8 2. Ovi brojevi označavaju broj ponavljanja (brojenje počinje od jedinica), ali te brojeve također treba kodirati. Pretpostavit ćemo da je broj ponavljanja u rasponu od 0 do 7 (odnosno, 3 bita su nam dovoljna da kodiramo broj ponavljanja). Tada je slijed o kojem se gore raspravljalo kodiran sljedećim nizom brojeva 5 6 7 0 1 2. Lako je izračunati da kodiranje izvornog niza zahtijeva 21 bit, au RLE komprimiranom obliku ovaj niz uzima 18 bita.Iako je ovaj algoritam vrlo jednostavan, njegova učinkovitost je relativno niska. Štoviše, u nekim slučajevima korištenje ovog algoritma ne dovodi do smanjenja, već do povećanja duljine niza. Na primjer, razmotrite sljedeći niz 111 0000 11111111 00. Odgovarajući RL niz izgleda ovako: 3 4 7 0 1 2. Dužina originalnog niza je 17 bita, duljina komprimiranog niza je 18 bita.
Ovaj je algoritam najučinkovitiji za crno-bijele slike. Također se često koristi kao jedan od međufaza kompresije složenijih algoritama.
Rječnički algoritmi
Ideja iza rječničkih algoritama je da su lanci elemenata izvornog niza kodirani. Ovo kodiranje koristi poseban rječnik, koji se dobiva na temelju izvornog niza.Postoji cijela obitelj rječničkih algoritama, ali mi ćemo se osvrnuti na najčešće LZW algoritam, nazvan po svojim programerima Lepel, Ziv i Welch.
Rječnik u ovom algoritmu je tablica koja se puni lancima kodiranja dok algoritam radi. Kada se komprimirani kod dekodira, rječnik se automatski vraća, tako da nema potrebe za prijenosom rječnika zajedno sa komprimiranim kodom.
Rječnik se inicijalizira sa svim pojedinačnim nizovima, tj. prvi redovi rječnika predstavljaju abecedu kojom kodiramo. Tijekom kompresije traži se najduži lanac koji je već zabilježen u rječniku. Svaki put kada se naiđe na lanac koji još nije upisan u rječnik, on se tamo dodaje, a izlazi komprimirani kod koji odgovara lancu koji je već upisan u rječnik. U teoriji nema ograničenja na veličinu rječnika, ali u praksi ima smisla ograničiti ovu veličinu, jer se s vremenom počinju pojavljivati lanci koji se više ne nalaze u tekstu. Osim toga, kada udvostručimo veličinu tablice, moramo dodijeliti dodatni bit za pohranu komprimiranih kodova. Kako bi se takve situacije spriječile uvodi se poseban kod, simbolizirajući inicijalizaciju tablice sa svim pojedinačnim lancima.
Pogledajmo primjer algoritma kompresije. Komprimirati ćemo liniju cuckoocuckoococoohood. Pretpostavimo da će rječnik sadržavati 32 mjesta, što znači da će svaki njegov kod zauzimati 5 bita. U početku se rječnik popunjava na sljedeći način:
Ta tablica postoji i na strani onoga tko komprimira informaciju i na strani onoga tko je dekompresira. Sada ćemo pogledati proces kompresije. 
U tablici je prikazan postupak popunjavanja rječnika. Lako je izračunati da rezultirajući komprimirani kod zauzima 105 bita, a izvorni tekst (pod pretpostavkom da potrošimo 4 bita na kodiranje jednog znaka) ima 116 bita.
U biti, proces dekodiranja se svodi na direktno dekodiranje kodova, a važno je da se tablica inicijalizira na isti način kao i kod kodiranja. Sada pogledajmo algoritam dekodiranja. 
Niz dodan rječniku u i-tom koraku možemo u potpunosti definirati samo na i+1. Očito, i-ti red mora završiti prvim znakom i+1 retka. Da. Upravo smo shvatili kako vratiti rječnik. Zanimljiva je situacija kada je kodirana sekvenca oblika cScSc, gdje je c jedan znak, a S niz, a riječ cS je već u rječniku. Na prvi pogled može se činiti da dekoder neće moći riješiti ovu situaciju, ali zapravo sve linije ove vrste moraju uvijek završavati istim znakom kojim počinju.
Statistički algoritmi kodiranja
Algoritmi u ovoj seriji dodjeljuju najkraći komprimirani kod najčešćim elementima sekvenci. Oni. nizovi iste duljine kodirani su komprimiranim kodovima različitih duljina. Štoviše, što se niz češće pojavljuje, to je odgovarajući komprimirani kod kraći.Huffmanov algoritam
Huffmanov algoritam omogućuje vam konstruiranje prefiks kodova. Možete zamisliti prefiks kodove kao staze do binarno stablo: prijelaz od čvora do njegovog lijevog djeteta odgovara 0 u kodu, a njegovom desnom djetetu odgovara 1. Ako lišće stabla označimo simbolima koje treba kodirati, dobivamo binarnu reprezentaciju stabla kod prefiksa.Opišimo algoritam za konstruiranje Huffmanovog stabla i dobivanje Huffmanovih kodova.
- Znakovi ulazne abecede tvore listu slobodnih čvorova. Svaki list ima težinu koja jednako frekvenciji izgled simbola
- Odabrana su dva slobodna čvora stabla s najmanjim težinama
- Njihov roditelj je stvoren s težinom jednakom njihovoj ukupnoj težini
- Roditelj se dodaje na popis slobodnih čvorova, a njegova dva djeteta se uklanjaju s ovog popisa
- Jednom luku koji napušta roditelj se dodjeljuje bit 1, drugom se dodjeljuje bit 0
- Koraci počevši od drugog ponavljaju se sve dok na popisu slobodnih čvorova ne ostane samo jedan slobodni čvor. Ovo će se smatrati korijenom stabla.
Aritmetičko kodiranje
Algoritmi aritmetičkog kodiranja kodiraju nizove elemenata u razlomak. U ovom slučaju uzima se u obzir frekvencijska distribucija elemenata. Trenutno su algoritmi aritmetičkog kodiranja zaštićeni patentima, pa ćemo se osvrnuti samo na osnovnu ideju.Neka se naša abeceda sastoji od N simbola a1,...,aN i njihove učestalosti pojavljivanja p1,...,pN. Podijelimo poluinterval; predstavljamo implementaciju paralelizacije svih faza JPEG algoritam koristeći CUDA tehnologiju, koja je značajno ubrzala performanse JPEG kompresije i dekodiranja.
U 2010. godini znanstvenici iz projekta PLANETS stavili su upute za čitanje JPEG formata u posebnu kapsulu, koja je smještena u posebnom bunkeru u švicarskim Alpama. To je učinjeno s ciljem očuvanja informacija o digitalnim formatima popularnim početkom 21. stoljeća za potomke.
vidi također
Bilješke
Linkovi
- JFIF specifikacija 1.02 (tekstualna datoteka)
- JPEG optimizacija. 1. dio, 2. dio, 3. dio.
(izgovara se "japeg" Joint Photographic Experts Group, prema nazivu razvojne organizacije) jedan je od popularnih grafičkih formata koji se koristi za pohranjivanje fotografija i sličnih slika. Datoteke koje sadrže JPEG podaci, obično imaju ekstenzije .jpeg, .jfif, .jpg, .JPG ili .JPE. Međutim, od ovih, .jpg je najpopularnije proširenje na svim platformama.
1. Zajednička skupina stručnjaka iz područja fotografije;
2. Metoda kompresije slike koju je razvila ova grupa i odgovarajući grafički format, koji se često koristi na WWW-u. Karakterizira kompaktnost datoteka i, prema tome, brz prijenos, kao i “gubitak” kvalitete slike. Koristi se prvenstveno za fotografije, jer je za njih gubitak kvalitete manje kritičan. Pohranjuje parametre boja u RGB modelu boja.
JPEG(izgovara se " jpeg", Engleski Zajednička skupina stručnjaka za fotografiju, po nazivu razvojne organizacije) jedan je od popularnih grafičkih formata koji se koristi za pohranu fotografija i sličnih slika. Datoteke koje sadrže JPEG podatke obično imaju nastavak .jpeg, .jfif, .jpg, .JPG, ili .JPE. Međutim, od ovih .jpg najpopularnije proširenje na svim platformama. Vrsta MIME je slika/jpeg.
JPEG algoritam je algoritam za kompresiju podataka s gubitkom.
Područje primjene
JPEG algoritam je najprikladniji za komprimiranje fotografija i slika koje sadrže realistične scene glatke prijelaze svjetlinu i boju. JPEG je najrasprostranjeniji u digitalna fotografija te za pohranjivanje i prijenos slika putem Interneta.
S druge strane, JPEG nije prikladan za komprimiranje crteža, teksta i grafike znakova, gdje oštar kontrast između susjednih piksela dovodi do vidljivih artefakata. Preporučljivo je pohraniti takve slike u formatima bez gubitaka kao što su TIFF, GIF, PNG ili RAW.
JPEG (kao i druge metode kompresije izobličenja) nije prikladan za komprimiranje slika tijekom višestupanjske obrade, jer će se izobličenja unijeti u slike svaki put kada se spremaju međurezultati obrade.
JPEG se ne smije koristiti u slučajevima kada su čak i minimalni gubici neprihvatljivi, na primjer, kod kompresije astronomskih ili medicinskih slika. U takvim slučajevima može se preporučiti način kompresije JPEG bez gubitaka koji nudi standard JPEG (koji nažalost nije podržan od strane većine popularnih kodeka) ili standard kompresije JPEG-LS.
Kompresija
Kada se komprimira, slika se pretvara iz prostor boja RGB u YCbCr (YUV). Treba napomenuti da standard JPEG (ISO/IEC 10918-1) ni na koji način ne regulira izbor YCbCr, dopuštajući druge vrste pretvorbe (na primjer, s brojem komponenti osim tri) i kompresiju bez pretvorbe (izravno na RGB), ali specifikacija JFIF (JPEG Format za razmjenu datoteka, koji su 1991. godine predložili stručnjaci iz C-Cube Microsystemsa, a koji je sada postao de facto standard) uključuje korištenje RGB->YCbCr pretvorbe.
Nakon RGB->YCbCr konverzije, može se izvršiti "poduzorkovanje" za kanale slike Cb i Cr, koji su odgovorni za boju, što se sastoji od dodjele prosječnih vrijednosti Cb i Cr (shema stanjivanja "4:2:0" ). Štoviše, za svaki 2x2 blok, umjesto 12 vrijednosti (4 Y, 4 Cb i 4 Cr), koristi se samo 6 (4 Y i po jedna prosječna Cb i Cr). Ako se postavljaju povećani zahtjevi za kvalitetu slike obnovljene nakon kompresije, stanjivanje se može izvesti samo u jednom smjeru - okomito (shema "4:4:0") ili vodoravno ("4:2:2"), ili se ne izvodi uopće (“4:4:4”).
Standard također dopušta decimaciju s usrednjavanjem Cb i Cr ne za blok 2x2, već za četiri piksela smještena sekvencijalno (okomito ili vodoravno), odnosno za blokove 1x4, 4x1 (shema "4:1:1"), kao i kao 2x4 i 4x2. Također je moguće koristiti različite vrste stanjivanje za Cb i Cr, ali u praksi se takve sheme koriste izuzetno rijetko.
Zatim se komponenta svjetline Y i komponente boje Cb i Cr dijele na blokove od 8x8 piksela. Svaki takav blok podvrgava se diskretnoj kosinusnoj transformaciji (DCT). Rezultirajući DCT koeficijenti su kvantizirani (općenito, različite kvantizacijske matrice se koriste za Y, Cb i Cr) i pakirani pomoću Huffmanovih kodova. JPEG standard također dopušta korištenje mnogo učinkovitijeg aritmetičkog kodiranja, međutim, zbog patentnih ograničenja (patent za aritmetički QM koder opisan u JPEG standardu pripada IBM-u), ne koristi se u praksi.
Matrice koje se koriste za kvantiziranje DCT koeficijenata pohranjene su u dijelu zaglavlja JPEG datoteke. Obično su konstruirani tako da su visokofrekventni koeficijenti podložni jačoj kvantizaciji od niskofrekventnih. To rezultira ogrubljivanjem sitnih detalja na slici. Što je veći omjer kompresije, to su svi koeficijenti snažnije kvantizirani.
Prilikom spremanja slike u JPEG datoteku, naveden je parametar kvalitete, naveden u nekim konvencionalnim jedinicama, na primjer, od 1 do 100 ili od 1 do 10. Veći broj obično odgovara boljoj kvaliteti (i većoj veličini komprimirana datoteka). Međutim, čak i kada se koristi najviša kvaliteta (koja odgovara kvantizacijskoj matrici koja se sastoji od samo jedinica), rekonstruirana slika neće točno odgovarati izvornoj, što je povezano i s konačnom točnošću DCT-a i s potrebom zaokruživanja vrijednosti Y, Cb, Cr i koeficijenata DCT na najbliži cijeli broj. Omogućuje JPEG način kompresije bez gubitaka, koji ne koristi DCT točno podudaranje restaurirane i originalne slike, međutim, njegova niska učinkovitost (omjer kompresije rijetko prelazi 2) i nedostatak podrške programera softver nije pridonio popularnosti Lossless JPEG-a.
Varijante shema kompresije JPEG
JPEG standard nudi dva glavna načina za predstavljanje kodiranih podataka.
Najčešći, podržan od strane većine dostupnih kodeka, je sekvencijalni JPEG prikaz podataka, koji uključuje sekvencijalni obilazak kodirane slike blok po blok slijeva nadesno, odozgo prema dolje. Gore opisane operacije izvode se na svakom kodiranom bloku slike, a rezultati kodiranja stavljaju se u izlazni tok u obliku jednog "skena", tj. niz kodiranih podataka koji odgovaraju sekvencijalno proslijeđenoj ("skeniranoj") slici. Glavni ili "osnovni" način kodiranja dopušta samo ovaj prikaz. Prošireni način rada, zajedno sa sekvencijalnim načinom, također omogućuje progresivno predstavljanje JPEG podataka.
U slučaju progresivnog JPEG-a, komprimirani podaci zapisuju se u izlazni tok kao skup skeniranja, od kojih svaki opisuje cijelu sliku sa sve većim stupnjem detalja. To se postiže ili snimanjem u svakom skeniranju ne cijeli set DCT koeficijente, ali samo neki njihov dio: prvi - niskofrekventni, u sljedećim skenovima - visokofrekventni (metoda "spektralne selekcije", tj. spektralnih uzoraka), ili sekvencijalnim, od skeniranja do skeniranja, usavršavanjem DCT koeficijenti ("sukcesivna" metoda aproksimacije", tj. uzastopne aproksimacije). Ovo progresivno predstavljanje podataka posebno je korisno pri prijenosu komprimirane slike koristeći komunikacijske kanale niske brzine, budući da vam omogućuje da dobijete ideju o cijeloj slici nakon prijenosa malog dijela JPEG datoteke.
Obje opisane sheme (i sekvencijalni i progresivni JPEG) temelje se na DCT-u i u osnovi ne dopuštaju dobivanje rekonstruirane slike potpuno identične originalnoj. Međutim, standard također dopušta kompresiju koja ne koristi DCT, već je izgrađena na temelju linearnog prediktora (bez gubitaka, tj. "bez gubitaka", JPEG), jamčeći potpuno, bit-za-bit, podudaranje izvornika i restaurirane slike. Istodobno, omjer kompresije za fotografske slike rijetko doseže 2, ali zajamčena odsutnost izobličenja u nekim slučajevima je tražena. Zamjetno veći omjeri kompresije mogu se postići metodom kompresije JPEG-LS, koja, unatoč sličnosti u nazivima, nije izravno povezana s JPEG ISO/IEC 10918-1 (ITU T.81 preporuka) standardom, opisanim od strane ISO/ IEC 14495-1 standard (ITU T.87 preporuka).
Sintaksa i struktura JPEG formata
JPEG datoteka sadrži niz markeri, od kojih svaki počinje bajtom 0xFF, koji označava početak markera, i bajtom identifikatora. Neki se markeri sastoje samo od ovog para bajtova, dok drugi sadrže dodatne podatke koji se sastoje od polja od dva bajta s duljinom informacijskog dijela markera (uključujući duljinu ovog polja, ali minus dva bajta početka oznake marker, tj. 0xFF i identifikator) i sami podaci.
| Marker | Bajtovi | Duljina | Svrha |
|---|
- Tutorial
UPD. Bio sam prisiljen ukloniti monospace formatiranje. Jednog lijepog dana habraparser je prestao prihvaćati formatiranje unutar pre i code oznaka. Cijeli tekst se pretvorio u kašu. Uprava Habra mi nije mogla pomoći. Sada je neravnomjerno, ali je barem čitljivo.
Jeste li ikada htjeli znati kako funkcionira jpg datoteka? Shvatimo sada! Zagrijte svoj omiljeni prevodilac i heksadecimalni uređivač, dekodirat ćemo ovo:
Namjerno sam uzeo manji crtež. Ovo je poznati, ali jako komprimirani Google favicon:
Odmah vas upozoravam da je opis pojednostavljen i da navedene informacije nisu potpune, ali kasnije će biti lako razumjeti specifikaciju.
Čak i ne znajući kako se kodiranje događa, već možemo izvući nešto iz datoteke.
- startni marker. Uvijek je na početku svih jpg datoteka.
Zatim dolaze bajtovi
. Ovo je oznaka koja označava početak odjeljka komentara. Sljedeća 2 bajta
- duljina odjeljka (uključujući ova 2 bajta). Dakle u sljedeća dva
- sam komentar. To su znakovni kodovi ":" i ")", tj. obični smajlić. Možete ga vidjeti u prvom redu na desnoj strani hex uređivača.
Malo teorije
Vrlo ukratko korak po korak:
Razmislimo o redoslijedu kojim se ti podaci mogu kodirati. Recimo da je kanal Y potpuno kodiran za cijelu sliku, zatim Cb, pa Cr. Svi se sjećaju učitavanja slika na dial-up. Da su kodirani na ovaj način, morali bismo pričekati da se cijela slika učita prije nego što se pojavi na ekranu. Također će biti neugodno ako se kraj datoteke izgubi. Vjerojatno postoje i drugi dobri razlozi. Stoga se kodirani podaci slažu jedan po jedan, u male dijelove. 
Dopustite da vas podsjetim da je svaki blok Y ij, Cb ij, Cr ij matrica DCT koeficijenata kodiranih Huffmanovim kodovima. U datoteci su raspoređeni ovim redoslijedom: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Čitanje datoteke
Nakon što izdvojimo komentar, bit će lako razumjeti sljedeće:- Datoteka je podijeljena na sektore kojima prethode oznake.
- Markeri su dugi 2 bajta, a prvi bajt je .
- Gotovo svi sektori pohranjuju svoju duljinu u sljedeća 2 bajta nakon oznake.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9
Marker: DQT - kvantizacijska tablica.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
Zaglavlje odjeljka uvijek zauzima 3 bajta. U našem slučaju je. Zaglavlje se sastoji od:
Duljina: 0x43 = 67 bajtova
Duljina vrijednosti u tablici: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tablice: 0
Preostala 64 bajta trebaju ispuniti tablicu 8x8.
Pažljivije pogledajte redoslijed kojim se popunjavaju vrijednosti tablice. Ovaj poredak se naziva cik-cak redoslijed: 
Marker: SOF0 - osnovni DCT
Ovaj marker se zove SOF0 i znači da je slika kodirana pomoću osnovne metode. Vrlo je čest. Ali ne manje popularna na Internetu je poznata progresivna metoda, kada se prvo učitava slika niske rezolucije, a zatim normalna slika. To vam omogućuje da razumijete što je tamo prikazano bez čekanja na potpuno preuzimanje. Specifikacija definira još nekoliko, kako mi se čini, ne baš uobičajenih metoda.FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01
Dužina: 17 bajtova.
Preciznost: 8 bita. U osnovnoj metodi uvijek je 8. Koliko ja razumijem, ovo je dubina bita vrijednosti kanala.
Visina slike: 0x10 = 16
Širina slike: 0x10 = 16
Broj komponenti: 3. Najčešće su to Y, Cb, Cr.
1. komponenta:
ID: 1
Horizontalno stanjivanje (H 1): 2
[_2]
Vertikalno stanjivanje (V 1): 2
ID kvantizacijske tablice: 0
2. komponenta:
ID: 2
Horizontalno stanjivanje (H 2): 1
[_1]
Vertikalno stanjivanje (V 2): 1
3. komponenta:
ID: 3
Horizontalno stanjivanje (H 3): 1
[_1]
Vertikalno stanjivanje (V 3): 1
ID kvantizacijske tablice: 1
Sada pogledajte kako odrediti koliko je slika tanka. Nalazimo H max =2 i V max =2. Kanal i bit će stanjen za H max /H i puta vodoravno i V max /V i puta okomito.
Marker: DHT (Huffmanova tablica)
Ovaj odjeljak pohranjuje kodove i vrijednosti dobivene Huffmanovim kodiranjem.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
duljina: 21 bajt.
klasa: 0 (0 - tablica DC koeficijenata, 1 - tablica AC koeficijenata).
[_0]
ID tablice: 0
Duljina Huffmanovog koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Pod brojem kodova podrazumijeva se broj kodova te duljine. Imajte na umu da odjeljak pohranjuje samo duljine kodova, a ne same kodove. Sami moramo pronaći kodove. Dakle, imamo jedan kod duljine 1 i jedan duljine 2. Ukupno 2 koda, nema više kodova u ovoj tablici.
Svaki kod ima pridruženu vrijednost, a one su navedene u datoteci kako slijedi. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. šifre.
- vrijednost 2. šifre.
Konstrukcija Huffmanovog kodnog stabla
Moramo izgraditi binarno stablo iz tablice koju smo dobili u odjeljku DHT. I iz ovog stabla prepoznajemo svaki kod. Dodajemo vrijednosti redoslijedom kojim su navedene u tablici. Algoritam je jednostavan: bez obzira u kojem se čvoru nalazimo, uvijek pokušavamo dodati vrijednost lijevoj grani. A ako je zauzeta, onda desno. A ako tamo nema mjesta, onda se vraćamo na višu razinu i pokušavamo od tamo. Trebate stati na razini jednaka duljini kodirati. Lijeve grane odgovaraju vrijednosti 0, desne - 1.Komentar:
Ne morate svaki put krenuti od vrha. Dodana vrijednost - povratak na višu razinu. Postoji li prava grana? Ako da, idite ponovno gore. Ako ne, stvorite desnu granu i idite tamo. Zatim, od ove točke, počnite tražiti kako biste dodali sljedeću vrijednost.
Stabla za sve tablice u ovom primjeru: 
UPD (hvala): Čvorovi prvog stabla (DC, id =0) moraju imati vrijednosti 0x03 i 0x02
U kružićima su značenja kodova, ispod kružića su sami kodovi (da objasnim da smo ih dobili prolazeći stazom od vrha do svakog čvora). Ovim kodovima (ove i drugih tablica) kodiran je sam sadržaj slike.
Oznaka: SOS (početak skeniranja)
Bajt u markeru znači „DA! Konačno smo prešli izravno na analizu odjeljka kodirane slike!” No rubrika se simbolično zove SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Dužina dijela zaglavlja (ne cijele sekcije): 12 bajtova.
Broj komponenti skeniranja. Imamo 3, po jedan za Y, Cb, Cr.
1. komponenta:
Broj komponente slike: 1 (Y)
ID Huffmanove tablice za DC koeficijente: 0
[_0]
ID Huffmanove tablice za AC koeficijente: 0
2. komponenta:
Broj komponente slike: 2 (Cb)
[_1]
3. komponenta:
Broj komponente slike: 3 (Cr)
ID Huffmanove tablice za DC koeficijente: 1
[_1]
ID Huffmanove tablice za AC koeficijente: 1
Ove komponente se ciklički izmjenjuju.
Ovdje završava dio zaglavlja, odavde do kraja (marker) su kodirani podaci.
0
Određivanje DC koeficijenta.
1.
Čitanje niza bitova (ako naiđemo na 2 bajta, onda to nije marker, već samo bajt). Nakon svakog bita, krećemo se po Huffmanovom stablu (s pripadajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako se nađemo na završnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, onda je koeficijent jednak 0, upisujemo to u tablicu i prelazimo na očitavanje ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je duljina koeficijenta u bitovima. Odnosno, čitamo sljedeća 2 bita, to će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka vrijednosti u binarnom prikazu 1, ostavljamo kako jest: DC_coef = vrijednost. U suprotnom transformiramo: DC_coef = value-2 value length +1 . Koeficijent upisujemo u tablicu na početku cik-cak - gornji lijevi kut.
Određivanje AC koeficijenata.
1.
Slično koraku 1, pronalaženje DC koeficijenta. Nastavljamo čitati niz:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je 0, to znači da preostale vrijednosti matrice moraju biti popunjene nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji pročitaju dovde i napišu mi o tome u osobnoj poruci dobit će plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - to je točno koliko nula moramo dodati matrici. To su 3 nula koeficijenta.
Drugi nibble: 0x1 - duljina koeficijenta u bitovima. Pročitajte sljedeći dio.
10
10
1110
1
110011101100001111100100
3. Slično koraku 3 pronalaženja DC koeficijenta.
Kao što već razumijete, morate čitati AC koeficijente dok ne naiđemo nulta vrijednost koda, ili dok se matrica ne popuni.
U našem slučaju dobit ćemo:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
i matrica:
Jeste li primijetili da su vrijednosti popunjene istim cik-cak uzorkom?
Razlog za korištenje ovog reda je jednostavan - budući da su veće vrijednosti v i u, manje je značajan koeficijent S vu u diskretnoj kosinusnoj transformaciji. Stoga se pri visokim stupnjevima kompresije beznačajni koeficijenti postavljaju na nulu, čime se smanjuje veličina datoteke.
[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-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 0] [ 0 0 0 0 0 0 0 0]
[-4 2 2 1 0 0 0 0]
[-1 0 -1 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]
Oh, zaboravio sam reći da kodirani DC koeficijenti nisu sami DC koeficijenti, već njihove razlike između koeficijenata prethodne tablice (isti kanal)! Matrice je potrebno ispraviti:
DC za 2.: 2 + (-4) = -2
DC za 3.: -2 + 5 = 3
DC za 4.: 3 + (-4) = -1
[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………
Sada je sve u redu. Ovo pravilo vrijedi do kraja datoteke.
...i po matrici za Cb i Cr:
[-1 0 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]
Budući da postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknuti.
Izračuni
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član s elementima kvantizacijske matrice. Ostaje samo odabrati onu koja vam je potrebna. Prvo smo skenirali prvu komponentu, njezina komponenta slike = 1. Komponenta slike s ovim ID-om koristi matricu kvantizacije 0 (naša je prva od dvije). Dakle, nakon množenja:
[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 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]
Slično tome, dobivamo još 3 Y-kanalne matrice...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 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 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]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 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]
...i matricom za Cb i Cr.
[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 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]
[ 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 0 0]
Inverzna diskretna kosinusna transformacija
Formula ne bi trebala biti preteška*. S vu je naša rezultirajuća matrica koeficijenata. u - stupac, v - red. s yx - izravno vrijednosti kanala.
*Općenito govoreći, to nije sasvim točno. Kada sam uspio dekodirati i prikazati sliku 16x16 na ekranu, uzeo sam sliku 600x600 (usput, ovo je bila naslovnica omiljenog albuma Mind.In.A.Boxa - Lost Alone). Nije uspjelo odmah - pojavile su se razne greške. Uskoro sam se mogao diviti ispravno učitanoj slici. Jedina stvar koja me stvarno uznemirila je brzina učitavanja. Još se sjećam da je trajalo 7 sekundi. Ali to nije iznenađujuće, ako nepromišljeno koristite gornju formulu, tada ćete za izračun jednog kanala od jednog piksela morati pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - gotovo tisuću teških operacija na samo jednom kanalu jednog piksela! Srećom, ima prostora za optimizaciju (nakon mnogo eksperimentiranja, smanjio sam vrijeme učitavanja na granicu točnosti timera od 15ms, a nakon toga sam promijenio sliku u fotografiju 25 puta veće površine. Možda o tome pišem u poseban članak).
Napisat ću rezultat izračuna samo prve matrice kanala Y (vrijednosti su zaokružene):
[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]
I preostala 2:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]
- Oh, idem jesti!
- Da, uopće se ne useljavam, o čemu mi pričamo.
- Nakon što se dobiju vrijednosti YCbCr boja, sve što preostaje je pretvoriti ih u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij) , Y ij, Cb ij, Cr ij - naše rezultirajuće matrice.
- 4 Y matrice, te po jedna Cb i Cr, pošto smo prorijedili kanale i 4 Y piksela odgovaraju jednom Cb i Cr. Stoga izračunajte ovako: YCbCrToRGB(Y ij , Cb , Cr )
YCbCr u RGB
R = Y + 1,402 * CrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Ne zaboravite dodati 128. Ako vrijednosti prelaze interval, dodijelite granične vrijednosti. Formula je jednostavna, ali također oduzima dio procesorskog vremena.
Ovdje su rezultirajuće tablice za R, G, B kanale za gornji lijevi kvadrat 8x8 našeg primjera:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
