Algoritmus JPEG je ztrátový algoritmus komprese dat.

Starý dobrý JPEG má i přes spoustu nepopiratelných výhod stále značná omezení. Byli povoláni, aby je sundali. nová metoda kompresi obrazu, která byla vyvíjena dlouhou 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. Stupeň zhoršení kvality je stanoven pro každý 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 převod barevného modelu 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á oproti jiným transformacím (například Fourierova transformace) řadu výhod lepší zotavení informace.

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 účelem transformace je zjistit velký obraz rozložení velkých (na obrázku - vlevo nahoře) a malých (vpravo dole) objektů, což 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. zaokrouhlování ostré rohy a rozmazání jemných prvků v obraze.
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 reálném čase 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

Například snímek získaný po filtrování dolní propustí po řádcích a řádcích (vlevo nahoře) nese největší množství informací, zatímco snímek získaný po filtraci horní propustí má 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 (parametr Progressive v Save 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áří velké zatížení pro diváka, 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 JPEG- komprimované obrázky s různými stupni komprese, rozlišení a dokonce i barevných modelů. 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- více vysoká rychlost pracovat (téměř okamžitá konverze) i s obrázky 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ě vykazuje lepší výsledky 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 jpeg soubor 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 stupni komprese (vlevo - uložený ve Photoshopu v formát 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), stupeň komprese 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. Chcete-li zobrazit takové obrázky, musíte si stáhnout poměrně velký přídavný modul(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í

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 se nejvíce používá v digitální fotografii a pro ukládání a přenos obrázků pomocí internetu.

Na druhou stranu je JPEG málo použitelný pro kompresi kreseb, textu a grafiky znaků, kde ostrý kontrast mezi sousedními pixely vede k znatelným artefaktům. Takové obrázky by měly být uloženy v bezztrátových formátech, jako je TIFF, GIF nebo PNG.

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ý však většina oblíbený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 počtem složek odlišných od tří) 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 (schéma "4:1:0"). Je také povoleno používat různé typy decimace pro Cb a Cr, ale v praxi se taková schémata používají extrémně 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í run a 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 používá jen zřídka. Do oblíbené knihovny libjpeg nejnovější verze podpora pro aritmetické kódování je zahrnuta, ale prohlížení obrázků komprimovaných pomocí této metody může být problematické, protože mnoho prohlížečů nepodporuje jejich dekódování.

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ž obrázek uložíte 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ší velikost komprimovaný soubor). Nicméně i při použití Nejlepší kvalita(odpovídá kvantizační matici skládající se pouze z jedniček), rekonstruovaný obraz nebude přesně odpovídat původnímu, což je spojeno jak s konečnou přesností provedení DCT, tak s nutností zaokrouhlit hodnoty Y, Cb, Cr a DCT koeficienty zaokrouhlené 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, ale jeho nízká účinnost (kompresní poměr zřídka přesahuje 2) a nedostatek podpory ze strany vývojářů softwaru nepřispěly 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í jsou umístěny do výstupního proudu ve formě jediného „skenování“, to znamená pole zakódovaných dat odpovídajících postupně předávaným („skenovaným“) obraz. 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 v každém skenování není zaznamenána ú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. vzorky), nebo postupným zpřesňováním DCT koeficientů od skenování ke skenování (metoda „postupné aproximace“, tedy 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. Norma 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 shodu bitů po bitech mezi původní a restaurované obrazy. 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 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, ale minus dva bajty začátku značky značka, tj. 0xFF a identifikátor) ​​a samotná data. Tato struktura souborů umožňuje rychle najít značku s potřebnými údaji (například délkou řádku, počtem řádků a počtem barevných složek komprimovaného obrázku).

Výhody a nevýhody

