VE VYSTAVBE!
- Morse, Morzeovka
- DIM, Zmena soustavy (dimenze)
- HUF, Huffman & Shannon-Fano
- RLE, Run-Length Encoding
- QTree, Ctvercovy strom (QuadTree Code)
- Patt, Pattern kody (Pattern)
- Diff, Difference Mapping
- Fract, Fractal kody (Fractal Code)
- CCITT, Tiff kody (CCITT)
Priloha 1 - CCITT3, PackBits
- LZW (LZ, LZW) - Lempel-Ziv-Welch
- Ari, Aritmericky kod (Arithmetic code)
Transformace
- BWT - Burrows-Wheeler transformace
- Wave transformace
- Wave: DCT - Kosinova transformace
- (nedok) Wave: DWT - WaveLet transformace
- (nedok) Wave: Ostatni
Priloha 2 - JPEG 4x4 DCT 1D
Priloha 3 - JPEG 4x4 DCT 2D
- (nedok) MPEG - Motion Jpeg
Pozn.1: Pouzite zkratky algoritmu mohou by smyslene pro tento text.
Pozn.2: Pokud neni metoda oznacena pod nadpisem jinak, je neztratova.
Pozn.3: V ucinnosti u prikladu neuvazuji o informaci nezbytnou pro dekodovani, u vetsiho poctu dat ma zanedbatelny vliv.
Pozn.4: Algoritmy je mozne rozsirit o ruzne vymozenosti, jako opravny kod, kontrolni soucty, ... viz soubor sifrovani.htm
Pozn.5: Pokud se bojite odhaleni principu svych algotitmu, nemejte strach. Disassembler to resi, hackeri si vas program spusti krok po kroku a mate po parade. :)
Tip: U komprimace textu lze uvazovat, ze kazde slovo konci mezerou. Pokud je jiny, zapise se jeho kod. Pri dekompresi pak odmaze mezeru. Pokud je s mezerou, prida se znak mezery nebo dvou, podle toho, jestli dalsi maze nebo ne mezeru.
Vhodna metoda komprese pro obrazky
2 barvy B/W: TIFF-CCITT4, Deflate
4-256 barev: GIF-Zip
16,7 milionu: JPG-DCT, LWF
Podporovane formaty pro internet
GIF (2-256 barev), JPG (16,7 milionu)
Code = oznaceni pro vystupni kod
Data = oznaceni pro vstupni data
BW = Black & White = cernobile
Hlavni menu
Je zalozena na cetnosti znaku anglicke abecedy
Domnivam se, ze vychazel ze spatneho schematu, mi vychazi poradi takto:
EN26 ETAOINHSRDLMWUFCYGBPVKXJQZ (Robinson Crusoe 624,000 znaku)
EN26 ETAOINHSRDLUFWCYMGPBKVJXQZ (Creatures that once were men 140,000 znaku, scifi)
CZ26 EAOILSNTRMUKVJDPZCYHBGFXWQ (bez hacku spojene povidky 900,000)
Morse
A .- I .. Q --.- 1 .----
B -... J .--- R .-. 2 ..---
C -.-. K -.- S ... 3 ...--
D -.. L .-.. T - 4 ....- -.-.- pozor
E . M -- U ..- 5 ..... ..... nerozumim
F ..-. N -. V ...- 6 -.... ...-.- konec vysilani
G --. O --- X -..- 7 --... ...-. rozumim
H .... P .--. Y -.-- 8 ---..
CH---- W .--- 9 ----.
Z --.. 0 -----
AHOJ = -.-.-/.-/..../---/.---/...-. (.=12 -=11 /=5)
Cisla byla doplnena pozdeji.
A jelikoz je snadne pomlouvat praci druheho, prikladam mou tabulku pro EN Robinsona:
0=. 1=-
E 0 H 000 W 110 B 0100 Q 1010
T 1 S 001 U 111 P 0101 Z 1011
A 00 R 010 F 0000 V 0110 1100
O 01 D 011 C 0001 K 0111 1101
I 10 L 100 Y 0010 X 1000 1110
N 11 M 101 G 0011 J 1001 1111
Stejne s Morse: ERT (3)
Podobne delkou: ABCDFIJNPQSUVXYZ(16)
Odlisnost: 26-19= (7)
Proc Morse a ne 1..32 binarne?
Odpoved je snadna, slo o komunikaci a bylo snadnejsi pouzit kratky kod s pauzou nez pak lustit radu cisel.
To samozrejme s vymozenosti techniky, ktera lusteni dela za nas, vypada pak legracne komplikovat si zivot :)
Pokracovatelem Morse jsou CCITT komunikacni normy.
Hlavni menu
Priklad 1: 8-bit -> 2-bit
7375 (4B) -> 00110001 (8b)
(25% = 8/32)
-------------------
1 = 00110001 --> 00
3 = 00110011 --> 01
5 = 00110101 --> 10
7 = 00110111 --> 11
-------------------
Pouziti: Anglictina ma 26 znaku + specialni (rekneme 32), to je 5 bitovy kod 00000-11110, 11111=ostatni znaky (ktere se vykopiruji nakonec)
Hlavni menu
Spocitaji se pocty znaku, seradi podle poctu vyskytu a priradi se jim kod promenlive delky. Prideleni kodu se podle mne provadi rovnomerne 50:50 .
Podobne metody jsou Shannon-Fano
Adaptive = tabulka se vytvari podle obsahu souboru a neni predem definovana
Priklad 2: Huffman pro znaky (adaptive)
7375171773755757 (16 B) -> 0111010 11001100 0111010 100100 (28 b)
(22% + Info = 28/128)
Data 1.2.3. krok
7 3 7 5 8x 7 = 0 (1) | 0 - 8:8 (50:50)
1 7 1 7 4x 5 = 10 (2) | 1 0 / - 4:4
7 3 7 5 2x 1 = 110 (3) | 1 1 0 / / - 2:2
5 7 5 7 2x 3 = 111 (3) | 1 1 1 / / /
_Code_
1. 0 _1_ 0, 1
2. 0 _1_ 0 and 10, 11
3. 0 1 0 and 10 and 110, 111
Huffmanuv strom kodu
Priklad 3: modifikace Huffmana
Rozdeleni kodu se provadi jinou metodou nez delenim 50:50 podle poctu vyskytu.
_Code__
1. 0 __1__ (0) / (1)
2. _0_ _1_ 0 + (10) / (11)
3. 0 1 0 1 0 + (100 101 110 111)
10x 1 000 -> 0
1x 2 001 -> 100
2x 3 010 -> 101
4x 4 011 -> 110
1x 5 100 -> 111
Priklad 4: Huffman pro retezce znaku = Shannon-Fano
BAAAAAADBBABBBBBAAADABCD (24 B)
-> 311x 2x22 31xx 3xx
-> 111101001100110110111100011000+DADACD (30b+6B)
(42% = (30+48)/192)
--------------
6x other x 0 other = D A D A C D
3x AAA 1 10
3x BB 2 110
3x B 3 111 Nejakym zpusobem si urcime caste retezce.
--------------
Priklad 5: Shannon-Fano pro binarni retezce
011011000110010110111100011000111100011001011011110001100000 (60 b)
-> 1213 x121 xxxx 2131 21xx xx
-> 1011010111 011011010 00000101 1101011110 110100000 0000 (50b)
(83% = 50/60)
----------------
9x x x 00/01 x = other = 100110000
7x 0110 1 10
4x 1100 2 110
4x 0101 3 111
----------------
Hlavni menu
Pocita se pocet opakovani znaku.
Priklad 6:
AABAAAABBBB (11) -> A2B1A4B4 (8) -> ABBAADBD
(73% = 8/11)
A-Z == 1-26 (1=A, 2=B, 3=C ...)
AABAAAABBBB (11) -> ABAB2144 (8) -> ABAB 01001111 (5)
(45% = 8/11)
max\x\= 4 (00=1 01=2 10=3 11=4)
Priklad 7:
AAACDAAAGAEFBBBBB (17) -> +3A -2CD +3A -4GAEF +5B (14) -> BAMCDBAQGAEFDB
(82% = 14/17)
A-M == 2 .. 14, N-Z == -1..-13
(Priklad 6)
AAACDAAAGAEFBBBBB (17) -> A3C1D1A3G1A1E1F1B5 (18)
(106% = 18/17)
AAACDAAAGAEFBBBBB (17) -> ACDAGAEFBB 10000010 00000000 1100 (10+3)
(76% = 13/17)
Priklad 8: RLE/Huffman pro bity
011110001110000010000 (20) 011110001110000010000 (20)
1 H-Kod 0 H/L = 8/13 = 0,6
-----------------
1 00 0 00 1
11 01 00 01 01
111 100 000 10 001
1111 101 0000 11 000
11111 110 00000 H/L = 3/6 = 0,5
111111 111 000000 . 1111/1110
-----------------
0 10110010011000101 (17) 01000000101000110111 (19)
(85% = 17/20) (95% = 19/20)
Priklad 9:
RLE/Huff nul RLE+Huff1 (delka+kod)
1 00 0 1 00+00 6 01+010 13 10+0010
01 01 1 01 00+01 7 01+011 14 10+0011
001 100 2 001 00+10 8 01+100 15 10+0100
0001 101 3 0001 00+11 9 01+101 16 10+0101
00001 110 4 01+000 10 01+110 17 10+0110
00000 111 5 01+001 11 01+111 18 10+0111 ... 59 11+11111
RLE+Huff2 (delkax+kod 2,4,6,8) RLE+Huff2 / RLE delka (v prvocislech)
00+00 (1) ... 01+1111 (4+16) 1/1 5/11 9/19 13/31
00+01 (2) 10+000000 2/2 6/13 10/21 14/37
00+10 (3) ... 3/3 7/15 11/23 15/41
00+11 10+111111 (20+64=84) 4/7 8/17 12/29 ...
01+0000 11+00000000
01+0001 ... 11+11111111 (84+256=340 kodu)
RLE+Huff2(v prvocislech 2,3,5,7) -> kod
00+00 ... 01+000 ... 10+00000 ... 11+0000000 (4+8+32+128=172)
Hlavni menu
Velke plochy cerne a bile je mozne kodovat po ctvercich.
Priklad 10:
___ _ _ _______ _______________
| |_|_| | |
|___|x|_| | |
| |x x| | |
|___|x_x|_______| |
|x x x x|x|_| | |
|x x x x|x|x|___| |
|x x x x|x x|x|_| |
|x_x_x_x|x_x|x|_|_______________|
|x x x x x x x x| | | |
|x x x x x x x x|___|___| |
|x x x x x x x x|x x| | |
|x x x x x x x x|x_x|___|_______|
|x x x x x x x x|x x x x| | |
|x x x x x x x x|x x x x|___|___|
|x x x x x x x x|x x x x|x x| |
|x_x_x_x_x_x_x_x|x_x_x_x|x_x|___|
(16x16 = 256 b)
oWoWWBWWB (Code 4x4)
A oooWoWWBWWBWBooBWBBWBoBWBW (ternary system o-W-B = 1-2-3)
-> 1111110 110010 00100 10111110 010100 1011100 100 (42 b)
(16% = 42/256)
--------------
10x 2 00 0
9x 3 01 10
7x 1 10 11
--------------
B Barvy: 1110110100100100101 (19)
Uzly : 1 1(10100 0 0 11001) 0 0 1(10000 0 0 10000) (29) (ano/ne)
(19% = 48/64)
'x' = black (cerna)
' ' = white (bila)
'o' - uzel (node)
'B' - cerna oblast (black area)
'W' - bila oblast (white area)
Princip:
Uzel je prvek, ktery deli spojuje 4 stejne oblasti s ruznymi barvami.
Cili, pokud ctverec obsahuje W a B, rozdelime ho uzlem na 4 casti.
0. 1. 2.
______ ___ ___ ___ _ _
| | |a1 |a2 | | | | |b1 b2
| x | | |x | | -o-
| x x| |---o---| | |x| |b3 b4
|___x_x| |a3 |x x|a4 |---o---
|___|x_x| | |x x|
|___|x_x|
uzel-a uzel-b
Code 4x4
1. o (uzel-a)
2. W (ctverec a1 obsahuje pouze barvu W)
3. o (uzel-b, ctverec a2 obsahuje barvy B a W)
4. WWBW (ctverec b1,b2 - W, b3 - B, b4 - W)
5. W (a3 - cely je v barve W, neni treba delit)
6. B (a4)
oWoWWBWWB
Hlavni menu
ZTRATOVA
Vyhledava se vzorek obrazku, ktery se vicekrat opakuje v priblizne podobe.
(Recognita - Scanned text to text)
(prevadeni skanovaneho textu z obrazku na textovy soubor)
Treba pismenko 'A' v textu na BW obrazku, ktere diky nepresnostem skenovani ma trosku odlisnou podobu, se nahradi jednim.
______ ______ ______
| xx | | xxx | | xx xx|
| x x | | x x | | x xx |
| xxxx | | xxxx | | xxxx |
|x x| |x x | |x x |
|x____x| |x___x_| |x___x_|
A A H
AAH -> AAA -> ZTRATY !
A = 6x5 = 30 b AAH = 90 b
codeA = 1+8 b AAA = 27 b
(30% = 27/90)
Hlavni menu
Metoda se pouziva pro filmy a video. Vyuziva toho, ze nekolik po sobe jdoucich obrazku se lisi jen velmi malo od prvniho.
Obvykle se pouziva pro 8 snimku, prvni komprimovany jako JPG se nazyva klicovy, ostatni rozdilove jsou komprimovane jinou metodou.
______ ______ ______
| xx | | xxx | | xx xx|
| x x | | x x | | x xx |
| xxxx | | xxxx | | xxxx |
|x x| |x x | |x x |
|x____x| |x___x_| |x___x_| ...
A A H
______ ______ ______
| xx | | x | | x xxx|
| x x | | | | x |
| xxxx | | | | |
|x x| | xx| | xx|
|x____x| |____xx| |____xx| ...
KeyFrame Frame2 Frame3
Hlavni menu
Podobne Patt kodu, zameruji se na obsah oblasti.
Kresba v obrazku se popise nejakym zpusobem.
Metoda 1 - trojuhelniky (mpeg)
Obrazek se rozdeli na plochy, ktere lze priblizne popsat pomoci stinovaneho trojuhelniku. Cize v rohu trojuhelniku se stanovy 3 barvy a zbytek trojuhelniku se vystinuje.
Metoda 2 - fraktalovou rovnici (puvodni fraktaly)
Kresba se popise rovnici, ktera vystihuje nekonecne spojeni jednoho vzorku podle nejakeho pravidla. Vznika tak obrazek treba zmensujiciho se hlemyzde. Velky kruh je postupne zmensovan po spiralovite draze do urcite konecne hloubky.
Hlavni menu
Format obrazku Tiff dnes podporuje LZW, JPEG a dalsi algoritmy.
Tyto kody se pouzivaji obvykle pro BW obrazky, kde jsou velmi efektivni. Faxy, BW obrazky, naskenovane texty.
CCITT 1 = Huffman 1D (T.4 MH)
CCITT 3 = 6:1 (1980,4,8) RLE/Huff - G31D (T.4 MR) / G32D (T.4 MMR)
CCITT 4 = 25:1 (1979 1985) G42D (T.6)
Deflate = fix/dynamic Huffman -> LZW (tabulka podobna CCITT3)
Packbits= CCITT G31D (RLE/Huffman)
CCITT (International Telegraph and Telephone Consultative Committee, fax group)
(1D,2D 1,2 dimensional; G=Group; MH, MMR: M=Modified H=Huffman R=Read)
Group 3 - 2D
Pouziva PackBits kody, zalozene na RLE a Huffmanovi ((2-12) bitu pro 2560 stejnych hodnot),
Proti 1D koduje jak horizontalne (po radcich), tak vertikalne, co je vyhodnejsi.
Priloha 1: CCITT 3 tabulka kodu - PackBits
Group 4 - 2D
Proti Group 3 ma navic specialni kodovani pro huste oblasti 2D, stridani cerne a bile.
Metoda pro huste oblasti
EOL = 0000 0000 0001 (end of line)
1. zacatek = 1x EOL , konec = 6x EOL (RTC return-to-control)
2. kazdy radek zacina bilou, jinak je kodovan jako 0
3. kazda rada pixelu je kodovana jako 0 nebo make-up kody od 0 do 63 (Terminating)
4. ... (nepochopil jsem)
kodova tabulka pro huste oblasti
pass 0001
horizontal 00 + m(a0a1) + m(a1a2)
v(0) 1
vL(1) 010
vR(1) 011
vL(2) 00010
vR(2) 00011
vL(3) 000010
vR(3) 000011
extension 000001xxx
v>3 specialni kod pro vzdalenost
v - vzdalenost (lenght) v(a1b1) = |a1b1|
L/R - vpravo/vlevo (left/right)
Priklad 11:
0123456789012345 ... delka linky = 16 bitu
________________
| xxxx xxx | line 0
| xxxx xxx | line 1
| xxxx xxx | line 2
| xxxxxx xxx | line 3
|__________xxxxx_| line 4
________________
| xxxx xxx | line 0
Z| Z Z Z Z | line 0 (z1,z2,z3,z4,z5)
| xxxx xxx | line 1
Z| Z Z Z Z | line 1 (z6,z7,z8,z9,z10)
| xxxx xxx | line 2
Z| Z Z Z Z | line 2 (z11,z12,z13,z14,z15)
| xxxxxx xxx | line 3
Z| Z Z Z Z | line 3 (z16,z17,z18,z19,z20)
| xxxxx | line 4
Z|__________Z____Z| line 4 (z21,z22,z23)
________________
Z| Z Z Z Z | line 0
A| A A A A | line 1
A| A A A A | line 2
A| B C A A | line 3
A|_____P____B____C| line 4
kod
P pass 0001
A v(0) 1
B vL(1) 010
C vR(1) 011
1. oznacime prechody B->W a W->B (Z) (changes)
2. urcime polohu prechodu od radku 1 (line1) podle prechodu nad nim v radku 0 (line0)
a propusti (pass)
z6 je pod z1, v(z6,z1) = 0 ... A
z7 je pod z2, v(z7,z2) = 0 ... A
:
z16 je pod z11, v(z16,z11) = 0 ... A
z17 je nalevo od z12, v(z17,z12) = 1 ... B
z18 je napravo od z13, v(z18,z13) = 1 ... C
... A
... A
z21 je pod z16, v(z21,z16) = 0 ... A
pod z17 neni ve vzdalenosti 0-3 napravo a na levo zadny jiny prechod nez z21 a ten uz jsme znacili,
oznacime propust... P
z22 je pod z18
v(Line1-4) = 4x16 = 64
Line1: AAAA = 11111
Line2: AAAA = 11111
Line3: BCAA = 101001111
Line4: PBC = 10001010011
\kodu\ = 5+5+9+11 = 30
(47% = 30/64)
Pozn. Bod 2 mi neni zcela jasny, nasel jsem jen takovyto obr na inetu.
--------------------------------------------------
Pro porovnani s QuadTree Code (128)
0 1 2 3 4 5 6 7 8 9 A B C D E F
.. . . . . . . . . . . . . . . ..
0. | |x|x x|x| | | |x|x x| .
|-o-| |-o-| |-o-| |
1. | |x|x x|x| | | |x|x x| .
---o---|---o---|---o---|---o---
2. | |x|x x|x| | | |x|x x| .
|-o-| |-o-| |-o-| |
3. |x|x|x x|x|x| | |x|x x| .
-------o-------|-------o-------
4. | | |x|x|x|x|x| .
| | |-o-|-o-|-o-
5. . . . |. . . .|. .|.|.|.|.|.|..
| |---o---|---o---
6. | | | | | .
| | | | |
7. | | | | | .
---------------o---------------.
.. . . . . . . .|. . . . . . . ..
0-7 x 0-7: o oo0o00110o0111o1o10101o101000 (29+1)
8-F x 0-7: oo0o01010o0101o1010o0o110000o1100o100000 (40)
1 = 22 (2b) o = 17+1 (2b) 0 = 31 (1b)
(85% = 109/128)
Barvy: 0001100111110101101000 0010100101101001100001100100000 (53)
Uzly : 1 1101011010100 110101100001010011100 (ano/ne)(34+1)
(68% = 87/128)
Hlavni menu
Vylepseni:
- slovnik se zapisuje do pameti usporne pomoci kodu BCS
- pri zaplneni max velikosti slovniku se nevycisti cely, ale jen malo caste kombinace znaku
- zapis kodu se da psat jako znak (treba 0) 0 + 0-255 pro 255 kombinaci, protoze prvni je dvojznak 00 pro 1 nulu (nebo 0+255,1+255 pro 512 kombinaci)
- nebo jako znak (treba 0) 0 + 1-x, kde x je velikost podle poctu bitu, treba 10, pak 1024 (0+x,1+x pro 2*x)
- predvidani - viz dole Selhani kodu, algoritmus predvida nasledujici kod a zvoli uspornejsi variantu zapisu kodu a upravi podle ni slovnik.
Clear kod - oznaceni, ze tabulka kodu presahla (12, 13, 14) znakove retezce a zacina se nova tabulka
(toto cislo je dane velikosti pameti)
(new table)
End kod - oznaceni konce souboru (end file)
New kod NC- novy kod a je pro nej treba 2 znaky. Prvni oznacuje kod, dalsi cislo kodu
Code1 = (End + Clear) + (Code) + End
definujeme End a Clear, zapiseme kod Code, zapiseme konec souboru End
Priklad 12:
Kodovani:
---------
Data = /WED/WE/WEE/WEB/WET ... 19 B
NC - novy kod
CS - slovnik s kodem, min 2 znaky (1 - oznaceni kodu, 2 - cislo kodu)
BCS - mensi verze CS pro pamet
NC/BCS a CS je tabulka ukladana pouze do pameti pocitace pri kodovani a dekodovani.
Data Code NC CS BCS
----------------------
/W / 256 /W /W
E W 257 WE WE
D E 258 ED ED
/ D 259 D/ D/
WE 256 260 /WE 256E
/ E 261 E/ E/
WEE 260 262 /WEE 260E
/W 261 263 E/W 261W
EB 257 264 WEB 257B
/ B 265 B/ b/
WET 260 266 /WET 260T
EOF T
\Data\ = 19 B
Code = / W E D 256 E 260 261 257 B 260 T
kod = 2 B
\Code\ = 4+ 2 +1+ 2+2+2 +1+ 2 +1 = 17 B
(89% = 17/19)
Princip:
--------
0. '/'
1. '/' + 'W' = '/W'
'/W' - najdi v tabulce, v tabulce nenasel (v tabulce nic neni, zatim)
zapis Code + '/' (kopiruj lomitko z Data)
(Code = '/')
zapis kod 256='/W' do tabulky
2. 'W' + 'E' = 'WE'
'WE' - tabulka, neni - zapis kod 257='WE' do tabulky
zapis Code + 'W' ('/W')
3. 'ED' - tabulka, neni - zapis kod 258='ED'
zapis Code + 'E' ('/WE')
4. 'D/' - tabulka, neni - zapis kod 259='D/'
zapis Code + 'D' ('/WED')
! 5. '/' + 'W' = '/W'
! '/W' - tabulka, JE - kod 256
! Data read+1 (cteni dat+1)
! memory = 256 (pamatuj si kod 256) (256)
! 6. '/W' + 'E' = '/WE'
! '/WE' - tabulka, neni - zapis kod 260='/WE'
! zapis Code + 256 ('/WED' 256)
! 7. '/WE' = 256+'E' zustane nam tedy jen 'E', ktere neni zapsane
(0.)
'E/' - tabulka, neni - zapis kod 261='E/'
zapis Code + 'E' ('/WED' 256 'E')
!! 8. '/W' - tabulka, JE - kod 256 (256)
!! 9. '/WE' - tabulka, JE - kod 260 (260)
!! 10. '/WE'+'E' - tabulka, neni - zapis kod 262='/WEE'
!! zapis Code + 260 ('/WED' 256 'E' 260)
11. '/WEE' = 262+'E'
'E/' - tabulka, JE - kod 261 (261)
12. 'E/W' - tabulka, neni - zapis kod 263='E/W'
zapis Code + 261 ('/WED' 256 'E' 260 261)
.......
Dekodovani:
-----------
Code = / W E D 256 E 260 261 257 B 260 T
Code Data NC NS
----------------------
/ /
W W 256 = /W
E E 257 = WE
D D 258 = ED
256 /W 259 = D/
E E 260 = /WE
260 /WE 261 = E/
261 E/ 262 = /WEE
257 WE 263 = E/W
B B 264 = WEB
260 /WE 265 = B/
T T 266 = /WET
0. s0 = '/' - neni kod (no code)
s1 = '/' (\code\min = 2B ... \'/'\ = 1B)
zapis Data + '/' ('/') (Data+s0)
1. s0 = 'W' - neni kod
s1 = '/W' - tabulka zapis kod 256='/W' do tabulky
(\code\min = 2B ... '/W')
(s1=s0(old)='/', new s0='W', s1=s1+s0[1]='/W')
zapis Data + 'W' ('/W')
2. s0 = 'E' - neni kod
s1 = 'WE' - tabulka zapis kod 257='WE' do tabulky
zapis Data + 'E' ('/WE')
3. s0 = 'D' - neni kod
s1 = 'ED' - tabulka zapis kod 258='ED'
zapis Data + 'D' ('/WED')
! 4. s0 = 256 - KOD
! s0 = 256 = '/W'
! s1 = 'D/' zapis kod 259='D/'
! (s1=s0='D', new s0='/W', s1=s1+s0[1]='D/')
! zapis Data + '/W' ('/WED/W') (Data+s0)
! 5. s0 = 'E'
! s1 = '/WE' zapis kod 260='/WE'
! zapis Data + 'E' ('/WED/WE') (Data+s0)
!! 6. s0 = 260 - kod
!! s0 = '/WE'
!! s1 = 'E/' zapis kod 261='E/'
!! (s1=s0='E', new s0='/WE', s1=s1+s0[1]='E/')
!! zapis Data + '/WE' ('/WED/WE/WE') (Data+s0)
!! 7. s0 = 261 - kod
!! s0 = 'E/'
!! s1 = '/WEE' zapis kod 262='/WEE'
!! (s1=s0='/WE', new s0='E/', s1=s1+s0[1]='/WEE')
!! zapis Data + 'E/' ('/WED/WE/WEE/') (Data+s0)
8. s0 = 257 - kod
s0 = 'WE'
s1 = 'E/W' zapis kod 263='E/W'
(s1=s0='E/', new s0='E/', s1=s1+s0[1]='E/W')
zapis Data + 'WE' ('/WED/WE/WEE/WE') (Data+s0)
.......
! Selhani kodu (Errors from code)
-------------------------------
Data = JOEYN JOEYN JOEYN JOEY
kod 288 = JOEY
kod 300 = JOEYN
...
kod 400 = JOEYNJ
kod 401 = JOEYNJO
Nejlepsi Code = ... 288 N 300 300 288 ... 9 (mLZW)
LZW Code = ... 288 N 300 J OEYN 288 ... 12 (LZW)
----- -----
300 400
Hlavni menu
Je velmi podobny kosinove transformaci, k velkemu cislu se postupne pricitaji mensi a mensi.
Vyuziva cetnosti znaku k pocitani cisla, ktere predstavuje vysledny retezec.
Cislo se pak prevede na souborovy zapis cisla (16-32 bitu)
Priklad 13:
Kodovani:
---------
pravd. low - high
--------------------
A 0,4 <0 - 0,4) ( 0 .. 0,399999)
B 0,3 <0,4 - 0,7)
C 0,2 <0,7 - 0,9) (0,7 .. 0,8999)
D 0,1 <0,9 - 1> (0,9 .. 1)
---
1,0
Symb Low High
------------------
A 0 0,4
B 0,16 0,28
B 0,208 0,244
C 0,2332 0,2404
Code = <0,2332 ; 0,2404> -> (0,24) -> zapis desetinne cislo
Code -> file
Princip:
--------
1 - Low = 0
2 - High= 1,0
/
3 - | Symbol = Data(new)
4 - | range(Symbol) -> low(Symbol) .. high(Symbol)
5 - | High = Low + range * high(Symbol)
6 - | Low = Low + range * low(Symbol)
\
7 - Select number(Low, High)
1 - Low = 0
2 - High= 1,0
/
Range = High-Low = 1,0
3 - A
4 - A (0,0 - 0,4)
5 - High= 0 + 1,0 * 0,4 = 0,4
6 - Low = 0 + 1,0 * 0 = 0
Range = High-Low = 0,4
3 - B
4 - B (0,4 - 0,7)
5 - High= 0 + 0,4 * 0,7 = 0,28
6 - Low = 0 + 0,4 * 0,4 = 0,16
Range = High-Low = 0,12
3 - B
4 - B (0,4 - 0,7)
5 - High= 0,16 + 0,12 * 0,7 = 0,244
6 - Low = 0,16 + 0,12 * 0,4 = 0,208
Range = High-Low = 0,036
3 - C
4 - C (0,7 - 0,9)
5 - High= 0,208 + 0,036 * 0,9 = 0,2404
6 - Low = 0,208 + 0,036 * 0,7 = 0,2332
7 - 0,24
X Problem 1: Na kolik desetinnych mist kodujeme? Nutne zapsat.
Dekodovani:
-----------
number s low high range
---------------------------
0.24 A 0 0.4 0.4
0.6 B 0.4 0.7 0.3
0.6666... B 0.4 0.7 0.3
0.8888886 C 0.7 0.9 0.2
/
| 1 - number
| 2 - find symbol(number)
| 3 - range(Symbol) = high(symbol)-low(symbol)
| 4 - number-low(symbol)
| 5 - number/range
\
Princip:
--------
1 - 0,24
2 - A <0,0 - 0,4) -> A
3 - range(A) = 0,4
4 - 0,24 - 0 = 0,24
5 - 0,24 / 0,4 = 0,6
1 - 0,6
2 - B <0,4 - 0,7) -> B
3 - range(B) = 0,3
4 - 0,6 - 0,4 = 0,2
5 - 0,2 / 0,3 = 0,6666666
1 - 0,6666
2 - B <0,4 - 0,7) -> B
3 - range(B) = 0,3
4 - 0,6666 - 0,4 = 0,2666
5 - 0,2666 / 0,3 = 0,8888888
1 - 0,8888
2 - C <0,7 - 0,9) -> C
3 - range(C) = 0,2
4 - 0,8888 - 0,7 = 0,1888
5 - 0,1888 / 0,2 = 0,9444444
X 1 - 0,94444
X 2 - D <0,9 - 1,0> -> D
X ...
X Problem 2: Je nutne znat pocet symbolu. takze bud kodovat vzdy stejny pocet znaku nebo nekde zapsat pocet.
Hlavni menu
Je to prehazeni dat podle pravidel serazeni na jine s minimalnim navysenim.
Vysledek by mohl byt priznivejsi pro kompresi.
Priklad 14:
Data->BWT
---------
Data 1423422 (7) [1-4] = IN
ABCDEFG Serazeni podle A
IN 1423422 1423422 1 = index
rot+1 2142342 2142342 2
rot+2 2214234 2214234 3
rot+3 4221423 2342214 4
rot+4 3422142 3422142 5
rot+5 2342214 4221423 6
rot+6 4234221 4234221 7
A G A G
rot+1 = 423422x -> x423422
rot+2 = 42342yx -> yx42342 == rot+1(rot+1) x42342y -> yx42342
OUT = G + index
OUT = 2244231 + [1] (9)
(1..4 = 00 01 10 11, index = 7 = 110 = 0110 .. 2 jednotky)
(129% = 9/7)
(Data = 1..256, \Data\=250 -> \index\=1 -> 100,4% = 251/250)
BWT->Data
---------
BWT = 2244231 + [1]
(G serazeno) = sloupec A = 1222344 (-a-)
(-a-) . gab . gab . gab . gab . gab (-b-) ga bcdef
[1] 1 . 21-> =>214 .x214 .x214 .x214 [1] 1 21 42342
2 . 22 22=> #>221 .x221 .x221 2 22 14234
3 . 42 42 42#> . 422 . 422 3 42 21423
4 . 42 42 42 . 42*> . 423 4 42 34221
5 . 23 23 23 *>23 .x23>> 5 23 42214
6 . 34 34 34 34 >>34 6 34 22142
7 ->14 x14 x14 x14 x14 7 14 23422
GA GA GA GA GA
[1,7] [2,5] [3,1] [4,5] [5,6] ...
V premene Data->BWT v nekonecnem radku pokracuje hodnota z 'G' hodnotou 'A'.
Z teto zavislosti se da urcit vektor premisteni.
Pri znalosti serazovaciho algoritmu (v nasem pripade, pokud hodnota n se rovna n+1, pak je nevymeni navzajem), lze tento vektor dopocitat.
(-b-)
b[1]: GA=21, posledni cislo je 1
najdi prvni volnou hodnotu ve sloupci 'g' zacinajici 1,
to je radek '7', hodnota 14, '7'
-> b[1] = a[7] = 4 -> vektor [1->7]
b[2]: GA=22, posledni cislo je 2
najdi prvni volnou hodnotu ve sloupci 'g' zacinajici 2,
-> to je radek '1', hodnota 23, '1' OK
-> b[2] = a[1] = 1 -> vektor [2->1]
b[3]: GA=42, posledni cislo je 2
najdi prvni volnou hodnotu ve sloupci 'g' zacinajici 2,
-> to je radek '1', hodnota 22, '1' OK
(protoze radek 5 uz byl pouzity pro c[2])
-> b[3] = a[2] = 2 -> vektor [3->2]
...
[1->7] [2->1] [3->2] [4->5] [5->6] [6->3] [7->4]
b[1]=a[7] ; b[2]=a[1] ; b[3]=a[2] ...
c[1]=b[7] ; c[2]=b[1] ; c[3]=b[2] ...
OUT2 = abcdefg = 1423422
Priklad 15: Vetsi rychlost
DATA->BWT
1423422 -> 1423422 1
-> AG: 12 22 24 43 32 24 41
->!seradim podle 'A': 12 22 24 24 32 43 41
-> zapisi: 2 2 4 4 2 3 1
Hlavni menu
DCT - Kosinova transformace (diskretni)
WLT - WaveLet transformace
Kdyz data hodnot propojime, vytvorime krivku.
Tuto krivku pak muzeme popsat jako nekonecny soucet nekonecne krivky (bezici vlny) s ruznymi parametry.
Nejcasteji se pouziva Kosinus, ale take jine krivky lze vyuzit.
Vychazi se z Fourrierovi transformace pro rovnici:
X(f) = integral[-nek..+nek] ( x(t) * e^( i2pi*f*t) ) dt
x(t) = integral[-nek..+nek] ( X(f) * e^(-i2pi*f*t) ) df
X(f) = 1/T * integral[0..T] ( x(t) * e^(i 2pi/T * f*t) ) dt
-> x(t) = suma[k=-nek..+nek] (X(f) * e^( i2pi/T * f*t) )
nek ... nekonecno
Xf=yk
Pro diskretni body
-> do xl = suma[k=0..N-1] (yk * e^( 2pi/T * i*k*l) ) l=0,1,..N-1
-> zpet yk = suma[k=0..N-1] (xk * e^( 2pi/T * i*k*l) ) k=0,1,..N-1
Fourrier
e^(-ix) = cos(x)-i*sin(x)
-> do x(t) = suma[k=0..N-1] (ak * cos( (2pi/T)*i*k*t) ) +
+suma[k=0..N-1] (bk * sin( (2pi/T)*i*k*t) )
Hadamard transform (DHT) 1D
binary 01 a +1
do X(k) = (1/N)^0,5 * suma[n=0..N-1] ( x(n)*(-1)^( suma[i=0..m-1] ( bi(n) * bi (k) )
zpet x(n) = (1/N)^0,5 * suma[k=0..N-1] ( X(k)*(-1)^( suma[i=0..m-1] ( bi(n) * bi (k) )
k=0..N-1
DWT->Zerotree->Arithmetic
inverse discrete wavelet transform IDWT
ck^(j+1) = suma[n] ( h\k-2n\ * cn^(j) + g\k-2n\ * dn^(j) )
c^J J=Log[2,N] (2^N)
j+1 scalin koeficienty
Fourier series analysis, where sinusoids are chosen as the basis function, wavelet analysis is also based on a decomposition of a signal using an orthonormal (typically, although not necessarily) family of basis functions. Unlike a sine wave, a wavelet has its energy concentrated in time. Sinusoids are useful in analyzing periodic and time-invariant phenomena, while wavelets are well suited for the analysis of transient, time-varying signals.
Fourier ýada anal>za, kde sinusoida jsou vybrat si jako z klad funkce, vlnka anal>za je tak' zalo§en na rozkl d n" sign lu pou§"v n" pý"mo--norm ln" (typicky, akoli ne nutn_) rodina z kladu funkce. Ne jako sinusovka, vlnka m jeho energii koncentrovanou vas. Sinusoids jsou u§iten" v analyzov n" periodick'ho a asu-nem_nn> _kazy, zat"mco vlnka jsou vhodn pro anal>zu pýechodn>, as-prom_nn' sign ly.
... ? pulz?
Hartley Transform (FHT Fast Hartley transform)
e^(-ix) = cos(x)-i*sin(x)
cas(x) = cos(x)+sin(x)
HNf (X) = 1/N * Suma[t=0..N-1] ( Xt * cas(2pi/N * f*t) ) = Ff
HNt^-1(F) = Suma[f=0..N-1] ( Ff * cas(2pi/N * f*t) ) = Xt
(for bin?)
Ht(v) = H\t-1\(v) + H\t-1,odd\(v) * cos(2pi*v/N) + H\t-1,even\(v) * sin(2pi*v/N)
Mallat Wavelets
Normalized Haar Transform
Walsh Tranform
Hlavni menu
ZTRATOVA
Fourrierova transformace je premena jakekoliv krivky v intervalu [0..2PI] na soucet nekonecne radu kosinusovek a sinusovek.
[-PI..PI] kosinova, [0..2PI] sinova rada
Rovnice jsou vyvozeny z integracnich rovnic Fourrierovi transformace pro disktretni body (konecny pocet bodu krivky).
Fourrierova transformace - viz teorie signalu (signal processing), matematika - integrace
Rovnice:
/1D/ ... FFT (Fast Fourrier Transformation - fast discrete cosine Fourr transf)
FFT(u) = (2/N)^0,5 * C(i) * E[i=0..N-1] ( f(i) * cos(PI/(2N)*(2i+1)*u) )
f(i) = (2/N)^0,5 * E[u=0..N-1] ( C(u) * FFT(u) * cos(PI/(2N)*(2u+1)*i) )
---N=64---
FFT(u)64 = Table1Da(i)64 * E[i=0..63] f(i)64x64 * Table1Db(i,u)64x64
f(i)64 = E[u=0..63] FFT(u)64x64 * Table1Dc(u,i)64x64
N = 64 [1,2,3 .. 64]
i,u = <0..63> = [0..N-1] = 0,1,2,3...
i=0 : C(i) = (1/N)^0,5 = 0,125
i>0 : C(i) = (2/N)^0,5 = 0,177
E ... suma
Table1Da(i) = 0,177 * C(i)
Table1Db(i,u) = cos(PI/128*(2i+1)*u)
Table1Dc(u,i) = 0,177 * C(u) * cos(PI/128*(2u+1)*i)
64 = tabulka s 64 hodnotami 64x64 = 64 tabulek s 64 hodnotami
... to je jen pro predstavu s jak velkou pameti se pracuje
Tabulky obsahuji konstantni hodnoty, takze cely prevod na DCT a zpet je jen otazkou nasobeni 2 nebo 3 hodnot.
/2D/ ... DCT (Discrete Cosine Transformation)
DCT(u,v) = (2/M)^0,5 * (2/N)^0,5 * C(i)*C(j) * E[i=0..M-1] E[j=0..N-1] ( f(i,j) * cos(PI/(2M)*(2i+1)*u) * cos(PI/(2N)*(2j+1)*v) )
f(i,j) = (2/M)^0,5 * (2/N)^0,5 * E[u=0..M-1] E[v=0..N-1] ( C(u)*C(v) * DCT(u,v) * cos(PI/(2M)*(2u+1)*i) * cos(PI/(2N)*(2v+1)*j) )
---8x8 M=N=8---
DCT(u,v) = Table2Da(i,j) * EE[i,j=0..7] f(i,j) * Table2Db(i,j,u,v)
f(i,j) = EE[u,v=0..7] DCT(u,v) * Table2Dc(u,v,i,j)
N = M = 8 (8x8)
i,j,u,v = 0..7 = <0..N-1>
i=0 (1/M) i>0 (2/M)
j=0 (1/N) j>0 (2/N)
i=0, j=0 : C(i) = (1/M)^0,5 * (1/N)^0,5 = 0,125
i=0, j>0 : C(i) = (1/M)^0,5 * (2/N)^0,5 = 0,177
i>0, j=0 : C(i) = (2/M)^0,5 * (1/N)^0,5 = 0,177
i>0, j>0 : C(i) = (2/M)^0,5 * (2/N)^0,5 = 0,25
Table2Da(i,j) = 1/4 * C(i)*C(j)
Table2Db(i,j,u,v) = cos(PI/16*(2i+1)*u) * cos(PI/16*(2j+1)*v)
Table2Dc(u,v,i,j) = 1/4 * C(u)*C(v) * cos(PI/16*(2u+1)*i) * cos(PI/16*(2v+1)*j)
Tabulky obsahuji konstantni hodnoty, takze cely prevod na DCT a zpet je jen otazkou nasobeni 2 nebo 3 hodnot.
Priloha 2: Priklad JPEG 16 DCT 1D
Priloha 3: Priklad JPEG 4x4 DCT 2D
JPEG (Joint Photographic Experts Group)
Jpeg - DCT
Neztratovy Jpeg (Lossless JPEG)
Metoda porovnava nekolik sousednich pixelu k jednomu a zapise pouze rozdilne hodnoty od prvniho.
Tyto byvaji obvykle male jako u DCT, proto Jpeg. Nepouziva ztratovou DCT.
Jbig - multi stranky (vice obr za sebou, jako animovany gif, video), efektni na bw obrazky
Progressive JPEG - jako gif, nejdriv se zobrazi obr v horsi kvalite nez se stahne zbytek obrazku z netu
Jpeg2000 - sdruzuje vetsinu obrazku a metod, jako to dela TIFF (CCITT,T.85 JBIG(T.82),T.43 JBIG(T.82) color,T.81 JPEG)
Jpeg(DCT);
1. VSTUP
2. On/Off Barevna transformace
3. On/Off Podvzorkovani
4. DCT
5. Uprava kvantizacni tabulkou
6. Finalni uprava a komprese - Huffman/ZeroTree/jina , LZW/jina
7. JPG
2. Barevna transformace - prevod RGB do jin'ho modelu - UWB (YCBCR).
Y = 0,299 . R + 0,587 . G + 0,114 . B
CB = 0,5643 . (B-Y)
CR = 0,7133 . (R-Y)
Y je v posdstate obrazek prevedeny na sedivy nebarevny
CB,CR jsou informace o barve
Pri transformaci muzou vzniknou male ztraty, pokud nepocitame presne.
3. Podvzorkovani
Slozka Y se obvykle nezmensuje, CB,CR tabulky se zmensi 4x (4 sousedni body se prepocitaji na 1)
1:1:1 - bez podvzorkovani
1:1:2 - CB,CR / 4
1:2:2 - Y,CB,CR /4
4. DCT
5. Uprava kvantizacni tabulkou - je to vlastne vydeleni hodnot DCT cisly tabulkou. Cim vetsi cislo, tim mensi ma koeficient z DCT vyznam. tabulka je volena intuitivne.
Quantization
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
6. Finalni uprava - Huffman (DCT) / ZeroTree (DWT)
Huffman
Z tabulky se oddeli stejna slozka (prvni koeficient), ktery je mnohem vetsi nez ostatni a zapise se zvlast.
Po te, se prepisi data podle vzoru:
Zig-zag scan alternate scan
0-01 05-06 14-15 27-28 0 4 6 20 22 36 38 52
/ / / / / / / | | | |/ | |/ | |
2 04 07 13 16 26 28 42 1 5 7 21 23 37 39 53
|/ / / / / / /| | / / |
3 08 12 17 25 30 41 43 2 8 19 24 34 40 50 54
/ / / / / / / | | | | | | | |
9 11 18 24 31 40 44 53 3 9 18 25 35 41 51 55
|/ / / / / / /| / / / /
10 19 23 32 39 45 52 54 10 17 26 30 42 46 56 60
/ / / / / / / | | | | | | | |
20 22 33 38 46 51 55 60 11 16 27 31 43 47 57 61
|/ / / / / / /| | | | | | | | |
21 34 37 47 50 56 59 61 12 15 28 32 44 48 58 62
/ / / / / / / | | | | | | | |
35-36 48-49 57-58 62-63 13-14 29 33 45 49 59 63
Priklad:
Zig-Zag Mapa hodnot RLE/huf huf
12 34 0 54 0 0 0 0 1101000 tab1 nul tab2
87 0 0 12 0 0 0 0 1001000 1 0 10 1 10
16 0 0 0 0 0 0 0 1000000 01 1 01 01 01
0 0 0 0 0 0 0 0 0000000 001 2 0011 001 0011
0 0 0 0 0 0 0 0 0000000 0001 3 0010 0001 0010
0 0 0 0 0 0 0 0 0000000 00001 4 0001 00001 0001
0 0 0 0 0 0 0 0 0000000 000001 5 0000 00000 11
0 0 0 0 0 0 0 0 0000000 000000 6 11 0.end 0000
12, 34,87,16,0,0,54,0,0,0,0,0,0,12,0 (14+50) ... Zig-Zag
12 + 34|87|16|0 0 54|0 0 0 0 0 0 12|0 (1+13+50)... RLE deleni, separace prvniho cisla
tab1:10 10 10 0011 11 10 1111111111111111 11(0011) + 34,87,16,54,21
(16% = 10/64) (1 + 4 + 5)
tab2:10 10 10 0011 11 01 0000 + 34,87,16,54,21
(14% = 9/64) (1 + 3 + 5)
Pozn.: Tabulky Huf/RLE jsou me smyslene.
Hlavni menu
ZTRATOVA
WLT(s,0) = 1/(s)^0,5 * f(0)*M(0)*s + E<1..n> f(0)^(1/2)/1!*M(1)*s^2 + O( s^(2+2) )
x! = 1*2*3* ... *x
Mp = integ (t^p PSI(t) dt)
Quantization
Zigzag Scan
/DPCM on DC component (ss slozka)
\RLE on AC Components (st slozka)
Entropy Coding - huffman/Arithmetic
Zerotree (Jerome M. Shapiro 1993)
(mozna neco jineho EPIC = 2 EPIC (Efficient Pyramid Image Coder 1990)
otec + potomci = strom
A + AE,AF,AG,AH
E + E1,E2,E3,E4
...
otec + vsichni potomci
A + AE,AF,AG,AH + E1,E2,E3,E4 + F1,F2,F3,F4 + G1,G2,G3,G4 + H1,H2,H3,H4
Morton scan Raster scan
01-02|05-06|17-18 21-22 01-02|05-06|17-18-19-20
--/--| / | / / --/--| / |
03-04|07-08|19-20 23-24 03-04|07-08|21-22-23-24
-----+-----| -----+-----|
09-10|13-14|25-26 29-30 09-10|13-14|25-26-27-28
/ | / | / / / | / |
11-12|15-16|27-28 31-32 11-12|15-16|29-30-31-32
-----------+----------- -----------+-----------
33-34 37-38|49-50 53-54 33-34-35-36|49-50-51-52
/ / | / / |
35-36 39-40|51-52 55-56 37-38-39-40|53-54-55-56
| |
41-42 45-46|57-58 61-62 41-42-43-44|57-58-59-60
/ / | / / |
43-44 47-48|59-60 63-64 45-46-47-48|61-62-63-64
Rozdil ve cteni hodnot? Obvykle prvnich 16 hodnot byva ruznych, ostatni jsou si velmi podobne.
Takze bud pokracujeme ve cteni zpusobem Morton nebo ty ostatni prepiseme normalne (Raster).
63 -34 49 10 7 13 -12 7 A B BE BF E1 E2 F1 F2
-31 23 14 -13 3 4 6 -1 C D BG BH E3 E4 F3 F4
15 14 3 -12 5 -7 3 9 CI CJ DM DN G1 G2 H1 H2
-9 -7 -14 8 4 -2 3 2 CK CL DO DP G3 G4 H3 H4
-5 9 -1 47 4 6 -2 2 I1 I2 J1 J2 M1 M2 N1 N2
3 0 -3 2 3 -2 0 4 I3 I4 J3 J4 M3 M4 N3 N4
2 -3 6 -4 3 6 3 6 K1 K2 L1 L2 O1 O2 P1 P2
5 11 5 6 0 3 -4 4 K3 K4 L3 L4 O3 O4 P3 P4
c D1 S1 Z1 D2 S2 Z2 D3 S3 Z3 ... D4,D5,D6
1 21 321
A 63 P 1 >=48 56 Z 1 >=56 60 Z 1>=60 62
B -34 N 0 <48 -40 T 0 <40 -36 Z 0 <36 -36
C -31 IZ <32 0 N 1 >=24 -28 Z 1 >=28 -30
D 23 T <32 0 P 0 <24 20 Z 1 >=20 22
BE 49 P 1 >=48 56 0 <56 52 Z 0 <52 50
BF 10 T <32 0 P 0 <12 10
BG 14 T <32 0 P 1 >=12 14
BH -13 T <32 0 N 1 >=12 -14
CI 15 T <32 0 T <16 0 P 1 >=12 14
CJ 14 IZ <32 0 T <16 0 P 1 >=12 14
CK -9 T <32 0 T <16 0 N 0 <12 -10
CL -7 T <32 0 T <16 0 T <8 0
DM 3 T <16 0 T <8 0
DN -12 T <16 0 N 1 >=12 -14
DO -14 T <16 0 N 1 >=12 -14
DP 8 T <16 0 P <12 10
E1 7 T <32 O .E,F,G,H(1,2,3,4)
E2 13 T <32 0 .I,J,K(1,2,3,4)
E3 3 T <32 0 .N,O,P(1,2,3,4)
E4 4 T <32 0 .
J1 -1 T <32 0 .
J2 47 P 0 >48 40 1 >=40 44 .
J3 -3 T <32 0
J4 2 T <32 0
T=(64,32,16,8,4, 2,1) (data max = 64)
1. D1: T=64 u=T/2=32 v=u/2=16 w=v/2=8
S1: [32,48):40 [48,64):56 32=u=x1 48=u+v=y1 40=(x+w) ... 48=y=x2 64=y+v=y2
2. A: c( 63), |c|>='u'(32) (PNZ) + c( 63) je kladny ... P ('u(32)'<|c|(63)<'T'(64))
B: c(-34), |c|>='u'(32) (PNZ) + c(-34) je zaporny ... N ('u'<|c|<)
C: c(-31), |c|<'u'(32) (TZ) + vsichni potomci > 'u' ... Z
D: c( 23), |c|<'u'(32) (TZ) + vsichni potomci < 'u' ... T
3. BE: B neni T: c( 49), |c|>='u'(32) (PNZ) + c( 49) je kladny ... P
BF,BG,BH
B neni T: c( ), |c|<'u'(32) (TZ) + potomci < 'u' ... T
CI: C neni T: c( 15), |c|<'u'(32) (TZ) + potomci < 'u' ... T
CJ: C neni T: c( 14), |c|<'u'(32) (TZ) + potomci > 'u' ... Z
CK,CL, DM,DN,DO,DP:
C/D neni T: c( ), |c|<'u'(32) (TZ) + potomci < 'u' ... T
4. E1,E2,E3,E4
BE neni T: c( ), |c|<'u'(32) (TZ) ... T
J1: CJ neni T: c( -1), |c|<'u'(32) (TZ) ... T
J2: CJ neni T: c( 47), |c|>='u'(32) (PNZ) + c( 47) je kladny ... P
J3: CJ neni T: c( -3), |c|<'u'(32) (TZ) ... T
J4: CJ neni T: c( 2), |c|<'u'(32) (TZ) ... T
(Z nebo T? Nemaji potomky, nesejde na tom, budu je davat T pro vetsi pocet T)
Ostatni hodnoty jsou oznacene jako strom v jejich Otcich, takze se nezapisuji.
5. S1: 0=[32,48):40 1=[48,64):56 'u'(32)<|c|<'T'(64)
A: |c|(63)>='y'(48) ... 1 (Z1[ A]=x2+w=P56=+56) 0=[32,48):40 1=[48,64):56
B: |c|(34)<'y'(48) ... 0 (Z1[ B]=x1+w=N40=-40)
BE: |c|(49)>='y'(48) ... 1 (Z1[BE]=x2+w=P56=+56)
J2: |c|(47)<'y'(48) ... 0 (Z1[J2]=x1+w=P40=+40)
-------------------------------------------------------
6. D2: T=32 u=16 v=8 w=4
S2: [16,24):20 [24,32):28 [32,40):36 [40,48):44 [48,56):52 [56,64):60
P/N cisla z D1 jsou dale povazovana za nulu s vyjimkou A.
A: A bude dal jako Z (Proc Z? Nevim, ja bych ho vubec neznacil)
B: potomci B <'u'(16) ... T (B, BE mame poznacene z D1)
C: c(-31), |c|>='u'(16) (PNZ) + c(-31) je zaporny ... N
D: c( 23), |c|>='u'(16) (PNZ) + c( 23) je kladny ... P
CI: C neni T: c( 15), |c|<'u'(16) (TZ) + potomci < 'u'(16) ... T
CJ,CK,CL, DM,DN,DO,DP:
C/D neni T: c( ), |c|<'u'(16) (TZ) + potomci < 'u'(16) ... T (J2 viz D1)
Ostatni hodnoty jsou oznacene jako strom v jejich Otcich, takze se nezapisuji.
S2: [16,24):20 [24,32):28 [32,40):36 [40,48):44 [48,56):52 [56,64):60
S2: A: |c|(63) 0=[48,56):52 1=[56,64):60 ... 1 (Z1[ A]=+60) (D1: >32 >48)
B: |c|(34) 0=[32,40):36 1=[40,48):44 ... 0 (Z1[ A]=-36) (D1: >32 <48)
BE: |c|(49) 0=[48,56):52 1=[56,64):60 ... 0
J2: |c|(47) 0=[32,40):36 1=[40,48):44 ... 1
+ nove P/N
0=[16,24):20 1=[24,32):28 'u'(16)<|c|<'T'(32)
C: |c|(31) >'y'(24) ... 1
D: |c|(23) <'y'(24) ... 0
---------------------------------------------------------
7. D3: T=16 u=8 v=4 w=2
S3: [ 8,12) [12,16) [16,20) [20,24) [24,28) [28,32) [32,36)
[36,40) [40,44) [44,48) [48,52) [52,56) [56,60) [60,64)
...
D1: pnzt pttttztt tttttptt
S1: 1010
D2: ztnp tttttttt
S2: 1001 10
D3: zzzz zppnppnttnnp tpttnttttttttptttptttttttttptttttttttttt
S3: 1001 11 01111011011000
D4: zzzzzzztztznzzzzpttptpptpnptntttttptpnpppptttttptptttpnp
S4: 11011111011001000001110110100010010101100
D5: zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt
S5: 10111100110100010111110101101100100000000110110110011000111
D6: zzzttztttztttttnnttt
(t=120 z=39 p=42 n=18 T=1 Z=00 P=011 N=010 / 0=0 1=1)
Pro mensi presnost D1S1-D3S3, pro vetsi D1S1-DxSx
Vysvetlivky:
D=dominant pass S=subordinate pass Z1,Z2,Z3=zpetne dekodovana hodnota
D: P=plus, N=minus, T=ZeroTree, Z=nula bez potomku, IZ=nula
(D: P=positive, N=negative, T=ZeroTree, Z=Zero, IZ=Izolated zero)
potomci = 1 nebo vice z potomku vsichni potomci = 1 nebo vice ze vsech
otec + potomci = strom
A + AE,AF,AG,AH
E + E1,E2,E3,E4 (E / BE)
otec + vsichni potomci
A + AE,AF,AG,AH + E1,E2,E3,E4 + F1,F2,F3,F4 + G1,G2,G3,G4 + H1,H2,H3,H4
T u,v,w,x,y=pomocne promenne c=cislo z tabulky (coefficient)
P/N = +/- c>T/2
T,Z,IZ c<T/2
P/N/IZ=hodnoty s potomky
(Z=IZ, pro kazde Z budem uvazovat potomky, usporime kod)
Hlavni menu
Hadamard transform - trojuhelnikove spicky
Haar transform - trojuhelnik nahore i dole
Cube transform (1994 Bijaoui)
--------------
I(x,y)= cp(x,y) + E<j=1..p> wj(x,y)
wj<j=1..p>
cp ... represent the transformation of I
cp je velmi rozmazana verze obrazi I
Very reductant
Pyramidal transform ()
-------------------
less redundant
jako cubic, ale pro 2D
fi(x) = 2 E<k> tk fi(2x-k)
psi(x) = 2 E<k> hk fi(2x-k)
hk = (-1)^(1-k) * tk
tK = (0.5 , 0.5) und hK = (0.5 , -0.5),
hk = 1/(4*odmoc2) * (1+ sqrt(3), 3+sqrt(3), 3-s(3), 1-s(3)
Hlavni menu
?Metody:
?
1. Difference Mapping - (Mpeg-2) Algoritmus pocita rozdily mezi dvema a vice po sobe jdoucimi obrazky. Obvykle se provadi pro 8 nasledujicich obrazku filmu, prvni se nazyva klicovy snimek.
?
2. Kodovani DCT - (Mpeg-1) Snimky se ukladaji do jpegu. (Mpeg-2) Jenom klicove snimky se ukladaji do jpegu, ostatni Hufman a jine kody.
?
3. Zvuk je mozne ukladat pomoci DCT.
DRUHY MPEG FORMľTŢ:
MPEG-1: üeç" probl'm synchronizace datov>ch proud pro obraz a zvuk. Standardizuje zpsob k_dov n" videosekvenc" vhodn> pro evropskou i americkou televizi s datov>m proudem kolem 1,5 Mb/s pomoc" DCT a zpsob audiok_dov n" (Layer I-III). Softwarov implementace kodeku.
MPEG-2: Jako pýedchoz", ale vçeobecn_jç". Rozç"ýen o pýenos prostorov'ho obrazu Multiview a v"cekan lov> zvuk (Video DVD) Popisuje protokol pro komunikan" heterogenn" s"t_.
MPEG-4: Od ledna 1999. Popisuje multimedi ln" form ty vhodn' pro objekty vznikl' sn"m n"m nebo um_l>m vytv ýen"m. Zab>v se multiplexem a synchronizac" t_chto dat pro pýenos po rozs hl>ch s"t"ch. Nov' algoritmy pro zvuk CELP (6-24Kb/s) speci ln_ pro mluven' slovo a AAC a Twin VQ pro obecn> sign l se vzorkovac" frekvenc" od 8 kHz a kvalitou stýedovlnn'ho rozhlasu. Upravuje ochrany proti neleg ln"mu ç"ýen" materi l chr n_n>ch autorsk>mi pr vy.
MPEG-7: Bude pomoc" speci ln"ho jazyka umo§ĺovat identifikovat multimedi ln" objekty pro organizov n", tý"zen" a prohled v n".
MPEG-1: üeç" probl'm synchronizace datov>ch proud pro obraz a zvuk. Standardizuje zpsob k_dov n" videosekvenc" vhodn> pro evropskou i americkou televizi s datov>m proudem kolem 1,5 Mb/s pomoc" DCT a zpsob audiok_dov n" (Layer I-III). Softwarov implementace kodeku.
MPEG-2: Jako pýedchoz", ale vçeobecn_jç". Rozç"ýen o pýenos prostorov'ho obrazu Multiview a v"cekan lov> zvuk (Video DVD) Popisuje protokol pro komunikan" heterogenn" s"t_.
MPEG-4: Od ledna 1999. Popisuje multimedi ln" form ty vhodn' pro objekty vznikl' sn"m n"m nebo um_l>m vytv ýen"m. Zab>v se multiplexem a synchronizac" t_chto dat pro pýenos po rozs hl>ch s"t"ch. Nov' algoritmy pro zvuk CELP (6-24Kb/s) speci ln_ pro mluven' slovo a AAC a Twin VQ pro obecn> sign l se vzorkovac" frekvenc" od 8 kHz a kvalitou stýedovlnn'ho rozhlasu. Upravuje ochrany proti neleg ln"mu ç"ýen" materi l chr n_n>ch autorsk>mi pr vy.
MPEG-7: Bude pomoc" speci ln"ho jazyka umo§ĺovat identifikovat multimedi ln" objekty pro organizov n", tý"zen" a prohled v n".
MPEG-2 video bitstream compression),
epic (efficient Pyra-mid image coder)
Hlavni menu
White/Black ... x=vzdalenost
Terminating Code word
x W B x W B
------------------------------------------------------------
0 00110101 0000110111 32 00011011 000001101010
1 00111 010 33 00010010 000001101011
2 0111 11 34 00010011 000011010010
3 1000 10 35 00010100 000011010011
4 1011 011 36 00010101 000011010100
5 1100 0011 37 00010110 000011010101
6 1110 0010 38 00010111 000011010110
7 1111 00011 39 00101000 000011010111
8 10011 000101 40 00101001 000001101100
9 10100 000100 41 00101010 000001101101
10 00111 0000100 42 00101011 000011011010
11 01000 0000101 43 00101100 000011011011
12 001000 0000111 44 00101101 000001010100
13 000011 00000100 45 00000100 000001010101
14 110100 00000111 46 00000101 000001010110
15 110101 000011000 47 00001010 000001010111
16 101010 0000010111 48 00001011 000001100100
17 101011 0000011000 49 01010010 000001100101
18 0100111 0000001000 50 01010011 000001010010
19 0001100 00001100111 51 01010100 000001010011
20 0001000 00001101000 52 01010101 000000100100
21 0010111 00001101100 53 00100100 000000110111
22 0000011 00000110111 54 00100101 000000111000
23 0000100 00000101000 55 01011000 000000100111
24 0101000 00000010111 56 01011001 000000101000
25 0101011 00000011000 57 01011010 000001011000
26 0010011 000011001010 58 01011011 000001011001
27 0100100 000011001011 59 01001010 000000101011
28 0011000 000011001100 60 01001011 000000101100
29 00000010 000011001101 61 00110010 000001011010
30 00000011 000001101000 62 00110011 000001100110
31 00011010 000001101001 63 00110100 000001100111
Make Up Codes
x W B x W B
------------------------------------------------------------
64 11011 0000001111 1344 011011010 0000001010011
128 10010 000011001000 1408 011011011 0000001010100
192 01011 000011001001 1472 010011000 0000001010101
256 0110111 000001011011 1536 010011001 0000001011010
320 00110110 000000110011 1600 010011010 0000001011011
384 00110111 000000110100 1664 011000 0000001100100
448 01100100 000000110101 1728 010011011 0000001100101
512 01100101 0000001101100 1792 00000001000
576 01101000 0000001101101 1856 00000001100
640 01100111 0000001001010 1920 00000001101
704 011001100 0000001001011 1984 000000010010
768 011001101 0000001001100 2048 000000010011
832 011010010 0000001001101 2112 000000010100
896 011010011 0000001110010 2176 000000010101
960 011010100 0000001110011 2240 000000010110
1024 011010101 0000001110100 2304 000000010111
1088 011010110 0000001110101 2368 000000011100
1152 011010111 0000001110110 2432 000000011101
1216 011011000 0000001110111 2496 000000011110
1280 011011001 0000001010010 2560 000000011111
Pro >= 1792 se pouzivaji stejne kody, takze se musi pouzit i kod pro x=0. jedna se o vetsi rozliseni nez je obvykle
Hlavni menu
Priklad:
Hodnoty jsou ruzne zaokrouhlene, pro presne vypocty doporucuji minimalne 2, nejlepe 3 cisla za desetinou carkou
Prevod do DCT 1D a Zpet [1..16]
POZNAMKA: Doufam, ze to mam dobre spocitane. Kazdou chvili se spletu :) Ale vychazi to, tak snad je to oki.
100% dobre mam priklad pro 8x8, ale ten tu neuvadim.
IN (Data) -> OUT (DCT1D*C1D/Q1D)
14 17 49 122 -> 23 -15 -3 1
8 56 67 121 -> -1 -6 0 0
18 219 163 88 -> -4 5 4 0
147 88 195 121 -> -4 5 -3 -2
Table f->DCT1D (viz niz) | Table OUT*Q1D
1493,0 -465,8 -77,3 57,3 | 368 -165 -30 16
-29,7 -205,1 -4,6 -5,9 | -12 -72 0 0
-152,0 193,7 198,2 -17,2 | -56 65 64 0
-166,0 236,6 -197,5 -176,8 | -56 85 -66 -58
Table DCT1D*C1D | Table OUT*Q1D/C1D
373,3 -164,7 -27,3 20,3 | 92,0 -58,3 -10,6 5,7
-10,5 -72,5 -1,6 -2,1 | -4,2 -25,4 0 0
-53,8 68,5 70,1 -6,1 | -19,8 23,0 22,6 0
-58,7 83,6 -69,8 -62,5 | -19,8 30,1 -23,3 -20,5
OUT (DCT1D*C1D/Q1D) | OUT2 (DCT1D->f) (viz niz)
23 -15 -3 1 | 10 12 51 115
-1 -6 0 0 | 11 60 66 116
-4 5 4 0 | 21 215 160 88
-4 5 -3 -2 | 143 86 197 118
(zaporne hodnoty, protoze mam malo hodnot pro kosinus)
-----------------------------------------
Table C1D (integralni konstanta - vypoctena)
0,250 0,354 0,354 0,354
0,354 0,354 0,354 0,354
0,354 0,354 0,354 0,354
0,354 0,354 0,354 0,354
[N=16] x=0: C1D=(1/N)^(1/2)=0,25
x>0: C1D=(2/N)^(1/2)=0,354
Table Q1D (quantizacni konstanta - zvolena)
16 11 10 16
12 12 14 19
14 13 16 24
14 17 22 29
-----------------------------------------
IN -> OUT2
14 17 49 122 -> 10 12 51 115
8 56 67 121 -> 11 60 66 116
18 219 163 88 -> 21 215 160 88
147 88 195 121 -> 143 86 197 118
Rozdil IN-OUT2
4 5 -2 7
-3 -4 1 5
-3 4 3 0
4 2 -2 3
-----------
Table f->DCT1D
--------------
Prvni hodnota je souctem tabulky DCT
DCT1D[1][ 1] = IN[ 1]*((10*cosDCT1D[1][ 1])/10) = 14 * 1,0 = 14
DCT1D[1][ 5] = IN[ 5]*((10*cosDCT1D[1][ 5])/10) = 8 * 1,0 = 8
DCT1D[2][13] = IN[13]*((10*cosDCT1D[2][13])/10) = 147 * -0,8 = -114
-466 = suma(DCT1D[2][1..16]) = suma (14,16,43,94,5,26,19,12,-2,-64... ...-120)
1493 DCT1D[1][1..16] -466 DCT1D[2][1..16] -77 57
14 17 49 122 14 16 43 94 14 14 27 24 13 11 5 -58
8 56 67 121 5 26 19 12 -2 -31 -56 -119 -7 -56 -52 -35
18 219 163 88 -2 -64 -77 -56 -18 -182 -91 -17 5 169 162 78
147 88 195 121 -114 -78 -187 -120 29 49 162 119 69 -9 -124 -116
-30 -205 -5 -6
13 7 -19 -113 12 2 -38 -117 12 -3 -48 -68 11 -8 -47 12
-7 -21 26 112 -2 36 67 57 4 55 13 -101 8 16 -59 -77
17 84 -62 -81 -8 -218 -103 26 -15 43 160 49 11 193 -47 -88
-136 -34 75 112 141 68 -19 -107 -82 -86 -38 101 -14 84 92 -94
-152 194 198 -17
10 -12 -35 86 9 -15 -14 121 8 -17 10 101 7 -17 31 35
6 -40 -47 86 -1 -54 32 94 -7 -11 66 -67 -8 43 7 -107
13 -155 -115 62 -14 -103 156 9 -10 215 -32 -73 16 -21 -126 84
104 -62 -138 86 -146 26 172 -77 122 17 -191 67 -43 -56 194 -57
-166 237 -198 -177
5 -16 45 -47 4 -13 49 -108 3 -9 41 -120 1 -5 23 -77
-3 52 -62 46 4 5 -43 116 8 -47 37 -24 6 -49 64 -120
7 -202 151 -34 -17 139 -16 -41 -4 122 -136 86 18 -210 144 -68
-56 81 -180 46 130 -88 151 -35 -144 73 -108 24 93 -41 57 -12
Table 10*cosDCT1D (kvuli zobrazeni na www jsem dal hodnoty 10x)
-----------------
10 10 10 10 10 10 9 8 10 8 6 2 10 6 1 -5
10 10 10 10 6 5 3 1 -2 -6 -8 -10 -9 -10 -8 -3
10 10 10 10 -1 -3 -5 -6 -10 -8 -6 -2 3 8 10 9
10 10 10 10 -8 -9 -10 -10 2 6 8 10 5 -1 -6 -10
9 4 -4 -9 9 1 -8 -10 8 -2 -10 -6 8 -5 -10 1
-9 -4 4 9 -3 6 10 5 6 10 2 -8 10 3 -9 -6
9 4 -4 -9 -5 -10 -6 3 -8 2 10 6 6 9 -3 -10
-9 -4 4 9 10 8 -1 -9 -6 -10 -2 8 -1 10 5 -8
7 -7 -7 7 6 -9 -3 10 6 -10 2 8 5 -10 6 3
7 -7 -7 7 -1 -10 5 8 -8 -2 10 -6 -10 8 1 -9
7 -7 -7 7 -8 -5 10 1 -6 10 -2 -8 9 -1 -8 10
7 -7 -7 7 -10 3 9 -6 8 2 -10 6 -3 -6 10 -5
4 -9 9 -4 3 -8 10 -9 2 -6 8 -10 1 -3 5 -6
-4 9 -9 4 5 1 -6 10 10 -8 6 -2 8 -9 10 -10
4 -9 9 -4 -10 6 -1 -5 -2 6 -8 10 10 -10 9 -8
-4 9 -9 4 9 -10 8 -3 -10 8 -6 2 6 -5 3 -1
Table DCT1D->f
--------------
Prvni hodnota je souctem tabulky f podobne jako u DCT1D
f[1][5] = OUT[1]*((10*cosf1D[1][1])/10) = -4,2 * 0,9 = -3,8 = -4
10 12 51 115
92 -58 -10 5 92 -56 -9 4 92 -51 -6 1 92 -45 -2 -3
-4 -22 0 0 -2 -2 0 0 2 20 0 0 4 24 0 0
-14 15 13 0 14 -20 -22 0 14 -7 4 0 -14 23 19 0
-8 9 -5 -2 18 -23 13 6 -18 30 -19 -10 8 -27 23 13
11 60 66 116
92 -37 2 -5 92 -27 6 -6 92 -17 9 -4 92 -6 10 -2
4 7 0 0 2 -16 0 0 -2 -25 0 0 -4 -12 0 0
-14 -2 -19 0 14 -22 -4 0 14 11 22 0 -14 18 -13 0
8 14 -23 -16 -18 3 19 18 18 -19 -13 -20 -8 29 5 20
21 215 160 88
92 6 10 2 92 17 9 4 92 27 6 6 92 37 2 5
-4 12 0 0 -2 25 0 0 2 16 0 0 4 -7 0 0
-14 -18 -13 0 14 -11 22 0 14 22 -4 0 -14 2 -19 0
-8 -29 5 -20 18 19 -13 20 -18 -3 19 -18 8 -14 -23 16
143 86 197 118
92 45 -2 3 92 51 -6 -1 92 56 -9 -4 92 58 -10 -5
4 -24 0 0 2 -20 0 0 -2 2 0 0 -4 22 0 0
-14 -23 19 0 14 7 4 0 14 20 -22 0 -14 -15 13 0
8 27 23 -13 -18 -30 -19 10 18 23 13 -6 -8 -9 -5 2
Table 10*cosf1D
---------------
10 10 10 10 10 10 8 6 10 9 6 1 10 8 2 -5
9 9 8 8 4 1 -2 -5 -4 -8 -10 -10 -9 -10 -6 1
7 6 6 5 -7 -9 -10 -10 -7 -3 2 6 7 10 8 3
4 3 2 1 -9 -8 -6 -3 9 10 8 5 -4 -9 -10 -6
10 6 -2 -9 10 5 -6 -10 10 3 -8 -8 10 1 -10 -3
-9 -3 6 10 -4 6 10 3 4 10 2 -9 9 5 -8 -6
7 -1 -8 -10 -7 -10 -2 8 -7 5 10 1 7 8 -6 -9
-4 5 10 8 9 1 -8 -9 -9 -6 6 10 4 10 -2 -10
10 -1 -10 3 10 -3 -8 8 10 -5 -6 10 10 -6 -2 9
9 -5 -8 6 4 -10 2 9 -4 -6 10 -3 -9 3 6 -10
7 -8 -6 9 -7 -5 10 -1 -7 10 -2 -8 7 1 -8 10
4 -10 -2 10 -9 6 6 -10 9 -1 -8 9 -4 -5 10 -8
10 -8 2 5 10 -9 6 -1 10 -10 8 -6 10 -10 10 -10
-9 10 -6 -1 -4 8 -10 10 4 -1 -2 5 9 -9 8 -8
7 -10 8 -3 -7 3 2 -6 -7 9 -10 10 7 -6 6 -5
-4 9 -10 6 9 -10 8 -5 -9 8 -6 3 4 -3 2 -1
DCT - Kosinova transformace
Hlavni menu
Priklad:
Hodnoty jsou ruzne zaokrouhlene, pro presne vypocty doporucuji minimalne 2, nejlepe 3 cisla za desetinou carkou
Prevod do DCT 2D a Zpet [4x4]
IN (Data) -> OUT (DCT2D*C2D/Q2D)
14 17 49 122 -> 23 -9 -5 0
8 56 67 121 -> -12 -5 5 -2
18 219 163 88 -> 0 1 5 3
147 88 195 121 -> 2 1 -4 -2
Table f->DCT2D (viz niz) | Table OUT*Q2D
1493,0 -280,8 -152,0 -14,6 | 368 -99 -50 0
-412,7 -112,9 131,8 -94,0 | -144 -60 70 -38
9,2 16,2 162,5 147,5 | 0 13 80 72
84,5 24,0 -161,2 -88,1 | 28 17 -88 -58
Table DCT2D*C2D | Table OUT*Q2D/C2D
373,3 -99,3 -53,8 -5,2 | 92,0 -35,0 -17,7 0
-145,9 -56,4 65,9 -47,0 | -50,9 -30,0 35,0 -19
3,2 8,1 81,3 73,8 | 0 6,5 40,0 36
29,9 12,0 -80,6 -44,1 | 9,9 8,5 -44,0 -29
OUT (DCT2D*C2D/Q2D) | OUT2 (DCT2D->f) (viz niz)
23 -9 -5 0 | 15 12 48 119
-12 -5 5 -2 | 12 41 75 126
0 1 5 3 | 14 225 158 86
2 1 -4 -2 | 147 86 191 117
(zaporne hodnoty, protoze mam malo hodnot pro kosinus)
-----------------------------------------
Table C2D (integralni konstanta - vypoctena)
y\x 0 1 2 3
0 0,250 0,354 0,354 0,354
1 0,354 0,5 0,5 0,5
2 0,354 0,5 0,5 0,5
3 0,354 0,5 0,5 0,5
[M=4] x=0 -> (1/M) y>0 -> (2/M)
[N=4] y=0 -> (1/N) y>0 -> (2/N)
x=y=0: C=( (1/M)*(1/N) )^(1/2)=0,25
x>0;y=0: C=( (2/M)*(1/N) )^(1/2)=0,354
x=0;y>0: C=( (1/M)*(2/N) )^(1/2)=0,354
x>0;y>0: C=( (2/M)*(2/N) )^(1/2)=0,5
Table Q2D (quantizacni konstanta - zvolena)
16 11 10 16
12 12 14 19
14 13 16 24
14 17 22 29
-----------------------------------------
IN -> OUT2
14 17 49 122 -> 15 12 48 119
8 56 67 121 -> 12 41 75 126
18 219 163 88 -> 14 225 158 86
147 88 195 121 -> 147 86 191 117
Rozdil IN-OUT2
-1 5 1 3
-4 15 -8 -5
4 -6 5 2
0 2 4 4
-----------
Table f->DCT
------------
Prvni hodnota je souctem tabulky DCT
DCT[1][ 1] = IN[ 1]*((10*cosDCT[1][ 1])/10) = 14 * 1,0 = 14
DCT[1][ 5] = IN[ 5]*((10*cosDCT[1][ 5])/10) = 8 * 1,0 = 8
DCT[2][13] = IN[13]*((10*cosDCT[2][13])/10) = 147 * -0,8 = -114
-466 = suma(DCT[2][1..16]) = suma (14,16,43,94,5,26,19,12,-2,-64... ...-120)
1493 -281 -152 -15
14 17 49 122 13 7 -19 -113 10 -12 -35 86 5 -16 45 -47
8 56 67 121 7 21 -26 -112 6 -40 -47 86 3 -52 62 -46
18 219 163 88 17 84 -62 -81 13 -155 -115 62 7 -202 151 -34
147 88 195 121 136 34 -75 -112 104 -62 -138 86 56 -81 180 -46
-413 -113 132 -94
13 16 45 113 12 6 -17 -104 9 -11 -32 80 5 -15 42 -43
3 21 26 46 3 8 -10 -43 2 -15 -18 33 1 -20 24 -18
-7 -84 -62 -34 -6 -32 24 31 -5 59 44 -24 -3 77 -58 13
-136 -81 -180 -112 -125 -31 69 103 -96 57 127 -79 -52 75 -166 43
9 16 163 148
10 12 35 86 9 5 -13 -80 7 -9 -25 61 4 -11 32 -33
-6 -40 -47 -86 -5 -15 18 79 -4 28 34 -61 -2 37 -44 33
-13 -155 -115 -62 -12 -59 44 57 -9 110 82 -44 -5 143 -106 24
104 62 138 86 96 24 -53 -79 74 -44 -98 61 40 -57 127 -33
84 24 -161 -88
5 7 19 47 5 2 -7 -43 4 -5 -13 33 2 -6 17 -18
-7 -52 -62 -112 -7 -20 24 103 -5 37 44 -79 -3 48 -57 43
17 202 151 81 15 77 -58 -75 12 -143 -106 57 6 -187 139 -31
-56 -34 -75 -46 -52 -13 29 43 -40 24 53 -33 -22 31 -69 18
Table 10*cosDCT2D (kvuli zobrazeni na www jsem dal hodnoty 10x)
---------------
10 10 10 10 9 4 -4 -9 7 -7 -7 7 4 -9 9 -4
10 10 10 10 9 4 -4 -9 7 -7 -7 7 4 -9 9 -4
10 10 10 10 9 4 -4 -9 7 -7 -7 7 4 -9 9 -4
10 10 10 10 9 4 -4 -9 7 -7 -7 7 4 -9 9 -4
9 9 9 9 9 4 -4 -9 7 -7 -7 7 4 -9 9 -4
4 4 4 4 4 1 -1 -4 3 -3 -3 3 1 -4 4 -1
-4 -4 -4 -4 -4 -1 1 4 -3 3 3 -3 -1 4 -4 1
-9 -9 -9 -9 -9 -4 4 9 -7 7 7 -7 -4 9 -9 4
7 7 7 7 7 3 -3 -7 5 -5 -5 5 3 -7 7 -3
-7 -7 -7 -7 -7 -3 3 7 -5 5 5 -5 -3 7 -7 3
-7 -7 -7 -7 -7 -3 3 7 -5 5 5 -5 -3 7 -7 3
7 7 7 7 7 3 -3 -7 5 -5 -5 5 3 -7 7 -3
4 4 4 4 4 1 -1 -4 3 -3 -3 3 1 -4 4 -1
-9 -9 -9 -9 -9 -4 4 9 -7 7 7 -7 -4 9 -9 4
9 9 9 9 9 4 -4 -9 7 -7 -7 7 4 -9 9 -4
-4 -4 -4 -4 -4 -1 1 4 -3 3 3 -3 -1 4 -4 1
Table DCT2D->f
------------
Prvni hodnota je souctem tabulky f podobne jako u DCT
f[1][5] = OUT[1]*((10*cosf[1][1])/10) = -4,2 * 0,9 = -3,8 = -4
15 12 48 119
92 -32 -13 0 92 -13 13 0 92 13 13 0 92 32 -13 0
-47 -26 23 -7 -47 -11 -23 16 -47 11 -23 -16 -47 26 23 7
0 4 20 10 0 2 -20 -24 0 -2 -20 24 0 -4 20 -10
4 3 -12 -4 4 1 12 10 4 -1 12 -10 4 -3 -12 4
12 41 75 126
92 -32 -13 0 92 -13 13 0 92 13 13 0 92 32 -13 0
-19 -11 9 -3 -19 -4 -9 7 -19 4 -9 -7 -19 11 9 3
0 -4 -20 -10 0 -2 20 24 0 2 20 -24 0 4 -20 10
-9 -7 29 10 -9 -3 -29 -25 -9 3 -29 25 -9 7 29 -10
14 225 158 86
92 -32 -13 0 92 -13 13 0 92 13 13 0 92 32 -13 0
19 11 -9 3 19 4 9 -7 19 -4 9 7 19 -11 -9 -3
0 -4 -20 -10 0 -2 20 24 0 2 20 -24 0 4 -20 10
9 7 -29 -10 9 3 29 25 9 -3 29 -25 9 -7 -29 10
147 86 191 117
92 -32 -13 0 92 -13 13 0 92 13 13 0 92 32 -13 0
47 26 -23 7 47 11 23 -16 47 -11 23 16 47 -26 -23 -7
0 4 20 10 0 2 -20 -24 0 -2 -20 24 0 -4 20 -10
-4 -3 12 4 -4 -1 -12 -10 -4 1 -12 10 -4 3 12 -4
Table 10*cosf2D
---------------
10 9 7 4 10 4 -7 -9 10 -4 -7 9 10 -9 7 -4
9 9 7 4 9 4 -7 -9 9 -4 -7 9 9 -9 7 -4
7 7 5 3 7 3 -5 -7 7 -3 -5 7 7 -7 5 -3
4 4 3 1 4 1 -3 -4 4 -1 -3 4 4 -4 3 -1
10 9 7 4 10 4 -7 -9 10 -4 -7 9 10 -9 7 -4
4 4 3 1 4 1 -3 -4 4 -1 -3 4 4 -4 3 -1
-7 -7 -5 -3 -7 -3 5 7 -7 3 5 -7 -7 7 -5 3
-9 -9 -7 -4 -9 -4 7 9 -9 4 7 -9 -9 9 -7 4
10 9 7 4 10 4 -7 -9 10 -4 -7 9 10 -9 7 -4
-4 -4 -3 -1 -4 -1 3 4 -4 1 3 -4 -4 4 -3 1
-7 -7 -5 -3 -7 -3 5 7 -7 3 5 -7 -7 7 -5 3
9 9 7 4 9 4 -7 -9 9 -4 -7 9 9 -9 7 -4
10 9 7 4 10 4 -7 -9 10 -4 -7 9 10 -9 7 -4
-9 -9 -7 -4 -9 -4 7 9 -9 4 7 -9 -9 9 -7 4
7 7 5 3 7 3 -5 -7 7 -3 -5 7 7 -7 5 -3
-4 -4 -3 -1 -4 -1 3 4 -4 1 3 -4 -4 4 -3 1
DCT - Kosinova transformace
Hlavni menu