Koju metodu kompresije koristi jpeg algoritam? JPEG kompresuje bolje od GIF-a

29.04.2019 Greške

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.

Kada govorimo o kompresiji bez gubitaka, mislimo da postoji inverzni algoritam u odnosu na algoritam kompresije koji vam omogućava da precizno vratite originalnu sliku. Za algoritme kompresije s gubicima obrnuti algoritam ne postoji. Postoji algoritam koji vraća sliku koja se nužno ne podudara s originalnom. Algoritmi kompresije i oporavka odabrani su kako bi se postigao visok omjer kompresije uz održavanje vizualnog kvaliteta slike.

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). 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

Huffmanov algoritam vam omogućava da gradite prefiks kodovi. Možete razmišljati o prefiksnim kodovima kao o putanjama do binarno stablo: prijelaz od čvora do njegovog lijevog djeteta odgovara 0 u kodu, a desno dijete odgovara 1. Ako označimo listove stabla simbolima koje treba kodirati, dobićemo binarni prikaz stabla kod prefiksa.
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 koju jednaka frekvenciji izgled 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.

Koristeći ovaj algoritam, možemo dobiti Huffmanove kodove za dati alfabet, uzimajući u obzir učestalost pojavljivanja znakova.

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 poluinterval 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 prvo učitava slika niske rezolucije, a zatim normalna slika. Ovo vam omogućava da shvatite šta je tamo prikazano bez čekanja puno opterećenje. 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.

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 )

Ako ste izabrali 1 i 4, onda mi je drago zbog vas. Ili ste dobro shvatili ili ćete uskoro uživati u hrani.

YCbCr u RGB

R = Y + 1,402 * Cr
G = 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 nerazumljivim problemima. 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:

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 Loša 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.

U stvari, slike dolaze u 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 sa ograničenim brojem 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 se dobija mala velicina 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 od velike važnosti. 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. I da koristim slike manja veličina i bez gubljenja kvaliteta, treba znati neke 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 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 se 24-bitna široko koristi razne slike Online. 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 format vektorske datoteke on 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

Format otvorenog koda koji je razvio Google 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.

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 rasterske grafike 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 binarni kod hromatičnost.

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.

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 tako jednostavna da snima samo JPEG i želite da dobijete maksimalni kvalitet, postavite maksimalnu veličinu i minimalnu kompresiju i nemojte se mučiti činjenicom 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 datoteka.

Algoritmi kompresije bez gubitaka;
Algoritmi kompresije sa gubitkom.

Algoritmi kompresije bez gubitaka

RLE algoritam

Algoritmi rječnika

Ova tabela postoji i na strani onoga ko komprimuje informaciju i na strani onoga ko je dekomprimuje. Sada ćemo pogledati proces kompresije.

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

Huffmanov algoritam

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.

Koristeći ovaj algoritam, možemo dobiti Huffmanove kodove za dati alfabet, uzimajući u obzir učestalost pojavljivanja znakova.

Aritmetičko kodiranje

Tutorial

Iz naslova ste ispravno shvatili da ovo nije sasvim običan opis JPEG algoritma (format fajla sam opisao detaljno u članku “JPEG dekodiranje za lutke”). Prije svega, odabrana metoda prezentacije materijala pretpostavlja da ne znamo ništa ne samo o JPEG-u, već ni o Fourier-ovoj transformaciji i Huffman-ovom kodiranju. Generalno, malo toga pamtimo sa predavanja. Samo su uzeli sliku i počeli razmišljati o tome kako se može komprimirati. Stoga sam pokušao jasno izraziti samo suštinu, ali u kojoj će čitatelj razviti prilično duboko i, što je najvažnije, intuitivno razumijevanje algoritma. Formule i matematičke kalkulacije - u najmanju ruku samo one koje su važne za razumijevanje onoga što se dešava.

Poznavanje JPEG algoritma je veoma korisno ne samo za kompresiju slike. Koristi teoriju iz digitalna obrada signali, matematička analiza, linearna algebra, teorija informacija, posebno Fourierova transformacija, kodiranje bez gubitaka, itd. Stoga stečeno znanje može biti korisno bilo gdje.

Ako želite, predlažem da sami prođete kroz iste korake paralelno sa člankom. Provjerite u kojoj mjeri je gore navedeno obrazloženje prikladno različite slike, pokušajte napraviti vlastite izmjene u algoritmu. Veoma je zanimljivo. Kao alat, mogu preporučiti divnu kombinaciju Python + NumPy + Matplotlib + PIL(Pillow). Gotovo sav moj rad (uključujući grafiku i animaciju) radio sam pomoću njih.

Pažnja, saobraćaj! Mnogo ilustracija, grafikona i animacija (~ 10Mb). Ironično, u članku o JPEG-u postoje samo 2 slike ovog formata od pedeset.

Bez obzira na algoritam kompresije informacija, njegov princip će uvijek biti isti - pronalaženje i opisivanje obrazaca. Što više obrazaca, to je više redundantnosti, manje informacija. Arhivari i koderi su obično „skrojeni“ za određenu vrstu informacija i znaju gdje ih pronaći. U nekim slučajevima, uzorak je odmah vidljiv, kao što je slika plavog neba. Svaki red njegove digitalne reprezentacije može se prilično precizno opisati ravnom linijom.

Treniraćemo na rakunskim mačkama. Siva slika iznad je uzeta kao primjer. Dobro kombinuje i homogena i kontrastna područja. A ako naučimo komprimirati sivu, onda neće biti problema s bojom.

Vektorska reprezentacija

Prvo, hajde da proverimo koliko su zavisna dva susedna piksela. Logično je pretpostaviti da će najvjerovatnije biti vrlo slični. Provjerimo ovo za sve parove slika. Označimo ih na koordinatnoj ravni tačkama tako da vrijednost tačke duž ose X bude vrijednost prvog piksela, a duž ose Y - drugog. Za našu sliku dimenzija 256 x 256 dobijamo 256*256/2 piksela:

Očekivano, većina tačaka se nalazi na ili blizu linije y=x (a ima ih čak i više nego što se može videti na slici, pošto se mnogo puta preklapaju i, osim toga, prozirne su). Ako je tako, bilo bi lakše raditi ako ih rotirate za 45°. Da biste to učinili, morate ih izraziti u drugom koordinatnom sistemu.

Osnovni vektori novog sistema su očigledno: . Primorani smo da podijelimo korijenom od dva da bismo dobili ortonormirani sistem (dužine baznih vektora su jednake jedan). Ovdje je pokazano da će određena tačka p = (x, y) u novom sistemu biti predstavljena kao tačka (a 0 , a 1). Poznavajući nove koeficijente, lako možemo dobiti stare okrećući ih. Očigledno je prva (nova) koordinata prosjek, a druga razlika x i y (ali podijeljena korijenom 2). Zamislite da se od vas traži da ostavite samo jednu od vrijednosti: ili 0 ili 1 (to jest, izjednačite drugu s nulom). Bolje je odabrati 0, jer će vrijednost 1 najvjerovatnije biti oko nule. Evo šta se dešava ako vratimo sliku samo iz 0:

4x uvećanje:

Iskreno, ova kompresija nije baš impresivna. Bolje je slično podijeliti sliku na trojke piksela i predstaviti ih u trodimenzionalnom prostoru.

Ovo je isti grafikon, ali iz različitih uglova. Crvene linije su sjekire koje su se sugerirale. Oni odgovaraju vektorima: . Da vas podsjetim da morate podijeliti sa nekim konstantama tako da dužine vektora postanu jednake jedan. Dakle, proširivanjem na ovoj osnovi, dobijamo 3 vrijednosti a 0, a 1, a 2, a 0 je važnije od 1, a 1 je važnije od 2. Ako odbacimo 2, tada će se graf „spljoštiti“ u smjeru vektora e 2. Ovaj već prilično tanak trodimenzionalni list postat će ravan. Neće toliko izgubiti, ali ćemo se osloboditi trećine vrijednosti. Uporedimo slike rekonstruisane iz trojki: (a 0, 0, 0), (a 1, a 2, 0) i (a 0, a 1, a 2). IN najnoviju verziju Nismo ništa bacili, pa ćemo uzeti original.

4x uvećanje:

Drugi crtež je već dobar. Oštre oblasti su malo izglađene, ali je slika u celini veoma dobro očuvana. A sada, hajde da podijelimo po četiri na isti način i vizualno odredimo osnovu u četverodimenzionalnom prostoru... O, pa, da. Ali možete pogoditi koji će biti jedan od osnovnih vektora: (1,1,1,1)/2. Stoga, možemo pogledati projekciju četverodimenzionalnog prostora na prostor okomit na vektor (1,1,1,1) da bismo identificirali druge. Ali ovo nije najbolji način.
Naš cilj je naučiti kako transformirati (x 0 , x 1 , ..., x n-1) u (a 0 , a 1 , ..., a n-1) tako da svaka vrijednost a i bude manje važna od prethodnih. Ako to možemo učiniti, onda se možda posljednje vrijednosti niza mogu potpuno odbaciti. Gore navedeni eksperimenti nagovještavaju da je to moguće. Ali ne možete bez matematičkog aparata.
Dakle, moramo transformisati tačke na novu osnovu. Ali prvo morate pronaći odgovarajuću osnovu. Vratimo se prvom eksperimentu uparivanja. Razmotrimo to općenito. Definirali smo osnovne vektore:

Kroz njih smo izrazili vektor str:

ili u koordinatama:

Da biste pronašli 0 i 1 morate projektirati str on e 0 i e 1 respektivno. A za ovo morate pronaći skalarni proizvod

slično:

U koordinatama:

Često je zgodnije izvršiti transformaciju u matričnom obliku.

Tada je A = EX i X = E T A. Ovo je lijep i zgodan oblik. Matrica E se zove transformaciona matrica i ortogonalna je, sa njom ćemo se susresti kasnije.

Prijelaz sa vektora na funkcije.

Pogodno je raditi s vektorima malih dimenzija. Međutim, želimo da pronađemo obrasce u većim blokovima, pa je umjesto N-dimenzionalnih vektora pogodnije raditi sa sekvencama koje predstavljaju sliku. Takve sekvence ću nazvati diskretnim funkcijama, budući da se sljedeće razmišljanje primjenjuje i na kontinuirane funkcije.
Da se vratimo na naš primjer, zamislimo funkciju f(i), koja je definirana u samo dvije točke: f(0)=x i f(1)=y. Slično, definiramo osnovne funkcije e 0 (i) i e 1 (i) na osnovu baza e 0 i e 1 . Dobijamo:

