Algoritmy komprese obrazu. JPEG, JPEG2000, JPEG-LS. Komprese obrazu se ztrátou a bez ztráty

JPEG a JPEG2000"

Dokončeno:

studentská skupina 819

Ugarov Dmitrij

Jak fungují algoritmy JPEG a JPEG2000

1. Algoritmus JPEG

JPEG (anglicky Joint Photographic Experts Group – společná skupina odborníků v oblasti fotografie) – je široce používaná metoda pro kompresi fotografických obrázků. Formát souboru, který obsahuje komprimovaná data, se obvykle také nazývá název JPEG; nejběžnější přípony takových souborů jsou .jpeg, .jfif, .jpg, .JPG nebo .JPE. Nicméně, .jpg je nejoblíbenější rozšíření na všech platformách.

Algoritmus JPEG je kompresní algoritmus se ztrátou kvality.

Oblast použití

Formát je ztrátový kompresní formát, takže je nesprávné předpokládat, že JPEG ukládá data jako 8 bitů na kanál (24 bitů na pixel). Na druhou stranu, protože data komprimovaná a dekomprimovaná JPEG mají obvykle 8 bitů na kanál, tato terminologie se někdy používá. Podporována je také komprese černobílých obrázků ve stupních šedi.

Při ukládání souboru JPEG můžete určit stupeň kvality, a tedy i stupeň komprese, který se obvykle nastavuje v nějakých libovolných jednotkách, například od 1 do 100 nebo od 1 do 10. Větší číslo odpovídá lepší kvalitě , ale zvětší se velikost souboru. Obvykle není rozdíl v kvalitě mezi 90 a 100 okem prakticky vnímán. Je třeba si uvědomit, že bit po bitu obnovený obraz se vždy liší od originálu. Obvyklá mylná představa je, že kvalita JPEG se rovná množství uložených informací.

Etapy kódování

Proces komprese JPEG zahrnuje několik kroků:

1. Převod obrazu do optimálního barevného prostoru;

Při použití barevného prostoru luma/chrominance (YCbCr) je dosaženo lepšího kompresního poměru. Na tuto fázi kódování pomocí vhodných poměrů se barevný model RGB převede 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.
Během dekódování lze použít vhodnou inverzní transformaci:
R = Y + 1,402 x Cr

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

B = Y + 1,772 x Cb.
Poznámka týkající se Y,Cb,Cr v lidském zrakovém systému:

Oko, zejména sítnice, má dva typy buněk jako vizuální analyzátory: buňky pro noční vidění, které vnímají pouze odstíny šedé (od jasně bílé po tmavě černou) a buňky pro denní vidění, které vnímají barevný odstín. První buňky poskytující barvu RGB detekují úroveň jasu podobnou hodnotě Y. Ostatní buňky zodpovědné za vnímání barevného odstínu určují hodnotu spojenou s rozdílem barev.

Velká část vizuální informace, na kterou je lidské oko nejcitlivější, se skládá z vysokofrekvenčních složek jasu ve stupních šedi (Y) barevného prostoru YCbCr. Další dvě složky chromatičnosti (Cb a Cr) obsahují vysokofrekvenční barevné informace, na které je lidské oko méně citlivé. Proto může být určitá jeho část vyřazena a tím je možné snížit počet uvažovaných pixelů pro barevné kanály.

1) zadejte 4:2:0 (když je obrázek rozdělen na čtverce 2x2 pixely a v každém z nich všechny pixely obdrží stejné hodnoty kanály Cb a Cr a jas Y y zůstává pro každý z nich)

2) typ 4:2:2 (sjednocení podle složek barevnosti se vyskytuje pouze horizontálně ve skupinách po dvou pixelech).

3) Typ 4:4:4 znamená, že každý pixel v každém řádku má svou vlastní jedinečnou hodnotu složek Y, Cb a Cr. (obr. 1 a)

4) typ 4:2:2. Podvzorkováním barvonosného signálu faktorem 2 horizontálně získáme proud YCbCr 4:2:2 z proudu YCbCr 4:4:4. Zápis „4:2:2“ znamená, že v jednom řádku jsou 4 hodnoty jasu na 2 hodnoty barvonosnosti (viz obr. 1b). Signál 4:2:2 YCbCr ztrácí na kvalitě obrazu oproti signálu 4:4:4 YCbCr jen velmi málo, ale požadovaná šířka pásma je snížena o 33 % původního signálu.

3. Použití diskrétních kosinusových transformací pro snížení redundance obrazových dat;

Hlavní fází algoritmu je diskrétní kosinová transformace (DCT nebo DCT), což je druh Fourierovy transformace. Používá se při práci s obrázky pro různé účely, nejen za účelem komprese. Přechod na frekvenční reprezentaci hodnot pixelů nám umožňuje jiný pohled na obrázek, jeho zpracování, a co je pro nás zajímavé, komprimaci. Navíc se znalostí převodních koeficientů můžeme vždy provést opačnou akci - vrátit původní obrázek.

DCT přímo aplikované na blok (v našem případě 8x8 pixelů) obrázku by vypadalo takto:

kde x, y - prostorové souřadnice pixelu (0..7) ,

f(x,y) - hodnoty pixelů původního makrobloku (řekněme jas)

u,v - souřadnice pixelů ve frekvenčním vyjádření (0..7)

w(u) =1/SQRT(2) pro u=0, jinak w(u)=1 (SQRT je druhá odmocnina)

w(v) =1/SQRT(2) pro v=0, jinak w(v)=1

Nebo v maticové podobě:

4. Kvantování každého bloku DCT koeficientů pomocí váhových funkcí optimalizovaných pro lidské zrakové vnímání;

Diskrétní kosinová transformace připravuje informace pro ztrátovou kompresi a zaokrouhlování. Pro každý prvek transformované matice existuje odpovídající prvek matice kvantování. Výsledná matice se získá vydělením každého prvku transformované matice odpovídajícím prvkem kvantizační matice a následným zaokrouhlením výsledku na nejbližší celé číslo. Při sestavování kvantizační matice jsou její velké prvky v levém dolním rohu, takže při jejich dělení jsou data v tomto rohu po diskrétní kosinové transformaci (právě ta, která zaokrouhlují méně bolestivá) zaokrouhlena hruběji. Proto jsou pro nás ztracené informace méně důležité než ty zbývající.

Poslední fází kodéru JPEG je kódování výsledné matice.

5.1 Klikatá permutace 64 DCT koeficientů

Takže poté, co jsme provedli DCT transformaci na bloku hodnot 8x8, máme nový blok 8x8. Poté je tento blok 8x8 naskenován cikcakem takto:

(Čísla v bloku 8x8 udávají pořadí, ve kterém se díváme na 2-rozměrnou matici 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

Jak vidíte, nejprve levý horní roh je (0,0), potom hodnota v (0,1), potom (1,0), potom (2,0), (1,1), (0, 2), (0,3), (1,2), (2,1), (3,0) atd.

Poté, co jsme kliknuli matici 8x8, máme nyní vektor s 64 koeficienty (0..63). Pointou tohoto klikatého vektoru je, že se díváme na 8x8 DCT koeficienty ve vzestupném pořadí prostorových frekvencí. Dostaneme tedy vektor seřazený podle prostorových frekvenčních kritérií: první hodnota na vektoru (index 0) odpovídá nejnižší frekvenci v obrázku – označuje se termínem DC. Jak se index na vektoru zvyšuje, dostáváme hodnoty odpovídající vyšším frekvencím (hodnota s indexem 63 odpovídá amplitudě nejvyšší frekvence v bloku 8x8). Zbytek DCT koeficientů je označen AC.

5.2 RunLength kódování nul (RLE)

Nyní máme vektor s dlouhou posloupností nul. Toho můžeme využít zakódováním po sobě jdoucích nul. DŮLEŽITÉ: Později uvidíte proč, ale zde přeskočíme kódování prvního koeficientu vektoru (DC koeficient), který je zakódován jinak. Zvažte původní vektor 64 jako vektor 63 (toto je vektor 64 bez prvního koeficientu)

Řekněme, že máme 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, pouze 0,... 0.0

Tady - jako RLC komprese jpeg provedeno pro tento příklad:

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

Jak vidíte, pro každou hodnotu jinou než 0 zakódujeme počet po sobě jdoucích PRIOR 0s před hodnotou, pak hodnotu přidáme. Další poznámka: EOB je zkratka pro konec bloku a je to speciální kódovaná hodnota (značka). Pokud jsme dosáhli pozice na vektoru, od které máme do konce vektoru jen nuly, přidělíme tuto pozici EOB a ukončíme RLC kompresi kvantovaného vektoru.

[Všimněte si, že pokud je kvantovaný vektor nenulově ukončený (má poslední prvek jiný než 0), nebudeme mít značku EOB.]

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

Další ZÁKLADNÍ věc: Řekněme někde na kvantovaném vektoru, který máme:

57, osmnáct nul, 3, 0,0, 0,0 2, třicet tři nul, 895, EOB

Kódování JPG Huffman omezuje, že počet úvodních nul musí být zakódován jako 4bitová hodnota – nesmí překročit 15.

Takže předchozí příklad by měl být kódován jako:

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

(15,0) je speciální kódovaná hodnota, která označuje to, co následuje za 16 po sobě jdoucími nulami.

5.3 Poslední krok - Huffmanovo kódování

Nejprve DŮLEŽITÁ poznámka: Namísto ukládání skutečné hodnoty specifikuje standard JPEG, že ukládáme minimální velikost v bitech, ve kterých můžeme danou hodnotu uchovávat (toto se nazývá kategorie této hodnoty) a poté bitově zakódovanou reprezentaci této hodnoty. hodnota 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ásledně pro předchozí příklad:

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

zakódujme pouze správnou hodnotu těchto párů, kromě párů, které jsou speciálními značkami jako (0,0) nebo (pokud musíme mít) (15,0)

45, podobně by bylo zakódováno jako (6.101101)

30 -> (5,00001)

A nyní znovu napíšeme řetězec dvojic:

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

Dvojice 2 hodnot uzavřených v závorkách mohou být reprezentovány v byte, protože ve skutečnosti může být každá ze 2 hodnot reprezentována ve 4bitovém bloku (počet nuly na začátku je vždy menší než 15 a stejně jako kategorie [čísla zakódovaná v JPG soubor- v oblasti -32767..32767]). V tomto bajtu představuje horní bit počet úvodních nul a nízký bit představuje kategorii nové hodnoty jiné než 0.

Posledním krokem kódování je Huffman zakódovat tento bajt a poté zapsat do souboru JPG jako bitový proud Huffmanův kód tohoto bajtu, následovaný bitovou reprezentací tohoto čísla.

Například pro bajt 6 (ekvivalent (0.6)) máme Huffmanův kód = 111000;

21 = (1,5) - 11111110110

4 = (0,4) - 1011

33 = (2,1) - 11011

0 = EOB= (0,0) - 1010

Konečný bitový tok zapsaný v souboru JPG na disk pro předchozí příklad je 63 koeficientů (nezapomeňte, že jsme vynechali první koeficient) -

111000 111001 111000 101101 1111111110011001 10111 11111110110 00001

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

Mezi nevýhody formátu patří skutečnost, že při silných kompresních poměrech se projevuje bloková datová struktura, obraz je „rozdělen na čtverce“ (každý o velikosti 8x8 pixelů). Tento efekt je zvláště patrný v oblastech s nízkou prostorovou frekvencí (hladké přechody obrazu, jako je jasná obloha). V oblastech s vysokou prostorovou frekvencí (například kontrastní okraje obrazu) se objevují charakteristické „artefakty“ – nepravidelná struktura pixelů zkreslené barvy a/nebo jasu. Z obrazu navíc mizí drobné barevné detaily. Nezapomeňte také, že tento formát nepodporuje průhlednost.

Navzdory svým nedostatkům se však JPEG velmi rozšířil díky vysokému kompresnímu poměru ve srovnání s alternativami existujícími v době jeho představení.

2. Algoritmus JPEG2000

Algoritmus JPEG-2000 byl vyvinut stejnou skupinou fotografických expertů jako JPEG. Vytvoření JPEG jako mezinárodního standardu bylo dokončeno v roce 1992. V roce 1997 se ukázalo, že je zapotřebí nový, flexibilnější a výkonnější standard, který byl dokončen v zimě roku 2000.

Hlavní rozdíly mezi algoritmem v JPEG 2000 a algoritmem v JPEG jsou následující:

1) Lepší kvalita obrazu se silným kompresním poměrem. Nebo, co je stejné, velký kompresní poměr se stejnou kvalitou pro vysoké kompresní poměry. Ve skutečnosti to znamená znatelné zmenšení velikosti grafiky „webové kvality“, kterou používá většina webů.

