Nahrávání obrazovky s využitím bezeztrátové interframe komprese videa

Úvod a trochu teorie

Při bezeztrátové kompresi jsou redukovány pouze ty informace, které je možné odvodit z jiných informací. Těmto nadbytečným informacím se říká redundance. Jen a pouze redundantní data lze redukovat s možností 100% obnovení původního obsahu. Proto je nutné hned na úvod říct, že bezeztrátová komprese zdaleka nedosahuje takového kompresního poměru, jako ztrátová komprese a proto je její použití omezené. Množství redundance také závisí na charakteru obsahu a účinnost komprese je tak různá. Může ale dobře posloužit např. ke zmenšení objemu video materiálu, který je určen k dalšímu zpracování.

Barevné modely a transformace

Základním barevným modelem je RGB. Kombinací červené, zelené a modré lze "namíchat" požadovaný odstín barvy (proto se tomuto modelu také říká aditivní). V případě formátu RGB24 je každá složka reprezentována 8-bity a může nabývat hodnot 0 až 255. Kombinací s ostatními složkami vznikne 16 777 216 odstínů barev pro každý pixel v obrazu. Existuje ještě varianta s alpha kanálem, ale zde se omezíme pouze na 3 základní složky.

Složky modelu RGB však obsahují závislost mezi sebou (tzv. korelaci). Uvažujme např. změnu jasu v jednom pixelu. U všech tří složek musí dojít k modifikaci hodnoty, aby se získal požadovaný odstín. Mnohem vhodnější jsou proto barevné modely, které oddělují jas od barevné informace. Změna jasu tak znamená změnu pouze jedné ze tří složek. Procesu převodu barevného modelu se říká barevná transformace. Existuje více typů. Známá je např. transformace YUV (Y je jas, U a V jsou chromatické složky). Avšak pro účely bezeztrátové komprese se hodí pouze ty transformace, které zaručují zpětný převod do RGB bez jakýchkoliv změn. Takovou transformací je např. LOCO-I (součást standardu JPEG-LS), nebo RCT (standard JPEG 2000). Jde jen o jednoduchý přepočet, který ovšem zajistí mnohem lepší výsledky komprese.

Prediktory

Obraz v digitální podobě typicky obsahuje tzv. prostorovou redundanci. Pokud vybereme libovolný pixel a porovnáme jej s jeho okolím, je velká pravděpodobnost, že okolní pixely budou velmi podobné, nebo dokonce stejné. Toho je možné využít při kompresi. Pokud lze hodnota pixelu odvodit z okolních pixelů, nemusí se kódovat celá hodnota, ale jen rozdíl. Původní hodnota lze poté dopočítat přičtením nebo odečtením rozdílu. Máme tedy první způsob, jak zmenšit objem dat beze ztráty.

Prostým kódováním rozdílů lze sice dosáhnout určité komprese, avšak mnohem účinnější jsou tzv. prediktory. Prediktor odhaduje hodnotu právě zpracovávaného pixelu pomocí určitého okolí předchozích pixelů. Poté se vypočte rozdíl od skutečné hodnoty, což je chyba predikce, které se prediktor dopustil a tato chyba je poté zakódována. Při dekódování proběhne stejný proces, avšak k predikované hodnotě je tentokrát přičtena chyba predikce, čímž se získá původní hodnota. Důležitou podmínkou je, aby prediktor uvažoval pouze okolí, které již prošlo zpracováním. Stejné okolí musí mít k dispozici i dekódovací strana, aby proces probíhal symetricky. Čím přesnější je odhad, tím lze dosáhnout lepšího kompresního poměru. Požadavkem tedy je, aby se prediktor mýlil co nejméně.

Díky vlastnostem obrazu (prostorová redundance) jsou prediktory schopny ve většině případů odhadovat s přesností 100% (nulová chyba predikce). Větší nebo menší chyby predikce se objevují se stále klesající četností. Jednotlivé četnosti se mohou měnit podle charakteru obrazu, avšak základní vlastnost většinou zůstává - nulových chyb predikce je nejvíce. Výjimkou může být zašuměný obraz, nebo v extrémním případě samotný šum. Zde tento postup selhává, protože hodnoty pixelů jsou náhodné a nelze je odhadnout z jejich okolí. K takovým extrémním situacím ale dochází málokdy.

Predikce z více snímků

Protože jde o kompresi videa, nabízí se možnost využít více snímků ke zlepšení predikce. Mohou totiž nastat situace, kdy jsou rozdíly mezi snímky minimální, nebo dokonce žádné. Prediktor s možností porovnání více snímků se označuje jako 3D prediktor. Zde jsou dva snímky z pracovní plochy, které mohou ve videu následovat hned za sebou.

