Ako funguje kompresný algoritmus JPEG. Algoritmus JPEG je stratový algoritmus kompresie údajov.

Algoritmus na konverziu grafického obrázka JPEG pozostáva z niekoľkých fáz, ktoré sa na obrázku vykonávajú postupne, jedna po druhej:

- konverzie farebného priestoru,

- podvzorkovanie,

– diskrétna kosínusová transformácia (DCT),

- kvantovanie,

- kódovanie.

Vo fáze konverzie farebného priestoru sa obraz prevedie z farebného priestoru RGB na YCbCr (kde Y je jas a Cb a Cr sú zložky farebného rozdielu bodu obrazu):

Aplikácia priestoru YCbCr namiesto bežného RGB kvôli fyziologickým vlastnostiam ľudského zraku, konkrétne skutočnosti, že ľudský nervový systém má oveľa väčšiu citlivosť na jas ( Y) než na farebné rozdiely komponentov (v tomto prípade Cb a Cr). Inverzná konverzia farebného priestoru (z YCrCb v RGB) vyzerá ako:

Algoritmus kompresie JPEG vám umožňuje komprimovať obrázky s rôznymi veľkosťami farebnej roviny. Označiť podľa x i a y išírka a výška i-tá farebná rovina obrazu. Nechaj X= max(x i), Y= max(y i), definujeme pre každú rovinu koeficienty Ahoj= X/ x i a Vi= Y/ y i. Najvyššia hodnota pre X a Y podľa algoritmu JPEG je 2 16 a pre Ahoj a Vi– 2 2 . Šírka a výška farebných rovín teda môžu byť 1 až 4 krát menšie ako rozmery najväčšej roviny. Pre obyčajných RGB obrázky sú rozmery všetkých farebných rovín rovnaké.

Podvzorkovanie má zmenšiť veľkosť lietadiel Cr a Cb. Najbežnejšie zmenšenie je 2-krát na šírku a 2-krát na výšku (pozri obrázok 1). Pre to Cr a Cb obrazové roviny sú rozdelené do blokov s veľkosťou 2 x 2 body a blok je nahradený jednou vzorkou zložiek farebného rozdielu (namiesto existujúcich 4 vzoriek sa vloží ich aritmetický priemer pre každý blok, čo umožňuje zmenšenie veľkosti pôvodného obrázka 2-krát).

Obrázok 1 – Bežné typy podvzorkovania

Potom samostatne pre každú zložku farebného priestoru Y, Cb a Cr vykoná sa priama diskrétna kosínusová transformácia. Na tento účel sa obrázok rozdelí na bloky s veľkosťou 8 x 8 pixelov a každý blok sa transformuje podľa vzorca:

Použitie diskrétnej kosínusovej transformácie umožňuje prejsť od priestorovej reprezentácie obrazu k spektrálnej. Inverzná diskrétna kosínusová transformácia má tvar:

Potom môžete pristúpiť ku kvantovaniu prijatých informácií. Myšlienkou kvantovania je vyradiť určité množstvo informácií. Je známe, že ľudské oko je menej náchylné na vysoké frekvencie (najmä na vysoké frekvencie zložiek farebných rozdielov), väčšina fotografických obrázkov obsahuje málo vysokofrekvenčných zložiek. Objavenie sa vysokých frekvencií je navyše dôsledkom procesu digitalizácie, t.j. kvôli výskytu sprievodného vzorkovacieho a kvantizačného šumu. V tejto fáze tzv kvantizačné tabuľky- matice pozostávajúce z kladných celých čísel s veľkosťou 8 x 8, do ktorých prvkov sú rozdelené zodpovedajúce frekvencie obrazových blokov, výsledok sa zaokrúhli na celé číslo:

.

V procese dekvantizácie sa používajú rovnaké tabuľky ako pri kvantizácii. Dekvantizácia spočíva vo vynásobení kvantovaných frekvencií zodpovedajúcimi prvkami kvantizačnej tabuľky:

So zvýšením kvantizačného koeficientu sa teda zvyšuje množstvo vyradených informácií. Pozrime sa na to podrobnejšie s príkladom.

Blok pred kvantizáciou:

3862, –22, –162, –111, –414, 12, 717, 490,

383, 902, 913, 234, –555, 18, –189, 236,

229, 707, –708, 775, 423, –411, –66, –685,

231, 34, –928, 34, –1221, 647, 98, –824,

–394, 128, –307, 757, 10, –21, 431, 427,

324, –874, –367, –103, –308, 74, –1017, 1502,

208, –90, 114, –363, 478, 330, 52, 558,

577, 1094, 62, 19, –810, –157, –979, –98

Tabuľka kvantifikácie (kvalita 90):

24, 16, 16, 24, 40, 64, 80, 96,

16, 16, 24, 32, 40, 96, 96, 88,

24, 24, 24, 40, 64, 88, 112, 88,

24, 24, 32, 48, 80, 136, 128, 96,

32, 32, 56, 88, 112, 176, 168, 120,

40, 56, 88, 104, 128, 168, 184, 144,

80, 104, 128, 136, 168, 192, 192, 160,

112, 144, 152, 160, 176, 160, 168, 160

Blok po kvantizácii:

161, –1, –10, –5, –10, 0, 9, 5,

24, 56, 38, 7, –14, 0, –2, 3,

10, 29, –30, 19, 7, –5, –1, –8,

10, 1, –29, 1, –15, 5, 1, –9,

–12, 4, –5, 9, 0, 0, 3, 4,

8, –16, –4, –1, –2, 0, –6, 10,

3, –1, 1, –3, 3, 2, 0, 3,

5, 8, 0, 0, –5, –1, –6, –1

3864, –16, –160, –120, –400, 0, 720, 480,

384, 896, 912, 224, –560, 0, –192, 264,

240, 696, –720, 760, 448, –440, –112, –704,

240, 24, –928, 48,–1200, 680, 128, –864,

–384, 128, –280, 792, 0, 0, 504, 480,

320, –896, –352, –104, –256, 0,–1104, 1440,

240, –104, 128, –408, 504, 384, 0, 480,

560, 1152, 0, 0, –880, –160,–1008, –160

Kvantizačná tabuľka (kvalita 45):

144, 96, 88, 144, 216, 352, 456, 544,

104, 104, 128, 168, 232, 512, 536, 488,

128, 112, 144, 216, 352, 504, 616, 496,

128, 152, 192, 256, 456, 776, 712, 552,

160, 192, 328, 496, 600, 968, 912, 680,

216, 312, 488, 568, 720, 920, 1000, 816,

432, 568, 696, 776, 912, 1072, 1064, 896,

640, 816, 840, 872, 992, 888, 912, 880

Blok po kvantizácii:

27, 0, –2, –1, –2, 0, 2, 1,

4, 9, 7, 1, –2, 0, 0, 0,

2, 6, –5, 4, 1, –1, 0, –1,

2, 0, –5, 0, –3, 1, 0, –1,

–2, 1, –1, 2, 0, 0, 0, 1,

2, –3, –1, 0, 0, 0, –1, 2,

0, 0, 0, 0, 1, 0, 0, 1,

1, 1, 0, 0, –1, 0, –1, 0

Blok po spätnej transformácii:

3888, 0, –176, –144, –432, 0, 912, 544,

416, 936, 896, 168, –464, 0, 0, 0,

