Phil 17. prosinca 2013. u 14:09

Izum JPEG-a

• Algoritmi,
• Obrada slike

• Tutorial

Iz naslova ste ispravno shvatili da ovo nije sasvim običan opis JPEG algoritma (format datoteke sam detaljno opisao u članku). Prije svega, odabrani način prezentiranja materijala pretpostavlja da ne znamo ništa ne samo o JPEG-u, već io Fourierovoj transformaciji i Huffmanovu kodiranju. Općenito, malo toga pamtimo s predavanja. Samo su snimili sliku i počeli razmišljati kako bi se mogla komprimirati. Stoga sam pokušao jasno izraziti samo bit, ali u kojoj će čitatelj razviti prilično duboko i, što je najvažnije, intuitivno razumijevanje algoritma. Formule i matematički izračuni - u najmanju ruku samo oni koji su važni za razumijevanje onoga što se događa.

Poznavanje JPEG algoritma vrlo je korisno ne samo za kompresiju slike. Koristi teoriju iz digitalna obrada signali, matematička analiza, linearna algebra, teorija informacija, posebice 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 s člankom. Provjerite koliko je gornje obrazloženje prikladno za različite slike, pokušajte napraviti vlastite izmjene algoritma. Jako je zanimljivo. Kao alat mogu preporučiti prekrasnu kombinaciju Python + NumPy + Matplotlib + PIL(Pillow). Gotovo sav moj rad (uključujući grafiku i animaciju) napravljen je pomoću njih.

Pozor, promet! Puno ilustracija, grafikona i animacija (~ 10Mb). Ironično, u članku o JPEG postoje samo 2 slike u ovom formatu od pedeset.

Kakav god bio algoritam kompresije informacija, njegov će princip uvijek biti isti - pronalaženje i opisivanje obrazaca. Što više uzoraka, više redundancije, manje informacija. Arhivari i koderi obično su “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 njegovog digitalnog prikaza može se prilično precizno opisati ravnom linijom.

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

Vektorski prikaz

Prvo, provjerimo koliko su dva susjedna piksela ovisna. Logično je pretpostaviti da će najvjerojatnije biti vrlo slični. Provjerimo ovo za sve parove slika. Označimo ih na koordinatnoj ravnini točkama tako da je vrijednost točke duž X osi vrijednost prvog piksela, a duž Y osi - drugog. Za našu sliku dimenzija 256 x 256, dobivamo 256*256/2 piksela:

Očekivano, većina točaka nalazi se na ili u blizini linije y=x (a ima ih čak i više nego što se može vidjeti na slici, budući da se višestruko preklapaju, a štoviše, prozirne su). Ako je tako, bilo bi lakše raditi ako ih okrenete za 45°. Da biste to učinili, morate ih izraziti u drugom koordinatnom sustavu.

Osnovni vektori novog sustava očito su: . Prisiljeni smo dijeliti s korijenom dva da bismo dobili ortonormirani sustav (duljine baznih vektora jednake su jedan). Ovdje pokazujemo da je neka točka p = (x, y) u novi sustav bit će predstavljen kao točka (a 0 , a 1). Poznavajući nove koeficijente, lako možemo dobiti stare okretanjem istih. Očito je da je prva (nova) koordinata prosjek, a druga razlika x i y (ali podijeljena s korijenom 2). Zamislite da se od vas traži da ostavite samo jednu vrijednost: ili 0 ili 1 (to jest, drugu izjednačite s nulom). Bolje je odabrati 0 jer će vrijednost 1 najvjerojatnije biti oko nule. Ovo se događa ako vratimo sliku samo iz 0:

4x povećanje:

Ova kompresija nije baš impresivna, da budem iskren. Bolje je na sličan način podijeliti sliku u triplete piksela i prikazati ih u trodimenzionalnom prostoru.

Ovo je isti grafikon, ali sa različite točke vizija. Crvene linije su osi koje su se same sugerirale. Oni odgovaraju vektorima: . Dopustite mi da vas podsjetim da morate podijeliti s nekim konstantama tako da duljine vektora postanu jednake jedan. Dakle, šireći na ovoj osnovi, dobivamo 3 vrijednosti 0, 1, 2, a 0 je važnija od 1, a 1 je važnija od 2. Ako odbacimo 2, tada će se graf "spljoštiti" u smjeru vektora e 2. Ova već prilično tanka trodimenzionalna ploča postat će ravna. Neće toliko izgubiti, ali ćemo se riješiti trećine vrijednosti. Usporedimo slike rekonstruirane iz trojki: (a 0 , 0, 0), (a 1 , a 2 , 0) i (a 0 , a 1 , a 2). U prošloj verziji nismo ništa bacali, pa ćemo dobiti original.

4x povećanje:

Drugi crtež je već dobar. Oštra područja su malo izglađena, ali sve u svemu slika je vrlo dobro očuvana. A sad, podijelimo na četiri na isti način i vizualno odredimo osnovu u četverodimenzionalnom prostoru... O, pa da. Ali možete pogoditi koji će biti jedan od baznih vektora: (1,1,1,1)/2. Stoga se može promatrati projekcija četverodimenzionalnog prostora na prostor okomit na vektor (1,1,1,1) kako bi se identificirali drugi. 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 u potpunosti odbaciti. Gornji eksperimenti nagovještavaju da je to moguće. Ali ne možete bez matematičkog aparata.
Dakle, moramo transformirati točke na novu osnovu. Ali prvo morate pronaći odgovarajuću osnovu. Vratimo se prvom eksperimentu sparivanja. Razmotrimo to općenito. Definirali smo bazne vektore:

Kroz njih smo izrazili vektor str:

ili u koordinatama:

Da biste pronašli 0 i 1 morate projicirati str na e 0 i e 1 odnosno. A za ovo morate pronaći skalarni produkt

sličan:

U koordinatama:

Često je prikladnije provesti transformaciju u obliku matrice.

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

Prijelaz s vektora na funkcije.

Pogodno je raditi s vektorima malih dimenzija. Međutim, želimo pronaći uzorke u većim blokovima, pa je umjesto N-dimenzionalnih vektora prikladnije raditi s nizovima koji predstavljaju sliku. Takve ću nizove nazvati diskretnim funkcijama, budući da se sljedeće razmišljanje također odnosi na kontinuirane funkcije.
Vraćajući se našem primjeru, zamislite funkciju f(i), koja je definirana u samo dvije točke: f(0)=x i f(1)=y. Postavimo slično osnovne funkcije e 0 (i) i e 1 (i) na temelju baza e 0 i e 1 . Dobivamo:

Ovo je vrlo važan zaključak. Sada u izrazu “proširenje vektora u ortonormirane vektore” možemo zamijeniti riječ “vektor” sa “funkcija” i dobiti potpuno ispravan izraz “proširenje funkcije u ortonormirane funkcije”. Nije važno što smo dobili tako kratku funkciju, budući da isto razmišljanje vrijedi za N-dimenzionalni vektor, koji se može prikazati kao diskretna funkcija s N vrijednostima. A rad s funkcijama je jasniji nego s N-dimenzionalnim vektorima. Obrnuto, takvu funkciju možete prikazati kao vektor. Štoviše, uobičajeno kontinuirana funkcija može se prikazati kao beskonačnodimenzionalni vektor, iako ne u euklidskom, već u Hilbertovom prostoru. Ali nećemo ići tamo; zanimat će nas samo diskretne funkcije.
I naš problem pronalaženja baze pretvara se u problem pronalaženja odgovarajućeg sustava ortonormiranih funkcija. U sljedećem razmišljanju pretpostavlja se da smo već nekako odredili skup baznih funkcija prema kojima ćemo dekomponirati.
Recimo da imamo neku funkciju (predstavljenu, na primjer, vrijednostima) koju želimo prikazati kao zbroj drugih. Ovaj proces možete prikazati u vektorskom obliku. Da biste dekomponirali funkciju, morate je "projicirati" na osnovne funkcije jednu po jednu. U vektorskom smislu, izračunavanje projekcije daje minimalno približavanje izvornog vektora drugom u smislu udaljenosti. Imajući na umu da se udaljenost izračunava pomoću Pitagorinog teorema, sličan prikaz u obliku funkcija daje najbolju aproksimaciju srednje kvadratne vrijednosti jedne funkcije drugoj. Dakle, svaki koeficijent (k) određuje "blizinu" funkcije. Formalnije, k*e(x) je najbolja aproksimacija srednjeg kvadrata f(x) među l*e(x).
Sljedeći primjer prikazuje postupak aproksimacije funkcije pomoću samo dvije točke. S desne strane je vektorski prikaz.

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

