Algoritam je razvila Joint Photographic Expert Group posebno za komprimiranje 24-bitnih slika i slika u sivim tonovima 1991. godine. Ovaj algoritam ne komprimira dvorazinske slike jako 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 ovom metodom komprimira 10 ili 20 puta.
Algoritam se temelji na DCT primijenjenoj na matricu blokova slika koji se ne preklapaju, veličine 8x8 piksela. DCT razlaže te 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 kvalitete restauracije.
Razmotrimo rad algoritma detaljnije. Pretpostavimo da komprimirate 24-bitnu sliku u punoj boji. U ovom slučaju dobivamo sljedeć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 dobiva množenjem inverzna matrica na vektor koji je u biti YUV prostor:
.
Korak 2 Izvornu sliku podijelimo na matrice 8x8. Formiramo tri DCT radne matrice od svake - 8 bitova 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 uzimaju se kroz točku u recima i stupcima.
Korak 3 Primjena DCT-a na slikovne blokove 8x8 piksela. Formalno, izravni DCT za blok 8x8 može se napisati kao
gdje 
. Budući da je DCT "srce" JPEG algoritma, poželjno ga je u praksi izračunati što brže. Jednostavan pristup ubrzavanju izračuna je unaprijed izračunati kosinusne funkcije i tabelarizirati rezultate izračuna. Štoviše, s obzirom na ortogonalnost kosinusnih funkcija s 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, ali 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 zbrajanja, što je znatno manje od izravnih izračuna korištenjem gornje formule. Na primjer, za pretvaranje slike veličine 512x512 piksela potrebne su 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, da biste transformirali jedan blok 8x8, morat ćete napraviti 54 množenja, 468 zbrajanja i pomaka bitova.
Kao rezultat DCT-a dobivamo matricu u kojoj su koeficijenti u lijevoj strani gornji kut odgovaraju niskofrekventnoj komponenti slike, au donjem desnom dijelu - visokofrekventnoj.
4. korak Kvantizacija. U ovom se koraku neke informacije odbacuju. Ovdje se svaki broj iz matrice dijeli posebnim brojem iz "tablice kvantizacije", 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 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 odabrati 64 koeficijenta, pa JPEG standard koristi dva pristupa za kvantizacijske matrice. Prvi je da JPEG standard uključuje dvije preporučene tablice kvantizacije: jednu za lumu i jednu za krominaciju. Ove tablice su prikazane u nastavku. Drugi pristup je sintetizirati (izračunati u hodu) tablicu kvantizacije ovisno o jednom parametru, koji je odredio korisnik. Sama tablica je izgrađena prema formuli
U koraku kvantizacije kontrolira se omjer kompresije i dolazi do najvećeg gubitka. Jasno je da ćemo postavljanjem tablica kvantizacije s velikim koeficijentima dobiti više nula i, posljedično, veći omjer kompresije.
Specifični učinci algoritma također su povezani s 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 očitovati u takozvanom "Gibbsovom efektu", kada se oko kontura s oštrim prijelazom boja formira valoviti "nimbus".
Korak 5 Prevodimo matricu 8x8 u vektor od 64 elementa koristeći "cik-cak" skeniranje (slika 2).
Riža. 2. Cik-cak skeniranje
Kao rezultat toga, na početku vektora, u pravilu, bit će upisani koeficijenti različiti od nule, a na kraju će se formirati lanci nula.
Korak 6 Vektor transformiramo modificiranim RLE algoritmom, na čijem izlazu dobivamo parove tipa (skip, broj), gdje je "skip" brojač preskočenih nula, a "broj" je vrijednost koja se mora unijeti sljedeću ćeliju. 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 biti jednak prosječnoj svjetlini bloka 8x8 i naziva se DC koeficijent. Slično za sve slikovne blokove. Ova okolnost sugerira da se DC koeficijenti mogu učinkovito komprimirati ako se ne pohranjuju njihove apsolutne vrijednosti, već relativne u obliku razlike između DC koeficijenta trenutnog bloka i DC koeficijenta prethodnog bloka i prvog bloka. koeficijent se pohranjuje takav kakav jest. U ovom slučaju, poredak istosmjernih koeficijenata može se izvesti, na primjer, na sljedeći način (slika 3). Preostali koeficijenti, koji se nazivaju AC koeficijenti, ostaju nepromijenjeni.
Korak 7 Dobivene parove skupljamo pomoću neuniformnih Huffmanovih kodova s fiksnom tablicom. Štoviše, za istosmjerne i izmjenične koeficijente koriste se različiti kodovi, t.j. različite tablice s Huffmanovim kodovima.
Riža. 3. Shema uređenja istosmjernih koeficijenata
Riža. 4. Blok dijagram JPEG algoritma
Proces rekonstrukcije slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućuje komprimiranje slika 10-15 puta bez vidljivog gubitka vida.
Razvoj ovog standarda bio je vođen činjenicom da ovaj algoritam trebao je komprimirati slike prilično brzo - ne više od minute na prosječnu sliku. 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 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 to, proizvođači stvaraju vlastite, nekompatibilne formate, te stoga mogu promijeniti algoritam. Dakle, interne tablice algoritma koje preporučuje ISO zamjenjuju se svojim vlastitim. Postoje i varijante JPEG-a za određene aplikacije.
JPEG algoritam je razvijen posebno za kompresiju slike od strane Joint Photographic Expert Group (JPEG) i temelji se na DCT-u.
DCT razlaže sliku u skup koeficijenata, od kojih neki mogu biti jednaki nuli zbog nekorištenja nekih DCT funkcija. Već koristim ova činjenica može se postići određena kompresija podataka. Ipak, najveći učinak postiže se uklanjanjem nekih beznačajnih koeficijenata (izjednačavanjem s nulom).
Obično izvana matrica ima jasno vidljivu značajku. Brojčane vrijednosti elemenata matrice brzo se smanjuju od gornjeg lijevog kuta 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 mogu se eliminirati. 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 danom fragmentu slike. Upravo u fazi kvantizacije dolazi do gubitka dijela informacija i, posljedično, gubitka kvalitete.
Kvantizacija se obično vrši na temelju 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 kvalitete.
Odabirom parametra q možete kontrolirati vrijednosti djelitelja i podesiti omjer kompresije. Na primjer, ako je q = 2, dobivate 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,
Učinak smanjenja vrijednosti od gore lijevo prema donjem desnom će biti još izraženiji.
Za ekonomičnu notaciju potrebno je promijeniti redoslijed prelaska dobivenih vrijednosti na način da nizovi nultih elemenata budu što duži. Jedan od mogući načini promjena redoslijeda obilaženja je cik-cak metoda (slika 3.7).
Slika 3.7. Transformacija dvodimenzionalne matrice u jednodimenzionalni niz metodom "cik-cak".
Kao što se vidi iz slike, dvodimenzionalna matrica formata 8 x 8 elemenata pretvara se u jednodimenzionalni niz duljine 64 elementa. Glavno svojstvo takvog niza bit će mjesto 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 ilustrirano na sl. 3.8.
Slika 3.8. Redoslijed operacija u implementaciji JPEG algoritma.
1. Ako je potrebno, slika se pretvara u YUV format.
2. Razlika u boji U i V signali uzorkovani su prema formatu 4:2:0. Dijeljenje slike na fragmente od 8 x 8 elemenata. Nadalje, obrada signala svjetline i krominacije može se izvoditi neovisno i paralelno.
3. Diskretna kosinusna transformacija se izvodi na svim blokovima od 8 x 8 elemenata.
4. Kvantizacija prema odabranom parametru kvalitete.
5. Skeniranje "cik-cak" kako bi se dobio jednodimenzionalni slijed od 64 elementa.
6. RLE algoritam primijenjen na jednodimenzionalni niz.
7. Huffmanov algoritam se primjenjuje na sekvencu već komprimiranu s RLE.
8. P.p. 3 - 7 se izvode za sve blokove u formatu 8 x 8 elemenata i za sve ravnine boja.
Ključne značajke JPEG metoda su kako slijedi:
1. Visok omjer kompresije, posebno za slike koje se smatraju dobrom ili izvrsnom kvalitetom.
2. Veliki broj parametara koji sofisticiranom korisniku omogućuju eksperimentiranje s postavkama metode i postizanje potrebne ravnoteže kompresije/kvaliteta.
3. Dobri rezultati za sve vrste kontinuiranih tonskih slika, bez obzira na njihovu razlučivost, prostor boja, veličinu piksela ili druga svojstva.
4. Prilično sofisticirana metoda kompresije, ali ne previše komplicirana, koja vam omogućuje stvaranje odgovarajućih uređaja i pisanje programa za implementaciju metode za računala većine platformi, kao i za hardver.
5. Mogućnost korištenja kompresije bez gubitka informacija pri ne baš visokom omjeru kompresije.
Da biste učinkovito komprimirali podatke, prvo morate procijeniti prirodu svoje slike. JPEG komprimira slikovne podatke na temelju onoga što ljudsko oko vidi. Stoga, kako bih vam pomogao razumjeti kako i što radi JPEG, želio bih vam dati Generalna ideja na ljudsku vizualnu 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-u je odabir odgovarajućeg načina predstavljanja boja. Boje su obično navedene u 3D koordinatnom sustavu. Sustav dobro poznat većini programera opisuje boju kao kombinaciju crvene, zelene i plave (RGB). Nažalost, u smislu sposobnosti kompresije, to nije Najbolji način opisi boja. Problem je u tome što su sve tri komponente – crvena, zelena i plava – ekvivalentne. Međutim, prijelaz na drugi sustav prikazivanja boja omogućuje vam 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 razinu "čiste" boje. Nezasićene boje često se neformalno nazivaju "prljavim" (sivkastim). Nijansa je ono što percipiramo kao boju objekta, kao što je crvena ili sivkasto zelena. Ovdje je važno napomenuti nevjerojatna činjenica: ljudski vid je osjetljiviji na promjene svjetla, a ne boje same po sebi!
Različite implementacije algoritma kompresije JPEG koriste različite sustavi boja. YCbCr sustav prikazivanja boja koji koristi JFIF format na mnogo je načina sličan shemi razvijenoj prije mnogo godina za televiziju u boji.
stanjivanje
Glavni razlog za pretvorbu iz jednog modela boja u drugi je identificiranje informacija koje su manje relevantne za gledanje na slici. JPEG smanjuje količinu informacija o boji. Dok se komponenta svjetline prenosi u punoj razlučivosti, komponente kroma koriste polovicu 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 a informacije o boji se prenose zasebno. Štoviše, informacije o boji prenose se 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 sivim tonovima. Pogledate li detaljnu sliku iz daljine, možete razaznati 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. Kako bi oponašao ovaj efekt, 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 vrlo je važna informacija o području slike. Vaše oko je manje osjetljivo na brzinu promjene boje, pa to nije toliko važno. Pretvaranje informacija o boji Na sličan način, ističemo informacije koje se mogu donirati.
Vjeruje se da su gubici uzrokovani ovom fazom. Ako kodirate sliku koristeći DCT, a zatim je vratite pomoću inverzne DCT funkcije, nećete dobiti potpuno isti skup bitova. Međutim, ova pogreška je pogreška zaokruživanja. Javlja se pri izvođenju aritmetičkih operacija i obično nije jako velik. Stoga radije razmišljam o DCT fazi kao o operaciji "uglavnom bez gubitaka".
Za velike slike izračun DCT-a i inverznog DCT-a je vrlo dugotrajan proces. Kako bi smanjio vrijeme računanja, JPEG dijeli sliku u mozaik od osam po osam piksela. Svaki od mozaika se obrađuje zasebno, što značajno smanjuje vrijeme izračuna potrebno za DCT. Problem koji se javlja s ovim pristupom je taj što se nakon kvantizacije (o čemu će biti riječi u sljedećem odjeljku) granice ovih kvadrata možda neće poklapati i stoga postaju vidljive pri određivanju niska vrijednost parametar kvalitete.
Kvantizacija
JPEG programere prvenstveno su zanimale slike fotografske kvalitete (fotografske, kontinuirani ton). U pravilu, ove polutonske slike karakteriziraju meki prijelazi iz jedne boje u drugu. Za takve slike, niskofrekventna (sporo mijenja) DCT komponenta je važnija od visokofrekventne (brzo mijenjajuće) komponente.
Pojam kvantizacija jednostavno znači "zaokruživanje". jpeg neke odbacuje grafičke informacije zaokruživanjem svakog člana DCT-a različitim težinama na temelju različitih čimbenika. Visokofrekventna komponenta je zaokružena više od niskofrekventne komponente. Na primjer, niskofrekventna komponenta, koja pohranjuje prosječnu vrijednost svjetline, može se zaokružiti na višekratnik od tri, dok se visokofrekventna komponenta može zaokružiti na višestruki od sto!
Operacija kvantizacije objašnjava zašto kompresija JPEG-a, u slučaju jasnih kontura, dovodi do stvaranja "tremljivih" linija. Konture su određene visokofrekventnom (brzo mijenjanom) prostornom komponentom. (Na prvi pogled može se činiti da biste trebali dobiti mutan obris, ali zapamtite da C u DCT označava kosinus.)
Tipično, ravnine boja su kvantizirane mnogo grublje od ravni luma. Ovdje pravi izbor Model boja pomaže identificirati informacije koje se mogu odbaciti.
Kompresija
Do sada, s izuzetkom slučaja kada je učestalost uzorkovanja dva kanali u boji, nije došlo do kompresije. Svi gore navedeni koraci - transformacija modela boja, DCT i kvantizacija - ostavili su veličinu podataka nepromijenjenom. Konačno, dolazimo do posljednjeg koraka, tijekom kojeg će standardna tehnika kompresije bez gubitaka zapravo smanjiti veličinu podataka.
Podaci razvrstani u prethodnim koracima mogu se komprimirati učinkovitije od sirovog materijala koji su RGB grafički podaci. Štoviše, niti jedan od poduzetih koraka nije bio suvišan, svaka promjena podataka bila je usmjerena na učinkovitije sažimanje konačne verzije.
Promjena modela boja omogućila je razrjeđivanje informacija o kanalu, a zatim ih snažnije kvantizirati.
DCT je omogućio izolaciju visokofrekventne prostorne komponente. Visokofrekventna komponenta obično ima male vrijednosti, što rezultira nerazmjernom količinom malih vrijednosti u izlazu DCT koraka, olakšavajući proces kompresije.
Tijekom 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 nudi dva drugačija metoda kompresiju bez gubitaka koja se može koristiti na posljednji korak. Huffmanova kompresija je dugo poznati nepatentirani algoritam koji se lako programira. Za razliku od njega, više novi algoritam aritmetičko kodiranje predmet je brojnih patenata. (Stoga nije iznenađujuće da mnogi programi za kompresiju JPEG podržavaju samo Huffmanovu kompresiju.)
Prilikom dekodiranja JPEG slike svi ti koraci moraju se poduzeti obrnuti redoslijed. Tok podataka se prvo dekomprimira, 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 napravljeno ispravno, gubitak informacija neće uzrokovati vidljivu degradaciju slike.
Problemi s algoritmima arhiviranja s gubitkomKonvencionalni algoritmi prvi su korišteni za arhiviranje slika. One koje su korištene i koje se koriste u backup sustavima, pri izradi distribucija itd. Ovi algoritmi su arhivirali informacije nepromijenjene. Međutim, glavni trend u posljednje vrijeme bila je uporaba 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čitu redundantnost. To je dovelo do stvaranja nove vrste algoritama - kompresije s gubitkom informacija. U pravilu se u njima može postaviti omjer arhiviranja i, posljedično, stupanj gubitka kvalitete. U tom se slučaju postiže kompromis između veličine i kvalitete slika.
Jedan od ozbiljnih problema računalne grafike je to što još nije pronađen adekvatan kriterij za procjenu gubitka kvalitete slike. I stalno se gubi – pri digitalizaciji, pri pretvorbi u ograničenu paletu boja, pri pretvorbi u drugi sustav prikaza boja za ispis i, što je za nas posebno važno, kod arhiviranja s 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). Istodobno, slike sa "snijegom" - oštrom promjenom boje pojedinačnih točaka, slabim prugama ili "moiréom" bit će prepoznate kao "gotovo nepromijenjene" (Objasnite zašto?). Ostali kriteriji također imaju svoje nedostatke.
Uzmimo u obzir, na primjer, maksimalno odstupanje:
Ova mjera, kao što možete pretpostaviti, izuzetno je osjetljiva na otkucaje pojedinih piksela. Oni. na cijeloj slici može se bitno promijeniti samo vrijednost jednog piksela (što je za 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 omjera signal-šum (peak-to-peak signal-to-noise ratio – PSNR).
Ova mjera je, zapravo, slična standardnoj devijaciji, ali je nešto prikladnija za korištenje zbog logaritamske ljestvice ljestvice. Ima iste nedostatke kao i standardna devijacija.
Gubitak kvalitete slike najbolje procjenjuje naše oči. Arhiviranje se smatra izvrsnim, u kojem je nemoguće okom razlučiti originalne i raspakirane slike. Dobro - kada možete reći koja je slika arhivirana, možete usporediti samo dvije susjedne slike. S daljnjim povećanjem omjera kompresije, u pravilu, nuspojave karakteristične za ovaj algoritam postaju vidljive. U praksi, čak i uz izvrsnu kvalitetu zadržavanja, slike se mogu redovito mijenjati. Stoga se algoritmi arhiviranja s gubitkom ne preporučuju za komprimiranje slika koje će kasnije biti ili ispisane s visokom kvalitetom ili obrađene programima za prepoznavanje slika. Neugodni efekti s takvim slikama, 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čki de facto standard za slike u punoj boji. Algoritam radi s 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 (vidi formule u nastavku), samo prvi koeficijenti pokazuju se značajnim. Dakle, kompresija u JPEG-u se provodi zahvaljujući glatkoći promjena boja na slici.
Algoritam je razvila skupina fotografskih stručnjaka posebno za komprimiranje 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 temelji na diskretnoj kosinusnoj transformaciji (u daljnjem tekstu DCT) primijenjenoj na matricu slike kako bi se dobila neka nova matrica koeficijenata. Za dobivanje izvorne slike primjenjuje se inverzna transformacija.
DCT razlaže sliku na amplitude određenih frekvencija. Tako pri transformaciji dobivamo 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 zamjetnog gubitka kvalitete 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 komprimiramo 24-bitnu sliku.
Korak 1.
Prevodimo sliku sa prostor boja RGB, s komponentama odgovornim za crvenu (crvenu), zelenu (zelena) i plavu (plavu) komponente boje točke, u prostor boja YCrCb (ponekad nazvan YUV).
U njemu je Y komponenta svjetline, a Cr, Cb su komponente odgovorne za boju (kromatska crvena i kromatsko 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, sukladno tome, visokim omjerima kompresije. Slična se transformacija 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 s inverznom matricom.
Korak 2
Izvornu sliku podijelimo na matrice 8x8. Formiramo tri DCT radne matrice od svake - 8 bitova 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 upisuju kroz redak i kroz stupac. Oni. iz originalne 16x16 matrice dobiva se samo jedna radna DCT matrica. U ovom slučaju, kao što je lako vidjeti, gubimo 3/4 korisna informacija o komponentama boje slike i odmah dobivamo dvostruku kompresiju. To možemo učiniti radom u prostoru YCrCb. Kao što je praksa pokazala, to ne utječe puno na rezultirajuću RGB sliku.
Korak 3
Na svaku radnu matricu primjenjujemo DCT. U ovom slučaju dobivamo matricu u kojoj koeficijenti u gornjem lijevom kutu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj komponenti.
U pojednostavljenom obliku, ova se transformacija može predstaviti na sljedeći način:
4. korak
Radimo kvantizaciju. U principu, ovo je jednostavno podjela radne matrice element po element matrice kvantizacije. Za svaku komponentu (Y, U i V), u općem slučaju specificira se vlastita kvantizatorska matrica q (u daljnjem tekstu MC).
U ovom koraku kontrolira se omjer kompresije i dolazi do najvećeg gubitka. Jasno je da ćemo postavljanjem MC s velikim koeficijentima dobiti više nula i, posljedično, veći omjer kompresije.
Specifični učinci algoritma također su povezani s kvantizacijom. Pri visokim vrijednostima gama koeficijenta, gubici na niskim frekvencijama mogu biti toliki da će se slika raspasti na kvadrate 8x8. Gubici u visokim frekvencijama mogu se očitovati u takozvanom "Gibbsovom efektu", kada se oko kontura s oštrim prijelazom boja formira svojevrsni "nimbus".
Korak 5.
Prevodimo matricu 8x8 u vektor od 64 elementa koristeći “cik-cak” skeniranje, tj. uzeti elemente s indeksima (0,0), (0,1), (1,0), (2,0)...
Tako na početku vektora dobivamo koeficijente matrice koji odgovaraju niske frekvencije, a na kraju - visoko.
Korak 6
Vektor konvolviramo pomoću algoritma grupnog kodiranja. U ovom slučaju dobivamo parove tipa (skip, broj), gdje je "skip" brojač preskočenih nula, a "broj" je vrijednost koja se mora staviti u sljedeć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 preklopimo Huffmanovim kodiranjem s fiksnom tablicom.
Proces rekonstrukcije slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućuje komprimiranje nekih slika 10-15 puta bez ozbiljnih gubitaka.
Cjevovod operacija koji se koristi u JPEG algoritmu.
značajan pozitivni aspekti algoritam je da:
- Postavlja omjer kompresije.
- slobodan dan slika u boji može imati 24 bita po točki.
- Povećanjem omjera kompresije slika se dijeli na zasebne kvadrate (8x8). To je zbog činjenice da na niskim frekvencijama tijekom kvantizacije dolazi do velikih gubitaka i postaje nemoguće vratiti izvorne podatke.
- Pojavljuje se Gibbsov efekt - aureole duž granica oštrih prijelaza boja.
Potonji zahtjev omogućio je igračke kao što su digitalni fotoaparati - uređaji veličine male video kamere koji snimaju 24-bitne fotografije na flash kartici od 10-20 MB s PCMCIA sučeljem. Zatim se ova kartica umetne u utor na vašem prijenosnom računalu i odgovarajući program vam omogućuje čitanje slika. Nije li istina da bi algoritam bio asimetričan, bilo bi neugodno dugo čekati dok se uređaj ne "napuni" - komprimira sliku.
Još jedno ne baš ugodno svojstvo JPEG-a je da su vodoravne i okomite pruge na zaslonu često potpuno nevidljive i mogu se pojaviti samo kada su ispisane u obliku moiré uzorka. Pojavljuje se kada se na vodoravne i okomite pruge slike nanese kosi uzorak ispisa. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u ispisu, postavljajući visoke koeficijente. Međutim, kada se arhiviraju slike namijenjene ljudskom gledanju, ono je trenutno neizostavno.
Široka primjena JPEG-a dugo vremena sputan, možda, samo činjenicom da operira s 24-bitnim slikama. Stoga, da bi se na konvencionalnom monitoru prikazala slika prihvatljive kvalitete 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 pretvoren u 24-bitni JPEG, a zatim natrag u GIF za gledanje, tada će se gubitak kvalitete dogoditi dvaput s obje konverzije. Međutim, dobitak u veličini arhive često je tako velik (3-20 puta!), a gubitak u kvaliteti tako mali da je pohranjivanje slika u JPEG vrlo učinkovito.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije fiksiran. Koristeći to, proizvođači stvaraju vlastite, nekompatibilne formate, te stoga mogu promijeniti algoritam. Dakle, interne tablice algoritma koje preporučuje ISO zamjenjuju se svojim vlastitim. Osim toga, postoji mala zbrka pri postavljanju stupnja gubitka. Na primjer, prilikom testiranja ispada da "izvrsna" kvaliteta, "100%" i "10 bodova" daju značajno različite slike. Istodobno, usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i varijante JPEG-a za određene aplikacije.
Kako se ISO standard JPEG počinje sve više koristiti u razmjeni slika u računalnim mrežama. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijskim sustavima.
Karakteristike algoritma JPEG:
Klasa slike: 24-bitne slike u boji ili slike u sivim tonovima bez oštrih prijelaza boja (fotografije).
Simetrija: 1
Karakteristike: U nekim slučajevima algoritam stvara "aureolu" oko oštrih horizontalnih i okomitih rubova na slici (Gibbsov efekt). Osim toga, uz visok stupanj kompresije, slika se raspada u blokove veličine 8x8 piksela.
Fraktalni algoritamIdeja o metodi
Fraktalno arhiviranje temelji se na činjenici da sliku predstavljamo u kompaktnijem obliku – koristeći koeficijente sustava iteriranih funkcija (Iterated Function System – u daljnjem tekstu IFS). Prije razmatranja samog procesa arhiviranja, pogledajmo kako IFS gradi sliku, t.j. proces dekompresije.
Strogo govoreći, IFS je skup trodimenzionalnih afinih transformacija, u našem slučaju pretvarajući jednu sliku u drugu. Točke u trodimenzionalnom prostoru (x_coordinate, y_coordinate, svjetlina) su podvrgnute transformaciji.
Taj je proces najjasnije pokazao Barnsley u svojoj knjizi “Fractal Image Compression”. Tamo je uveden koncept fotokopirnog uređaja koji se sastoji od zaslona na kojem se prikazuje originalna slika i sustava leća koje projiciraju sliku na drugi zaslon:
- Leće mogu projicirati dio slike slobodnog oblika na bilo koje drugo mjesto na novoj slici.
- područja, u kojem slike se projiciraju ne sijeku.
- leća može promijeniti svjetlinu i smanjiti kontrast.
- leća može preokrenuti i rotirati vaš fragment slike.
- Leće trebao bi mjeriti(smanjite) fragment vaše slike.
Postavljanjem leća i promjenom njihovih karakteristika možemo kontrolirati dobivenu sliku. Jedna iteracija rada Stroja sastoji se u tome da se od izvorne 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 se prestati mijenjati. To će ovisiti samo o mjestu i karakteristikama leća, a neće ovisiti o izvornoj slici. Ova slika se zove " fiksna točka" ili atraktor ovaj IFS. Odgovarajuća teorija jamči da postoji točno jedna fiksna točka za svaki IFS.
Budući da je mapiranje leće kontraktivno, svaka leća eksplicitno definira sebi slični područja na našoj slici. Zahvaljujući samosličnosti, dobivamo složenu strukturu slike pri bilo kojem povećanju. Dakle, intuitivno je jasno da sustav iteriranih funkcija definira fraktalni(nestrogo - sebi sličan matematički objekt).
Najpoznatije su dvije slike dobivene uz pomoć IFS-a: “Sierpinski trokut” i “Paprat Barnsley”. "Sierpinski trokut" zadan je s tri, a "Barnsleyeva paprat" s četiri afine transformacije (ili, u našoj terminologiji, "leće"). 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 svako od njih bi bilo slično cijeloj slici (ne zaboravite stabljiku paprati).
Iz navedenog postaje jasno kako arhiver radi i zašto je potrebno toliko vremena. Zapravo, 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 primjenjuje algoritam optimizacije, bit će potrebno nabrojati i usporediti sve moguće fragmente slike različitih veličina. Čak i za male slike, uzimajući u obzir diskretnost, dobit ćemo astronomski broj opcija koje treba razvrstati. Štoviše, čak i oštro sužavanje klasa transformacije, na primjer, skaliranjem samo određeni broj puta, ne daje zamjetnu dobit u vremenu. Osim toga, gubi se kvaliteta slike. Velika većina istraživanja u području fraktalne kompresije sada je usmjerena na smanjenje vremena arhiviranja potrebnog za dobivanje slike visoke kvalitete.
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. Točka kao što se zove fiksna točka(atraktor) transformacije.
Definicija. Za transformaciju u metričkom prostoru (X, d) kažemo 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 s prilično jakim ograničenjima na koeficijente.
Teorema. (O transformaciji kompresije)
Neka u kompletnom metričkom prostoru (X, d). Tada postoji točno jedna fiksna točka ove transformacije, a za bilo koju točku niz 
konvergira na .
Općenitija formulacija ovog teorema jamči konvergenciju.
Definicija. Slika je funkcija S definirana na jediničnom kvadratu i uzima vrijednosti od 0 do 1 ili
Neka se trodimenzionalna afina transformacija piš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 pomakom (e,f) i rotaciju koju daje matrica
Međutim, ako protumačimo vrijednost S kako će se svjetlina odgovarajućih točaka smanjiti u str puta (transformacija mora biti kontraktivna) i promijenit će se u pomak q.
Definicija.
konačna populacija W ugovaranje trodimenzionalnih afinih transformacija definiranih na domenama tako da i 
, Zove se sustav iteriranih funkcija ( IFS).
Sustav iteriranih funkcija jedinstveno je povezan s fiksnom točkom - slikom. Dakle, proces kompresije se sastoji u traženju koeficijenata sustava, a proces dekompresije se sastoji u iteraciji sustava dok se rezultirajuća slika ne stabilizira (fiksna točka IFS). U praksi je dovoljno 7-16 iteracija. Regije će se nazivati rangiranje, i područja domena.
Izgradnja algoritma
Kao što je iz navedenog već postalo očito, 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 dobivamo astronomski broj opcija za razvrstavanje različitih fragmenata, koji se trenutno ne mogu obraditi čak ni na superračunalu.
V 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. Zapravo, mi ćemo aproksimirati cijeli mnogostrukost geometrijski oblici samo kvadrati.
- Prilikom pretvaranja područja domene u domenu ranga, veličina se smanjuje točno dvaput. To uvelike pojednostavljuje i kompresor i dekompresor. zadatak skaliranja malih područja nije trivijalan.
- Svi blokovi domene su kvadrati i imaju fiksna veličina. Slika je podijeljena jednoličnom mrežom u skup blokova domene.
- Područja domene se preuzimaju "kroz točku" u X i 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 dopušteno zrcalni odraz. Ukupni broj moguće transformacije (brojeći prazno) - 8.
- Provodi se skaliranje (kompresija) okomito (svjetlina). fiksni broj puta- na 0,75.
Ova ograničenja dopuštaju:
- Konstruirajte algoritam koji zahtijeva relativno mali broj operacija čak i na dovoljno velikim slikama.
- Vrlo je kompaktan za predstavljanje podataka koji se zapisuju 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 biti dovoljno 8 bitova po broju.
- tri bita za određivanje transformacije simetrije prilikom pretvaranja bloka domene u blok ranga.
- 7-9 bita za postavljanje pomaka svjetline tijekom prijevoda.
Na primjer, za datoteku u sivim tonovima od 256 boja od 512x512 piksela, s veličinom bloka od 8 piksela, afine transformacije bit će 4096 (512/8x512/8). Svaki će zahtijevati 3,5 bajta. Stoga, ako je izvorna datoteka zauzimala 262144 (512x512) bajtova (bez zaglavlja), tada bi datoteka s koeficijentima zauzela 14336 bajtova. Koeficijent arhiviranja - 18 puta. Istodobno, ne uzimamo u obzir da datoteka s koeficijentima također može imati redundantnost i biti arhivirana 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, kut između kojih nije višekratnik 90 0 .
Sam algoritam pakiranja svodi se na nabrajanje svih blokova domene i odabir za svaki odgovarajući blok ranga. Ispod je dijagram ovog algoritma.
za (sve blokove raspona) (
min_distance = Maksimalna udaljenost;
R i J= slika->KopirajBlok(i,j);
za (svi blokovi domene) ( // S rotacijama i neg.
struja=Trenutačne koordinate transformacije;
D=slika->KopirajBlok(trenutno);
strujna_udaljenost = R i J.L2udaljenost(D);
if(trenutna_udaljenost< min_distance) {
// Ako su najbolji izgledi lošiji:
min_udaljenost = trenutna_udaljenost;
najbolje = trenutno;
}
) //Sljedeći raspon
Save_Coefficients_to_file(najbolje);
) //Sljedeća domena
Kao što se može vidjeti 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 s najmanjom mjerom L 2 (najmanje standardno odstupanje) i spremite 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 izračunava se na sljedeći način:
,
gdje r i J- vrijednosti piksela bloka za rangiranje ( R), a d i J- vrijednosti piksela bloka domene ( D). U ovom slučaju mjera se smatra kao:
.
Ne kalkuliramo korijen od L 2 mjeriti i ne dijeliti po n, budući da su podaci o transformaciji monotoni i neće nas spriječiti u pronalaženju ekstrema, 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 tonovima 256 boja 512x512 piksela s veličinom bloka od 8 piksela:
Tako smo uspjeli svesti broj operacija algoritma kompresije na sasvim izračunljive (iako u nekoliko sati) vrijednosti.
Dijagram algoritma dekompresije slike
Dekompresija algoritma fraktalne kompresije iznimno je jednostavna. Potrebno je provesti nekoliko iteracija trodimenzionalnih afinih transformacija čiji su koeficijenti dobiveni u fazi kompresije.
Apsolutno bilo koja slika (na primjer, apsolutno crna) može se uzeti kao početna, budući da nam odgovarajući matematički aparat jamči konvergenciju slijeda slika dobivenih tijekom IFS iteracija na nepokretnu sliku (blizu izvornoj). Obično je za to dovoljno 16 iteracija.
Pročitajte koeficijente svih blokova iz datoteke;
Krenimo crna slika prava veličina;
Dok (slika neće stati)(
Za(svaki raspon (R))(
D=slika->KopirajBlok(D_koord_za_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 zabilježili koeficijente za blokove R i J(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 pomoću afine transformacije.
Kao što se može izračunati, broj operacija po pikselu slike u sivim tonovima tijekom 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!). Istodobno, za fraktalni algoritam, množenje se događa 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 umnožak dvaju vektora, što je neophodno u slučaju JPEG-a. Za sliku u punoj boji situacija se ne mijenja kvalitativno, budući da oba algoritma koriste pretvorbu u drugi prostor boja.
Procjena gubitaka i načini njihovog reguliranja
Na 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čito rješenje je razbiti ovaj fragment na manje i pokušati ih potražiti. Istodobno, jasno je da se ovaj postupak ne može ponavljati beskonačno, inače će broj potrebnih transformacija postati toliko velik 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 s gubicima, vrlo su važni mehanizmi pomoću kojih će se moći kontrolirati stupanj kompresije i stupanj gubitka. Do danas je razvijen dovoljno velik skup takvih metoda. Prvo, moguće je ograničiti broj afinih transformacija osiguravajući da omjer kompresije ne bude 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 vrijednosti praga, taj 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 toč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 puno veća od one najbližeg "konkurenta" - JPEG algoritma.
Karakteristike fraktalnog algoritma :
Omjeri kompresije: 2-2000 (korisnički definirano)
Klasa slike: 24-bitne slike u boji ili slike u sivim tonovima bez oštrih prijelaza 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 mutna.
Simetrija: 100-100000
Karakteristike: Može slobodno skalirati sliku prilikom otkopčavanja, povećavajući je 2-4 puta bez pojave "efekta stubišta". Kako se razina kompresije povećava, na rubovima blokova na slici pojavljuje se "blokiran" efekt.
Rekurzivni (valni) algoritamEngleski naziv za rekurzivnu kompresiju je wavelet. Na ruski se prevodi kao kompresija vala, i kao kompresija pomoću rafala. Ova vrsta arhiviranja poznata je dugo vremena i izravno proizlazi iz ideje korištenja koherentnosti regija. Algoritam je fokusiran na slike u boji i crno-bijele s glatki prijelazi. Idealno za slike poput x-zrake. Omjer kompresije je postavljen i varira između 5-100. Kada pokušate postaviti veći koeficijent na oštrim rubovima, posebno onima koji prolaze dijagonalno, pojavljuje se "efekt stepenica" - koraci različite svjetline veličine nekoliko piksela.
Ideja algoritma je da razliku spremamo 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 se može predstaviti kao b 1 i=(a 2i +a 2i +1 )/2 i b 2 i=(a 2i -a 2i +1 )/2. Slično slijed a imogu se prevesti u parovima u niz b 1.2i.
Hajdemo analizirati konkretan primjer: Komprimirajmo niz vrijednosti svjetline od 8 piksela ( a i): (220, 211, 212, 218, 217, 214, 210, 202). Dobit ćemo sljedeće sekvence b 1 i, i 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 se radnja izvodi kao rekurzivno, otuda i naziv algoritma. Dobivamo 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, pomoću Huffmanovog algoritma s fiksnim tablicama, možemo staviti u datoteku.
Imajte na umu da smo samo dvaput primijenili našu transformaciju na lanac. U stvarnosti, možemo si priuštiti primjenu wavelet transformacije 4-6 puta. Štoviše, dodatna kompresija se može postići korištenjem Huffmanovih tablica neujednačenih koraka (tj. moramo pohraniti Huffmanov kod za najbližu vrijednost u tablici). Ove tehnike omogućuju postizanje vidljivih omjera kompresije.
Vježba: Vratili smo lanac (215, 211) (0, 5) (5, -3, 2, 4) iz datoteke (vidi primjer). Napravite niz od osam vrijednosti svjetline piksela koje će algoritam kompresije vala ponovno stvoriti.
Algoritam za dvodimenzionalne podatke implementiran je na sličan način. Ako imamo kvadrat od 4 točke sa svjetlinama a 2i, 2j,a 2 i +1 , 2 j,a 2i, 2j+1, i a 2 i +1 , 2 j +1, onda
| Početni | B1 | B2 | |
| slika | B3 | B4 |
Koristeći ove formule, za sliku veličine 512x512 piksela, nakon prve transformacije, dobit ć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 s dvodimenzionalnim slučajem, možemo ponoviti našu transformaciju i umjesto prve matrice dobiti 4 matrice veličine 128x128. 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 dobivene u zadnjem retku () obično se zanemaruju (odmah dobivamo dobit od oko trećine veličine datoteke - 1- 1/4 - 1/16 - 1/64 ...).
Prednosti ovog algoritma uključuju činjenicu da vrlo jednostavno omogućuje implementaciju mogućnosti postupnog "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. Točnije, radimo s blokovima 2x2, 4x4, 8x8 itd. Međutim, zbog činjenice da koeficijente za ove blokove pohranjujemo neovisno, vrlo lako možemo izbjeći podjelu slike na "mozaične" kvadrate.
Karakteristike valnog algoritma:
Omjeri kompresije: 2-200 (korisnički definirano)
Klasa slike: Kao fraktal i JPEG.
Simetrija: ~1.5
Karakteristike: Osim toga, s visokim stupnjem kompresije, slika se raspada u zasebne blokove.
Zaključak
U zaključku, pogledajmo tablice koje sažimaju parametre različitih algoritama kompresije slike o kojima smo gore raspravljali.
| Algoritam | Značajke 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čita frekvencija boja: 2 2 3 2 2 4 3 2 2 2 4 |
| CCITT-3 | prevlast bijela boja na slici, velika područja ispunjena jednom bojom |
| Ponavljajući | Glatki prijelazi boja i bez oštrih rubova |
| JPEG | Nema oštrih granica |
| fraktalni | Sličnost između elemenata slike |
| Algoritam | K-you kompresiju | Simetrija u vremenu | Za što orijentiran |
Gubici | Dimenzija |
| RLE | 32, 2, 0.5 | 1 | 3,4-bitni | Ne | 1D |
| LZW | 1000, 4, 5/7 | 1.2-3 | 1-8 bita | Ne | 1D |
| huffman | 8, 1.5, 1 | 1-1.5 | 8 bita | Ne | 1D |
| CCITT-3 | 213(3), 5, 0.25 | ~1 | 1-bitni | Ne | 1D |
| JBIG | 2-30 puta | ~1 | 1-bitni | 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 |
| fraktalni | 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 opažati formatiranje unutra pre oznake i kod. Sav tekst se pretvorio u nered. Uprava habra mi nije mogla pomoći. Sada neujednačeno, ali barem čitljivo.
Jeste li ikada željeli znati kako funkcionira jpg datoteka? A sad da shvatimo! Zagrijte svoj omiljeni prevodilac i heksadecimalni uređivač, dekodirajmo ovo:
Posebno je napravio manji crtež. Ovo je poznati, ali jako komprimirani Googleov favicon:
Odmah vas upozoravam da je opis pojednostavljen, a navedene 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 oznaka koja označava početak odjeljka komentara. Sljedeća 2 bajta
- duljina odjeljka (uključujući ova 2 bajta). Tako u sljedeća dva
- sam komentar. To su znakovni kodovi ":" i ")", tj. obični smajli. Možete ga vidjeti u prvom retku s desne strane hex uređivača.
Malo teorije
Vrlo kratko korak po korak:
Razmislimo o redoslijedu kojim se ti 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 pričekati da se cijela slika učita prije nego što se pojavi na ekranu. Također će biti neugodno ako se izgubi kraj datoteke. Vjerojatno postoje i drugi dobri razlozi. Stoga se kodirani podaci slažu naizmjenično, u malim dijelovima. 
Dopustite mi 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 datoteke
Nakon što izdvojimo komentar, bit će lako razumjeti da:- Datoteka je podijeljena na sektore kojima prethode markeri.
- Tokeni su dugi 2 bajta, s prvim bajtom .
- Gotovo svi sektori pohranjuju svoju duljinu 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 - tablica kvantizacije.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
Zaglavlje odjeljka uvijek ima 3 bajta. U našem slučaju, ovo je . Zaglavlje se sastoji od:
Duljina: 0x43 = 67 bajtova
Duljina vrijednosti u tablici: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tablice: 0
Preostala 64 bajta trebaju ispuniti tablicu 8x8.
Pogledajte pobliže redoslijed kojim se popunjavaju vrijednosti tablice. Ovaj redoslijed naziva se cik-cak redoslijed: 
Oznaka : SOF0 - Osnovni DCT
Ova oznaka 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. To vam omogućuje da shvatite što 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
Duljina: 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 tablice kvantizacije: 1
Sada pogledajte kako odrediti koliko je slika istanjena. Nalazimo H max = 2 i V max \u003d 2. Kanal i bit će desetkovan za H max /H i puta horizontalno i V max /V i puta okomito.
Marker: DHT (Huffmanov 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 - tablica koeficijenta istosmjerne struje, 1 - tablica koeficijenta izmjenične struje).
[_0]
ID tablice: 0
Duljina Huffmanovog koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Broj kodova znači broj kodova te duljine. Imajte na umu da odjeljak pohranjuje samo duljine kodova, a ne same kodove. Šifre moramo pronaći sami. Dakle, imamo jedan kod duljine 1 i jedan duljine 2. Ukupno su 2 koda, u ovoj tablici 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 izgraditi binarno stablo iz tablice koju smo dobili u odjeljku DHT. I već po ovom stablu prepoznat ćemo svaki kod. Vrijednosti se dodaju redoslijedom kojim su navedene u tablici. 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 mjesta, onda se vraćamo na razinu iznad, i pokušavamo odatle. Morate se zaustaviti na razini koja je jednaka duljini koda. Lijeve grane odgovaraju vrijednosti 0 , desne - 1 .Komentar:
Nije potrebno svaki put krenuti od vrha. Dodana vrijednost - povratak na gornju razinu. Postoji li desna grana? Ako da, idi opet gore. Ako ne, stvorite desnu granu i idite tamo. Zatim, odatle, počnite tražiti da biste dodali sljedeću vrijednost.
Stabla za sve tablice u ovom primjeru: 
UPD (hvala): Čvorovi prvog stabla (DC, id =0) moraju imati vrijednosti 0x03 i 0x02
U krugovima - vrijednosti kodova, ispod krugova - sami kodovi (objasnit ću da smo ih dobili idući od vrha do svakog čvora). Upravo takvim kodovima (ove i drugih tablica) je kodiran sam sadržaj slike.
Marker: SOS (početak skeniranja)
Bajt u tokenu znači "DA! Konačno, prešli smo izravno na raščlanjivanje dijela kodirane slike! No, dionica se simbolično zove SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Duljina 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 završava dio zaglavlja, odavde do kraja (marker) kodiranih podataka.
0
Pronalaženje istosmjernog koeficijenta.
1.
Čitanje niza bitova (ako susrećemo 2 bajta, onda ovo nije marker, već samo bajt). Nakon svakog bita krećemo se duž Huffmanovog stabla (s odgovarajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako smo na završnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, tada je koeficijent 0, upišite ga u tablicu i nastavite s čitanjem ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je duljina koeficijenta u bitovima. To jest, čitamo sljedeća 2 bita, to će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka vrijednosti u binarni prikaz- 1, zatim ostavite kako jest: DC_coef = vrijednost. Inače, pretvorite: DC_coef = vrijednost-2 duljina vrijednosti +1 . Koeficijent upisujemo u tablicu na početku cik-cak - gornji lijevi kut.
Pronalaženje AC-koeficijenata.
1.
Slično točki 1, pronalaženje DC koeficijenta. Nastavljamo čitati slijed:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednako 0, to znači da preostale vrijednosti matrice moraju biti ispunjene nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji su pročitali do ove točke i pisali mi o tome osobno, dobit će plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - to je koliko nula trebamo dodati u matricu. To su 3 nula koeficijenta.
Drugi grickanje: 0x1 - duljina koeficijenta u bitovima. Pročitajte sljedeći dio.
10
10
1110
1
110011101100001111100100
3. Slično točki 3 pronalaženja DC-koeficijenta.
Kao što ste već shvatili, morate čitati AC koeficijente dok ne naiđete na nultu vrijednost koda ili dok se matrica ne popuni.
U našem slučaju ćemo dobiti:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
i matrica:
Jeste li primijetili da su vrijednosti ispunjene istim cik-cak uzorkom?
Razlog za korištenje ove narudžbe je jednostavan – jer što 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 iz prethodne tablice (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čite. Ovo pravilo vrijedi do kraja datoteke.
… 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]
Budući da postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknutima.
Računalstvo
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član s elementima matrice kvantizacije. Ostaje odabrati pravi. Prvo smo skenirali prvu komponentu, njezina komponenta slike = 1. Komponenta slike s 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, dobivamo još 3 Y-kanalne matrice ...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
… i 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 rezultirajuća matrica koeficijenata. u - stupac, v - red. s yx - izravne vrijednosti kanala.
* Općenito govoreći, to nije sasvim toč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 – isplivale su razne greške. Uskoro sam se mogao diviti ispravno 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, tada za izračunavanje jednog kanala od jednog piksela morate pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - gotovo tisuću 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 točnosti timera od 15 ms, a nakon toga promijenio sliku u fotografiju 25 puta veću. Možda ću o tome pisati u zasebnom č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 ostala 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 uopće ne ulazim, o čemu ti pričaš.
- Nakon što se dobiju vrijednosti boja YCbCr, preostaje konvertirati u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij), Y ij, Cb ij, Cr ij su naše primljene matrice.
- 4 Y matrice, i po jedna Cb i Cr, budući da 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.
Ovdje su rezultirajuće tablice za R, G, B kanale za gornji lijevi kvadrat 8x8 našeg primjera:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