256, 672, –720, 864, 352, –504, 0, –496,

256, 0, –960, 0,–1368, 776, 0, –552,

–320, 192, –328, 992, 0, 0, 0, 680,

432, –936, –488, 0, 0, 0,–1000, 1632,

0, 0, 0, 0, 912, 0, 0, 896,

640, 816, 0, 0, –992, 0, –912, 0

Ako vidno, v prvom prípade ide o zmenu DC koeficient v dôsledku kompresie je 2 av druhom 26, zatiaľ čo kvantovaný DC koeficient v druhom prípade je 6-krát menší ako v prvom.

Kódovanie je posledná fáza kompresie, počas ktorej sa obrazové bloky prevedú do vektorovej podoby podľa pravidla určeného blokmi formulára:

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

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

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

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

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

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

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

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

kde prvky bloku sú vektorové indexy zodpovedajúcich zložiek matice. V tomto prípade je nulový prvok zakódovaný ako rozdiel s nulovým prvkom predchádzajúceho bloku. Nulové prvky označujú DC, obsahujú konštantnú zložku bloku (všetky ostatné prvky AC sa zvyčajne označujú AC).

Výsledné dáta sú potom komprimované pomocou aritmetického kódovania alebo modifikácie Huffmanovho algoritmu. Táto etapa nie je z pohľadu steganografie v grafických obrázkoch veľmi zaujímavá, takže je mimo rámca našej úvahy.

JPEG je jeden z najnovších a pomerne výkonných algoritmov. V praxi je to de facto štandard pre plnofarebné obrázky. Algoritmus pracuje s oblasťami 8x8, na ktorých sa jas a farba menia pomerne hladko. Výsledkom je, že pri rozklade matice takejto oblasti na dvojitý rad z hľadiska kosínusov (vzorce nižšie) sa ukážu ako významné iba prvé koeficienty. Kompresia v JPFG sa teda vykonáva kvôli plynulosti farebných zmien v obraze.

Algoritmus bol vyvinutý skupinou fotografických expertov špeciálne pre kompresiu 24-bitových JPEG obrázkov – Joint Photographic Expert Group – divízia v rámci ISO – Medzinárodnej organizácie pre normalizáciu. Vo všeobecnosti je algoritmus založený na diskrétnej kosínusovej transformácii (ďalej DCT) aplikovanej na maticu obrazu, aby sa získala nejaká nová matica koeficientov. Na získanie pôvodného obrázka sa použije inverzná transformácia

DCT rozkladá obraz v zmysle amplitúd niektorých frekvencií, takže počas transformácie dostaneme maticu, v ktorej je veľa koeficientov buď blízkych alebo rovných nule. Navyše, ľudský systém vnímania farieb je slabý pri rozpoznávaní určitých frekvencií. Preto je možné niektoré koeficienty aproximovať hrubšie bez výraznej straty kvality obrazu.

Na to sa používa kvantovanie koeficientov. V najjednoduchšom prípade ide o aritmetický bitový posun doprava. Táto transformácia stratí niektoré informácie, ale možno dosiahnuť veľké kompresné pomery.

Práca algoritmu.

Poďme komprimovať 24-bitový obrázok.

Krok I

Prevádzame obrázok z farebného priestoru RGB so zložkami zodpovednými za červenú (červenú), zelenú (zelenú) a modrú (modrú) zložku farby bodu do farebného priestoru YCrCb (niekedy nazývaného YUV).

V ňom je Y jasová zložka a Cr, Cb sú zložky zodpovedné za farbu (chromatická červená a chromatická modrá). Vzhľadom na skutočnosť, že ľudské oko je menej citlivé na farbu ako na jas, je možné archivovať polia pre zložky Cr a Cb s veľkými stratami, a teda s veľkými kompresnými pomermi. Podobná transformácia sa už dávno používa v televízii. Užšie frekvenčné pásmo je pridelené signálom zodpovedným za farbu.

Zjednodušene možno preklad z farebného priestoru RGB do farebného priestoru YCrCb znázorniť takto:

Inverzná transformácia sa vykonáva vynásobením vektora YUV inverznou maticou:

Krok 2

Pôvodný obrázok sme rozdelili na matice 8x8. Z každej vytvoríme tri pracovné matice DCT - 8 bitov samostatne pre každý komponent. Pri vysokých kompresných pomeroch môže byť tento krok trochu náročnejší. Obrázok je rozdelený zložkou Y - ako v prvom prípade a pre zložky Cr a Cb sa matice typujú cez riadok a cez stĺpec. Tie. z pôvodnej matice 16x16 sa získa iba jedna pracovná matica DCT. Navyše, ako je dobre vidieť, stratíme 3/4 užitočných informácií o farebných zložkách obrázka a okamžite získame dvojnásobnú kompresiu. Môžeme to urobiť prácou v priestore YCrCb. Na výslednom RGB obrázku to, ako ukázala prax, nemá veľký vplyv.

Krok 3

Na každú pracovnú matricu aplikujeme DCT. V tomto prípade dostaneme maticu, v ktorej koeficienty v ľavom hornom rohu zodpovedajú nízkofrekvenčnej zložke obrazu av pravom dolnom rohu - vysokofrekvenčnej.

V zjednodušenej forme možno túto transformáciu znázorniť takto:

Krok 4

Poďme kvantovať. V princípe ide jednoducho o delenie pracovnej matice kvantizačnou maticou prvok po prvku. Pre každú zložku (Y, U a V) je vo všeobecnom prípade špecifikovaná jej vlastná kvantizačná matica (ďalej MC).

V tomto kroku sa riadi kompresný pomer a dochádza k najväčšej strate. Je jasné, že nastavením MC s veľkými koeficientmi získame viac núl a následne aj väčší kompresný pomer.

Špecifické účinky algoritmu sú tiež spojené s kvantizáciou. Pre veľké hodnoty koeficientu gama , - strata v nízkych frekvenciách môže byť taká veľká, že sa obraz rozpadne na štvorce 8x8. Straty vo vysokých frekvenciách sa môžu prejaviť takzvaným „Gibbsovým efektom“, kedy sa okolo kontúr s ostrým farebným prechodom vytvorí akési „halo“.

Krok 5

Prevod matice 8x8 na 64-prvkový vektor pomocou cik-cak skenovania, t.j. vyberte prvky s indexmi (0,0). (0,1). (1,0). (2.0)...

Na začiatku vektora teda dostaneme koeficienty matice zodpovedajúce nízkym frekvenciám a na konci - vysokým.

Krok 6

Vektor konvolujeme pomocou algoritmu skupinového kódovania. V tomto prípade dostaneme dvojice typu (preskočiť, číslo), kde „preskočiť“ je počítadlo preskočených núl a „číslo“ je hodnota, ktorú je potrebné zadať do nasledujúcej bunky.

Takže vektor bude zložený do párov (0, 42) (0, 3) (3, -2) (4, 1)

Krok 7

Zbalíme naučené páry pomocou Huffmanovho kódovania s pevnou tabuľkou.

Proces rekonštrukcie obrazu v tomto algoritme je úplne symetrický. Metóda vám umožňuje komprimovať niektoré obrázky 10-15 krát bez vážnych strát.

Operačný kanál používaný v algoritme JPEG.

Významné pozitívne aspekty algoritmu sú:

• 1) Nastavte kompresný pomer
• 2) Výstupný farebný obrázok môže mať 24 bitov na bod.

