Algoritmus byl vyvinut v roce 1991 skupinou fotografických expertů (JPEG – Joint Photographic Expert Group – divize v rámci ISO) speciálně pro kompresi 24bitových obrázků.
Algoritmus je založen na diskrétní kosinové transformaci (dále DCT) aplikované na matici obrazu pro získání nové matice koeficientů.
DCT rozkládá obraz podle amplitud určitých frekvencí. Při transformaci tedy získáme matici, ve které je mnoho koeficientů buď blízkých nebo rovných nule.
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 vysokými ztrátami, a tedy vysokými kompresními poměry.
Zjednodušený převod z barevného prostoru RGB do barevného prostoru YCrCb lze znázornit pomocí přechodové matice:
Inverzní transformace se provádí vynásobením YUV vektoru inverzní maticí.
Krok 2. Původní obrázek rozdělíme na matice 8×8. Z každé vytvoříme tři pracovní matice DCT – 8 bitů zvlášť pro
každá součástka. Při vyšších kompresních poměrech může být tento krok trochu obtížnější. Tito. z původní matrice o velikosti 16×16 se získá pouze jedna pracovní matrice DCT. V tomto případě 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.
Krok 3. Aplikujte DCT na každou pracovní matrici. V tomto případě získáme matici, ve které koeficienty v levém 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. Provedeme kvantování. V podstatě je to jen dělení pracovní matice maticí
kvantování prvek po prvku. Pro každou složku (Y, U a V) je v obecném případě určena vlastní kvantizační matice q[u,v] (dále jen MC).
Standard JPEG zahrnuje doporučené MK, vytvořené experimentálně. Matice pro větší či menší kompresní poměry získáme vynásobením původní matice určitým číslem gama.
Krok 5. Převod matice 8×8 na 64-prvkový vektor pomocí cik-cak skenování
Na začátku vektoru tedy získáme maticové koeficienty odpovídající nízkým frekvencím a na konci vysokým.
Krok 6. Konvolujte vektor pomocí algoritmu skupinového kódování. V tomto případě dostaneme dvojice typu (přeskočit, číslo), kde „přeskočit“ je počítadlo přeskočených nul a „číslo“ je hodnota, kterou je třeba vložit do další buňky. Vektor je tedy 42 3 0 0 0 – 2 0 0 0 0 1 . budou srolovány do dvojic
Krok 7. Výsledné páry sbalíme pomocí Huffmanova kódování s pevnou tabulkou.
Proces obnovy 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.
Mezi významné pozitivní aspekty algoritmu patří:
1. Nastavte kompresní poměr.
2. Výstupní barevný obrázek může mít 24 bitů na bod. Negativní aspekty algoritmu jsou, že:
1. Jak se kompresní poměr zvyšuje, obraz se rozpadá na samostatné čtverce
(8×8). 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 – halo podél hranic ostrých barevných přechodů. Vlastnosti algoritmu JPEG:
Kompresní poměry: 2-200 (definované uživatelem).
Třída obrázků: Plnobarevné 24bitové obrázky nebo obrázky ve stupních šedi bez ostrých barevných přechodů (fotografie).
Charakteristické rysy: V některých případech algoritmus vytváří „halo“ kolem ostrých horizontálních a vertikálních hranic v obraze (Gibbsův efekt). Navíc při vysokém stupni komprese je obraz rozdělen do bloků 8×8 pixelů.
JPEG 2000/rozdíly od JPEG
Lepší kvalita obrazu s vysokou kompresí. Podpora pro kódování jednotlivých oblastí v lepší kvalitě.
Převod DCT byl nahrazen DWT (plynulý vývoj obrazu je nyní zpočátku součástí standardu). Pro zvýšení kompresního poměru používá algoritmus aritmetickou kompresi.
Kódování s explicitní specifikací požadované velikosti spolu s tradiční metodou kódování kvality.
Podpora bezztrátové komprese (je možné použít JPEG ke komprimaci lékařských snímků, při tisku, při ukládání textu pro rozpoznání OCR). Podporuje kompresi jednobitových (2barevných) obrázků.
Průhlednost je podporována na úrovni formátu.
• Kompresní poměry: 2-200 (definované uživatelem), možná bezeztrátová komprese.
• Třída obrázků: Plně barevné 24bitové obrázky, obrázky ve stupních šedi, 1bitové obrázky (JPEG-2000 je nejuniverzálnější).
• Funkce: Můžete nastavit kvalitu oblastí obrazu.
18) Obecná charakteristika algoritmů ztrátové komprese. Obecné myšlenky a charakteristiky algoritmů fraktální komprese
Pro archivaci snímků byly jako první použity konvenční algoritmy. Ty, které byly a jsou používány v záložní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 algoritmu – komprese se ztrátou informace. Zpravidla lze nastavit koeficient archivace a tím i míru ztráty kvality v nich. To vytváří kompromis mezi velikostí obrazu a kvalitou.
Ztrátu kvality obrazu nejlépe posoudí naše oči. Archivace je považována za vynikající, pokud není možné rozlišit mezi původními a nearchivovanými snímky pouhým okem. Dobré je, že když zjistí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, dokonce i při zachování vynikající kvality, mohou být na obrázku pravidelně prováděny specifické změny.
Základem metody fraktálního kódování je detekce sobě podobných oblastí v obraze. Možnost aplikace teorie iterovaného funkčního systému (IFS) na problém komprese obrazu poprvé prozkoumali Michael Barnsley[1] a Alan Sloan. Svůj nápad si patentovali v letech 1990 a 1991 (US Patent 5 065 447). A. Jacquin (francouzsky: Arnaud Jacquin)
představila metodu fraktálního kódování, která využívá systémy doménových a rozsahových podobrazových bloků, čtvercových bloků pokrývajících celý obraz. Tento přístup se stal základem pro většinu metod fraktálního kódování. Vylepšil jej Yuval Fisher a řada dalších výzkumníků.
V souladu s touto metodou se obraz rozdělí na sadu nepřekrývajících se řadových subobrazů (anglicky range subimages) a určí se sada překrývajících se doménových subobrazů (anglická doménová subimages). Pro každý rank blok najde kódovací algoritmus nejvhodnější doménový blok a afinní transformaci, která převede tento doménový blok do daného rank bloku. Struktura obrazu je mapována do systému rank bloků, doménových bloků a transformací.
Myšlenka je následující: předpokládejme, že původní obrázek je pevným bodem nějakého kompresního mapování. Toto mapování si pak místo samotného obrázku můžete nějak zapamatovat a pro jeho obnovení stačí toto mapování opakovaně aplikovat na libovolný počáteční obrázek.
Podle Banachovy věty takové iterace vždy vedou k pevnému bodu, tedy k původnímu obrazu. V praxi spočívá problém v nalezení nejvhodnějšího kompresního mapování z obrázku a jeho kompaktním uložení. Mapovací vyhledávací algoritmy (tj. kompresní algoritmy) jsou obvykle
vyčerpávající a vyžadují velké výpočetní náklady. Algoritmy obnovy jsou přitom poměrně účinné a rychlé.
Fraktální komprese je ztrátový algoritmus, který se objevil v roce 1992. Ke konstrukci obrázků používá afinní transformace, což umožňuje velmi kompaktně specifikovat složité struktury. Komprese se provádí hledáním sobě podobných oblastí v obraze.
Myšlenka fraktálního algoritmu
• Koeficienty zapisujeme do souboru
• Pokud je velikost koeficientů menší než velikost zdrojového souboru, dostaneme kompresní algoritmus
• Významnou nevýhodou je dlouhá doba komprese. Tito. Komprese obrázku trvá na výkonných počítačích hodiny.
Fraktální komprese / Charakteristika
Kompresní poměry: 2 až 100krát.
Symetrie: Výrazně asymetrická. Koeficient asymetrie dosahuje 10000 XNUMX.