2) Podpora kódování jedné oblasti s lepší kvalitou. Je známo, že určité oblasti obrazu jsou kritické pro lidské vnímání (například oči na fotografii), zatímco kvalita jiných může být obětována (například pozadí). Při „ruční“ optimalizaci se zvýšení kompresního poměru provádí, dokud se kvalita v některé důležité části obrazu neztratí. Nyní je možné nastavit kvalitu v kritických oblastech a zbylé oblasti stlačit silněji, tzn. získáme ještě vyšší výsledný kompresní poměr se subjektivně stejnou kvalitou obrazu.

3)Hlavní kompresní algoritmus byl nahrazen waveletem. Kromě výše uvedeného zvýšení kompresního poměru to eliminovalo 8-pixelovou blokaci, ke které dochází při zvýšení kompresního poměru. Kromě toho je nyní plynulý vývoj obrazu již ze své podstaty standardní (Progresivní JPEG, aktivně používaný na internetu, se objevil mnohem později než JPEG).

4) Ke zvýšení kompresního poměru používá algoritmus aritmetickou kompresi. Standard JPEG původně zahrnoval i aritmetickou kompresi, ale ta byla později nahrazena méně účinnou Huffmanovou kompresí, protože aritmetická komprese byla chráněna patenty. Nyní vypršela platnost hlavního patentu a je zde příležitost algoritmus vylepšit.

5) Podpora bezztrátové komprese. Kromě běžné ztrátové komprese bude nyní nový JPEG podporovat také bezeztrátovou kompresi. Je tak možné použít JPEG pro kompresi lékařských snímků, při tisku, při ukládání textu pro rozpoznání systémy OCR atd.

6)Podpora komprese jednobitových (2barevných) obrázků. Pro ukládání jednobitových obrázků (kresby inkoustem, naskenovaný text atd.) byl dříve široce doporučován formát GIF, protože komprese pomocí DCT je velmi neefektivní pro obrázky s ostrými barevnými přechody. V JPEGu se při komprimaci 1bitový obrázek zmenšil na 8bitový, tzn. zvýšena 8krát, načež byl učiněn pokus o kompresi, často méně než 8krát. Nyní můžeme doporučit JPEG 2000 jako univerzální algoritmus.

7) Transparentnost je podporována na úrovni formátu. Nově bude možné plynule překrývat pozadí při tvorbě WWW stránek nejen v GIF, ale i v JPEG 2000. Navíc je podporován nejen 1 bit průhlednosti (pixel je průhledný / neprůhledný), ale samostatný kanál, což vám umožní nastavit plynulý přechod z neprůhledného obrázku na průhledné pozadí.

Úroveň formátu navíc podporuje zahrnutí informací o autorských právech do obrázku, podporu odolnosti proti bitovým chybám při přenosu a vysílání, můžete si vyžádat externí nástroje (pluginy) pro dekompresi nebo zpracování, můžete zahrnout jeho popis, informace o vyhledávání, atd. .d.

Etapy kódování

Proces komprese podle schématu JPEG2000 zahrnuje několik kroků:

1. Převod obrazu do optimálního barevného prostoru.
V této fázi kódování je barevný model RGB pomocí vhodných poměrů převeden na YUV:

Při dekompresi se použije odpovídající inverzní transformace:

2. Diskrétní vlnková transformace.

Diskrétní vlnková transformace (DWT) může být také dvou typů – pro případ ztrátové komprese a pro bezeztrátovou kompresi.

Tato transformace v jednorozměrném případě je skalárním součinem odpovídajících koeficientů a řetězce hodnot. Ale od mnoho koeficientů je nulových, pak lze přímé a inverzní vlnkové transformace zapsat pomocí následujících vzorců (pro transformaci extrémních prvků čáry se používá její rozšíření o 2 pixely v každém směru, jejichž hodnoty jsou symetrické s hodnoty prvků řádku vzhledem k jeho krajním pixelům):
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. Kvantování koeficientů.

Stejně jako v algoritmu JPEG se kvantizace používá při kódování obrazu ve formátu JPEG2000. Diskrétní vlnková transformace, stejně jako její analog, třídí koeficienty podle frekvence. Ale na rozdíl od JPEG je v novém formátu kvantizační matice stejná pro celý obrázek.

. Stejně jako u JPEG je v novém formátu posledním krokem kompresního algoritmu bezeztrátové kódování. Na rozdíl od předchozího formátu však JPEG2000 používá aritmetický kompresní algoritmus.

Implementace softwaru

V tomto článku jsou implementovány algoritmy JPEG a JPEG2000. Oba algoritmy implementují přímé a zpětné kódování (neexistuje poslední stupeň sekundární komprese). Výpočet JPEG trvá poměrně dlouho (cca 30 sekund) kvůli „přímému“ výpočtu DCT. Pokud potřebujete zvýšit rychlost práce, měli byste nejprve vypočítat matici DCT (provést změny ve třídě DCT).

Pojďme se podívat na program:

1. 
   Po spuštění se objeví okno kde

Po:

Starý dobrý JPEG má i přes spoustu nepopiratelných výhod stále značná omezení. K jejich odstranění byla povolána nová metoda komprese obrazu, jejíž vývoj probíhá již delší dobu. Nyní, když se JPEG2000 stal oficiálně uznávaným formátem, by to měl být začátek jeho aktivní podpory ze strany různých výrobců softwaru.

Mnoho lidí pracujících s grafikou na počítači se jistě zajímá o otázku: jak lze obrázek, který zabírá velmi působivé množství v paměti počítače, vtěsnat na disk do mnohem menší velikosti? Pamatuji si, že na úsvitu mé publikační činnosti pro mě bylo slovo „komprese“ tak záhadné a překvapivé... Jak vlastně funguje komprese obrazu – ostatně dnes je nemyslitelné představit si Web, digitální fotografii, popř. barevný tisk bez něj?

