Fotografije i slike razlikuju se jedna od druge ne samo sadržajem, već i drugim „kompjuterskim“ karakteristikama. Na primjer, po veličini.
Dešava se da izgleda da postoje dva identična crteža, ali jedan je tri puta veći od drugog.
Slike se takođe razlikuju po kvalitetu. Mislim da ste više puta naišli na fotografije izuzetno lošeg kvaliteta. Ovo je vidljivo golim okom. Na primjer, dvije identične fotografije, ali jedna je boljeg, a druga lošijeg kvaliteta.
I dešava se da crtežu nedostaju boje. Evo primjera.
A format ili tip datoteke je odgovoran za sve ovo.
Zapravo, slike mogu biti najviše različitim formatima. A ima ih jako, jako puno. Nećemo ih sve razmatrati, već ćemo govoriti o najčešćim. To su formati kao što su bmp, gif, jpg, png, tiff.
Razlikuju se jedni od drugih, prije svega, po kvaliteti. A kvaliteta se razlikuje po broju (zasićenosti) boja.
Na primjer, slikam sliku različitim bojama. I onda odjednom neke od njih prođu, i moraš završiti slikanje onim što imaš. Naravno, pokušat ću učiniti sve što je moguće kako to ne bi uvelike utjecalo na rezultat, ali slika ipak neće ispasti onako kako bih želio - izblijedjela, mutnija.
Tako je to sa formatima slika. Neki ostavljaju sve boje, dok drugi odrežu neke. I ponekad to uzrokuje pogoršanje slike.
Ovo je prilično grub primjer. U stvari, sve je nešto komplikovanije, ali mislim da ste shvatili suštinu.
Uobičajeni formati slika
BMP je format za crteže napravljene u programu Paint. Može se koristiti za čuvanje nacrtanih slika na vašem računaru. Ali ova vrsta datoteke se ne koristi na Internetu zbog svoje velike veličine. Dakle, ako želite da objavite sliku nacrtanu u Paint-u na blogu ili društvenoj mreži, ona mora biti drugog tipa - gif, jpg ili png.
GIF je popularan format slika na Internetu. Možete ih sačuvati u njemu bez gubitka kvaliteta, ali uz ograničena količina boja - 256. GIF je stekao posebnu popularnost zbog činjenice da može kreirati male animirane (pokretne) slike.
JPG je format za fotografije i slike sa velikim brojem boja. Možete sačuvati sliku u njoj i bez gubitka kvaliteta i sa gubitkom.
PNG je moderan format slike. Ova vrsta slike nije dobijena velika veličina i bez gubitka kvaliteta. Vrlo zgodno: datoteka je mala i kvalitet je dobar. Takođe podržava transparentnost.
TIFF - slike su vrlo dobrog kvaliteta, bez kompresije, tako da je veličina takvih datoteka ogromna. TIFF se koristi kada je kvalitet veliki značaj. Na primjer, kada kreirate vizit karte, knjižice, naslovnice časopisa.
Koji format odabrati
- BMP - ako je ovo crtež napravljen u Paint-u i čuvaćete ga samo na računaru.
- GIF - ako je animacija ili crtež sa malim brojem boja za objavljivanje na Internetu.
- PNG - ako je ovo slika koja ima puno boja ili neke prozirne dijelove.
- JPG (jpeg) - ako je fotografija.
- TIFF - slika za štampu (vizit karte, knjižice, posteri, itd.).
Zdravo dragi prijatelji. Danas ćemo razgovarati o tome koji je format slike najbolji za korištenje na web stranici, koji su formati grafičkih datoteka danas dostupni za web stranicu i da li je potrebno tražiti nove grafičke formate.
Dobijam dosta ovakvih pitanja; mnogi moji studenti pitaju da li mogu da koriste nove SVG i WebP formate i gde je najbolje mesto za korišćenje ovih slika. Naravno, možete koristiti nove formate, samo trebate razumjeti koji je format za šta prikladniji.
Danas su slike na web stranici sastavni dio. Počevši od grafički dizajn i učitavanje slika u članke, grafike prate većinu web lokacija na mreži. Ali ljepota ima cijenu
Neoptimizirane slike su jedan od faktora koji usporavaju web stranicu, na što ukazuju usluge verifikacije.
Stoga ćete uvijek morati odabrati koji format da odaberete za sliku. O tome će ovisiti njegova veličina i kvaliteta. A da biste koristili manje slike bez gubitka kvaliteta, morate znati nekoliko stvari.
Koje slike za web stranice koristim danas?
Sve slike za web stranice podijeljene su na:
- raster (primjer - JPG, JPEG, GIF, PNG),
- vektor (primjer - SVG).
Raster Slike se sastoje od piksela koji pohranjuju vrijednosti boje i prozirnosti. Ovi formati uključuju slike u člancima, dugmad, ikone i elemente dizajna. Ove slike su popularne među programerima i vlasnicima web stranica. Glavni nedostatak rasterskih slika je to što one nisu dobro skalirane.
Odnosno, kada se veličina slike poveća, dolazi do gubitka kvaliteta.
Vector slike se sastoje od linija i putnih tačaka. Informacije o slici se pohranjuju u matematičke upute za renderiranje, što omogućava da se takve slike skaliraju koliko god želite bez gubitka kvalitete.
Sve ove slike se mogu i koriste na modernim web stranicama. Samo to trebate razumjeti prije postavljanja na stranicu, !
Opis popularnih formata slika za stranicu
Iz opisa ovih formata shvatit ćete gdje i koji format je najbolje koristiti na stranici.
JPEG
JPEG ili JPG jedan je od najpopularnijih formata slika za web stranice. Format podržava milione boja, što mu daje vodeću poziciju u prezentaciji fotografija i slika na sajtu.
Slike u ovom formatu su prilično dobro optimizovane bez gubitka kvaliteta, što vam omogućava da dobijete manju datoteku bez vizuelnog gubitka kvaliteta. Treba imati na umu da svaka sljedeća optimizacija smanjuje kvalitetu.
Datoteke ovog formata podržavaju svi uređaji i preglednici, što još jednom potvrđuje njegovu popularnost i omogućava vam da ne brinete o problemima s prikazom na web stranicama.
Veliki nedostatak ovog formata je nedostatak transparentnosti. Odnosno, neće biti moguće kombinirati slike u ovom formatu. Za takve zadatke bolje je koristiti sljedeći format.
PNG
Ovaj format koristi algoritam kompresije bez gubitaka. Što se tiče broja boja i nivoa transparentnosti, dostupan je u dva tipa: 8 i 24-bitni. Oba podržavaju transparentnost.
8-bitna nije baš popularna, ali 24-bitna se široko koristi za razne slike na web stranici. Zbog transparentnosti vam omogućava da kreirate kombinovane slike. Često se koristi za kreiranje animiranih dugmadi i ikona gdje je potreban efekat transparentnosti.
Slike u PNG formatu mogu se optimizirati i uređivati mnogo puta - zadržat će originalni kvalitet.
Format također podržavaju svi pretraživači i uređaji, osiguravajući da se može prikazati na bilo kojem ekranu.
Kvaliteta slika izgleda bolje od JPG-a, ali će težina datoteke biti veća. Ovo se mora uzeti u obzir prilikom postavljanja fajlova na sajt.
GIF
To je 8-bitni format koji podržava 256 boja, transparentnost i animaciju. Zbog podrške malog broja boja, težina datoteke je također minimalna.
Format nije prikladan za fotografije i slike sa širok raspon boje.
Ali se široko koristi u kreiranju banera, dugmadi, ikona i tako dalje.
Na modernim web stranicama ovaj format se sve manje koristi.
Dalje, hajde da pričamo o relativno novijim SVG i WebP formatima, koji nisu toliko popularni, ali dobijaju popularnost i podršku, i savršeno odgovaraju zahtevima brzine učitavanja i prilagodljivosti web sajta.
SVG
Ovo je vektorski format datoteke XML baziran. Format je nedavno počeo da dobija na popularnosti, jer je ranije bio slabo podržan u pretraživačima. A zbog problema sa ekranom, niko nije žurio da ga koristi.
Danas SVG podržavaju svi moderni pretraživači. Ali problemi sa ekranom se i dalje javljaju.
Ovaj format se najčešće koristi za jednostavne slike kao što su logotipi, elementi dizajna i tako dalje. Nije pogodno za fotografije.
SVG format je lagan, vrlo skalabilan, pruža oštre slike na bilo kojoj rezoluciji ekrana, podržava animaciju, može se kontrolisati preko CSS-a i staviti u HTML, smanjujući broj zahtjeva.
WebP
Otvoreni format izvorni kod, koju je Google razvio posebno za internet. Danas YouTube koristi konverziju sličica videa u WebP.
Format pruža vrhunsku kompresiju i podržava transparentnost. Kombinira prednosti JPG i PNG formata bez povećanja veličine datoteke.
Ali, unatoč prednostima formata, ne podržavaju ga svi pretraživači, na primjer, IE, Edge, Firefox i Safari.
Postoje načini da se zaobiđu ova ograničenja, ali one sprečavaju da se format koristi svuda.
Zaključak
Prijatelji, nadam se da sam sve jasno objasnio, a sada znate koji format slike je najbolje koristiti na sajtu i zašto ne insistiram na korišćenju jednog određenog formata, već preporučujem integrisani pristup.
Možda kada WebP dobije široku podršku, svi ćemo se prebaciti na njega i zamijeniti jpg i png na našim stranicama.
Hajde da prodiskutujemo u komentarima koje formate koristite na svojim sajtovima, šta volite, a šta ne.
To je sve za danas, cekam vase komentare.
Srdačan pozdrav, Maxim Zaitsev.
- 1-bitna boja (21 = 2 boje) binarna boja, najčešće predstavljena crnom i bijelom (ili crnom i zelenom)
- 2-bitna boja (22 = 4 boje) CGA, NeXTstation sivilo
- 3-bitna boja (23 = 8 boja) mnogi stari lični računari sa TV izlazom
- 4-bitna boja (24 = 16 boja) poznata je kao EGA i u manjoj mjeri kao VGA standard visoke rezolucije
- 5-bitna boja (25 = 32 boje) Originalni Amiga čipset
- 6-bitna boja (26 = 64 boje) Originalni Amiga čipset
- 8-bitna boja (28 = 256 boja) Naslijeđene Unix radne stanice, VGA niske rezolucije, Super VGA, AGA
- 12-bitna boja (212 = 4.096 boja) na nekim sistemima Silicon Graphics, NeXTstation sistemima i Amiga HAM sistemima.
- Algoritmi kompresije bez gubitaka;
- Algoritmi kompresije sa gubitkom.
WITH Tri najpopularnija formata datoteka su JPEG, RAW, TIFF. Ponekad se mogu čuti nesuglasice među fotografima - koji je format fajla bolji za fotografiju, u kom formatu je bolje slikati, jer moderne kamere omogućavaju fotografisanjetografija u bilo kojem od ovih formata, a ponekad i u nekoliko odjednom!
Format datoteke u kojem je slika pohranjena je u suštini kompromis između kvaliteta slike i veličine datoteke.
Vjerovatno već znate da se rasterska slika sastoji od piksela. Način na koji je rasterska datoteka organizirana i u kojem obliku su informacije o pikselima pohranjene u njoj određuje format datoteke. Kvalitet slike rasterske datoteke određuju dva glavna parametra: veličina piksela (to jest, ukupan broj piksela) i tačnost boje piksela u predstavljanju stvarne boje.Sa veličinom piksela je jasno - što je više piksela (ili što je „manji“ piksel), to bolje.A tačnost reprodukcije boja ovisi o broju boja po pikselu ili dubini boje.
Dubina boje (kvalitet prikazivanja boja, dubina bita slike) - količina memorije u broju bitova koji se koriste za pohranjivanje i predstavljanje boje prilikom kodiranja jednog piksela rasterska grafika ili video slike. Broj bitova označava broj gradacija (tonskih koraka) u svakoj komponenti boje ili, jednostavno, broj boja. Dodavanje 1 bita je dodavanje još jednog bita binarnom kodu boje.
Na primjer, radimo u RGB prostoru boja. To znači da postoje tri kanala iz kojih se formira konačna boja piksela: crveni kanal (Rad), zeleni kanal (Green) i plavi kanal (Blue). Pretpostavimo da su kanali četverobitni. To znači da svaki kanal ima mogućnost prikaza 16 boja. Kao rezultat, sav RGB će biti 12-bitni i moći će se prikazati
C=16x16x16=4096 boja
Dubina boje u ovom slučaju je 12 bita.
Kada ljudi govore o 24-bitnom RGB-u, misle na 8-bitne kanale (svaki od 256 boja) sa ukupnim brojem opcija boja po pikselu
C=256x256x256=16777216 boja.
Brojka je impresivna. Ovaj broj boja za svaki piksel zadovoljava zahtjeve i najzahtjevnijeg fotografa.
Malo o samim formatima.
TIFF format
TIFF je skraćenica od Tagged Image File Format i standard je za industriju štampe i štampe.
Kao rezultat, ovo se događa:
1. Ako je vaša kamera toliko jednostavna da snima samo JPEG, a želite maksimalan kvalitet, postavite maksimalnu veličinu i minimalnu kompresiju i nemojte da vas muči činjenica da nemate druge formate. U većini slučajeva, pažljivo ručno renderovana RAW slika odgovara JPEG-u koji je kamera automatski snimila.
2. Vjerovatno ne biste trebali fotografisati u TIFF formatu. Snimanje u ovom formatu je teže, ali nema primjetne razlike u odnosu na kvalitetan JPEG.
3. Ako imate priliku da slikate u , radite s tim. Sami ćete osjetiti da li je to pravo za vas. U nekim slučajevima, samo RAW omogućava snimanje jedinstvene fotografije za veliko uvećanje prilikom štampanja.
Ostaje još jedno rješenje, moglo bi se reći univerzalni. Postoji režim koji vam omogućava da istovremeno snimate kadrove u dva formata: RAW+ JPEG. Snimajte važne scene u ovom režimu. Moderno digitalno skladištenje informacija - i memorijske kartice i čvrsti diskovi - omogućavaju to. U tom slučaju, dobijate JPEG da odmah koristite fotografiju, bez trošenja vremena na reviziju. A ako vam je to potrebno, povjerite RAW datoteku stručnjaku na obradu.
Fotografija. Formati fajlova.
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 fotoaparatima ili skenerima visoka rezolucija, tada njihova veličina može biti i veća. Unatoč brzom rastu kapaciteta uređaja za pohranu, različiti algoritmi kompresije slike i dalje su vrlo relevantni.
Svi postojeći algoritmi mogu se podijeliti u dvije velike klase:
Algoritmi kompresije bez gubitaka
RLE algoritam
Svi algoritmi RLE serija zasnivaju se na vrlo jednostavnoj ideji: ponavljajuće grupe elemenata zamjenjuju se parom (broj ponavljanja, element koji se ponavlja). Razmotrimo ovaj algoritam koristeći primjer niza bitova. Ovaj niz će izmjenjivati grupe nula i jedinica. Štaviš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 (brojanje počinje od jedinica), ali ovi brojevi također moraju biti kodirani. Pretpostavit ćemo da se broj ponavljanja nalazi u rasponu od 0 do 7 (to jest, 3 bita su nam dovoljna da kodiramo broj ponavljanja). Tada se gore razmatrana sekvenca kodira sljedećim nizom brojeva 5 6 7 0 1 2. Lako je izračunati da je za kodiranje originalne sekvence potreban 21 bit, a u komprimiranom RLE metoda U obliku, ovaj niz traje 18 bita.Iako je ovaj algoritam vrlo jednostavan, njegova efikasnost je relativno niska. Štoviše, u nekim slučajevima korištenje ovog algoritma ne dovodi do smanjenja, već do povećanja dužine niza. Na primjer, razmotrite sljedeću sekvencu 111 0000 11111111 00. Odgovarajuća RL sekvenca izgleda ovako: 3 4 7 0 1 2. Dužina originalne sekvence je 17 bita, dužina komprimirane sekvence je 18 bita.
Ovaj algoritam je najefikasniji za crno-bijele slike. Takođe se često koristi kao jedna od međufaza kompresije složenijih algoritama.
Algoritmi rječnika
Ideja iza algoritama rječnika je da se lanci elemenata originalnog niza kodiraju. Ovo kodiranje koristi poseban rečnik, koji se dobija na osnovu originalnog niza.Postoji čitava porodica algoritama rječnika, ali ćemo se osvrnuti na najčešći algoritam LZW, nazvan po svojim programerima Lepel, Ziv i Welch.
Rječnik u ovom algoritmu je tabela 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 singleton stringovima, tj. prvi redovi rječnika predstavljaju abecedu kojom kodiramo. Tokom 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 dodaje tamo i izlazi komprimirani kod koji odgovara lancu koji je već napisan u rječniku. U teoriji se ne nameću ograničenja na veličinu rječnika, ali u praksi ima smisla ograničiti ovu veličinu, jer s vremenom počinju da se pojavljuju lanci koji se više ne nalaze u tekstu. Osim toga, kada udvostručimo veličinu tablice, moramo dodijeliti dodatni bit za pohranjivanje komprimiranih kodova. Kako bi se takve situacije spriječile, uvodi se poseban kod koji simbolizira inicijalizaciju tablice sa svim lancima od jednog elementa.
Pogledajmo primjer algoritma kompresije. Komprimovaćemo liniju cuckoocuckoocuckoohood. Pretpostavimo da će rječnik sadržavati 32 pozicije, što znači da će svaki njegov kod zauzimati 5 bita. U početku se rječnik popunjava na sljedeći način:
Ova tabela postoji i na strani onoga ko komprimuje informaciju i na strani onoga ko je dekomprimuje. Sada ćemo pogledati proces kompresije.
U tabeli je prikazan proces popunjavanja rječnika. Lako je izračunati da rezultirajući komprimirani kod zauzima 105 bita, a originalni tekst (pod pretpostavkom da potrošimo 4 bita na kodiranje jednog znaka) 116 bita.
U suštini, proces dekodiranja se svodi na direktno dekodiranje kodova, a važno je da se tabela inicijalizira na isti način kao i tokom kodiranja. Pogledajmo sada algoritam dekodiranja.
Mi možemo u potpunosti definirati string dodan u rječnik u i-tom koraku samo na i+1. Očigledno, i-ti red mora završiti prvim znakom i+1 reda. To. Upravo smo shvatili kako vratiti rječnik. Zanimljiva je situacija kada je kodiran niz oblika cScSc, gdje je c jedan znak, a S niz, a riječ cS se već nalazi u rječniku. Na prvi pogled može izgledati da dekoder neće moći riješiti ovu situaciju, ali zapravo svi redovi ovog tipa uvijek moraju završavati istim znakom kojim počinju.
Statistički algoritmi kodiranja
Algoritmi u ovoj seriji dodeljuju najkraći komprimovani kod najčešćim elementima sekvenci. One. sekvence iste dužine kodirane su komprimiranim kodovima različitih dužina. Štaviše, što se sekvenca češće javlja, kraći je odgovarajući komprimovani kod.Huffmanov algoritam
Hafmanov algoritam vam omogućava da konstruišete prefiksne kodove. Prefiksne kodove možemo zamisliti kao staze u binarnom stablu: odlazak od čvora do njegovog lijevog potomka odgovara 0 u kodu, a desno dijete odgovara 1. Ako lišće stabla označimo simbolima da bude kodiran, dobijamo reprezentaciju kod prefiksa u obliku binarnog stabla.Hajde da opišemo algoritam za konstruisanje Hafmanovog stabla i dobijanje Hafmanovih kodova.
- Znakovi ulazne abecede formiraju listu slobodnih čvorova. Svaki list ima težinu koja je jednaka učestalosti pojavljivanja simbola
- Odabrana su dva slobodna čvora stabla sa najmanjim težinama
- Njihov roditelj je kreiran sa težinom jednakom njihovoj ukupnoj težini
- Roditelj se dodaje na listu slobodnih čvorova, a njegova dva podređena se uklanjaju sa ove liste
- Jednom luku koji napušta roditelj je dodeljen bit 1, a drugom bit 0
- Koraci koji počinju od drugog se ponavljaju sve dok samo jedan slobodni čvor ne ostane na listi slobodnih čvorova. Ovo će se smatrati korijenom drveta.
Aritmetičko kodiranje
Algoritmi aritmetičkog kodiranja kodiraju nizove elemenata u razlomak. U ovom slučaju se uzima u obzir frekvencijska raspodjela elemenata. Trenutno su algoritmi aritmetičkog kodiranja zaštićeni patentima, pa ćemo se osvrnuti samo na osnovnu ideju.- Tutorial
UPD. Bio sam primoran da uklonim monospace formatiranje. Jednog lepog dana, habraparser je prestao da prihvata formatiranje unutar oznaka pre i koda. Cijeli tekst se pretvorio u kašu. Uprava Habra mi nije mogla pomoći. Sada je neujednačeno, ali je barem čitljivo.
Da li ste ikada želeli da znate kako funkcioniše jpg fajl? Hajde da to sada shvatimo! Zagrijte svoj omiljeni kompajler i hex editor, mi ćemo ovo dekodirati:
Namjerno sam uzeo manji crtež. Ovo je poznat, ali jako komprimiran Google favicon:
Odmah vas upozoravam da je opis pojednostavljen i date informacije nisu potpune, ali će kasnije biti lako razumjeti specifikaciju.
Čak i bez znanja kako se kodiranje događa, već možemo izdvojiti nešto iz datoteke.
- startni marker. Uvijek je na početku svih jpg datoteka.
Slijede bajtovi
. Ovo je marker koji označava početak odjeljka za komentare. Sljedeća 2 bajta
- dužina sekcije (uključujući ova 2 bajta). Dakle u sljedeća dva
- sam komentar. To su kodovi znakova ":" i ")", tj. običan emotikon. Možete ga vidjeti u prvom redu na desnoj strani hex editora.
Malo teorije
Vrlo kratko korak po korak:
Razmislimo o redoslijedu kojim se ovi 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 čekati da se cijela slika učita prije nego što se pojavi na ekranu. Također će biti neugodno ako se izgubi kraj datoteke. Vjerovatno postoje i drugi dobri razlozi. Stoga se kodirani podaci slažu jedan po jedan, u malim dijelovima. 
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 fajla
Nakon što izdvojimo komentar, biće lako razumjeti da:- Fajl je podijeljen na sektore kojima prethode markeri.
- Markeri su dugi 2 bajta, pri čemu je prvi bajt .
- Gotovo svi sektori pohranjuju svoju dužinu u sljedeća 2 bajta nakon markera.
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 - tabela kvantizacije.
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 jeste. Zaglavlje se sastoji od:
Dužina: 0x43 = 67 bajtova
Dužina vrijednosti u tabeli: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tabele: 0
Preostala 64 bajta treba da popune tabelu 8x8.
Pažljivije pogledajte redoslijed kojim se popunjavaju vrijednosti u tabeli. Ovaj redosled se zove cik-cak redosled: 
Marker: SOF0 - Osnovni DCT
Ovaj marker se zove SOF0 i znači da je slika kodirana korištenjem osnovne metode. Vrlo je česta. Ali ništa manje popularna na Internetu nije poznata progresivna metoda, kada se slika prvi put učitava niske rezolucije, a zatim normalna slika. Ovo vam omogućava da shvatite šta 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 to je uvijek 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 tablice kvantizacije: 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 tablice kvantizacije: 1
Sada pogledajte kako odrediti koliko je slika tanka. Nalazimo H max =2 i V max =2. Kanal i će se istanjiti za H max /H i puta horizontalno i V max /V i puta vertikalno.
Marker: DHT (Huffmanova tablica)
Ovaj odjeljak pohranjuje kodove i vrijednosti dobivene Huffman kodiranjem.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
dužina: 21 bajt.
klasa: 0 (0 - tabela DC koeficijenata, 1 - tabela AC koeficijenata).
[_0]
id tabele: 0
Duljina Huffman koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Broj kodova znači broj kodova te dužine. Imajte na umu da odjeljak pohranjuje samo dužine kodova, a ne same kodove. Šifre moramo pronaći sami. Dakle, imamo jedan kod dužine 1 i jedan dužine 2. Ukupno 2 koda, u ovoj tabeli više nema kodova.
Svaki kod ima pridruženu vrijednost i oni su navedeni u datoteci kako slijedi. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. koda.
- vrijednost 2. koda.
Konstrukcija Huffmanovog kodnog stabla
Moramo da napravimo binarno stablo iz tabele koju smo dobili u DHT sekciji. I iz ovog stabla prepoznajemo svaki kod. Vrijednosti dodajemo redoslijedom kojim su navedene u tabeli. Algoritam je jednostavan: bez obzira u kom 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ši nivo i pokušavamo odatle. Morate se zaustaviti na nivou koji je jednak dužini koda. Lijeve grane odgovaraju vrijednosti 0, desne - 1.komentar:
Ne morate svaki put početi od vrha. Dodata vrijednost - vratite se na viši nivo. Postoji li prava grana? Ako jeste, idite ponovo gore. Ako ne, kreirajte desnu granu i idite tamo. Zatim, od ove tačke, počnite tražiti da dodate sljedeću vrijednost.
Stabla za sve tabele 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 tako što smo prošli put od vrha do svakog čvora). Ovim kodovima (ove i drugih tabela) je kodiran sam sadržaj slike.
Marker: SOS (početak skeniranja)
Bajt u markeru znači „DA! Konačno, prešli smo direktno na raščlanjivanje dijela kodirane slike!” Međutim, dio se simbolično naziva SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Dužina dijela zaglavlja (ne cijelog odjeljka): 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 se završava dio zaglavlja, odavde do kraja (marker) su kodirani podaci.
0
Pronalaženje DC koeficijenta.
1.
Čitanje niza bitova (ako naiđemo na 2 bajta, onda ovo nije marker, već samo bajt). Nakon svakog bita krećemo se duž Huffmanovog stabla (sa odgovarajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako se nađemo na konačnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, tada je koeficijent jednak 0, upisujemo ga u tablicu i prelazimo na očitavanje ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je dužina koeficijenta u bitovima. To jest, čitamo sljedeća 2 bita, to će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka vrijednosti u binarnom prikazu 1, onda je ostavljamo kakva jest: DC_coef = vrijednost. Inače, transformiramo: DC_coef = vrijednost-2 vrijednost dužine +1. Koeficijent upisujemo u tablicu na početku cik-cak - gornjem lijevom uglu.
Pronalaženje AC koeficijenata.
1.
Slično koraku 1, pronalaženje DC koeficijenta. Nastavljamo da čitamo sekvencu:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je 0, to znači da preostale vrijednosti matrice treba popuniti nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji pročitaju dovde i napišu mi o tome u ličnoj poruci dobiće plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - ovo je tačno koliko nula moramo dodati u matricu. Ovo su 3 nula koeficijenta.
Drugi grickanje: 0x1 - dužina koeficijenta u bitovima. Pročitajte sledeći deo.
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 na nultu vrijednost koda, ili dok se matrica ne popuni.
U našem slučaju dobijamo:
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, pri visokim stopama kompresije, beznačajni koeficijenti se 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 iz prethodne tabele (isti kanal)! Potrebno je ispraviti matrice:
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 važi do kraja fajla.
... i prema 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]
Pošto postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknutim.
Računanja
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član sa elementima matrice kvantizacije. Ostaje samo da odaberete onu koja vam je potrebna. Prvo smo skenirali prvu komponentu, njena komponenta slike = 1. Komponenta slike sa ovim ID-om koristi matricu kvantizacije od 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, dobijamo 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 po matrici 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 teška*. S vu je naša rezultujuća matrica koeficijenata. u - stupac, v - red. s yx - direktno vrijednosti kanala.
*Uopšteno govoreći, ovo nije sasvim tačno. Kada sam uspio dekodirati i prikazati sliku veličine 16x16 na ekranu, uzeo sam sliku od 600x600 (usput rečeno, ovo je bila naslovnica omiljenog albuma Mind.In.A.Boxa - Lost Alone). Nije uspjelo odmah - pojavile su se razne greške. Uskoro sam mogao da se divim pravilno učitanoj slici. Jedina stvar koja me stvarno uznemirila je brzina preuzimanja. Još se sjećam da je trebalo 7 sekundi. Ali to nije iznenađujuće, ako nepromišljeno koristite gornju formulu, tada ćete za izračunavanje jednog kanala od jednog piksela morati pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - skoro hiljadu teških operacija na samo jednom kanalu od jednog piksela! Srećom, ima prostora za optimizaciju (nakon mnogo eksperimentisanja smanjio sam vrijeme učitavanja na granicu tačnosti tajmera od 15ms, a nakon toga promijenio sliku u fotografiju sa 25 puta većom površinom. Možda ću o tome pisati u poseban članak).
Napisat ću rezultat izračunavanja 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 da jedem!
- Da, ne useljavam se uopšte, o čemu pričamo.
- Nakon što se dobiju vrijednosti boja YCbCr, ostaje samo da ih konvertujete u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij) , Y ij , Cb ij , Cr ij - naše rezultirajuće matrice.
- 4 Y matrice, i po jedna Cb i Cr, pošto smo razrijedili 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 troši dio procesorskog vremena.
Evo rezultujućih tabela 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
Kraj
Generalno, nisam stručnjak za JPEG, tako da teško mogu odgovoriti na sva pitanja. Samo, kada sam pisao svoj dekoder, često sam morao da se nosim sa raznim stvarima neshvatljivi problemi. A kada je slika bila pogrešno prikazana, nisam znao gdje sam pogriješio. Možda je pogrešno protumačio bitove, ili je možda pogrešno koristio DCT. Zaista mi je nedostajao korak po korak primjer, pa se nadam da će ovaj članak pomoći pri pisanju dekodera. Mislim da pokriva opis osnovne metode, ali to ipak ne možete učiniti sami. Nudim vam linkove koji su mi pomogli: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 fotoaparatima ili skenerima visoke rezolucije, onda njihova veličina može biti i veća. Unatoč brzom rastu kapaciteta uređaja za pohranu, različiti algoritmi kompresije slike i dalje su vrlo relevantni.
Svi postojeći algoritmi mogu se podijeliti u dvije velike klase:
- Algoritmi kompresije bez gubitaka;
- Algoritmi kompresije sa gubitkom.
Algoritmi kompresije bez gubitaka
RLE algoritam
Svi algoritmi serije RLE zasnovani su na vrlo jednostavnoj ideji: ponavljajuće grupe elemenata zamjenjuju se parom (broj ponavljanja, ponavljajući element). Razmotrimo ovaj algoritam koristeći primjer niza bitova. Ovaj niz će izmjenjivati grupe nula i jedinica. Štaviš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 (brojanje počinje od jedinica), ali ovi brojevi također moraju biti kodirani. Pretpostavit ćemo da se broj ponavljanja nalazi u rasponu od 0 do 7 (to jest, 3 bita su nam dovoljna da kodiramo broj ponavljanja). Zatim se gore diskutovana sekvenca kodira sljedećim nizom brojeva 5 6 7 0 1 2. Lako je izračunati da kodiranje originalnog niza zahtijeva 21 bit, au RLE komprimiranom obliku ovaj niz traje 18 bita.Iako je ovaj algoritam vrlo jednostavan, njegova efikasnost je relativno niska. Štoviše, u nekim slučajevima korištenje ovog algoritma ne dovodi do smanjenja, već do povećanja dužine niza. Na primjer, razmotrite sljedeću sekvencu 111 0000 11111111 00. Odgovarajuća RL sekvenca izgleda ovako: 3 4 7 0 1 2. Dužina originalne sekvence je 17 bita, dužina komprimirane sekvence je 18 bita.
Ovaj algoritam je najefikasniji za crno-bijele slike. Takođe se često koristi kao jedna od međufaza kompresije složenijih algoritama.
Algoritmi rječnika
Ideja iza algoritama rječnika je da se lanci elemenata originalnog niza kodiraju. Ovo kodiranje koristi poseban rečnik, koji se dobija na osnovu originalnog niza.Postoji čitava porodica algoritama rječnika, ali ćemo se osvrnuti na najčešći algoritam LZW, nazvan po svojim programerima Lepel, Ziv i Welch.
Rječnik u ovom algoritmu je tabela 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 singleton stringovima, tj. prvi redovi rječnika predstavljaju abecedu kojom kodiramo. Tokom 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 dodaje tamo i izlazi komprimirani kod koji odgovara lancu koji je već napisan u rječniku. U teoriji se ne nameću ograničenja na veličinu rječnika, ali u praksi ima smisla ograničiti ovu veličinu, jer s vremenom počinju da se pojavljuju lanci koji se više ne nalaze u tekstu. Osim toga, kada udvostručimo veličinu tablice, moramo dodijeliti dodatni bit za pohranjivanje komprimiranih kodova. Kako bi se takve situacije spriječile, uvodi se poseban kod koji simbolizira inicijalizaciju tablice sa svim lancima od jednog elementa.
Pogledajmo primjer algoritma kompresije. Komprimovaćemo liniju cuckoocuckoocuckoohood. Pretpostavimo da će rječnik sadržavati 32 pozicije, što znači da će svaki njegov kod zauzimati 5 bita. U početku se rječnik popunjava na sljedeći način:
Ova tabela postoji i na strani onoga ko komprimuje informaciju i na strani onoga ko je dekomprimuje. Sada ćemo pogledati proces kompresije. 
U tabeli je prikazan proces popunjavanja rječnika. Lako je izračunati da rezultirajući komprimirani kod zauzima 105 bita, a originalni tekst (pod pretpostavkom da potrošimo 4 bita na kodiranje jednog znaka) 116 bita.
U suštini, proces dekodiranja se svodi na direktno dekodiranje kodova, a važno je da se tabela inicijalizira na isti način kao i tokom kodiranja. Pogledajmo sada algoritam dekodiranja. 
Mi možemo u potpunosti definirati string dodan u rječnik u i-tom koraku samo na i+1. Očigledno, i-ti red mora završiti prvim znakom i+1 reda. To. Upravo smo shvatili kako vratiti rječnik. Zanimljiva je situacija kada je kodiran niz oblika cScSc, gdje je c jedan znak, a S niz, a riječ cS se već nalazi u rječniku. Na prvi pogled može izgledati da dekoder neće moći riješiti ovu situaciju, ali zapravo svi redovi ovog tipa uvijek moraju završavati istim znakom kojim počinju.
Statistički algoritmi kodiranja
Algoritmi u ovoj seriji dodeljuju najkraći komprimovani kod najčešćim elementima sekvenci. One. sekvence iste dužine kodirane su komprimiranim kodovima različitih dužina. Štaviše, što se sekvenca češće javlja, kraći je odgovarajući komprimovani kod.Huffmanov algoritam
Hafmanov algoritam vam omogućava da konstruišete prefiksne kodove. Prefiksne kodove možemo zamisliti kao staze u binarnom stablu: odlazak od čvora do njegovog lijevog potomka odgovara 0 u kodu, a desno dijete odgovara 1. Ako lišće stabla označimo simbolima da bude kodiran, dobijamo reprezentaciju prefiksnog koda u binarnom stablu.Hajde da opišemo algoritam za konstruisanje Hafmanovog stabla i dobijanje Hafmanovih kodova.
- Znakovi ulazne abecede formiraju listu slobodnih čvorova. Svaki list ima težinu koja je jednaka učestalosti pojavljivanja simbola
- Odabrana su dva slobodna čvora stabla sa najmanjim težinama
- Njihov roditelj je kreiran sa težinom jednakom njihovoj ukupnoj težini
- Roditelj se dodaje na listu slobodnih čvorova, a njegova dva podređena se uklanjaju sa ove liste
- Jednom luku koji napušta roditelj je dodeljen bit 1, a drugom bit 0
- Koraci koji počinju od drugog se ponavljaju sve dok samo jedan slobodni čvor ne ostane na listi slobodnih čvorova. Ovo će se smatrati korijenom drveta.
Aritmetičko kodiranje
Algoritmi aritmetičkog kodiranja kodiraju nizove elemenata u razlomak. U ovom slučaju se uzima u obzir frekvencijska raspodjela 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 frekvencije pojavljivanja p1,...,pN, redom. Podijelimo pola intervala)