Ako uzmemo 3 točke, tada moramo uzeti u obzir trodimenzionalne vektore, ali će aproksimacija biti točnija. A za diskretnu funkciju s N vrijednostima, trebate uzeti u obzir N-dimenzionalne vektore.
Imajući skup dobivenih koeficijenata, možete lako dobiti izvorna funkcija, zbrajanje osnovnih funkcija uzetih s odgovarajućim koeficijentima. Analiza ovih koeficijenata može puno otkriti korisna informacija(ovisno o osnovi). Poseban slučaj ovih razmatranja je princip proširenja u Fourierov red. Uostalom, naše razmišljanje je primjenjivo na bilo koju bazu, a kada se proširuje u Fourierov red, uzima se sasvim specifična.

Diskretne Fourierove transformacije (DFT)

U prethodnom dijelu smo došli do zaključka da bi bilo lijepo funkciju rastaviti na komponente. O tome je početkom 19. stoljeća razmišljao i Fourier. Istina, nije imao sliku rakuna, pa je morao proučavati raspodjelu topline duž metalnog prstena. Zatim je otkrio da je vrlo zgodno izraziti temperaturu (i njezinu promjenu) u svakoj točki prstena kao zbroj sinusoida s različitim periodima. “Fourier je otkrio (preporučam čitanje, zanimljivo je) da drugi harmonik opada 4 puta brže od prvog, a harmonici višeg reda opadaju čak i bržom brzinom.”
Općenito, ubrzo se pokazalo da se periodične funkcije mogu savršeno rastaviti na zbroj sinusoida. A budući da u prirodi postoji mnogo objekata i procesa opisanih periodičkim funkcijama, pojavio se moćan alat za njihovu analizu.
Možda je zvuk jedan od najzornijih periodičnih procesa.

• 1. grafikon - čisti ton frekvencije 2500 herca.
• 2. - bijeli šum. To jest, šum s frekvencijama ravnomjerno raspoređenim u cijelom rasponu.
• 3. - zbroj prva dva.

Da su mi dali vrijednosti posljednje funkcije u tom trenutku kada nisam znao za Fourierove redove i tražili da ih analiziram, onda bih se sigurno zbunio i ne bih mogao ništa vrijedno reći. Pa da, nekakva funkcija, ali kako razumjeti da je tu nešto naručeno? Ali da sam mislio slušati posljednja funkcija, tada bi uho među bukom uhvatilo čisti ton. Iako nije baš dobro, budući da sam tijekom generiranja 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 to radi. Međutim, nedavno je postalo jasno da ne razlaže zvuk na sinusne valove. 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 pokušati koristiti sinusoide kao osnovu? Zapravo, mi smo to već učinili. Prisjetimo se naše dekompozicije na 3 bazna vektora i predstavimo ih na grafu:

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


Nije dobro složena provjera pokazuje da su ti vektori u 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 dobiva formula DCT transformacije:

Ovo je još uvijek ista formula: A = EX sa zamijenjenom bazom. Bazisni vektori navedenog DCT-a (oni su također vektori reda matrice E) su ortogonalni, ali ne i ortonormirani. Ovoga se treba sjetiti kada inverzna transformacija(Neću se zadržavati na ovome, ali za one koji su zainteresirani, inverzni DCT ima član 0,5*a 0, ​​budući da je vektor nulte baze veći od ostalih).
Sljedeći primjer prikazuje postupak približavanja međuzbrojeva izvornim vrijednostima. U svakoj iteraciji, sljedeća baza se množi sa sljedećim koeficijentom i dodaje međuzbroju (to jest, isto kao u ranim eksperimentima na rakunu - trećina vrijednosti, dvije trećine).

No, unatoč nekim argumentima o uputnosti odabira takve osnove, još nema pravih argumenata. Doista, za razliku od zvuka, izvedivost rastavljanja slike na periodične funkcije mnogo je manje očita. Međutim, slika doista može biti previše nepredvidljiva čak i na malom području. Stoga je slika podijeljena na komadiće koji su dovoljno mali, ali ne baš sićušni, da bi razlaganje imalo smisla. U JPEG-u, slika je "isječena" na kvadrate 8x8. Unutar takvog djela fotografije su obično vrlo ujednačene: pozadina plus male fluktuacije. Takvim se područjima lijepo približavaju sinusoide.
Pa, recimo da je ova činjenica više-manje intuitivna. Ali postoji loš osjećaj u vezi s naglim prijelazima boja, jer nas sporo mijenjanje funkcija neće spasiti. Moramo dodati razne visokofrekventne funkcije koje rade svoj posao, ali se pojavljuju postrance na homogenoj pozadini. Uzmimo sliku 256x256 s dva kontrastna područja:

Rastavimo svaki red pomoću DCT-a, dobivajući tako 256 koeficijenata po retku.
Tada ostavljamo samo prvih n koeficijenata, a ostale postavljamo na nulu, pa će slika biti prikazana kao zbroj 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 pozornost na obrub - unatoč svim najboljim aproksimacijama, uz dijagonalu su jasno vidljive 2 trake, jedna svjetlija, druga tamnija. Dio zadnje slike uvećan 4 puta:

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

Visina ovih izbočina, koje se pojavljuju u blizini diskontinuiteta funkcije, neće se smanjivati ​​s povećanjem broja sumandi funkcija. U diskretnoj transformaciji nestaje samo kada su gotovo svi koeficijenti sačuvani. Točnije, postaje nevidljiv.
Sljedeći primjer potpuno je sličan gornjoj dekompoziciji trokuta, ali na pravom rakunu:


Prilikom proučavanja DCT-a može se steći pogrešan dojam da je samo prvih nekoliko (niskofrekventnih) koeficijenata uvijek dovoljno. To vrijedi za mnoge dijelove fotografija, one čija se značenja dramatično ne mijenjaju. Međutim, na granici kontrastnih područja, vrijednosti će brzo "skočiti", pa će čak i posljednji koeficijenti biti veliki. Stoga, kada čujete o svojstvu DCT-a za očuvanje energije, uzmite u obzir činjenicu da se ono odnosi na mnoge vrste signala s kojima se susrećete, ali ne na sve. Na primjer, razmislite o tome kako bi izgledala diskretna funkcija čiji su koeficijenti proširenja jednaki nuli, osim posljednje. Savjet: Zamislite dekompoziciju u vektorskom obliku.
Unatoč nedostacima, odabrana osnova jedna je od najboljih na stvarnim fotografijama. Malo kasnije ćemo vidjeti malu usporedbu s drugima.

DCT protiv svega ostalog

Kad sam proučavao pitanje ortogonalnih transformacija, da budem iskren, nisu me baš uvjerili argumenti da je sve oko zbroj harmonijske vibracije, pa slike treba rastaviti na sinusoide. Ili bi možda neke funkcije koraka bile bolje? Stoga sam potražio rezultate istraživanja o optimalnosti DCT-a na stvarnim slikama. Posvuda je napisana činjenica da se “DCT najčešće nalazi u praktičnim primjenama zbog svojstva “zbijanja energije”. Ovo svojstvo znači da je najveća količina informacija sadržana u prvim koeficijentima. I zašto? Nije teško provoditi istraživanje: naoružamo se hrpom različitih slika, raznim poznatim bazama i počnemo izračunavati standardno odstupanje od stvarne slike za različite količine koeficijenti Pronašao sam malu studiju u članku (korištene slike) o ovoj tehnici. Prikazuje grafove ovisnosti pohranjene energije o broju prvih koeficijenata ekspanzije za različite baze. Ako ste pogledali ljestvice, uvjerili ste se da DCT konstantno zauzima časno... hm... 3. mjesto. Kako to? Kakva je ovo KLT konverzija? Hvalio sam DCT, a onda...

KLT

Sve transformacije, osim KLT, su transformacije s konstantnom bazom. A u KLT-u (Karhunen-Loeve transformacija) izračunava se najoptimalnija baza za nekoliko vektora. Izračunava se na način da prvi koeficijenti daju najmanju srednju kvadratnu grešku ukupno za sve vektore. Prethodno smo slične radove obavljali ručno, vizualno određujući osnovu. Isprva se čini kao dobra ideja. Mogli bismo, na primjer, podijeliti sliku u male dijelove i za svaki izračunati vlastitu osnovu. Ali ne samo da postoji briga oko pohranjivanja ove osnove, već je i operacija njezinog izračuna prilično radno intenzivna. Ali DCT gubi samo malo, a osim toga, DCT ima brze algoritme pretvorbe.

DFT

DFT (diskretna Fourierova transformacija) - diskretna transformacija Fourier. Pod tim imenom se ponekad naziva ne samo određena transformacija, već i cijeli razred diskretnih transformacija (DCT, DST...). Pogledajmo DFT formulu:

Kao što možete pogoditi, ovo je ortogonalna transformacija s nekom vrstom složene baze. Pošto takav složeni oblik javlja malo češće nego uvijek, ima smisla proučiti njegov zaključak.
Može se činiti da će bilo koji čisti harmonijski signal (s cijelobrojnom frekvencijom) s DCT dekompozicijom dati samo jedan koeficijent različit od nule koji odgovara tom harmoniku. To nije istina, jer osim frekvencije bitna je i faza ovog signala. Na primjer, širenje sinusa u kosinuse (na sličan način u diskretnom širenju) bit će ovako:

Toliko o čistim harmonicima. Iznjedrila je hrpu drugih. Animacija prikazuje DCT koeficijente sinusnog vala u različite faze.


Ako vam se činilo da se stupci okreću oko osi, onda vam se nije činilo.
To znači da ćemo sada proširiti funkciju u zbroj sinusoida ne samo različitih frekvencija, već i onih pomaknutih duž neke faze. Bit će prikladnije razmotriti fazni pomak na primjeru kosinusa:

Jednostavan trigonometrijski identitet daje važan rezultat: fazni pomak zamijenjen je zbrojem sinusa i kosinusa, uzetog s koeficijentima cos(b) i sin(b). To znači da se funkcije mogu proširiti u zbroj sinusa i kosinusa (bez ikakvih faza). Ovo je uobičajeni trigonometrijski oblik. Međutim, kompleks se koristi mnogo češće. Da biste ga dobili, morate koristiti Eulerovu formulu. Jednostavnom zamjenom formula za izvod za sinus i kosinus, dobivamo:


Sada za malu promjenu. Podvlaka je konjugirani broj.

Dobivamo konačnu jednakost:

c je kompleksni koeficijent čiji je realni dio jednak kosinusnom koeficijentu, a imaginarni dio jednak sinusnom koeficijentu. A skup točaka (cos(b), sin(b)) je kružnica. U takvom zapisu svaki harmonik ulazi u ekspanziju i s pozitivnom i s negativnom frekvencijom. Stoga se u raznim formulama Fourierove analize zbrajanje ili integracija obično odvija od minus do plus beskonačno. Često je prikladnije izvršiti izračune u ovom složenom obliku.
Transformacija razlaže signal na harmonike s frekvencijama od jedan do N oscilacija u području signala. Ali stopa uzorkovanja je N po području signala. A prema Kotelnikovljevom teoremu (aka Nyquist-Shannonov teorem), frekvencija uzorkovanja trebala bi biti barem dvostruku frekvenciju signala. Ako to nije slučaj, tada je učinak pojava signala s lažnom frekvencijom:

Isprekidana linija prikazuje pogrešno rekonstruirani signal. Često ste se u životu susretali s ovom pojavom. Na primjer, smiješno kretanje kotača automobila u videu ili moire efekt.
To dovodi do činjenice da se čini da se druga polovica N kompleksnih amplituda sastoji od drugih frekvencija. Ovi lažni harmonici druge polovice zrcalna su slika prve i ne nose dodatne informacije. Dakle, ostaje nam N/2 kosinusa i N/2 sinusa (tvoreći ortogonalnu bazu).
Dobro, postoji osnova. Njegove komponente su harmonici s cijelim brojem oscilacija u području signala, što znači da su ekstremne vrijednosti harmonika jednake. Točnije, gotovo su jednake, budući da posljednja vrijednost nije uzeta u cijelosti s ruba. Štoviše, svaki je harmonik gotovo zrcalno simetričan u odnosu na svoje središte. Sve ove pojave posebno su jake u niske frekvencije, koji su nam važni kod kodiranja. To je također loše jer će granice blokova biti vidljive na komprimiranoj slici. Dopustite mi da ilustriram DFT osnovu s N=8. Prva 2 reda su kosinusne komponente, posljednji su sinusne komponente:

Obratite pozornost na pojavu dupliciranih komponenti kako se učestalost povećava.

Možete mentalno razmišljati o tome kako signal čije vrijednosti postupno opadaju maksimalna vrijednost na početku do minimuma na kraju. Koliko-toliko adekvatnu aproksimaciju mogli bi dati tek harmonici pred kraj, što nam nije baš sjajno. Slika s lijeve strane je aproksimacija jednostranog signala. Desno - simetrično:


S prvim stvari stoje izuzetno loše.
Dakle, možda možemo to učiniti kao u DCT-u - smanjiti frekvencije za 2 ili neki drugi broj puta, tako da je broj nekih oscilacija razlomak i da su granice u različitim fazama? Tada će komponente biti neortogonalne. I tu se ne može ništa učiniti.

DST

Što ako koristimo sinuse umjesto kosinusa u DCT-u? Dobit ćemo diskretnu sinusnu transformaciju (DST). Ali za naš zadatak, svi oni su nezanimljivi, budući da su i cijeli i poluperiodi sinusa blizu nule na granicama. To jest, dobit ćemo približno istu neprikladnu dekompoziciju kao kod DFT-a.

Povratak na DCT

Kako mu je na granicama? Fino. Postoje protufaze i nema nula.

Sve ostalo

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

Dakle, sinula vam je ideja da osmislite vlastitu transformaciju. Zapamtite ovo:

1. Baza mora biti ortogonalna.
2. S fiksnom osnovom ne možete nadmašiti KLT za kvalitetu kompresije. U međuvremenu, na pravim fotografijama, DCT je gotovo jednako dobar.
3. Koristeći primjer DFT i DST, morate se sjetiti granica.
4. I zapamtite da DCT ima još jednu dobru prednost - u blizini granica njihovih komponenti, derivacije su jednake nuli, što znači da će prijelaz između susjednih blokova biti prilično gladak.
5. Fourierove transformacije imaju brze algoritme složenosti O(N*logN), za razliku od izravnog izračuna: O(N 2).

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

2D transformacije

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

Njegov 3D grafikon:

Prođimo kroz DCT (N=32) kroz svaki redak:

Sada želim da prođete očima kroz svaki stupac dobivenih koeficijenata, to jest od vrha do dna. Upamtite da je naš cilj ostaviti što manje vrijednosti, eliminirajući one koje nisu značajne. Vjerojatno ste pogodili da se vrijednosti svakog stupca rezultirajućih koeficijenata mogu proširiti na točno isti način kao i vrijednosti izvorne slike. Nitko nas ne ograničava u odabiru matrice ortogonalne transformacije, ali ćemo to ponovno učiniti pomoću DCT(N=8):

Koeficijent (0,0) se pokazao prevelikim pa je u grafu smanjen za 4 puta.
Dakle, što se dogodilo?
U gornjem lijevom kutu su najznačajniji koeficijenti ekspanzije najznačajnijih koeficijenata.
Donji lijevi kut je najbeznačajniji koeficijent ekspanzije najznačajnijih koeficijenata.
Gornji desni kut je najznačajniji koeficijent širenja najbeznačajnijih koeficijenata.
Donji desni kut su najbeznačajniji koeficijenti ekspanzije najbeznačajnijih koeficijenata.
Jasno je da se značaj koeficijenata smanjuje ako se pomaknete dijagonalno iz gornjeg lijevog u donji desni. Što je važnije: (0, 7) ili (7, 0)? Što oni uopće znače?
Prvo po redovima: A 0 = (EX T) T = XE T (transponirano, jer je formula A=EX za stupce), zatim po stupcima: A=EA 0 = EXE T . Ako pažljivo izračunate, dobit ćete formulu:

Dakle, ako se vektor rastavlja na sinusoide, tada se matrica rastavlja na funkcije oblika cos(ax)*cos(by). Svaki blok 8x8 u JPEG-u predstavljen je kao zbroj 64 funkcije oblika:


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

Stoga su koeficijenti (0, 7) ili (7, 0) jednako korisni.
Međutim, zapravo je ovo obična jednodimenzionalna dekompozicija na 64 64-dimenzionalne baze. Sve navedeno ne vrijedi samo za DCT, već i za svaku ortogonalnu dekompoziciju. Postupajući analogno, u općem slučaju dobivamo N-dimenzionalnu ortogonalnu transformaciju.
A evo i 2D transformacije rakuna (DCT 256x256). Opet s vraćanjem vrijednosti na nulu. Brojevi - broj nenuliranih koeficijenata od svih (najviše značajne vrijednosti, koji se nalazi u trokutastom području s lijeve strane gornji kut).

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

Odabir veličine bloka

Prijatelj pita zašto JPEG koristi particioniranje 8x8. Iz negativnog odgovora:

DCT tretira blok kao da je periodičan i mora rekonstruirati rezultirajući skok na granicama. Ako uzmete blokove 64x64, najvjerojatnije ćete imati ogroman skok na granicama i trebat će vam mnogo visokofrekventnih komponenti da to rekonstruirate do zadovoljavajuće preciznosti

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

• Mali profit kada se podijeli u velike blokove.
• Sve veća računalna složenost.
• Velika vjerojatnost velikog broja oštrih granica u jednom bloku, što će izazvati Gibbsov efekt.

Predlažem da to sami istražite. Počnimo s prvi.