Takže komprese. Může a nemusí vést ke ztrátě kvality. Posledním případem jsou metody jako RLE (Run Length Encoding, kódování délek běhů, v důsledku čehož se páry typu ( přeskočit, hodnota, Kde přeskočit je počet po sobě jdoucích nul a hodnota- hodnota za nimi navazující) a LZW (komprese metodou Lempel-Ziff-Welch), implementovaná v r. PSD formáty, GIF a TIFF. Jsou široce používány archivátory, jako jsou RAR a ZIP. Průměrný bezeztrátový kompresní poměr je 2-3krát.

Pokud potřebujete komprimovat obraz silněji, neobejdete se bez ztráty kvality. Jaké jsou zásady? Za prvé, každý obrázek obsahuje určitou redundanci, jejíž odstranění nepovede k výrazné změně kvality obrázku. Za druhé, lidské oko je citlivější na změny jasu než barvy. Proto se pro různé kanály obrazu používají různé kompresní poměry - informace se ztratí, ale není to vizuálně patrné. Citlivost oka na malé obrazové prvky je navíc nízká, což umožňuje jejich odstranění bez snížení kvality. Tímto způsobem můžete komprimovat obrázek (i když je zhoršení kvality již patrné) až na přijatelnou hranici. U každého je stanoven stupeň zhoršení kvality konkrétní případ. Pro tisk jsou přijatelné pouze minimální deformace a pro zveřejnění na internetu (v závislosti na účelu) - mnohem více.

Mezi metodami ztrátové komprese je nejoblíbenější JPEG, který si zachovává dostatečnou kvalitu obrazu i při třicetinásobné kompresi. Mimochodem, ve většině moderních metod komprese dat (například Layer-4, známé jako mp3, stejně jako MPEG) jsou implementovány mechanismy podobné JPEG. Podívejme se na tento formát blíže, zvláště proto, že nedávno byla konečně schválena jeho nejnovější implementace, JPEG2000, která zahrnuje všechny doplňky JPEG/MPEG provedené za deset let jeho vývoje.

JPEG

Název kompresního algoritmu je zkratkou pro Joint Photographic Expert Group, iniciativní skupinu tvořenou odborníky z ITU (International Telecommunication Union) a ISO (International Organization for Standardization). Proto je v jeho názvu přítomna předpona Joint. V roce 1992 byl JPEG prohlášen za mezinárodní standard pro grafiku.

Komprese JPEG vždy ztrácí kvalitu. V tomto případě je vždy na výběr: dát přednost kvalitě na úkor objemu (velikost souboru se zkomprimuje asi třikrát) nebo naopak dosáhnout minimální velikosti obrázku, při které zůstane stále rozpoznatelný ( kompresní poměr může dosáhnout 100). Komprese, kdy rozdíl v kvalitě mezi výsledným obrázkem a originálem stále není patrný, poskytuje 10-20násobné zmenšení velikosti souboru.

Oblast použití

JPEG nejlépe komprimuje plnobarevné a monochromatické obrázky fotografické kvality. Pokud chcete uložit obrázek s indexovou paletou, pak se nejprve převede do plné barvy. Při kompresi pomocí metody JPEG je třeba mít na paměti, že vše závisí na povaze obrázků: ty, kde jsou změny barev nevýznamné a nejsou tam žádné ostré barevné přechody, zaberou mnohem menší objem. JPEG se používá všude tam, kde je potřeba ukládat fotografie: v digitálních fotoaparátech, tisk (EPS DCS 2.0), internet je bez něj nemyslitelný.

Existuje několik druhů komprese JPEG, ale budeme zvažovat pouze dvě z nich, které se používají ve standardním balíčku pro práci s bitmapy Adobe Photoshop, základní linie A progresivní. Další dvě metody – arifmetické a bezztrátové – jsou exotické, z řady důvodů se příliš nepoužívají.

Jak probíhá komprese

1. První etapa spočívá v konvertování barevný model obrazu (obvykle RGB) do modelu, kde jsou jasové a barevné složky odděleny (například YCbCr nebo YUV), což umožňuje optimálně přiblížit výběr úrovní komprese pro každý kanál (s přihlédnutím k vnímání oka). Převod probíhá takto:

Y = 0,299xR+0,587*G+0,114xB Cb = (B-Y)/0,866/2+128 Cr = (R-Y)/0,701/2+128

2. V další fázi, tzv. předfiltrace, ve kterém jsou sousední pixely odděleně v každém z Cb a Cr kanálů seskupeny do párů v horizontálním a vertikálním směru a jasový kanál Y je ponechán beze změny. Poté celá skupina čtyř pixelů obdrží průměrnou hodnotu příslušných složek Cb a Cr. Pro stručnost lze takové schéma označit jako 4:1:1 (stejná forma zobrazení je převzata v DRAW - exportním okně jpeg). Vezmeme-li v úvahu skutečnost, že každý pixel je zakódován do 3 bajtů (256 úrovní pro každý ze tří kanálů), v důsledku toho se množství dat automaticky sníží dvakrát (namísto 12 bajtů pro přenos 4 pixelů je stačí přenést pouze 4+1+1 = 6 bajtů) . Z hlediska matematiky taková transformace vede ke značné ztrátě informací, ale lidské oko ztrátu nevnímá, protože v běžných fotografických obrázcích existuje výrazná redundance.

3. Přijaté informace, které prošly fází primárního „čištění“, jsou opět seskupeny samostatně v každém kanálu do bloků, ale již o velikosti 8x8, po kterých je na ně aplikována hlavní komprese - tzv. diskrétní kosinusová transformace, zkráceně - DCT (diskrétní kosinusová transformace). V důsledku toho informace o distribuci jas pixelu je převeden do jiné formy, kde je popsán rozdělením na základě četnost výskytu jas jednoho nebo druhého pixelu. DCT má řadu výhod oproti jiným transformacím (například Fourierova transformace), které poskytují lepší obnovu informací.

Místo pole 64 hodnot (8x8 pixelů) pro každý blok, který tvoří obrázek, dostaneme pole 64 frekvencí. Zvažte fungování DCT na příkladu. Řekněme, že jas pixelů v jednom bloku našeho obrázku má tvar znázorněný na Obr. 1 vlevo, pak bude výsledek převodu takový, jaký je zobrazen vpravo.

Navzdory značné přesnosti dochází v této fázi k určité ztrátě informací – proto JPEG vždy vede ke ztrátě kvality. Hlavním cílem transformace je zjistit obecný obraz o rozložení velkých (na obrázku vlevo nahoře) a malých (vpravo dole) objektů, který se bude hodit později, při eliminaci nepodstatných informací.

4. Dalším krokem je odstranění informací, které jsou okem stěží postřehnutelné z bloku, popř kvantování(kvantizace). Všechny složky jsou rozděleny do různých koeficientů, které určují význam každé z nich pro kvalitativní obnovu původního obrazu a výsledek zaokrouhleno nahoru na celočíselnou hodnotu. Právě tento postup přináší největší ztrátu kvality a snižuje konečný objem obrazu. Vysokofrekvenční složky jsou kvantovány hrubě a nízkofrekvenční složky jsou kvantovány přesněji, protože jsou nejnápadnější. Aby se poněkud vyrovnal pokles kvality, jsou v jasovém kanálu použity menší dělicí faktory než v barevných kanálech. Ale častěji (to se provádí pro urychlení výpočtů) se místo speciálně vybraných hodnot bere pouze jedna - ta, kterou uživatel zadá při výběru stupně komprese.

Zde je například ukázka toho, jak vypadá okno Photoshopu při ukládání obrázku pomocí operace Uložit pro web, kde je parametr Kvalita (nebo spíše jeho odvozenina) stejný zaokrouhlovací faktor(obr. 2).

V důsledku kvantizace se získá soubor komponent, podle kterých se s danou přesností obnoví původní obraz (obr. 3).

4

Na Obr. 4 ukazuje výsledek obnovy černobílého čtverce s jednou, čtyřmi a patnácti komponentami.

5. Po provedení hlavní práce na kompresi obrazu jsou další transformace redukovány na vedlejší úkoly: zbývající komponenty jít v pořadí tak, že nejprve jsou lokalizováni ti, kteří jsou zodpovědní za velké detaily, a poté za všechny ty menší. Když se podíváte na obrázek, pohyb kodéru vypadá jako klikatá čára. Stupeň se nazývá ZigZag (obr. 5).

5

Poté je výsledná sekvence komprimována: nejprve obvyklým RLE, poté Huffmanovou metodou.

6. A nakonec čisté technická etapa- data jsou uzavřena v shellu, dodávaném s hlavičkou, která uvádí všechny parametry komprese, aby bylo možné obraz obnovit. Někdy však tyto informace nejsou zahrnuty v hlavičkách, což poskytuje další zisk v kompresi, ale v tomto případě si musíte být jisti, že aplikace, která bude soubor číst, o nich ví.

Zde obecně a všechny transformace. Nyní spočítejme, jak velké komprese bylo dosaženo v našem příkladu. Získali jsme 7 hodnot, které obnoví původní obrázek 8x8. Takže komprese z aplikace DCT konverze v obou barevných kanálech byla 8x8/7 9krát. Jasovému kanálu přiřaďme ne sedm, ale 11 koeficientů, což dá 8x8/11 6. Pro všechny tři kanály dostáváme (9+9+6)/3=8 krát. Snížení kvality během „decimace“ obrazu, ke kterému došlo ve druhé fázi, poskytuje další dvojnásobné zvýšení (schéma 4-1-1, s přihlédnutím k vlastnostem kódování složky jasu), což poskytne konečný výsledek - 16krát. Jedná se o hrubý odhad, který nezohledňuje některé aspekty, ale odráží skutečný obraz. Chcete-li dosáhnout třicetinásobného snížení velikosti souboru, musíte ponechat pouze 3-4 komponenty.

Proces rekonstrukce obrazu probíhá v opačném pořadí: nejprve se složky vynásobí hodnotami z kvantizační tabulky a získají se přibližné koeficienty pro inverzní kosinusovou transformaci. Čím lepší kvalita je zvolena při kompresi, tím vyšší je stupeň přiblížení k původním koeficientům, což znamená, že obraz bude obnoven přesněji. Zbývá přidat pouze jednu akci: před koncem proveďte nějaké úpravy (šum) na hraničních pixelech ze sousedních bloků, abyste odstranili ostré rozdíly mezi nimi.

Nevýhody JPEG

1. Nemožnost dosažení vysokých kompresních poměrů kvůli omezení velikosti bloku (pouze 8x8).
2. Bloková struktura při vysokém kompresním poměru.
3. Zaoblení ostrých rohů a rozmazání tenkých prvků na obrázku.
4. Podporovány jsou pouze obrázky RGB (JPEG lze použít pouze pro obrázky CMYK ve formátu EPS prostřednictvím DCS).
5. Obrázek nelze zobrazit, dokud se plně nenačte.

Od schválení JPEG jako standardu uplynulo deset let. Během této doby výzkumné skupiny navrhly řadu významných dodatků k původní verzi, které vyústily na konci loňského roku ke vzniku nového standardu.

JPEG2000

Od roku 1997 začaly práce zaměřené na vytvoření univerzálního kódovacího systému, který by odstranil všechna omezení uložená JPEG a dokázal by efektivně pracovat se všemi typy obrázků: černobílými, ve stupních šedi, plnobarevnými a vícesložkovými a bez ohledu na obsah (ať už fotografie, poměrně malý text nebo dokonce kresby). Spolu s mezinárodními standardizačními organizacemi se na jeho vývoji podíleli takoví průmysloví giganti jako Agfa, Canon, Fujifilm, Hewlett-Packard, Kodak, LuraTech, Motorola, Ricoh, Sony a další.

Protože nový algoritmus tvrdil, že je univerzální, měl navíc za úkol používat různé způsoby přenosu dat (v skutečný režimčas a s úzkou šířkou pásma), což je zvláště důležité v multimediálních aplikacích, například v reálném vysílání přes internet.

Základní požadavky na formát JPEG2000:

1. Dosažení vyššího stupně komprese ve srovnání s JPEG.
2. Podpora monochromatických obrázků, což umožní jeho použití ke kompresi obrázků s textem.
3. Možnost bezztrátové komprese.
4. Výstup obrázků s postupným zlepšováním detailů (jako u progresivního GIFu).
5. Použití prioritních oblastí v obrázku, pro které lze nastavit vyšší kvalitu než u zbytku obrázku.
6. Dekódování v reálném čase (bez zpoždění).

Princip komprese

Jako hlavní kompresní mechanismus v JPEG2000 se na rozdíl od JPEG používá wave (wavelet) transformace - systém filtrů aplikovaných na celý obraz. Aniž bychom zacházeli do detailů komprese, zaznamenáme pouze hlavní body.

6

Nejvíce jich má například snímek získaný po filtrování dolní propusti po řádcích a řádcích (vlevo nahoře). velké množství informace a přijaté po vysokofrekvenční - minimum. Informační obsah obrázků získaný po dolní propusti řádků a vysokofrekvenčním filtrování pro sloupce (a naopak) je průměrný. Nejinformativnější obrázek je znovu filtrován a výsledné složky, jako u komprese jpeg, jsou kvantovány. To se děje několikrát: u bezztrátové komprese se smyčka obvykle opakuje 3x se ztrátami - 10 iterací je považováno za rozumný kompromis mezi velikostí, kvalitou a rychlostí dekomprese. Výsledkem je jeden malý obrázek a sada obrázků s malými detaily, které postupně a s určitou přesností obnovují do normální velikosti. Je zřejmé, že největšího stupně komprese je dosaženo u velkých obrázků, protože lze nastavit více cyklů.

Praktické provedení

Od doby, kdy byly položeny základy komprese JPEG2000, řada společností vyvinula poměrně účinné algoritmy pro její implementaci.

Z významných softwarových vývojářů lze zaznamenat Corel (mimochodem jako jeden z prvních zavedl do svých balíčků podporu formátu wi založeného na vlnových transformacích, za což je čest a chvála) - všechny obrázky dodávané na CD s balíčkem CorelDRAW až do deváté verze byly tímto způsobem komprimovány.

Později k tomu přistoupilo i Adobe. Některé z myšlenek JPEG2000 byly aplikovány vývojáři Photoshopu 6 ve formě pokročilých možností při ukládání obrázku jako JPEG (běžný, založený na kosinové transformaci). Mezi nimi je progresivní JPEG (volba Progresivní v okně Uložit pro web). Tento algoritmus je určen především pro systémy reálného času a funguje úplně stejně jako progresivní GIF. Nejprve se objeví hrubá kopie obrázku skládající se pouze z několika bloků. velká velikost a postupem času, když je načten zbytek dat, se struktura začíná prohlížet stále jasněji, až se nakonec úplně obnoví konečný obrázek. Na rozdíl od GIF tento algoritmus vytváří těžký náklad na prohlížeč, protože bude muset dokončit celý cyklus konverze pro každou přenášenou verzi.

Mezi další doplňky si všimneme zahrnutí několika obrázků komprimovaných JPEG do souboru s různými stupni komprese, rozlišením a dokonce i barevnými modely. V souladu s tím bylo ve Photoshopu 6 možné vybrat jednotlivé oblasti v obraze a použít na ně různá nastavení komprese ( Oblast zájmu, poprvé byl takový mechanismus navržen již v roce 1995 s použitím nižších hodnot v kvantizační tabulce. K tomu se nastaví požadovaná oblast (například ve formě nového kanálu v obrázku) a stiskne se ikona masky u položky Kvalita. V okně, které se objeví, můžete s obrázkem experimentovat pohybem posuvníků – hotový výsledek se zobrazí na obrazovce, což vám umožní rychle najít potřebný kompromis mezi kvalitou a velikostí.

Specializované převodníky a prohlížeče

Vzhledem k tomu, že standard nespecifikuje konkrétní implementace kompresních/dekompresních metod, ponechává prostor pro vývojáře kompresních algoritmů třetích stran. Ve skutečnosti můžete buď použít zjednodušený algoritmus tvaru vlny a tím urychlit proces komprese, nebo naopak použít složitější algoritmus, a tedy vyžadovat velké systémové prostředky.

Specializovaná řešení od jiných společností jsou k dispozici jako komerční vývoj. Některé jsou implementovány jako samostatné programy (JPEG 2000 vyvinutý společností Aware), jiné jako přídavné moduly pro nejběžnější rastrové editory (ImagePress JPEG2000 vyvinutý společností Pegasus Imaging a modul LEAD JPEG2000 od společnosti LEAD Technologies). Na jejich pozadí vyniká společnost LuraTech, která se touto problematikou dlouhodobě zabývá. Svou technologii LuraWave propaguje v samostatném produktu LuraWave SmartCompress (nyní je k dispozici 3. verze) a nabízí moduly pro Photoshop, Paintshop, Photopaint. Výrazná vlastnost- vyšší rychlost (téměř okamžitá konverze) i u obrázků o velikosti několika megabajtů. V souladu s tím je cena tohoto modulu nejvyšší - 79 $.

Pro prohlížení obrázků JPEG2000 v prohlížečích je potřeba nainstalovat speciální modul prohlížeče (všichni vývojáři jej nabízejí zdarma). Vložení obrázku do html dokumentu, jako každý zásuvný modul, spočívá v použití konstrukce EMBED (s další možnosti). Například to znamená, že bude použita metoda progresivního přenosu obrazu. To znamená, že v našem příkladu (soubor 139 KB) se nejprve přenese pouze 250 bajtů, na základě kterých se sestaví hrubý obrázek, poté se po načtení 500 bajtů obrázek aktualizuje (to pokračuje, dokud není hodnota LIMIT dosaženo).

Pokud chcete získat lepší obrázek, je třeba vybrat položku Improve z nabídky, která se objeví na pravém tlačítku (obr. 9). U čtyř životopisů se stáhne celý obrázek.

9

závěry

JPEG2000 tedy objektivně ukazuje nejlepší skóre než JPEG pouze při vysokých kompresních poměrech. Při stlačení 10-20krát není velký rozdíl. Bude schopen nahradit nebo jednoduše konkurovat rozšířenému formátu? V blízké budoucnosti - stěží, ve většině případů je poměr kvalita / velikost poskytovaný JPEG docela přijatelný. A oněch 10–20 % dodatečné komprese, kterou JPEG2000 poskytuje s vizuálně stejnou kvalitou, pravděpodobně nepovede ke zvýšení jeho popularity.

Na druhou stranu společnosti zabývající se digitálními fotoaparáty projevují o nový formát velký zájem, protože velikost fotosenzitivních matric každým rokem neustále roste a ukládat snímky do paměti je stále obtížnější. A pak se nový formát rozšíří a kdo ví, třeba po nějaké době JPEG2000 dohoní JPEG. Analog Micro Devices každopádně nedávno vydala specializovaný čip, ve kterém je na hardwarové úrovni implementována komprese/dekomprese pomocí nové technologie a americké ministerstvo obrany již aktivně používá nový formát pro záznam fotografií přijatých ze špionážních satelitů.

Fakta a dohady

1. JPEG ztrácí kvalitu při otevírání a opětovném ukládání souboru.

Není pravda. Kvalita se ztratí pouze v případě, že je zvolen kompresní poměr nižší než ten, ve kterém byl obrázek uložen.

2. JPEG ztrácí kvalitu při úpravách souboru.

Je to pravda. Když uložíte upravený soubor, všechny převody se provedou znovu – vyhněte se proto časté úpravě obrázků. To platí pouze při zavření souboru, pokud soubor zůstane otevřený, není důvod k obavám.

3. Výsledek komprese se stejnými parametry v různých programech bude stejný.

Není pravda. Různé programy interpretují uživatelem zadané hodnoty různými způsoby. Například v jednom programu je indikována kvalita uloženého obrázku (jako např. ve Photoshopu), v druhém pak míra jeho komprese (reciproční).

4. Při nastavení na maximální kvalitu se snímek uloží bez ztráty kvality.

Není pravda. JPEG komprimuje vždy se ztrátami. Ale nastavení například 90% kvality místo 100% má za následek zmenšení velikosti souboru větší, než je ztráta kvality vnímaná okem.

5. Jakýkoli soubor JPEG lze otevřít v libovolném editoru, který rozumí formátu JPEG.

Není pravda. Progresivní JPEG je varianta JPEG, které někteří editoři nerozumí.

6. JPEG nepodporuje průhlednost.

Je to pravda. Někdy se může zdát, že některá část obrázku je průhledná, ale ve skutečnosti je její barva jednoduše zvolena tak, aby odpovídala barvě pozadí na html stránce.

7. JPEG komprimuje lépe než GIF.

Není pravda. Mají různé oblasti použití. Obecně platí, že typický "gif" obrázek po převodu do JPEG bude mít větší objem.

JPEG2000 vs. JPEG

2. S vyšší kompresí je kvalita JPEG2000 výrazně vyšší než kvalita JPEG, což umožňuje komprimovat bez velkých ztrát až 50krát a s určitými ztrátami (mluvíme o obrázcích pro internet) - až 100 a dokonce až na 200.

3. S vysokými kompresními poměry v oblastech, kde dochází k hladké změně barev, obraz nezíská blokovou strukturu charakteristickou pro jednoduchý JPEG. JPEG2000 také poněkud rozmazává a zaobluje ostré hrany - viz fotografie (obr. 7 a 8).

Zobrazuje výsledky komprese testovacího souboru s různými kompresními poměry (vlevo - uloženo ve Photoshopu ve formátu JPG, vpravo - ve formátu JPEG2000). Pro obrázek na Obr. Bylo zvoleno 7 úrovní komprese 20, 40, 70 a 145 (lze je explicitně specifikovat při ukládání do JPEG2000), kompresní poměr JPG byl zvolen tak, aby velikost souboru byla stejná jako po kompresi JPEG2000. Jak se říká, výsledky jsou tu. Pro názornost byl proveden druhý experiment na snímku s ostřejšími detaily (s úrovněmi komprese 10, 20, 40 a 80). Výhoda je opět na straně JPEG2000 (obr. 8).

8

4. Protože ve skutečnosti jsou kopie s různým rozlišením uloženy v jednom souboru JPEG2000

Pro ty, kteří vytvářejí galerie obrázků na internetu, tedy není potřeba vytvářet pro ně náhledy.

5. Zvláště zajímavá je komprese bez zkreslení (bezztrátový režim). Takže testovací soubor s kompresí LZW z Photoshopu zabral 827 KB a komprimovaný JPEG2000 - 473 KB.

6. Ve srovnání s JPEG spotřebovává jeho pokročilejší jmenovec výrazně více systémových prostředků. Ale výkon počítačů, který se za posledních pár let výrazně zvýšil, umožňuje úspěšně řešit problémy komprese obrazu novou metodou.

7. Nedostatek podpory JPEG2000 v prohlížečích. Pro zobrazení takových obrázků je potřeba stáhnout si poměrně velký doplněk (1,2 MB).

8. Nedostatek bezplatného softwaru pro ukládání obrázků v novém formátu.

Časopisy ve veřejné doméně.

Na stejné téma:

Oblast použití

Formát je ztrátový kompresní formát, takže je nesprávné předpokládat, že JPEG ukládá data jako 8 bitů na kanál (24 bitů na pixel). Na druhou stranu, protože data komprimovaná a dekomprimovaná JPEG jsou obvykle reprezentována v 8 bitech na kanál, tato terminologie se někdy používá. Podporována je také komprese černobílých obrázků ve stupních šedi.

Při ukládání souboru JPEG můžete určit stupeň kvality, a tedy i stupeň komprese, který se obvykle nastavuje v nějakých libovolných jednotkách, například od 1 do 100 nebo od 1 do 10. Větší číslo odpovídá lepší kvalitě , ale zvětší se velikost souboru. Obvykle není rozdíl v kvalitě mezi 90 a 100 okem prakticky vnímán. Je třeba si uvědomit, že obraz obnovený z formátu JPEG není přesnou kopií originálu. Obvyklá mylná představa je, že kvalita JPEG se rovná množství uložených informací.

Široká podpora formátu JPEG ze strany různých softwarů často vede ke kódování JPEG obrázků, které k tomu nejsou určeny – bez zvýšení kompresního poměru ve srovnání se správně vytvořeným PNG nebo GIF, ale s neblahými důsledky pro kvalitu. Například pokus zaznamenat do JPEG obrázek obsahující malé kontrastní detaily (zejména barevné) povede k výskytu charakteristických, dobře značených artefaktů i při vysokém „stupni kvality“.

Komprese

Při komprimaci je obraz převeden z barevného prostoru RGB do YCbCr (YUV). Je třeba poznamenat, že standard JPEG (ISO / IEC 10918-1) nijak neupravuje volbu YCbCr, umožňuje jiné typy transformace (například s jiným počtem složek než tři) a kompresi bez konverze (přímo na RGB), nicméně specifikace JFIF (JPEG File Interchange Format, navržená v roce 1991 společností C-Cube Microsystems a nyní de facto standard) zahrnuje použití konverze RGB->YCbCr.

Po konverzi RGB->YCbCr lze pro obrazové kanály Cb a Cr zodpovědné za barvu provést "decimaci" (podvzorkování), což znamená, že každému bloku 4 pixelů (2x2) jasového kanálu Y jsou přiřazeny průměrné hodnoty. ​​​​Cb a Cr (schéma ztenčování "4:2:0". V tomto případě je pro každý blok 2x2 místo 12 hodnot (4 Y, 4 Cb a 4 Cr) použito pouze 6 (4 Y a po jednom zprůměrovaném Cb a Cr). Pokud jsou na kvalitu obnoveného obrazu po kompresi obrazu kladeny zvýšené požadavky, lze ztenčení provádět pouze v jednom směru – vertikálně (schéma „4:4:0“) nebo horizontálně („4: 2:2") nebo se neprovádí vůbec ("4:4:4").

Norma také umožňuje decimaci s průměrováním Cb a Cr nikoli pro blok 2x2, ale pro čtyři po sobě jdoucí (vertikálně nebo horizontálně) pixely, tedy pro bloky 1x4 nebo 4x1 (schéma "4:1:1"). Je také možné použít různé typy decimace pro Cb a Cr, ale v praxi jsou taková schémata extrémně vzácná.

Dále jsou složka jasu Y a složky zodpovědné za barvu Cb a Cr rozděleny do bloků 8x8 pixelů. Každý takový blok je podroben diskrétní kosinové transformaci (DCT). Výsledné DCT koeficienty jsou kvantovány (pro Y, Cb a Cr se obecně používají různé kvantizační matice) a sbaleny pomocí Huffmanových kódů. Standard JPEG také umožňuje použití mnohem efektivnějšího aritmetického kódování, ale kvůli patentovým omezením (patent na aritmetický QM kodér popsaný ve standardu JPEG patří IBM) se v praxi nepoužívá.

Matice použité pro kvantování DCT koeficientů jsou uloženy v záhlaví souboru JPEG. Obvykle jsou postaveny tak, že vysokofrekvenční koeficienty jsou podrobeny silnější kvantizaci než nízkofrekvenční. To vede k zhrubnutí jemných detailů v obraze. Čím vyšší je kompresní poměr, tím silnější je kvantování všech koeficientů.

Různé schémata komprese JPEG

Standard JPEG poskytuje dva hlavní způsoby reprezentace kódovaných dat.

Nejběžnější, podporovaná většinou dostupných kodeků, je sekvenční (sekvenční JPEG) reprezentace dat, která předpokládá sekvenční procházení zakódovaného obrazu blok po bloku zleva doprava, shora dolů. Výše popsané operace se provádějí na každém zakódovaném obrazovém bloku a výsledky kódování se postupně umístí do výstupního proudu ve formě jediného "skenování" (pole kódovaných dat). Hlavní nebo „základní“ (základní) režim kódování umožňuje pouze takové znázornění. Rozšířený (rozšířený) režim spolu se sekvenčním umožňuje také progresivní (progresivní JPEG) reprezentaci dat.

V případě progresivního JPEG jsou komprimovaná data zapsána do výstupního proudu jako sada skenů, z nichž každý popisuje celý obraz ve stále větších detailech. Toho je dosaženo buď tím, že se v každém skenování nezaznamená úplná sada koeficientů DCT, ale pouze některé z nich: první - nízkofrekvenční, v dalších skenech - vysokofrekvenční (metoda spektrálního výběru, tj. spektrální vzorky), nebo postupným , od skenování ke skenování, zpřesňování DCT koeficientů (metoda „postupné aproximace“, tj. postupné aproximace). Tato progresivní reprezentace dat je užitečná zejména při přenosu komprimovaných obrázků pomocí nízkorychlostních komunikačních kanálů, protože umožňuje získat pohled na celý obrázek po přenesení malé části souboru JPEG.

Obě popsaná schémata (jak sekvenční, tak progresivní JPEG) jsou založena na DCT a zásadně neumožňují získat obnovený obraz, který je absolutně totožný s tím původním. Standard však umožňuje i kompresi, která nepoužívá DCT, ale je postavena na bázi lineárního prediktoru (bezeztrátový, tedy „bezeztrátový“, JPEG), který zaručuje úplnou bitovou shodu mezi originálem a obnovené obrázky. Současně kompresní poměr u fotografických obrázků zřídka dosahuje 2, ale v některých případech je zaručená absence zkreslení žádaná. nápadně skvělé stupně kompresi lze získat pomocí kompresní metody JPEG-LS, která i přes podobnost názvů přímo nesouvisí s JPEG ISO/IEC 10918-1 (doporučení ITU T.81) 0,87).

Syntaxe a struktura

Soubor JPEG obsahuje sekvenci značek, z nichž každá začíná bytem 0xFF, který označuje začátek značky, a bytem identifikátoru. Některé značky se skládají pouze z této dvojice bajtů, zatímco jiné obsahují další data, sestávající z dvoubajtového pole o délce informační části značky (včetně délky tohoto pole, ale minus dva bajty začátku značka, tj. 0xFF a identifikátor) ​​a aktuální data.

Pro archivaci snímků byly jako první použity konvenční algoritmy. Ty, které se používaly a používají v zálohovacích systémech, při vytváření distribucí atp. Tyto algoritmy archivovaly informace beze změny. Hlavním trendem v poslední době je však používání nových tříd obrázků. Staré algoritmy již nesplňují požadavky na archivaci. Mnoho obrázků nebylo prakticky komprimováno, i když „na první pohled“ měly zjevnou redundanci. To vedlo k vytvoření nového typu algoritmů - komprese se ztrátou informace. Zpravidla lze nastavit poměr archivace a následně i míru ztráty kvality v nich. V tomto případě je dosaženo kompromisu mezi velikostí a kvalitou snímků.

Jedním z vážných problémů počítačové grafiky je, že dosud nebylo nalezeno adekvátní kritérium pro posouzení ztráty kvality obrazu. A neustále se ztrácí – při digitalizaci, při převodu na omezenou paletu barev, při převodu na jiný systém barevného znázornění pro tisk a, což je pro nás obzvlášť důležité, při archivaci se ztrátami. Můžete uvést příklad jednoduché kritérium: standardní odchylka hodnot pixelů (L 2 měření nebo odmocnina - RMS):

Podle ní se obraz velmi poškodí, když se jas sníží jen o 5 % (oko to nepostřehne – nastavení jasu se u různých monitorů liší mnohem více). Přitom snímky se „sněhem“ – ostrá změna barvy jednotlivých bodů, slabé proužky nebo „moaré“ budou rozpoznány jako „téměř nezměněné“ (Vysvětlete proč?). Další kritéria mají také své nevýhody.

Zvažte například maximální odchylku:

Toto měření, jak asi tušíte, je extrémně citlivé na bití jednotlivých pixelů. Tito. v celém snímku se může výrazně změnit pouze hodnota jednoho pixelu (což je okem téměř nepostřehnutelné), nicméně podle tohoto opatření bude obraz silně poškozen.

V praxi používaná míra se nazývá míra odstupu signálu od šumu (peak-to-peak signal-to-noise ratio - PSNR).

Tato míra je ve skutečnosti podobná standardní odchylce, ale její použití je poněkud pohodlnější kvůli logaritmické škále stupnice. Má stejné nevýhody jako směrodatná odchylka.

Ztrátu kvality obrazu nejlépe posoudí naše oči. Za vynikající je považována archivace, při které nelze pouhým okem rozlišit původní a rozbalené snímky. Dobré – když poznáte, který z obrázků byl archivován, můžete porovnat pouze dva sousední obrázky. S dalším zvýšením kompresního poměru se zpravidla projeví vedlejší účinky charakteristické pro tento algoritmus. V praxi lze i při vynikajícím zachování kvality provádět pravidelné specifické změny obrazu. Ztrátové archivační algoritmy se proto nedoporučují pro kompresi obrázků, které budou následně vytištěny z vysoká kvalita nebo zpracovány programy pro rozpoznávání obrázků. Nepříjemné efekty u takových obrázků, jak jsme si již řekli, mohou nastat i při jednoduchém zmenšení obrázku. Algoritmus JPEG

JPEG je jeden z nejnovějších a poměrně výkonných algoritmů. Je to prakticky de facto standard pro plnobarevné obrázky. Algoritmus pracuje s plochami 8x8, na kterých se jas a barva mění poměrně plynule. Výsledkem je, že při rozšíření matice takové oblasti na dvojitou řadu z hlediska cosinus (viz vzorce níže) se ukáží jako významné pouze první koeficienty. Komprese v JPEG se tedy provádí kvůli plynulosti barevných změn v obrázku.

Algoritmus byl vyvinut skupinou fotografických expertů speciálně pro kompresi 24bitových obrázků. JPEG - Joint Photographic Expert Group - divize v rámci ISO - International Organization for Standardization. Název algoritmu zní ["jei" peg]. Obecně je algoritmus založen na diskrétní kosinové transformaci (dále DCT) aplikované na matici obrazu pro získání nějaké nové matice koeficientů. Pro získání původního obrázku se použije inverzní transformace.

DCT rozloží obraz na amplitudy určitých frekvencí. Při transformaci tedy dostaneme matici, ve které je mnoho koeficientů buď blízkých nebo rovných nule. Navíc díky nedokonalosti lidského zraku je možné koeficienty aproximovat hruběji bez znatelné ztráty kvality obrazu.

K tomu se používá kvantování koeficientů. V nejjednodušším případě se jedná o aritmetický bitový posun doprava. Tato transformace ztratí některé informace, ale lze dosáhnout velkých kompresních poměrů.

Jak funguje algoritmus

Podívejme se tedy na algoritmus podrobněji. Řekněme, že komprimujeme 24bitový obrázek.

Krok 1.

Převedeme obrázek z barevného prostoru RGB se složkami zodpovědnými za červenou (Red), zelenou (Green) a modrou (Blue) složku barvy bodu do barevného prostoru YCrCb (někdy nazývaného YUV).

V něm je Y složka jasu a Cr, Cb jsou složky zodpovědné za barvu (chromatická červená a chromatická modrá). Vzhledem k tomu, že lidské oko je méně citlivé na barvu než na jas, je možné archivovat pole pro složky Cr a Cb s velkými ztrátami, a tedy velkými kompresními poměry. Podobná transformace se už dávno používá v televizi. Signálům zodpovědným za barvu je přiděleno užší frekvenční pásmo.

Zjednodušeně lze převod z barevného prostoru RGB do barevného prostoru YCrCb reprezentovat pomocí přechodové matice:

Inverzní transformace se provádí vynásobením YUV vektoru inverzní maticí.

Krok 2

Původní obrázek jsme rozdělili na matice 8x8. Z každé vytvoříme tři pracovní matice DCT - 8 bitů zvlášť pro každou komponentu. Při vysokých kompresních poměrech může být tento krok trochu obtížnější. Obrázek je rozdělen složkou Y - stejně jako v prvním případě a pro složky Cr a Cb se matice typují přes řádek a přes sloupec. Tito. z původní matice 16x16 se získá pouze jedna pracovní matice DCT. V tomto případě, jak je dobře vidět, přijdeme o 3/4 užitečných informací o barevných složkách obrázku a okamžitě získáme dvojnásobnou kompresi. Můžeme to udělat prací v prostoru YCrCb. Jak ukázala praxe, výsledný RGB obraz to příliš neovlivňuje.

Krok 3

Na každou pracovní matrici aplikujeme DCT. V tomto případě získáme matici, ve které jsou koeficienty vlevo horním rohu odpovídají nízkofrekvenční složce obrazu a vpravo dole - vysokofrekvenční.

Ve zjednodušené formě lze tuto transformaci znázornit takto:

Krok 4

Provádíme kvantování. V principu jde jednoduše o rozdělení pracovní matice kvantizační maticí prvek po prvku. Pro každou komponentu (Y, U a V), v obecném případě je specifikována vlastní kvantizační matice q (dále MC). V tomto kroku je řízen kompresní poměr a dochází k největší ztrátě. Je jasné, že nastavením MC s velkými koeficienty získáme více nul a následně i větší kompresní poměr.

Specifické efekty algoritmu jsou také spojeny s kvantizací. Při vysokých hodnotách koeficientu gama mohou být ztráty na nízkých frekvencích tak velké, že se obraz rozpadne na čtverce 8x8. Ztráty v vysoké frekvence se mohou projevit tzv. „Gibbsovým efektem“, kdy se kolem kontur s ostrým barevným přechodem vytvoří jakési „halo“.

Krok 5.

Matici 8x8 převedeme do 64prvkového vektoru pomocí „cik-cak“ skenování, tzn. vzít prvky s indexy (0,0), (0,1), (1,0), (2,0)...

Na začátku vektoru tedy dostaneme koeficienty matice odpovídající nízké frekvence, a na konci - vysoká.

Krok 6

Vektor konvolujeme pomocí algoritmu skupinového kódování. V tomto případě dostáváme dvojice typu (přeskočit, číslo), kde „přeskočit“ je počítadlo přeskočených nul a „číslo“ je hodnota, která musí být vložena do další buňky. Vektor 42 3 0 0 0 -2 0 0 0 0 1 ... bude tedy složen do dvojic (0,42) (0,3) (3,-2) (4,1) ... .

Krok 7

Výsledné páry skládáme Huffmanovým kódováním s pevným stolem.

Proces rekonstrukce obrazu v tomto algoritmu je zcela symetrický. Tato metoda umožňuje komprimovat některé obrázky 10-15krát bez vážných ztrát.

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

Mezi významné pozitivní aspekty algoritmu patří:

1. Nastaví kompresní poměr.
2. volno barevný obrázek může mít 24 bitů na bod.

1. Zvýšením kompresního poměru se obraz rozdělí na samostatné čtverce (8x8). To je způsobeno skutečností, že na nízkých frekvencích během kvantování dochází k velkým ztrátám a je nemožné obnovit původní data.
2. Objeví se Gibbsův efekt – svatozáře podél okrajů ostrých barevných přechodů.

Posledně jmenovaný požadavek umožnil vznik hraček, jako jsou digitální fotoaparáty – zařízení velikosti malé videokamery, která pořizují 24bitové fotografie na 10-20 MB flash kartu s rozhraním PCMCIA. Poté se tato karta vloží do slotu na vašem notebooku a příslušný program vám umožní číst snímky. Není pravda, že pokud by byl algoritmus asymetrický, bylo by nepříjemné dlouho čekat, než se zařízení „dobije“ – zkomprimuje obraz.

Další nepříliš příjemnou vlastností JPEG je, že často horizontální a svislé pruhy jsou na displeji zcela neviditelné a mohou se objevit pouze při tisku ve formě moaré vzoru. Dochází k němu, když je na vodorovné a svislé pruhy obrazu aplikován šikmý tiskový vzor. Kvůli těmto překvapením se JPEG nedoporučuje pro aktivní použití při tisku, nastavení vysokých koeficientů. Při archivaci snímků určených pro lidské prohlížení je však v současnosti nepostradatelný.

Široká aplikace JPEG na dlouhou dobu omezen snad jen tím, že pracuje s 24bitovými obrázky. Proto, aby bylo možné zobrazit obraz v přijatelné kvalitě na běžném monitoru v paletě 256 barev, bylo zapotřebí použití vhodných algoritmů, a tedy určitý čas. V aplikacích, které cílí na vybíravého uživatele, jako jsou hry, jsou taková zpoždění nepřijatelná. Navíc, pokud máte obrázky, řekněme, v 8bitovém formátu GIF, převedené do 24bitového JPEG a poté zpět do GIF pro prohlížení, pak dojde u obou převodů ke ztrátě kvality dvakrát. Nicméně nárůst velikosti archivu je často tak velký (3-20krát!) a ztráta kvality je tak malá, že ukládání obrázků ve formátu JPEG je velmi efektivní.

Je třeba říci několik slov o modifikacích tohoto algoritmu. Přestože je JPEG standardem ISO, jeho formát souboru nebyl opraven. Pomocí toho výrobci vytvářejí své vlastní, nekompatibilní formáty, a proto mohou měnit algoritmus. Interní tabulky algoritmu doporučeného ISO jsou jimi nahrazeny vlastními. Navíc je mírný zmatek při nastavování stupně ztráty. Například při testování se ukázalo, že „výborná“ kvalita, „100 %“ a „10 bodů“ poskytují výrazně odlišné obrázky. Mimochodem, „100%“ kvalita neznamená bezeztrátovou kompresi. Existují také varianty JPEG pro specifické aplikace.

Jak se standard ISO JPEG začíná stále více používat při výměně obrázků v počítačové sítě. Algoritmus JPEG je podporován ve formátech Quick Time, PostScript Level 2, Tiff 6.0 a v současnosti zaujímá přední místo v multimediálních systémech.

Charakteristika algoritmu JPEG:

Třída obrázku: Plně barevné 24bitové nebo šedé obrázky bez ostrých barevných přechodů (fotografie).

Symetrie: 1

Vlastnosti: V některých případech algoritmus vytváří „halo“ kolem ostrých horizontálních a vertikálních hran v obraze (Gibbsův efekt). Navíc při vysokém stupni komprese se obraz rozpadá na bloky 8x8 pixelů.

Myšlenka na metodu

Archivace fraktálů je založena na tom, že obrázek reprezentujeme v kompaktnější podobě - ​​pomocí koeficientů systému iterovaných funkcí (Iterated Function System - dále jen IFS). Než se budeme zabývat samotným procesem archivace, podívejme se, jak IFS buduje image, tzn. dekompresní proces.

Přísně vzato, IFS je soubor trojrozměrných afinních transformací, v našem případě přeměny jednoho obrázku na jiný. Body v trojrozměrném prostoru (x_souřadnice, y_souřadnice, jas) jsou podrobeny transformaci.

Tento proces nejjasněji demonstroval Barnsley ve své knize „Fractal Image Compression“. Tam byl představen koncept kopírky, který se skládá z obrazovky, na které je zobrazen původní obraz, a systému čoček promítajících obraz na jinou obrazovku:

• Čočky mohou promítat část obrazu volná forma na jakékoli jiné místo v novém obrázku.
• oblasti, ve kterém obrázky se promítají neprotínají se.
• může objektiv změnit jas a snížit kontrast.
• může objektiv převrátit a otočit fragment vašeho obrázku.
• Objektiv musí škálovat(zmenšit) fragment obrázku.

Umístěním čoček a změnou jejich charakteristik můžeme ovládat výsledný obraz. Jedna iterace práce Stroje spočívá v tom, že se z původního obrazu pomocí projekce sestaví nový, načež se nový vezme jako výchozí. Tvrdí se, že v procesu iterací získáme obrázek, který se přestane měnit. Bude záviset pouze na umístění a vlastnostech čoček a nebude záviset na původním snímku. Tento obrázek se nazývá " pevný bod"nebo atraktor tento IFS. Odpovídající teorie zaručuje, že pro každý IFS existuje přesně jeden pevný bod.

Vzhledem k tomu, že mapování čočky je kontrakční, každá čočka výslovně definuje sobě podobný oblasti na našem obrázku. Díky sebepodobnosti získáme složitou strukturu obrazu při libovolném zvětšení. Je tedy intuitivně jasné, že systém iterovaných funkcí definuje fraktál(nestriktně - soběpodobný matematický objekt).

Nejznámější jsou dva obrázky získané pomocí IFS: „Sierpinského trojúhelník“ a „Barnsley fern“. „Sierpinského trojúhelník“ je dán třemi a „Barnsleyho kapradina“ čtyřmi afinními transformacemi (nebo v naší terminologii „čočkami“). Každá transformace je zakódována v doslova přečtených bytech, zatímco obraz vytvořený s jejich pomocí může zabrat několik megabajtů.

Cvičení: Označte na obrázku 4 oblasti, které by se spojily, aby pokryly celý obrázek, a z nichž každá by byla podobná celému obrázku (nezapomeňte na stonek kapradiny).

=>
V nejhorším případě, pokud není použit optimalizační algoritmus, bude nutné vyčíslit a porovnat všechny možné fragmenty obrazu různých velikostí. I pro malé obrázky, vezmeme-li v úvahu diskrétnost, získáme astronomický počet možností, které je třeba vyřešit. Navíc ani prudké zúžení transformačních tříd, například škálováním pouze určitým počtem opakování, nepřináší znatelný zisk v čase. Navíc se ztrácí kvalita obrazu. Naprostá většina výzkumů v oblasti fraktální komprese je nyní zaměřena na zkrácení doby archivace potřebné k získání vysoce kvalitního obrazu.

Definice.

Kde a B c d e f reálná čísla a je volána dvourozměrná afinní transformace.

Definice. Transformace, reprezentovatelná ve formě

kde a, b, c, d, e, f, p, q, r, s, t, u jsou reálná čísla a nazývá se trojrozměrná afinní transformace.

Definice. Nechť je transformace v prostoru X. Bod, jako je tzv pevný bod(atraktor) transformace.

Definice. Transformace v metrickém prostoru (X, d) je považována za kontrakční, pokud existuje číslo s: , takový že

Komentář: Formálně můžeme pro fraktální kompresi použít jakékoli mapování kontrakce, ale ve skutečnosti se používají pouze trojrozměrné afinní transformace s poměrně silným omezením koeficientů.

Teorém. (O kompresní transformaci)

Vpusťte úplný metrický prostor (X, d). Pak existuje právě jeden pevný bod této transformace a pro jakýkoli bod posloupnost konverguje k .

Obecnější formulace této věty zaručuje konvergenci.

Definice. obraz je funkce S definovaná na jednotkové čtverci a nabývající hodnot od 0 do 1 resp

Nechť je trojrozměrná afinní transformace zapsána jako

a je definován na kompaktní podmnožině kartézského čtverce x. Poté přeloží část povrchu S do oblasti nacházející se s posunem (e,f) a rotace dané maticí

Pokud však interpretujeme hodnotu S jako jas odpovídajících bodů bude klesat p krát (přeměna musí být kontrakční) a změní se na posun q.

Definice. konečná populace W kontrahování trojrozměrných afinních transformací definovaných na doménách tak, že a , je nazýván systém iterovaných funkcí ( IFS).

Systém iterovaných funkcí je jednoznačně spojen s pevným bodem – obrázkem. Proces komprese tedy spočívá v nalezení koeficientů systému a proces dekomprese spočívá v iteraci systému, dokud není výsledný obraz stabilizován (pevný bod IFS). V praxi stačí 7-16 iterací. Regiony budou označovány jako žebříčku a oblasti doména.

Sestavení algoritmu

Jak již bylo zřejmé z výše uvedeného, ​​hlavním úkolem při kompresi fraktálovým algoritmem je najít odpovídající afinní transformace. V nejobecnějším případě můžeme překládat obrazové oblasti libovolné velikosti a tvaru, nicméně v tomto případě získáme astronomické množství možností pro vytřídění různých fragmentů, které v tuto chvíli nelze zpracovat ani na superpočítači.

V cvičná verze algoritmu , jak je uvedeno níže, platí pro oblast následující omezení:

1. Všechny oblasti jsou čtverce se stranami rovnoběžnými se stranami obrázku. Toto omezení je poměrně závažné. Ve skutečnosti budeme celou škálu geometrických tvarů aproximovat pouze pomocí čtverců.
2. Při převodu oblasti domény na doménu hodnosti se velikost zmenší rovnou dvakrát. To značně zjednodušuje kompresor i dekompresor. úkol škálování malých oblastí není triviální.
3. Všechny bloky domény jsou čtvercové a mají pevná velikost. Obrázek je rozdělen jednotnou mřížkou na sadu doménových bloků.
4. Oblasti domény jsou obsazeny „přes bod“ v X i Y, což okamžitě zkrátí vyhledávání faktorem 4.
5. Při převodu domény domény na hodnostní lze kostku otáčet pouze na 0 0 , 90 0 , 180 0 nebo 270 0. Povoleno je i zrcadlení. Celkový počet možných transformací (počítáno prázdné) je 8.
6. Provádí se vertikální škálování (komprese) (jas). pevně stanovený počet opakování- v 0,75.

1. Sestavte algoritmus, který vyžaduje relativně malý počet operací i na dostatečně velkých obrázcích.
2. Je velmi kompaktní, aby reprezentoval data, která mají být zapsána do souboru. Pro každou afinní transformaci v IFS potřebujeme:

• dvě čísla pro nastavení offsetu bloku domény. Pokud omezíme vstupní obrázky velikost 512x512, pak bude stačit 8 bitů pro každé číslo.
• tři bity pro určení transformace symetrie při převodu bloku domény na blok pořadí.
• 7-9 bitů pro nastavení posunu jasu během překladu.

Například pro soubor ve stupních šedi s 256 barvami o velikosti 512 x 512 pixelů s velikostí bloku 8 pixelů budou afinní transformace 4096 (512/8 x 512/8). Každý bude vyžadovat 3,5 bajtu. Pokud by tedy původní soubor zabíral 262144 (512x512) bajtů (bez hlavičky), pak by soubor s koeficienty zabral 14336 bajtů. Archivační koeficient - 18x. Zároveň nebereme v úvahu, že soubor s koeficienty může mít i redundanci a být archivován bezeztrátovou metodou archivace, jako je LZW.

Negativní aspekty navrhovaných omezení:

1. Vzhledem k tomu, že všechny oblasti jsou čtverce, není možné použít podobnost objektů, které mají ke čtvercovému tvaru daleko (které jsou na skutečných obrázcích zcela běžné.)
2. Podobně nebudeme moci využít podobnost objektů na obrázku, jehož koeficient podobnosti je velmi odlišný od 2.
3. Algoritmus nebude schopen využít podobnosti objektů v obraze, jejichž úhel mezi nimi není násobkem 90 0 .

Samotný balicí algoritmus je redukován na výčet všech bloků domény a výběr pro každý odpovídající blok hodnosti. Níže je schéma tohoto algoritmu.

pro (všechny bloky rozsahu) (
min_distance = MaximumDistance;
R ij= obrázek->CopyBlock(i,j);
for (všechny bloky domény) ( // S rotacemi a neg.
current=Aktuální souřadnice transformace;
D=image->CopyBlock(aktuální);
aktuální_vzdálenost = R ij.L2vzdálenost(D);
if(aktuální_vzdálenost< min_distance) {
// Pokud jsou nejlepší šance horší:
min_distance = aktuální_vzdálenost;
nejlepší=aktuální;
}
) //Další rozsah
Save_Coefficients_to_file(nejlepší);
) //Další doména

Jak je patrné z výše uvedeného algoritmu, pro každý blok hodnosti jej zkontrolujeme se všemi možnými bloky domény (včetně těch, které prošly transformací symetrie), najdeme variantu s nejmenší mírou L 2 (nejmenší směrodatná odchylka) a uložte koeficienty této transformace do souboru. Koeficienty jsou (1) souřadnice nalezeného bloku, (2) číslo od 0 do 7 charakterizující transformaci symetrie (rotace, odraz bloku) a (3) posun jasu pro tuto dvojici bloků. Posun jasu se vypočítá takto:

,

Kde r ij- hodnoty pixelů hodnotícího bloku ( R), A d ij- hodnoty pixelů bloku domény ( D). V tomto případě se opatření považuje za:

.

Nepočítáme druhou odmocninu L 2 měřit a nerozdělovat tím n, protože transformační data jsou monotónní a nebudou nám bránit v nalezení extrému, budeme však moci pro každý blok provést o dvě operace méně.

Spočítejme si počet operací, které potřebujeme ke kompresi obrázku ve stupních šedi 256 barev 512x512 pixelů s velikostí bloku 8 pixelů:

Podařilo se nám tak snížit počet operací kompresního algoritmu na celkem vyčíslitelné (i když za pár hodin) hodnoty.

Schéma algoritmu dekomprese obrazu

Dekomprese algoritmu fraktální komprese je extrémně jednoduchá. Je nutné provést několik iterací trojrozměrných afinních transformací, jejichž koeficienty byly získány ve fázi komprese.

Jako výchozí lze brát absolutně jakýkoli obrázek (například absolutně černý), protože odpovídající matematický aparát nám zaručuje konvergenci sekvence snímků získaných při IFS iteracích k statickému snímku (blízkému původnímu). Obvykle k tomu stačí 16 iterací.

Přečtěte si koeficienty všech bloků ze souboru;
Pojďme tvořit černý obrázek správná velikost;
Dokud(obrázek se neznehybní)(
Pro (každý rozsah (R)) (
D=image->CopyBlock(D_coord_for_R);
Pro (každý pixel( i,j) v bloku (
R ij = 0,75 D ij + Ó R;
) //Další pixel
) //Další blok
)//Až do konce

Protože jsme zaznamenali koeficienty pro bloky R ij(což, jak jsme uvedli, jsou v našem konkrétním případě čtverce stejné velikosti) postupně, ukazuje se, že obrázek postupně vyplňujeme čtverci mřížky dělení pomocí afinní transformace.

Jak lze vypočítat, počet operací na pixel obrazu ve stupních šedi během restaurování je neobvykle malý (N operací „+“, 1 operace „*“, kde N je počet iterací, tj. 7-16). Díky tomu je dekomprese obrazu pro fraktální algoritmus rychlejší než dekomprese, například pro algoritmus JPEG, ve kterém je 64 „+“ a 64 „? “ (s výjimkou kroků RLE a Huffmanova kódování!). Zároveň u fraktálního algoritmu dochází k násobení racionálním číslem, jedním pro každý blok. To znamená, že můžeme nejprve použít celočíselnou racionální aritmetiku, která je podstatně rychlejší než aritmetika s pohyblivou řádovou čárkou. Za druhé, násobení vektoru číslem je jednodušší a rychlejší operace, často zabudovaná do architektury procesoru (procesory SGI, Intel MMX...), než skalární součin dvou vektorů, který je v případě JPEG nezbytný. U plnobarevného obrázku se situace kvalitativně nemění, protože oba algoritmy využívají převod do jiného barevného prostoru.

Odhady ztrát a způsoby jejich regulace

V souhrnu zjednodušené verze algoritmu bylo opomenuto mnoho důležitých problémů. Co když například algoritmus nemůže najít podobný obrázek pro žádný fragment obrázku? Samozřejmým řešením je rozdělit tento fragment na menší a pokusit se je vyhledat. Zároveň je jasné, že tento postup nelze donekonečna opakovat, jinak se počet nutných transformací natolik rozroste, že algoritmus přestane být kompresním algoritmem. Proto povolujeme ztrátu v některé části obrazu.

Pro algoritmus fraktální komprese, stejně jako pro další algoritmy ztrátové komprese, jsou velmi důležité mechanismy, kterými bude možné řídit míru komprese a míru ztráty. K dnešnímu dni byl vyvinut dostatečně velký soubor takových metod. Za prvé, je možné omezit počet afinních transformací zajištěním, že kompresní poměr není nižší než pevná hodnota. Za druhé lze požadovat, aby v situaci, kdy je rozdíl mezi zpracovávaným fragmentem a jeho nejlepší aproximací nad určitou prahovou hodnotou, musel být tento fragment rozdělen (musí být pro něj vytvořeno několik „čoček“). Za třetí, je možné zakázat fragmentaci fragmentů menších než například čtyři body. Změnou prahových hodnot a priority těchto podmínek budeme mít velmi flexibilní kontrolu nad poměrem komprese obrazu v rozsahu od bitové shody po jakýkoli stupeň komprese. Všimněte si, že tato flexibilita bude mnohem vyšší než u nejbližšího „konkurence“ – algoritmu JPEG.

Charakteristika fraktálního algoritmu :

Kompresní poměry: 2–2000 (definováno uživatelem)

Třída obrázku: Plně barevné 24bitové nebo šedé obrázky bez ostrých barevných přechodů (fotografie). Je žádoucí, aby oblasti většího významu (pro vnímání) byly kontrastnější a ostřejší a oblasti menšího významu – málo kontrastní a rozmazané.

Symetrie: 100-100000

Vlastnosti: Při rozbalování může libovolně měnit měřítko obrázku a zvětšit jej 2-4krát, aniž by se objevil „efekt schodiště“. Se zvyšující se úrovní komprese se na okrajích bloků v obraze objeví „blokový“ efekt.

Anglický název pro rekurzivní kompresi je wavelet. Do ruštiny se překládá jako komprese vlny a jako komprese pomocí burstů. Tento typ archivace je znám již dlouhou dobu a přímo vychází z myšlenky využití soudržnosti regionů. Algoritmus je zaměřen na barevné a černobílé obrázky s plynulými přechody. Ideální pro snímky, jako jsou rentgenové snímky. Kompresní poměr je nastaven a pohybuje se mezi 5-100. Když se pokusíte nastavit vyšší koeficient na ostrých hranách, zejména těch, které procházejí diagonálně, objeví se „efekt schodiště“ - kroky různého jasu o velikosti několika pixelů.

Myšlenkou algoritmu je, že do souboru uložíme rozdíl – číslo mezi průměrnými hodnotami sousedních bloků v obrázku, které obvykle nabývá hodnot blízkých 0.

Takže dvě čísla A 2i A A 2i +1 může být vždy reprezentován jako b 1 i=(A 2i +A 2i +1 )/2 a b 2 i=(A 2i -A 2i +1 )/2. Podobně pořadí A ilze přeložit ve dvojicích do sekvence b 1.2i.

Podívejme se na konkrétní příklad: zkomprimujme řetězec 8 hodnot jasu pixelů ( A i): (220, 211, 212, 218, 217, 214, 210, 202). Dostaneme následující sekvence b 1 i, A b 2 i: (215,5, 215, 215,5, 206) a (4,5, -3, 1,5, 4). Všimněte si, že hodnoty b 2 idostatečně blízko k 0. Zopakujme operaci s ohledem b 1 i Jak A i. Tato akce se provádí jakoby rekurzivně, odtud název algoritmu. Získáme z (215,5, 215, 215,5, 206): (215,25, 210,75) (0,25, 4,75). Výsledné koeficienty, zaokrouhlené na celá čísla a komprimované např. pomocí Huffmanova algoritmu s pevnými tabulkami, můžeme vložit do souboru.

Všimněte si, že jsme naši transformaci na řetězec aplikovali pouze dvakrát. Ve skutečnosti si můžeme dovolit aplikovat vlnkovou transformaci 4-6krát. Navíc lze další kompresi získat použitím nejednotných tabulek krokového Huffmanova algoritmu (tj. musíme uložit Huffmanův kód pro nejbližší hodnotu v tabulce). Tyto techniky umožňují dosáhnout znatelných kompresních poměrů.

Cvičení: Obnovili jsme řetěz (215, 211) (0, 5) (5, -3, 2, 4) ze souboru (viz příklad). Sestavte řetězec osmi hodnot jasu pixelů, které algoritmus komprese vln znovu vytvoří.

Pomocí těchto vzorců pro obrázek 512x512 pixelů po první transformaci získáme 4 matice o velikosti 256x256 prvků:

-- První, jak asi tušíte, bude ukládat zmenšenou kopii obrázku. Ve druhém - průměrné rozdíly párů hodnot pixelů podél horizontály. Za třetí - průměrné rozdíly párů hodnot pixelů podél vertikály. Za čtvrté - průměrný rozdíl v hodnotách pixelů podél úhlopříčky. Analogicky s dvourozměrným případem můžeme zopakovat naši transformaci a získat 4 matice o velikosti 128x128 místo první matice. Opakováním naší transformace potřetí dostaneme: 4 matice 64x64, 3 matice 128x128 a 3 matice 256x256. V praxi se při zápisu do souboru hodnoty získané na posledním řádku () obvykle zanedbávají (okamžitě získáme zisk asi třetiny velikosti souboru - 1- 1/4 - 1/16 - 1/64 ...).

Mezi výhody tohoto algoritmu patří skutečnost, že velmi snadno umožňuje realizovat možnost postupného „vývoje“ obrazu při přenosu obrazu po síti. Navíc, protože ve skutečnosti ukládáme jeho malou kopii na začátek obrázku, je snazší zobrazit „hrubý“ obrázek podle názvu.

Na rozdíl od JPEG a fraktálního algoritmu tato metoda nepracuje s bloky, například 8x8 pixelů. Přesněji řečeno, operujeme s bloky 2x2, 4x4, 8x8 atd. Vzhledem k tomu, že koeficienty pro tyto bloky ukládáme nezávisle, se však poměrně snadno vyhneme rozdělení obrázku na „mozaikové“ čtverečky.

Charakteristika vlnového algoritmu:

Kompresní poměry: 2–200 (definováno uživatelem)

Třída obrázku: Jako fraktál a JPEG.

Symetrie: ~1.5

Vlastnosti: Navíc při vysokém stupni komprese se obraz rozpadne na samostatné bloky.

Závěr

Na závěr se podívejme na tabulky, které shrnují parametry různých algoritmů komprese obrazu diskutovaných výše.

(vyslovováno „japeg“ skupinou Joint Photographic Experts Group, podle názvu vývojářské organizace) je jedním z populárních grafických formátů používaných pro ukládání fotografických obrázků a podobných obrázků. Soubory obsahující data JPEG mají obvykle přípony .jpeg, .jfif, .jpg, .JPG nebo .JPE. Nicméně, .jpg je nejoblíbenější rozšíření na všech platformách.

1. Společná skupina fotografických expertů;

2. Metoda komprese obrazu vyvinutá touto skupinou a odpovídající grafický formát běžně používaný na WWW. Vyznačuje se kompaktností souborů, a tedy rychlým přenosem, stejně jako „ztrátou“ kvality obrazu. Používá se hlavně pro fotografie, protože ztráta kvality je pro ně méně kritická. Ukládá nastavení barev v barevném modelu RGB.

JPEG(vyslovuje se " jpeg", Angličtina. Společná skupina fotografických expertů, podle názvu vývojářské organizace) je jedním z populárních grafických formátů používaných k ukládání fotografických obrázků a podobných obrázků. Soubory obsahující data JPEG mají obvykle přípony .jpeg, .jfif, .jpg, .JPG nebo .jpe. Nicméně z těchto .jpg nejoblíbenější rozšíření na všech platformách. Typ MIME je image/jpeg.

Algoritmus JPEG je ztrátový algoritmus komprese dat.

Oblast použití

Algoritmus JPEG je nejvhodnější pro kompresi fotografií a maleb obsahujících realistické scény s plynulými přechody jasu a barev. JPEG je nejrozšířenější v digitální fotografie a pro ukládání a přenos obrázků pomocí internetu.

Na druhou stranu je JPEG málo využitelný pro kompresi kreseb, textu a grafiky znaků, kde ostrý kontrast mezi sousedními pixely vede k znatelným artefaktům. Takové snímky je vhodné ukládat v bezztrátových formátech jako TIFF, GIF, PNG nebo RAW.

JPEG (stejně jako jiné metody zkreslující komprese) není vhodný pro kompresi obrázků ve vícestupňovém zpracování, protože při každém uložení mezivýsledků zpracování se do obrázků zanesou zkreslení.

JPEG by se neměl používat v případech, kdy je i minimální ztráta nepřijatelná, například při komprimaci astronomických nebo lékařských snímků. V takových případech lze doporučit režim komprese Lossless JPEG poskytovaný standardem JPEG (který bohužel většina populárních kodeků nepodporuje) nebo kompresní standard JPEG-LS.

Komprese

Při komprimaci je obraz převeden z barevného prostoru RGB do YCbCr (YUV). Je třeba poznamenat, že standard JPEG (ISO / IEC 10918-1) nijak neupravuje volbu YCbCr, umožňuje jiné typy transformace (například s jiným počtem složek než tři) a kompresi bez konverze (přímo na RGB), nicméně specifikace JFIF (JPEG File Interchange Format, navržená v roce 1991 společností C-Cube Microsystems a nyní de facto standard) zahrnuje použití konverze RGB->YCbCr.

Po konverzi RGB->YCbCr lze pro obrazové kanály Cb a Cr zodpovědné za barvu provést „decimaci“ (podvzorkování), které spočívá v tom, že každému bloku 4 pixelů (2x2) jasového kanálu Y je přiřazeno průměrné hodnoty Cb a Cr (decimační schéma "4:2:0"). Zároveň je pro každý blok 2x2 místo 12 hodnot (4 Y, 4 Cb a 4 Cr) použito pouze 6 (každý 4 Y a jeden zprůměrovaný Cb a Cr). Pokud jsou vyšší požadavky na kvalitu obrazu obnoveného po kompresi, lze ztenčení provést pouze v jednom směru - vertikálně (schéma "4:4:0") nebo horizontálně ("4:2:2"), nebo neprovádět vůbec ("4:4:4").

Norma také umožňuje decimaci s průměrováním Cb a Cr nikoli pro blok 2x2, ale pro čtyři po sobě jdoucí (vertikálně nebo horizontálně) pixely, tedy pro bloky 1x4, 4x1 (schéma „4:1:1“), jakož i 2x4 a 4x2. Je také možné použít různé typy decimace pro Cb a Cr, ale v praxi se taková schémata používají velmi zřídka.

Dále jsou složka jasu Y a složky zodpovědné za barvu Cb a Cr rozděleny do bloků 8x8 pixelů. Každý takový blok je podroben diskrétní kosinové transformaci (DCT). Výsledné DCT koeficienty jsou kvantovány (pro Y, Cb a Cr se obecně používají různé kvantizační matice) a sbaleny pomocí Huffmanových kódů. Standard JPEG také umožňuje použití mnohem efektivnějšího aritmetického kódování, ale kvůli patentovým omezením (patent na aritmetický QM kodér popsaný ve standardu JPEG patří IBM) se v praxi nepoužívá.

Matice použité pro kvantování DCT koeficientů jsou uloženy v záhlaví souboru JPEG. Obvykle jsou postaveny tak, že vysokofrekvenční koeficienty jsou podrobeny silnější kvantizaci než nízkofrekvenční. To vede k zhrubnutí jemných detailů v obraze. Čím vyšší je kompresní poměr, tím silnější je kvantování všech koeficientů.

Když uložíte obrázek jako soubor JPEG, určíte nastavení kvality v libovolných jednotkách, například 1 až 100 nebo 1 až 10. Vyšší číslo obvykle znamená lepší kvalitu (a větší komprimovaný soubor). I při použití nejvyšší kvality (odpovídající kvantizační matici skládající se pouze z jednotek) však rekonstruovaný obraz nebude přesně odpovídat původnímu, což je spojeno jak s konečnou přesností provedení DCT, tak s nutností zaokrouhlovat hodnoty. ​​Y, Cb, Cr a koeficienty DCT na nejbližší celé číslo. Bezztrátový režim komprese JPEG, který nepoužívá DCT, poskytuje přesnou shodu mezi obnovenými a původními obrázky, nicméně jeho nízká účinnost (kompresní poměr zřídka přesahuje 2) a nedostatečná podpora ze strany vývojářů. software nepřispěl k popularitě Lossless JPEG.

Různé schémata komprese JPEG

Standard JPEG poskytuje dva hlavní způsoby reprezentace kódovaných dat.

Nejběžnější, podporovaná většinou dostupných kodeků, je sekvenční (sekvenční JPEG) reprezentace dat, která předpokládá sekvenční procházení zakódovaného obrazu blok po bloku zleva doprava, shora dolů. Výše popsané operace se provádějí na každém zakódovaném obrazovém bloku a výsledky kódování se umístí do výstupního proudu ve formě jednoho „skenování“, tzn. pole kódovaných dat odpovídajících sekvenčně předávanému ("naskenovanému") obrazu. Hlavní nebo „základní“ (základní) režim kódování umožňuje pouze takové znázornění. Rozšířený (rozšířený) režim spolu se sekvenčním umožňuje také progresivní (progresivní JPEG) reprezentaci dat.

V případě progresivního JPEG jsou komprimovaná data zapsána do výstupního proudu jako sada skenů, z nichž každý popisuje celý obraz ve stále větších detailech. Toho je dosaženo buď tím, že se v každém skenování nezaznamená úplná sada koeficientů DCT, ale pouze některé z nich: první - nízkofrekvenční, v dalších skenech - vysokofrekvenční (metoda spektrálního výběru, tj. spektrální vzorky), nebo postupným , od skenování ke skenování, zpřesňování DCT koeficientů (metoda „postupné aproximace“, tj. postupné aproximace). Tato progresivní reprezentace dat je užitečná zejména při přenosu komprimovaných obrázků pomocí nízkorychlostních komunikačních kanálů, protože umožňuje získat pohled na celý obrázek po přenesení malé části souboru JPEG.

Obě popsaná schémata (jak sekvenční, tak progresivní JPEG) jsou založena na DCT a zásadně neumožňují získat obnovený obraz, který je absolutně totožný s tím původním. Standard však umožňuje i kompresi, která nepoužívá DCT, ale je postavena na bázi lineárního prediktoru (bezeztrátový, tedy „bezeztrátový“, JPEG), který zaručuje úplnou bitovou shodu mezi originálem a obnovené obrázky. Současně kompresní poměr u fotografických obrázků zřídka dosahuje 2, ale v některých případech je zaručená absence zkreslení žádaná. Znatelně vyšší kompresní poměry lze získat pomocí kompresní metody JPEG-LS popsané v ISO/IEC 14495-1, která i přes podobnost názvů přímo nesouvisí s JPEG ISO/IEC 10918-1 (doporučení ITU T.81 ) standard (doporučení ITU T.87).

Syntaxe a struktura formátu JPEG

Soubor JPEG obsahuje sekvenci markery, z nichž každý začíná bytem 0xFF, který označuje začátek značky, a bytem identifikátoru. Některé značky se skládají pouze z této dvojice bajtů, zatímco jiné obsahují další data sestávající z dvoubajtového pole o délce informační části značky (včetně délky tohoto pole mínus dva bajty začátku značky , tedy 0xFF a identifikátor) ​​a samotná data.