Ovo je veoma važan zaključak. Sada u frazi “proširenje vektora u ortonormiranim vektorima” možemo zamijeniti riječ “vektor” sa “funkcija” i dobiti potpuno ispravan izraz “proširivanje funkcije u ortonormalne funkcije”. Nema veze što smo dobili tako kratku funkciju, jer isto razmišljanje radi i za N-dimenzionalni vektor, koji se može predstaviti kao diskretna funkcija sa N vrijednosti. A rad sa funkcijama je jasniji nego sa N-dimenzionalnim vektorima. Suprotno tome, takvu funkciju možete predstaviti kao vektor. Štaviše, uobičajeno kontinuirana funkcija može se predstaviti kao beskonačno-dimenzionalan vektor, iako ne u Euklidskom, već u Hilbertovom prostoru. Ali nećemo ići tamo; zanimat će nas samo diskretne funkcije.
A naš problem nalaženja baze pretvara se u problem nalaženja odgovarajućeg sistema ortonormiranih funkcija. U nastavku razmišljanja pretpostavlja se da smo već nekako odredili skup osnovnih funkcija prema kojima ćemo dekomponirati.
Recimo da imamo neku funkciju (predstavljenu, na primjer, vrijednostima) koju želimo predstaviti kao zbir drugih. Ovaj proces možete predstaviti u vektorskom obliku. Da biste dekomponirali funkciju, trebate je "projecirati" na osnovne funkcije jednu po jednu. U vektorskom smislu, izračunavanje projekcije daje minimalni pristup originalnog vektora drugom u smislu udaljenosti. Imajući na umu da se udaljenost izračunava pomoću Pitagorine teoreme, sličan prikaz u obliku funkcija daje najbolju aproksimaciju srednjeg kvadrata funkcije drugoj. Dakle, svaki koeficijent (k) određuje “zatvorenost” funkcije. Formalnije, k*e(x) je najbolja aproksimacija srednjeg kvadrata za f(x) među l*e(x).
Sljedeći primjer pokazuje proces aproksimacije funkcije koristeći samo dvije točke. Desno je vektorski prikaz.

U odnosu na naš eksperiment podjele u parove, možemo reći da su ove dvije tačke (0 i 1 duž apscise) par susjednih piksela (x, y).
Ista stvar, ali sa animacijom:

Ako uzmemo 3 boda, onda moramo uzeti u obzir 3D vektori, međutim, aproksimacija će biti preciznija. A za diskretnu funkciju sa N vrijednostima, morate uzeti u obzir N-dimenzionalne vektore.
Imajući skup dobijenih koeficijenata, možete lako dobiti originalnu funkciju zbrajanjem osnovnih funkcija uzetih s odgovarajućim koeficijentima. Analiza ovih koeficijenata može otkriti mnogo toga korisne informacije(u zavisnosti od osnove). Poseban slučaj ovih razmatranja je princip ekspanzije Fourierovog reda. Na kraju krajeva, naše razmišljanje je primjenjivo na bilo koju osnovu, a kada se proširi u Fourierov niz, uzima se potpuno specifična.

Diskretne Fourierove transformacije (DFT)

U prethodnom dijelu smo došli do zaključka da bi bilo lijepo funkciju razložiti na njene komponente. Početkom 19. veka o tome je razmišljao i Fourier. Istina, nije imao sliku rakuna, pa je morao proučiti raspodjelu topline duž metalnog prstena. Tada je otkrio da je vrlo zgodno izraziti temperaturu (i njenu promjenu) u svakoj tački prstena kao zbir sinusoida sa različitim periodima. “Fourier je otkrio (preporučujem da pročitate, zanimljivo je) da drugi harmonik opada 4 puta brže od prvog, a harmonici višeg reda raspadaju još bržom brzinom.”
Općenito, ubrzo se pokazalo da se periodične funkcije mogu savršeno razložiti u zbir sinusoida. A budući da u prirodi postoji mnogo objekata i procesa opisanih periodičnim funkcijama, pojavio se moćan alat za njihovu analizu.
Možda je jedan od najvizuelnijih periodičnih procesa zvuk.

1. graf - čisti ton sa frekvencijom od 2500 herca.
2. - bijeli šum. To jest, buka sa frekvencijama ravnomjerno raspoređenim po cijelom rasponu.
3. - zbir prva dva.

Da su mi dali vrijednosti posljednje funkcije u onom trenutku kada nisam znao za Fourierove redove i zamolili me da ih analiziram, onda bih se definitivno zbunio i ne bih mogao reći ništa vrijedno. Pa da, nekakva funkcija, ali kako shvatiti da je tu nešto naručeno? Ali da sam pogodio da slušam posljednju funkciju, moje uho bi među bukom uhvatilo čist ton. Iako ne baš dobro, jer sam tokom generacije posebno odabrao takve parametre kako bi se na sumarnom grafikonu signal vizualno otopio u šumu. Koliko sam shvatio, još uvijek nije jasno kako slušni aparat radi to. Međutim, nedavno je postalo jasno da on ne razlaže zvuk na sinusne talase. Možda ćemo jednog dana shvatiti kako se to događa i pojavit će se napredniji algoritmi. Pa, za sada to radimo na starinski način.
Zašto ne biste pokušali koristiti sinusoide kao osnovu? U stvari, mi smo to već uradili. Prisjetimo se naše dekompozicije na 3 bazna vektora i predstavimo ih na grafu:

Da, da, znam, izgleda kao prilagođavanje, ali sa tri vektora teško je očekivati više. Ali sada je jasno kako dobiti, na primjer, 8 baznih vektora:

Nije dobro kompleksna provera pokazuje da su ovi vektori po paru okomiti, tj. ortogonalni. To znači da se mogu koristiti kao osnova. Transformacija na takvoj osnovi je široko poznata i naziva se diskretna kosinusna transformacija (DCT). Mislim da je iz gornjih grafikona jasno kako se dobija formula DCT transformacije:

Ovo je i dalje ista formula: A = EX sa zamijenjenom osnovom. Bazni vektori specificiranog DCT-a (oni su također vektori reda matrice E) su ortogonalni, ali ne i ortonormalni. Ovo treba imati na umu tokom inverzne transformacije (neću se zadržavati na ovome, ali za one koji su zainteresovani, inverzni DCT ima termin 0,5*a 0, pošto je vektor nulte baze veći od ostalih).
Sljedeći primjer pokazuje proces aproksimacije međuzbirova originalnim vrijednostima. Na svakoj iteraciji, sljedeća osnova se množi sa sljedećim koeficijentom i dodaje srednjem zbroju (to jest, isto kao u ranim eksperimentima na rakunu - trećina vrijednosti, dvije trećine).

Ali, ipak, uprkos nekim argumentima o preporučljivosti odabira takve osnove, pravih argumenata još nema. Zaista, za razliku od zvuka, izvodljivost dekompozicije slike na periodične funkcije je mnogo manje očigledna. Međutim, slika zaista može biti previše nepredvidljiva čak i na maloj površini. Dakle, slika je podijeljena na komadiće dovoljno male, ali ne baš sićušne, da bi dekompozicija imala smisla. U JPEG-u, slika je “isječena” na kvadrate 8x8. Unutar takvog komada, fotografije su obično vrlo ujednačene: pozadina plus male fluktuacije. Takvim područjima se lijepo približavaju sinusoidi.
Pa, recimo da je ova činjenica manje-više intuitivna. Ali postoji loš osjećaj o naglim prijelazima boja, jer nas polagana promjena funkcija neće spasiti. Moramo dodati razne visokofrekventne funkcije koje rade svoj posao, ali se pojavljuju postrance na homogenoj pozadini. Uzmimo sliku 256x256 sa dva kontrastna područja:

Hajde da dekomponujemo svaki red koristeći DCT, tako da dobijemo 256 koeficijenata po redu.
Tada ostavljamo samo prvih n koeficijenata, a ostale postavljamo na nulu, pa će slika biti predstavljena kao zbir samo prvih harmonika:

Broj na slici je broj preostalih kvota. Na prvoj slici ostaje samo prosječna vrijednost. Na drugom je već dodana jedna niskofrekventna sinusoida itd. Usput, obratite pažnju na ivicu - uprkos svim najboljim aproksimacijama, 2 pruge su jasno vidljive pored dijagonale, jedna svjetlija, druga tamnija. Dio zadnje slike uvećan 4 puta:

I općenito, ako daleko od granice vidimo početnu jednoliku pozadinu, onda kada joj se približimo, amplituda počinje rasti, konačno dostiže minimalnu vrijednost, a zatim odjednom postaje maksimalna. Ovaj fenomen je poznat kao Gibbsov efekat.

Visina ovih grba, koje se pojavljuju u blizini diskontinuiteta funkcije, neće se smanjivati kako se broj sabiraka funkcija povećava. U diskretnoj transformaciji nestaje tek kada su sačuvani gotovo svi koeficijenti. Tačnije, postaje nevidljiv.
Sljedeći primjer je potpuno sličan gornjoj dekompoziciji trokuta, ali na pravom rakunu:

Prilikom proučavanja DCT-a može se steći pogrešan utisak da je uvijek dovoljno samo prvih nekoliko (niskofrekventnih) koeficijenata. To vrijedi za mnoge fotografije, one čija se značenja ne mijenjaju dramatično. Međutim, na granici kontrastnih područja, vrijednosti će brzo "skočiti", pa će čak i posljednji koeficijenti biti veliki. Stoga, kada čujete za svojstvo očuvanja energije DCT-a, uzmite u obzir činjenicu da se ono primjenjuje na mnoge vrste signala na koje se nailazi, ali ne na sve. Na primjer, razmislite kako bi izgledala diskretna funkcija čiji su koeficijenti proširenja jednaki nuli, osim posljednje. Savjet: Zamislite dekompoziciju u vektorskom obliku.
Unatoč nedostacima, odabrana osnova je jedna od najboljih na pravim fotografijama. Videćemo malo poređenje sa ostalima malo kasnije.

DCT naspram svega ostalog

