Algoritam je razvijen od strane Joint Photographic Expert Group posebno za kompresiju 24-bitnih i sivih slika 1991. godine. Ovaj algoritam ne komprimira dvostepene slike vrlo dobro, ali vrlo dobro obrađuje slike s kontinuiranim tonovima, u kojima obližnji pikseli obično imaju slične boje. Obično oko ne može primijetiti nikakvu razliku kada se komprimira ovom metodom 10 ili 20 puta.
Algoritam se zasniva na DCT primenjenom na matricu blokova slika koji se ne preklapaju, veličine 8x8 piksela. DCT dekomponuje ove blokove prema amplitudama određenih frekvencija. Rezultat je matrica u kojoj mnogi koeficijenti imaju tendenciju da budu blizu nule, što se može prikazati u grubom numeričkom obliku, tj. u kvantiziranom obliku bez značajnog gubitka u kvaliteti restauracije.
Razmotrimo rad algoritma detaljnije. Pretpostavimo da komprimirate 24-bitnu sliku u punoj boji. U ovom slučaju dobijamo sledeće faze rada.
Korak 1. Prevodimo sliku iz RGB prostora u YCbCr prostor koristeći sljedeći izraz:
Odmah napominjemo da se inverzna transformacija lako dobija množenjem inverzna matrica na vektor koji je u suštini YUV prostor:
.
Korak 2 Originalnu sliku podijelimo na matrice 8x8. Formiramo tri DCT radne matrice od svake - 8 bita posebno za svaku komponentu. Pri visokim omjerima kompresije, blok 8x8 se razlaže na YCbCr komponente u formatu 4:2:0, tj. komponente za Cb i Cr su provučene kroz tačku u redovima i kolonama.
Korak 3 Primjena DCT-a na blokove slike 8x8 piksela. Formalno, direktni DCT za blok 8x8 se može napisati kao
gdje 
. Pošto je DCT "srce" JPEG algoritma, poželjno je u praksi da se izračuna što je brže moguće. Jednostavan pristup za ubrzavanje izračunavanja je da se unaprijed izračunaju kosinusne funkcije i da se rezultati izračuna u tabeli. Štoviše, s obzirom na ortogonalnost kosinusnih funkcija sa različite frekvencije, gornja formula se može napisati kao
.
Ovdje je 8x8 matrica koja opisuje 8-dimenzionalni prostor za predstavljanje blok stupaca u ovom prostoru. Matrica je transponirana matrica i radi istu stvar samo za blok redove. Rezultat je odvojiva transformacija, koja je zapisana u matričnom obliku kao
Ovdje je rezultat DCT-a, za čije izračunavanje su potrebne operacije množenja i gotovo isti broj sabiranja, što je mnogo manje od direktnih proračuna koristeći gornju formulu. Na primjer, da biste pretvorili sliku veličine 512x512 piksela, potrebne su aritmetičke operacije. Uzimajući u obzir 3 komponente svjetline, dobijamo vrijednost od 12.582.912 aritmetičkih operacija. Broj množenja i sabiranja može se dodatno smanjiti korištenjem algoritma brze Fourierove transformacije. Kao rezultat toga, da biste transformirali jedan blok 8x8, morat ćete napraviti 54 množenja, 468 sabiranja i pomaka bitova.
Kao rezultat DCT-a, dobijamo matricu u kojoj su koeficijenti na lijevoj strani gornji ugao odgovaraju niskofrekventnoj komponenti slike, au donjem desnom uglu - visokofrekventnoj.
Korak 4 Kvantizacija. U ovom koraku, neke informacije se odbacuju. Ovdje se svaki broj iz matrice dijeli posebnim brojem iz "tablice kvantizacije", a rezultat se zaokružuje na najbliži cijeli broj:
.
Štaviše, za svaku matricu Y, Cb i Cr, možete postaviti vlastite tablice kvantizacije. JPEG standard čak dozvoljava vlastite tablice kvantizacije, koje će, međutim, morati biti proslijeđene dekoderu zajedno sa komprimiranim podacima, što će povećati ukupnu veličinu datoteke. Jasno je da je korisniku teško samostalno izabrati 64 koeficijenta, pa JPEG standard koristi dva pristupa za matrice kvantizacije. Prvi je da JPEG standard uključuje dvije preporučene tabele kvantizacije: jednu za luma i jednu za hrominaciju. Ove tabele su prikazane u nastavku. Drugi pristup je sintetizacija (izračunavanje u hodu) tabele kvantizacije u zavisnosti od jednog parametra, koji je odredio korisnik. Sama tabela je izgrađena prema formuli
U koraku kvantizacije, omjer kompresije se kontrolira i dolazi do najvećeg gubitka. Jasno je da ćemo postavljanjem tablica kvantizacije sa velikim koeficijentima dobiti više nula i, posljedično, veći omjer kompresije.
Specifični efekti algoritma su takođe povezani sa kvantizacijom. Pri velikim vrijednostima koraka kvantizacije, gubici mogu biti toliki da se slika razbije na obične kvadrate 8x8. Zauzvrat gubici visoke frekvencije mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura formira valoviti "nimbus" s oštrim prijelazom boja.
Korak 5 Prevodimo matricu 8x8 u vektor od 64 elementa koristeći "cik-cak" skeniranje (slika 2).
Rice. 2. Cik-cak skeniranje
Kao rezultat toga, na početku vektora, po pravilu, biće upisani koeficijenti različiti od nule, a na kraju će se formirati lanci nula.
Korak 6 Vektor transformišemo modifikovanim RLE algoritmom, na čijem izlazu dobijamo parove tipa (skip, broj), gde je "skip" brojač preskočenih nula, a "broj" je vrednost koja se mora uneti sledeća ćelija. Na primjer, vektor 1118 3 0 0 0 -2 0 0 0 0 1 … bit će presavijen u parove (0, 1118) (0,3) (3,-2) (4,1) … .
Treba napomenuti da je prvi broj transformirane komponente u suštini jednak prosječnoj svjetlini bloka 8x8 i naziva se DC koeficijent. Slično za sve blokove slika. Ova okolnost sugerira da se DC koeficijenti mogu efikasno komprimirati ako se pohranjuju ne njihove apsolutne vrijednosti, već relativne u obliku razlike između DC koeficijenta trenutnog bloka i DC koeficijenta prethodnog bloka, i prvog bloka. koeficijent se čuva takav kakav jeste. U ovom slučaju, poredak DC koeficijenata može se izvršiti, na primjer, na sljedeći način (slika 3). Preostali koeficijenti, koji se nazivaju AC koeficijenti, ostaju nepromijenjeni.
Korak 7 Dobivene parove skupljamo koristeći neuniformne Huffmanove kodove s fiksnom tablicom. Osim toga, koriste se različiti kodovi za DC i AC koeficijente, tj. različite tabele sa Huffman kodovima.
Rice. 3. Šema uređenja DC koeficijenata
Rice. 4. Blok dijagram JPEG algoritma
Proces rekonstrukcije slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate slike 10-15 puta bez vidljivog gubitka vida.
Razvoj ovog standarda bio je vođen činjenicom da ovaj algoritam trebalo je da komprimuje slike prilično brzo - ne više od jedne minute na prosečnoj slici. Ovo je 1991! A njegova hardverska implementacija bi trebala biti relativno jednostavna i jeftina. U ovom slučaju, algoritam je morao biti simetričan u smislu vremena rada. Ispunjenje posljednjeg zahtjeva mogući izgled digitalni fotoaparati koji snimaju 24-bitne slike. Da je algoritam asimetričan, bilo bi neugodno dugo čekati dok se uređaj ne "napuni" - komprimira sliku.
Iako je JPEG algoritam ISO standard, njegov format datoteke nije fiksiran. Koristeći ovo, proizvođači kreiraju svoje, nekompatibilne formate, i stoga mogu promijeniti algoritam. Dakle, interne tabele algoritma koje preporučuje ISO su zamenjene njima sopstvenim. Postoje i varijante JPEG-a za specifične aplikacije.
JPEG algoritam je razvijen posebno za kompresiju slike od strane Joint Photographic Expert Group (JPEG) i baziran je na DCT.
DCT razlaže sliku u skup koeficijenata, od kojih neki mogu biti jednaki nuli zbog nekorištenja nekih DCT funkcija. Već koristim ovu činjenicu može se postići određena kompresija podataka. Ipak, najveći efekat se postiže uklanjanjem nekih beznačajnih koeficijenata (izjednačavanjem sa nulom).
Obično spolja matrica ima jasno vidljivu karakteristiku. Numeričke vrijednosti elemenata matrice brzo se smanjuju od gornjeg lijevog ugla do donjeg desnog kuta. Tako se najvažniji podaci stavljaju u gornji lijevi kut, a najmanje važni podaci u donji desni. Koristeći ovu činjenicu, najmanje značajni podaci se mogu eliminisati. Da biste to učinili, kvantizirajte transformirane podatke.
Ideja kvantizacije je da spektralna (frekvencijska) informacija mora premašiti poznati prag kako bi činila važan dio svih informacija o datom fragmentu slike. Upravo u fazi kvantizacije dolazi do gubitka dijela informacije i, posljedično, gubitka kvaliteta.
Kvantizacija se obično vrši na osnovu posebna matrica, koji sadrži djelitelje kojima će se elementi DCT-a trebati podijeliti. Često se koristi sljedeći algoritam:
Q(i,j) = 1 + ((1 + i + j)q);
Gdje je Q(i,j) matrica djelitelja,
q - parametar kvaliteta.
Odabirom parametra q, možete kontrolirati vrijednosti djelitelja i podesiti omjer kompresije. Na primjer, ako je q = 2, dobićete matricu sljedećeg oblika (slika 3.6):
Slika 3.6. Primjer matrice za kvantizaciju.
Nakon podjele 64 elementa matrice na elemente matrice Q(i,j), kao rezultat, matrica koja ima:
Bit će veliki broj dodatnih nultih vrijednosti,
Efekat smanjenja vrijednosti od gornjeg lijevog prema donjem desnom će biti još izraženiji.
Za ekonomičnu notaciju potrebno je promijeniti redoslijed obilaženja dobivenih vrijednosti na način da nizovi nultih elemenata budu što duži. Jedan od mogući načini promena redosleda prelaska je cik-cak metoda (slika 3.7).
Slika 3.7. Transformacija dvodimenzionalne matrice u jednodimenzionalni niz metodom "cik-cak".
Kao što se može vidjeti sa slike, dvodimenzionalna matrica od 8 x 8 elemenata se pretvara u jednodimenzionalni niz dužine 64 elementa. Glavno svojstvo takvog niza bit će lokacija najznačajnijih koeficijenata na njegovom početku, a najmanje značajni elementi(obično nule) na njegovom kraju.
Implementacija algoritma uključuje uzastopne radnje, što je ilustrovano na sl. 3.8.
Slika 3.8. Redoslijed operacija u implementaciji JPEG algoritma.
1. Ako je potrebno, slika se konvertuje u YUV format.
2. Razlika u boji U i V signali su uzorkovani prema formatu 4:2:0. Podjela slike na fragmente od 8 x 8 elemenata. Nadalje, obrada signala svjetline i boje može se obavljati nezavisno i paralelno.
3. Diskretna kosinusna transformacija se izvodi na svim blokovima od 8 x 8 elemenata.
4. Kvantizacija prema odabranom parametru kvaliteta.
5. Skeniranje "cik-cak" da bi se dobio jednodimenzionalni niz od 64 elementa.
6. RLE algoritam primijenjen na jednodimenzionalni niz.
7. Huffmanov algoritam se primjenjuje na sekvencu koja je već komprimirana sa RLE.
8. P.p. 3 - 7 se izvode za sve blokove u formatu 8 x 8 elemenata i za sve ravni boje.
Ključne karakteristike JPEG metoda su kako slijedi:
1. Visok omjer kompresije, posebno za slike koje se smatraju dobrim ili odličnim kvalitetom.
2. Veliki broj parametara koji omogućavaju sofisticiranom korisniku da eksperimentiše sa postavkama metode i postigne potrebnu ravnotežu kompresije/kvaliteta.
3. Dobri rezultati za sve vrste neprekidnih tonskih slika, bez obzira na njihovu rezoluciju, prostor boja, veličinu piksela ili druga svojstva.
4. Prilično sofisticirana metoda kompresije, ali ne previše komplikovana, koja vam omogućava da kreirate odgovarajuće uređaje i pišete programe za implementaciju metode za računare većine platformi, kao i za hardver.
5. Mogućnost korištenja kompresije bez gubitka informacija pri ne baš visokom omjeru kompresije.
Da biste efikasno komprimirali podatke, prvo morate procijeniti prirodu vaše slike. JPEG kompresuje slikovne podatke na osnovu onoga što ljudsko oko vidi. Stoga, da bih vam pomogao da shvatite kako i šta radi JPEG, želio bih vam dati opšta ideja na ljudsku vizuelnu percepciju.
JPEG kompresija se odvija u nekoliko faza. Cilj je transformirati grafičke podatke na način da se nebitne vizualne informacije lako identificiraju i odbace. Ova kompresija s gubitkom razlikuje se od većine drugih pristupa koji se koriste s grafičkim formatima, koji pokušavaju zadržati svaki dio slike netaknutim.
model u boji
Prvi korak u JPEG formatu je odabir odgovarajućeg načina za predstavljanje boja. Boje se obično specificiraju u 3D koordinatnom sistemu. Sistem dobro poznat većini programera opisuje boju kao kombinaciju crvene, zelene i plave (RGB). Nažalost, u smislu mogućnosti kompresije, to nije Najbolji način opisi boja. Problem je što su sve tri komponente - crvena, zelena i plava - ekvivalentne. Međutim, prelazak na drugi sistem prikazivanja boja vam omogućava da istaknete još neke važna informacija.
Profesionalci koriste dva modela boja: HSL (Hue-Saturation-Lightness) i HSV (Hue-Saturation-Value). Intuitivno je jasno da komponenta svjetline (Lightness) HSL modela i komponenta svjetline (Vrijednost) HSV modela određuju omjer svjetla i sjene svaka na svoj način. Zasićenost određuje nivo "čiste" boje. Nezasićene boje se često neformalno nazivaju "prljavim" (sivkastim). Nijansa je ono što doživljavamo kao boju objekta, kao što je crvena ili sivkasto zelena. Ovdje je važno napomenuti neverovatna činjenica: ljudski vid je osjetljiviji na promjene svjetla, a ne boje same po sebi!
Različite implementacije algoritma kompresije JPEG koriste različite sistemi boja. YCbCr sistem za prikazivanje boja koji koristi JFIF format je na mnogo načina sličan šemi razvijenoj prije mnogo godina za televiziju u boji.
stanjivanje
Glavni razlog za konverziju iz jednog modela boja u drugi je prepoznavanje informacija koje su manje relevantne za gledanje na slici. JPEG smanjuje količinu informacija o boji. Dok se komponenta osvjetljenja prenosi u punoj rezoluciji, komponente boje koriste polovinu raspona vrijednosti. Kao rezultat jednostavan korak količina podataka je smanjena za trećinu.
Subsampling prilagođava boje TV slike u boji. Obično na TV-u crno-bijela slika i informacije o boji se prenose odvojeno. Štaviše, informacije o boji se prenose u manje strogom obliku od informacija o svjetlini slike.
Diskretna kosinusna transformacija (DCT)
Svaka komponenta boje se tretira zasebno, kao da nisu u jednoj boji već tri slike u nijansama sive. Ako detaljnu sliku pogledate iz daljine, možete uočiti samo opći ton slike. Na primjer, "uglavnom plava" ili "uglavnom crvena". Što se više približavate slici, više detalja možete vidjeti. Da bi oponašao ovaj efekat, JPEG koristi matematički trik nazvan Diskretna kosinusna transformacija (DCT). DCT pretvara informacije o pikselima u informacije o promjeni piksela. Prva stvar koju DCT može dati je prosječna boja područja. Zatim sve više razrađuje detalje.
Kao u slučaju udaljenu sliku, prosječna vrijednost boje je vrlo važna informacija o području slike. Vaše oko je manje osjetljivo na brzinu promjene boje, tako da to nije toliko važno. Pretvaranje informacija o bojama Na sličan način, ističemo informacije koje možete donirati.
Vjeruje se da su gubici uzrokovani ovom fazom. Ako kodirate sliku koristeći DCT, a zatim je vratite koristeći inverznu DCT funkciju, nećete dobiti potpuno isti skup bitova. Međutim, ova greška je greška zaokruživanja. Javlja se prilikom izvođenja aritmetičkih operacija i obično nije velika. Stoga, više volim da razmišljam o DCT fazi kao o operaciji "uglavnom bez gubitaka".
Za velike slike izračunavanje DCT-a i inverznog DCT-a je veoma dugotrajan proces. Da bi smanjio vrijeme izračunavanja, JPEG dijeli sliku u mozaik od osam po osam piksela. Svaki od mozaika se obrađuje zasebno, što značajno smanjuje vrijeme proračuna potrebno za DCT. Problem koji se javlja s ovim pristupom je da nakon kvantizacije (o čemu će biti riječi u sljedećem odjeljku), granice ovih kvadrata možda se neće poklapati i stoga postaju vidljive kada se specificira niska vrijednost parametar kvaliteta.
Kvantizacija
JPEG programeri su prvenstveno bili zainteresovani za slike fotografskog kvaliteta (fotografski, kontinuirani ton). Po pravilu, ove polutonske slike karakteriziraju meki prelazi iz jedne boje u drugu. Za takve slike, niskofrekventna (sporo se mijenja) DCT komponenta je važnija od komponente visoke frekvencije (brzo mijenjanje).
Termin kvantizacija jednostavno znači "zaokruživanje". jpeg odbacuje neke grafičke informacije zaokruživanjem svakog člana DCT-a različitim težinama na osnovu različitih faktora. Komponenta visoke frekvencije je zaokružena više od komponente niske frekvencije. Na primjer, komponenta niske frekvencije, koja pohranjuje prosječnu vrijednost svjetline, može se zaokružiti na višestruki od tri, dok se komponenta visoke frekvencije može zaokružiti na višestruki od sto!
Operacija kvantizacije objašnjava zašto JPEG kompresija, u slučaju jasnih kontura, dovodi do formiranja "tremljivih" linija. Konture su određene visokofrekventnom (brzo mijenjanom) prostornom komponentom. (Na prvi pogled, moglo bi se činiti da biste trebali dobiti mutan obris, ali zapamtite da C u DCT označava kosinus.)
Tipično, ravni boja su kvantizirane mnogo grublje od ravni luma. Evo pravi izbor Model boja pomaže da se identifikuju informacije koje se mogu odbaciti.
Kompresija
Do sada, izuzev slučaja kada je frekvencija uzorkovanja dva kanali u boji, nije došlo do kompresije. Svi gore razmotreni koraci - transformacija modela boja, DCT i kvantizacija - ostavili su veličinu podataka nepromijenjenom. Konačno, dolazimo do posljednjeg koraka, tokom kojeg će standardna tehnika kompresije bez gubitaka zapravo smanjiti veličinu podataka.
Podaci sortirani u prethodnim koracima mogu se kompresovati efikasnije od sirovog materijala koji su RGB grafički podaci. Štaviše, nijedan od preduzetih koraka nije bio suvišan, svaka promena podataka je imala za cilj efikasnije kompresovanje konačne verzije.
Promjena modela boja omogućila je razrjeđivanje informacija o kanalu, a zatim ih snažnije kvantizirati.
DCT je omogućio da se izoluje visokofrekventna prostorna komponenta. Komponenta visoke frekvencije obično ima male vrijednosti, što rezultira nesrazmjernom količinom malih vrijednosti u izlazu DCT koraka, olakšavajući proces kompresije.
Tokom procesa kvantizacije, većina visokofrekventne komponente se postavlja na nulu, a ostatak poprima određene vrijednosti. Smanjenje broja različita značenja također olakšava proces kompresije podataka.
JPEG standard pruža dva različite metode kompresiju bez gubitaka koja se može koristiti na poslednji korak. Huffmanova kompresija je dugo poznati nepatentirani algoritam koji se lako programira. Za razliku od njega, više novi algoritam aritmetičko kodiranje je predmet brojnih patenata. (Stoga, nije iznenađujuće da mnogi programi za kompresiju JPEG podržavaju samo Huffmanovu kompresiju.)
Prilikom dekodiranja JPEG slike svi ovi koraci se moraju preduzeti obrnutim redosledom. Tok podataka se prvo dekompresuje, zatim se svaki blok od 8-8 podvrgava inverznom DCT-u, a na kraju se slika pretvara u odgovarajući model u boji(obično RGB). Imajte na umu da se informacije koje su namjerno odbačene decimacijom i kvantizacijom nikada ne vraćaju. Međutim, ako je sve urađeno ispravno, gubitak informacija neće uzrokovati vidljivu degradaciju slike.
Problemi sa algoritmima arhiviranja sa gubicimaKonvencionalni algoritmi su bili prvi koji su korišćeni za arhiviranje slika. One koje su korištene i koriste se u backup sistemima, pri kreiranju distribucija itd. Ovi algoritmi su arhivirali informacije nepromijenjene. Međutim, glavni trend u posljednje vrijeme bila je upotreba novih klasa slika. Stari algoritmi više ne ispunjavaju zahtjeve za arhiviranje. Mnoge slike praktički nisu bile komprimirane, iako su "na prvi pogled" imale očiglednu redundantnost. To je dovelo do stvaranja nove vrste algoritama - kompresije sa gubitkom informacija. U pravilu se može podesiti omjer arhiviranja, a samim tim i stepen gubitka kvaliteta u njima. U ovom slučaju se postiže kompromis između veličine i kvaliteta slika.
Jedan od ozbiljnih problema kompjuterske grafike je to što još nije pronađen adekvatan kriterijum za procenu gubitka kvaliteta slike. I stalno se gubi – pri digitalizaciji, pri konvertovanju u ograničenu paletu boja, pri pretvaranju u drugi sistem predstavljanja boja za štampu i, što je za nas posebno važno, kada se arhivira sa gubicima. Možemo dati primjer jednostavnog kriterija: standardna devijacija vrijednosti piksela (L 2 mjera ili srednji kvadrat - RMS):
Prema njemu, slika će biti jako oštećena kada se svjetlina smanji za samo 5% (oko to neće primijetiti - u različiti monitori postavka svjetline mnogo više varira). Istovremeno, slike sa "snijegom" - oštrom promjenom boje pojedinačnih tačaka, slabim prugama ili "moiréom" prepoznat će se kao "gotovo nepromijenjene" (Objasnite zašto?). I drugi kriterijumi imaju svoje nedostatke.
Uzmite u obzir, na primjer, maksimalno odstupanje:
Ova mjera je, kao što možete pretpostaviti, izuzetno osjetljiva na otkucaje pojedinačnih piksela. One. na cijeloj slici može se značajno promijeniti samo vrijednost jednog piksela (što je oko gotovo neprimjetno), međutim, prema ovoj mjeri, slika će biti ozbiljno oštećena.
Mjera koja se trenutno koristi u praksi naziva se mjera odnosa signal-šum (peak-to-peak signal-to-noise ratio - PSNR).
Ova mjera je, zapravo, slična standardnoj devijaciji, ali je nešto praktičnija za korištenje zbog logaritamske skale skale. Ima iste nedostatke kao i standardna devijacija.
Gubitak kvaliteta slike najbolje procjenjuje naše oči. Arhiviranje se smatra odličnim, u kojem je nemoguće okom razlikovati originalne i raspakirane slike. Dobro - kada znate koja od slika je arhivirana, možete uporediti samo dvije susjedne slike. Daljnjim povećanjem omjera kompresije, u pravilu, nuspojave karakteristične za ovaj algoritam postaju uočljive. U praksi, čak i uz odličan kvalitet zadržavanja, na slici se mogu vršiti redovne specifične promjene. Stoga se algoritmi arhiviranja s gubicima ne preporučuju za komprimiranje slika koje će kasnije biti ili odštampane u visokom kvalitetu ili obrađene programima za prepoznavanje slika. Neprijatni efekti kod ovakvih slika, kao što smo već rekli, mogu se pojaviti čak i kod jednostavnog skaliranja slike. JPEG algoritam
JPEG je jedan od najnovijih i prilično moćnih algoritama. To je praktično de facto standard za slike u punoj boji. Algoritam radi sa područjima 8x8, na kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, kada se matrica takve regije proširi u dvostruki niz u smislu kosinusa (pogledajte formule u nastavku), samo prvi koeficijenti ispadaju značajni. Dakle, kompresija u JPEG-u se vrši zbog glatkih promjena boja na slici.
Algoritam je razvila grupa stručnjaka za fotografiju posebno za kompresiju 24-bitnih slika. JPEG - Joint Photographic Expert Group - odjel unutar ISO - Međunarodne organizacije za standardizaciju. Naziv algoritma glasi ["jei" peg]. Općenito, algoritam se zasniva na diskretnoj kosinusnoj transformaciji (u daljem tekstu DCT) primijenjenoj na matricu slike da bi se dobila neka nova matrica koeficijenata. Za dobivanje originalne slike primjenjuje se inverzna transformacija.
DCT razlaže sliku na amplitude određenih frekvencija. Tako, prilikom transformacije, dobijamo matricu u kojoj su mnogi koeficijenti ili blizu ili jednaki nuli. Osim toga, zbog nesavršenosti ljudskog vida, moguće je grublje aproksimirati koeficijente bez primjetnog gubitka u kvaliteti slike.
Za to se koristi kvantizacija koeficijenata. U samom jednostavan slučaj je aritmetički pobitni pomak udesno. Ova transformacija gubi neke informacije, ali se mogu postići veliki omjeri kompresije.
Kako algoritam radi
Dakle, razmotrimo algoritam detaljnije. Recimo da komprimujemo 24-bitnu sliku.
Korak 1.
Prevodimo sliku sa prostor boja RGB, sa komponentama odgovornim za crvene (crvene), zelene (zelene) i plave (plave) komponente boje tačke, u YCrCb prostor boja (ponekad nazvan YUV).
U njemu je Y komponenta svjetline, a Cr, Cb su komponente odgovorne za boju (hromatska crvena i hromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za Cr i Cb komponente s visokim gubicima i, shodno tome, visokim omjerima kompresije. Slična transformacija se već dugo koristi na televiziji. Signalima odgovornim za boju dodjeljuje se uži frekvencijski pojas.
Pojednostavljeno, prijevod iz RGB prostora boja u YCrCb prostor boja može se predstaviti korištenjem prijelazne matrice:
Inverzna transformacija se vrši množenjem YUV vektora sa inverznom matricom.
Korak 2
Originalnu sliku podijelimo na matrice 8x8. Formiramo tri DCT radne matrice od svake - 8 bita posebno za svaku komponentu. Pri visokim omjerima 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 kucaju kroz red i kroz kolonu. One. od originalne 16x16 matrice dobija se samo jedna radna DCT matrica. U ovom slučaju, kao što je lako vidjeti, gubimo 3/4 korisne informacije o komponentama boje slike i odmah dobijamo dvostruku kompresiju. To možemo učiniti radeći u YCrCb prostoru. Kao što je praksa pokazala, to ne utiče mnogo na rezultujuću RGB sliku.
Korak 3
Mi primjenjujemo DCT na svaku radnu matricu. U ovom slučaju dobijamo matricu u kojoj koeficijenti u gornjem lijevom uglu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj komponenti.
U pojednostavljenom obliku, ova transformacija se može predstaviti na sljedeći način:
Korak 4
Radimo kvantizaciju. U principu, ovo je jednostavno podjela radne matrice element po element matrice kvantizacije. Za svaku komponentu (Y, U i V), u opštem slučaju, specificira se sopstvena matrica kvantizacije q (u daljem tekstu MC).
U ovom koraku se kontrolira omjer kompresije i dolazi do najvećeg gubitka. Jasno je da ćemo postavljanjem MC sa velikim koeficijentima dobiti više nula i, posljedično, veći omjer kompresije.
Specifični efekti algoritma su takođe povezani sa kvantizacijom. Pri visokim vrijednostima gama koeficijenta, gubici na niskim frekvencijama mogu biti toliko veliki da će se slika raspasti na kvadrate 8x8. Gubici na visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura s oštrim prijelazom boja formira neka vrsta "nimbusa".
Korak 5.
Prevodimo matricu 8x8 u vektor od 64 elementa koristeći “cik-cak” skeniranje, tj. uzeti elemente sa indeksima (0,0), (0,1), (1,0), (2,0)...
Dakle, na početku vektora dobijamo koeficijente matrice koji odgovaraju niske frekvencije, i na kraju - visoko.
Korak 6
Vektor konvolviramo koristeći algoritam grupnog kodiranja. U ovom slučaju dobijamo parove tipa (skip, broj), gde je „skip“ brojač preskočenih nula, a „broj“ je vrednost koja se mora staviti u sledeću ćeliju. Tako će vektor 42 3 0 0 0 -2 0 0 0 0 1 ... biti presavijen u parove (0,42) (0,3) (3,-2) (4,1) ... .
Korak 7
Dobivene parove savijamo Huffmanovim kodiranjem sa fiksnom tablicom.
Proces rekonstrukcije slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate neke slike 10-15 puta bez ozbiljnih gubitaka.
Operativni cjevovod koji se koristi u JPEG algoritmu.
značajan pozitivni aspekti algoritam je to:
- Postavlja omjer kompresije.
- slobodan dan slika u boji može imati 24 bita po tački.
- Povećanje omjera kompresije dijeli sliku na zasebne kvadrate (8x8). To je zbog činjenice da se veliki gubici javljaju na niskim frekvencijama tokom kvantizacije i postaje nemoguće vratiti originalne podatke.
- Pojavljuje se Gibbsov efekat - oreoli duž granica oštrih prijelaza boja.
Posljednji zahtjev je omogućio igračke kao što su digitalni fotoaparati - uređaji veličine male video kamere koji snimaju 24-bitne fotografije na fleš kartici od 10-20 MB sa PCMCIA interfejsom. Zatim se ova kartica ubacuje u slot na vašem laptopu i odgovarajući program vam omogućava da čitate slike. Nije li istina da bi algoritam bio asimetričan, bilo bi neugodno dugo čekati dok se uređaj "napuni" - komprimira sliku.
Još jedno ne baš prijatno svojstvo JPEG-a je da su često horizontalne i vertikalne pruge na ekranu apsolutno nevidljive i mogu se pojaviti samo kada se štampaju u obliku moiré uzorka. Javlja se kada se na horizontalne i okomite pruge slike primjenjuje kosi uzorak otiska. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u štampi, postavljajući visoke koeficijente. Međutim, kada se arhiviraju slike namijenjene ljudskom gledanju, ono je trenutno neizostavno.
Široka primjena JPEG-a dugo vrijeme sputan, možda, samo činjenicom da radi sa 24-bitnim slikama. Stoga, da bi se na konvencionalnom monitoru prikazala slika prihvatljivog kvaliteta u paleti od 256 boja, bilo je potrebno koristiti odgovarajuće algoritme i, stoga, određeno vrijeme. U aplikacijama koje ciljaju na izbirljive korisnike, kao što su igre, takva kašnjenja su neprihvatljiva. Osim toga, ako slike imate, recimo, u 8-bitnim GIF format konvertovan u 24-bitni JPEG, a zatim nazad u GIF za gledanje, tada će se gubitak kvaliteta desiti dva puta sa obe konverzije. Međutim, dobitak u veličini arhive je često tako velik (3-20 puta!), a gubitak u kvalitetu tako mali da je pohranjivanje slika u JPEG vrlo efikasno.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije fiksiran. Koristeći ovo, proizvođači kreiraju svoje, nekompatibilne formate, i stoga mogu promijeniti algoritam. Dakle, interne tabele algoritma koje preporučuje ISO su zamenjene njima sopstvenim. Osim toga, postoji mala zabuna prilikom postavljanja stepena gubitka. Na primjer, prilikom testiranja ispostavilo se da “odličan” kvalitet, “100%” i “10 bodova” daju značajno različite slike. U isto vrijeme, usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i varijante JPEG-a za specifične aplikacije.
Kako se ISO standard JPEG sve više koristi u razmjeni slika u kompjuterskim mrežama. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijalnim sistemima.
Karakteristike algoritma JPEG:
Klasa slike: 24-bitne slike ili slike u nijansama sive boje bez oštrih prelaza boja (fotografije).
simetrija: 1
karakteristike: U nekim slučajevima, algoritam stvara "halo" oko oštrih horizontalnih i vertikalnih rubova na slici (Gibbsov efekat). Osim toga, uz visok stepen kompresije, slika se raspada na blokove veličine 8x8 piksela.
Fraktalni algoritamIdeja o metodi
Fraktalno arhiviranje se zasniva na činjenici da sliku predstavljamo u kompaktnijem obliku – koristeći koeficijente sistema iteriranih funkcija (Iterated Function System – u daljem tekstu IFS). Prije nego što razmotrimo sam proces arhiviranja, pogledajmo kako IFS gradi sliku, tj. proces dekompresije.
Strogo govoreći, IFS je skup trodimenzionalnih afinih transformacija, u našem slučaju, pretvarajući jednu sliku u drugu. Tačke u trodimenzionalnom prostoru (x_coordinate, y_coordinate, svjetlina) su podvrgnute transformaciji.
Ovaj proces je najjasnije pokazao Barnsley u svojoj knjizi “Fractal Image Compression”. Tamo je uveden koncept fotokopirnog uređaja koji se sastoji od ekrana na kojem se prikazuje originalna slika i sistema sočiva koji projektuju sliku na drugi ekran:
- Objektivi mogu projektovati dio slike slobodne forme na bilo koje drugo mjesto na novoj slici.
- Područja, u kojem slike se projektuju ne seku.
- lens can promijenite svjetlinu i smanjite kontrast.
- lens can preokrenuti i rotirati vaš fragment slike.
- Objektiv trebalo bi u skali(smanjite) fragment vaše slike.
Postavljanjem sočiva i promjenom njihovih karakteristika možemo kontrolirati rezultirajuću sliku. Jedna iteracija rada Mašine sastoji se u tome što se od originalne slike uz pomoć projekcije gradi nova, nakon čega se nova uzima kao početna. Tvrdi se da ćemo u procesu iteracija dobiti sliku koja će prestati da se mijenja. To će ovisiti samo o lokaciji i karakteristikama sočiva, a neće ovisiti o originalnoj slici. Ova slika se zove " fiksna tačka" ili atraktor ovaj IFS. Odgovarajuća teorija garantuje da postoji tačno jedna fiksna tačka za svaki IFS.
Pošto je mapiranje sočiva kontraktivno, svako sočivo eksplicitno definira sebi slični područja na našoj slici. Zahvaljujući samosličnosti, dobijamo složenu strukturu slike pri bilo kom uvećanju. Dakle, intuitivno je jasno da sistem iteriranih funkcija definira fraktal(nestrogo - samosličan matematički objekat).
Najpoznatije su dvije slike dobijene uz pomoć IFS-a: “Sierpinski trougao” i “Barnsley paprat”. "Sierpinski trougao" je dat sa tri, a "Barnslijeva paprat" sa četiri afine transformacije (ili, u našoj terminologiji, "sočiva"). Svaka transformacija je kodirana u doslovno pročitanim bajtovima, dok slika izgrađena uz njihovu pomoć može zauzeti nekoliko megabajta.
Vježba: Označite 4 područja na slici koja bi se kombinirala kako bi pokrila cijelu sliku, a od kojih bi svaka bila slična cijeloj slici (ne zaboravite stabljiku paprati).
Iz navedenog postaje jasno kako arhivator radi i zašto je potrebno toliko vremena. U stvari, fraktalna kompresija je traženje samosličnih područja na slici i određivanje parametara afine transformacije za njih.
=>
U najgorem slučaju, ako se ne primeni algoritam optimizacije, biće potrebno nabrojati i uporediti sve moguće fragmente slike različitih veličina. Čak i za male slike, uzimajući u obzir diskretnost, dobićemo astronomski broj opcija koje treba sortirati. Štoviše, čak i oštro sužavanje klasa transformacije, na primjer, skaliranjem samo određeni broj puta, ne daje primjetan dobitak u vremenu. Osim toga, gubi se kvalitet slike. Velika većina istraživanja u području fraktalne kompresije sada je usmjerena na smanjenje vremena arhiviranja potrebnog za dobivanje slike visokog kvaliteta.
Definicija.
gdje a, b, c, d, e, f realni brojevi i zove se dvodimenzionalna afina transformacija.
Definicija. Transformacija, reprezentabilna u obliku
gdje su a, b, c, d, e, f, p, q, r, s, t, u realni brojevi i naziva se trodimenzionalna afina transformacija.
Definicija. Neka je transformacija u prostoru X. Tačka kao što se zove fiksna tačka(atraktor) transformacije.
Definicija. Za transformaciju u metričkom prostoru (X, d) se kaže da je kontraktivna ako postoji broj s: , takav da
komentar: Formalno, možemo koristiti bilo koje mapiranje kontrakcije za fraktalnu kompresiju, ali u stvarnosti se koriste samo trodimenzionalne afine transformacije sa prilično jakim ograničenjima na koeficijente.
Teorema. (O transformaciji kompresije)
Neka u kompletnom metričkom prostoru (X, d). Tada postoji tačno jedna fiksna tačka ove transformacije, a za bilo koju tačku niz 
konvergira na .
Općenitija formulacija ove teoreme garantuje konvergenciju.
Definicija. Slika je funkcija S definirana na jediničnom kvadratu i uzima vrijednosti od 0 do 1 ili
Neka se trodimenzionalna afina transformacija , zapiše kao
i definiran je na kompaktnom podskupu kartezijanskog kvadrata x. Tada će prevesti dio površine S na područje koje se nalazi sa smjenom (e,f) i rotaciju koju daje matrica
Međutim, ako tumačimo vrijednost S kako će se svjetlina odgovarajućih tačaka smanjivati str puta (transformacija mora biti kontraktivna) i promijenit će se u pomak q.
Definicija.
konacna populacija W ugovaranje trodimenzionalnih afinih transformacija definisanih na domenima tako da i 
, zove se sistem iteriranih funkcija ( IFS).
Sistem iteriranih funkcija je jedinstveno povezan sa fiksnom tačkom - slikom. Dakle, proces kompresije se sastoji u traženju koeficijenata sistema, a proces dekompresije se sastoji u iteraciji sistema dok se rezultujuća slika ne stabilizuje (fiksna tačka IFS). U praksi je dovoljno 7-16 iteracija. Regije će se nazivati rangiranje, i područja domena.
Izgradnja algoritma
Kao što je već postalo očigledno iz gore navedenog, glavni zadatak kompresije fraktalnim algoritmom je pronaći odgovarajuće afine transformacije. U najopćenitijem slučaju možemo prevesti područja slike bilo koje veličine i oblika, međutim, u ovom slučaju dobijamo astronomski broj opcija za razvrstavanje različitih fragmenata, koji se trenutno ne mogu obraditi čak ni na superkompjuteru.
IN trenažna verzija algoritma , navedeno u nastavku, uvedena su sljedeća ograničenja na području:
- Sva područja su kvadrati sa stranicama paralelnim sa stranicama slike. Ovo ograničenje je prilično ozbiljno. U stvari, mi ćemo aproksimirati cijelu mnogostrukost geometrijski oblici samo kvadrati.
- Prilikom pretvaranja područja domene u domen ranga, veličina se smanjuje tačno dva puta. Ovo uvelike pojednostavljuje i kompresor i dekompresor. zadatak skaliranja malih područja nije trivijalan.
- Svi blokovi domena su kvadrati i imaju fiksna veličina. Slika je podijeljena uniformnom mrežom na skup blokova domena.
- Područja domena su zauzeta „kroz tačku“ i u X i u Y, što odmah smanjuje pretragu za faktor 4.
- Prilikom pretvaranja domene u rang jedan, kocka se može rotirati samo na 0 0 , 90 0 , 180 0 ili 270 0. Također dozvoljeno odraz ogledala. Ukupan broj moguće transformacije (brojeći prazno) - 8.
- Skaliranje (kompresija) se vrši vertikalno (osvjetljenje). fiksni broj puta- na 0,75.
Ova ograničenja dozvoljavaju:
- Konstruirajte algoritam koji zahtijeva relativno mali broj operacija čak i na dovoljno velikim slikama.
- Veoma je kompaktan za predstavljanje podataka koji se upisuju u datoteku. Za svaku afinu transformaciju u IFS-u trebamo:
- dva broja za postavljanje pomaka bloka domene. Ako ograničimo ulazne slike na 512x512, tada će 8 bitova po broju biti dovoljno.
- tri bita za specificiranje transformacije simetrije prilikom pretvaranja bloka domene u blok ranga.
- 7-9 bita za postavljanje pomaka u svjetlini tokom prijevoda.
Na primjer, za datoteku u sivim tonovima od 256 boja od 512x512 piksela, sa veličinom bloka od 8 piksela, afine transformacije će biti 4096 (512/8x512/8). Svaki će zahtijevati 3,5 bajta. Stoga, ako je originalna datoteka zauzimala 262144 (512x512) bajtova (bez zaglavlja), tada bi datoteka sa koeficijentima zauzela 14336 bajtova. Koeficijent arhiviranja - 18 puta. Istovremeno, ne uzimamo u obzir da fajl sa koeficijentima takođe može imati redundantnost i biti arhiviran metodom arhiviranja bez gubitaka, kao što je LZW.
Negativni aspekti predloženih ograničenja:
- Budući da su sva područja kvadrati, nemoguće je koristiti sličnost objekata koji su po obliku daleko od kvadrata (koji su prilično česti na stvarnim slikama).
- Slično, nećemo moći koristiti sličnost objekata na slici, koeficijent sličnosti između kojih se jako razlikuje od 2.
- Algoritam neće moći koristiti sličnost objekata na slici, ugao između kojih nije višekratnik 90 0 .
Sam algoritam pakovanja se svodi na nabrajanje svih blokova domena i odabir za svaki odgovarajući blok ranga. Ispod je dijagram ovog algoritma.
za (sve blokove opsega) (
min_distance = Maksimalna udaljenost;
R ij= slika->CopyBlock(i,j);
za (svi blokovi domene) ( // Sa rotacijama i neg.
current=Trenutne koordinate transformacije;
D=slika->CopyBlock(trenutno);
trenutna_udaljenost = R ij.L2distance(D);
if(trenutna_udaljenost< min_distance) {
// Ako su najbolje kvote lošije:
min_distance = trenutna_distance;
najbolje = trenutno;
}
) //Sljedeći raspon
Save_Coefficients_to_file(najbolje);
) //Sljedeća domena
Kao što se vidi iz gornjeg algoritma, za svaki blok ranga provjeravamo ga sa svim mogućim blokovima domene (uključujući i one koji su prošli transformaciju simetrije), nalazimo varijantu sa najmanjom mjerom L 2 (najmanje standardno odstupanje) i sačuvajte koeficijente ove transformacije u datoteku. Koeficijenti su (1) koordinate pronađenog bloka, (2) broj od 0 do 7 koji karakterizira transformaciju simetrije (rotacija, refleksija bloka) i (3) pomak svjetline za ovaj par blokova. Pomak osvjetljenja se izračunava na sljedeći način:
,
gdje r ij- vrijednosti piksela rangirajućeg bloka ( R), ali d ij- vrijednosti piksela bloka domene ( D). U ovom slučaju, mjera se smatra kao:
.
Mi ne kalkulišemo kvadratni korijen od L 2 mjeri i ne dijeli sa n, budući da su podaci o transformaciji monotoni i neće nas spriječiti da pronađemo ekstrem, međutim, moći ćemo izvesti dvije manje operacije za svaki blok.
Izračunajmo broj operacija koje su nam potrebne za komprimiranje slike u sivim 256 boja 512x512 piksela sa veličinom bloka od 8 piksela:
Tako smo uspjeli smanjiti broj operacija algoritma kompresije na prilično izračunljive (iako za nekoliko sati) vrijednosti.
Dijagram algoritma dekompresije slike
Dekompresija algoritma fraktalne kompresije je izuzetno jednostavna. Potrebno je provesti nekoliko iteracija trodimenzionalnih afinskih transformacija čiji su koeficijenti dobiveni u fazi kompresije.
Apsolutno bilo koja slika (na primjer, apsolutno crna) može se uzeti kao početna, jer nam odgovarajući matematički aparat jamči konvergenciju niza slika dobivenih tijekom IFS iteracija na nepokretnu sliku (blizu originalnoj). Obično je za to dovoljno 16 iteracija.
Pročitajte koeficijente svih blokova iz datoteke;
Kreirajmo crna slika prava veličina;
Do (slika neće stati)(
Za(svaki raspon (R))(
D=image->CopyBlock(D_coord_for_R);
Za(svaki piksel( i,j) u bloku (
R ij = 0,75 D ij + o R;
) //Sljedeći piksel
) //Sljedeći blok
)//Do kraja
Pošto smo evidentirali koeficijente za blokove R ij(koji su, kao što smo naveli, u našem konkretnom slučaju kvadrati iste veličine) sukcesivno, ispada da sukcesivno popunjavamo sliku kvadratima particione mreže koristeći afinu transformaciju.
Kao što se može izračunati, broj operacija po pikselu slike u sivim tonovima tokom restauracije je neobično mali (N operacija “+”, 1 operacija “*”, gdje je N broj iteracija, tj. 7-16). Zbog toga je dekompresija slike za fraktalni algoritam brža od dekompresije, na primjer, za JPEG algoritam, u kojem ima 64 “+” i 64 “? ” (isključujući RLE korake i Huffmanovo kodiranje!). Istovremeno, za fraktalni algoritam, množenje se dešava racionalnim brojem, po jedan za svaki blok. To znači da možemo, prvo, koristiti cjelobrojnu racionalnu aritmetiku, koja je znatno brža od aritmetike s pomičnim zarezom. Drugo, množenje vektora brojem je jednostavnija i brža operacija, često ugrađena u arhitekturu procesora (SGI procesori, Intel MMX...), nego skalarni proizvod dva vektora, koji je neophodan u slučaju JPEG-a. Za sliku u punoj boji situacija se ne mijenja kvalitativno, jer oba algoritma koriste konverziju u drugi prostor boja.
Procjena gubitaka i načini njihovog regulisanja
At sažetak Pojednostavljena verzija algoritma propustila je mnoga važna pitanja. Na primjer, što ako algoritam ne može pronaći sličnu sliku ni za jedan fragment slike? Dovoljno očigledno rješenje je razbiti ovaj fragment na manje i pokušati ih potražiti. Istovremeno, jasno je da se ovaj postupak ne može ponavljati beskonačno, inače će broj potrebnih transformacija postati toliki da će algoritam prestati biti algoritam kompresije. Stoga dopuštamo gubitak u nekom dijelu slike.
Za algoritam fraktalne kompresije, kao i za druge algoritme kompresije sa gubicima, veoma su važni mehanizmi pomoću kojih će biti moguće kontrolisati stepen kompresije i stepen gubitka. Do danas je razvijen dovoljno veliki skup takvih metoda. Prvo, moguće je ograničiti broj afinskih transformacija osiguravajući da omjer kompresije nije niži od fiksne vrijednosti. Drugo, može se zahtijevati da se u situaciji u kojoj je razlika između fragmenta koji se obrađuje i njegove najbolje aproksimacije iznad određene granične vrijednosti, ovaj fragment nužno podijeli (za njega se nužno kreira nekoliko „leća“). Treće, moguće je zabraniti fragmentaciju fragmenata manjih od, recimo, četiri tačke. Promjenom graničnih vrijednosti i prioriteta ovih uvjeta, imat ćemo vrlo fleksibilnu kontrolu nad omjerom kompresije slike u rasponu od podudaranja bit po bit do bilo kojeg stupnja kompresije. Imajte na umu da će ova fleksibilnost biti mnogo veća od one kod najbližeg "konkurenta" - JPEG algoritma.
Karakteristike fraktalnog algoritma :
Omjeri kompresije: 2-2000 (korisnički definirano)
Klasa slike: 24-bitne slike ili slike u nijansama sive boje bez oštrih prelaza boja (fotografije). Poželjno je da područja većeg značaja (za percepciju) budu kontrastnija i oštrija, a područja manjeg značaja - niskog kontrasta i zamućena.
simetrija: 100-100000
karakteristike: Može slobodno skalirati sliku prilikom otkopčavanja, povećavajući je 2-4 puta bez pojave "efekta stepenica". Kako se nivo kompresije povećava, na ivicama blokova na slici pojavljuje se "blokirani" efekat.
Rekurzivni (talasni) algoritamEngleski naziv za rekurzivnu kompresiju je wavelet. Na ruski se prevodi kao kompresija talasa, i kao kompresija pomoću rafala. Ova vrsta arhiviranja poznata je dugo vremena i direktno proizilazi iz ideje korištenja koherentnosti regija. Algoritam je fokusiran na slike u boji i crno-bijele glatki prelazi. Idealno za slike poput x-zrake. Omjer kompresije je podešen i varira između 5-100. Kada pokušate postaviti veći koeficijent na oštrim granicama, posebno onima koje prolaze dijagonalno, pojavljuje se „efekat stepenica“ - stepenice različite svjetline veličine nekoliko piksela.
Ideja algoritma je da razliku pohranjujemo u datoteku - broj između prosječnih vrijednosti susjednih blokova na slici, koji obično uzima vrijednosti bliske 0.
Dakle, dva broja a 2i I a 2i +1 uvijek može biti predstavljen kao b 1 i=(a 2i +a 2i +1 )/2 i b 2 i=(a 2i -a 2i +1 )/2. Sličan niz a imogu se prevesti u parovima u niz b 1.2i.
Hajde da analiziramo konkretan primjer: Komprimirajmo niz vrijednosti svjetline od 8 piksela ( a i): (220, 211, 212, 218, 217, 214, 210, 202). Dobićemo sledeće sekvence b 1 i, And b 2 i: (215,5, 215, 215,5, 206) i (4,5, -3, 1,5, 4). Imajte na umu da vrijednosti b 2 idovoljno blizu 0. Ponovimo operaciju, uzimajući u obzir b 1 i kako a i. Ova akcija se izvodi kao rekurzivno, otuda i naziv algoritma. Dobijamo iz (215,5, 215, 215,5, 206): (215,25, 210,75) (0,25, 4,75). Rezultirajuće koeficijente, zaokružene na cijele brojeve i komprimirane, na primjer, koristeći Huffman algoritam sa fiksnim tablicama, možemo staviti u datoteku.
Imajte na umu da smo samo dva puta primijenili našu transformaciju na lanac. U stvarnosti, možemo sebi priuštiti primjenu talasne transformacije 4-6 puta. Štaviše, dodatna kompresija se može postići korištenjem tablica Hafmanovog algoritma neujednačenih koraka (tj. moramo sačuvati Huffman kod za najbližu vrijednost u tabeli). Ove tehnike vam omogućavaju da postignete primjetne omjere kompresije.
vježba: Vratili smo lanac (215, 211) (0, 5) (5, -3, 2, 4) iz datoteke (pogledajte primjer). Napravite niz od osam vrijednosti svjetline piksela koje će algoritam kompresije valova ponovo kreirati.
Algoritam za dvodimenzionalne podatke implementiran je na sličan način. Ako imamo kvadrat od 4 tačke sa svjetlinama a 2i, 2j,a 2 i +1 , 2 j,a 2i, 2j+1, And a 2 i +1 , 2 j +1, onda
| Inicijal | B1 | B2 | |
| slika | B3 | B4 |
Koristeći ove formule, za sliku veličine 512x512 piksela, nakon prve transformacije, dobićemo 4 matrice veličine 256x256 elemenata:
-- 
Prvi će, kao što možete pretpostaviti, pohraniti smanjenu kopiju slike. U drugom - prosječne razlike parova vrijednosti piksela duž horizontale. U trećem - prosječne razlike parova vrijednosti piksela duž vertikale. U četvrtom - prosječna razlika u vrijednostima piksela duž dijagonale. Po analogiji sa dvodimenzionalnim slučajem, možemo ponoviti našu transformaciju i dobiti 4 matrice veličine 128x128 umjesto prve matrice. Ponavljajući našu transformaciju po treći put, na kraju ćemo dobiti: 4 matrice 64x64, 3 matrice 128x128 i 3 matrice 256x256. U praksi, prilikom pisanja u datoteku, vrijednosti dobijene u posljednjem redu () se obično zanemaruju (odmah se dobiva povećanje od oko trećine veličine datoteke - 1- 1/4 - 1/16 - 1/64 ...).
Prednosti ovog algoritma uključuju činjenicu da vam vrlo lako omogućava da ostvarite mogućnost postepenog "razvoja" slike prilikom prijenosa slike preko mreže. Osim toga, budući da zapravo pohranjujemo malu kopiju na početku slike, lakše je prikazati "grubu" sliku po naslovu.
Za razliku od JPEG-a i fraktalnog algoritma, ova metoda ne radi s blokovima, na primjer, 8x8 piksela. Tačnije, radimo sa blokovima 2x2, 4x4, 8x8 itd. Međutim, zbog činjenice da koeficijente za ove blokove pohranjujemo nezavisno, vrlo lako možemo izbjeći cijepanje slike na „mozaične“ kvadrate.
Karakteristike talasnog algoritma:
Omjeri kompresije: 2-200 (korisnički definirano)
Klasa slike: Kao fraktal i JPEG.
simetrija: ~1.5
karakteristike: Osim toga, uz visok stepen kompresije, slika se raspada u zasebne blokove.
Zaključak
U zaključku, pogledajmo tabele koje sumiraju parametre različitih algoritama kompresije slike o kojima smo gore raspravljali.
| Algoritam | Karakteristike slike zbog kojih dolazi do kompresije |
| RLE | Uzastopne identične boje: 2 2 2 2 2 2 15 15 15 |
| LZW | Isti podnizovi: 2 3 15 40 2 3 15 40 |
| huffman | Različite frekvencije boja: 2 2 3 2 2 4 3 2 2 2 4 |
| CCITT-3 | prevlast bijele boje na slici, velike površine ispunjene jednom bojom |
| Rekurzivno | Glatki prijelazi boja i bez oštrih rubova |
| JPEG | Nema oštrih granica |
| fraktal | Sličnost između elemenata slike |
| Algoritam | K-you kompresija | Simetrija u vremenu | Za što orijentisan |
Gubici | Dimenzija |
| RLE | 32, 2, 0.5 | 1 | 3.4-bit | Ne | 1D |
| LZW | 1000, 4, 5/7 | 1.2-3 | 1-8 bit | Ne | 1D |
| huffman | 8, 1.5, 1 | 1-1.5 | 8 bit | Ne | 1D |
| CCITT-3 | 213(3), 5, 0.25 | ~1 | 1-bit | Ne | 1D |
| JBIG | 2-30 puta | ~1 | 1-bit | Ne | 2D |
| JPEG bez gubitaka | 2 puta | ~1 | 24-bitna siva | Ne | 2D |
| JPEG | 2-20 puta | ~1 | 24-bitna siva | Da | 2D |
| Rekurzivna kompresija | 2-200 puta | 1.5 | 24-bitna siva | Da | 2D |
| fraktal | 2-2000 puta | 1000-10000 | 24-bitna siva | Da | 2.5D |
- tutorial
UPD. Bio sam prisiljen ukloniti monospace formatiranje. Jednog lijepog dana, habraparser je prestao da opaža formatiranje unutra pre tags i kod. Sav tekst se pretvorio u nered. Administracija habra mi nije mogla pomoći. Sada neujednačen, ali barem čitljiv.
Da li ste ikada želeli da znate kako funkcioniše jpg fajl? Hajde sada da shvatimo! Zagrijte svoj omiljeni kompajler i heksadecimalni uređivač, dekodirajte ovo:
Posebno sam napravio manji crtež. Ovo je poznati, ali jako komprimirani Googleov favicon:
Odmah vas upozoravam da je opis pojednostavljen, a date informacije nisu potpune, ali tada će biti lako razumjeti specifikaciju.
Čak i bez znanja kako se kodiranje odvija, već možemo izdvojiti nešto iz datoteke.
- startni marker. Uvijek je na početku svih jpg datoteka.
Slijede bajtovi.
. Ovo je marker koji označava početak odjeljka komentara. Sljedeća 2 bajta
- dužina sekcije (uključujući ova 2 bajta). Dakle u sljedeća dva
- sam komentar. To su kodovi znakova ":" i ")", tj. običan smajlić. Možete ga vidjeti na prvom redu desne strane hex editora.
Malo teorije
Vrlo kratko korak po korak:
Razmislimo o redoslijedu kojim se ovi podaci mogu kodirati. Pretpostavimo da je u početku Y kanal kodiran za cijelu sliku, zatim Cb, a zatim Cr. Svi se sjećaju učitavanja slika na dial-up. Da su kodirani na ovaj način, morali bismo čekati da se učita cijela slika prije nego što se pojavi na ekranu. Također će biti neugodno ako se izgubi kraj datoteke. Vjerovatno postoje i drugi dobri razlozi. Stoga su kodirani podaci raspoređeni naizmjenično, u malim dijelovima. 
Da vas podsjetim da je svaki blok Y ij, Cb ij, Cr ij matrica DCT koeficijenata kodiranih Huffmanovim kodovima. Oni se nalaze u datoteci sljedećim redoslijedom: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Čitanje fajla
Nakon što izdvojimo komentar, biće lako razumjeti da:- Fajl je podijeljen na sektore kojima prethode markeri.
- Tokeni su dugi 2 bajta, s prvim bajtom.
- Gotovo svi sektori pohranjuju svoju dužinu u sljedeća 2 bajta nakon markera.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01FF
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 00AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9
Marker: DQT - tabela kvantizacije.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
Zaglavlje odjeljka je uvijek 3 bajta. U našem slučaju, ovo je . Zaglavlje se sastoji od:
Dužina: 0x43 = 67 bajtova
Dužina vrijednosti u tabeli: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tabele: 0
Preostala 64 bajta treba da popune tabelu 8x8.
Pažljivije pogledajte redoslijed popunjavanja vrijednosti tablice. Ovaj redosled se zove cik-cak redosled: 
Marker : SOF0 - Osnovni DCT
Ovaj marker se zove SOF0, što znači da je slika kodirana osnovnom metodom. Vrlo je česta. Ali na Internetu, progresivna metoda koja vam je poznata nije ništa manje popularna, kada se slika prvi put učitava niske rezolucije, a zatim normalna slika. Ovo vam omogućava da shvatite šta je tamo prikazano, bez čekanja puno opterećenje. Specifikacija definira još nekoliko, čini mi se, ne baš uobičajenih metoda.FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01
Dužina: 17 bajtova.
Preciznost: 8 bita U osnovnoj metodi, to je uvijek 8. Koliko ja razumijem, ovo je dubina bita vrijednosti kanala.
Visina slike: 0x10 = 16
Širina uzorka: 0x10 = 16
Broj komponenti: 3. Najčešće je to Y, Cb, Cr.
1. komponenta:
ID: 1
Horizontalno stanjivanje (H 1): 2
[_2]
Vertikalno stanjivanje (V 1): 2
ID tablice kvantizacije: 0
2. komponenta:
ID: 2
Horizontalno stanjivanje (H 2): 1
[_1]
Vertikalno stanjivanje (V 2): 1
3. komponenta:
ID: 3
Horizontalno stanjivanje (H 3): 1
[_1]
Vertikalno stanjivanje (V 3): 1
Identifikator tabele kvantizacije: 1
Sada pogledajte kako odrediti koliko je istanjena slika. Nalazimo H max = 2 i V max = 2. Kanal i će biti desetkovan za H max /H i puta horizontalno i V max /V i puta vertikalno.
Marker : DHT (Huffman grafikon)
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
dužina: 21 bajt.
klasa: 0 (0 - tabela koeficijenta jednosmerne struje, 1 - tabela koeficijenta naizmenične struje).
[_0]
id tabele: 0
Duljina Huffman koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Broj kodova znači broj kodova te dužine. Imajte na umu da odjeljak pohranjuje samo dužine kodova, a ne same kodove. Šifre moramo pronaći sami. Dakle, imamo jedan kod dužine 1 i jedan dužine 2. Ukupno ima 2 koda, u ovoj tabeli više nema kodova.
Svaki kod ima pridruženu vrijednost i oni su navedeni u datoteci. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. koda.
- vrijednost 2. koda.
Izgradnja stabla Huffmanovih kodova
Moramo da napravimo binarno stablo iz tabele koju smo dobili u DHT sekciji. I već po ovom stablu prepoznaćemo svaki kod. Vrijednosti se dodaju redoslijedom kojim su navedene u tabeli. Algoritam je jednostavan: bez obzira gdje se nalazimo, uvijek pokušavamo dodati vrijednost lijevoj grani. A ako je zauzeta, onda desno. A ako tamo nema mesta, onda se vraćamo na nivo iznad i pokušavamo odatle. Morate se zaustaviti na nivou koji je jednak dužini koda. Lijeva grana odgovara vrijednosti 0, desna - 1.komentar:
Nema potrebe da svaki put počinjete od vrha. Dodata vrijednost - povratak na nivo iznad. Postoji li prava grana? Ako jeste, idite ponovo gore. Ako ne, kreirajte desnu granu i idite tamo. Zatim, odatle, počnite tražiti da dodate sljedeću vrijednost.
Stabla za sve tabele u ovom primjeru: 
UPD (hvala): Čvorovi prvog stabla (DC, id =0) moraju imati vrijednosti 0x03 i 0x02
U kružićima - vrijednosti kodova, ispod kružića - sami kodovi (objasnit ću da smo ih dobili idući od vrha do svakog čvora). Sa takvim kodovima (ove i drugih tabela) je kodiran sam sadržaj slike.
Marker : SOS (početak skeniranja)
Bajt u tokenu znači "DA! Konačno, prešli smo direktno na raščlanjivanje dijela kodirane slike! Međutim, dio se simbolično zove SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Dužina zaglavlja (ne cijelog odjeljka): 12 bajtova.
Broj komponenti skeniranja. Imamo 3, po jedan za Y, Cb, Cr.
1. komponenta:
Broj komponente slike: 1 (Y)
ID Huffmanove tablice za DC koeficijente: 0
[_0]
ID Huffmanove tablice za AC koeficijente: 0
2. komponenta:
Broj komponente slike: 2 (Cb)
[_1]
3. komponenta:
Broj komponente slike: 3 (Cr)
ID Huffmanove tablice za DC koeficijente: 1
[_1]
ID Huffmanove tablice za AC koeficijente: 1
Ove komponente se ciklički izmjenjuju.
Ovdje se završava dio zaglavlja, odavde do kraja (markerom) kodiranih podataka.
0
Pronalaženje DC koeficijenta.
1.
Čitanje niza bitova (ako sretnemo 2 bajta, onda ovo nije marker, već samo bajt). Nakon svakog bita krećemo se duž Huffmanovog stabla (sa odgovarajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako smo na konačnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, tada je koeficijent 0, upišite ga u tabelu i nastavite sa čitanjem ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je dužina koeficijenta u bitovima. To jest, čitamo sljedeća 2 bita, ovo će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka vrijednosti u binarno predstavljanje- 1, zatim ostavite kako jeste: DC_coef = vrijednost. U suprotnom, pretvorite: DC_coef = vrijednost-2 vrijednost dužine +1. Koeficijent upisujemo u tablicu na početku cik-cak - gornjem lijevom uglu.
Pronalaženje AC-koeficijenata.
1.
Slično kao kod tačke 1, pronalaženje DC koeficijenta. Nastavljamo da čitamo sekvencu:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednako 0, to znači da preostale vrijednosti matrice moraju biti popunjene nulama. Zatim se sljedeća matrica kodira. Prvih nekoliko koji su pročitali do ove tačke i pisali mi o tome u lično, dobiće plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - to je koliko nula treba da dodamo matrici. Ovo su 3 nula koeficijenta.
Drugi grickanje: 0x1 - dužina koeficijenta u bitovima. Pročitajte sljedeći dio.
10
10
1110
1
110011101100001111100100
3. Slično tački 3 pronalaženja DC-koeficijenta.
Kao što ste već shvatili, morate čitati AC koeficijente dok ne naiđete na nula vrijednost koda, ili dok se matrica ne popuni.
U našem slučaju dobić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 ove narudžbe je jednostavan - jer šta više vrijednosti v i u, manje je značajan koeficijent S vu u diskretnoj kosinusnoj transformaciji. Stoga, pri visokim omjerima kompresije, beznačajni koeficijenti se postavljaju na nulu, čime se smanjuje veličina datoteke.
[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Oh, zaboravio sam reći da kodirani DC koeficijenti nisu sami DC koeficijenti, već njihove razlike između koeficijenata prethodne tabele (istog kanala)! Morate popraviti matrice:
DC za 2.: 2 + (-4) = -2
DC za 3.: -2 + 5 = 3
DC za 4.: 3 + (-4) = -1
[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………
Sada naruči. Ovo pravilo važi do kraja fajla.
… i po matrici za Cb i Cr:
[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Pošto postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknutim.
Računarstvo
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član sa elementima matrice kvantizacije. Ostaje odabrati pravi. Prvo smo skenirali prvu komponentu, njena komponenta slike = 1. Komponenta slike sa ovim ID-om koristi matricu kvantizacije od 0 (imamo je prvu od dvije). Dakle, nakon množenja:
[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Slično, dobijamo još 3 Y-kanalne matrice...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
… i po matrici za Cb i Cr.
[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
Inverzna diskretna kosinusna transformacija
Formula ne bi trebala biti teška*. S vu je naša rezultujuća matrica koeficijenata. u - stupac, v - red. s yx - direktne vrijednosti kanala.
* Uopšteno govoreći, ovo nije sasvim tačno. Kada sam uspio dekodirati i prikazati crtež veličine 16x16 na ekranu, napravio sam sliku veličine 600x600 (usput rečeno, ovo je bila naslovnica mog omiljenog albuma Mind.In.A.Box - Lost Alone). Nije uspjelo odmah - pojavile su se razne greške. Uskoro sam mogao da se divim pravilno učitanoj slici. Jedino razočaranje je brzina preuzimanja. Još se sjećam da je trebalo 7 sekundi. Ali to nije iznenađujuće, ako nepromišljeno koristite gornju formulu, onda da biste izračunali jedan kanal od jednog piksela, morate pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - skoro hiljadu teških operacija za samo jedan kanal od jednog piksela! Srećom, ovdje ima mjesta za optimizaciju (nakon mnogo eksperimentiranja, smanjio sam vrijeme učitavanja na granicu tačnosti tajmera od 15ms, a nakon toga promijenio sliku u fotografiju 25 puta veću. Možda ću o tome pisati u posebnom članku ).
Napisat ću rezultat izračunavanja samo prve matrice Y kanala (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 druga 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, idemo jesti!
- Da ne ulazim uopste, o cemu pricas.
- Kada se dobiju YCbCr vrijednosti boja, ostaje da se konvertuje u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij), Y ij, Cb ij, Cr ij - naše primljene matrice.
- 4 Y matrice, i po jedna Cb i Cr, pošto smo razrijedili kanale i 4 Y piksela odgovaraju po 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
Nemojte zaboraviti dodati po 128. Ako vrijednosti idu izvan intervala, tada dodijelite granične vrijednosti. Formula je jednostavna, ali također troši djelić vremena procesora.
Evo rezultujućih tabela za R, G, B kanale za gornji lijevi kvadrat 8x8 našeg primjera:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
