Jak se kóduje JPEG?

Pro práci se soubory jpeg bylo napsáno mnoho knihoven. Dokonce i Java ve výchozím nastavení podporuje čtení a zápis souborů jpeg. Když však potřebujete dekódovat složitější typy přenosu jpeg, musíte pochopit, jak formát funguje a jaké algoritmy se používají. V tomto článku se pokusím co nejdůkladněji analyzovat kódování jpeg.

typy převodů jpeg

Před analýzou barevného kódování ve formátu jpeg je nutné jasně oddělit dvě věci: barevné kódování a přenos obrazových bloků.

Barevné kódování je sada algoritmů pro vytváření, tzv. MCU, bloků 8×8 nebo 16×16 pixelů. Tyto algoritmy jsou zodpovědné za kompresi obrazu.

Existuje několik typů přenosu nebo ukládání obrazových bloků. Soubor je nejběžnější metodou. Na začátku souboru je popis kvantizačních tabulek a všechny druhy metainformací o obrázku. Poté následuje seznam bloků MCU jpeg.

Navzdory skutečnosti, že soubor je použit v 99.999% případů, existují i ​​​​jiné způsoby přenosu obrázků jpeg. V podstatě řeší ten či onen problém, který nelze vyřešit pomocí standardních souborů. Nepřetržitý jpeg – způsob přenosu „nekonečného“ souboru jpeg. Používá se v meteorologických družicích k přenosu pásem skenování Země. Vzhledem k tomu, že satelit létá kolem Země a neustále vysílá informace, zdá se, že obraz má „nekonečnou“ výšku.

SSDV je způsob přenosu souboru jpeg, ve kterém mohou být některé pakety ztraceny. Používá se v satelitech s užším kanálem přenosu dat.

Níže se pokusím popsat pouze algoritmy kódování barev v jpeg.

kódování jpeg

Krok 1: Převeďte na YCbCr

Původní barva RGB se převede na YCbCr pomocí vzorce:

Proč se to udělalo? Zde je důležité pochopit, že veškerá komprese jpeg je založena na lidském vnímání barev. Úkolem algoritmu je zmenšit velikost obrázku tak, aby člověk nepostřehl velký rozdíl. Důležité je zde „nevšiml jsem si“. Někdo si toho může všimnout, někdo ne. Algoritmus mezi nimi nerozlišuje, ale pracuje s průměrnou hodnotou „nevšiml si“. Tato hodnota byla získána empiricky průzkumem mnoha lidí.

V tomto případě je důležité vědět, že lidské oko je citlivější na zelenou barvu. Také lidské oko je citlivější na kontrast než na odstíny barev. Je to dáno především tím, že rohovka umožňuje rozlišovat předměty ve tmě.

Když to víte, můžete převést „počítačový“ formát RGB na YCbCr, který je více lidský. Snížením kvality CbCr můžete výrazně snížit množství informací bez ztráty kvality vnímání. Na tom je založen další krok.

Krok 2: Vzorkování

Složky Cb a Cr lze vzorkovat ve významných intervalech, čímž se zmenšuje velikost obrazu. Tato technika se nazývá chroma subsampling. Spočívá v tom, že pro každý blok Y se v určitém intervalu berou bloky Cb a Cr.

Text není SVG – nelze zobrazit

Například na obrázku výše je podvzorkování barev 4:2:0. To znamená, že pro blok 2×2 pixelů jsou složky Y, pixely Cb a Cr, zprůměrovány a brány pouze jednou. Jpeg podporuje různé možnosti podvzorkování: 4:1:1, 4:2:0.

V tomto případě se nám ho podařilo zmenšit z 12 bajtů (3 * 4 * 1 bajt) na 6 bajtů (4 bajty + bajt + byte). To znamená, že velikost zmenšete 2krát!

Krok 3.

Nejjednodušším krokem je převést barvu z intervalu 0 ~ 255 na rozsah se znaménkem -128 ~ 127.

Krok 4: Diskrétní kosinová transformace

Následující kroky zmenší velikost odfiltrováním vysokofrekvenčních detailů v obraze. Tento proces je lépe pochopitelný na příkladu. Nejprve však musíte rozdělit obrazové pixely na bloky 8×8 pixelů. Nějaká jpeg terminologie. DU (datová jednotka) je blok 8×8 pixelů jedné komponenty. MCU (minimální kódovací jednotka) je několik nebo jeden DU, které dohromady dávají kusu obrazu 8×8 nebo 16×16 pixelů. Ve výše uvedeném příkladu vypadá MCU takto:

Text není SVG – nelze zobrazit

MCU se skládá ze 6 DU. Každý blok DU se skládá z 8×8 pixelů.

Po rozdělení obrázku na bloky DU je každý blok zakódován. Diskrétní kosinusová transformace je postupně aplikována na každou z nich. Tato operace převede matici čísel 8×8 na jejich frekvenční reprezentaci. To je velmi podobné diskrétní Fourierově transformaci. Výsledná matice 8×8 má jednu vlastnost: nejvíce energie je soustředěno v levém horním rohu a nejméně energie je v pravém dolním rohu.

Tato nemovitost bude dále využívána.

Krok 5. Cik-cak transformace

Hlavním účelem všech těchto transformací je odstranění vysokofrekvenčních složek, které se nacházejí v pravém dolním rohu. K tomu je však nutné reprezentovat pole tak, aby všechny vysokofrekvenční hodnoty byly v poli poslední. K tomu se používá tzv. cik-cak transformace. Prvky pole 8×8 se přebírají v klikatém pořadí, počínaje levým horním rohem.

Text není SVG – nelze zobrazit

Krok 6. Kvantizovat

V tomto kroku se odstraní vysokofrekvenční hodnoty. V posledním kroku je třeba výslednou matici rozdělit prvek po prvku do kvantizační tabulky. Složka Y má vlastní kvantizační tabulku, Cb a Cr vlastní. Každá z těchto tabulek byla získána empiricky na základě průzkumu mnoha lidí.

Z této tabulky je vidět, že hodnoty v pravém dolním rohu mají největší hodnoty a odpovídají vysokofrekvenčním hodnotám DU. Pokud odpovídající hodnoty tabulky rozdělíte navzájem a zaokrouhlíte na nejbližší celé číslo, pak s vysokou pravděpodobností bude v pravém dolním rohu 0.

Například po provedení diskrétní kosinové transformace máme tabulku:

Po kvantizaci a cik-cak transformaci dostaneme:

Krok 7: Kódování série

První prvek pole má speciální vlastnosti – je vždy nenulový. Proto je ve standardu jpeg výsledné pole rozděleno na 2 části a zakódováno různými způsoby. První prvek se nazývá DC koeficient a dále popíšu, jak se kóduje. Zbývající pole se nazývá AC koeficienty. Jsou kódovány pomocí řad. K tomu je pole zapsáno následovně:

První číslo představuje počet „0s“, které jsou před druhým číslem. EOB (end of block) je speciální číslo, které označuje, že blok skončil a pokračuje pouze 0. Zde je další příklad kódování série:

Cik-cak transformace byla právě to, co bylo potřeba k tomu, aby se všechny „0“ umístily na konec a nahradily je EOB.

Jednou z podmínek kódování je, že první číslo nemůže být větší než 0xF. Proto je 16 nebo více nul zakódováno do několika bloků. Například 57 osmnáct nul 45 je kódováno jako:

Krok 8: Huffmanovo kódování pro AC koeficienty

Než přejdeme k Huffmanovu kódování, je nutné popsat, jak se čísla ukládají podle standardu jpeg. Typicky se k ukládání čísel v programu používají datové typy s pevnou délkou: byte, short, int. Jpeg používá minimální počet bitů k uložení čísla. To znamená, že pro uložení čísla „1“ je použit pouze 1 bit. Pro uložení čísla „9“ se používají 4 bity – 1001. Protože však délka čísla není předem známa, je nutné uložit i jeho délku. Ve standardu jpeg se délka čísla nazývá kategorie. Zde je seznam možných délek a jejich odpovídajících čísel:

Hodnoty	kategorie	bitů
		–
-1,1	1	0,1
-3, -2,2,3	2	00,01,10,11
-7, -6, -5, -4,4,5,6,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	–

Výsledek z posledního kroku:

Můžete to přepsat do trochu jiného tvaru – (počet nul, kategorie, číslo v binárním tvaru):

Nyní si můžete všimnout, že první 2 čísla nemohou přesáhnout jeden bajt. Počet nul nesmí být větší než 0xF a počet kategorií také nesmí být větší než 0xF. Tento první bajt je zakódován pomocí Huffmanova kódu.