Kada sam proučavao pitanje ortogonalnih transformacija, da budem iskren, nisam bio baš uvjeren argumentima da je sve okolo zbir harmonijske vibracije, tako da morate da razložite slike na sinusoide. Ili bi možda neke funkcije koraka bile bolje? Stoga sam tražio rezultate istraživanja o optimalnosti DCT-a na stvarnim slikama. Svugdje je zapisano da se „u praktičnim primjenama najčešće nalazi DCT zbog svojstva „energetskog zbijanja“. Ovo svojstvo znači da je maksimalna količina informacija sadržana u prvim koeficijentima. I zašto? Nije teško provesti istraživanje: naoružamo se gomilom različitih slika, različitih poznatih baza i počinjemo računati standardnu devijaciju od stvarne slike za različit broj koeficijenata. Pronašao sam malu studiju u članku (korišćene slike) o ovoj tehnici. Prikazuje grafove zavisnosti pohranjene energije od broja prvih koeficijenata ekspanzije za različite baze. Ako ste pogledali grafikone, bili ste uvjereni da DCT konstantno zauzima počasno... hm... 3. mjesto. Kako to? Kakva je ovo KLT konverzija? Hvalio sam DCT, a onda...

KLT

Sve transformacije, osim KLT, su transformacije sa konstantnom osnovom. A u KLT-u (Karhunen-Loeve transformacija) izračunava se najoptimalnija osnova za nekoliko vektora. Izračunava se na način da prvi koeficijenti daju najmanju srednju kvadratnu grešku ukupno za sve vektore. Prethodno smo obavljali sličan rad ručno, vizualno određujući osnovu. U početku se čini kao dobra ideja. Mogli bismo, na primjer, podijeliti sliku na male dijelove i izračunati vlastitu osnovu za svaki. Ali ne samo da postoji briga o čuvanju ove osnove, već je i operacija njenog izračunavanja prilično radno intenzivna. Ali DCT gubi samo malo, a osim toga, DCT ima brze algoritme konverzije.

DFT

DFT (Diskretna Fourierova transformacija) - diskretna transformacija Fourier. Pod ovim imenom se ponekad spominje ne samo određena transformacija, već i čitava klasa diskretnih transformacija (DCT, DST...). Pogledajmo DFT formulu:

Kao što možete pretpostaviti, ovo je ortogonalna transformacija sa nekom vrstom složene osnove. Budući da se takav složeni oblik javlja malo češće nego inače, ima smisla proučiti njegovo izvođenje.
Može se činiti da će svaki čisti harmonijski signal (sa cjelobrojnom frekvencijom) sa DCT dekompozicijom dati samo jedan koeficijent različit od nule koji odgovara ovom harmoniku. To nije tačno, jer je osim frekvencije važna i faza ovog signala. Na primjer, proširenje sinusa u kosinuse (na sličan način u diskretnoj ekspanziji) će biti ovako:

Toliko o čistim harmonicima. Izrodila je gomilu drugih. Animacija prikazuje DCT koeficijente sinusnog vala različite faze.

Ako vam se činilo da se stupovi okreću oko ose, onda vam se nije činilo.
Dakle, sada nećemo jednostavno proširiti funkciju u zbir sinusoida različite frekvencije, ali i pomaknut u nekoj fazi. Bit će prikladnije razmotriti fazni pomak na primjeru kosinusa:

Jednostavan trigonometrijski identitet daje važan rezultat: fazni pomak je zamijenjen sumom sinusa i kosinusa, uzetim sa koeficijentima cos(b) i sin(b). To znači da se funkcije mogu proširiti na zbir sinusa i kosinusa (bez ikakvih faza). Ovo je uobičajena trigonometrijska forma. Međutim, kompleks se koristi mnogo češće. Da biste je dobili potrebno je koristiti Ojlerovu formulu. Jednostavnom zamjenom derivativnih formula za sinus i kosinus, dobivamo:

Sada za malu promjenu. Donja crta je konjugirani broj.

Dobijamo konačnu jednakost:

c je kompleksni koeficijent čiji je stvarni dio jednak koeficijentu kosinusa, a imaginarni dio je jednak koeficijentu sinusa. A skup tačaka (cos(b), sin(b)) je krug. U takvom snimku svaki harmonik ulazi u ekspanziju i sa pozitivnom i sa negativnom frekvencijom. Stoga se u različitim formulama Fourierove analize obično zbraja ili integracija odvija od minus do plus beskonačnosti. Često je prikladnije izvršiti proračune u ovom složenom obliku.
Transformacija razlaže signal u harmonike sa frekvencijama od jedne do N oscilacija u području signala. Ali stopa uzorkovanja je N po području signala. A prema Kotelnikovovoj teoremi (poznatoj kao Nyquist-Shannon teorem), frekvencija uzorkovanja bi trebala biti najmanje dvostruku frekvenciju signala. Ako to nije slučaj, onda je učinak pojava signala s lažnom frekvencijom:

Isprekidana linija prikazuje pogrešno rekonstruirani signal. Često ste se susreli sa ovim fenomenom u životu. Na primjer, smiješno kretanje kotača automobila u videu ili moire efekat.
Ovo dovodi do činjenice da se čini da se druga polovina amplituda N kompleksa sastoji od drugih frekvencija. Ovi lažni harmonici druge polovine jesu zrcalnu sliku oni to ne nose prvi Dodatne informacije. Dakle, ostaje nam N/2 kosinusa i N/2 sinusa (koji formiraju ortogonalnu osnovu).
U redu, postoji osnova. Njegove komponente su harmonici sa cijelim brojem oscilacija u području signala, što znači da su ekstremne vrijednosti harmonika jednake. Tačnije, oni su skoro jednaki, jer posljednja vrijednost nije uzeta u potpunosti sa ruba. Štaviše, svaki harmonik je gotovo zrcalno simetričan u odnosu na njegov centar. Sve ove pojave su posebno jake u niske frekvencije, koji su nam važni prilikom kodiranja. Ovo je također loše jer će granice bloka biti vidljive na komprimiranoj slici. Dozvolite mi da ilustrujem DFT osnovu sa N=8. Prva 2 reda su kosinusne komponente, a zadnja su sinusne:

Obratite pažnju na pojavu duplih komponenti kako se frekvencija povećava.

Možete mentalno razmišljati o tome kako bi se signal čije vrijednosti postepeno smanjuju od maksimalne vrijednosti na početku do minimalne vrijednosti na kraju mogao razložiti. Manje ili više adekvatnu aproksimaciju mogli bi napraviti samo harmonici pred kraj, što za nas nije baš sjajno. Slika na lijevoj strani je aproksimacija jednostranog signala. Desno - simetrično:

Sa prvim su stvari izuzetno loše.
Pa možda možemo to učiniti kao u DCT-u - smanjiti frekvencije za 2 ili drugi broj puta, tako da broj nekih oscilacija bude razloman, a granice u različitim fazama? Tada će komponente biti neortogonalne. I tu se ništa ne može učiniti.

DST

Šta ako koristimo sinuse umjesto kosinusa u DCT? Dobićemo diskretnu sinusnu transformaciju (DST). Ali za naš zadatak, svi su oni nezanimljivi, jer su i cijeli i poluperiod sinusa blizu nule na granicama. To jest, dobićemo približno istu neprikladnu dekompoziciju kao DFT.

Vraćanje na DCT

Kako mu ide na granici? U redu. Ima antifaza i nema nula.

Sve ostalo

Ne-Furierove transformacije. Neću to opisivati.
WHT - matrica se sastoji samo od komponenti koraka sa vrijednostima -1 i 1.
Haar je također ortogonalna wavelet transformacija.
Oni su inferiorni u odnosu na DCT, ali ih je lakše izračunati.

Dakle, došla vam je ideja da osmislite vlastitu transformaciju. Zapamtite ovo:

Osnova mora biti ortogonalna.
Sa fiksnom osnovom, ne možete nadmašiti KLT za kvalitet kompresije. U međuvremenu, na stvarnim fotografijama, DCT je skoro jednako dobar.
Koristeći primjer DFT i DST, morate se sjetiti granica.
I zapamtite da DCT ima još jednu dobru prednost - u blizini granica njihovih komponenti, derivati su jednaki nuli, što znači da će prijelaz između susjednih blokova biti prilično gladak.
Fourierove transformacije imaju brze algoritme složenosti O(N*logN), za razliku od jednostavnog izračunavanja: O(N 2).

Neće biti lako, zar ne? Međutim, za neke vrste slika moguće je odabrati bolju osnovu od DCT-a.

2D transformacije

Pokušajmo sada provesti takav eksperiment. Uzmimo, na primjer, dio slike.

Njegov 3D grafikon:

Idemo kroz DCT(N=32) kroz svaki red:

Sada želim da prođete očima kroz svaki stupac dobijenih koeficijenata, odnosno od vrha do dna. Zapamtite da nam je cilj ostaviti što manje vrijednosti, eliminirajući one koje nisu značajne. Vjerovatno ste pogodili da se vrijednosti svake kolone rezultirajućih koeficijenata mogu proširiti na potpuno isti način kao i vrijednosti originalne slike. Niko nas ne ograničava u odabiru matrice ortogonalne transformacije, ali ćemo to učiniti ponovo koristeći DCT(N=8):

Pokazalo se da je koeficijent (0,0) prevelik, pa je na grafikonu smanjen za 4 puta.
Šta se desilo?
U gornjem lijevom uglu su najznačajniji koeficijenti proširenja najznačajnijih koeficijenata.
U donjem lijevom uglu su najbeznačajniji koeficijenti proširenja najznačajnijih koeficijenata.
U gornjem desnom uglu su najznačajniji koeficijenti ekspanzije od najbeznačajnijih koeficijenata.
U donjem desnom uglu su najbeznačajniji koeficijenti proširenja najbeznačajnijih koeficijenata.
Jasno je da se značajnost koeficijenata smanjuje ako se krećete dijagonalno od gornjeg lijevog ka donjem desnom. Šta je važnije: (0, 7) ili (7, 0)? Šta oni uopće znače?
Prvo, po redovima: A 0 = (EX T) T = XE T (transponirano, pošto je formula A=EX za kolone), zatim po kolonama: A=EA 0 = EXE T . Ako pažljivo izračunate, dobit ćete formulu:

Dakle, ako se vektor razloži na sinusoide, tada se matrica razlaže na funkcije oblika cos(ax)*cos(by). Svaki blok 8x8 u JPEG-u predstavljen je kao zbir 64 funkcije oblika:

Na Wikipediji i drugim izvorima takve su funkcije predstavljene u prikladnijem obliku:

Stoga su koeficijenti (0, 7) ili (7, 0) podjednako korisni.
Međutim, u stvari ovo je obična jednodimenzionalna dekompozicija na 64 64-dimenzionalne baze. Sve gore navedeno se ne odnosi samo na DCT, već i na bilo koju ortogonalnu dekompoziciju. Postupajući po analogiji, u opštem slučaju dobijamo N-dimenzionalnu ortogonalnu transformaciju.
A evo i 2D transformacije rakuna (DCT 256x256). Opet sa vrijednostima resetiranim na nulu. Brojevi - broj nenuliranih koeficijenata od svih (zadržane su najznačajnije vrijednosti koje se nalaze u trouglastom području u gornjem lijevom uglu).

Zapamtite da se koeficijent (0, 0) naziva DC, a preostalih 63 naziva se AC.

Odabir veličine bloka

Prijatelj pita zašto JPEG koristi 8x8 particije. Iz odgovora koji nije glasao:

DCT tretira blok kao da je periodičan i mora rekonstruisati rezultujući skok na granicama. Ako uzmete blokove 64x64, najvjerovatnije ćete imati ogroman skok na granicama i trebat će vam puno visokofrekventnih komponenti da to rekonstruišete na zadovoljavajuću preciznost

Kao, DCT dobro radi samo na periodičnim funkcijama, a ako krenete na veliko, vjerovatno ćete dobiti ogroman skok na granicama bloka i trebat će vam puno visokofrekventnih komponenti da to pokrijete. Ovo nije istina! Ovo objašnjenje je vrlo slično DFT-u, ali ne i DCT-u, jer savršeno pokriva takve skokove s prvim komponentama.
Na istoj stranici je odgovor iz MPEG FAQ, sa glavnim argumentima protiv velikih blokova:

Mali profit kada se podijeli na velike blokove.
Povećana računska složenost.
Velika vjerovatnoća velika količina oštre granice u jednom bloku, što će uzrokovati Gibbsov efekat.

Predlažem da ovo sami istražite. Počnimo sa prvo.

Horizontalna os prikazuje udio prvih nenuliranih koeficijenata. Vertikalno - standardna devijacija piksela od originala. Maksimalno moguće odstupanje se uzima kao jedan. Naravno, jedna slika očigledno nije dovoljna za presudu. Osim toga, ne ponašam se sasvim ispravno, jednostavno resetujem na nulu. U stvarnom JPEG-u, ovisno o matrici kvantizacije, samo male vrijednosti visokofrekventnih komponenti se nule. Stoga, sljedeći eksperimenti i zaključci imaju za cilj da iznesu principe i obrasce.
Možete uporediti podjelu na različite blokove sa 25 posto koeficijenata lijevo (s lijeva na desno, zatim s desna na lijevo):

Veliki blokovi nisu prikazani, jer se vizualno gotovo ne razlikuju od 32x32. Sada pogledajmo apsolutnu razliku u odnosu na originalnu sliku (pojačana 2 puta, inače ništa nije vidljivo):

8x8 daje najbolji rezultat nego 4x4. Dalje povećanje veličine više ne pruža jasno vidljivu prednost. Iako bih ozbiljno razmotrio 16x16 umjesto 8x8: povećanje složenosti za 33% (više o složenosti u sljedećem paragrafu) daje malo, ali još uvijek vidljivo poboljšanje za isti broj koeficijenata. Međutim, izbor 8x8 izgleda sasvim razuman i može biti zlatna sredina. JPEG je objavljen 1991. Mislim da je takva kompresija bila veoma teška za procesore tog vremena.

Sekunda argument. Jedna stvar koju treba imati na umu je da će povećanje veličine bloka zahtijevati više proračuna. Procijenimo koliko. Složenost konverzije, kao što već dobro znamo: O(N 2), budući da se svaki koeficijent sastoji od N članova. Ali u praksi se koristi efikasan algoritam brze Fourierove transformacije (FFT). Njegov opis je izvan okvira ovog članka. Njegova složenost: O(N*logN). Za dvodimenzionalno proširenje morate ga koristiti dva puta N puta. Dakle, složenost 2D DCT je O(N 2 logN). Sada uporedimo složenost izračunavanja slike s jednim blokom i nekoliko malih:

Jedan blok (kN)x(kN): O((kN) 2 log(kN)) = O(k 2 N 2 log(kN))
k*k blokova N*N: O(k 2 N 2 logN)

To znači da je, na primjer, proračun za particiju 64x64 dvostruko složeniji od particije 8x8.

Treće argument. Ako imamo oštru granicu boja na slici, to će utjecati na cijeli blok. Možda bi bilo bolje da ovaj blok bude dovoljno mali, jer u mnogim susjednim blokovima takve granice vjerovatno više neće biti. Međutim, daleko od granica, slabljenje se događa prilično brzo. Osim toga, sama granica će izgledati bolje. Provjerimo to na primjeru s velikim brojem kontrastnih prijelaza, opet sa samo četvrtinom koeficijenata:

Iako se distorzija blokova 16x16 proteže dalje od one kod 8x8, slova su glatkija. Dakle, samo prva dva argumenta su me uvjerila. Ali nekako mi se više sviđa divizija 16x16.

Kvantizacija

U ovom trenutku imamo gomilu 8x8 matrica sa kosinusnim koeficijentima transformacije. Vrijeme je da se riješite beznačajnih koeficijenata. Postoji elegantnije rešenje od jednostavnog resetovanja poslednjih koeficijenata na nulu, kao što smo uradili gore. Nismo zadovoljni ovom metodom, jer se nenulte vrijednosti pohranjuju s pretjeranom preciznošću, a među onima koji nisu imali sreće moglo bi biti i prilično važnih. Rješenje je korištenje matrice za kvantizaciju. Gubici nastaju upravo u ovoj fazi. Svaki Fourier koeficijent je podijeljen sa odgovarajućim brojem u matrici kvantizacije. Pogledajmo primjer. Uzmimo prvi blok od našeg rakuna i izvršimo kvantizaciju. JPEG specifikacija pruža standardnu matricu:

Standardna matrica odgovara 50% kvaliteta u FastStone i IrfanView. Ova tabela je odabrana u smislu ravnoteže između kvaliteta i omjera kompresije. Mislim da je vrijednost za DC koeficijent veća od njegovih susjeda zbog činjenice da DCT nije normaliziran i prva vrijednost je veća nego što bi trebala biti. Visokofrekventni koeficijenti su jače grublji zbog manje važnosti. Mislim da se takve matrice sada rijetko koriste, jer je pogoršanje kvaliteta jasno vidljivo. Niko ne zabranjuje korišćenje vaše tabele (sa vrednostima od 1 do 255)
Tokom dekodiranja dolazi do obrnutog procesa - kvantizirani koeficijenti se množe pojam po član vrijednostima matrice kvantizacije. Ali pošto smo zaokružili vrijednosti, nećemo moći precizno vratiti originalne Fourierove koeficijente. Što je veći broj kvantizacije, veća je greška. Dakle, rekonstruisani koeficijent je samo najbliži višekratnik.
Drugi primjer:

A za desert uzmite u obzir 5% kvaliteta (kada kodirate u Fast Stone).

Kada vratimo ovaj blok, dobićemo samo prosječnu vrijednost plus vertikalni gradijent (zbog očuvane vrijednosti -1). Ali za njega se pohranjuju samo dvije vrijednosti: 7 i -1. Ništa bolja situacija nije ni sa ostalim blokovima, evo restaurirane slike:

Inače, oko 100% kvaliteta. Kao što možete pretpostaviti, u ovom slučaju matrica kvantizacije se u potpunosti sastoji od jedinica, odnosno ne dolazi do kvantizacije. Međutim, zbog zaokruživanja koeficijenata na najbliži cijeli broj, ne možemo precizno vratiti originalnu sliku. Na primjer, rakun je zadržao 96% piksela tačno, ali je 4% bilo manje za 1/256. Naravno, takva "izobličenja" se ne mogu uočiti vizuelno.
Ili možete pogledati matrice kvantizacije raznih kamera.

Kodiranje

Prije nego što krenemo dalje, moramo koristiti jednostavnije primjere da bismo razumjeli kako možemo komprimirati rezultirajuće vrijednosti.

Primjer 0(za zagrevanje)
Zamislite takvu situaciju da vam je prijatelj kod kuće zaboravio komad papira sa spiskom i sada traži da ga diktirate telefonom (drugih načina komunikacije nema).
Lista:

d9rg3
wfr43gt
wfr43gt
d9rg3
d9rg3
d9rg3
wfr43gt
d9rg3

Kako biste olakšali svoj zadatak? Nemate posebnu želju da bolno diktirate sve ove riječi. Ali postoje samo dva i ponavljaju se. Stoga jednostavno nekako diktirate prve dvije riječi i slažete se da ćete od sada prvu riječ zvati “d9rg3”, a drugu “wfr43gt”. Tada će biti dovoljno da izdiktirate: 1, 2, 2, 1, 1, 1, 2, 1.

Riječi ćemo označiti kao A, B, C... i nazvati ih simbolima. Štaviše, pod simbolom se može sakriti bilo šta: slovo abecede, riječ ili nilski konj u zoološkom vrtu. Glavna stvar je da identični simboli odgovaraju identičnim konceptima, a različiti odgovaraju različitim. Budući da je naš zadatak efikasno kodiranje (kompresija), radit ćemo sa bitovima, jer su to najmanje jedinice predstavljanja informacija. Stoga, napišimo listu kao ABBAAABA. Umjesto "prve riječi" i "druge riječi" mogu se koristiti bitovi 0 i 1. Tada se ABBAAABA kodira kao 01100010 (8 bitova = 1 bajt).

Primjer 1
Kodiranje ABC.
Nemoguće je povezati 3 različita znaka (A, B, C) sa 2 moguće vrijednosti bita (0 i 1). A ako je tako, onda možete koristiti 2 bita po simbolu. Na primjer:

O: 00
B:01
C: 10

Niz bitova povezanih sa simbolom će se zvati kod. ABC će biti kodiran ovako: 000110.

Primjer 2
Kodirajte AAAAAABC.
Upotreba 2 bita po karakteru A izgleda pomalo rasipnički. Šta ako probate ovo:

C: 00

Kodirana sekvenca: 000000100.
Očigledno, ova opcija nije prikladna, jer nije jasno kako dekodirati prva dva bita ove sekvence: kao AA ili kao C? Vrlo je rasipno koristiti bilo kakav separator između kodova, razmislit ćemo o tome kako zaobići ovu prepreku na drugačiji način. Dakle, greška je zbog činjenice da kod C počinje kodom A. Ali mi smo odlučni da kodiramo A sa jednim bitom, čak i ako B i C imaju po dva. Na osnovu ove želje, A dajemo kod 0. Tada kodovi B i C ne mogu početi sa 0. Ali mogu početi sa 1:

B: 10
C: 11

Slijed je kodiran ovako: 0000001011. Pokušajte ga mentalno dekodirati. Ovo možete učiniti samo na jedan način.
Razvili smo dva zahtjeva za kodiranje:

Što je veća težina simbola, to bi njegov kod trebao biti kraći. I obrnuto.
Za nedvosmisleno dekodiranje, kod karaktera ne može početi kodom bilo kojeg drugog znaka.

Očigledno, redosled likova nije bitan, zanima nas samo učestalost njihovog pojavljivanja. Stoga je svaki simbol povezan s brojem koji se naziva težina. Težina simbola može biti sljedeća: relativna veličina, koji odražava udio njegovog pojavljivanja, i apsolutni, jednak broju znakova. Glavna stvar je da su težine proporcionalne pojavljivanju simbola.

Primjer 3
Razmotrimo opći slučaj za 4 simbola s bilo kojom težinom.

A:pa
B:pb
C:pc
D:pd

Bez gubitka opštosti, stavimo pa ≥ pb ≥ pc ≥ pd. Postoje samo dvije opcije koje se fundamentalno razlikuju po dužini koda:

Koji je poželjniji? Da biste to učinili, morate izračunati rezultirajuće dužine kodiranih poruka:
W1 = 2*pa + 2*pb + 2*pc + 2*pd
W2 = pa + 2*pb + 3*pc + 3*pd
Ako je W1 manji od W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc+pd)< 0 =>pa< pc+pd.
Ako se C i D zajedno javljaju češće od ostalih, tada njihov zajednički vrh prima najkraći jednobitni kod. U suprotnom, jedan bit ide znaku A. To znači da se unija karaktera ponaša kao nezavisni karakter i ima težinu jednaku zbroju ulaznih znakova.
Općenito, ako je p težina znaka predstavljena dijelom njegovog pojavljivanja (od 0 do 1), onda je najbolja dužina koda s=-log 2 p.
Pogledajmo ovo jednostavan slučaj(lako ga je zamisliti u obliku drveta). Dakle, trebamo kodirati 2 s karaktera sa jednakim težinama (1/2 s). Zbog jednakosti težina, dužine kodova će biti iste. Svaki znak će zahtijevati s bitova. To znači da ako je težina simbola 1/2 s, onda je njegova dužina s. Ako zamenimo težinu sa p, dobićemo dužinu koda s=-log 2 p. To znači da ako se jedan znak pojavljuje dva puta češće od drugog, tada će dužina njegovog koda biti za jedan bit duža. Međutim, ovaj zaključak je lako izvući ako se sjetite da vam dodavanje jednog bita omogućava udvostručenje broja mogućih opcija.
I još jedno zapažanje - dva simbola s najmanjom težinom uvijek imaju najveće, ali jednake dužine kodovi Štaviše, njihovi bitovi, osim posljednjeg, su isti. Ako to nije tačno, onda bi se barem jedan kod mogao skratiti za 1 bit bez razbijanja prefiksa. To znači da dva simbola sa najmanjom težinom u kodnom stablu imaju zajedničkog roditelja na višem nivou. Ovo možete vidjeti u primjeru C i D iznad.

Primjer 4
Pokušajmo riješiti sljedeći primjer, na osnovu zaključaka dobijenih u prethodnom primjeru.

Svi simboli su sortirani po opadajućem redoslijedu po težini.
Poslednja dva simbola se kombinuju u grupu. Ovoj grupi se dodeljuje težina jednaka zbiru težina ovih elemenata. Ova grupa učestvuje u algoritmu zajedno sa simbolima i drugim grupama.

Koraci se ponavljaju dok ne ostane samo jedna grupa. Unutar svake grupe, jednom karakteru (ili podgrupi) je dodijeljen bit 0, a drugom karakterni bit 1.
Ovaj algoritam se zove Huffmanovo kodiranje.
Ilustracija prikazuje primjer sa 5 znakova (A: 8, B: 6, C: 5, D: 4, E: 3). Desno je težina simbola (ili grupe).

Kodiramo koeficijente

Hajdemo nazad. Sada imamo mnogo blokova sa 64 koeficijenta u svakom, koje treba nekako sačuvati. Najjednostavnije rješenje je korištenje fiksnog broja bitova po koeficijentu - očito neuspješno. Napravimo histogram svih dobijenih vrijednosti (tj. ovisnost broja koeficijenata o njihovoj vrijednosti):

Imajte na umu - skala je logaritamska! Možete li objasniti razlog za pojavu klastera vrijednosti koje prelaze 200? Ovo su DC koeficijenti. Budući da se jako razlikuju od ostalih, ne čudi što su kodirani zasebno. Evo samo DC:

Imajte na umu da oblik grafa podsjeća na grafove iz najranijih eksperimenata uparivanja i utrostručenja piksela.
Općenito, vrijednosti DC koeficijenta mogu varirati od 0 do 2047 (tačnije od -1024 do 1023, budući da JPEG oduzima 128 od svih originalnih vrijednosti, što odgovara oduzimanju 1024 od DC) i raspoređuje se prilično ravnomjerno s malim vrhovima. Dakle, Huffmanovo kodiranje ovdje neće puno pomoći. I zamislite koliko će veliko stablo kodiranja biti! I tokom dekodiranja morat ćete tražiti značenje u njemu. Veoma je skupo. Razmišljamo dalje.
DC koeficijent je prosječna vrijednost bloka 8x8. Zamislimo gradijentni prijelaz (iako nije idealan), koji se često nalazi na fotografijama. Same vrijednosti DC bit će različite, ali će predstavljati aritmetičku progresiju. To znači da će njihova razlika biti manje-više konstantna. Napravimo histogram razlika:

Ovo je bolje, jer su vrijednosti uglavnom koncentrisane oko nule (ali Huffmanov algoritam će opet dati preveliko stablo). Male vrijednosti (od apsolutna vrijednost) su česte, velike su rijetke. A budući da male vrijednosti zauzimaju nekoliko bitova (ako uklonite vodeće nule), jedno od pravila kompresije dobro funkcionira: dodijelite simbole s velikim težinama kratki kodovi(i obrnuto). Trenutno smo ograničeni nepoštovanjem još jednog pravila: nemogućnosti nedvosmislenog dekodiranja. Generalno, ovaj problem se može riješiti na sljedeće načine: zamarati se kodom za razdvajanje, naznačiti dužinu koda, koristiti prefiksne kodove (već ih znate - to je slučaj kada nijedan kod ne počinje drugim). Idemo sa jednostavnom drugom opcijom, tj. svaki koeficijent (tačnije, razlika između susjednih) biće napisan ovako: (dužina)(vrijednost), prema ovom znaku:

To jest, pozitivne vrijednosti su direktno kodirane njihovim binarnim prikazom, a negativne vrijednosti su kodirane na isti način, ali s vodećim 1 zamijenjenim 0. Ostaje odlučiti kako kodirati dužine. Pošto postoji 12 mogućih vrijednosti, 4 bita se mogu koristiti za pohranjivanje dužine. Ali ovdje je bolje koristiti Huffmanovo kodiranje.

Najviše je vrijednosti sa dužinama 4 i 6, tako da su dobili najkraće kodove (00 i 01).

Može se postaviti pitanje: zašto, u primjeru, vrijednost 9 ima šifru 1111110, a ne 1111111? Na kraju krajeva, možete bezbedno podići "9" na viši nivo, pored "0"? Činjenica je da u JPEG-u ne možete koristiti kod koji se sastoji samo od jedan - takav je kod rezerviran.
Postoji još jedna karakteristika. Kodovi dobijeni opisanim Huffman algoritmom možda se neće poklopiti u bitovima sa kodovima u JPEG formatu, iako će njihove dužine biti iste. Koristeći Huffman algoritam, dobiju se dužine kodova, a sami kodovi se generiraju (algoritam je jednostavan - počnite s kratkim kodovima i dodajte ih jedan po jedan u stablo što je više moguće lijevo, čuvajući svojstvo prefiksa ). Na primjer, za stablo iznad liste je pohranjeno: 0,2,3,1,1,1,1,1. I, naravno, pohranjuje se lista vrijednosti: 4,6,3,5,7,2,8,1,0,9. Tokom dekodiranja, kodovi se generišu na isti način.

Sada je sve u redu. Shvatili smo kako se DC pohranjuju:
[Huffmanov kod za dužinu DC razlike (u bitovima)]
gdje je DC diff = DC struja - DC prethodni

Pogledajmo AC:

Pošto je graf vrlo sličan grafu za DC razlike, princip je isti: [Huffmanov kod za AC dužinu (u bitovima)]. Ali ne baš! Budući da je skala na grafikonu logaritamska, nije odmah uočljivo da ima otprilike 10 puta više nultih vrijednosti od vrijednosti 2, sljedeće po učestalosti. To je razumljivo – nisu svi preživjeli kvantizaciju. Vratimo se na matricu vrijednosti dobijenih tokom faze kvantizacije (koristeći FastStone matricu kvantizacije, 90%).

Pošto postoji mnogo grupa uzastopnih nula, nameće se ideja - da se zapiše samo broj nula u grupi. Ovaj algoritam kompresije se zove RLE (Run-length encoding). Ostaje da se otkrije smjer obilaznice "uzastopnih" - ko je iza koga? Pisanje s lijeva na desno i odozgo prema dolje nije vrlo efikasno, jer su koeficijenti različiti od nule koncentrisani blizu gornjeg lijevog ugla, a što je bliže donjem desnom, to je više nula.