Mezi nevýhody komprese JPEG patří výskyt charakteristických artefaktů na obnovených snímcích při vysokých kompresních poměrech: obraz je rozptýlen do bloků o velikosti 8x8 pixelů (tento efekt je patrný zejména v oblastech obrazu s plynulými změnami jasu), v oblastech s vysokým prostorové frekvenci (například na kontrastních obrysech a okrajích obrazu) se objevují artefakty ve formě šumových halo. Je třeba poznamenat, že standard JPEG (ISO/IEC 10918-1, příloha K, článek K.8) umožňuje použití speciálních filtrů pro potlačení blokových artefaktů, ale v praxi takové filtry, i přes svou vysokou účinnost, prakticky nejsou použitý. JPEG se však i přes nedostatky velmi rozšířil díky poměrně vysokému (ve srovnání s alternativami, které existovaly v době jeho vzniku) kompresnímu poměru, podpoře komprese plnobarevných obrázků a relativně nízké výpočetní náročnosti.

Výkon komprese JPEG

Pro urychlení procesu komprese podle standardu JPEG se tradičně používá paralelizace výpočtů, zejména při výpočtu DCT. Historicky jeden z prvních pokusů o urychlení procesu komprese pomocí tohoto přístupu je popsán v článku z roku 1993 od Kasperoviche a Babkina, který navrhl originální aproximaci DCT, která umožňuje efektivní paralelizaci výpočtů pomocí 32bitových registrů. obecný účel procesory Intel 80386. Efektivnější výpočetní schémata, která se objevila později, využívala SIMD rozšíření instrukční sady procesorů x86. Hodně nejlepší výsledky umožňují dosáhnout schémat využívajících výpočetní schopnosti grafických akcelerátorů (technologie NVIDIA CUDA a AMD FireStream) pro organizaci paralelní počítání nejen DCT, ale i další stupně komprese JPEG (převod barevného prostoru, run-level, statistické kódování atd.), navíc pro každý blok 8x8 kódovaného nebo dekódovaného obrázku. Článek byl poprvé [ zdroj?] je prezentována implementace paralelizace všech stupňů algoritmu JPEG pomocí technologie CUDA, která výrazně zrychlila výkon komprese a dekódování podle standardu JPEG.

V roce 2010 vědci z projektu PLANETS umístili návod na čtení formátu JPEG do speciální kapsle, která byla umístěna ve speciálním bunkru ve švýcarských Alpách. Stalo se tak za účelem uchování informací o digitálních formátech populárních na začátku 21. století pro budoucí generace.

viz také

Poznámky

Odkazy

• Specifikace JFIF 1.02 (textový soubor)
• Optimalizace JPEG. Část 1 , Část 2 , Část 3 .

(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 se nejvíce používá v digitální fotografii 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, avšak jeho nízká účinnost (kompresní poměr zřídka přesahuje 2) a nedostatek podpory ze strany vývojářů softwaru nepřispěly k popularitě. Bezztrátový 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.

komprese jpeg digitální obraz

Jedním z nejkomplexnějších a nejoblíbenějších standardů komprese obrazu je standard JPEG.

Samotný proces komprese se skládá ze tří po sobě jdoucích kroků:

a) Výpočet diskrétní kosinové transformace (DCT) pro matice 8*8-bloků získané po standardním rozdělení matice CI;

b) kvantování DCT koeficientů;

c) kódování nejednotným kódem.

Nejprve je CI rozdělena do samostatných bloků 8 * 8 prvků, které jsou zpracovávány postupně zleva doprava a shora dolů. Zpracování každého bloku začíná posunem jasu hodnot všech jeho 64 prvků, čehož dosáhneme odečtením hodnoty , kde je maximální počet úrovní jasu. Poté se vypočítá dvourozměrný DCT prvků bloku. Získané hodnoty koeficientů jsou kvantovány podle vzorce:

,

kde je výsledek kvantování hodnoty koeficientu DCT a je odpovídajícím prvkem matice kvantovacích koeficientů:

.

(Je třeba poznamenat, že předtím, než mohou být kvantované DCT koeficienty podrobeny inverzní DCT pro rekonstrukci obrazového bloku, musí být vynásobeny:

. (2.5)

Je zřejmé, že inverzní transformace získaných hodnot bude mít za následek aproximaci rekonstruovaného obrazového bloku.)

