Lektor:
Kurz:
KOMPRESE STATICKÝCH OBRAZŮ
STANDARD JPEG
VIDEOTECHNIKA A MULTIMÉDIA
Kamil Říha
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
2 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Komprese obrazu: základní myšlenka
• Bezztrátová komprese: odstraňuje statistickou nadbytečnost (redundance),
obraz je možné rekonstruovat úplně, bez jakýchkoli změn.
• Ztrátová komprese: odstraňuje nevratně takovou informaci, která nemá pro
daného diváka v dané situaci význam – jsou irelevantní. Obraz není možné
zrekonstruovat v původní podobě.
• Některé malé detaily v obraze není lidský zrakový orgán schopen vnímat, ty
je možné selektivně odstranit a tím uspořit paměťovou/přenosovou kapacitu.
• Jemné jasové detaily odpovídají vysokým frekvencím obrazového signálu: je
tedy na místě použít vhodnou transformační metodu pro z prostorové do
frekvenční oblasti a v této oblasti vybrat pouze důležité frekvence.
• V praxi používána zejména diskrétní kosinová transformace (DCT) v
kompresi JPEG, diskrétní vlnková transformace (DWT) v JPEG 2000.
• Díky menší citlivosti oka na barvy než na jas je možné v prvním kroku
komprese podvzorkovat barevné kanály (první ztrátový krok).
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
3 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií







M
x
yx,f π4cos)(
DFT funkce dvou proměnných - 2D DFT
jednoduché příklady 2D amplitudových spekter
   ),(, yxfvuF F
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
4 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií







N
y
yxf π4cos),(
DFT funkce dvou proměnných - 2D DFT
jednoduché příklady 2D amplitudových spekter
   ),(, yxfvuF F
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
5 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií













N
y
M
x
yxf π4cos),(
DFT funkce dvou proměnných - 2D DFT
jednoduché příklady 2D amplitudových spekter
   ),(, yxfvuF F
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
6 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií













N
y
M
x
yxf π4cos),(
DFT funkce dvou proměnných - 2D DFT
jednoduché příklady 2D amplitudových spekter
   ),(, yxfvuF F
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
7 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií



















N
y
M
x
M
x
yxf π8sinπ4sin),(
DFT funkce dvou proměnných - 2D DFT
jednoduché příklady 2D amplitudových spekter
   ),(, yxfvuF F
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
8 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
DFT funkce dvou proměnných - 2D DFT
příklad 2D DFT spektra reálného obrazu
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
9 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Standard JPEG (Joint Picture Expert Group)
• definován ve standardech ISO/IEC 10918 a ITU T.81
• první mezinárodní standard pro kompresi barevných, šedotónových a černo-bílých
digitálních statických obrazů
• v praxi soubory s příponou většinou *.jpg nebo *.jpeg
• podporuje zejména ztrátovou kompresi pomocí diskrétní kosinové transformace (DCT)
• umožňuje i bezeztrátovou kompresi
• je navržen zejména pro kompresi fotografických nebo fotorealistickýh snímků
• nepodporuje označení průhledné barvy
• pokročilejší JPEG 2000 využívající DWT se v praxi příliš nepoužívá (patentované algoritmy)
• Celkem 4 módy kódování:
• základní mód – ztrátové kódování (kompresní poměr ~1:20),
• rozšířený mód – ztrátové kódování, progresivní kódování, DC všech bloků, 1. AC všech bloků, atd.,
• bezeztrátové kódování,
• hierarchické kódování – několik prostorových rozlišení.
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
10 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
RGB
obraz
kvantizace
Huffmanovo
kódování
model
YCbCr
podvzorkování
4:2:0
bloky
8×8
2D-DCT
kvantizační
tabulky
čtení
cik-cak
Huffmanovy
tabulky
DATA
DPCM
RLE
C(0)
C(63)
.
.
.
JPEG kodér
DPCM: difrenční PCM, kdy se kóduje jen rozdíl DC
složek jednotlivých bloků
RLE: Run-length encoding, kdy se uspoří data
v případě, kdy se znaky často opakují (nuly)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
11 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Diskrétní Fourierova transformace
   
 
1
1...2,1,0,,1,...2,1,0frekvence,ová...prostor
funkcediskrétnívanátransformo...
e
1 1
0
2


 



j
MxMuu
xf
xf
M
uF
M
x
M
x
uj π
By User:Bunzil via Wikimedia Commons from Wikimedia Commons
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
12 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Fourierova transformace v 1D
diskrétní Fourierova transformace (DFT)
Eulerův vztah proΘjΘjΘ
sincose 
 


1
0
π2
e
1 M
x
M
x
uj
xf
M
   















1
0
]π2π2[cos
1 M
x M
x
usinj
M
x
uxf
M
uF
     
kde,e uj
uFuF 

     
       spektrumfázovéjeReImtan
spektruméamplitudovjeImRe
1
22
uuu
uuuF




KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
13 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Diskrétní kosinová transformace
• upravená verze DFT, kdy je transformovaná funkce (obrazový řádek,
sloupec) upravena tak, aby byla sudá
• DFT sudé funkce obsahuje pouze kosinové složky
• sudá funkce: 𝑓 𝑥 = 𝑓 −𝑥
     

















1
0
21
0
1
]2sin2[cos
1 M
x
M
x
ujM
x
exf
MM
x
uj
M
x
uxf
M
uF
π
ππ
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
14 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Odvození DCT z DFT
   




1
0
21 M
x
M
x
uj
exf
M
uF
π
 
 
 





12pro12
10pro
MxMxMf
Mxxf
xf
nechť je transformovaná funkce symetricky rozšířená (sudá):
potom je její DFT:
   




12
0
2
2
2
1 M
x
M
x
uj
exf
M
uF
π
M
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
15 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Odvození DCT z DFT
     






12
2
21
0
2
2
12
11 M
Mx
M
x
ujM
x
M
x
uj
exMf
M
exf
M
uF
ππ
      





0
1
2
12
21
0
2
2 11
Mm
M
mM
ujM
x
M
x
uj
emf
M
exf
M
uF
ππ
xMm  12:substituce
   




12
0
2
2
2
1 M
x
M
x
uj
exf
M
uF
π
     







1
0
2
12
21
0
2
2 11 M
x
M
xM
ujM
x
M
x
uj
exf
M
exf
M
uF
ππ
M
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
16 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Odvození DCT z DFT
      





0
1
2
12
21
0
2
2 11
Mm
M
mM
ujM
x
M
x
uj
emf
M
exf
M
uF
ππ
     







1
0
2
12
21
0
2
2 11 M
x
M
xM
ujM
x
M
x
uj
exf
M
exf
M
uF
ππ
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
17 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
M
Odvození DCT z DFT
      





0
1
2
12
21
0
2
2 11
Mm
M
mM
ujM
x
M
x
uj
emf
M
exf
M
uF
ππ
     







1
0
2
12
21
0
2
2 11 M
x
M
xM
ujM
x
M
x
uj
exf
M
exf
M
uF
ππ
𝑓 𝑥
𝑒−𝑗2𝜋
𝑥
2𝑀pro první harmonickou:
2𝑀 − 1
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
18 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
N
Odvození DCT z DFT
      





0
1
2
12
21
0
2
2 11
Mm
M
mM
ujM
x
M
x
uj
emf
M
exf
M
uF
ππ
     







1
0
2
12
21
0
2
2 11 M
x
M
xM
ujM
x
M
x
uj
exf
M
exf
M
uF
ππ
𝑓 𝑥
pro první harmonickou:
2𝑀 − 1
𝑒−𝑗2𝜋
𝑥
2𝑀
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
19 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Odvození DCT z DFT
     







1
0
2
12
21
0
2
2 11 M
x
M
xM
ujM
x
M
x
uj
exf
M
exf
M
uF
ππ
   











1
0
2
12
2
2
2
2
1 M
x
M
xM
uj
M
x
uj
eexf
M
uF
ππ
M
x
uj
M
uj
M
x
uj
M
uj
M
M
uj
M
xM
uj
eeeeee 2
2
2
1
2
2
2
2
1
2
2
2
2
2
12
2 ππππππ




   










1
0
2
2
2
1
2
2
2
11
2
1 M
x
M
x
uj
M
uj
M
x
uj
M
uj
M
uj
eeeexfe
M
uF
πππππ
= 1
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
20 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Odvození DCT z DFT
   










1
0
2
2
2
1
2
2
2
11
2
1 M
x
M
x
uj
M
uj
M
x
uj
M
uj
M
uj
eeeexfe
M
uF
πππππ
   











1
0
2
21
2
211
2
1 M
x
M
x
uj
M
x
uj
M
uj
eexfe
M
uF
πππ 𝑒−𝑗𝜃 = cos 𝜃 − j ∙ sin 𝜃
𝑒 𝑗𝜃
= cos 𝜃 + j ∙ sin 𝜃
   







 

1
0
1
2
21
cos2
2
1 M
x
M
uj
M
x
uxfe
M
uF π
π
komplexní číslo
𝑥0
𝑥1
𝑥2
𝑥3
𝑥4
𝑥0
𝑥1
𝑥2
𝑥3
𝑥4
2𝑁 − 1
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
21 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Odvození DCT z DFT
   










1
0
2
2
2
1
2
2
2
11
2
1 M
x
M
x
uj
M
uj
M
x
uj
M
uj
M
uj
eeeexfe
M
uF
πππππ
   











1
0
2
21
2
211
2
1 M
x
M
x
uj
M
x
uj
M
uj
eexfe
M
uF
πππ 𝑒−𝑗𝜃 = cos 𝜃 − j ∙ sin 𝜃
𝑒 𝑗𝜃
= cos 𝜃 + j ∙ sin 𝜃
   







 

1
0
1
2
21
cos2
2
1 M
x
M
uj
M
x
uxfe
M
uF π
π
vykrátí se, když se zdrojová funkce
navíc „zředí“ nulami u lichých prvků
𝑥0
𝑥1
𝑥2
𝑥3
𝑥4
𝑥0
𝑥1
𝑥2
𝑥3
𝑥4
4𝑁 − 1
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
22 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
DCT použití v JPEG
• v každém bloku jsou 2D DCT
koeficienty vypočteny jako součet
všech vstupních vzorků,
váhovaných kosinovou funkcí
• výsledkem je tedy opět blok 8×8
• frekvenční koeficienty samy o
sobě tedy nepředstavují žádnou
kompresi, pouze jinou formu dat
• DC komponent (střední hodnota)
je umístěn v levém horním rohu
• čím větší vzdálenost od DC složky,
tím vyšší frekvence (detaily)
• samotná ztrátová komprese je
realizována při kvantování
By FelixH commonswiki via Wikimedia Commons from Wikimedia Commons
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
23 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
JPEG – kvantování
• prvky matice frekvenčních
koeficientů 𝐆 označme 𝑔𝑖,𝑗
• kvantizované koeficienty jsou
vypočteny pomocí prvků 𝑘𝑖,𝑗
kvantizační (empirické) tabulky
(viz příklad)
• kvantizované DCT koeficienty jsou
vypočteny:
𝑏𝑖,𝑗 = round
𝑔𝑖,𝑗
𝑘𝑖,𝑗
• kontrolní otázka: jak bude vypadat
tabulka pro 100% kvalitu, tedy pro
bezztrátovou kompresi?
By FelixH commonswiki via Wikimedia Commons from Wikimedia Commons
3 2 2 3 5 8 10 12
2 2 3 4 5 12 12 11
3 3 3 5 8 11 14 11
3 3 4 6 10 17 16 12
4 4 7 11 14 22 21 15
5 7 11 13 16 21 23 18
10 13 16 17 21 24 24 20
14 18 19 20 22 20 21 20
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
24 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
JPEG – kvantování
• příklad matice DCT koeficientů
před kvantováním:
1019 -4 2 0 -3 5 -5 3
-5 5 -2 -2 5 -5 4 -3
2 -2 1 0 -2 3 -2 2
1 -1 1 1 -2 1 -1 1
-3 3 -2 1 3 -5 5 -4
7 -7 1 3 -6 6 -5 3
-6 7 -2 -4 6 -6 5 -2
-2 -1 5 -4 0 5 -8 6
• a výsledek kvantování:
340 -2 1 0 -1 1 -1 0
-3 3 -1 -1 1 0 0 0
1 -1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-1 1 0 0 0 0 0 0
1 -1 0 0 0 0 0 0
-1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
25 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Čtení cik-cak
• kvantované hodnoty jsou vyčteny
od DC složky v pořadí od
nejnižších frekvencí po nejvyšší
(detaily)
By Alex Khristov via Wikimedia Commons from Wikimedia Commons
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
26 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování
• každá hodnota může být kódována jinou délkou kódového slova
• hodnoty jsou tříděny podle empiricky stanovených pravděpodobností výskytu
• pravděpodobnější hodnoty jsou kódovány kratším slovem
• nepravděpodobnější hodnoty jsou kódovány delším slovem
• žádné (kratší) slovo nesmí být začátkem jiného (delšího) slova
• Postup:
• kódované prvky jsou seřazeny podle pravděpodobnosti výskytu od nejvyšší
• poslední dvě pravděpodobnosti jsou sečteny a výsledek je zařazen do ostatních
hodnot podle velikosti výsledné (sečtené) pravděpodobnosti
• tento postup je opakován tak dlouho, dokud není součet pravděpodobností
posledních dvou prvků roven jedné (všechny prvky byly analyzovány)
• posledním dvěma prvkům jsou přiřazeny kódové znaky 0 (prvku s nižší
pravděpodobností) a 1 (prvku s vyšší pravděpodobností)
• zpětně přiřazujeme hodnoty 0 nebo 1 všem prvkům v řadě
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
27 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x3
(p=0,22)
x5
(p=0,08)
x1
(p=0,06)
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
28 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x3
(p=0,22)
x3
(p=0,22)
x5
(p=0,08)
x12
(p=0,1)
x1
(p=0,06)
x5
(p=0,08)
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
29 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
x5
(p=0,08)
x12
(p=0,1)
x125
(p=0,18)
x1
(p=0,06)
x5
(p=0,08)
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
30 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
x1235
(p=0,4)
x5
(p=0,08)
x12
(p=0,1)
x125
(p=0,18)
x1
(p=0,06)
x5
(p=0,08)
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
31 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
x125
(p=0,18)
x1
(p=0,06)
x5
(p=0,08)
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
32 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
x125
(p=0,18)
0
x1
(p=0,06)
x5
(p=0,08)
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
33 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
x5
(p=0,08)
0
x2
(p=0,04)
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
34 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
1
x5
(p=0,08)
0
x2
(p=0,04)
0
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
35 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
1
x5
(p=0,08)
0
x2
(p=0,04)
0
x1 → 0
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
36 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
1
x5
(p=0,08)
0
x2
(p=0,04)
0
x1 → 00
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
37 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
1
x5
(p=0,08)
0
x2
(p=0,04)
0
x1 → 001
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
38 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
1
x5
(p=0,08)
0
x2
(p=0,04)
0
x1 → 0011
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
39 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Huffmanovo kódování – příklad
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
x4
(p=0,6)
1
x3
(p=0,22)
x3
(p=0,22)
x3
(p=0,22)
1
x1235
(p=0,4)
0
x5
(p=0,08)
x12
(p=0,1)
1
x125
(p=0,18)
0
x1
(p=0,06)
1
x5
(p=0,08)
0
x2
(p=0,04)
0
x1 → 0011
x2 → 0010
x3 → 01
x4 → 1
x5 → 000
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
40 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Dekodér JPEG
RGB
obraz
inverzní
kvantizace
Huffmanovo
dekódování
model
YCbCr
nadvzorkování
4:4:4
bloky
8×8
inverzní
2D-DCT
kvantizační
tabulky
zápis
cik-cak
Huffmanovy
tabulky
DATA
IDPCM
IRLE
C(0)
C(63)
.
.
.
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
41 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Módy kódování JPEG
Základní (sekvenční) mód: všechny koeficienty jednoho bloku jsou kódovány
postupně (sekvenčně), taktéž jednotlivé bloky. Nevýhodou je, že data jsou
uložena v paměti postupně a v plném rozlišení, takže je možné načítat pouze
postupně.
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
42 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Módy kódování JPEG
Progresivní (rozšířený) mód: kvantované koeficienty jsou uloženy do
mezipaměti a přeneseny později. Nejdříve jsou přeneseny DC složky všech
bloků, dále existují dvě varianty:
• spektrální selekce: postupně jsou přenášeny všechny AC složky všech bloků od
nejnižších frekvencí po nejvyšší, (případně určité rozsahy nízkých frekvencí)
• postupná aproximace: postupně jsou přenášeny jednotlivé bity (případně jejich
rozsahy) všech AC složek v pořadí od MSB
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
43 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Módy kódování JPEG
Hierarchický mód: podobný progresivnímu, postupného zvyšování kvality je
však dosaženo pomocí různých úrovní podvzorkování, kdy je nejdříve
přenesena verze s menším rozlišením a postupně jsou přenášeny rozdílové
informace úrovní s vyšším rozlišením.
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
44 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Typické JPEG artefakty
detail téměř bez komprese:
detail s vysokou kompresí
(blokové artefakty):
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
45 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Typické JPEG artefakty
detail bez komprese: detail s vysokou kompresí:
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
46 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Kritéria hodnocení kvality komprimovaných obrazů
• subjektivní: nákladné testování subjektivního dojmu souboru diváků
• objektivní: vyjádření rozdílnosti komprimovaného snímku od originálu
• označme 𝑥𝑖 jasové hodnoty pixelů (barevných elementů) originálu
• označme 𝑥𝑖
′
jasové hodnoty pixelů (barevných elementů) komprimovaného obrazu
• střední kvadratická chyba, MSE (Mean Square Error)
𝑀𝑆𝐸 =
1
𝑀
𝑖=1
𝑀
𝑥𝑖 − 𝑥𝑖
′ 2
• poměr signálu k šumu, SNR (Signal to Noise Ratio) 𝑑𝐵
𝑆𝑁𝑅 = 10 log10
𝑃2
𝑀𝑆𝐸2
kde 𝑃 je interval hodnot vstupního jasu 𝑃 = max 𝑥1 … 𝑥 𝑀 − m𝑖𝑛 𝑥1 … 𝑥 𝑀
• špičkový poměr signál/šum, PSNR (Peak Signal to nise Ratio)
𝑃𝑆𝑁𝑅 = 10 log10
𝑁2
𝑀𝑆𝐸2
kde 𝑁 je maximální hodnota vstupních dat, tj. typicky 255 pro 8 bitů
KOMPRESE STATICKÝCH OBRAZŮ Videotechnika a multimédia
47 / ?? Kamil Říha
Vysoké učení technické v Brně Fakulta elektrotechniky a komunikačních technologií
Děkuji za pozornost