Nevýhody algoritmu sú tieto:

• 1) Keď sa kompresný pomer zvýši, obrázok sa rozdelí na samostatné štvorce (8x8). Je to spôsobené tým, že počas kvantovania dochádza pri nízkych frekvenciách k veľkým stratám a nie je možné obnoviť pôvodné dáta.
• 2) Objaví sa Gibbsov efekt - haló pozdĺž okrajov ostrých farebných prechodov.

Štandardizovaný JPEG relatívne nedávno - v roku 1991. Ale aj vtedy existovali algoritmy, ktoré komprimovali silnejšie s menšou stratou kvality. Faktom je, že akcie vývojárov štandardu boli obmedzené silou technológie, ktorá v tom čase existovala. To znamená, že aj na osobnom počítači musel algoritmus pracovať menej ako minútu na priemernom obrázku a jeho hardvérová implementácia by mala byť relatívne jednoduchá a lacná. Algoritmus musel byť symetrický (čas rozbalenia je približne rovnaký ako čas archivácie).

Posledná požiadavka umožnila vznik digitálnych fotoaparátov - zariadení veľkosti malej videokamery, ktoré snímajú 24-bitové fotografie na 10-20 MB flash kartu s rozhraním PCMCIA. Potom sa karta vloží do slotu na notebooku a príslušný program vám umožní čítať obrázky. Ak by bol algoritmus asymetrický, bolo by nepríjemné dlho čakať, kým sa zariadenie „dobije“ – skomprimuje obraz.

Ďalšou nie veľmi príjemnou vlastnosťou JPEG je, že často horizontálne a vertikálne pruhy na displeji nie sú absolútne viditeľné a môžu sa objaviť len pri tlači vo forme moaré vzoru. Vyskytuje sa, keď sa na vodorovné a zvislé pruhy obrázka aplikuje šikmý vzor tlače. Kvôli týmto prekvapeniam sa JPEG neodporúča na aktívne používanie pri tlači s nastavením vysokých koeficientov. Pri archivácii a záberoch určených na prezeranie človekom je však v súčasnosti nepostrádateľný.

Široké používanie JPEG po dlhú dobu brzdilo snáď len to, že pracuje s 24-bitovými obrázkami. Preto, aby bolo možné zobraziť obraz s prijateľnou kvalitou na bežnom monitore v 256-farebnej palete, bolo potrebné použiť vhodné algoritmy, a teda určitý čas. V aplikáciách zameraných na vyberavého používateľa, ako sú hry, sú takéto oneskorenia neprijateľné. Okrem toho, ak máte obrázky, povedzme, v 8-bitovom formáte GIF, skonvertované do 24-bitového JPEG a potom späť na GIF na prezeranie, potom pri oboch prevodoch dôjde k strate kvality dvakrát. Avšak nárast veľkosti archívu je často taký veľký (3-20 krát!) a strata kvality je taká malá, že ukladanie obrázkov vo formáte JPEG je veľmi efektívne.

Je potrebné povedať niekoľko slov o modifikáciách tohto algoritmu. Hoci JPEG je štandard ISO, jeho formát súboru nebol opravený. Výrobcovia využívajú túto výhodu a používajú svoje vlastné, nekompatibilné formáty, a preto môžu zmeniť algoritmus. Takže interné tabuľky algoritmu odporúčané ISO. sú nimi nahradené vlastnými.Navyše je mierny zmätok pri nastavovaní miery straty. Napríklad pri testovaní sa ukázalo, že „výborná“ kvalita, „100 %“ a „10 bodov“ poskytujú výrazne odlišné obrázky. Navyše, mimochodom, "100%" kvalita neznamená bezstratovú kompresiu. Existujú aj varianty JPEG pre špecifické aplikácie.

Ako sa ISO štandard JPEG začína čoraz viac využívať pri výmene obrázkov v počítačových sieťach. Algoritmus JPEG je podporovaný vo formátoch Quick Time, PostScript Level 2, Tiff 6.0 a v súčasnosti zaujíma popredné miesto v multimediálnych systémoch.

Charakteristika algoritmu JPFG:

Kompresné pomery: 2-200 (definované používateľom).

Trieda obrázka: Plnofarebné 24-bitové obrázky alebo obrázky v odtieňoch sivej bez ostrých farebných prechodov (fotografie).

Symetria: 1.

Špeciálne vlastnosti: V niektorých prípadoch algoritmus vytvára „halo“ okolo ostrých horizontálnych a vertikálnych okrajov v obraze (Gibbsov efekt). Navyše, pri vysokej miere kompresie sa obraz rozpadá na bloky 8x8 pixelov.

„Implementácia algoritmov

JPEG a JPEG2000"

Dokončené:

študentská skupina 819

Ugarov Dmitrij

Ako fungujú algoritmy JPEG a JPEG2000

1. Algoritmus JPEG

JPEG (English Joint Photographic Experts Group - spoločná skupina odborníkov v oblasti fotografie) - je široko používaná metóda na kompresiu fotografických obrázkov. Formát súboru, ktorý obsahuje komprimované údaje, sa zvyčajne nazýva aj názov JPEG; najbežnejšie prípony takýchto súborov sú .jpeg, .jfif, .jpg, .JPG alebo .JPE. Z nich je však .jpg najobľúbenejšou príponou na všetkých platformách.

Algoritmus JPEG je kompresný algoritmus so stratou kvality.

Oblasť použitia

Formát je stratový kompresný formát, takže je nesprávne predpokladať, že JPEG ukladá dáta ako 8 bitov na kanál (24 bitov na pixel). Na druhej strane, keďže JPEG-komprimované a dekomprimované dáta majú zvyčajne 8 bitov na kanál, táto terminológia sa niekedy používa. Podporovaná je aj kompresia čiernobielych obrázkov v odtieňoch sivej.

Pri ukladaní súboru JPEG môžete určiť stupeň kvality a tým aj stupeň kompresie, ktorý sa zvyčajne nastavuje v ľubovoľných jednotkách, napríklad od 1 do 100 alebo od 1 do 10. Väčšie číslo zodpovedá lepšej kvalite , ale veľkosť súboru sa zväčší. Zvyčajne rozdiel v kvalite medzi 90 a 100 oko prakticky nevníma. Malo by sa pamätať na to, že bit po bite obnovený obraz sa vždy líši od originálu. Bežnou mylnou predstavou je, že kvalita JPEG sa rovná množstvu uložených informácií.

Etapy kódovania

Proces kompresie JPEG zahŕňa niekoľko krokov:

1. Konverzia obrazu do optimálneho farebného priestoru;

Pri použití farebného priestoru luma/chrominance (YCbCr) sa dosiahne lepší kompresný pomer. V tejto fáze kódovania sa pomocou vhodných pomerov farebný model RGB prevedie na YCbCr:

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

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

Cr = 0,5*R – 0,4187*G – 0,0813*B.
Počas dekódovania je možné použiť vhodnú inverznú transformáciu:
R = Y + 1,402 x Cr

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

B = Y + 1,772 x Cb.
Poznámka týkajúca sa Y,Cb,Cr v ľudskom zrakovom systéme:

Oko, najmä sietnica, má dva typy buniek ako vizuálne analyzátory: bunky nočného videnia, ktoré vnímajú iba odtiene sivej (od jasne bielej po tmavo čiernu) a bunky denného videnia, ktoré vnímajú farebný odtieň. Prvé bunky poskytujúce farbu RGB detegujú úroveň jasu podobnú hodnote Y. Ostatné bunky zodpovedné za vnímanie farebného odtieňa určujú hodnotu súvisiacu s rozdielom farieb.

2. podvzorkovanie farbonosných zložiek spriemerovaním skupín pixelov;

Veľká časť vizuálnych informácií, na ktoré je ľudské oko najcitlivejšie, pozostáva z vysokofrekvenčných zložiek jasu v odtieňoch šedej (Y) farebného priestoru YCbCr. Ďalšie dve zložky chromatičnosti (Cb a Cr) obsahujú vysokofrekvenčné farebné informácie, na ktoré je ľudské oko menej citlivé. Preto môže byť určitá jeho časť vyradená a tým je možné znížiť počet uvažovaných pixelov pre farebné kanály.

1) typ 4:2:0 (keď je obraz rozdelený na štvorce 2x2 pixely a v každom z nich všetky pixely dostávajú rovnaké hodnoty kanálov Cb a Cr a jas Y y zostáva pre každý iný)

2) typ 4:2:2 (zjednotenie komponentmi chromatickosti sa vyskytuje iba horizontálne v skupinách po dvoch pixeloch).

3) Typ 4:4:4 znamená, že každý pixel v každom riadku má svoju vlastnú jedinečnú hodnotu zložiek Y, Cb a Cr. (Obr. 1 a)

4) typu 4:2:2. Horizontálnym podvzorkovaním farbonosného signálu faktorom 2 získame prúd YCbCr 4:2:2 z prúdu 4:4:4 YCbCr. Záznam "4: 2: 2" znamená, že v jednom riadku sú 4 hodnoty jasu na 2 hodnoty chrominancie (pozri obr. 1 b). Signál 4:2:2 YCbCr stráca na kvalite obrazu v porovnaní so signálom 4:4:4 YCbCr len veľmi málo, ale požadovaná šírka pásma je znížená o 33 % pôvodnej.

3. Aplikácia diskrétnych kosínusových transformácií na zníženie redundancie obrazových údajov;

Hlavnou fázou algoritmu je diskrétna kosínusová transformácia (DCT alebo DCT), ktorá je druhom Fourierovej transformácie. Používa sa pri práci s obrázkami na rôzne účely, nielen za účelom kompresie. Prechod na frekvenčnú reprezentáciu hodnôt pixelov nám umožňuje iný pohľad na obrázok, jeho spracovanie, a čo je pre nás zaujímavé, aj kompresiu. Navyše, ak poznáme prevodné koeficienty, môžeme vždy vykonať opačnú akciu - vrátiť pôvodný obrázok.

DCT priamo aplikovaná na blok (v našom prípade 8x8 pixelov) obrázka by vyzerala takto:

kde x, y - priestorové súradnice pixelu (0..7) ,

f(x,y) - hodnoty pixelov pôvodného makrobloku (povedzme jas)

u,v - súradnice pixelov vo frekvenčnom vyjadrení (0..7)

w(u) =1/SQRT(2) pre u=0, inak w(u)=1 (SQRT je druhá odmocnina)

w(v) =1/SQRT(2) pre v=0, inak w(v)=1

Alebo v maticovej forme:

4. Kvantovanie každého bloku DCT koeficientov pomocou váhových funkcií optimalizovaných pre ľudské vizuálne vnímanie;

Diskrétna kosínusová transformácia pripravuje informácie na stratovú kompresiu a zaokrúhľovanie. Pre každý prvok transformovanej matice existuje zodpovedajúci prvok matice kvantovanie. Výsledná matica sa získa vydelením každého prvku transformovanej matice zodpovedajúcim prvkom kvantizačnej matice a následným zaokrúhlením výsledku na najbližšie celé číslo. Pri zostavovaní kvantizačnej matice sú jej veľké prvky v ľavom dolnom rohu, takže pri ich delení sú údaje v tomto rohu po diskrétnej kosínusovej transformácii (práve tie, ktoré zaokrúhľujú budú menej bolestivé) zaokrúhlené nahrubšie. Preto sú stratené informácie pre nás menej dôležité ako ostatné.

5. Stupeň sekundárnej kompresie

Poslednou fázou kódovača JPEG je kódovanie výslednej matice.

5.1 Kľukatá permutácia 64 DCT koeficientov

Takže potom, čo sme vykonali transformáciu DCT na bloku hodnôt 8x8, máme nový blok 8x8. Potom sa tento blok 8x8 naskenuje cik-cak takto:

(Čísla v bloku 8x8 označujú poradie, v ktorom sa pozeráme na 2-rozmernú maticu 8x8)

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

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

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

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

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

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

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

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

Ako vidíte, najprv je ľavý horný roh (0,0), potom hodnota (0,1), potom (1,0), potom (2,0), (1,1), (0, 2), (0,3), (1,2), (2,1), (3,0) atď.

Po cikcaku matice 8x8 máme teraz vektor so 64 koeficientmi (0..63). Zmyslom tohto cikcakového vektora je, že sa pozeráme na 8x8 DCT koeficienty vo vzostupnom poradí priestorových frekvencií. Dostaneme teda vektor zoradený podľa kritérií priestorovej frekvencie: prvá hodnota na vektore (index 0) zodpovedá najnižšej frekvencii v obraze – označujeme ju pojmom DC. Keď sa index na vektore zvyšuje, dostávame hodnoty zodpovedajúce vyšším frekvenciám (hodnota s indexom 63 zodpovedá amplitúde najvyššej frekvencie v bloku 8x8). Zvyšné DCT koeficienty sú označené AC.

5.2 RunLength kódovanie núl (RLE)

Teraz máme vektor s dlhou postupnosťou núl. Môžeme to použiť kódovaním po sebe idúcich núl. DÔLEŽITÉ: Neskôr uvidíte prečo, ale tu preskočíme kódovanie prvého koeficientu vektora (koeficient DC), ktorý je zakódovaný inak. Zvážte pôvodný vektor 64 ako vektor 63 (toto je vektor 64 bez prvého koeficientu)

Povedzme, že máme 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, iba 0,... .0

Takto sa robí kompresia RLC JPEG pre tento príklad:

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

Ako vidíte, pre každú hodnotu inú ako 0 zakódujeme počet po sebe idúcich PRIOR 0s pred hodnotou, potom hodnotu pridáme. Ďalšia poznámka: EOB je skrátená forma pre koniec bloku a je to špeciálna kódovaná hodnota (značka). Ak sme dosiahli pozíciu na vektore, od ktorej máme do konca vektora len nuly, pridelíme túto pozíciu EOB a ukončíme RLC kompresiu kvantovaného vektora.

[Všimnite si, že ak kvantovaný vektor nie je ukončený nulou (má posledný prvok iný ako 0), nebudeme mať EOB marker.]

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

Ďalšia ZÁKLADNÁ vec: Povedzme niekde na kvantovanom vektore, ktorý máme:

57, osemnásť núl, 3, 0,0, 0,0 2, tridsaťtri núl, 895, EOB

Kódovanie JPG Huffman predstavuje obmedzenie, že počet úvodných núl musí byť zakódovaný ako 4-bitová hodnota – nemôže presiahnuť 15.

Takže predchádzajúci príklad by mal byť kódovaný takto:

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