Kvantované hodnoty koeficientů jsou změněny cikcak transformací podle:

kde je zobrazeno pořadí, ve kterém jsou koeficienty vybírány. Výsledkem je jednorozměrná sekvence kvantovaných koeficientů.

Jednorozměrné pole získané po klikaté transformaci je tříděno podle rostoucí prostorové frekvence a zpravidla existují dlouhé sekvence nul, čehož efektivně využívá procedura kódování JPEG. Doporučená kvantizační matice JPEG je následující:

Příklad. Sekvenční JPEG kódování a dekódování. Zvažte komprimaci a dekompresi následujícího bloku 8*8 prvků podle standardu sekvenčního kódování JPEG:

Původní pixely mohou mít 256 nebo 28 úrovní jasu, takže proces kódování začíná posunem v rozsahu hodnot – odečtením 27 nebo 128 od hodnot pixelů. Výsledkem je pole:

který po přímé DCT bude vypadat takto:

Pokud se výše uvedená kvantizační matice použije ke kvantování přijatých dat, pak po kvantizaci budou mít koeficienty tvar:

Kvantovací procedura dává významný počet nulových prvků. Po změně pořadí koeficientů podle klikaté transformace získáme následující pole:

(-26 -31 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 KB)

Kódové slovo KB znamená konec bloku, označuje, že všechny zbývající koeficienty v přeuspořádané sekvenci jsou 0. Chcete-li zakódovat výsledné pole, standardní kódy Huffman, transformující pole na nepřetržitý proud bitů.

Při obnově komprimovaného JPEG bloku musí dekodér nejprve rekonstruovat kvantované DCT koeficienty ze spojitého bitového toku. Protože binární sekvence Huffmanova kódu je jedinečně dekódovatelná, lze tento krok snadno implementovat pomocí vyhledávání v tabulce. Po vynásobení kvantizačními koeficienty podle (2.5) dostaneme pole:

Plně obnovený blok se získá po provedení reverzní DCT výsledného pole:

a zpětný posun rozsahu hodnot o +2 7 = +128. V důsledku toho získáme:

Všechny rozdíly v hodnotách prvků původních a obnovených bloků vznikají ze samotné podstaty ztrátové komprese, která je podstatou komprese JPEG a procedur obnovy. V tomto příkladu se chyby obnovy pohybují od -14 do 11 a jsou rozděleny následovně:

Charakteristické rysy jednotného počtu digitálních obrazových maticových bloků v kompresi JPEG . Původní DI ve stupních šedi, uložený v nějakém bezztrátovém formátu, např. ve formátu TIF, jehož matice má rozměry , rozdělíme standardním způsobem do bloků. Pokud se pro každý CI blok určí množina všech VLF (singulární spektrum), pak se ukáže, že v průměru pouze 2,40 % z celkového počtu bloků (OCHB) má nulové VLF.

Tento fakt ne náhodné. Hodnost jakékoli matice je určena počtem jejích nenulových SLF, což znamená, že přítomnost nul v singulárním spektru bude znamenat, že počet jejích lineárně nezávislých řádků (sloupců) je menší než velikost. Avšak pro libovolný reálný CI, i když vezmeme v úvahu korelaci hodnot jasu pixelů, je pravděpodobnost, že řádky (sloupce) dalšího bloku budou lineárně závislé, malá.

Kvantování DCT koeficientů, ke kterému dochází v procesu ukládání DI ve formátu JPEG (se ztrátami), je nevratný postup a vede k některým rysům poruch VLF bloku.

Nechte původní CI podrobit kompresi JPEG. Proveďme pro něj operaci částečné obnovy (PR), která zahrnuje: 1) dekódování entropie; 2) násobení získaných koeficientů odpovídajícími prvky normalizačního pole (kvantizační matice); 3) aplikace inverzní DCT, ale bez následného zaokrouhlení.

