Kompresni algoritmy grafiky

Report
Kompresní algoritmy grafiky
Jan Janoušek
F11125
K čemu je komprese dobrá?
• Pokud je třeba
skladovat datově
náročné soubory. Např.
pro záznam obrazu,
hudby a hlavně videa je
třeba skladovat
překvapivě mnoho dat.
• Při přenosu dat po síti.
Zmenšením datové
náročnosti se
minimalizuje čas
potřebný k přenosu.
Základní pojmy
Data
• „Jakékoliv fyzicky (materiálně)
zaznamenané znalosti
(vědomosti), poznatky,
zkušenosti nebo výsledky
pozorování procesů, projevů,
činností a prvků reálného
světa (reality).“
• „Surovina, z níž se tvoří
informace.“
Zdroj:
http://cs.wikipedia.org/wiki/Data
Informace
• Data která dávají smysl.
Základní pojmy
Kompresní algoritmus
• Postup, který minimalizuje
množství dat potřebné k
popsání dané informace.
Entropie
• Míra množství informace
• Všechny kompresní
algoritmy využívají faktu, že
data často obsahují řadu
nadbytečných informací. S
odstraňováním těchto
redundantních informací se
zvyšuje entropie dat.
Základní pojmy
Kompresní poměr k
• Jedná se o poměr mezi
velikostí dat po a před
kompresí nebo o poměr
zkomprimovaného
datového toku k
nezkomprimovanému.
Kompresní zisk z
• Kompresní zisk je dán
vztahem z=1-k a určuje tedy,
kolik dat bylo kompresí
„ušetřeno“. V případě, že
kompresní algoritmus zvětší
objem dat (kompresní
poměr je větší, než jedna),
je kompresní zisk záporný.
Základní pojmy
Bezztrátový kompresní
algoritmus
• Z komprimovaných dat lze
získat původní data bez
jakékoliv ztráty kvality.
Obvykle méně účinná, než
ztrátová komprese.
Ztrátový kompresní algoritmus
• Z komprimovaných dat
nelze zrekonstruovat
původní data, protože při
komprimaci dochází k
určitému zkreslení. Při
komprimaci grafiky se
využívá znalostí
psychovizuálního model.
Výhody/nevýhody
Ztrátové
• Z komprimovaných dat
nelze zrekonstruovat
původní data
• Pro obrázky s vysokým
počtem barev (fotky) lepší
kompresní poměr
Bezztrátové
• Nehodí se pro fotky a spol.
• Z komprimovaných dat lze
zrekonstruovat původní
data
• U obrázků z nízkým počtem
barev obvykle lepší
kompresní poměr i kvalita.
Bezztrátové kompresní algoritmy
• Slovníkové metody komprese
– Komprimovaná data jsou ukládána do „slovníku“.
Při opakování dat, která jsou už ve slovníku
obsažena, se místo dat samotných uvede odkaz na
pozici ve slovníku
• Statistické metody komprese
– Statistické metody komprese jsou založeny na
tom, že pro nejčastěji se vyskytující znaky jsou
vytvářeny nejkratší odkazy.
• Ostatní metody komprese
Ostatní metody komprese
RLE
• Vstup:
– wwwwwbwwwbbbbwbbbbbb
• Výstup:
– 5w1b3w4b1w6b
• Kompresní poměr (v tomto
případě):
–
12
20
= 0,6
Vlastnosti RLE
• Velmi záleží na typu obrázku
• Záleží i na orientaci obrázku
• V některých případech
může být i záporný
kompresní zisk
Slovníkové metody komprese – LZ77
„Podle principu je nazývána metodou posuvného okna. Pro
lepší vysvětlení předpokládejme, že budou data
reprezentována řetězcem. Posuvné okno (sliding window) je
rozděleno na část, kde už jsou zakódovaná data, a na část, kde
jsou ta nezakódovaná.
Kódování začíná nastavením sliding window na řetězec, který
má být zakódován, tak, že část pro již zakódovaná data je
prázdná a druhá část je naplněna řetězcem (netřeba celým).
Hledá se shoda co nejdelšího řetězce (počínajíce rozmezím) z
nezakódované části s řetězcem v zakódované části. V případě
shody je nový podřetězec zakódován uspořádanou dvojicí (p,
n), kde p je pozice prvního znaku v zakódované části, a n je
délka shodného podřetězce. “
Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování.
Slovníkové metody komprese – LZ77
Příklad:
Vstupní text: leze leze po železe
Výstupní text: leze l(2,3) po že(5,4)
Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování.
Zdroj: Večerka, Arnošt. Komprese dat
Slovníkové metody komprese – LZW84
• Použití:
– Gif, tiff, zip
• Na 20 let byl chráněn
patentem
Zdroj: Foltýnek, Tomáš a Přichystal,
Jan. Komprimace a šifrování.
Statistické metody komprese
Huffmanovo kódování
„Konvertuje znaky vstupního souboru do bitových řetězců
různé délky. Znaky, které se ve vstupním souboru
vyskytují nejčastěji, jsou konvertovány do bitových
řetězců s nejkratší délkou (nejfrekventovanější znak tak
může být konvertován do jediného bitu), znaky, které se
vyskytují velmi zřídka, jsou konvertovány do delších
řetězců (mohou být i delší než 8 bitů).
Nejjednodušší metoda komprese touto metodou probíhá
ve dvou fázích. První projde soubor a vytvoří statistiku
četností každého znaku. Ve druhé fázi se využije této
statistiky pro vytvoření binárního stromu a k následné
kompresi vstupních dat.“
Zdroj: http://cs.wikipedia.org/wiki/Huffmanovo_k%C3%B3dov%C3%A1n%C3%AD
Ztrátové kompresní algoritmy
• Ztrátové kompresní algoritmy se používají
tam, kde nevadí určité zkreslení informací
(obraz, audio, video).
• Psychovizuálním model pro obrazová data
• Psychoakustický model pro zvuková data
Psychoakustický model
• Klíčové znalosti pro ztrátovou kompresi
obrazu:
– Lidské oko je mnohem citlivější na jas barvy, než
na její odstín.
– Lidské oko má větší citlivost na nízké frekvence,
než na vysoké.
• Při ztrátové kompresi jsou tedy přednostně
komprimovány (a tedy zkreslovány) právě tyto
informace.
Kompresní algoritmus JPEG
• Pro velké obrázky z mnoha barvami se
bezztrátové komprimační algoritmy nehodí.
• Algoritmus využívá tzv. diskrétní kosinová
transformace (DCT)
Kompresní algoritmus JPEG
„Metoda je vhodná především pro kódování fotografií, u
nichž sousední pixely mají sice odlišné, ale přesto blízké
barvy. Snižování kvality se projevuje potlačováním rozdílů
v blízkých barvách. U metody DCT je kompresní poměr
řízen požadavkem na výši kvality dekomprimovaného
obrazu. V praxi se ukazuje, že snížení kvality na 75 % je
pro většinu uživatelů nepozorovatelné, přitom
kompresní poměr v takovém případě může být až 25:1.“
Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a
šifrování.
Postup kompresního algoritmu
1. Transformace barev z
barevného prostoru RGB
do YCBCR – kvůli aplikaci
komprese využívající
psychovizuálního modelu
(barevné složky budou ve
výsledku více zkreslené,
než složky jasové)
2. Podvzorkování
barevných složek –
redukce objemu dat
zprůměrováním barevných
složek sousedních pixelů
Postup kompresního algoritmu
3. Rozdělení obrazu na
čtverce 8 × 8
4. Aplikace dopředné
diskrétní kosinové
transformace na prvky
čtvercové matice vzniklé v
minulém kroku
Postup kompresního algoritmu
5. Kvantování koeficientů
matice – v tomto kroku se
určuje stupeň komprese
obrazu)
6. Zkomprimování
kvantovaných koeficientů
pomocí Huffmanova
kompresního algoritmu –
po předchozím kroku má
mnoho prvků matice
nulovou hodnotu
Transformace barev
• Transformace z barevného prostoru RGB do
barevného prostoru YCBCR je přesně
definována ve specifikaci JFIF, ve které jsou
uvedeny jak rovnice pro převod z barevného
prostoru RGB do YCBCR, tak rovnice pro převod
inverzní.
Transformace barev
• Specifikace předpokládá, že složky RGB a
YCBCR jsou reprezentovány jako celá čísla v
rozsahu 0 až 255.
• Ačkoliv tato transformace je v principu
bezztrátová, tyto samotné převody jsou do
určité míry ztrátové, protože dochází k
zaokrouhlování výsledků na celá čísla.
YCBCR
Jasová složka barvy – Y (luma)
Barevné složky – CB a CR (chroma)
 Na tuto složku je lidské oko