(15,0) je špeciálna kódovaná hodnota, ktorá označuje to, čo nasleduje za 16 po sebe idúcimi nulami.

5.3 Posledný krok - Huffmanovo kódovanie

Najprv DÔLEŽITÁ poznámka: Namiesto ukladania skutočnej hodnoty štandard JPEG špecifikuje, že minimálnu veľkosť ukladáme v bitoch, v ktorých môžeme túto hodnotu uchovávať (toto sa nazýva kategória tejto hodnoty) a potom bitovo kódované znázornenie tejto hodnoty. hodnotu takto:

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

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

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

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

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

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

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

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

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

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

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

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

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

Následne pre predchádzajúci príklad:

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

zakódujme iba správnu hodnotu týchto párov, okrem párov, ktoré sú špeciálnymi značkami ako (0,0) alebo (ak musíme mať) (15,0)

45 by bolo podobne zakódované ako (6.101101)

30 -> (5,00001)

A teraz znova napíšeme reťazec párov:

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

Dvojice 2 hodnôt uzavretých v zátvorkách môžu byť reprezentované v byte, pretože v skutočnosti každá z 2 hodnôt môže byť reprezentovaná v 4-bitovom bloku (počet úvodných núl je vždy menší ako 15 a rovnako aj kategória [čísla zakódované v súbore JPG - v oblasti -32767..32767]). V tomto byte vysoký bit predstavuje počet úvodných núl a nízky bit predstavuje kategóriu novej hodnoty inú ako 0.

Posledným krokom kódovania je Huffman zakódovať tento bajt a potom zapísať do súboru JPG ako bitový tok Huffmanov kód tohto bajtu, po ktorom nasleduje bitová reprezentácia tohto čísla.

Napríklad pre bajt 6 (ekvivalent (0,6)) máme Huffmanov kód = 111000;

21 = (1,5) - 11111110110

4 = (0,4) - 1011

33 = (2,1) - 11011

0 = EOB= (0,0) - 1010

Konečný bitový tok zapísaný v súbore JPG na disk pre predchádzajúci príklad je 63 koeficientov (nezabudnite, že sme vynechali prvý koeficient) -

111000 111001 111000 101101 1111111110011001 10111 11111110110 00001

1011 0111 11011 1 1010
Výhody a nevýhody

Medzi nevýhody formátu patrí skutočnosť, že pri silných kompresných pomeroch sa prejavuje dátová štruktúra bloku, obraz je „rozdelený na štvorce“ (každý s veľkosťou 8x8 pixelov). Tento efekt je badateľný najmä v oblastiach s nízkou priestorovou frekvenciou (plynulé prechody obrazu, napr. jasná obloha). V oblastiach s vysokou priestorovou frekvenciou (napríklad kontrastné okraje obrazu) sa objavujú charakteristické „artefakty“ – nepravidelná štruktúra pixelov skreslenej farby a/alebo jasu. Z obrazu navyše zmiznú malé farebné detaily. Nezabudnite tiež, že tento formát nepodporuje transparentnosť.

Napriek svojim nedostatkom sa však JPEG veľmi rozšíril vďaka vysokému kompresnému pomeru v porovnaní s alternatívami existujúcimi v čase jeho uvedenia.

2. Algoritmus JPEG2000

Algoritmus JPEG-2000 bol vyvinutý rovnakou skupinou odborníkov na fotografiu ako JPEG. Vytvorenie JPEG ako medzinárodného štandardu bolo dokončené v roku 1992. V roku 1997 sa ukázalo, že je potrebný nový, flexibilnejší a výkonnejší štandard, ktorý bol dokončený v zime 2000.

Hlavné rozdiely medzi algoritmom v JPEG 2000 a algoritmom v JPEG sú nasledovné:

1) Lepšia kvalita obrazu so silným kompresným pomerom. Alebo, čo je to isté, veľký kompresný pomer s rovnakou kvalitou pre vysoké kompresné pomery. V skutočnosti to znamená výrazné zmenšenie veľkosti grafiky „webovej kvality“, ktorú používa väčšina stránok.

2) Podpora kódovania jednej oblasti s lepšou kvalitou. Je známe, že určité oblasti obrazu sú kritické pre ľudské vnímanie (napríklad oči na fotografii), zatiaľ čo kvalita iných môže byť obetovaná (napríklad pozadie). Pri „manuálnej“ optimalizácii sa zvýšenie kompresného pomeru vykonáva dovtedy, kým sa nestratí kvalita v niektorej dôležitej časti obrazu. Teraz je možné nastaviť kvalitu v kritických oblastiach a ostatné oblasti stlačiť silnejšie, t.j. získame ešte vyšší konečný kompresný pomer pri subjektívne rovnakej kvalite obrazu.

3)Hlavný kompresný algoritmus bol nahradený vlnkou. Okrem vyššie uvedeného zvýšenia kompresného pomeru to eliminovalo 8-pixelovú blokovosť, ku ktorej dochádza pri zvýšení kompresného pomeru. Navyše, plynulý vývoj obrazu je dnes už neodmysliteľne štandardom (progresívny JPEG, aktívne používaný na internete, sa objavil oveľa neskôr ako JPEG).

4) Na zvýšenie kompresného pomeru používa algoritmus aritmetickú kompresiu. Štandard JPEG pôvodne obsahoval aj aritmetickú kompresiu, no neskôr bola nahradená menej efektívnou Huffmanovou kompresiou, pretože aritmetická kompresia bola chránená patentmi. Teraz vypršala platnosť hlavného patentu a existuje príležitosť na zlepšenie algoritmu.

5) Podpora bezstratovej kompresie. Okrem bežnej stratovej kompresie bude nový JPEG teraz podporovať aj bezstratovú kompresiu. Takto je možné použiť JPEG na kompresiu lekárskych obrázkov, pri tlači, pri ukladaní textu na rozpoznanie systémom OCR atď.

6) Podpora kompresie jednobitových (2-farebných) obrázkov. Na ukladanie jednobitových obrázkov (kresby atramentom, naskenovaný text atď.) sa predtým široko odporúčal formát GIF, pretože kompresia pomocou DCT je veľmi neefektívna pre obrázky s ostrými farebnými prechodmi. V JPEG sa pri kompresii 1-bitový obrázok zmenšil na 8-bitový, t.j. zvýšená o 8-krát, potom bol urobený pokus o kompresiu, často menej ako 8-krát. Teraz môžeme odporučiť JPEG 2000 ako univerzálny algoritmus.

7) Transparentnosť je podporovaná na úrovni formátu. Teraz bude možné plynulo prekrývať pozadie pri vytváraní WWW stránok nielen v GIF, ale aj v JPEG 2000. Navyše je podporovaná nielen 1 bitová priehľadnosť (pixel je priehľadný / nepriehľadný), ale samostatný kanál, ktorý vám umožní nastaviť plynulý prechod z nepriehľadného obrázku na priehľadné pozadie.

Okrem toho úroveň formátu podporuje zahrnutie informácií o autorských právach do obrázka, podporu odolnosti voči bitovým chybám počas prenosu a vysielania, môžete požiadať o externé nástroje (pluginy) na dekompresiu alebo spracovanie, môžete zahrnúť jeho popis, informácie o vyhľadávaní, atď. .d.

Etapy kódovania

Proces kompresie podľa schémy JPEG2000 zahŕňa niekoľko krokov:

1. Konverzia obrazu do optimálneho farebného priestoru.
V tejto fáze kódovania sa pomocou vhodných pomerov farebný model RGB prevedie na YUV:

Pri dekompresii sa použije zodpovedajúca inverzná transformácia:

2. Diskrétna vlnková transformácia.

Diskrétna vlnková transformácia (DWT) môže byť tiež dvoch typov – pre prípad stratovej kompresie a pre bezstratovú kompresiu.

Táto transformácia v jednorozmernom prípade je skalárnym súčinom zodpovedajúcich koeficientov a reťazca hodnôt. Ale odvtedy veľa koeficientov je nulových, potom je možné priame a inverzné vlnkové transformácie zapísať pomocou nasledujúcich vzorcov (na transformáciu extrémnych prvkov čiary sa používa jej rozšírenie o 2 pixely v každom smere, ktorých hodnoty sú symetrické s hodnoty prvkov riadku vo vzťahu k jeho extrémnym pixelom):
y(2*n + 1) = x(2*n + 1) - (int)(x(2*n) + x(2*n + 2)) / 2

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

a naopak

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

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

3. Kvantovanie koeficientov.

Rovnako ako v algoritme JPEG sa kvantizácia používa pri kódovaní obrázka vo formáte JPEG2000. Diskrétna vlnková transformácia, podobne ako jej analóg, triedi koeficienty podľa frekvencie. Ale na rozdiel od JPEG je v novom formáte kvantizačná matica rovnaká pre celý obrázok.

4. Stupeň sekundárnej kompresie

. Rovnako ako v prípade JPEG, aj v novom formáte je posledným krokom v kompresnom algoritme bezstratové kódovanie. Na rozdiel od predchádzajúceho formátu však JPEG2000 používa aritmetický kompresný algoritmus.

Softvérová implementácia

V tomto článku sú implementované algoritmy JPEG a JPEG2000. Oba algoritmy implementujú priame a reverzné kódovanie (neexistuje posledná fáza sekundárnej kompresie). Výpočet JPEG trvá pomerne dlho (asi 30 sekúnd) kvôli „priamemu“ výpočtu DCT. Ak potrebujete zvýšiť rýchlosť práce, mali by ste najskôr vypočítať maticu DCT (vykonať zmeny v triede DCT).

Poďme sa pozrieť na program:

1. 
   Po spustení sa zobrazí okno, kde

a môžete ho uložiť stlačením tlačidla (2) a zadaním požadovaného názvu do dialógového okna.

S dostatočne veľkým faktorom kvality sa obraz dramaticky zmení. Ak ide o algoritmus JPEG, vysloví sa bloky 8x8. (V prípade algoritmu JPEG2000 nebude delenie blokov)

Predtým:

po:

JPEG je jedným z nových a pomerne výkonných algoritmov. Je to prakticky de facto štandard pre plnofarebné obrázky. Algoritmus pracuje s oblasťami 8x8, kde sa jas a farba menia pomerne hladko. Výsledkom je, že pri rozklade matice takejto oblasti na dvojitý rad v kosínoch (pozri vzorce nižšie) sú významné iba prvé koeficienty.Takže kompresia v JPEG sa uskutočňuje kvôli plynulosti zmeny farieb v obraze. .

Algoritmus bol vyvinutý skupinou fotografických expertov špeciálne na kompresiu 24-bitových obrázkov. JPEG – Joint Photographic Expert Group – divízia v rámci ISO – International Organization for Standardization. Názov algoritmu sa číta ako ["jei" peg]. Vo všeobecnosti je algoritmus založený na diskrétnej kosínusovej transformácii (ďalej - DCT) aplikovanej na maticu obrazu, aby sa získala nejaká nová matica koeficientov. Na získanie pôvodného obrázka sa použije inverzná transformácia.

DCT rozkladá obraz na amplitúdy určitých frekvencií. Pri transformácii teda dostaneme maticu, v ktorej je veľa koeficientov buď blízkych alebo rovných nule. Navyše vďaka nedokonalosti ľudského videnia je možné koeficienty aproximovať hrubšie bez citeľnej straty kvality obrazu.

Na to sa používa kvantovanie koeficientov. V najjednoduchšom prípade ide o aritmetický bitový posun doprava. Táto transformácia stratí časť informácií, ale dá sa dosiahnuť väčší stupeň kompresie.

Ako funguje algoritmus

Pozrime sa teda na algoritmus podrobnejšie (obr. 2.1). Povedzme, že komprimujeme 24-bitový obrázok.

Krok 1. Prevádzame obrázok z farebného priestoru RGB so zložkami zodpovednými za červenú (červenú), zelenú (zelenú) a modrú (modrú) zložku farby bodu do farebného priestoru YCrCb (niekedy nazývaného YUV).

V ňom je Y zložka jasu a Cr, Co sú zložky zodpovedné za farbu (chromatická červená a chromatická modrá). Vzhľadom na skutočnosť, že ľudské oko je menej citlivé na farbu ako na jas, je možné archivovať polia pre komponenty Cr a Co s vysokými stratami a tým aj vysokými kompresnými pomermi.Takáto transformácia sa už dlho používa v televízii. Užšie frekvenčné pásmo je pridelené signálom zodpovedným za farbu. Zjednodušene možno preklad z farebného priestoru RGB do farebného priestoru YCrCb reprezentovať pomocou prechodovej matice:

Krok 2 Pôvodný obrázok sme rozdelili na matice 8x8. Pracovné matice DCT vytvárame z každých 3 - 8 bitov samostatne pre každý komponent. Pri vyšších kompresných pomeroch môže byť tento krok trochu náročnejší. Obrázok je rozdelený zložkou Y ako v prvom prípade a pre zložky Cr a Cb sa matice typujú cez riadok a cez stĺpec. To znamená, že z pôvodnej matice 16x16 sa získa iba jedna pracovná matica DCT. V tomto prípade, ako je dobre vidieť, stratíme 3/4 užitočných informácií o farebných zložkách obrázka a okamžite získame 2-násobnú kompresiu. Môžeme to urobiť prácou v priestore YCrCb. Ako ukázala prax, výsledný RGB obraz to veľmi neovplyvní.

Krok 3 V zjednodušenej forme možno DCT pre n=8 znázorniť takto:

nu,v] = ^Hc(i,u)xC(j,v)y

rY)

Yq= Celé číslo

V tomto kroku sa riadi kompresný pomer a dochádza k najväčším stratám. Je jasné, že nastavením MC s veľkými koeficientmi získame viac núl a následne aj väčší kompresný pomer.

Špecifické účinky algoritmu sú tiež spojené s kvantizáciou. Pri vysokých hodnotách koeficientu gama môžu byť straty v nízkych frekvenciách také veľké, že sa obraz rozpadne na štvorce 8x8. Straty na vysokých frekvenciách sa môžu prejaviť tzv Gibbsov efekt, keď sa okolo obrysov vytvorí akýsi „nimbus“ s ostrým prechodom farby.

Krok 5. Maticu 8x8 prevedieme na 64-prvkový vektor pomocou "cik-cak" skenovania, teda zoberieme prvky s indexmi (0,0), (0,1), (1,0), (2,0 )...

Na začiatku vektora teda dostaneme koeficienty matice zodpovedajúce nízkym frekvenciám a na konci - vysokým.