Na vodoravnoj osi prikazan je udio prvih nenuliranih koeficijenata. Okomito - standardno odstupanje piksela od originala. Maksimalno moguće odstupanje uzima se kao jedan. Naravno, jedna slika očito nije dovoljna za presudu. Osim toga, ne postupam sasvim ispravno, jednostavno vraćam na nulu. U stvarnom JPEG-u, ovisno o kvantizacijskoj matrici, samo male vrijednosti visokofrekventnih komponenti su nulirane. Stoga su sljedeći pokusi i zaključci namijenjeni otkrivanju načela i obrazaca.
Možete usporediti podjelu na različite blokove s 25 posto preostalih koeficijenata (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 izvornu sliku (pojačanu 2 puta, inače se zapravo ništa ne vidi):

8x8 daje bolje rezultate od 4x4. Daljnje povećanje veličine više ne daje jasno vidljivu prednost. Iako bih ozbiljno razmotrio 16x16 umjesto 8x8: povećanje složenosti za 33% (više o složenosti u sljedećem odlomku) daje malo, ali ipak vidljivo poboljšanje za isti broj koeficijenata. Međutim, izbor 8x8 čini se sasvim razumnim i možda je zlatna sredina. JPEG je objavljen 1991. Mislim da je takva kompresija bila vrlo teška za procesore tog vremena.

Drugi argument. Jedna stvar koju treba imati na umu je da će povećanje veličine bloka zahtijevati više izračuna. Procijenimo koliko. Složenost pretvorbe, kao što već dobro znamo: O(N 2), budući da se svaki koeficijent sastoji od N članova. Ali u praksi se koristi učinkovit algoritam brza Fourierova transformacija (FFT, Fast Fourier Transform, FFT). Njegov opis je izvan opsega ovog članka. Njegova složenost: O(N*logN). Za dvodimenzionalno širenje trebate ga upotrijebiti dvaput N puta. Dakle, složenost 2D DCT je O(N 2 logN). Sada usporedimo složenost izračuna 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, izračun za particiju 64x64 dvostruko složeniji od particije 8x8.

Treći argument. Ako imamo na slici oštra granica boje, to će utjecati na cijeli blok. Možda bi bilo bolje da ovaj blok bude dovoljno mali, jer u mnogim susjednim blokovima vjerojatno više neće biti takve granice. Međutim, daleko od granica, slabljenje se događa vrlo brzo. Osim toga, sama granica će izgledati bolje. Provjerimo primjer s veliki iznos kontrastni prijelazi, opet, sa samo četvrtinom koeficijenata:


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

Kvantizacija

U ovom trenutku imamo hrpu 8x8 matrica s koeficijentima kosinusne transformacije. Vrijeme je da se riješite beznačajnih koeficijenata. Postoji elegantnije rješenje od jednostavnog vraćanja zadnjih koeficijenata na nulu, kao što smo učinili gore. Nismo zadovoljni ovom metodom, jer se nenulirane vrijednosti pohranjuju s pretjeranom preciznošću, a među onima koji nisu imali sreće moglo bi biti vrlo važnih. Rješenje je korištenje kvantizacijske matrice. Upravo u ovoj fazi nastaju gubici. Svaki Fourierov koeficijent se dijeli s odgovarajućim brojem u matrici kvantizacije. Pogledajmo primjer. Uzmimo prvi blok od našeg rakuna i izvršimo kvantizaciju. JPEG specifikacija daje standardnu ​​matricu:


Standardna matrica odgovara 50% kvalitete u FastStone i IrfanView. Ova je tablica odabrana u smislu ravnoteže između kvalitete i omjera kompresije. Mislim da je vrijednost za DC koeficijent veća od svojih susjeda zbog činjenice da DCT nije normaliziran i da je prva vrijednost veća nego što bi trebala biti. Visokofrekventni koeficijenti su jače ogrubljeni zbog svoje manje važnosti. Mislim da se takve matrice sada rijetko koriste, jer je pogoršanje kvalitete jasno vidljivo. Nitko ne zabranjuje korištenje vaše tablice (s vrijednostima od 1 do 255)
Tijekom dekodiranja događa se obrnuti proces - kvantizirani koeficijenti se množe po član s vrijednostima matrice kvantizacije. Ali budući da smo zaokružili vrijednosti, nećemo moći točno vratiti izvorne Fourierove koeficijente. Što je veći kvantizacijski broj, to je veća greška. Dakle, rekonstruirani koeficijent je samo najbliži višekratnik.
Još jedan primjer:

I za desert, razmislite o 5% kvalitete (prilikom kodiranja u Fast Stone).


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

Usput, oko 100% kvaliteta. Kao što možete pogoditi, u ovom slučaju kvantizacijska matrica sastoji se isključivo od jedinica, to jest, nema kvantizacije. Međutim, zbog zaokruživanja koeficijenata na najbliži cijeli broj, ne možemo točno vratiti izvornu sliku. Na primjer, rakun je točno zadržao 96% piksela, ali 4% je bilo za 1/256. Naravno, takva se "iskrivljenja" ne mogu vizualno primijetiti.
Ili možete pogledati kvantizacijske matrice raznih kamera.

Kodiranje

Prije nego krenemo dalje, moramo upotrijebiti jednostavnije primjere da bismo razumjeli kako možemo komprimirati dobivene vrijednosti.

Primjer 0(za zagrijavanje)
Zamislite takvu situaciju da vam je prijatelj kod kuće zaboravio papirić s popisom i traži da ga izdiktirate preko telefona (nema drugih načina komunikacije).
Popis:

• d9rg3
• wfr43gt
• wfr43gt
• d9rg3
• d9rg3
• d9rg3
• wfr43gt
• d9rg3

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

Riječi ćemo označavati kao A, B, C..., i nazivati ​​ih simbolima. Štoviše, pod simbolom se može sakriti bilo što: slovo abecede, riječ ili nilski konj u zoološkom vrtu. Glavna stvar je da identični simboli odgovaraju identičnim pojmovima, a različiti odgovaraju različitim. Budući da je naš zadatak učinkovito kodiranje (kompresija), radit ćemo s bitovima, budući da su to najmanje jedinice prikaza informacija. Stoga, napišimo popis 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
Kodiraj ABC.
3m različiti likovi(A, B, C) se ne mogu uspoređivati ​​ni na koji način 2 moguće vrijednosti bitovi (0 i 1). I ako je tako, onda možete koristiti 2 bita po simbolu. Na primjer:

• O: 00
• B:01
• C: 10

Slijed bitova povezanih sa simbolom nazvat ćemo kod. ABC će biti kodiran ovako: 000110.

Primjer 2
Kodiraj AAAAAABC.
Korištenje 2 bita po znaku A čini se pomalo rasipnim. Što ako probate ovo:

• C: 00

Kodirani niz: 000000100.
Očito, ova opcija nije prikladna, jer nije jasno kako dekodirati prva dva bita ovog niza: kao AA ili kao C? Vrlo je rasipno koristiti bilo kakav separator između kodova, razmislit ćemo kako tu prepreku zaobići na drugačiji način. Dakle, neuspjeh je zbog činjenice da kod C počinje kodom A. Ali mi smo odlučni kodirati A s jednim bitom, čak i ako B i C imaju po dva. Na temelju te želje A dajemo kod 0. Tada kodovi B i C ne mogu početi s 0. Ali mogu početi s 1:

• B: 10
• C: 11

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

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

Očito redoslijed znakova 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 ili relativna vrijednost, koja odražava udio njegovog pojavljivanja, ili apsolutna vrijednost, jednaka broju znakova. Glavno je da su težine proporcionalne pojavljivanju simbola.

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

• O: pa
• B: pb
• C: kom
• D:pd

Bez gubitka općenitosti, neka je pa ≥ pb ≥ pc ≥ pd. Postoje samo dvije opcije koje se bitno razlikuju u duljini koda:


Koji je poželjniji? Da biste to učinili, trebate izračunati rezultirajuće duljine 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 =>godišnje< pc+pd.
Ako se C i D zajedno pojavljuju češće od ostalih, tada njihov zajednički vrh prima najkraći jednobitni kod. Inače, jedan bit ide znaku A. To znači da se unija znakova ponaša kao neovisni znak i ima težinu jednaku zbroju ulaznih znakova.
Općenito, ako je p težina znaka predstavljena udjelom njegovog pojavljivanja (od 0 do 1), tada je najbolja duljina koda s=-log 2 p.
Pogledajmo ovo jednostavan slučaj(lako ga je zamisliti u obliku stabla). Dakle, moramo kodirati 2 s znakova s ​​jednakim težinama (1/2 s). Zbog jednakosti težina, duljine kodova bit će iste. Svaki znak zahtijeva s bitova. To znači da ako je težina simbola 1/2 s, onda je njegova duljina s. Ako težinu zamijenimo s p, dobivamo duljinu koda s=-log 2 p . To znači da ako se jedan znak pojavljuje dva puta češće od drugog, tada će duljina njegovog koda biti jedan bit duža. Međutim, ovaj zaključak je lako izvući ako se sjetite da vam dodavanje jednog bita omogućuje udvostručenje broja mogućih opcija.
I još jedno zapažanje - dva simbola s najmanjim težinama uvijek imaju najveću, ali jednake duljinešifre Štoviše, njihovi su dijelovi, osim posljednjeg, isti. Da to nije točno, onda bi se barem jedan kod mogao skratiti za 1 bit bez razbijanja prefiksa. To znači da su dva simbola s najmanjim težinama u kodno stablo imaju zajedničkog roditelja na višoj razini. To možete vidjeti u primjerima C i D iznad.

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

1. Svi simboli poredani su silaznim redoslijedom težine.
2. Zadnja dva simbola su spojena u grupu. Ovoj grupi se dodjeljuje težina jednaka zbroju težina ovih elemenata. Ova grupa sudjeluje u algoritmu zajedno sa simbolima i drugim grupama.

Koraci se ponavljaju sve dok ne ostane samo jedna grupa. Unutar svake grupe, jednom znaku (ili podskupini) je dodijeljen bit 0, a drugom znaku bit 1.
Ovaj algoritam se naziva Huffmanovo kodiranje.
Ilustracija prikazuje primjer s 5 znakova (A: 8, B: 6, C: 5, D: 4, E: 3). S desne strane je težina simbola (ili grupe).

Kodiramo koeficijente

Vratimo se. Sada imamo mnogo blokova sa 64 koeficijenta u svakom, koje treba nekako spremiti. Najjednostavnije rješenje je korištenje fiksnog broja bitova po koeficijentu - očito neuspješno. Izgradimo histogram svih dobivenih vrijednosti (tj. Ovisnost broja koeficijenata o njihovoj vrijednosti):

Napomena - skala je logaritamska! Možete li objasniti razlog pojave klastera vrijednosti većih od 200? Ovo su DC koeficijenti. Budući da se jako razlikuju od ostalih, ne čudi što su zasebno kodirani. Evo samo DC:

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

Ovo je bolje, jer su vrijednosti općenito koncentrirane oko nule (ali Huffmanov algoritam će opet dati preveliko stablo). Male vrijednosti (po apsolutna vrijednost) su česti, veliki su rijetki. A budući da male vrijednosti zauzimaju nekoliko bitova (ako se uklone vodeće nule), dobro se poštuje jedno od pravila kompresije: simbolima s velikim težinama dodjeljuju se kratki kodovi (i obrnuto). Trenutno smo ograničeni nepoštivanjem još jednog pravila: nemogućnosti jednoznačnog dekodiranja. Općenito, ovaj problem je riješen na sljedeće načine: baviti se kodom za razdvajanje, odrediti duljinu koda, koristiti prefiksni kodovi(već ih znate - ovo je slučaj kada nijedan kod ne počinje s drugim). Idemo s drugom jednostavnom opcijom, tj. svaki koeficijent (točnije, razlika između susjednih) bit će napisan ovako: (duljina) (vrijednost), prema ovom znaku:

To jest, pozitivne vrijednosti su izravno 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 duljine. Budući da postoji 12 mogućih vrijednosti, 4 bita se mogu koristiti za pohranu duljine. Ali ovdje je bolje koristiti Huffmanovo kodiranje.

Najviše je vrijednosti s duljinama 4 i 6, pa 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? Uostalom, možete sigurno podići "9" na višu razinu, pored "0"? Činjenica je da u JPEG-u ne možete koristiti kod koji se sastoji samo od jedinica - takav kod je rezerviran.
Postoji još jedna značajka. Kodovi dobiveni opisanim Huffmanovim algoritmom možda se neće podudarati u bitovima s kodovima u JPEG-u, iako će njihove duljine biti iste. Pomoću Huffmanovog algoritma dobivaju se duljine kodova i generiraju se sami kodovi (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 popisa je pohranjeno: 0,2,3,1,1,1,1,1. I, naravno, pohranjuje se popis vrijednosti: 4,6,3,5,7,2,8,1,0,9. Tijekom dekodiranja kodovi se generiraju na isti način.

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

Gledajmo AC:

Budući da je graf vrlo sličan grafu za DC razlike, princip je isti: [Huffmanov kod za AC duljinu (u bitovima)]. Ali ne baš! Budući da je skala na grafikonu logaritamska, to se ne može odmah primijetiti nulte vrijednosti otprilike 10 puta veća od vrijednosti 2, sljedeće po učestalosti. To je razumljivo - nisu svi preživjeli kvantizaciju. Vratimo se matrici vrijednosti dobivenih tijekom faze kvantizacije (koristeći matricu kvantizacije FastStone, 90%).

Budući da postoji mnogo grupa uzastopnih nula, nameće se ideja - zapisati samo broj nula u grupi. Ovaj algoritam kompresije naziva se RLE (Run-length encoding). Ostaje još otkriti smjer obilaznice “uzastopnih” – tko iza koga stoji? Pisanje s lijeva na desno i odozgo prema dolje nije vrlo učinkovito, budući da su koeficijenti različiti od nule koncentrirani blizu gornjeg lijevog kuta, a što su bliže donjem desnom kutu, to je više nula.

Stoga JPEG koristi redoslijed koji se zove "Zig-zag", koji je prikazan na lijevoj slici. Ova metoda dobro razlikuje grupe nula. Na desnoj slici - alternativni način premosnica, nije vezana za JPEG, ali sa zanimljivim imenom (dokaz). Može se koristiti u MPEG-u za isprepletenu video kompresiju. Odabir algoritma prolaska ne utječe na kvalitetu slike, ali može povećati broj kodiranih skupina nula, što u konačnici može utjecati na veličinu datoteke.
Promijenimo naš unos. Za svaki AC koeficijent koji nije nula:
[Broj nula prije AC][Huffmanov kod za duljinu AC (u bitovima)]
Mislim da odmah možete reći da je Huffman savršeno kodirao i broj nula! Ovo je vrlo blizak i dobar odgovor. Ali može se malo optimizirati. Zamislimo da imamo neki koeficijent AC ispred kojeg je bilo 7 nula (naravno, ako je napisano cik-cak). Ove nule su duh vrijednosti koji nije preživio kvantizaciju. Najvjerojatnije je i naš koeficijent jako oštećen i postao je mali, što znači da mu je duljina kratka. To znači da su broj nula ispred AC i duljina AC zavisne veličine. Stoga to pišemo ovako:
[Huffmanov kod za (broj nula prije AC, duljina AC (u bitovima)]
Algoritam kodiranja ostaje isti: oni parovi (broj nula ispred AC, duljina AC) koji se često pojavljuju primit će kratke kodove i obrnuto.

Gradimo histogram količinske ovisnosti za te parove i Huffmanovo stablo.


Dugi “brdski greben” potvrđuje našu pretpostavku.

Značajke implementacije u JPEG:
Takav par zauzima 1 bajt: 4 bita za broj nula i 4 bita za duljinu AC. 4 bita su vrijednosti od 0 do 15. Za duljinu AC to je više nego dovoljno, ali može li biti više od 15 nula? Zatim 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. Budući da uvijek ima puno nula blizu kraja bloka, par (0,0) se koristi nakon posljednjeg koeficijenta koji nije nula. Ako se naiđe tijekom dekodiranja, tada su preostale vrijednosti 0.

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

Slika u boji

Način prikaza slike u boji ovisi o odabranom model u boji. Jednostavno rješenje je koristiti RGB i zasebno kodirati svaki kanal boje slike. Tada se kodiranje neće razlikovati od kodiranja sive slike, samo 3 puta više posla. Ali kompresija slike može se povećati ako se prisjetimo da je oko osjetljivije na promjene svjetline nego boje. To znači da se boja može pohraniti uz veće gubitke od svjetline. RGB nema zaseban kanal svjetline. Ovisi o zbroju vrijednosti svakog kanala. Stoga je RGB kocka (ovo je prikaz svih mogućih vrijednosti) jednostavno "postavljena" na dijagonalu - što je viša, to je svjetlija. Ali tu se ne zaustavljaju - kocka je malo pritisnuta sa strane i ispada više poput paralelopipeda, ali to je samo da se uzmu u obzir značajke oka. Na primjer, osjetljiviji je na zelenu nego na plavu. Tako se pojavio model YCbCr.

(Slika s Intel.com)
Y je komponenta osvjetljenja, Cb i Cr su komponente razlike plave i crvene boje. Stoga, ako žele više komprimirati sliku, tada se RGB pretvara u YCbCr, a kanali Cb i Cr se stanji. Odnosno, podijeljeni su u 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 2 ili 4 puta okomito i/ili vodoravno.

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 boja (kanale) na bilo koji način i svaka će biti spremljena zasebno. Svjestan sam upotrebe sivih tonova (1 kanal), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Prva tri podržavaju gotovo svi, ali ima problema sa zadnjim 4-kanalnim. FastStone, GIMP ih ispravno podržavaju, a standardni Windows programi, paint.net ispravno izvlače sve informacije, ali onda izbacuju 4. crni kanal, dakle (rekao je da ga ne bacaju, pročitajte njegove komentare) prikaži više svijetla slika. S lijeve strane je klasični YCbCr JPEG, s desne strane je CMYK JPEG:



Ako se razlikuju u boji ili je vidljiva samo jedna slika, najvjerojatnije imate IE (bilo koju verziju) (UPD. u komentarima kažu "ili Safari"). Možete pokušati otvoriti članak u različitim preglednicima.

I još jedna stvar

Ukratko o dodatnim značajkama.

Progresivni način rada

Rastavimo dobivene tablice DCT koeficijenata na zbroj tablica (otprilike 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 članove (kao što smo već naučili: Huffman i cik-cak obilazak), zatim drugi, itd. Ovaj trik je koristan kada je internet spor, jer se prvo učitavaju samo DC koeficijenti koji se koriste za konstruirajte grubu sliku s 8x8 "piksela". Zatim zaokružite AC koeficijente za pročišćavanje brojke. Zatim njihove grube korekcije, pa 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 duljinu kodova, jer svaka faza koristi svoju Huffmanovu tablicu.

Način rada bez gubitaka

Kompresija bez gubitaka. Nema DCT-a. Koristi se predviđanje 4. točke na temelju tri susjedne. Pogreške predviđanja su Huffmanovo kodirane. Po mom mišljenju, koristi se malo češće nego nikad.

Hijerarhijski način rada

Iz slike se stvara nekoliko slojeva različitih razlučivosti. Prvi grubi sloj je kodiran kao i obično, a zatim samo razlika (pročišćavanje slike) između slojeva (pretpostavlja se da je Haarov valić). Za kodiranje se koristi DCT ili Lossless. Po mom mišljenju, koristi se malo rjeđe nego nikad.

Aritmetičko kodiranje

Huffmanov algoritam proizvodi optimalne kodove na temelju težine znakova, ali to vrijedi samo za fiksno preslikavanje znakova u kod. Aritmetika nema tako kruto vezanje, što omogućuje korištenje kodova kao s frakcijskim brojem bitova. Tvrdi da smanjuje veličinu datoteke u prosjeku za 10% u usporedbi s Huffmanom. Nije široko rasprostranjeno zbog problema s patentima, ne podržavaju ga svi.

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

UPD
predloženo s naznakom korištenog softvera. Zadovoljstvo mi je objaviti da je sve dostupno i besplatno:

• Python + NumPy + Matplotlib + PIL (Jastuk). Glavni alat. Našao sam ga tražeći "Matlab besplatna alternativa". Preporučam! Čak i ako niste upoznati s Pythonom, u samo nekoliko sati naučit ćete kako računati i graditi prekrasne grafikone.
• JpegSnoop. Prikazuje detaljne informacije o jpeg datoteci.
• yEd. Uređivač grafikona.
• Inkscape. U njemu sam napravio ilustracije, poput primjera Huffmanovog algoritma. Pročitao sam nekoliko lekcija, pokazalo se vrlo cool.
• Urednik Daumovih jednadžbi. tražio sam vizualni urednik formule, budući da nisam baš prijatelj s lateksom. Daum Equation dodatak je za Chrome koji smatram vrlo zgodnim. Osim bockanja mišem, možete urediti Latex.
• FastStone. Mislim da ga nema potrebe predstavljati.
• PicPick. Besplatna alternativa SnagIt. Sjedi u traci, snima zaslon onoga što govore i gdje to govore. Plus sve vrste stvari, kao što su ravnala, pipete, kutomjeri itd.

Oznake:

• jpeg
• dct
• dft
• Fourier
• Huffman

Dodaj oznake

Područje primjene

JPEG algoritam najprikladniji za sažimanje fotografija i slika koje sadrže realistične scene s glatke prijelaze svjetlinu i boju. JPEG je najrašireniji u digitalnoj fotografiji te za pohranu i prijenos slika putem Interneta.

S druge strane, JPEG je malo koristan za komprimiranje crteža, teksta i grafike znakova, gdje oštri kontrasti između susjednih piksela dovode do primjetnih artefakata. Preporučljivo je pohraniti takve slike u formatima bez gubitaka kao što su TIFF, GIF ili PNG.

JPEG (kao i druge metode kompresije izobličenja) nije prikladan za komprimiranje slika tijekom višestupanjske obrade, jer će se izobličenja unijeti u slike svaki put kada se spremaju međurezultati obrade.

JPEG se ne smije koristiti u slučajevima kada su čak i minimalni gubici neprihvatljivi, na primjer, kod kompresije astronomskih ili medicinskih slika. U takvim slučajevima može se preporučiti način kompresije JPEG bez gubitaka koji omogućuje JPEG standard (koji, međutim, ne podržava većina popularnih kodeka) ili standard kompresije JPEG-LS.

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), međutim, specifikacija JFIF (JPEG File Interchange Format, koju su 1991. godine predložili stručnjaci iz C-Cube Microsystems, a koja je sada postala de facto standard) uključuje korištenje RGB->YCbCr pretvorbe.

Nakon RGB->YCbCr konverzije za slikovne kanale Cb i Cr, koji su odgovorni za boju, može se izvršiti "poduzorkovanje", koje se sastoji u tome da se svakom bloku od 4 piksela (2x2) kanala svjetline Y dodjeljuje prosječne 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 (shema “4:1:0”). Također je moguće koristiti različite vrste stanjivanja za Cb i Cr, ali u praksi se takve sheme koriste izuzetno rijetko.

Zatim se komponenta svjetline Y i komponente boje Cb i Cr dijele na blokove od 8x8 piksela. Svaki takav blok podvrgava se diskretnoj kosinusnoj transformaciji (DCT). Rezultirajući DCT koeficijenti su kvantizirani (općenito se koriste različite matrice kvantizacije za Y, Cb i Cr) i pakirani korištenjem run i Huffmanovog kodiranja. JPEG standard također dopušta korištenje mnogo učinkovitijeg aritmetičkog kodiranja, međutim, zbog patentnih ograničenja (patent za aritmetički QM koder opisan u JPEG standardu pripada IBM-u), rijetko se koristi u praksi. Najnovije verzije popularne biblioteke libjpeg uključuju podršku za aritmetičko kodiranje, ali gledanje slika komprimiranih ovom metodom može biti problematično jer mnogi preglednici ne podržavaju njihovo dekodiranje.

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 kao JPEG datoteke, parametar kvalitete je naveden u nekoj proizvoljnoj jedinici, na primjer, od 1 do 100 ili od 1 do 10. Veći broj obično odgovara boljoj kvaliteti (i većoj veličini komprimirana datoteka). Međutim, čak i 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 softvera nisu pridonijeli 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 "skeniranja", odnosno niza kodiranih podataka koji odgovaraju sekvencijalno proslijeđenim ("skeniranim") slika. 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 cijelog skupa DCT koeficijenata, već samo nekog njihovog dijela: prvi - niskofrekventni, u sljedećim skeniranjima - visokofrekventni (metoda "spektralne selekcije", tj. spektralnih uzoraka), ili sekvencijalnim, od skeniranja do skeniranja, prečišćavanjem DCT koeficijenata (metoda “sukcesivne aproksimacije”, odnosno sukcesivne 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 (lossless, to jest, "lossless", 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 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, odnosno 0xFF i identifikator) i sami podaci. Ova struktura datoteke omogućuje vam brzo pronalaženje oznake s potrebnim podacima (na primjer, duljina linije, broj linija i broj komponenti boje komprimirane slike).

Osnovni JPEG markeri

Marker	Bajtovi	Duljina	Svrha	Komentari
PA JA	0xFFD8	Ne	Početak slike
SOF0	0xFFC0	promjenjiva veličina	Početak okvira (osnovni, DCT)	Označava da je slika kodirana u osnovnom načinu pomoću DCT i Huffmanovog koda. Marker sadrži broj redaka i duljinu retka slike (dvobajtna polja s pomacima od 5 odnosno 7 u odnosu na početak markera), broj komponenti (bajt polje s pomakom 8 u odnosu na početak) markera), broj bitova po komponenti (bajt polje s pomakom 4 u odnosu na početak markera), kao i omjer komponenti (na primjer, 4:2:0).
SOF1	0xFFC1	promjenjiva veličina	Početak okvira (prošireno, DCT, Huffmanov kod)	Označava da je slika kodirana u proširenom načinu pomoću DCT i Huffmanovog koda. Oznaka sadrži broj linija i duljinu linije slike, broj komponenti, broj bitova po komponenti i omjer komponenti (na primjer, 4:2:0).
SOF2	0xFFC2	promjenjiva veličina	Početak okvira (progresivno, DCT, Huffmanov kod)	Označava da je slika kodirana u progresivnom načinu pomoću DCT i Huffmanovog koda. Oznaka sadrži broj linija i duljinu linije slike, broj komponenti, broj bitova po komponenti i omjer komponenti (na primjer, 4:2:0).
DHT	0xFFC4	promjenjiva veličina	Sadrži Huffmanove tablice	Određuje jednu ili više Huffmanovih tablica.
DQT	0xFFDB	promjenjiva veličina	Sadrži kvantizacijske tablice	Određuje jednu ili više kvantizacijskih tablica.
DRI	0xFFDD	4 bajta	Određuje interval ponavljanja	Postavlja interval između RST markera n u makroblokovima.
SOS	0xFFDA	promjenjiva veličina	Započnite skeniranje	Početak prvog ili sljedećeg skeniranja slike sa smjerom prijelaza slijeva nadesno odozgo prema dolje. Ako je korišten osnovni način kodiranja, koristi se jedno skeniranje. Pri korištenju progresivnih načina rada koristi se višestruko skeniranje. SOS oznaka je razdjelnik između informativnog (zaglavlje) i kodiranog (zapravo komprimirani podaci) dijela slike.
RST n	0xFFD n	Ne	Ponovno pokretanje	Umetnut u svaki r makroblok, gdje r- Interval ponovnog pokretanja markera DRI. Ne koristi se ako nema DRI markera. n, niska 3 bita oznake koda, ciklusi od 0 do 7.
APP n	0xFFE n	promjenjiva veličina	Postavljeno aplikacijom	Na primjer, EXIF ​​JPEG datoteke koristi oznaku APP1 za pohranu metapodataka raspoređenih u strukturu temeljenu na TIFF-u.
COM	0xFFFE	promjenjiva veličina	Komentar	Sadrži tekst komentara.
EOI	0xFFD9	Ne	Kraj kodiranog dijela slike.

Prednosti i nedostatci

Nedostaci kompresije prema JPEG standardu uključuju pojavu karakterističnih artefakata u restauriranim slikama pri visokim stopama kompresije: slika je raspršena u blokove od 8x8 piksela (ovaj učinak je posebno vidljiv u područjima slike s glatkim promjenama svjetline), u područjima s visokom prostornom frekvencijom (na primjer, konture kontrasta i granice slike), artefakti se pojavljuju u obliku aureola šuma. Treba napomenuti da standard JPEG (ISO/IEC 10918-1, Aneks K, klauzula K.8) predviđa upotrebu posebnih filtara za suzbijanje artefakata blokiranja, ali u praksi takvi filtri, unatoč njihovoj visokoj učinkovitosti, praktički nisu koristi se. Međutim, unatoč svojim nedostacima, JPEG je postao vrlo raširen zbog prilično visokog (u odnosu na alternative koje su postojale u vrijeme njegove pojave) omjera kompresije, podrške za kompresiju slika u boji i relativno niske računalne složenosti.

Performanse JPEG kompresije

Kako bi se ubrzao proces kompresije prema JPEG standardu, tradicionalno se koristi paralelizacija izračuna, posebice pri izračunavanju DCT. Povijesno gledano, jedan od prvih pokušaja da se ubrza proces kompresije korištenjem ovog pristupa opisan je u radu objavljenom 1993. od strane Kasperovicha i Babkina, koji je predložio originalnu DCT aproksimaciju koja omogućuje učinkovito paraleliziranje izračuna korištenjem 32-bitne opće namjene registri Intel procesori 80386. Produktivniji su se pojavili kasnije računalni sklopovi korištena SIMD proširenja skupa instrukcija x86 procesora. Mnogo najbolje rezultate omogućuju postizanje shema koje koriste računalne mogućnosti grafičkih akceleratora (NVIDIA CUDA i AMD FireStream tehnologije) za organiziranje paralelnih izračuna ne samo DCT-a, već i drugih stupnjeva JPEG kompresija(pretvorba prostora boja, razina izvođenja, statističko kodiranje, itd.), i za svaki 8x8 blok kodirane ili dekodirane slike. Članak je prvi put [ izvor?] predstavlja implementaciju paralelizacije svih faza JPEG algoritma korištenjem CUDA tehnologije, čime je značajno ubrzana izvedba kompresije i dekodiranja korištenjem JPEG standarda.

U 2010. godini znanstvenici iz projekta PLANETS stavili su upute za čitanje JPEG formata u posebnu kapsulu, koja je smještena u posebnom bunkeru u švicarskim Alpama. To je učinjeno s ciljem očuvanja informacija o digitalnim formatima popularnim početkom 21. stoljeća za potomke.

vidi također

Bilješke

Linkovi

• JFIF specifikacija 1.02 (tekstualna datoteka)
• JPEG optimizacija. 1. dio, 2. dio, 3. dio.

Područje primjene

Format je format kompresije s gubitkom, pa je netočno misliti da JPEG pohranjuje podatke kao 8 bita po kanalu (24 bita po pikselu). S druge strane, budući da su JPEG komprimirani i dekomprimirani podaci obično predstavljeni u formatu od 8 bita po kanalu, ova se terminologija ponekad koristi. Podržana je i kompresija crno-bijelih polutonskih slika.

Prilikom spremanja JPEG datoteke možete odrediti stupanj kvalitete, a time i stupanj 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 boljoj kvaliteti , ali se veličina datoteke povećava. Obično se razlika u kvaliteti između 90 i 100 praktički ne opaža okom. Upamtite da slika vraćena iz JPEG formata nije točna kopija izvornik. Uobičajena zabluda je da JPEG kvaliteta identičan udjelu pohranjenih informacija.

Široko rasprostranjena podrška za JPEG format od strane raznih softvera često dovodi do JPEG kodiranja slika koje nisu bile namijenjene za tu svrhu - bez ikakvog dobitka u kompresiji u usporedbi s ispravno napravljenim PNG ili GIF, ali s nesretnim posljedicama za kvalitetu. Na primjer, pokušaj snimanja slike u JPEG formatu koja sadrži male kontrastne detalje (osobito one u boji) dovest će do pojave karakterističnih, jasno vidljivih artefakata čak i na visokoj "razini kvalitete".

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, za kanale slike Cb i Cr, koji su odgovorni za boju, može se izvršiti “poduzorkovanje” koje se sastoji u tome da se svakom bloku od 4 piksela (2x2) kanala svjetline Y dodjeljuje prosječne vrijednosti Cb i Cr (shema stanjivanja "4:2:0". U ovom slučaju, za svaki 2x2 blok, umjesto 12 vrijednosti (4 Y, 4 Cb i 4 Cr), koristi se samo 6 (4 Y i jedan prosječni Cb i Cr).Ako kvaliteta kompresije rekonstruirane slike ima povećane zahtjeve, stanjivanje se može izvesti samo u jednom smjeru - vertikalno (shema "4:4:0") ili horizontalno ("4:2 :2"), ili se uopće ne izvodi ("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 (vertikalno ili vodoravno), to jest za blokove 1x4 ili 4x1 (shema "4:1:1"). Također je moguće koristiti različite vrste stanjivanja za Cb i Cr, ali u praksi su takve sheme izuzetno rijetke.

Zatim se komponenta svjetline Y i komponente boje Cb i Cr dijele na blokove od 8x8 piksela. Svaki takav blok podvrgava se diskretnoj kosinusnoj transformaciji (DCT). Rezultirajući DCT koeficijenti su kvantizirani (općenito se koriste različite matrice kvantizacije za Y, Cb i Cr) i pakirani pomoću Huffmanovih kodova. JPEG standard također omogućuje korištenje mnogo učinkovitijeg aritmetičkog kodiranja, međutim, zbog patentnih ograničenja (patent za aritmetički QM koder opisan u JPEG standardu pripada IBM-u), on se ne koristi 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.

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 bloku kodirane slike, a rezultati kodiranja se sekvencijalno smještaju u izlazni tok u obliku jednog "skena" (niza kodiranih podataka). 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 cijelog skupa DCT koeficijenata, već samo nekog njihovog dijela: prvi - niskofrekventni, u sljedećim skeniranjima - visokofrekventni (metoda "spektralne selekcije", tj. spektralni uzorci ), ili sekvencijalnim, od skeniranja do skeniranja, prečišćavanjem DCT koeficijenata (metoda “sukcesivne aproksimacije”, tj. uzastopne aproksimacije). Ovaj progresivni prikaz podataka posebno je koristan pri prijenosu komprimiranih slika korištenjem sporih komunikacijskih kanala, budući da vam omogućuje pregled cijele slike nakon što je prenesen samo mali dio 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 dobiti metodom koja, unatoč sličnosti u nazivima, nije izravno povezana s JPEG ISO/IEC 10918-1 (ITU T.81 preporuka) standardom JPEG-LS kompresija, opisan standardom ISO/IEC 14495-1 (preporuka ITU T.87).

Sintaksa i struktura

JPEG datoteka sadrži slijed markera, od kojih svaki počinje s 0xFF bajtom 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.

Osnovni JPEG markeri

Marker	Bajtovi	Duljina	Svrha

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:

Napomenimo odmah da se inverzna transformacija lako dobiva množenjem inverzne matrice s vektorom, 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 koeficijenti u gornjem lijevom kutu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj komponenti.

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. Vektor transformiramo pomoću modificiranog RLE algoritma, čiji izlaz su parovi tipa (preskoči, broj), gdje je “preskoči” brojač preskočenih nula, a “broj” je vrijednost koju treba staviti u sljedeći ćelija. 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, različiti kodovi se koriste za DC i AC koeficijente, 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 je ovaj algoritam morao 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. Ispunjavanje posljednjeg postavljenog zahtjeva 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 je JPEG algoritam 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.

Adaptivno generiranje kvantizacijskih matrica u shemama sličnim JPEG

Lužkov Jurij Valerijevič,

postdiplomski student Sankt Peterburga državno sveučilište informacijske tehnologije, mehanike i optike.

Znanstveni voditelj – doktor tehničkih znanosti, prof

Tropčenko Aleksandar Yuvenalievich.

Uvod

U posljednjih godina Postoji jasna tendencija popularizacije shema kompresije slike s gubitkom na temelju valićnih transformacija. Međutim, formati kompresije slike koji se temelje na diskretnoj kosinusnoj transformaciji (DCT) još uvijek se najčešće koriste.

Rasprostranjen format JPEG (Joint Photographic Experts Group) [ Wallace G.K.] istraživačima postavlja sljedeće pitanje: je li moguće modificirati postojeću shemu kompresije na način da se poveća kvaliteta kompresije bez promjene algoritma dekompresije? Rješavanje ovog problema omogućit će implementaciju izmjena u postojeće kompresore bez brige o dostupnosti posebnog (modificiranog) softvera za dekompresiju slike od strane korisnika.

Pod shemom sličnom JPEG-u podrazumijevamo varijantu sheme kompresije s dijeljenjem slike u pravokutne fragmente, čiji su obvezni elementi: ortogonalna transformacija, kvantizacija pretvorenih podataka i njihovo naknadno statističko kodiranje.

Mnogi algoritmi kompresije koriste niz zadanih parametara. U JPEG-u to uključuje kvantizacijske matrice i Huffmanove tablice. Oni su pohranjeni u zaglavlju komprimirane datoteke i korisnik ih može samostalno odrediti, što omogućuje poboljšanje kvalitete kompresije.

Stoga je danas već predloženo nekoliko pristupa za sastavljanje JPEG kvantizacijskih matrica (na primjer, i ), koji, međutim, nisu univerzalni. U našem radu razmotrit ćemo generalizirani pristup adaptivnoj skalarnoj kvantizaciji koeficijenata spektra, koji je jednostavan za implementaciju i može se primijeniti u shemama sličnim JPEG.

Prilagodljiva kvantizacija signala

Kvantizacija je metoda obrade signala koja uključuje uvođenje izobličenja u signal. Suština skalarna kvantizacija svodi se na do dijeljenja raspona vrijednosti funkcije u konačan broj intervala i zatim odabira jedne vrijednosti koja predstavlja bilo koju vrijednost iz tog intervala.

Dakle, neka je zadan skup intervala i skup točaka funkcija kvantizacije je definiran kao za . Kada uniformna skalarna kvantizacija skup intervala može se predstaviti kao:

Gdje - parametar ili korak kvantizacije, – pomak osnovnog intervala, , – broj intervala koji je kodirani objekt. Tada se operacija kvantizacije može svesti na jednostavno dijeljenje sa zaokruživanjem:

.(1)

Prilagodljivost u skalarnoj kvantizaciji postiže se individualnim odabirom koraka kvantizacije za svaku kvantiziranu vrijednost.

Adaptivna skalarna kvantizacija temeljena na kriteriju težine

Pristup koji predlažemo temelji se na statistička analiza spektralnih koeficijenata. Može se koristiti u shemama kompresije (npr JPEG ) pod uvjetom da prozor za skeniranje signala ima stalnu veličinu.

Dakle, neka je dan niz količina, podijeljen naMidentični blokoviNvrijednosti u svakom, te je indeks elementa u danom bloku, odnosno svaki element ima svoj analog u bilo kojem drugom bloku. Suština predloženog pristupa je sljedeća: za svakinth elementa, izračunava se vrijednost posebnog težinskog kriterija, a korak kvantizacije zadanog elementa spektra postavlja se veći što je odgovarajuća vrijednost težinskog kriterija manja.

Stoga se postupak kvantizacije izvodi uzimajući u obzir neke statističke informacije o signalu, koje daje , prikupljene izMblokova i jedinstven za elemente svakog indeksa n. Funkcija kvantizacije (1) u ovom slučaju bit će označena kao , i funkcija kvantizacijskog parametra – .

Uvedimo kriterij, nazvavši ga koeficijent spektra težina. Vrijednost će odražavati stupanj značajnosti odgovarajućeg spektralnog položajankoeficijenti .

Jedna metoda izračuna temelji se na prosječnim amplitudama:

.(2)

Kao što su eksperimenti pokazali, izračun prema (2) za DCT koeficijente dovodi do neproporcionalne distribucije vrijednosti kriterija za koeficijente spektra visoke i niske frekvencije. Situaciju možete ispraviti korištenjem korektivna funkcija(vidi dolje), ili izračunavanjem vrijednosti na temelju maksimalnih amplituda:

.(3)

Prijeđimo na pitanje definiranja funkcije. Neka njegove vrijednosti budu ograničene rasponom . Uvedimo linearnu funkciju od:

,

gdje su i najmanja, odnosno najveća vrijednost (slučaj se razmatra zasebno).

U praksi može biti korisno koristiti nelinearnu funkciju od , što se postiže upotrebom funkcije korekcije:

.(4)

Budući da any općenito ovisi o svim elementima izvornog spektralnog vektora, funkcijaEtakođer ovisi o . Zapravo, ovo je funkcija koraka kvantizacije signala. Uvedimo notaciju . Tada formula (4) konačno poprima oblik:

.(5)

Dakle, funkcija koraka kvantizacije je lokalizirana u rasponu oda 1 do a 2 Variranjem njegovog oblika moguće je u većoj ili manjoj mjeri potisnuti pojedine skupine koeficijenata.

Primijenimo sada predloženi pristup za adaptivno generiranje kvantizacijskih matrica u krugu JPEG . U (5) koristit ćemo linearnu korekcijsku funkciju i kriterij maksimalnih amplituda (3).

Grafovi zadanih kvantizacijskih korak funkcija JPEG prikazani su na sl.1 preostao. Δ Grafikoni prilagođeno generirani za sliku "Starac" prikazani su na sl.1, točno. U oba slučaja, vrijednosti su poredane uzlaznim redoslijedom. Kao što vidite, za prvu trećinu vrijednosti argumenata postoji nagli porast Δ, što je posebno tipično za generirane funkcije. Na ovoj stranici generiranΔ na nekim mjestima značajno premašuje standardne vrijednosti, što dovodi do većeg potiskivanja odgovarajućih frekvencija.

Riža. 1. Standardne i generirane funkcije parametara kvantizacije s uređenim

uzlazne vrijednosti.

Grafikon za sliku "Starac» prikazano je na sl.2 su ostala. Desno su rezultati kompresije korištenjem zadanih matrica i matrica generiranih u sklopu eksperimenta. Kao što je vidljivo iz rezultata, razlika u omjeru kompresije je do 20% u korist adaptivnog pristupa s istim vrijednostima PSNR.

Riža. 2. Generiranje adaptivnih kvantizacijskih matrica za sklop JPEG.

Zaključak

Predložili smo metodu za adaptivnu skalarnu kvantizaciju koeficijenata spektra, koja se temelji na izračunavanju kriterija značajnosti spektralnih komponenti. Kao što su eksperimenti pokazali, korištenje razmatranog pristupa u krugu JPEG omogućuje vam da dobijete dobitak u omjeru kompresije do 20% u usporedbi s korištenjem standardnih kvantizacijskih matrica.

Praktična uporaba razmatrane modifikacije uključuje implementaciju samo kompresora, a za pregled slika dovoljno je koristiti standardni JPEG -dekompresor, što je važna prednost predloženog rješenja.

Književnost

1. Fung H. T., Parker K. J. Dizajn kvantizacijskih tablica prilagođenih slici za JPEG // Journal of Electronic Imaging. – 1996. – God. 4, N. 2. – S. 144 – 150.

2. Gray R.M., Neuhoff D.L.Kvantizacija // IEEE Transactions on Information Theory. – 1998. – God. 44, N. 6. – P. 2325 – 2383.

3. Ratnakar V., Livny M. Proširenje RD -OPT s globalnim pragom za JPEG optimizaciju // Data Compression Conference.– 1996.

4. Wallace G. K. Standard kompresije JPEG fotografije // IEEE Trans. Potrošačke elektronike. – 1992. – God. 38, broj 1. – str. 18 – 34.