nejvíce citlivé a podléhá
tedy nejmenší kompresi.
• Barevné složky pro modrou
a červenou barvu.
•  = −0,1687 −
0,3313 + 0,5 + 128
•  = 0,5 − 0,4187 +
0,0813 + 128
• Barevná složka pro zelenou
se neuvádí, protože je jí
možno z Y, CB a CR dopočítat.
  = 0,299 + 0,587 +
0,114
Zpětný převod
  =  + 1,402 ×  − 128
  =  − 0,34414 ×  − 128 − 0,71414 ×
 − 128
  =  + 1,772 ×  − 128
Podvzorkování barevných složek
• Protože lidské oko je mnohem méně citlivé na
barvy, než na jas, využívá se podvzorkování
(nebo také redukce) barvonosných složek pro
zvýšení efektivity kompresního algoritmu.
• Jedná se o první významněji ztrátový převod,
protože informace o barvách v tomto procesu
zanikají.
Podvzorkování barevných složek
Podvzorkování funguje tak, že z hodnot
barevných složek sousedních pixelů je spočítána
průměrná hodnota. Jsou přípustné dvě
možnosti:
Podvzorkování barevných složek
• Průměrování hodnot
dvou sousedních pixelů
na řádku.
– Úspora dat ze 6 bytů na
4, kompresní poměr tedy
asi 67%.
• Průměrování hodnot
pixelů tvořící čtverec
2×2
– Úspora dat ze 12 bytů na
6, kompresní poměr tedy
50%.
Rozdělení obrazu na čtverce 8 × 8
• Obrázek je rozdělen na
čtvercové bloky o
rozměrech 8 × 8 pixelů.
• Tohoto rozdělení lze
později využít pro rychle
generování
náhledového obrázku.
Rozdělení obrazu na čtverce 8 × 8
• Pokud není výška nebo šířka obrázku dělitelná
osmi, je nutné tyto „okrajové“ bloky vhodně
doplnit do požadovaného rozměru 8 × 8
pixelů. Způsob doplnění je ponechán na
konkrétním software, který obrázek
zpracovává. Obvykle se používá zrcadlení již
existujících pixelů.
Aplikace dopředné diskrétní kosinové
transformace
• Nyní máme matici 8 × 8
pixelů, kde každý prvek
této matice obsahuje
informaci o jasu (složka
Y) a o barvě (složky CB a
CR).
• Od všech jednotlivých
složek se odečte
hodnota 128, čímž se
přetransformuje jejich
rozsah do intervalu -128
až 127
Aplikace dopředné diskrétní kosinové
transformace
• Jednotlivé složky se
budou nyní dopřednou
DCT zpracovávat
samostatně.
• DCT je nutno provést
celkem třikrát: jednou
pro jasovou složku Y a
dvakrát pro barevné
složky CB a CR.
• Účelem DCT je
přetransformovat tuto
matici do matice nové,
ve které budou, z
hlediska lidského
vnímání, nejdůležitější
prvky uvedeny v levém
horním rohu a směrem
k rohu levému bude
jejich důležitost klesat.
Aplikace dopředné diskrétní kosinové
transformace
• Transformace se pro jednotlivé prvky provádí
pomocí rovnice:
•
  , 