Ve výsledné matici téměř všechny bloky obsahují nulu SLF a takových hodnot bude v blocích poměrně hodně (tabulka 2.1). Tato situace je přirozená. Po kvantování a zaokrouhlení koeficientů bloků DCT bude mnoho z nich, odpovídajících vysokým a středním frekvencím, nastaveno na nulu, přičemž po FB zůstane nula, což vzhledem ke shodě mezi koeficienty diskrétní Fourierovy transformace a singulární trojice obrazové matice, kde je SLF a odpovídající levý a pravý SNF, povedou k vynulování nejmenších (a možná středně velkých) blokových matic ELF.

Tabulka 2.1. Výsledky singulárního hodnotového rozkladu bloků částečně rekonstruovaných obrazů

Všimněte si, že čím méně nulových ELF v uvažovaném bloku, tím více vrstevnic obsahuje. Přítomnost obrysů v bloku skutečně indikuje významnou vysokofrekvenční složku v signálu odpovídajícímu tomuto bloku. Pak budou koeficienty DCT odpovídající vysokým a středním frekvencím relativně velké a po kvantizaci a frekvenční odezvě mohou zůstat nenulové, což znamená, že přispějí nejen k maximální VLF.

Pro vizuální znázornění platnosti výše uvedeného zvažte obrázek CELL.TIF (obr. 2.5(a)). Obrázek 2.5(b) ukazuje matici nulových VLF bloků (MNSCHB) rozměru FM obrazu, jejíž každý prvek je roven počtu nulových VLF bloků v odpovídajícím bloku. Na obrázku jsou zvýrazněny prvky s nejmenšími hodnotami, což vám umožňuje vizuálně vidět shodu mezi obrysy původní digitální reference a bloky obsahujícími nejmenší počet nulových VLF.

Nechte původní obrázek komprimovaný ve formátu JPEG zcela obnovit. To znamená, že po FW jsou všechny hodnoty jasu pixelů zaokrouhleny nahoru na celá čísla a vloženy do rozsahu. Tato akce naruší obrazovou matici získanou po FW, počet nulových VLF v blocích se určitým způsobem změní (tabulka 2.2). Tam, kde po CV nebyly žádné prvky významně menší než 0 nebo větší než 255, bude narušení matice malé. V souladu s poměrem

, (2.6)

probíhající pro libovolnou matici, kde je SLF původní a narušené matice, respektive, je poruchová matice bloku, je normou spektrální matice, SLF jsou necitlivé na rušivé vlivy. Pokud se některé z nulových bloků ELF matice obrazu FM po úplné obnově (RT) stanou nenulovými, pak budou jejich hodnoty srovnatelné se zaokrouhlovací chybou, která není typická pro bloky původního DI.

Obr.2.5. Původní obrázek CELL.TIF (a); MNSCHB za CV (b); MNSCHB po úplném zotavení (c)

Nejpatrnější rozdíl mezi agregovaným původním obrázkem a plně rekonstruovaným obrázkem zkomprimovaným JPEG bude při porovnání jejich MLNB. Typický obrázek je na obr. 2.5(c), zatímco MNSIF pro CELL.TIF měl pouze nulové hodnoty.

Tabulka 2.2. Výsledky dekompozice singulární hodnoty bloků kompletně rekonstruovaných obrazů

Otázky

1. Co znamená komprese dat? Co je redundance dat?
2. Hlavní typy redundance dat.
3. Jak je komprese implementována kvantizací?
4. Co je aproximace nízkého hodnocení? Jak je implementována komprese prostřednictvím použití aproximací obrázků nízké úrovně?
5. Jaký je singulární rozklad matice?
6. Jaký je spektrální rozklad matice?
7. Korespondence mezi parametry digitálního obrazu v prostorové a frekvenční oblasti.
8. Základní kroky Komprese JPEG digitálního obrázku. Kvantovací matice.
9. Charakteristické rysy jednotného počtu digitálních obrazových maticových bloků v kompresi JPEG.
10. Částečné a plné zotavení digitální obraz po kompresi.

