JPEG. Algoritmus kompresie

Ahojte znova! Našiel som tento článok, napísaný ešte v máji 2019. Toto je pokračovanie série článkov o WAVE a JPEG. Tu je prvý. Tento príspevok zahrnie informácie o algoritme kódovania obrázkov a o formáte samotnom.

Štipka histórie

Polievková lyžica z Wikipédie:

JPEG (Joint Photographic Experts Group) – jeden z populárnych rastrových grafických formátov, používaný na uchovanie fotografií a podobných obrázkov.

Tento štandard bol vyvinutý Spoločnou skupinou expertov na fotografiu už v roku 1991 na efektívne kompresovanie obrázkov.

Akú cestu prechádzajú obrázky od surového vzhľadu po JPEG

Niektorí si myslia, že JPEG obrázky sú komprimované metódou Huffmanovho kódovania surové dáta, ale to nie je pravda. Pred kontrolným stlačením prechádzajú dáta dlhú cestu.

Najprv sa farebná schéma zmení z RGB na YCbCr. Na to existuje špeciálny algoritmus – tu. Y sa nemení, pretože zodpovedá za jas a jeho zmena by bola viditeľná.

Prvá vec, ktorú urobia s obrázkom – je „zjednodušenie“ (subsampling). Je to jednoduché pochopiť: vezme sa 2x2 mriežka pixelov, ďalej sa vezmú Cb a Cr – priemerné hodnoty každého z komponentov YCbCr týchto 4 pixelov. A tak, získali sme 6 bajtov, namiesto 4 Y, 4 Cb, 4 Cr sme dostali 4 Y a rovnaké pre každého z nich Cb a Cr (4 + 4 + 4 = 12; 4 + 1 + 1 = 6; 12 — 6 = 6). V rozsahu dokonca 2×2 vyzerá kompresia s stratou s pomerom kompresie 2:1 solídne. To sa aplikuje na celý obrázok. A tak – sme znížili veľkosť o polovicu. Takýto postup môžeme využiť vďaka nášmu farebnému vnímaniu. Človek si ľahko všimne rozdiel v jase, ale nie v farbe, ak je priemerná v malom bloku pixelov. Zjednodušenie môže byť tiež vykonané v línii, 4 pixely horizontálne a vertikálne. Prvá varianta sa používa častejšie. Ak je kvalita obrázka dôležitá, zjednodušenie sa vôbec nevykonáva.
Názorná ilustrácia zjednodušenia (Habr neumožnil vložiť gif) – https://i.ibb.co/Rg5Th9H/150953010617579181.gif

Hlavná časť prípravy

DCT

Teraz tá najnáročnejšia a najpotrebnejšia časť. Celý obrázok sa rozdelí na bloky 8×8 (používa sa vyplnenie, ak rozlíšenie nie je násobkom strany bloku).

Teraz sa k každému bloku aplikuje DCT (Diskrétna kosínusová transformácia)V tejto časti sa z obrázka odstráni všetko nadbytočné. Použitím DCT treba pochopiť, či daný blok (8×8) opisuje nejakú monotónnu časť obrázka: oblohu, stenu; alebo obsahuje zložitú štruktúru (vlasy, symboly atď.). Je logické, že 64 podobných farebných pixelov možno opísať iba jedným, pretože veľkosť bloku je už známa. Tu sa dostáva k kompresii: 64 ku 1.

DCT premení blok na spektrum, a tam, kde sa hodnoty ostro menia, koeficient sa stáva kladným, a čím ostrejší je prechod, tým vyšší bude výstup. Tam, kde je koeficient vyšší, sú na obrázku zobrazené jasné prechody v farbe a jasu, kde je nižší — slabé (hladké) zmeny hodnôt komponentov YCbCr v bloku.

Kvantovanie

Tu sa už aplikujú nastavenia kompresie. Každý z koeficientov v každej z matíc 8×8 sa delí na určité číslo. Ak kvalitu obrázka po všetkých jeho modifikáciách viac zmenšovať nebudete, potom by mal deliteľ byť jednotkou. Ak vám záleží viac na pamäti, ktorú táto fotografia zaberá, potom bude deliteľ väčší ako 1, a podiel sa zaokrúhľuje. Tak sa stáva, že po zaokrúhlení sa často získa veľa núl.

Kvantovanie sa robí na vytvorenie možnosti ešte väčšej kompresie. Takto to vyzerá na príklade kvantovania grafu y = sin(x):

Komprimácia

Najprv prechádzame maticou zig-zagom:

Získame jednorozmerné pole s číslami. Vidíme, že v ňom je veľa núl, ktoré môžeme odstrániť. Na to namiesto sekvencie z mnohých núl zapisujeme 1 nulu a po nej číslo, ktoré označuje ich počet v sekvencii. Týmto spôsobom môžeme zmenšiť celé pole až na 1/3 jeho veľkosti. A ďalej jednoducho skomprimujeme toto pole metódou Huffmana a zapíšeme už do samotného súboru.

Kde sa používa

Všade. Tak ako PNG, aj JPEG sa používa v fotoaparátov, OS-ách (ako logá spoločností, ikony aplikácií, thumbnail-y) a vo všetkých možných oblastiach, kde je potrebné efektívne uchovávať obrázky.

Záver

V súčasnosti sú vedomosti o JPEG cenné iba na vzdelávacie účely, pretože je už všade zabudovaný a optimalizovaný veľkými skupinami ľudí, ale granit vedy je však stále chutný.

Zdroje

Článok o YCbCr na Wikipédii
Článok o JPEG na Wikipédii
Trochu o DCT z príspevku Pikabu
Článok o DCT na Wikipédii

Zdroj: habr.com