Stoga JPEG koristi redoslijed nazvan "cik-cak", koji je prikazan na lijevoj slici. Ova metoda dobro razlikuje grupe nula. Na desnoj slici je alternativna metoda zaobilaženja, koja nije vezana za JPEG, ali sa zanimljivim imenom (dokaz). Može se koristiti u MPEG-u za prepletenu video kompresiju. Izbor algoritma prelaska ne utiče na kvalitet slike, ali može povećati broj kodiranih grupa nula, što na kraju može uticati na veličinu datoteke.
Izmijenimo naš unos. Za svaki AC koeficijent koji nije nula:
[Broj nula prije AC][Huffman kod za dužinu AC (u bitovima)]
Mislim da možete odmah reći da je broj nula također savršeno kodiran od strane Huffmana! Ovo je vrlo blizak i dobar odgovor. Ali može se malo optimizirati. Zamislite da imamo neki koeficijent AC, prije kojeg je bilo 7 nula (naravno, ako je napisano cik-cak redoslijedom). Ove nule su duh vrijednosti koji nije preživio kvantizaciju. Najvjerovatnije je i naš koeficijent bio jako oštećen i postao je mali, što znači da je njegova dužina kratka. To znači da su broj nula ispred AC i dužina AC zavisne veličine. Stoga to pišemo ovako:
[Huffmanov kod za (Broj nula prije AC, dužina AC (u bitovima)]
Algoritam kodiranja ostaje isti: oni parovi (broj nula prije AC, dužina AC) koji se pojavljuju često će dobiti kratke kodove i obrnuto.

Za ove parove i Hafmanovo stablo gradimo histogram količinske zavisnosti.

Dugačak "planinski greben" potvrđuje našu pretpostavku.

Karakteristike implementacije u JPEG:
Takav par zauzima 1 bajt: 4 bita za broj nula i 4 bita za dužinu AC. 4 bita su vrijednosti od 0 do 15. Za dužinu AC ovo je više nego dovoljno, ali može li biti više od 15 nula? Tada se koristi više parova. Na primjer, za 20 nula: (15, 0)(5, AC). To jest, 16. nula je kodirana kao koeficijent koji nije nula. Pošto uvijek ima puno nula blizu kraja bloka, par (0,0) se koristi nakon posljednjeg koeficijenta različitog od nule. Ako se naiđe tokom dekodiranja, preostale vrijednosti su 0.

Saznali smo da je svaki blok kodiran i pohranjen u datoteci poput ove:
[Huffmanov kod za dužinu DC razlike]
[Huffmanov kod za (broj nula prije AC 1, dužina AC 1]
…
[Huffmanov kod za (broj nula prije AC n, dužina AC n]
Gdje su AC i koeficijenti AC različiti od nule.

Slika u boji

Način na koji je slika u boji predstavljena zavisi od odabranog modela boja. Jednostavno rješenje je koristiti RGB i kodirati svaki kanal u boji slike odvojeno. Tada se kodiranje neće razlikovati od kodiranja sive slike, samo 3 puta više posla. Ali kompresija slike se može povećati ako se sjetimo da je oko osjetljivije na promjene svjetline od boja. To znači da se boja može pohraniti s većim gubicima od svjetline. RGB nema poseban kanal za osvetljenje. Zavisi od zbira vrijednosti svakog kanala. Stoga se RGB kocka (ovo je prikaz svih mogućih vrijednosti) jednostavno "smjesti" na dijagonalu - što je veća, to je svjetlija. Ali oni se tu ne zaustavljaju - kocka se malo pritisne sa strana i ispada više kao paralelepiped, ali to je samo da se uzmu u obzir karakteristike oka. Na primjer, osjetljiviji je na zelenu nego na plavu. Tako se pojavio model YCbCr.

(Slika sa Intel.com)
Y je komponenta osvjetljenja, Cb i Cr su komponente razlike u plavoj i crvenoj boji. Stoga, ako žele više komprimirati sliku, onda se RGB pretvara u YCbCr, a Cb i Cr kanali se razrjeđuju. Odnosno, podijeljeni su na male blokove, na primjer 2x2, 4x2, 1x2, a sve vrijednosti jednog bloka su prosječne. Ili, drugim riječima, smanjuju veličinu slike za ovaj kanal za 2 ili 4 puta vertikalno i/ili horizontalno.

Svaki 8x8 blok je kodiran (DCT + Huffman), a kodirane sekvence su napisane ovim redoslijedom:

Zanimljivo je da JPEG specifikacija ne ograničava izbor modela, odnosno implementacija enkodera može podijeliti sliku na komponente u boji (kanale) na bilo koji način i svaka će se posebno čuvati. Svjestan sam upotrebe sivih tonova (1 kanal), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Prva tri podržavaju skoro svi, ali postoje problemi sa zadnjim 4-kanalnim. FastStone, GIMP ih podržavaju ispravno i standardno Windows programi, paint.net ispravno izvlači sve informacije, ali onda izbaci 4. crni kanal, pa (Antelle je rekao da to ne bacaju, pročitajte njegove komentare) pokazuju svjetliju sliku. Sa lijeve strane je klasični YCbCr JPEG, sa desne strane je CMYK JPEG:

Ako se razlikuju po boji, ili je vidljiva samo jedna slika, onda najvjerovatnije imate IE (bilo koju verziju) (UPD. u komentarima kažu “ili Safari”). Možete pokušati otvoriti članak u različitim pretraživačima.

I još nešto

Ukratko o dodatnim funkcijama.

Progresivni način rada

Razložimo rezultirajuće tablice DCT koeficijenata u zbir tabela (približno ovako (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20 , -20, 0, 0) + (0, 1, -2, 2, 1)). Prvo kodiramo sve prve pojmove (kao što smo već naučili: Huffman i cik-cak prelazak), zatim drugi, itd. Ovaj trik je koristan kada je internet spor, jer se prvo učitavaju samo DC koeficijenti koji se koriste za konstruisati grubu sliku sa 8x8 “piksela”. Zatim se zaokružuju AC koeficijenti kako bi se precizirao broj. Zatim grube korekcije, pa one preciznije. I tako dalje. Koeficijenti su zaokruženi, jer u ranim fazama učitavanja točnost nije toliko važna, ali zaokruživanje ima pozitivan učinak na dužinu kodova, jer svaka faza koristi svoju Huffmanovu tablicu.

Način rada bez gubitaka

Kompresija bez gubitaka. Nema DCT. Koristi se predviđanje 4. tačke na osnovu tri susedne tačke. Greške predviđanja su Huffman kodirane. Po mom mišljenju, koristi se malo češće nego nikad.

Hijerarhijski način rada

Od slike se kreira nekoliko slojeva različite rezolucije. Prvi grubi sloj se kodira kao i obično, a zatim samo razlika (pročišćavanje slike) između slojeva (pretvara se da je Haar talas). DCT ili Lossless se koristi za kodiranje. Po mom mišljenju, koristi se malo rjeđe nego nikad.

Aritmetičko kodiranje

Huffmanov algoritam proizvodi optimalne kodove na osnovu težine znakova, ali to vrijedi samo za fiksno mapiranje karaktera u kod. Aritmetika nema tako kruto vezivanje, što omogućava korištenje kodova kao da su s razlomkom broja bitova. Tvrdi da smanjuje veličinu datoteke u prosjeku za 10% u odnosu na Huffman. Nije široko rasprostranjeno zbog problema sa patentima, ne podržavaju ga svi.

Nadam se da sada intuitivno razumete JPEG algoritam. Hvala na čitanju!

UPD
vanwin je predložio navođenje korištenog softvera. Sa zadovoljstvom mogu objaviti da je sve dostupno i besplatno:

Python + NumPy + Matplotlib + PIL (jastuk). Glavni alat. Našao sam ga tražeći “Matlab besplatna alternativa”. Predlažem! Čak i ako niste upoznati sa Python-om, za samo nekoliko sati naučićete kako da pravite proračune i pravite prelepe grafikone.
JpegSnoop. Prikazuje detaljne informacije o jpeg datoteci.
yEd. Editor grafikona.
Inkscape. U njemu sam napravio ilustracije, kao što je primjer Huffmanovog algoritma. Pročitao sam nekoliko lekcija, pokazalo se da je super.
Daum Equation Editor. Tražio sam uređivač vizualnih formula, jer nisam baš dobar s Latexom. Daum Equation je dodatak za Chrome koji sam smatrao vrlo zgodnim. Osim bockanja mišem, možete uređivati Latex.
FastStone. Mislim da ga nema potrebe predstavljati.
PicPick. Besplatna alternativa SnagItu. Sjedi u traci, snima screenshot onoga što kažu i gdje to kažu. Plus sve vrste poslastica, kao što su lenjiri, pipete, kutomjeri itd.

Oznake: Dodajte oznake

„Implementacija algoritama

JPEG i JPEG2000"

Završeno:

učenik grupe 819

Ugarov Dmitry

Principi rada JPEG i JPEG2000 algoritama

1. JPEG algoritam

JPEG (Joint Photographic Experts Group) je široko korištena metoda za kompresiju fotografskih slika. Format datoteke koji sadrži komprimirane podatke obično se naziva i JPEG; Najčešće ekstenzije za takve datoteke su .jpeg, .jfif, .jpg, .JPG ili .JPE. Međutim, od njih, .jpg je najpopularnija ekstenzija na svim platformama.

JPEG algoritam je kompresijski algoritam sa gubitkom kvaliteta.

Područje primjene

Format je format kompresije sa gubitkom, tako da je pogrešno misliti da JPEG čuva podatke kao 8 bita po kanalu (24 bita po pikselu). S druge strane, budući da su podaci podvrgnuti kompresiji od strane JPEG format a dekomprimirani podaci su obično predstavljeni u 8 bita po kanalu, ova terminologija se ponekad koristi. Kompresija crno-bijelih polutonskih slika je također podržana.

Prilikom snimanja JPEG datoteke možete odrediti stepen kvaliteta, a time i stepen kompresije, koji se obično navodi u nekim konvencionalnim jedinicama, na primjer, od 1 do 100 ili od 1 do 10. Veći broj odgovara boljem kvalitetu , ali se veličina datoteke povećava. Obično se okom praktički ne percipira razlika u kvaliteti između 90 i 100. Treba imati na umu da se bit-po-bit obnovljena slika uvijek razlikuje od originala. Uobičajena zabluda je to JPEG kvaliteta identičan udjelu pohranjenih informacija.

Faze kodiranja

Proces kompresije JPEG-a uključuje nekoliko koraka:

1. Pretvorite sliku u optimalni prostor boja;

U slučaju upotrebe prostor boja svjetlina/krominacija (YCbCr) postiže najbolji omjer kompresije. U ovoj fazi kodiranja, RGB model boja se pretvara u YCbCr koristeći odgovarajuće odnose:

Y = 0,299*R + 0,587*G + 0,114*B

Cb = - 0,1687*R – 0,3313*G + 0,5*B

Cr = 0,5*R – 0,4187*G – 0,0813*B.
Tokom dekodiranja možete koristiti odgovarajuću inverznu transformaciju:
R = Y + 1,402*Cr

G = Y – 0,34414*Cb – 0,71414*Cr

B = Y + 1,772*Cb.
Napomena o Y,Cb,Cr u ljudskom vizuelnom sistemu:

Oko, posebno mrežnica, ima dvije vrste ćelija kao vizualnih analizatora: ćelije noćnog vida koje percipiraju samo nijanse sive (od svijetlo bijele do tamno crne) i ćelije dnevnog vida koje percipiraju nijansu boja. Prve ćelije, koje proizvode RGB boju, detektuju nivo osvetljenosti sličan vrednosti Y. Druge ćelije, odgovorne za percepciju nijanse, određuju vrednost povezanu sa razlikom u boji.

2. Poduzorkovanje komponenti boja usrednjavanjem grupa piksela;

Većina vizuelnih informacija na koje je ljudsko oko najosjetljivije sastoji se od visokofrekventnih komponenti osvjetljenja u sivim tonovima (Y) YCbCr prostora boja. Druge dvije hromatske komponente (Cb i Cr) sadrže informacije o boji visoke frekvencije na koje je ljudsko oko manje osjetljivo. Stoga se određeni dio može odbaciti i time smanjiti broj piksela koji se uzimaju u obzir za kanale boja.

1) upišite 4:2:0 (kada je slika podijeljena na kvadrate od 2x2 piksela i u svakom od njih svi pikseli primaju iste vrijednosti Cb i Cr kanala, a svjetlina Y ostaje različita za svaki)

2) tip 4:2:2 (kombinacija po komponentama hromatičnosti se javlja samo horizontalno u grupama od dva piksela).

3) Tip 4:4:4 znači da svaki piksel u svakom redu ima svoju jedinstvenu vrijednost Y, Cb i Cr komponenti. (Slika 1 a)