Červený rámeček vyznačuje místo v obrazu, kde došlo ke změně mezi snímky. Změnila se pozice okna, ale okolí zůstává zcela stejné. Pokud prediktor udělá odhad podle předchozího snímku, je vidět, že se v mnoha místech obrazu trefí na 100%. 2D prediktor pracující pouze s okolím v jednom snímku by se dopustil výrazně větších chyb kvůli různým hranám a přechodům v obrazu. S použitím 3D prediktoru výrazně klesne počet chyb různých od nuly. 3D prediktor tak může odstraňovat redundanci mezi snímky - informace, které jsou již známy z předchozích snímků a není třeba je kódovat (jde o interframe kompresi). Má to však určitá omezení, protože snímky mohou být i velmi odlišné (např. při otevření nějakého okna na celou obrazovku) a 3D predikce by mohla výsledky zhoršovat. V mé práci jsem prováděl různé experimenty, až jsem došel k řešení, které kombinuje 2D a 3D prediktor (podrobnější popis v BP).

Entropické kodéry

Z četností chyb predikce lze odvodit rozdělení pravděpodobnosti. Nulové chyby jsou nejpravděpodobnější, zatímco u větších chyb pravděpodobnost postupně klesá. Toho lze využít při kódování. Symbolům s největší četností se přidělí nejkratší kód a symbolům s menší četností delší kód. Takovému postupu se říká entropické kódování.

Golombovo-Riceovo kódování

Tento kód patří do skupiny kódů, které pracují s fixním pravděpodobnostním modelem. To je případ popsaný výše, kdy se vždy předpokládá, že četnost nulových chyb predikce bude největší. Číslům blízko nuly se přiděluje nejkratší kód a větším číslům kód delší. Protože kódování pracuje pouze s celými nezápornými čísly, je nutné nejdříve namapovat záporná čísla na kladná (chyby predikce moho být i záporné). Záporná čísla jsou vynásobena -2 a od výsledku je odečtena 1. Kladná čísla jsou pouze vynásobena dvěma. Toto jednoduché mapování způsobí, že ze záporných čísel se stanou kladná lichá a z kladných čísel kladná sudá. Zpětné mapování je rovněž jednoduché.

Golombovo-Riceovo kódování je založeno na dělení čísel a na kódování výsledku a zbytku po dělení. Dělitel je ždy nějaká mocnina čísla 2. Výhodou je, že se tím usnadní implementace (operace se dají realizovat bitovými posuny). Výsledek po dělení se zakóduje unárně, zbytek po dělení pak binárně na určitý počet bitů, který se odvíjí od velikosti dělitele. Výsledek a zbytek jsou vždy odděleny jedním nulovým bitem. Pro větší čísla je vhodné volit větší dělitel, pro menší čísla naopak menší. Nějkratšího kódu lze dosáhnout při kódování nuly s dělitelem 1. V takovém případě kód tvoří pouze oddělovací nulový bit, protože výsledek i zbytek po dělení je nula. Zde si můžete všimnout 8-násobné úspory dat proti běžné reprezentaci čísla v jednom bajtu (8 bitů).

Aritmetické kódování

Jde o další způsob entropického kódování. Zde je přiřazován jeden kód celému vstupnímu souboru. Pracuje se s určitým intervalem hodnot. Vstupní soubor se čte symbol po symbolu a pravděpodobnost každého symbolu je použita ke zúžení intervalu. Z výsledného intervalu pak stačí vzít libovolné číslo (takové které lze nejlépe reprezentovat). Čím užší interval je potřeba vyjádřit, tím je kód delší. Symboly s větší pravděpodobností výskytu zužují interval méně, zatímco symboly s nižší pravděpodobností více. Velkou výhodou tohoto postupu je dosahovaný kompresní poměr. Golombovo-Riceovo kódování přidělovalo při nejlepším 1 bit/symbol (případ s nulou). Aritmetické kódování je však schopno přidělovat i kódy kratší než 1 bit, protože nepracuje se symboly samostatně, ale kóduje celý jejich soubor.

Při realizace však nastává problém s konečnou přesností desetinných čísel. Interval nelze zmenšovat do nekonečna. Celý algoritmus je proto nutné realizovat pomocí celočíselné aritmetiky. Jako interval dělení je použita celočíselná 32-bitová proměnná. Při kódování k sobě konvergují horní a dolní mez intervalu a je nutné provádět úpravy pomocí E1, E2 a E3 škálování. Výstupem kodéru jsou jednotlivé bity, které se skládají do větších celků (bajt, word, dword) a tyto celky se ukládají do souboru.