Literatura

1. Kobozeva A.A. Analýza informační bezpečnosti / A.A. Kobozeva, V.A. Khoroshko. - K.: Ed. GUIKT, 2009. - 251 s.
2. Demmel J. Computational linear algebra / J. Demmel; překlad z angličtiny. H.D. Ikramová. - M.: Mir, 2001. - 430 s.
3. Bakhvalov N.S. Numerické metody / N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov. - M.: BINOM. Vědomostní laboratoř, 2006. - 636 s.
4. Gonzalez R. digitální zpracování obrázky / R. Gonzalez, R. Woods; za. z angličtiny. vyd. P.A. Chochia. - M.: Technosfera, 2005. - 1072 s.
5. Kahaner D. Numerické metody a software/ D. Kahaner, K. Mowler, S. Nash; za. z angličtiny. H.D. Ikramová. - M.: Mir, 2001. - 575 s.
6. Gantmakher F.R. Teorie matic / F. R. Gantmakher. - M.: Nauka, 1988. - 552 s.
7. Voevodin V.V. Výpočetní základy lineární algebra/ V. V. Voevodin. - M.: Věda. Vedoucí redaktor fyzikální a matematické literatury, 1977. - 304 s.

Je snadné spočítat, že nekomprimovaný plně barevný obrázek 2000*1000 pixelů bude mít velikost asi 6 megabajtů. Pokud mluvíme o snímcích získaných z profesionálních fotoaparátů nebo skenerů s vysokým rozlišením, pak jejich velikost může být ještě větší. Navzdory rychlému růstu kapacity úložných zařízení jsou různé algoritmy pro kompresi obrazu stále velmi relevantní.
Všechny existující algoritmy lze rozdělit do dvou velkých tříd:

• Bezeztrátové kompresní algoritmy;
• Ztrátové kompresní algoritmy.

Bezeztrátové kompresní algoritmy

Algoritmus RLE

Slovníkové algoritmy

Tato tabulka je jak na straně toho, kdo informace komprimuje, tak na straně toho, kdo dekomprimuje. Nyní se podíváme na proces komprese.

Tabulka ukazuje proces plnění slovníku. Je snadné spočítat, že výsledný komprimovaný kód zabere 105 bitů a původní text (za předpokladu, že strávíme 4 bity na kódování jednoho znaku) zabere 116 bitů.
Ve skutečnosti je proces dekódování redukován na přímé dekódování kódů, přičemž je důležité, aby byla tabulka inicializována stejným způsobem jako při kódování. Nyní zvažte dekódovací algoritmus.


Řetězec přidaný do slovníku v i-tém kroku lze zcela určit pouze v i+1. Je zřejmé, že i-tý řádek musí končit prvním znakem řádku i+1. Že. právě jsme přišli na to, jak obnovit slovník. Zajímavá je situace, kdy je zakódována sekvence ve tvaru cScSc, kde c je jeden znak a S je řetězec a slovo cS je již ve slovníku. Na první pohled se může zdát, že dekodér tuto situaci nevyřeší, ale ve skutečnosti musí všechny řetězce tohoto typu končit vždy stejným znakem, kterým začínají.

Entropické kódovací algoritmy

Huffmanův algoritmus

1. Znaky vstupní abecedy tvoří seznam volných uzlů. Každý list má váhu, která se rovná četnosti výskytu symbolu
2. Jsou vybrány dva volné uzly stromu s nejmenší váhou
3. Jejich rodič je vytvořen s váhou rovnou jejich celkové hmotnosti
4. Rodič je přidán do seznamu volných uzlů a jeho dva potomci jsou z tohoto seznamu odstraněni.
5. Jeden oblouk vycházející z rodiče má přiřazen bit 1, druhý je přiřazen bit 0
6. Kroky počínaje druhým se opakují, dokud v seznamu volných uzlů nezůstane pouze jeden volný uzel. Bude považován za kořen stromu.

Aritmetické kódování