Algoritmy komprese dat Digitalizace a komprese videa
13.1.2016
NSWI072 - 18
Úvod Video ≈ posloupnost snímků Komprese videa × obrazu • změna průměrného jasu obrázku » zanedbatelná po dekompresi statického obrazu » viditelná v posloupnosti snímků
• špatná reprodukce ostrých hran » vážný problém pro kompresi obrazu » zanedbatelná ve video sekvenci
2
Úvod Klasifikace algoritmů dle aplikační oblasti • oboustranná komunikace ⇒ symetrická komprese / dekomprese • jednostranná komunikace ⇒ vyšší tolerance pro složitost komprese
3
Reprezentace video signálu CRT – Cathode Ray Tube • emise paprsku elektronů • povrch pokrytý fosforem
4
Reprezentace video signálu
Obnovovací frekvence fps (frames per second) • • • • •
min 15fps 16fps → 24fps (35mm film) zdvojování 48fps (72fps) PAL,SECAM 25fps USA 30fps (1930), 29.97fps (1953) 5
Analogová TV (USA) NTSC (National Television Standards Committee) • 525 řádků, jen asi 483 viditelných (snímkové zatemňování) • poměr stran 4:3 ⇒ délka řádku 4/3 ∗ 483 = 644 • 59.94fps, prokládání (2× 262.5 řádku)
6
Analogová TV (Evropa) PAL (Phase Alternating Line, Německo) • 625 řádků (asi 576 viditelných) • poměr stran 4:3 • 50fps, prokládání 2:1
SECAM (Séquential Couleur avec Mémoire, Francie)
7
Reprezentace barev Barevná TV • 3 elektronové paprsky → R, G, B
8
Reprezentace barev Kompozitní signál • 1953: zpětná kompatibilita s č/b TV • Y (jas), C1,C2 (barevné složky) » Y používaly č/b TV přijímače
9
Gama korekce
10
Kompozitní/komponentní video NTSC: YIQ • • • •
Y = 0.299 R’ + 0.587 G’ + 0.114 B’ I = 0.596 R’ - 0.274 G’ - 0.322 B’ Q = 0.211 R’ - 0.523 G’ + 0.311 B’ R’,G’,B’ := R,G,B po gama korekci
PAL: YUV
SECAM: YDrDb
Jediný kanál pro všechny 3 složky Komponentní video: 3 kanály pro separátní přenos
11
Digitální video Nejprve pokusy o vzorkování kompozitního videa • problém NTSC x PAL • 70. léta : vzorkování komponent ⇒ mezinárodní standard
ITU – R recommendation 601 (CCIR 601) • digitalizace prokládaného analogového videosignálu • barevný prostor YCbCr • vzorkovací frekvence 3.375MHz » pro každou komponentu celočíselný násobek (až 4x) » 4:4:4 ⇒ 13.5MHz každá » 4:2:2 ⇒ 13.5MHz jas, 6.75MHz barevné složky •
Y: 720 vz/ř , C: 360 vz/ř 12
ITU – R 601
13
ITU – R 601 Normalizace YCbCr vzorků • Y∈〈0,1〉, CbCr ∈〈-1/2,1/2〉
Konverze na 8b hodnoty • Y = 219Ys + 16 • U = 224Cbs + 128 • V = 224Crs + 128
14
MPEG – 1 Formát MPEG-SIF : vychází z ITU-R 601 4:2:2 anti-aliasing
15
MPEG - 1
16
H.261 ITU-R H.261 • videotelefon, videokonference
Výchozí formát CIF (Common Interchange Format) • Y: 288 × 352 • UV: 144 × 176 • QCIF (Quarter) poloviční v obou směrech
17
H.261 ☀ Idea • snímek → bloky 8 × 8 • predikce + diferenční kódování » predikce dle předchozího snímku » nebo O → když předchozí neexistuje nebo se příliš liší
• DCT • kvantizace • entropický kodér » s proměnnou délkou kódového slova
18
Schéma H.261
19
Kompenzace pohybu Diferenční kódování • predikce pomocí stejné pozice na předchozím snímku nedostatečná • vektor pohybu
20
Blokově orientovaná kompenzace snímek → čtvercové bloky for each blok B kódovaného snímku do najdi blok P předchozího snímku s min d(B,P) • d ∈{d1, σ2} if d(B,P) > ε then zakóduj P bez predikce else vektor-pohybu := levý-horní-roh(B) levý-horní-roh(P)
21
Kompenzace pohybu Zvětšení velikosti bloku • menší # bloků • větší # operací při porovnání • předměty pohybující se různým směrem
22
Kompenzace pohybu Omezení oblasti prohledávání • menší # porovnání • méně kandidátů, horší shoda
23
H.261: kompenzace pohybu ☝Řešení H.261 • makrobloky » Y: 16 × 16 (4 bloky 8 × 8) » UV: 8 × 8
• kompenzace pohybu na úrovni makrobloků » hledání nejlepší shody na předchozím snímku » pouze pro složku Y » oblast prohledávání: < ±15 v obou směrech » vektor pohybu pro UV: (vektor pohybu pro Y) × ½ •
(-3,10) → (-1,5)
24
Vyhlazovací filtr Ostré hrany ve snímku použitém pro predikci • vyšší variace hodnot diferencí • vysoké VF koeficienty po DCT • nižší kompresní poměr
Vyhlazovací filtr • 2rozměrný separabilní: řádky, sloupce • koeficienty (1/4, ½, 1/4) • mimo okraje bloku
☀ Příklad 110 218 116 112
110 165 140 112
110 165 140 112
108 210 110 114
108 159 135 114
108 167 148 113
110 218 210 112
110 188 187 112
110 161 154 113
112 108 110 116
112 109 111 116
112 109 111 116
25
Transformace DCT bloků 8 × 8 • blok diferencí (režim inter) • původní blok (režim intra)
Kodér simuluje činnost dekodéru • rekonstrukce komprimovaných snímků • uložení výsledku
26
Kvantizace Velká variace koeficientů pro kvantizaci • vysoká hodnota DC koeficientu intra bloku • malé změny mezi snímky ⇒ nízké hodnoty koeficientů inter bloku
32 kvantovačů • intra DC koeficient: uniformní kvantovač s krokem 8 s nulovým dělícím bodem • ostatní: uniformní s krokem ∈ 〈2,62〉 s nulovým intervalem • menší krok ⇒ více nenulových koeficientů 27
Kvantizace Identifikace použitého kvantovače • hlavička makrobloku • GOB (group of blocks): 3 řady po 11 makroblocích » 5bitový identifikátor v hlavičce GOB
28
Kódování Cik-cak průchod blokem kvantovaných koeficientů • • • •
≈ JPEG (počet předchozích nulových, aktuální koeficient) 20 nejčastějších → proměnná délka kódového slova ostatní → pevná délka 20b » escape (6b), délka běhu nul (6b), koeficient (8b)
CBP (coded block pattern) • v hlavičce makrobloku • které bloky (4 jasové, 2 barevné) obsahují nenulové koeficienty 29
Řízení přenosu (rate control) Aplikace: videotelefon, videokonference • minimální zpoždění (< 150ms)
Přenosový buffer • má zajistit konstantní rychlost přenosu • buffer se vyprazdňuje/ přeplňuje • kodér dodává data s nižší/vyšší frekvencí než vyžadováno pro přenos • může požádat kodér o změnu
Požadavek na vyšší/nižší přenosovou rychlost • kodér vybere kvantovač s menším/větším krokem » větší krok → více nulových koeficientů
• mezní řešení: některé snímky nepřenášet 30
MPEG-1 Základ podobný H.261 • • • • • •
bloky 8 × 8 inter/intra kompenzace pohybu na úrovni makrobloku DCT kvantizace a kódování řízení přenosové rychlosti pomocí přenosového bufferu
Rozdíly: • rozdílné aplikace • MPEG-1: digital storage media 31
Typy snímků Snímky • I-snímek (intraframe) běžný snímek • P-snímek (predictive frame) diference mezi běžným a předchozím I nebo P-snímkem • B-frame (bi-directional frame) diference mezi dvěma nejbližšími I/P-snímky • např. I:P:B ≈ 2:5:12
32
Skupiny snímků Group of Pictures (GOP) • opakující se posloupnost 10-30 snímků • DVD (MPEG-2) omezení » PAL DVD ≤15 snímků / GOP » NTSC DVD ≤18 snímků / GOP
33
GOP Alespoň jeden I-snímek Začátek • I-snímek • B-snímky, které pro predikci požívají jen následující I-snímek
☝Vlastnosti • přehrávání v původní rychlosti i na pomalém zařízení • rychlost lze zajistit přeskočením B, P, případně I-snímků • rychlé převíjení, skok dopředu / dozadu 34
GOP ☀ Příklad IBBPBBPBBPBBI Display order • I1 B2 B3 P4 B5 B6 P7 B8 B9 P10 B11 B12 I13
Bitstream order • I1 P4 B2 B3 P7 B5 ...
35
Kódování Kompenzace pohybu • standard nespecifikuje konkrétní metodu • oblast prohledávání by měla růst se vzdáleností mezi snímky
Kódování a kvantizace ≈ JPEG • různé kvantovací tabulky pro různé snímky
Řízení přenosu • nejprve B-snímky • zvýšení velikosti kroku kvantovače • vynechání VF koeficientů 36
Kódování CPB (constrained parameter bitsteam) • doporučené hodnoty parametrů • 352x288 (25sn/s), 352x240 (30sn/s) -> 1-1.5Mb /s
Vlastnosti • VHS kvalita (low-moderate motion) • horší než VHS (high-motion) • neuvažuje prokládání
37
MPEG Moving Picture Experts Group • • • •
pracovní skupina ISO/IEC vývoj standartů pro kódování digitálního audia/videa 1988 (Ottawa) cca 350 členů
Standard popisuje • formát bitového proudu a dekodér • nikoliv kodér
38
MPEG MPEG-1 (1993) • • • •
ztrátová komprese zvuku & videa až 4095×4095, 30 snímků/s, 1.5Mb/s, obraz YUV standard for Video CD Layer 3 (.mp3) formát pro kompresi audia
MPEG-2 (1994) • až 15Mb/s • TV vysílání » DVB, kabelová TV, HDTV • DVD 39
MPEG-2 Profily • simple, main, snr-scalable, spatially scalable, high • simple: bez B-snímků • main: viz MPEG-1
Použití více vrstev • snr-scalable, spatially scalable, high • základní vrstva: kódování video signálu nízké kvality • doplňková vrstva: diferenční kódování pro zvýšení kvality 40
☀ Příklad DCT koeficienty 29.75 6.1 -6.03 1.93 -2.0 1.23 -0.95 2.11 Kvantovač s délkou kroku 4 • • •
stejný krok pro všechny koeficienty pro jednoduchost lij = ⎣θij / 4 + 0.5⎦
✓ˆij = lij · 4 Koeficienty po rekonstrukci 28 8 -8 0 -4 0 0 4 Rozdíl původní-rekontruovaná (chyba kvantovače) 1.75 -1.9 1.97 1.93 1.99 1.23 -0.95 -1.89 41
☀ Příklad Doplňková vrstva: • kvantizace rozdílů • kvantovač s krokem 2
Hodnoty v doplňkové vrstvě po rekontrukci 2 -2 2 2 2 2 0 -2 Po přičtení v hodnotám v základní vrstvě 30 6 -6 2 -2 2 0 2 Chyba kvantovače -0.25 0.1 -0.03 -0.07 -0.01 -0.77 -0.95 0.11 42
MPEG-2 Úrovně (level) • • • • •
low (352 x 240) main (720 x 480) high 1440 (1440 x 1152) high (1920 x 1080) všechny úrovně 30 sn/sec
Prokládání • P-snímky: lze nahradit 2 P-půlsnímky • B-snímky: lze nahradit 2 B-půlsnímky • I-snímky: 2 I-půlsnímky nebo I a P-půlsnímek » využití půlsnímků pro predikci 43
MPEG-2
44
MPEG MPEG-3 • původně navržen pro HDTV • vývoj zastaven, sloučen s MPEG-2 • MPEG-3 ≠ MP3 = MPEG-1 Layer 3
MPEG-4 (2001) • navržen pro kódování s nízkou přenosovou rychlostí • skládání různých informací z mnoha datových toků » objektově orientovaný přístup (audio, video a VRML objekty) » popis 3D scény pomocí virtuálních kamer (VRML, X3D) » popis a animace výrazu obličeje (talking-head) » popis hlasových prvků (fonémy) pro automatický převod textu na řeč » DRM (Digital Rights Management) 45
MPEG MPEG-4 • povoluje použití libovolných kodeků (MPEG-1-2 kódování dáno normou) » efektivnější komprese / nižší kompatibilita » kodeky třeba instalovat » MPEG-4 Part 2: DivX, XviD, Quicktime 6 » MPEG-4 Part 10 (H.264): Quicktime 7, HD DVD, Blu-ray
46