–
•
1
2
a   =   = 1 pro ,  ≠ 0

–
•
Funkce, pro které platí:  0 =
Rozměr matice. V tomto případě tedy platí  = 8.
 , 
– Hodnota matice v bodě , .
Aplikace dopředné diskrétní kosinové
transformace
• Výsledkem transformace je matice, která
v levém horním rohu obsahuje tzv.
stejnosměrný koeficient (DC), u něhož jsou
hodnoty Y, CB a CR průměrné celého bloku
matice.
Aplikace dopředné diskrétní kosinové
transformace
• Výsledkem transformace je matice, která
v levém horním rohu obsahuje tzv.
stejnosměrný koeficient (DC), u něhož jsou
hodnoty Y, CB a CR průměrné celého bloku
matice.
Aplikace dopředné diskrétní kosinové
transformace
• Ostatní koeficienty jsou tzv. střídavé (AC). Čím
vyšší frekvenci tyto koeficienty mají, tím je
jejich důležitost nižší a mohou se
v následujícím kroku více zkomprimovat (a
tedy více zkreslit jejich hodnota).
Kvantování koeficientů matice
• Až na proces podvzorkování barvonosných
složek dosud algoritmus dosud neprováděl
žádnou kompresi. Ta nejdůležitější část
komprese – kvantování koeficientů tabulky –
se provádí právě zde.
Kvantování koeficientů matice
• Z předchozího kroku je připravena matice,
která má v určité části důležité koeficienty a
v jiné méně důležité až téměř nevýznamné.
Každý prvek této matice se celočíselně vydělí
hodnotami z tzv. kvantizační tabulky.
Kvantování koeficientů matice
• Kvantizační tabulky obsahují
nízké hodnoty u důležitých
členů (nízkofrekvenčních) a
vysoké hodnoty u důležitých
členů (vysokofrekvenčních).
Po tomto procesu tedy
vzniknou u
vysokofrekvenčních prvků
převážně nuly.
Zdroj:
http://www.root.cz/clanky/p
rogramujeme-jpegkvantizace-dct-koeficientu/
Kvantování koeficientů matice
• Výsledná kvalita závisí
převážně na použité
kvantizační tabulce.
Proto obvykle existují
pro různé stupně
komprese různé
tabulky.
• Kvantizační tabulky
nejsou dány normou, a
proto každý výrobce
softwaru může zvolit
vlastní sadu
kvantizačních tabulek.
Kvantování koeficientů matice
• Často aplikace neobsahuje pro každý stupeň
komprese specifickou kvantizační tabulku.
Tento problém se řeší pomocí lineární
interpolace ze známých příslušných hodnot
ostatních kvantizačních tabulek.
Kvantování koeficientů matice
Zdroj: http://www.root.cz/clanky/programujeme-jpeg-kvantizace-dctkoeficientu/
Zkomprimování kvantovaných
koeficientů
• V aktuálním stavu obsahuje kvantovaný blok 8
× 8 pixelů mnoho pixelů v části
vysokofrekvenčních členů. Tento blok nyní
stačí už pouze zkomprimovat pomocí
Huffmanova kompresního algoritmu.
Zkomprimování kvantovaných
koeficientů
• Matice je komprimována
postupně „cik-cak“ od členu s
nejnižší frekvencí (stejnosměrný
člen – DC) po člen s nejvyšší
frekvencí. Tímto postupem
Huffmanovo kódování dosáhne
nejvyšší účinnosti díky opakování
mnoha nul po sobě.
Zdroj:
http://www.root.cz/clan
ky/programujeme-jpegkvantizace-dctkoeficientu/
Zkomprimování kvantovaných
koeficientů
• Tímto krokem je samotná komprimace
dokončena. Nyní zbývá už jen data uložit v
podobě dle specifikace, přidat hlavičku a
ostatní metadata (EXIF, IPTC apod.).
Zdroje
1.
2.
3.
4.
5.
6.
7.
Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování. [Online] [Citace: 6. 4
2012.] https://akela.mendelu.cz/~foltynek/KAS/elearning/KAS_PDF.pdf.
Večerka, Arnošt. Komprese dat. [Online] 2008. [Citace: 6. 4 2012.]
phoenix.inf.upol.cz/esf/ucebni/komprese.pd.
Tišnovský, Pavel. Programujeme JPEG: diskrétní kosinová transformace (DCT).
Root.cz. [Online] 4. 1 2007. [Citace: 6. 4 2012.]
http://www.root.cz/clanky/programujeme-jpeg-diskretni-kosinova-transformacedct/.
—. Programujeme JPEG: Kvantizace DCT koeficientů. Root.cz. [Online] 11. 1 2007.
[Citace: 6. 4 2012.] http://www.root.cz/clanky/programujeme-jpeg-kvantizacedct-koeficientu/.
Bařina, David. Ztrátová komprese obrazu. FIT VUT Brno. [Online] 2007. [Citace: 6.
4 2012.] www.fit.vutbr.cz/study/DP/rpfile.php?id=5779.
Data compression ratio. Wikipedia. [Online] [Citace: 6. 4 2012.]
http://en.wikipedia.org/wiki/Data_compression_ratio.
Komprese Dat. Wikipedia. [Online] [Citace: 1. 4 2012.]
http://cs.wikipedia.org/wiki/Komprese_dat.

similar documents