Tímto končí velmi stručný úvod do teorie bezeztrátové komprese. Chcete-li se dozvědět více, můžete si přečíst bakalářskou práci, která všechny postupy podrobněji rozebírá. Odkaz je uveden na konci článku.

Vytvořený bezeztrátový kodek

Za úkol bylo naprogramovat kodek pro framework VfW a nebo DirectShow použitelný v systému Windows. Z implementačních detailů bych zde zmínil vícevláknové zpracování. Protože je proces kódování velmi náročný, je vhodné, když se na něm podílí více jader procesoru. První varianta počítala s rozdělením obrazu na 4 části a jejich nezávislé zpracování pomocí 4 vláken. Tento způsob rozdělení nevyžaduje žádnou synchronizaci ani komunikaci mezi vlákny během činnosti. Stačí synchronizovat pouze jejich spuštění a ukončení. Každé vlákno produkuje svůj datový proud, jehož velikost není předem známá (velikost datového toku je silně závislá na charakteru obrazu, který zrovna prochází zpracováním). Datové proudy je poté nutné spojit do jednoho. Tím vzniká určitá režie navíc. Přesto však tento způsob využití paralelizace přináší významné zrychlení.

V původní verzi byl obraz rozdělen podle poloviny vertikálního a horizontálního rozměru. Později jsem provedl úpravu na 8 vláken, což už bylo nad rámec bakalářské práce, takže tato úprava tam popsána není. Obraz je rozdělen na 8 pruhů, které mají plné horizontální rozlišení. Každý pruh dostane ke zpracování jedno z 8 vláken. Postup je jinak stejný. Spustit vlákna a poté spojit jejich datové proudy. Dostavilo se další zrychlení a téměř ve všech případech lze dosáhnout zpracování 720p videa v reálném čase (30 fps). U vyšších rozlišení je rychlost zatím nižší. Kodek využívá 8 vláken od verze 1.1. Drobnou nevýhodou je mírné zhoršení kompresního poměru, ale jen v řádu desetin procent.

Využití bezeztrátové interframe komprese při nahrávání obrazovky

Obraz vykreslovaný na monitor v prostředí operačního systému je velmi vhodný materiál, na kterém může profitovat interframe komprese. Pokud uživatel zrovna nehraje nějakou hru, ale provádí běžnou práci, nedochází příliš často ke změnám celé pracovní plochy. Ve spoustě případech je jediným rozdílem mezi snímky pohyb kurzoru myši, změna textu v některém okně apod. To jsou rozdíly minimální.

Běžně používané bezeztrátové kodeky používají pouze intraframe kompresi (komprimují každý snímek samostatně bez návaznosti na předchozí snímky). V případě nahrávání plochy to znamená, že není brán ohled na počet změn mezi snímky a velikost komprimovaných dat určuje pouze charakter obrazu. Pokud bychom porovnali nahrávku s žádnými změnami mezi snímky a nahrávku s mnoha změnami, jejich velikosti by byly podobné.

Vlastní kodek se zaměřil na snížení redundance mezi snímky. Dva sousední snímky jsou porovnávány mezi sebou a dochází-li v některých místech ke shodám, jsou tato místa predikována přesně, což umožní výrazně snížit datový tok videa. Mějme situaci, kdy se v obrazu změnil pouze kurzor myši. Intraframe kodek by zakódoval celé snímky bez ohledu na minimální změnu. Interframe kodek zakóduje první snímek celý a následující snímky obsahují pouze změny, které nastaly od referenčního (klíčového) snímku. Zjednodušeně se dá říci, že rozdílové snímky by v tomto případě obsahovaly pouze informace o změně polohy kurzoru. Zbytek snímku zůstal stejný a tak není potřeba jej znovu kódovat.

CamStudio

K otestování kodeku pro nahrávání obrazovky jsem použil program CamStudio ve verzi 2.7.4.
camstudio.org

Vlastní kodek má označení JK Lossless Video Codec a je po instalaci k dispozici v menu Options - Video options.

Nastavení Quality a Set Key Frames Every není třeba měnit, kodek se tím neřídí. Interval klíčových snímků lze měnit v konfiguračním dialogu kodeku (defaultní hodnota je 120) a je tam možné i přepínat mezi Golomb. Riceovým kodérem (rychlý, komprese průměrná), nebo aritmetickým kodérem (pomalejší, ale mnohem větší komprese). Nastavení kvality není třeba řešit vůbec, protože k žádné ztrátě kvality nedochází. Kodek je již nastaven tak, aby podával co nejlepší vysledky, takže do konfigurace není potřeba zasahovat.