4) tip 4:2:2. Poduzorkovanjem signala hrominacije sa faktorom 2 horizontalno, dobijamo od 4:4:4 YCbCr toka 4:2:2 YCbCr toka. Unos "4: 2: 2" znači da u jednom redu postoje 4 vrijednosti svjetline za 2 vrijednosti hromatike (vidi sliku 1 b). Signal 4:2:2 YCbCr je vrlo malo inferioran u kvalitetu slike u odnosu na 4:4:4 YCbCr signal, ali je potrebna širina pojasa smanjena za 33% od originala.

3. Primjena diskretnih kosinusnih transformacija za smanjenje redundantnosti slikovnih podataka;

Glavna faza algoritma je diskretna kosinusna transformacija (DCT ili DCT), koja je vrsta Fourierove transformacije. Koristi se pri radu sa slikama u različite svrhe, a ne samo u svrhu kompresije. Prijelaz na frekvencijski prikaz vrijednosti piksela omogućava nam da drugačije pogledamo sliku, obradimo je i, što je za nas zanimljivo, komprimiramo je. Štoviše, znajući koeficijente konverzije, uvijek možemo izvršiti suprotnu akciju - vratiti originalnu sliku.

DCT direktno primijenjen na blok (u našem slučaju 8x8 piksela) slike će izgledati ovako:

gdje su x, y prostorne koordinate piksela (0..7),

f(x,y) - vrijednosti piksela originalnog makrobloka (na primjer, svjetlina)

u,v - koordinate piksela u frekvencijskoj predstavi (0..7)

w(u) =1/SQRT(2) za u=0, u ostalim slučajevima w(u)=1 (SQRT - kvadratni korijen)

w(v) =1/SQRT(2) za v=0, u ostalim slučajevima w(v)=1

Ili u matričnom obliku:

4. Kvantizacija svakog bloka DCT koeficijenata korištenjem težinskih funkcija optimiziranih uzimajući u obzir ljudsku vizualnu percepciju;

Diskretna kosinusna transformacija priprema informacije za kompresiju sa gubicima i zaokruživanje. Za svaki element matrice koji se transformiše postoji odgovarajući element matrice kvantizacija. Rezultirajuća matrica se dobiva dijeljenjem svakog elementa matrice koja se transformira odgovarajućim elementom matrice kvantizacije i zatim zaokruživanjem rezultata na najbliži cijeli broj. Prilikom sastavljanja matrice kvantizacije, njeni veliki elementi se nalaze u donjem lijevom uglu, tako da se prilikom dijeljenja njima podaci u ovom kutu nakon diskretne kosinusne transformacije (upravo oni čije će zaokruživanje biti manje bolno) grublje zaokružuju. Odnosno izgubljene informacije manje važan za nas od preostalog.

5. Sekundarni stupanj kompresije

Posljednja faza JPEG kodera je kodiranje rezultirajuće matrice.

5.1 Cik-cak permutacija 64 DCT koeficijenta

Dakle, nakon što smo izvršili DCT transformaciju na bloku vrijednosti 8x8, imamo novi blok 8x8. Zatim se ovaj blok 8x8 prelazi u cik-cak obrascu ovako:

(Brojevi u bloku 8x8 označavaju redoslijed kojim skeniramo 2-dimenzionalnu matricu 8x8)

0, 1, 5, 6,14,15,27,28,

2, 4, 7,13,16,26,29,42,

3, 8,12,17,25,30,41,43,

9,11,18,24,31,40,44,53,

10,19,23,32,39,45,52,54,

20,22,33,38,46,51,55,60,

21,34,37,47,50,56,59,61,

35,36,48,49,57,58,62,63

Kao što vidite, prvo je gornji lijevi ugao (0,0), zatim vrijednost na (0,1), zatim (1,0), pa (2,0), (1,1), (0, 2), (0,3), (1,2), (2,1), (3,0) itd.

Nakon što prođemo cik-cak kroz matricu 8x8, sada imamo vektor sa 64 koeficijenta (0..63).Poenta ovog cik-cak vektora je da gledamo kroz 8x8 DCT koeficijente u redoslijedu povećanja prostornih frekvencija. Dakle, dobijamo vektor sortiran po kriterijumima prostorne frekvencije: prva vrednost na vektoru (indeks 0) odgovara najnižoj frekvenciji na slici - označava se terminom DC. Kako se indeks na vektoru povećava, dobijamo vrijednosti koje odgovaraju višim frekvencijama (vrijednost sa indeksom 63 odgovara amplitudi najveće frekvencije u bloku 8x8). Ostali DCT koeficijenti su označeni sa AC.

5.2 RunLength nulto kodiranje (RLE)

Sada imamo vektor sa dugim nizom nula. Ovo možemo koristiti kodiranjem uzastopnih nula. VAŽNO: Kasnije ćete vidjeti zašto, ali ovdje preskačemo kodiranje prvog vektorskog koeficijenta (DC koeficijenta), koji je kodiran drugačije. Zamislite originalni vektor 64 kao vektor 63 (ovo je vektor 64 bez prvog koeficijenta)

Recimo da imamo 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, samo 0,... .0

Evo kako se radi RLC JPEG kompresija za ovaj primjer:

(0,57); (0,45); (4,23); (1,-30); (0,-16); (2.1); EOB

Kao što možete vidjeti, za svaku vrijednost različitu od 0 kodiramo broj uzastopnih VODEĆIH nula prije vrijednosti, a zatim dodajemo vrijednost. Još jedna napomena: EOB je kratka forma za kraj bloka, to je posebna kodirana vrijednost (marker). Ako smo došli do pozicije na vektoru od koje imamo samo vektorske nule do kraja, dodijelit ćemo tu poziciju sa EOB-om i kompletnom RLC kompresijom kvantiziranog vektora.

[Imajte na umu da ako kvantizirani vektor nije nul-terminiran (posljednji element nije 0), nećemo imati EOB token.]

(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); (0,0)

Još jedna OSNOVNA stvar: Recimo negdje na kvantiziranom vektoru koji imamo:

57, osamnaest nula, 3, 0,0 ,0,0 2, trideset tri nule, 895, EOB

JPG Huffman kodiranje postavlja ograničenje da broj vodećih nula mora biti kodiran kao 4-bitna vrijednost ne može premašiti 15.

Dakle, prethodni primjer bi trebao biti kodiran kao:

(0,57); (15,0) (2,3); (4,2); (15,0) (15,0) (1,895), (0,0)

(15,0) je posebna kodirana vrijednost koja označava da slijedi 16 uzastopnih nula.

5.3 Završni korak - Huffmanovo kodiranje

Prvo VAŽNA napomena: Umjesto pohranjivanja stvarne vrijednosti, JPEG standard navodi da pohranjujemo minimalnu veličinu bita na kojoj možemo zadržati ovu vrijednost (ovo se zove kategorija ove vrijednosti), a zatim bit-kodirani prikaz ove vrijednosti Volim ovo:

7,..,-4,4,..,7 3 000,001,010,011,100,101,110,111

15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111

31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111

63,..,-32,32,..,63 6 .

127,..,-64,64,..,127 7 .

255,..,-128,128,..,255 8 .

511,..,-256,256,..,511 9 .

1023,..,-512,512,..,1023 10 .

2047,..,-1024,1024,..,2047 11 .

4095,..,-2048,2048,..,4095 12 .

8191,..,-4096,4096,..,8191 13 .

16383,..,-8192,8192,..,16383 14 .

32767,..,-16384,16384,..,32767 15 .

Nakon toga za prethodni primjer:

(0,57); (0,45); (4,23); (1,-30); (0,-8); (2,1); (0,0)

kodirajmo samo desnu vrijednost ovih parova, osim parova koji su posebni tokeni poput (0,0) ili (ako moramo imati) (15,0)

45, na sličan način, bilo bi kodirano kao (6.101101)

30 -> (5,00001)

A sada ćemo ponovo napisati niz parova:

(0,6), 111001; (0,6), 101101; (4,5), 10111; (1,5), 00001; (0,4), 0111; (2,1), 1; (0,0)