Huffmanovy kódy jsou založeny na poměrně zajímavé myšlence: zakódujme nejčastěji se vyskytující čísla s nejmenším počtem bitů. Například pro sekvenci 6 6 4 5 6 4 nahraďte číslo „6“ „0“. Pak místo 110 bude zakódováno jako 0. Ale to nestačí. Je nutné zakódovat počet bitů v čísle. To se provádí pomocí kódování prefixů. To znamená, že pokud znáte předponu, můžete jednoznačně určit hodnotu čísla. V tomto případě vzácná čísla zaberou více bitů. Formálnější popis Huffmanova kódu pomocí binárních stromů si můžete přečíst na Wikipedii.

Pro kódování AC koeficientů existuje Huffmanova tabulka. Může být definována v souboru nebo předem dohodnuta. Může to vypadat například takto:

Počet nul/kategorie	Délka kódu	Kód
0/0 (EOB)	4	1010
0/1	2	00
0/2	2	01
0/3	3	100
0/4	4	1011
1/1	4	1100
0/5	5	11010
.
15/10	16	1111111111111110

Toto je příklad Huffmanovy tabulky ze standardu jpeg. Nikdo vás však neobtěžuje mít pro každý soubor vlastní tabulku. Mimochodem, mnoho programů pro optimalizaci souborů jpeg je založeno na tomto. Namísto použití standardní tabulky tyto programy počítají počet nejběžnějších čísel a sestavují z nich své Huffmanovy tabulky.

Uložení Huffmanova stolu je také netriviální. Místo uložení výsledné tabulky ukládá soubor 2 tabulky: seznam délek a seznam hodnot. Pomocí nich můžete sestavit potřebné tabulky.

Takže pomocí Huffmanovy tabulky můžeme zakódovat první bajt takto:

Krok 9: Huffmanovo kódování pro DC koeficient

Stejnosměrný koeficient je speciální, a proto je kódován samostatně. Algoritmus se skládá ze dvou fází:

1. výpočet rozdílu s předchozím DC koeficientem. Výzkumníci si všimli, že po sobě jdoucí bloky 8×8 mívají velmi podobné DC koeficienty. Pokud odečtete jeden od druhého, pak rozdíl mezi nimi není velký a ve výsledku to při Huffmanově kódování zabere méně bitů. Je tedy zakódován pouze rozdíl v DC koeficientech:

Pokud neexistuje žádný předchozí, považuje se za rovný „0“.

V důsledku toho bude DC koeficient „13“ zakódován jako (101,1101):

A konečný výsledek:

Kdybychom to zakódovali přímo, vyšlo by to (8 * * 8 bitů = 512 bitů. Pomocí různých algoritmů však byly zmenšeny na 25 bitů. Celková komprese je téměř 20krát!

Všichni zbývající DU jsou zakódováni stejným způsobem.

dekódování jpeg

Chcete-li dekódovat jpeg, musíte všechny kroky provést v opačném pořadí.

Charakteristickým rysem dekódování je hledání kódového slova v Huffmanově tabulce. Obvykle se pro tyto účely vytvářejí vyhledávací tabulky se všemi možnými předponami Huffmanova kódu. Poté se ze souboru načtou 2 bajty a vyhledá se kategorie, počet nul atd.

prémie

Pokud si pozorně přečtete algoritmy, všimnete si, že diskrétní kosinová transformace, kvantizace a konverze RGB na YCbCr mohou vytvářet zlomkové hodnoty. A protože barvy jsou uloženy jako celá hodnota, dojde k zaokrouhlování. Při jednorázovém dekódování z jpeg (YCbCr) do RGB toto zaokrouhlení nevyvolá znatelnou chybu. Při opakovaném převodu z rastru na jpeg a zpět se však chyba nahromadí a přinese znatelné výsledky.

Někteří editoři definují takzvaný „kompresní poměr“ jpeg. To je implementováno zcela jednoduše: všechny koeficienty kvantizační matice jsou vynásobeny určitým číslem. Čím větší číslo, tím větší koeficient, tím větší je pravděpodobnost, že v matici barevných hodnot budou nuly. To současně snižuje velikost obrázku a snižuje jeho kvalitu.