Testování

Vlastní kodek jsem porovnával s jinými bezeztrátovými kodeky, konkrétně CamStudio Lossless Codec v1.5 (přímo od tvůrců tohoto programu) a Lagarith 1.3.27 (velmi rychlý bezeztrátový kodek). Nahrávání probíhalo na sestavě s CPU AMD FX-8320, 8 GB RAM DDR3, Radeon R9 270X a OS Windows 7 HP SP 1. Plocha byla nahrávána v plném rozlišení 1920×1080 px se snímkovou frekvencí, která kolísala mezi 8 a 10 fps.

První testovací případ

Na ploše je okno CamStudio, správce úloh a Visual studio. Ve Visual Studiu přepínám zobrazení jednotlivých zdrojových souborů a scrollováním je procházím. Délka videa je 1 minuta.

Výsledná velikost souborů:

Lagarith: 398 686 kB (100 %)
CamStudio Lossless Codec: 86 732 kB (21,75 %)
JK Lossless Video Codec: 32 955 kB (8,26 %)

Druhý testovací případ

Okna CamStudio a správce úloh zůstávají. V pravé části obrazovky je přehráváno video. Malé okno přehrávače každých 15 s zvětším, až zabírá téměř celou plochu. Délka videa je 1 minuta.

Výsledná velikost souborů:

Lagarith: 974 873 kB (100 %)
CamStudio Lossless Codec: 708 590 kB (72,68 %)
JK Lossless Video Codec: 276 454 kB (28,35 %)

V tomto testu docházelo postupně k větším změnám mezi snímky. Z výsledků je vidět, že velikost souborů narostla a rozdíl oproti kodeku Lagarith se zmenšil.

Třetí testovací případ

Tento test ukazuje, jak velký potenciál se skrývá v bezeztrátové interframe kompresi. Opět zůstávají okna CamStudio a správce úloh. V pravé části obrazovky je otevřen prohlížeč pdf a v textu bliká kurzor. Kromě něj se na obrazovce mění ještě graf vytížení procesoru ve správci úloh a text v okně CamStudio. Jinak zůstává plocha zcela beze změn. Délka opět 1 minuta.

Výsledná velikost souborů:

Lagarith: 665 280 kB (100 %)
CamStudio Lossless Codec: 77 760 kB (11,68 %)
JK Lossless Video Codec: 11 857 kB (1,78 %)

Intraframe kodek Lagarith zpracovává každý snímek zvlášť a je mu jedno, jestli dochází mezi snímky ke změnám. CamStudio Lossless Codec již nějaké změny reflektuje a dokáže výrazně snížit velikost dat. Vlastní kodek však dokázal odstranit nejvíce redundantních informací a velikost videa v tomto případě redukoval o 98,22 % proti kodeku Lagarith a o 84,75 % proti kodeku CamStudio. A stále bez jakékoli ztráty kvality.

Průměr všech výsledků - velikost souborů

Shrnutí

Podařilo se vytvořit bezeztrátový video kodek s interframe kompresí a vícevláknovým zpracováním. Testy ukázaly, že v situacích, jako je záznam obrazovky, může video materiál obsahovat spoustu redundance mezi snímky a jejím odstraněním lze dosáhnout výrazně lepší komprese. S použitím vícevláknového zpracování zvládá kodek zpracovávat obraz i ve vyšším rozlišení. Vytvořený kodek má k dokonalosti samozřejmě daleko, nicméně je plně funkční a budete-li s ním experimentovat, můžete napsat do komentářů vaše zkušenosti. Pokud se ukáže mezi uživateli zájem, není problém ve vývoji pokračovat a kodek vylepšovat.

Kodek je ve 32-bitové i 64-bitové verzi a lze jej použít v programech, které umí pracovat s VfW kodeky (např. editory VirtualDub, Movie Maker 2012, Vegas Pro/Movie Studio a přehrávače WMP, MPC-HC a BS player). Kodek není omezen pouze k nahrávání obrazovky. Testy v bakalářské práci ukázaly, že i v jiných situacích existuje spousta redundance mezi snímky, kterou lze odstranit (animované filmy, záznamy z počítačových her).

Zdroj

Jan Kafka: Bezeztrátová komprese videa, bakalářská práce, Brno, FIT VUT v Brně, 2015
http://www.fit.vutbr.cz/study/DP/BP.php?id=9988&y= 2014

Kodek ke stažení (včetně zdrojových kódů). Verze 1.1 využívá 8 vláken.
~xkafka00