Krok 6 Vektor konvolujeme pomocou algoritmu skupinového kódovania. V tomto prípade dostaneme dvojice typu<пропустить, число>, kde "preskočiť" je počet núl, ktoré sa majú preskočiť, a "číslo" je hodnota, ktorá sa má vložiť do ďalšej bunky. Takže vektor 42 3000-2 00001 ... bude zložený do párov (0,42) (0,3) (3,-2) (4,1)....

Krok 7. Výsledné dvojice poskladajte pomocou Huffmanovho kódovania s pevným stolom.

Proces rekonštrukcie obrazu v tomto algoritme je úplne symetrický. Metóda vám umožňuje komprimovať niektoré obrázky 10-15 krát bez vážnych strát.

Významné pozitívne aspekty algoritmu sú:

■ je nastavený stupeň kompresie;

■ Výstupný farebný obrázok môže mať 24 bitov na bod.

Nevýhody algoritmu sú tieto:

■ Zvýšením kompresného pomeru sa obrázok rozdelí na jednotlivé štvorce (8x8). Je to spôsobené tým, že počas kvantovania dochádza pri nízkych frekvenciách k veľkým stratám a nie je možné obnoviť pôvodné dáta.

■ Efekt Gibbs-halo sa objavuje pozdĺž hraníc ostrých farebných prechodov.

Ako už bolo spomenuté, JPEG bol štandardizovaný relatívne nedávno - v roku 1991. Ale aj vtedy existovali algoritmy, ktoré komprimovali silnejšie s menšou stratou kvality. Faktom je, že akcie vývojárov štandardu boli obmedzené silou technológie, ktorá v tom čase existovala. To znamená, že aj na PC musel algoritmus pracovať menej ako minútu na priemernom obrázku a jeho hardvérová implementácia by mala byť relatívne jednoduchá a lacná. Algoritmus musel byť symetrický (čas rozbalenia je približne rovnaký ako čas archivácie).

Splnenie poslednej požiadavky umožnilo objavenie sa zariadení ako sú digitálne fotoaparáty, ktoré snímajú 24-bitové fotografie na 8-256 MB flash kartu." Potom sa táto karta vloží do slotu na Vašom notebooku a príslušný program Vám umožní prečítajte si obrázky. Nie je to pravda nya, ak by bol algoritmus asymetrický, bolo by nepríjemné dlho čakať, kým sa zariadenie „dobije“ – skomprimuje obraz.

Nie veľmi pekná vlastnosť JPEG je tiež potom,že často sú horizontálne a vertikálne pruhy na displeji úplne neviditeľné a môžu sa objaviť len pri tlači vo forme moaré vzoru. Vyskytuje sa, keď sa na vodorovné a zvislé pruhy obrázka aplikuje šikmý vzor tlače. Kvôli týmto prekvapeniam JPEG nie je aktívne odporúčané použitie v polygrafickom priemysle, nastavenie vysokých koeficientov kvantizačnej matice. Pri archivácii záberov určených na prezeranie človekom je však v súčasnosti nepostrádateľný.

široký Použitie JPEG bolo dlho brzdené snáď len tým, že pracuje s 24-bitovými obrázkami. Preto, aby bolo možné zobraziť obraz s prijateľnou kvalitou na bežnom monitore v 256-farebnej palete, bolo potrebné použiť vhodné algoritmy, a teda určitý čas. V aplikáciách zameraných na vyberavého používateľa, ako sú hry, sú takéto oneskorenia neprijateľné. Okrem toho, ak máte obrázky, povedzme, v 8-bitovom formáte GIF, skonvertované do 24-bitového JPEG a potom späť na GIF na prezeranie, potom pri oboch prevodoch dôjde k strate kvality dvakrát. Nárast veľkosti archívu je však často taký veľký (3-20 krát) a strata kvality taká malá, že ukladanie obrázkov vo formáte JPEG je veľmi efektívne.

Je potrebné povedať niekoľko slov o modifikáciách tohto algoritmu. Hoci JPEG je štandard ISO, jeho formát súboru nebol opravený. Pomocou toho výrobcovia vytvárajú svoje vlastné nekompatibilné formáty, a preto môžu meniť algoritmus. Takže interné tabuľky algoritmu odporúčaného ISO sú nimi nahradené vlastnými. Navyše je mierny zmätok pri nastavovaní miery straty. Napríklad pri testovaní sa ukázalo, že „výborná“ kvalita, „100 %“ a „10 bodov“ poskytujú výrazne odlišné obrázky. Zároveň, mimochodom, „100 %“ kvalita neznamená bezstratovú kompresiu. Existujú aj varianty JPEG pre špecifické aplikácie.

Ako sa ISO štandard JPEG začína čoraz viac využívať pri výmene obrázkov v počítačových sieťach. Algoritmus JPEG je podporovaný vo formátoch Quick Time, PostScript Level 2, Tiff 6.0 a v súčasnosti zaujíma popredné miesto v multimediálnych systémoch.

Charakteristika algoritmu JPEG: o ! sh. ,. Pomer kompresie: 2-200 (nastavené používateľom). ,c, :_,. . Trieda obrázka: plnofarebné obrázky 2jj.bit alebo iso | Fermentácia v odtieňoch šedej bez ostrých farebných prechodov ^ o &, (fotografie).

Symetria: 1.

Charakteristika: v niektorých prípadoch algoritmus vytvára! halo okolo ostrých horizontálnych a vertikálnych okrajov v obraze (Gibbsov efekt). Navyše s vysokým stupňom kompresie iso-! Obrázok je rozdelený na bloky 8x8 pixelov.

Ak chcete efektívne komprimovať údaje, musíte najprv vyhodnotiť povahu obrázka. JPEG komprimuje obrazové údaje na základe toho, čo vidí ľudské oko. Preto, aby som vám pomohol pochopiť, ako a čo robí JPEG, rád by som vám poskytol všeobecnú predstavu o ľudskom vizuálnom vnímaní.

Kompresia JPEG prebieha v niekoľkých fázach. Cieľom je transformovať grafické dáta takým spôsobom, aby sa irelevantné vizuálne informácie dali ľahko identifikovať a zahodiť. Táto „stratová“ kompresia sa líši od väčšiny ostatných prístupov používaných pri grafických formátoch, ktoré sa snažia zachovať každý kúsok obrazu nedotknutý.

farebný model

Prvým krokom v JPEG je výber vhodného spôsobu reprezentácie farieb. Farby sú zvyčajne špecifikované v 3D súradnicovom systéme. Systém dobre známy väčšine programátorov popisuje farbu ako kombináciu červenej, zelenej a modrej (RGB). Bohužiaľ, z hľadiska kompresie to nie je najlepší spôsob, ako opísať farbu. Problém je, že všetky tri zložky – červená, zelená a modrá – sú rovnocenné. Prechod na iný systém vykresľovania však umožňuje zvýrazniť niektoré dôležitejšie informácie.

Profesionáli používajú dva farebné modely: HSL (Hue-Saturation-Lightness) a HSV (Hue-Saturation-Value). Intuitívne je jasné, že zložka jasu (Lightness) modelu HSL a zložka jasu (Value) modelu HSV každý určuje pomer svetla a tieňa vlastným spôsobom. Sýtosť určuje úroveň "čistej" farby. Desaturované farby sú často neformálne označované ako „špinavé“ (sivé). Odtieň je to, čo vnímame ako farbu objektu, napríklad červenú alebo sivozelenú. Tu je dôležité poznamenať úžasný fakt: ľudské videnie je citlivejšie na zmeny osvetlenia a nie na farbu ako takú!