Parovi od 2 vrijednosti zatvoreni u zagradama mogu biti predstavljeni u bajtu, jer u stvari svaka od 2 vrijednosti može biti predstavljena u 4-bitnom komadu (broj vodećih nula je uvijek manji od 15 i isti kao kategorija [brojevi kodirani u JPG datoteci - u području -32767..32767]). U ovom bajtu, visoki bit predstavlja broj prethodnih nula, a niži bit predstavlja kategoriju nove vrijednosti koja nije 0.

Posljednji korak kodiranja je da Huffman kodira ovaj bajt, a zatim snimi u JPG datoteku, kao tok bitova, Huffmanov kod ovog bajta, nakon čega slijedi prikaz ovog broja u bitovima.

Na primjer, za bajt 6 (ekvivalentno (0,6)) imamo Huffman kod = 111000;

21 = (1,5) - 11111110110

4 = (0,4) - 1011

33 = (2,1) - 11011

0 = EOB= (0,0) - 1010

Konačni bitstream napisan u JPG datoteci na disk za prethodni primjer je 63 koeficijenta (zapamtite da smo preskočili prvi koeficijent) -

111000 111001 111000 101101 1111111110011001 10111 11111110110 00001

1011 0111 11011 1 1010
Prednosti i nedostaci

Nedostaci formata uključuju činjenicu da se pri visokim nivoima kompresije, struktura blok podataka osjeća sama po sebi, slika je "podijeljena na kvadrate" (svaki veličine 8x8 piksela). Ovaj efekat je posebno primetan u oblastima sa niskom prostornom frekvencijom (glatki prelazi slike, na primer, vedro nebo). U područjima s visokom prostornom frekvencijom (na primjer, kontrastne ivice slike), pojavljuju se karakteristični "artefakti" - nepravilna struktura piksela s izobličenom bojom i/ili svjetlinom. Osim toga, mali detalji u boji nestaju sa slike. To takođe ne treba zaboraviti ovaj format ne podržava transparentnost.

Međutim, uprkos svojim nedostacima, JPEG je postao veoma raširen zbog svog visokog stepena kompresije u odnosu na alternative koje su postojale u vreme njegovog uvođenja.

2. JPEG2000 algoritam

Algoritam JPEG-2000 razvila je ista grupa stručnjaka za fotografiju koja je razvila JPEG. Formiranje JPEG-a kao međunarodnog standarda završeno je 1992. godine. Godine 1997. postalo je jasno da je potreban novi, fleksibilniji i moćniji standard, koji je finaliziran do zime 2000. godine.

Glavne razlike između algoritma u JPEG 2000 i algoritma u JPEG-u su sljedeće:

1) Bolji kvalitet slike sa visokim stepenom kompresije. Ili, što je ista stvar, veći omjer kompresije sa istim kvalitetom za visoke omjere kompresije. U stvari, to znači primjetno smanjenje veličine grafike "web kvaliteta" koju koristi većina web lokacija.

2)Podrška za kodiranje pojedinačnih područja sa najbolji kvalitet. Poznato je da su određena područja slike kritična za ljudsku percepciju (na primjer, oči na fotografiji), dok se kvalitet drugih može žrtvovati (na primjer, pozadina). Sa “ručnom” optimizacijom, stepen kompresije se povećava sve dok se kvalitet ne izgubi u nekom važnom dijelu slike. Sada postaje moguće postaviti kvalitet u kritična područja, jače kompresujući druga područja, tj. dobijamo još veći konačni omjer kompresije uz subjektivno jednak kvalitet slike.

3) Glavni algoritam kompresije je zamijenjen waveletom. Pored navedenog povećanja omjera kompresije, ovo je omogućilo da se riješimo blokade od 8 piksela koja se javlja kada se poveća omjer kompresije. Osim toga, glatki razvoj slike sada je u početku uključen u standard (progresivni JPEG, koji se aktivno koristi na Internetu, pojavio se mnogo kasnije od JPEG-a).

4) Za povećanje omjera kompresije, algoritam koristi aritmetičku kompresiju. U početku je JPEG standard uključivao i aritmetičku kompresiju, ali je to kasnije zamijenjeno manje efikasnom Huffman kompresijom jer je aritmetička kompresija bila zaštićena patentima. Sada je glavni patent istekao i postoji prilika za poboljšanje algoritma.

5) Podržava kompresiju bez gubitaka. Pored uobičajene kompresije sa gubicima, novi JPEG će sada podržavati kompresiju bez gubitaka. Tako postaje moguće koristiti JPEG za kompresiju medicinskih slika, u štampi, uz čuvanje teksta za prepoznavanje od strane OCR sistema itd.

6) Podržava kompresiju jednobitnih (2-bojnih) slika. Za čuvanje jednobitnih slika (crteži mastilom, skenirani tekst, itd.), GIF format je ranije bio široko preporučljiv, jer je DCT kompresija vrlo neefikasna za slike sa oštrim prelazima boja. U JPEG-u, kada se kompresuje, 1-bitna slika je konvertovana u 8-bitnu, tj. povećao za 8 puta, nakon čega je učinjen pokušaj kompresije, često manje od 8 puta. Sada možemo preporučiti JPEG 2000 kao univerzalni algoritam.

7) Transparentnost je podržana na nivou formata. Sada će biti moguće glatko primijeniti pozadinu prilikom kreiranja WWW stranica ne samo u GIF, već iu JPEG 2000. Osim toga, nije podržan samo 1 bit transparentnosti (piksel je transparentan/neproziran), već i poseban kanal, koji će vam omogućiti da postavite glatki prijelaz sa neprozirne slike na prozirnu pozadinu.

Pored toga, nivo formata podržava uključivanje informacija o autorskim pravima u sliku, podršku za toleranciju grešaka bitova tokom prenosa i emitovanja, i može se tražiti za dekompresiju ili obradu eksterna sredstva(plug-ins), možete uključiti njegov opis, informacije o pretraživanju, itd. u sliku.

Faze kodiranja

Proces kompresije JPEG2000 uključuje nekoliko koraka:

1. Pretvorite sliku u optimalni prostor boja.
U ovoj fazi kodiranja, RGB model boja se pretvara u YUV koristeći odgovarajuće odnose:

Prilikom dekompresije primjenjuje se odgovarajuća inverzna transformacija:

2. Diskretna talasna transformacija.

Diskretno wavelet konverzija(DWT) takođe može biti dva tipa - za slučaj kompresije sa gubicima i za kompresiju bez gubitaka.

Ova transformacija u jednodimenzionalnom slučaju je skalarni proizvod odgovarajućih koeficijenata i niza vrijednosti. Ali zato mnogi koeficijenti su nula, tada se direktna i inverzna wavelet transformacija može napisati sljedećim formulama (za transformaciju ekstremnih elemenata linije koristi se njeno proširenje za 2 piksela u svakom smjeru, čije su vrijednosti simetrične s vrijednosti elemenata linije u odnosu na njene ekstremne piksele):
y(2*n + 1) = x(2*n + 1) - (int)(x(2*n) + x(2*n + 2)) / 2

y(2*n) = x(2*n) + (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4

i obrnuto

x(2*n) = y(2*n) - (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4

x(2*n + 1) = y(2*n + 1) + (int)(x(2*n) + x(2*n + 2)) / 2.

3. Kvantizacija koeficijenata.

Baš kao i JPEG algoritam, kvantizacija se koristi kada se slika kodira u JPEG2000 format. Diskretna talasna transformacija, kao i njen analog, sortira koeficijente po frekvenciji. Ali, za razliku od JPEG-a, u novom formatu postoji jedna matrica kvantizacije za cijelu sliku.

4. Sekundarni stupanj kompresije

. Kao i JPEG, posljednji korak u algoritmu kompresije u novom formatu je kodiranje bez gubitaka. Ali, za razliku od prethodnog formata, JPEG2000 koristi algoritam aritmetičke kompresije.

Implementacija softvera

U ovom radu implementirani su algoritmi JPEG i JPEG2000. Oba algoritma implementiraju unaprijed i obrnuto kodiranje (posljednja faza sekundarne kompresije je odsutna). JPEG proračun traje dosta vremena (oko 30 sekundi) zbog "direktnog" izračunavanja DCT-a. Ako trebate povećati brzinu rada, prvo bi trebali izračunati DCT matricu (promjene treba izvršiti u DCT klasi).

Pređimo na program:

Nakon pokretanja, pojavljuje se prozor gdje

a možete ga sačuvati klikom na dugme (2) i unosom željenog imena u dijalog box.

Uz dovoljno veliki faktor kvalitete, slika će se uvelike promijeniti. Ako je ovo JPEG algoritam, tada će blokovi veličine 8x8 biti jasno vidljivi (u slučaju JPEG2000 algoritma, neće biti podjele blokova)

prije:

nakon:

Koju metodu kompresije koristi jpeg algoritam? JPEG kompresuje bolje od GIF-a

Algoritmi kompresije bez gubitaka

RLE algoritam

Algoritmi rječnika

Statistički algoritmi kodiranja

Huffmanov algoritam

Aritmetičko kodiranje

Marker: SOF0 - Osnovni DCT

Marker: DHT (Huffmanova tablica)

Konstrukcija Huffmanovog kodnog stabla

Marker: SOS (početak skeniranja)

Računanja

Kvantizacija

Inverzna diskretna kosinusna transformacija

YCbCr u RGB

Kraj

Uobičajeni formati slika

Koji format odabrati

Koje slike za web stranice koristim danas?

Opis popularnih formata slika za stranicu

JPEG

PNG

GIF

SVG

WebP

Zaključak

Malo o samim formatima.

TIFF format

Algoritmi kompresije bez gubitaka

RLE algoritam

Algoritmi rječnika

Statistički algoritmi kodiranja

Huffmanov algoritam

Aritmetičko kodiranje

Vektorska reprezentacija

Prijelaz sa vektora na funkcije.

Diskretne Fourierove transformacije (DFT)

DCT naspram svega ostalog

KLT

DFT

DST

Vraćanje na DCT

Sve ostalo

2D transformacije

Odabir veličine bloka

Kvantizacija

Kodiranje

Kodiramo koeficijente

Slika u boji

I još nešto

Progresivni način rada

Način rada bez gubitaka

Hijerarhijski način rada

Aritmetičko kodiranje

Najbolji članci na ovu temu