Algoritam je 1991. razvila Joint Photographic Expert Group posebno za komprimiranje 24-bitnih slika i slika u sivim tonovima. Ovaj algoritam ne sažima dobro dvorazinske slike, ali dobro radi na slikama kontinuiranog tona u kojima bliski pikseli obično imaju slične boje. Oko obično ne može primijetiti nikakvu razliku kada se komprimira ovom metodom 10 ili 20 puta.
Algoritam se temelji na DCT primijenjenom na matricu disjunktnih blokova slike od 8x8 piksela. DCT rastavlja te blokove prema amplitudama određenih frekvencija. Rezultat je matrica u kojoj su mnogi koeficijenti, u pravilu, blizu nule, što se može prikazati u grubom numeričkom obliku, tj. u kvantiziranom obliku bez značajnog gubitka kvalitete restauracije.
Razmotrimo detaljnije rad algoritma. Pretpostavimo da se komprimira 24-bitna slika u punoj boji. U ovom slučaju dobivamo sljedeće faze rada.
Korak 1. Sliku pretvaramo iz RGB prostora u YCbCr prostor koristeći sljedeći izraz:
Odmah napomenimo da se inverzna transformacija lako dobiva množenjem inverzna matrica u vektor, koji je u biti YUV prostor:
.
Korak 2. Podijelili smo izvornu sliku na matrice 8x8. Od svake formiramo tri radne DCT matrice - 8 bita zasebno za svaku komponentu. Pri visokim omjerima kompresije, blok 8x8 se rastavlja na komponente YCbCr u formatu 4:2:0, tj. komponente za Cb i Cr uzimaju se kroz točku u redovima i stupcima.
3. korak Primjena DCT-a na blokove slike veličine 8x8 piksela. Formalno, direktni DCT za blok 8x8 može se napisati kao
Gdje 
. Budući da je DCT "srce" JPEG algoritma, u praksi ga je poželjno izračunati što je brže moguće. Jednostavan pristup ubrzanju izračuna je unaprijed izračunati kosinusne funkcije i tabelirati rezultate. Štoviše, s obzirom na ortogonalnost kosinusnih funkcija s različite frekvencije, gornja formula se može napisati kao
.
Ovdje je matrica od 8x8 elemenata, koja opisuje 8-dimenzionalni prostor, za predstavljanje stupaca bloka u ovom prostoru. Matrica je transponirana matrica i radi istu stvar, ali za blok retke. Rezultat je separabilna transformacija, koja se u matričnom obliku piše kao
Ovdje je rezultat DCT-a, čiji izračun zahtijeva operacije množenja i gotovo isto toliko zbrajanja, što je znatno manje od izravnih izračuna pomoću gornje formule. Na primjer, za pretvaranje slike veličine 512x512 piksela trebat će vam aritmetičke operacije. Uzimajući u obzir 3 komponente svjetline, dobivamo vrijednost od 12 582 912 aritmetičkih operacija. Broj množenja i zbrajanja može se dodatno smanjiti korištenjem algoritma brze Fourierove transformacije. Kao rezultat toga, za transformaciju jednog bloka 8x8 morat ćete napraviti 54 množenja, 468 zbrajanja i pomaka bitova.
Kao rezultat DCT-a dobivamo matricu u kojoj su koeficijenti lijevo gornji kut odgovaraju niskofrekventnoj komponenti slike, au donjem desnom dijelu - visokofrekventnoj.
Korak 4. Kvantizacija. U ovom koraku neke informacije se odbacuju. Ovdje se svaki broj iz matrice dijeli s posebnim brojem iz "kvantizacijske tablice", a rezultat se zaokružuje na najbliži cijeli broj:
.
Štoviše, za svaku matricu Y, Cb i Cr možete postaviti vlastite tablice kvantizacije. JPEG standard čak dopušta korištenje vlastitih kvantizacijskih tablica, koje će se, međutim, morati prenijeti u dekoder zajedno s komprimiranim podacima, što će povećati ukupnu veličinu datoteke. Jasno je da je korisniku teško samostalno odabrati 64 koeficijenta, pa JPEG standard koristi dva pristupa za kvantizacijske matrice. Prvi je da JPEG standard uključuje dvije preporučene kvantizacijske tablice: jednu za svjetlinu i jednu za boju. Ove tablice prikazane su u nastavku. Drugi pristup je sintetizirati (izračun u hodu) kvantizacijsku tablicu koja ovisi o jednom parametru koji je odredio korisnik. Sama tablica je izgrađena prema formuli
Faza kvantizacije je mjesto gdje se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo određivanjem kvantizacijskih tablica s velikim koeficijentima dobiti više nula, a time i veći omjer kompresije.
Specifični učinci algoritma također su povezani s kvantizacijom. Na velike vrijednosti koraku kvantizacije, gubici mogu biti toliki da se slika razbije na monokromatske kvadrate 8x8. Zauzvrat, gubici u visoke frekvencije mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura formira valovita "aureola" s oštrim prijelazom boja.
Korak 5. Matricu 8x8 pretvaramo u vektor od 64 elementa pomoću cik-cak skeniranja (slika 2).
Riža. 2. Cik-cak skeniranje
Kao rezultat toga, koeficijenti različiti od nule u pravilu će biti zapisani na početku vektora, a lanci nula će se formirati na kraju.
Korak 6. Transformiramo vektor pomoću modificiranog RLE algoritam, na čijem izlazu dobivamo parove tipa (skip, number), gdje je “skip” brojač preskočenih nula, a “number” je vrijednost koju je potrebno staviti u sljedeću ćeliju. Na primjer, vektor 1118 3 0 0 0 -2 0 0 0 0 1 ... će se sažeti u parove (0, 1118) (0,3) (3,-2) (4,1) ... .
Treba napomenuti da je prvi broj pretvorene komponente u biti jednak prosječnoj svjetlini bloka 8x8 i naziva se DC koeficijent. Isto za sve blokove slika. Ova okolnost sugerira da se DC koeficijenti mogu učinkovito komprimirati ako se ne sjećate njihovih apsolutnih vrijednosti, već relativnih u obliku razlike između DC koeficijenta trenutnog bloka i DC koeficijenta prethodnog bloka, i zapamtite prvi koeficijent kao to je. U ovom slučaju, poredak koeficijenata istosmjerne struje može se napraviti, na primjer, ovako (slika 3). Ostali koeficijenti, koji se nazivaju AC koeficijenti, ostaju nepromijenjeni.
Korak 7 Rezultirajuće parove konvolviramo pomoću neuniformnih Huffmanovih kodova s fiksnom tablicom. Štoviše, za DC i AC koeficijente, različite šifre, tj. različite tablice s Huffmanovim kodovima.
Riža. 3. Shema sređivanja istosmjernih koeficijenata
Riža. 4. Blok dijagram JPEG algoritma
Proces obnove slike u ovom algoritmu potpuno je simetričan. Metoda vam omogućuje komprimiranje slika 10-15 puta bez primjetnih gubitaka vida.
Pri razvoju ovog standarda vodili smo se činjenicom da ovaj algoritam morao je komprimirati slike prilično brzo - ne više od minute na prosječnoj slici. Ovo je 1991.! A njegova hardverska implementacija trebala bi biti relativno jednostavna i jeftina. U ovom slučaju, algoritam je morao biti simetričan u vremenu rada. Izvođenje najnoviji zahtjev učinio mogući izgled digitalni fotoaparati koji snimaju 24-bitne slike. Da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku.
Iako JPEG algoritam i ISO standard, njegov format datoteke nije fiksiran. Iskorištavajući to, proizvođači stvaraju vlastite formate koji su međusobno nekompatibilni i stoga mogu promijeniti algoritam. Stoga su interne tablice algoritama koje preporučuje ISO zamijenjene njihovim vlastitim. Postoje i JPEG opcije za posebne aplikacije.
- Tutorial
UPD. Bio sam prisiljen ukloniti monospace formatiranje. Jednog lijepog dana, habraparser je prestao prihvaćati formatiranje unutra oznake pre i kod. Cijeli tekst se pretvorio u kašu. Uprava Habra mi nije mogla pomoći. Sada je neravnomjerno, ali je barem čitljivo.
Jeste li ikada htjeli znati kako funkcionira jpg datoteka? Shvatimo sada! Zagrijte svoj omiljeni prevodilac i heksadecimalni uređivač, dekodirat ćemo ovo:
Namjerno sam uzeo manji crtež. Ovo je poznati, ali jako komprimirani Google favicon:
Odmah vas upozoravam da je opis pojednostavljen i da navedene informacije nisu potpune, ali kasnije će biti lako razumjeti specifikaciju.
Čak i ne znajući kako se kodiranje događa, već možemo izvući nešto iz datoteke.
- startni marker. Uvijek je na početku svih jpg datoteka.
Slijede bajtovi
. Ovo je oznaka koja označava početak odjeljka komentara. Sljedeća 2 bajta
- duljina odjeljka (uključujući ova 2 bajta). Dakle u sljedeća dva
- sam komentar. To su znakovni kodovi ":" i ")", tj. obični emotikon. Možete ga vidjeti u prvom redu na desnoj strani hex uređivača.
Malo teorije
Vrlo ukratko korak po korak:
Razmislimo o redoslijedu kojim se ti podaci mogu kodirati. Recimo da je kanal Y potpuno kodiran za cijelu sliku, zatim Cb, pa Cr. Svi se sjećaju učitavanja slika na dial-up. Da su kodirani na ovaj način, morali bismo pričekati da se cijela slika učita prije nego što se pojavi na ekranu. Također će biti neugodno ako se kraj datoteke izgubi. Vjerojatno postoje i drugi dobri razlozi. Stoga se kodirani podaci slažu jedan po jedan, u male dijelove. 
Dopustite da vas podsjetim da je svaki blok Y ij, Cb ij, Cr ij matrica DCT koeficijenata kodiranih Huffmanovim kodovima. U datoteci su raspoređeni ovim redoslijedom: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Čitanje datoteke
Nakon što izdvojimo komentar, bit će lako razumjeti sljedeće:- Datoteka je podijeljena na sektore kojima prethode oznake.
- Markeri su dugi 2 bajta, a prvi bajt je .
- Gotovo svi sektori pohranjuju svoju duljinu u sljedeća 2 bajta nakon oznake.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9
Marker: DQT - kvantizacijska tablica.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
Zaglavlje odjeljka uvijek zauzima 3 bajta. U našem slučaju je. Zaglavlje se sastoji od:
Duljina: 0x43 = 67 bajtova
Duljina vrijednosti u tablici: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tablice: 0
Preostala 64 bajta trebaju ispuniti tablicu 8x8.
Pažljivije pogledajte redoslijed kojim se popunjavaju vrijednosti tablice. Ovaj poredak se naziva cik-cak redoslijed: 
Marker: SOF0 - osnovni DCT
Ovaj marker se zove SOF0 i znači da je slika kodirana pomoću osnovne metode. Vrlo je čest. Ali ne manje popularna na Internetu je poznata progresivna metoda, kada se slika prvo učitava iz niske rezolucije, a onda normalna slika. To vam omogućuje da bez čekanja razumijete što je tamo prikazano 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
Duljina: 17 bajtova.
Preciznost: 8 bita. U osnovnoj metodi uvijek je 8. Koliko ja razumijem, ovo je dubina bita vrijednosti kanala.
Visina slike: 0x10 = 16
Širina figure: 0x10 = 16
Broj komponenti: 3. Najčešće su to Y, Cb, Cr.
1. komponenta:
ID: 1
Horizontalno stanjivanje (H 1): 2
[_2]
Vertikalno stanjivanje (V 1): 2
ID kvantizacijske tablice: 0
2. komponenta:
ID: 2
Horizontalno stanjivanje (H 2): 1
[_1]
Vertikalno stanjivanje (V 2): 1
3. komponenta:
ID: 3
Horizontalno stanjivanje (H 3): 1
[_1]
Vertikalno stanjivanje (V 3): 1
ID kvantizacijske tablice: 1
Sada pogledajte kako odrediti koliko je slika tanka. Nalazimo H max =2 i V max =2. Kanal i bit će stanjen za H max /H i puta vodoravno i V max /V i puta okomito.
Marker: DHT (Huffmanova tablica)
Ovaj odjeljak pohranjuje kodove i vrijednosti dobivene Huffmanovim kodiranjem.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
duljina: 21 bajt.
klasa: 0 (0 - tablica DC koeficijenata, 1 - tablica AC koeficijenata).
[_0]
ID tablice: 0
Duljina Huffmanovog koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Pod brojem kodova podrazumijeva se broj kodova te duljine. Imajte na umu da odjeljak pohranjuje samo duljine kodova, a ne same kodove. Sami moramo pronaći kodove. Dakle, imamo jedan kod duljine 1 i jedan duljine 2. Ukupno 2 koda, nema više kodova u ovoj tablici.
Svaki kod ima pridruženu vrijednost, a one su navedene u datoteci kako slijedi. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. šifre.
- vrijednost 2. šifre.
Konstrukcija Huffmanovog kodnog stabla
Moramo izgraditi binarno stablo iz tablice koju smo dobili u odjeljku DHT. I iz ovog stabla prepoznajemo svaki kod. Dodajemo vrijednosti redoslijedom kojim su navedene u tablici. Algoritam je jednostavan: bez obzira u kojem se čvoru nalazimo, uvijek pokušavamo dodati vrijednost lijevoj grani. A ako je zauzeta, onda desno. A ako tamo nema mjesta, onda se vraćamo na višu razinu i pokušavamo od tamo. Trebate stati na razini jednaka duljini kodirati. Lijeve grane odgovaraju vrijednosti 0, desne - 1.Komentar:
Ne morate svaki put krenuti od vrha. Dodana vrijednost - povratak na višu razinu. Postoji li prava grana? Ako da, idite ponovno gore. Ako ne, stvorite desnu granu i idite tamo. Zatim, od ove točke, počnite tražiti kako biste dodali sljedeću vrijednost.
Stabla za sve tablice u ovom primjeru: 
UPD (hvala): Čvorovi prvog stabla (DC, id =0) moraju imati vrijednosti 0x03 i 0x02
U kružićima su značenja kodova, ispod kružića su sami kodovi (da objasnim da smo ih dobili prolazeći stazom od vrha do svakog čvora). Ovim kodovima (ove i drugih tablica) kodiran je sam sadržaj slike.
Oznaka: SOS (početak skeniranja)
Bajt u markeru znači „DA! Napokon smo prešli izravno na analizu odjeljka kodirane slike!” No rubrika je simbolično nazvana SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Dužina dijela zaglavlja (ne cijele sekcije): 12 bajtova.
Broj komponenti skeniranja. Imamo 3, po jedan za Y, Cb, Cr.
1. komponenta:
Broj komponente slike: 1 (Y)
ID Huffmanove tablice za DC koeficijente: 0
[_0]
ID Huffmanove tablice za AC koeficijente: 0
2. komponenta:
Broj komponente slike: 2 (Cb)
[_1]
3. komponenta:
Broj komponente slike: 3 (Cr)
ID Huffmanove tablice za DC koeficijente: 1
[_1]
ID Huffmanove tablice za AC koeficijente: 1
Ove komponente se ciklički izmjenjuju.
Ovdje završava dio zaglavlja, odavde do kraja (marker) su kodirani podaci.
0
Određivanje DC koeficijenta.
1.
Čitanje niza bitova (ako naiđemo na 2 bajta, onda to nije marker, već samo bajt). Nakon svakog bita, krećemo se po Huffmanovom stablu (s pripadajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako se nađemo na završnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, onda je koeficijent jednak 0, upisujemo to u tablicu i prelazimo na očitavanje ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je duljina koeficijenta u bitovima. Odnosno, čitamo sljedeća 2 bita, to će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka vrijednosti u binarnom prikazu 1, ostavljamo kako jest: DC_coef = vrijednost. U suprotnom transformiramo: DC_coef = value-2 value length +1 . Koeficijent upisujemo u tablicu na početku cik-cak - gornji lijevi kut.
Određivanje AC koeficijenata.
1.
Slično koraku 1, pronalaženje DC koeficijenta. Nastavljamo čitati niz:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je 0, to znači da preostale vrijednosti matrice moraju biti popunjene nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji pročitaju dovde i napišu mi o tome u osobnoj poruci dobit će plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - to je točno koliko nula moramo dodati matrici. To su 3 nula koeficijenta.
Drugi nibble: 0x1 - duljina koeficijenta u bitovima. Pročitajte sljedeći dio.
10
10
1110
1
110011101100001111100100
3. Slično koraku 3 pronalaženja DC koeficijenta.
Kao što već razumijete, trebate čitati AC koeficijente dok ne naiđemo nulta vrijednost koda, ili dok se matrica ne popuni.
U našem slučaju dobit ćemo:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
i matrica:
Jeste li primijetili da su vrijednosti popunjene istim cik-cak uzorkom?
Razlog za korištenje ovog reda je jednostavan - budući da su veće vrijednosti v i u, manje je značajan koeficijent S vu u diskretnoj kosinusnoj transformaciji. Stoga se pri visokim stupnjevima kompresije beznačajni koeficijenti postavljaju na nulu, čime se smanjuje veličina datoteke.
[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Oh, zaboravio sam reći da kodirani DC koeficijenti nisu sami DC koeficijenti, već njihove razlike između koeficijenata prethodne tablice (isti kanal)! Matrice je potrebno ispraviti:
DC za 2.: 2 + (-4) = -2
DC za 3.: -2 + 5 = 3
DC za 4.: 3 + (-4) = -1
[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………
Sada je sve u redu. Ovo pravilo vrijedi do kraja datoteke.
... a 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]
Budući da postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknuti.
Izračuni
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član s elementima kvantizacijske matrice. Ostaje samo odabrati onu koja vam je potrebna. Prvo smo skenirali prvu komponentu, njezina komponenta slike = 1. Komponenta slike s ovim ID-om koristi matricu kvantizacije 0 (naša je prva od dvije). Dakle, nakon množenja:
[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Slično tome, dobivamo još 3 Y-kanalne matrice...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
...i matricom za Cb i Cr.
[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
Inverzna diskretna kosinusna transformacija
Formula ne bi trebala biti teška*. S vu je naša rezultirajuća matrica koeficijenata. u - stupac, v - red. s yx - izravno vrijednosti kanala.
*Općenito govoreći, to nije sasvim točno. Kada sam uspio dekodirati i prikazati sliku 16x16 na ekranu, uzeo sam sliku 600x600 (usput, ovo je bila naslovnica omiljenog albuma Mind.In.A.Boxa - Lost Alone). Nije uspjelo odmah - pojavile su se razne greške. Uskoro sam se mogao diviti ispravno učitanoj slici. Jedina stvar koja me stvarno uznemirila je brzina preuzimanja. Još se sjećam da je trajalo 7 sekundi. Ali to nije iznenađujuće, ako nepromišljeno koristite gornju formulu, tada ćete za izračun jednog kanala od jednog piksela morati pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - gotovo tisuću teških operacija na samo jednom kanalu jednog piksela! Srećom, ima prostora za optimizaciju (nakon mnogo eksperimentiranja, smanjio sam vrijeme učitavanja na granicu točnosti timera od 15ms, a nakon toga promijenio sliku u fotografiju 25 puta veće površine. Možda o tome pišem u poseban članak).
Napisat ću rezultat izračuna samo prve matrice kanala Y (vrijednosti su zaokružene):
[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]
I preostala 2:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]
- Oh, idem jesti!
- Da, uopće se ne useljavam, o čemu mi pričamo.
- Nakon što se dobiju vrijednosti YCbCr boja, sve što preostaje je pretvoriti ih u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij) , Y ij, Cb ij, Cr ij - naše rezultirajuće matrice.
- 4 Y matrice, te po jedna Cb i Cr, pošto smo prorijedili kanale i 4 Y piksela odgovaraju jednom Cb i Cr. Stoga izračunajte ovako: YCbCrToRGB(Y ij , Cb , Cr )
YCbCr u RGB
R = Y + 1,402 * CrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Ne zaboravite dodati 128. Ako vrijednosti prelaze interval, dodijelite granične vrijednosti. Formula je jednostavna, ali također oduzima dio procesorskog vremena.
Ovdje su dobivene tablice za R, G, B kanale za gornji lijevi kvadrat 8x8 našeg primjera:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
Kraj
Općenito, nisam stručnjak za JPEG, pa teško mogu odgovoriti na sva pitanja. Samo što sam, dok sam pisao svoj dekoder, često imao posla s raznim stvarima neshvatljivi problemi. A kada je slika bila netočno prikazana, nisam znao gdje sam pogriješio. Možda je krivo protumačio bitove ili je možda krivo upotrijebio DCT. Jako mi je nedostajalo korak po korak primjer, stoga se nadamo da će ovaj članak pomoći pri pisanju dekodera. Mislim da pokriva opis osnovna metoda, ali ipak ne možete proći samo s njom. Nudim vam linkove koji su mi pomogli:JPEG je jedan od najnovijih i prilično moćnih algoritama. U praksi, to je "de facto" standard za slike u boji. Algoritam radi na 8x8 područjima u kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, pri rastavljanju matrice takve regije u dvostruki niz u kosinusima (formule u nastavku), značajni su samo prvi koeficijenti. Stoga se JPFG kompresija postiže izglađivanjem promjena boja na slici.
Algoritam je razvila skupina stručnjaka za fotografiju posebno za komprimiranje 24-bita JPEG slike- Joint Photographic Expert Group - odjel unutar ISO-a - Međunarodne organizacije za standardizaciju. Općenito, algoritam se temelji na diskretnoj kosinusnoj transformaciji (u daljnjem tekstu DCT) primijenjenoj na matricu slike kako bi se dobila nova matrica koeficijenata. Za dobivanje izvorne slike primjenjuje se inverzna transformacija
DCT rastavlja sliku prema amplitudama određenih frekvencija, pa se tijekom transformacije dobiva matrica u kojoj su mnogi koeficijenti ili blizu nule ili jednaki nuli. Osim, ljudski sustav percepcija boja slabo prepoznaje određene frekvencije. Stoga je neke koeficijente moguće grublje aproksimirati bez primjetnog gubitka kvalitete slike.
U tu svrhu koristi se kvantizacija koeficijenata. U samom jednostavan slučaj je aritmetički bitni pomak udesno. Ovom pretvorbom gube se neke informacije, ali se mogu postići veliki omjeri kompresije.
Rad algoritma.
Neka 24-bitna slika bude komprimirana.
Korak I.
Sliku iz RGB prostora boja, s komponentama odgovornim za crvenu (Red), zelenu (Green) i plavu (Blue) komponentu boje točke, pretvaramo u prostor boja YCrCb (ponekad zvan YUV).
U njemu je Y komponenta svjetline, a Cr, Cb komponente odgovorne za boju (kromatska crvena i kromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za komponente Cr i Cb s velikim gubicima i, sukladno tome, velikim omjerima kompresije. Ova vrsta pretvorbe već se dugo koristi na televiziji. Tamo je dodijeljen uži frekvencijski pojas za signale odgovorne za boju.
Pojednostavljeni prijevod iz RGB prostora boja u YCrCb prostor boja može se predstaviti na sljedeći način:
Inverzna transformacija se provodi množenjem YUV vektora inverznom matricom:
Korak 2.
Podijelili smo izvornu sliku na matrice 8x8. Od svake formiramo tri radne DCT matrice - 8 bita zasebno za svaku komponentu. Kod viših omjera kompresije, ovaj korak može biti malo teži. Slika je podijeljena Y komponentom - kao u prvom slučaju, a za Cr i Cb komponente matrice se upisuju kroz red i kroz stupac. Oni. od originalne 16x16 matrice, dobiva se samo jedna radna DCT matrica. Iako je lako primijetiti, gubimo 3/4 korisna informacija o komponentama boje slike i odmah dobiti dvostruku kompresiju. To možemo učiniti radom u YCrCb prostoru. Na nastaloj RGB slika, kao što je praksa pokazala, to nema jak učinak.
3. korak
DCT primjenjujemo na svaku radnu matricu. U ovom slučaju dobivamo matricu u kojoj koeficijenti u gornjem lijevom kutu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj.
U pojednostavljenom obliku, ova se transformacija može prikazati na sljedeći način:
Korak 4.
Provodimo kvantizaciju. U principu, ovo je jednostavno dijeljenje radne matrice s kvantizacijskom matricom element po element. Za svaku komponentu (Y, U i V), in opći slučaj, specificirana je vlastita kvantizacijska matrica (u daljnjem tekstu MC).
U ovom koraku se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem MK s velikim koeficijentima dobiti više nula, a time i veći stupanj kompresije.
Specifični učinci algoritma također su povezani s kvantizacijom. Za velike vrijednosti koeficijenata gama , - gubici u nižim frekvencijama mogu biti toliko veliki da se slika raspada na 8x8 kvadrata. Gubici u visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom učinku", kada se oko kontura formira neka vrsta "aureole" s oštrim prijelazom boja.
Korak 5.
Matricu 8x8 pretvaramo u vektor od 64 elementa pomoću cik-cak skeniranja, tj. odaberite elemente s indeksima (0.0). (0,1). (1,0). (2.0)...
Dakle, na početku vektora dobivamo koeficijente matrice koji odgovaraju niskim frekvencijama, a na kraju - visokim.
Korak 6.
Sažimamo vektor pomoću algoritma grupnog kodiranja. U ovom slučaju dobivamo parove tipa (preskoči, broj), gdje je "preskoči" brojač preskočenih nula, a "broj" je vrijednost koju treba staviti u sljedeću ćeliju.
Dakle, vektor će biti sažet u parove (0, 42) (0, 3) (3, -2) (4, 1)
Korak 7
Sažimamo naučene parove koristeći Huffmanovo kodiranje s fiksnom tablicom.
Proces obnove slike u ovom algoritmu potpuno je simetričan. Metoda vam omogućuje komprimiranje nekih slika 10-15 puta bez ozbiljnih gubitaka.
Cjevovod operacija korišten u JPEG algoritmu.
Bitno pozitivni aspekti Algoritam je sljedeći:
- 1) Postavlja omjer kompresije
- 2) Slobodan dan slika u boji može imati 24 bita po točki.
Negativni aspekti algoritma su sljedeći:
- 1) Kako se razina kompresije povećava, slika se raspada u zasebne kvadrate (8x8). To je zbog činjenice da nastaju veliki gubici u niske frekvencije Kada se kvantizira, postaje nemoguće vratiti izvorne podatke.
- 2) Pojavljuje se Gibbsov učinak - aureole duž granica oštrih prijelaza boja.
JPEG je standardiziran relativno nedavno - 1991. Ali čak i tada su postojali algoritmi koji su jače komprimirali kada manje gubitaka kvaliteta. Činjenica je da su radnje standardnih programera bile ograničene snagom tehnologije koja je postojala u to vrijeme. Odnosno čak i na osobno računalo algoritam je morao raditi manje od minute na prosječnoj slici, a njegova hardverska implementacija morala je biti relativno jednostavna i jeftina. Algoritam je morao biti simetričan (vrijeme raspakiranja približno je jednako vremenu arhiviranja).
Potonji zahtjev omogućio je za digitalne kamere- uređaji veličine male video kamere koji snimaju 24-bitne fotografije na flash karticu od 10-20 MB s PCMCIA sučeljem. Zatim se kartica umetne u utor na prijenosnom računalu i odgovarajući program omogućuje čitanje slika. Da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku.
Još jedno ne baš ugodno svojstvo JPEG-a je često horizontalno i okomite pruge potpuno su nevidljivi na zaslonu i mogu se pojaviti samo pri ispisu u obliku moiré uzorka. To se događa kada se kosi ispisni raster postavi na vodoravne i okomite pruge slike. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u ispisu, postavljanje visokih koeficijenata. Međutim, kod arhiviranja i slika namijenjenih ljudskom gledanju, jest ovaj trenutak nezamjenjiva.
Široka primjena JPEG-a dugo vremena je, možda, bila sputana samo činjenicom da radi na 24-bitnim slikama. Stoga, kako biste vidjeli sliku prihvatljive kvalitete na redoviti monitor u paleti od 256 boja, zahtijevao korištenje odgovarajućih algoritama i, stoga, Određeno vrijeme. U aplikacijama namijenjenim zahtjevnim korisnicima, poput igara, takva su kašnjenja neprihvatljiva. Također, ako su slike koje imate recimo 8-bitne GIF format pretvoriti u 24-bitni JPEG, a zatim natrag u GIF za gledanje, tada će do gubitka kvalitete doći dva puta tijekom obje pretvorbe. Međutim, dobitak u veličini arhive često je toliko velik (3-20 puta!), a gubitak u kvaliteti tako mali da je pohranjivanje slika u JPEG vrlo učinkovito.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije popravljen. Iskorištavajući to, proizvođači koriste svoje vlastite formate koji su međusobno nekompatibilni, te stoga mogu promijeniti algoritam. Dakle, tablice internih algoritama koje preporučuje ISO. zamjenjuju oni svojima.. Osim toga, postoji mala zabuna kod postavljanja stupnja gubitaka. Na primjer, tijekom testiranja pokazalo se da "izvrsna" kvaliteta, "100%" i "10 bodova" daju značajno različite slike. Usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i JPEG opcije za posebne aplikacije.
Kako se ISO standard JPEG sve više koristi u razmjeni slika računalne mreže. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijskim sustavima.
Karakteristike JPFG algoritma:
Omjeri kompresije: 2-200 (korisnički definirano).
Klasa slike: 24-bitne slike u boji ili slike u sivim tonovima bez oštrih prijelaza boja (fotografije).
Simetrija: 1.
Karakteristične značajke: U nekim slučajevima algoritam stvara "aureolu" oko oštrih vodoravnih i okomitih granica na slici (Gibbsov efekt). Osim toga, s visokim stupnjem kompresije, slika je podijeljena u blokove od 8x8 piksela.
(izgovara se "japeg" Joint Photographic Experts Group, prema nazivu razvojne organizacije) - jedan od popularnih grafički formati, služi za pohranjivanje fotografija i sličnih slika. Datoteke koje sadrže JPEG podaci, obično imaju ekstenzije .jpeg, .jfif, .jpg, .JPG ili .JPE. Međutim, od ovih, .jpg je najpopularnije proširenje na svim platformama.
1. Zajednička skupina stručnjaka iz područja fotografije;
2. Metoda kompresije slike koju je razvila ova grupa i odgovarajući grafički format, koji se često koristi na WWW-u. Karakterizira kompaktnost datoteka i, prema tome, brz prijenos, kao i “gubitak” kvalitete slike. Koristi se prvenstveno za fotografije, jer je za njih gubitak kvalitete manje kritičan. Sprema postavke boja u model u boji RGB.
JPEG(izgovara se " jpeg", Engleski Zajednička skupina stručnjaka za fotografiju, po nazivu razvojne organizacije) je jedan od popularnih grafičkih formata koji se koristi za pohranu fotografija i sličnih slika. Datoteke koje sadrže JPEG podatke obično imaju nastavak .jpeg, .jfif, .jpg, .JPG, ili .JPE. Međutim, od ovih .jpg najpopularnije proširenje na svim platformama. Vrsta MIME je slika/jpeg.
JPEG algoritam je algoritam za kompresiju podataka s gubitkom.
Područje primjene
JPEG algoritam u najvećoj mjeri pogodan za sažimanje fotografija i slika koje sadrže realistične scene s glatke prijelaze svjetlinu i boju. JPEG je najrasprostranjeniji u digitalna fotografija te za pohranu i prijenos slika putem Interneta.
S druge strane, JPEG nije prikladan za komprimiranje crteža, teksta i grafike znakova, gdje oštar kontrast između susjednih piksela dovodi do vidljivih artefakata. Preporučljivo je pohraniti takve slike u formatima bez gubitaka kao što su TIFF, GIF, PNG ili RAW.
JPEG (kao i druge metode kompresije izobličenja) nije prikladan za komprimiranje slika tijekom višestupanjske obrade, jer će se izobličenja unijeti u slike svaki put kada se spremaju međurezultati obrade.
JPEG se ne smije koristiti u slučajevima kada su čak i minimalni gubici neprihvatljivi, na primjer, kod kompresije astronomskih ili medicinskih slika. U takvim slučajevima, način kompresije JPEG bez gubitaka koji omogućuje JPEG standard (koji, nažalost, nije podržan od strane većine popularnih kodeka) ili standard JPEG-LS kompresija.
Kompresija
Kompresija pretvara sliku iz RGB prostora boja u YCbCr (YUV). Treba napomenuti da standard JPEG (ISO/IEC 10918-1) ni na koji način ne regulira izbor YCbCr, dopuštajući druge vrste pretvorbe (na primjer, s brojem komponenti osim tri) i kompresiju bez pretvorbe (izravno na RGB), ali specifikacija JFIF (JPEG Format za razmjenu datoteka, koji su 1991. godine predložili stručnjaci iz C-Cube Microsystemsa, a koji je sada postao de facto standard) uključuje korištenje RGB->YCbCr pretvorbe.
Nakon RGB->YCbCr konverzije, može se izvršiti "poduzorkovanje" za kanale slike Cb i Cr, koji su odgovorni za boju, što se sastoji od dodjele prosječnih vrijednosti Cb i Cr (shema stanjivanja "4:2:0" ). Štoviše, za svaki 2x2 blok, umjesto 12 vrijednosti (4 Y, 4 Cb i 4 Cr), koristi se samo 6 (4 Y i po jedna prosječna Cb i Cr). Ako se postavljaju povećani zahtjevi za kvalitetu slike obnovljene nakon kompresije, stanjivanje se može izvesti samo u jednom smjeru - okomito (shema "4:4:0") ili vodoravno ("4:2:2"), ili se ne izvodi uopće (“4:4:4”).
Standard također dopušta decimaciju s usrednjavanjem Cb i Cr ne za blok 2x2, već za četiri piksela smještena sekvencijalno (okomito ili vodoravno), odnosno za blokove 1x4, 4x1 (shema "4:1:1"), kao i kao 2x4 i 4x2. Također je moguće koristiti različite vrste stanjivanje za Cb i Cr, ali u praksi se takve sheme koriste izuzetno rijetko.
Zatim se komponenta svjetline Y i komponente boje Cb i Cr dijele na blokove od 8x8 piksela. Svaki takav blok podvrgava se diskretnoj kosinusnoj transformaciji (DCT). Dobiveni DCT koeficijenti su kvantizirani (za Y, Cb i Cr, u općem slučaju, različite matrice kvantizacija) i pakiraju se pomoću Huffmanovih kodova. JPEG standard također omogućuje mnogo učinkovitije korištenje aritmetičko kodiranje, međutim, zbog patentnih ograničenja (patent za aritmetički QM koder opisan u JPEG standardu pripada IBM-u), ne koristi se u praksi.
Matrice koje se koriste za kvantiziranje DCT koeficijenata pohranjene su u dijelu zaglavlja JPEG datoteke. Obično su konstruirani tako da su visokofrekventni koeficijenti podložni jačoj kvantizaciji od niskofrekventnih. To rezultira ogrubljivanjem sitnih detalja na slici. Što je veći omjer kompresije, to su svi koeficijenti snažnije kvantizirani.
Prilikom spremanja slike u JPEG datoteku, naveden je parametar kvalitete, naveden u nekim konvencionalnim jedinicama, na primjer, od 1 do 100 ili od 1 do 10. Veći broj obično odgovara bolja kvaliteta(I veće veličine komprimirana datoteka). Međutim, čak i pri korištenju najviša kvaliteta(odgovara kvantizacijskoj matrici koja se sastoji od samo jedan), rekonstruirana slika neće se točno podudarati s izvornom, što je povezano i s konačnom točnošću implementacije DCT-a i s potrebom zaokruživanja vrijednosti Y, Cb, Cr i DCT koeficijenti na najbliži cijeli broj. Omogućuje JPEG način kompresije bez gubitaka, koji ne koristi DCT točno podudaranje restaurirane i originalne slike, međutim, njegova niska učinkovitost (omjer kompresije rijetko prelazi 2) i nedostatak podrške programera softver nije pridonio popularnosti Lossless JPEG-a.
Varijante shema kompresije JPEG
JPEG standard nudi dva glavna načina za predstavljanje kodiranih podataka.
Najčešći, podržan od strane većine dostupnih kodeka, je sekvencijalni JPEG prikaz podataka, koji uključuje sekvencijalni obilazak kodirane slike blok po blok slijeva nadesno, odozgo prema dolje. Gore opisane operacije izvode se na svakom kodiranom bloku slike, a rezultati kodiranja stavljaju se u izlazni tok u obliku jednog "skena", tj. niz kodiranih podataka koji odgovaraju sekvencijalno proslijeđenoj ("skeniranoj") slici. Glavni ili "osnovni" način kodiranja dopušta samo ovaj prikaz. Prošireni način rada, zajedno sa sekvencijalnim načinom, također omogućuje progresivno predstavljanje JPEG podataka.
U slučaju progresivnog JPEG-a, komprimirani podaci zapisuju se u izlazni tok kao skup skeniranja, od kojih svaki opisuje cijelu sliku sa sve većim stupnjem detalja. To se postiže ili snimanjem u svakom skeniranju ne cijeli set DCT koeficijente, ali samo neki njihov dio: prvi - niskofrekventni, u sljedećim skenovima - visokofrekventni (metoda "spektralne selekcije", tj. spektralnih uzoraka), ili sekvencijalnim, od skeniranja do skeniranja, usavršavanjem DCT koeficijenti (aproksimacija "uzastopne" metode", tj. uzastopne aproksimacije). Ovo progresivno predstavljanje podataka posebno je korisno pri prijenosu komprimirane slike koristeći komunikacijske kanale niske brzine, budući da vam omogućuje da dobijete ideju o cijeloj slici nakon prijenosa malog dijela JPEG datoteke.
Obje opisane sheme (i sekvencijalni i progresivni JPEG) temelje se na DCT-u i u osnovi ne dopuštaju dobivanje rekonstruirane slike potpuno identične originalnoj. Međutim, standard također dopušta kompresiju koja ne koristi DCT, već je izgrađena na temelju linearnog prediktora (bez gubitaka, tj. "bez gubitaka", JPEG), jamčeći potpuno, bit-za-bit, podudaranje izvornika i restaurirane slike. Istodobno, omjer kompresije za fotografske slike rijetko doseže 2, ali zajamčena odsutnost izobličenja u nekim slučajevima je tražena. Zamjetno veći omjeri kompresije mogu se postići metodom kompresije JPEG-LS, koja, unatoč sličnosti naziva, nije izravno povezana s JPEG ISO/IEC 10918-1 (ITU T.81 preporuka) standardom, opisanim od strane ISO/ IEC 14495-1 standard (ITU T.87 preporuka).
Sintaksa i struktura JPEG formata
JPEG datoteka sadrži niz oznake, od kojih svaki počinje bajtom 0xFF, koji označava početak markera, i bajtom identifikatora. Neki markeri sastoje se samo od ovog para bajtova, dok drugi sadrže dodatne podatke koji se sastoje od polja od dva bajta s duljinom informacijskog dijela markera (uključujući duljinu ovog polja, ali minus dva bajta početka oznake marker, tj. 0xFF i identifikator) i sami podaci.
| Marker | Bajtovi | Duljina | Svrha |
|---|
JPEG je jedan od novih i prilično moćnih algoritama. To je praktički de facto standard za slike u boji. Algoritam radi na 8x8 područjima u kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, pri rastavljanju matrice takvog područja u dvostruki niz u kosinusima (vidi formule u nastavku), značajni su samo prvi koeficijenti. Dakle, kompresija u JPEG-u se provodi zbog glatkoće promjena boje na slici.
Algoritam je razvila skupina fotografskih stručnjaka posebno za komprimiranje 24-bitnih slika. JPEG - Joint Photographic Expert Group - odjel unutar ISO-a - Međunarodne organizacije za standardizaciju. Naziv algoritma čita se kao ["jei"peg]. Općenito, algoritam se temelji na diskretnoj kosinusnoj transformaciji (u daljnjem tekstu DCT) primijenjenoj na matricu slike kako bi se dobila nova matrica koeficijenata. Za dobivanje izvorne slike primjenjuje se inverzna transformacija.
DCT rastavlja sliku prema amplitudama određenih frekvencija. Tako transformacijom dobivamo matricu u kojoj su mnogi koeficijenti ili blizu nule ili jednaki nuli. Osim toga, zbog nesavršenosti ljudskog vida, moguće je grublje aproksimirati koeficijente bez zamjetnog gubitka kvalitete slike.
U tu svrhu koristi se kvantizacija koeficijenata. U najjednostavnijem slučaju, to je aritmetički pomak udesno. Ovom pretvorbom gubi se dio informacija, ali se može postići veći stupanj kompresije.
Kako algoritam radi
Dakle, pogledajmo algoritam detaljnije (slika 2.1). Komprimirajmo 24-bitnu sliku.
Korak 1. Pretvaramo sliku iz RGB prostora boja, s komponentama odgovornim za crvenu, zelenu i plavu komponentu boje točke, u YCrCb prostor boja (ponekad zvan YUV).
U njemu je Y komponenta svjetline, a Cr, Co komponente odgovorne za boju (kromatska crvena i kromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za komponente Cr i Co s velikim gubicima i, sukladno tome, visokim omjerima kompresije.Slična pretvorba već se dugo koristi u televiziji. Tamo je dodijeljen uži frekvencijski pojas za signale odgovorne za boju. Pojednostavljeni prijevod iz RGB prostora boja u YCrCb prostor boja može se prikazati pomoću prijelazne matrice:
Korak 2. Podijelili smo izvornu sliku na matrice 8x8. Od svake formiramo 3 radne DCT matrice - 8 bita zasebno za svaku komponentu. Kod viših omjera kompresije ovaj korak može biti malo teži. Slika je podijeljena Y komponentom, kao iu prvom slučaju, a za Cr i Cb komponente matrice se upisuju kroz red i kroz stupac. Odnosno, iz izvorne matrice 16x16 dobiva se samo jedna radna DCT matrica. U ovom slučaju, kao što je lako vidjeti, gubimo 3/4 korisnih informacija o komponentama boje slike i odmah dobivamo dvostruku kompresiju. To možemo učiniti radom u YCrCb prostoru. Kao što je praksa pokazala, to nema značajan učinak na rezultirajuću RGB sliku.
3. korak U pojednostavljenom obliku, DCT za n=8 može se predstaviti na sljedeći način:
nu,v] = ^Hc(i,u)xC(j,v)y rY) Yq= Zaokruži cijeli broj U ovom koraku se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem MK s velikim koeficijentima dobiti više nula, a time i veći stupanj kompresije. Specifični učinci algoritma također su povezani s kvantizacijom. Pri visokim gama vrijednostima gubitak u niskim frekvencijama može biti toliko velik da se slika raspada na kvadrate 8x8. Gubici na visokim frekvencijama mogu se očitovati u tzv Gibbsov učinak, kada se oko kontura formira neka vrsta "aureole" s oštrim prijelazom boja. Korak 5. Matricu 8x8 pretvaramo u vektor od 64 elementa cik-cak skeniranjem, tj. uzimamo elemente s indeksima (0,0), (0,1), (1,0), (2,0 ). . Dakle, na početku vektora dobivamo koeficijente matrice koji odgovaraju niskim frekvencijama, a na kraju - visokim. Korak 6. Sažimamo vektor pomoću algoritma grupnog kodiranja. U ovom slučaju dobivamo parove tipa<пропустить, число>, gdje je "skip" broj preskočenih nula, a "number" je vrijednost koju treba staviti u sljedeću ćeliju. Tako će vektor 42 3000-2 00001 ... biti presavijen u parove (0,42) (0,3) (3,-2) (4,1).... Korak 7. Sažimamo dobivene parove koristeći Huffmanovo kodiranje s fiksnom tablicom. Proces obnove slike u ovom algoritmu potpuno je simetričan. Metoda vam omogućuje komprimiranje nekih slika 10-15 puta bez ozbiljnih gubitaka. Značajni pozitivni aspekti algoritma su sljedeći: ■ postavljena je razina kompresije; ■ Izlazna slika u boji može biti 24 bita po točki. Negativni aspekti algoritma su sljedeći: ■ Kako se razina kompresije povećava, slika se raspada u pojedinačne kvadrate (8x8). To je zbog činjenice da se tijekom kvantizacije javljaju veliki gubici na niskim frekvencijama i postaje nemoguće vratiti izvorne podatke. ■ Pojavljuje se Gibbsov efekt - aureole duž granica oštrih prijelaza boja. Kao što je već spomenuto, JPEG je standardiziran relativno nedavno - 1991. Ali čak i tada su postojali algoritmi koji su se jače komprimirali s manjim gubitkom kvalitete. Činjenica je da su radnje standardnih programera bile ograničene snagom tehnologije koja je postojala u to vrijeme. Odnosno, čak i na računalu, algoritam je morao raditi manje od minute na prosječnoj slici, a njegova hardverska implementacija morala je biti relativno jednostavna i jeftina. Algoritam je morao biti simetričan (vrijeme raspakiranja približno je jednako vremenu arhiviranja). Ispunjenje posljednjeg zahtjeva omogućilo je pojavu uređaja kao što su digitalni fotoaparati koji snimaju 24-bitne fotografije na flash karticu od 8-256 MB." Zatim se ta kartica umetne u utor na vašem prijenosnom računalu i odgovarajući program vam omogućuje čitati slike.Nije istina Nya, da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku. Još jedno ne baš ugodno svojstvo JPEG-a je Da, da su često vodoravne i okomite pruge na zaslonu potpuno nevidljive i mogu se pojaviti samo pri ispisu u obliku moiré uzorka. To se događa kada se kosi ispisni raster postavi na vodoravne i okomite pruge slike. Zbog ovih iznenađenja, JPEG nije aktivno se preporučuje koristi se u tiskarstvu, postavljajući visoke koeficijente matrice kvantizacije. No, kod arhiviranja slika namijenjenih ljudskom gledanju trenutno je neizostavan. Širok Upotreba JPEG-a dugo je bila ograničena, možda, jedino činjenicom da radi na 24-bitnim slikama. Dakle, da bi se na običnom monitoru prikazala slika prihvatljive kvalitete u paleti od 256 boja, bila je potrebna upotreba odgovarajućih algoritama, a time i određeno vrijeme. U aplikacijama namijenjenim zahtjevnim korisnicima, poput igara, takva su kašnjenja neprihvatljiva. Osim toga, ako imate slike, recimo, u 8-bitnom GIF formatu, pretvorene u 24-bitni JPEG, a zatim natrag u GIF za gledanje, tada će se gubitak kvalitete dogoditi dva puta tijekom obje pretvorbe. Unatoč tome, dobitak u veličini arhive često je toliko velik (3-20 puta), a gubitak u kvaliteti tako mali da je pohranjivanje slika u JPEG vrlo učinkovito. Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije popravljen. Iskorištavajući to, proizvođači stvaraju vlastite formate koji su međusobno nekompatibilni i stoga mogu promijeniti algoritam. Stoga su interne tablice algoritama koje preporučuje ISO zamijenjene njihovim vlastitim. Osim toga, postoji mala zabuna pri postavljanju stupnja gubitka. Na primjer, tijekom testiranja pokazalo se da "izvrsna" kvaliteta, "100%" i "10 bodova" daju značajno različite slike. Međutim, usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i JPEG opcije za posebne aplikacije. Kao ISO standard, JPEG se sve više koristi za razmjenu slika na računalnim mrežama. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijskim sustavima. Karakteristike JPEG algoritma: o ! w. ,. Omjer kompresije: 2-200 (postavlja korisnik). ,ts, :_,. . Klasa slike: pune boje 2jj.bit slike ili iso-| refleksije u sivim tonovima bez oštrih prijelaza boja (fotografije). Simetrija: 1. Karakteristike: u nekim slučajevima algoritam stvara! "halo" oko oštrih vodoravnih i okomitih granica na slici (Gibbsov učinak). Osim toga, pri visokom omjeru kompresije, iso-! Slika je razbijena u blokove 8x8 piksela.