Rôzne implementácie kompresného algoritmu JPEG používajú rôzne systémy farieb. Systém podania farieb YCbCr používaný formátom JFIF je v mnohom podobný schéme vyvinutej pred mnohými rokmi pre farebnú televíziu.

rednutie

Hlavným dôvodom konverzie z jedného farebného modelu na iný je identifikácia informácií, ktoré sú menej relevantné pre zobrazenie na obrázku. JPEG znižuje množstvo farebných informácií. Kým jasová zložka sa prenáša v plnom rozlíšení, farebná zložka využíva polovičný rozsah hodnôt. V dôsledku tohto jednoduchého kroku sa množstvo dát zníži o tretinu.

Subsampling upravuje farby farebného TV obrazu. Čiernobiele obrázky a farebné informácie sa zvyčajne prenášajú do televízie oddelene. Okrem toho sa informácie o farbe prenášajú v menej prísnej forme ako informácie o jase obrazu.

Diskrétna kosínusová transformácia (DCT)

S každou farebnou zložkou sa zaobchádza oddelene, ako keby nešlo o jednu farbu, ale o tri obrázky v odtieňoch sivej. Ak sa na detailný obrázok pozriete z diaľky, môžete rozoznať iba všeobecný tón obrázka. Napríklad „väčšinou modrá“ alebo „väčšinou červená“. Čím bližšie k obrázku, tým viac detailov môžete vidieť. Na napodobnenie tohto efektu používa JPEG matematický trik nazývaný diskrétna kosínová transformácia (DCT). DCT konvertuje informácie o pixeloch na informácie o zmene pixelov. Prvá vec, ktorú môže DCT poskytnúť, je priemerná farba oblasti. Potom viac a viac rozpracúva detaily.

Rovnako ako v prípade vzdialeného obrázka je priemerná hodnota farby veľmi dôležitou informáciou o ploche obrázka. Vaše oko je menej citlivé na rýchlosť zmeny farby, takže to nie je také dôležité. Transformáciou informácií o farbe týmto spôsobom zvýrazníme informácie, ktoré možno obetovať.

Predpokladá sa, že straty sú spôsobené touto fázou. Ak zakódujete obrázok pomocou DCT a potom ho obnovíte pomocou inverznej funkcie DCT, nezískate presne rovnakú sadu bitov. Táto chyba je však chybou zaokrúhľovania. Vyskytuje sa pri vykonávaní aritmetických operácií a zvyčajne nie je príliš veľký. Preto radšej uvažujem o fáze DCT ako o „väčšinou bezstratovej“ operácii.

Pri veľkých obrázkoch je výpočet DCT a inverzného DCT veľmi časovo náročný proces. Aby sa skrátil čas výpočtu, JPEG rozdelí obrázok na mozaiku s rozmermi 8 x 8 pixelov. Každá z mozaík je spracovaná samostatne, čo výrazne skracuje čas potrebný na výpočet DCT. Problém s týmto prístupom je, že po kvantizácii (o ktorej sa bude diskutovať v ďalšej časti) sa hranice týchto štvorcov nemusia zhodovať, a preto sa stanú viditeľnými, keď je parameter kvality nastavený na nízku hodnotu.

Kvantovanie

Vývojári JPEG sa zaujímali predovšetkým o obrázky vo fotografickej kvalite (fotografický, súvislý tón). Spravidla sa tieto poltónové obrázky vyznačujú jemnými prechodmi z jednej farby do druhej. Pre takéto obrázky je nízkofrekvenčná (pomaly sa meniaca) zložka DCT dôležitejšia ako vysokofrekvenčná (rýchlo sa meniaca) zložka.

Termín kvantizácia jednoducho znamená „zaokrúhľovanie“. JPEG zahodí niektoré grafické informácie zaokrúhlením každého člena DCT s rôznymi váhami na základe rôznych faktorov. Vysokofrekvenčná zložka je zaoblená viac ako nízkofrekvenčná zložka. Napríklad nízkofrekvenčná zložka, v ktorej je uložená priemerná hodnota jasu, môže byť zaokrúhlená na násobok troch, kým vysokofrekvenčná zložka môže byť zaokrúhlená na násobok stovky!

Operácia kvantizácie vysvetľuje, prečo kompresia JPEG v prípade jasných kontúr vedie k tvorbe „chvených“ čiar. Obrysy určuje vysokofrekvenčná (rýchlo sa meniaca) priestorová zložka. (Na prvý pohľad sa môže zdať, že by ste mali mať rozmazaný obrys, ale nezabudnite, že C v DCT znamená kosínus.)

Typicky sú farebné roviny kvantované oveľa hrubšie ako luma roviny. Tu správny výber farebného modelu pomáha identifikovať informácie, ktoré možno vyradiť.

Kompresia

Doteraz, s výnimkou vzorkovacej frekvencie dvoch farebných kanálov, nedošlo k žiadnej kompresii. Všetky vyššie uvedené kroky – transformácia farebného modelu, DCT a kvantizácia – ponechali veľkosť údajov nezmenenú. Nakoniec sa dostávame k poslednému kroku, počas ktorého štandardná technika bezstratovej kompresie skutočne zníži veľkosť dát.

Údaje zoradené v predchádzajúcich krokoch je možné komprimovať efektívnejšie ako surový materiál, ktorým sú grafické údaje RGB. Navyše žiadny z prijatých krokov nebol nadbytočný, každá zmena v údajoch bola zameraná na efektívnejšiu kompresiu finálnej verzie.

Zmena farebného modelu umožnila zredukovať informácie o kanáli a následne ich energickejšie kvantovať.

DCT umožnilo izolovať vysokofrekvenčnú priestorovú zložku. Vysokofrekvenčná zložka má zvyčajne malé hodnoty, čo vedie k neúmernému množstvu malých hodnôt na výstupe kroku DCT, čo uľahčuje proces kompresie.

Počas procesu kvantovania sa väčšina vysokofrekvenčnej zložky nastaví na nulu a zvyšok nadobudne konkrétne hodnoty. Zníženie počtu odlišných hodnôt tiež uľahčuje kompresiu údajov.

Štandard JPEG poskytuje dve rôzne metódy bezstratovej kompresie, ktoré možno použiť v poslednom kroku. Huffmanova kompresia je dobre známy nechránený, ľahko programovateľný algoritmus. Naproti tomu novší algoritmus aritmetického kódovania (aritmetické kódovanie) je predmetom mnohých patentov. (Preto nie je prekvapujúce, že mnohé programy na kompresiu JPEG podporujú iba Huffmanova kompresia.)

Pri dekódovaní obrázkov JPEG musíte vykonať všetky tieto kroky v opačnom poradí. Dátový tok je najprv dekomprimovaný, potom je každý 8-8 blok podrobený inverznej DCT a nakoniec je obraz konvertovaný do vhodného farebného modelu (zvyčajne RGB). Všimnite si, že informácie, ktoré boli zámerne vyradené decimáciou a kvantizáciou, sa nikdy neobnovia. Ak však bolo všetko urobené správne, strata informácií nespôsobí žiadnu viditeľnú degradáciu obrazu.