Kody morzeovky jsou vytvareny podle cetnosti znaku anglicke abecedy (huffmanuv kod). Pro elektronickou komunikaci byla morzeovka rozsirena o cisla, ruzne znaky, signaly. Doporucovane casove intervaly: carka:tecka = 3:1, mezera mezi elementy (carka/tecka) = 1, pismeny = 3, slovy = 7.
International Morse code 1844 A ·- I ·· Q --·- 1 ·---- ···/---/··· S-O-S B -··· J ·--- R ·-· 2 ··--- (signal nouze, volani o pomoc, zachrante mne) C -·-· K -·- S ··· 3 ···-- D -·· L ·-·· T - 4 ····- CH ---- (nebo pouzijte C+H) E · M -- U ··- 5 ····· F ··-· N -· V ···- 6 -···· G --· O --- W ·--- 7 --··· H ···· P ·--· X -··- 8 ---·· Y -·-- 9 ----· Z --·· 0 ----- -- --- ·-· ··· · -·-· --- -·· · M O R S E C O D E Pro zajimavost, tabulka kodu pro cetnost znaku podle Robinsona Crusoe, EN: 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 1111Top
Podminky: Mame omezeny pocet znaku zapsany vetsim poctem bitu nez je nezbytne nutne.
Priklad 1: Zmena dimenze 8-bit -> 2-bit inp = 7375 (4*8 b) -> out = 00110001 (8 b) [ komprese = 25% = 8/32 ] val val(bin) code 1 00110001 00 3 00110011 01 5 00110101 10 7 00110111 11Top
Princip: Spocitaji se pocty znaku. Seradi podle poctu vyskytu. A priradi se jim kod promenlive delky.
Priklad 1: Huffman 50:50 inp = 7375171773755757 (16*8 b) -> out = 0111010 11001100 0111010 100100 (28 b) [ komprese = 22% + Info = 28/128) inp freq val code 7 3 7 5 8x 7 0 1 7 1 7 4x 5 10 7 3 7 5 2x 1 110 5 7 5 7 2x 3 111 Huffmanuv strom kodu _Code_ 1. 0 _1_ 0, 1 (0 1) 2. 0 _1_ 1 + 0/1 (10 11) 3. 0 1 11 + 0/1 (110 111) Priklad 2: Modifikace Huffmana - rozdeleni kodu jinou metodou nez delenim 50:50 _Code__ 1. 0 __1__ 0, 1 (0 1) 2. _0_ _1_ 1 + 0/1 (10 11) 3. 0 1 0 1 10 + 0/1 (100 101), 11 + 0/1 (110 111) freq val bin code 10x 1 000 0 1x 2 001 100 2x 3 010 101 4x 4 011 110 1x 5 100 111 Priklad 3: Huffman pro retezce znaku = Shannon-Fano inp = BAAAAAADBBABBBBBAAADABCD (24 B) -> out = 311x 2x22 31xx 3xx + other -> 111101001100110110111100011000 + DADACD (30 b + 6 B) [ komprese = 42% = (30+48)/192 ] freq val code 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 opakujici retezce (bity/znaky, kombinace bitu/znaku). Priklad 4: Shannon-Fano pro binarni retezce 0110 1100 0110 0101 1 0110 1100 0110 0 0 1 1 1100 0110 0101 0110 1100 0110 0 0 0 0 (61 b) -> out = 1 2 1 3 x 1 2 1 x x x x 2 1 3 1 2 1 x x x x -> 10 110 10 111 (01) 10 110 10 (00 00 01 01) 110 10 111 10 110 10 (00 00 00 00) (50 b) [ komprese = 82% = 50/61 ] freq val code 9x x x 0+0/1 (code 0 + bit 0/1) other = 100110000 7x 0110 1 10 4x 1100 2 110 4x 0101 3 111 Retezce si urcime treba jako prvni 3 unikatni kombinace ctverice bitu nebo nejvice opakujici kombinace. V mem pripade se na vstupu hodne stridaji 0 a 1, tak je vyhodne pouzit kombinace se tridanim 0 a 1. Pozn. V podstate je to podobne tokenizovani a algoritmu Byte pair encoding.Top
(Robinson A. H.; Cherry C. 1967; 1983 patented by Hitachi)
Odkazy:
https://rosettacode.org/wiki/Run-length_encoding (RLE asi ve 100 prg. jazycich)
Princip: Nahrazuje opakujici se znaky jednim znakem a poctem opakovani.
Priklad 1: Pocet opakovani jednoho znaku (pro caste opakovani) inp = AABAAAABBBB (11) -> out = A2B1A4B4 (8) -> ABBAADBD [ komprese = 73% = 8/11 ] A-Z == 1-26 (1=A, 2=B, 3=C ...) Priklad 2: S omezim poctu opakovani na ctyri a jeho zapisu binarne (pro mene caste opakovani) inp = AABAAAABBBB (11) -> out = ABAB2144 -> ABAB 01001111 (5) [ komprese = 45% = 5/11 ] 00=1 01=2 10=3 11=4 Priklad 3: Pocty opakujicich (+num) a neopakujici znaku (-num) (pro mene caste opakovani) inp = AAACDAAAGAEFBBBBB (17) -> out = +3A -2CD +3A -4GAEF +5B (14) -> BAMCDBAQGAEFDB [ komprese = 82% = 14/17 ] A-M == 2 .. 14, N-Z == -1 .. -13 Srovnani s predchozimi priklady inp = AAACDAAAGAEFBBBBB (17) -> out = A3C1D1A3G1A1E1F1B5 (18) [priklad 1] [ komprese = 106% = 18/17 ] inp = AAACDAAAGAEFBBBBB (17) -> out = ACDAGAEFBB 10000010 00000000 1100 (10+3) [priklad 2] [ komprese = 76% = 13/17 ] Priklad 4: RLE s Huffman kody pro bity a srovnani s Huffmanem inp = 011110001110000010000 (20) inp = 011110001110000010000 (20) len1 code len0 H/L = 8/13 = 0.6 (pomer jednicky:nuly) ----------------- 1 00 0 val code (huff table) 11 01 00 00 1 111 100 000 01 01 1111 101 0000 10 001 11111 110 00000 11 000 11111+ 111 00000+ H/L = 3/6 = 0.5 ----------------- out = 0010110010011000101 (19) out = 01000000101000110111 (19) [ komprese = 95% = 19/20] [ komprese = 95% = 19/20] Priklady dalsich tabulek input code 1 00 01 01 001 100 0001 101 00001 110 00000 111 Pocty kodu, kdyz je cast kodu vyjadrena binarnim cislem o n-bitech (2 3 4 5) input code in code in code 0 1 00+00 6 01+010 13 10+0010 1 01 00+01 7 01+011 14 10+0011 2 001 00+10 8 01+100 15 10+0100 3 0001 00+11 9 01+101 16 10+0101 4 ... 01+000 10 01+110 17 10+0110 5 ... 01+001 11 01+111 18 10+0111 ... 59 11+11111 (60 codes) Pocty kodu pri stupnovani po 2 bitech (2 4 6 8) 00+00 az 00+11 (4) 01+0000 az 01+1111 (16) 10+000000 az 10+111111 (64) 11+00000000 az 11+11111111 (256, celkem 4+16+64+256 = 340 codes) Pocet kodu pri stupnovani prvociselne (2 3 5 7) 00+00 az 00+11 (4) 01+000 az 01+111 (8) 10+00000 az 10+11111 (32) 11+0000000 az 11+1111111 (128, celkem 4+8+32+128 = 172 codes)Top
Odkazy
QuadTree Coder 16x16 (javascript)
Princip:
Pokud ctverec obsahuje ruzne barvy (W i B, bila, cerna), rozdelime jej uzlem na 4 casti,
zapiseme uzel (o). Pokud obsahuje jen jednu barvu, zapiseme ji (B nebo W).
0. 1. 2.
______ ___ ___ ___ _ _
| |a b0| | |b1 | | | |c0 c1
| x | | |x | | |-o-|
| x x| |---o---| | |x| |c2 c3
|___x_x| b2| |x x|b3 |---o---|
|___|x_x| | |x x|
|___|x_x|
Step Code
1. o (ctverec a obsahuje obe barvy, vytvorime uzel o)
2. W (ctverec b0 obsahuje pouze barvu W, zapiseme W)
3. o (ctverec b1 obsahuje obe barvy, vytvorime uzel o)
4. WWBW (ctverce c0, c1, c2, c3 obsahuji po jedne barve, zapiseme je)
5. W (ctverec b2 obsahuje pouze barvu W, zapiseme W)
6. B (ctverec b3 obsahuje pouze barvu B, zapiseme B)
out = oWoWWBWWB
Priklad:
___ _ _ _______ _______________
| |_|_| | | 'x' = black (cerna)
|___|x|_| | | ' ' = white (bila)
| |x x| | | 'o' - uzel (node)
|___|x_x|_______| | 'B' - cerna oblast (black area)
|x x x x|x|_| | | 'W' - bila oblast (white area)
|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|___|
inp (16x16 = 256 b)
out = oooWoWWBWWBWBooBWBBWBoBWBWWBooWWBWWBoWWBW (o=10, W=18, B=13)
a) binary coding: o=01, W=00, B=11, delka = 10*2 + 18*2 + 13*2 = 82 b
[ komprese = 32% = 82/256 ]
b) huffman coding: o=0, W=10, B=11, delka = 10*1 + 18*2 + 13*2 = 72 b
[ komprese = 28% = 72/256 ]
c) huffman coding: W=0, B=11, o=10, delka = 10*2 + 18*1 + 13*2 = 64 b
(+ 2b define, who use one-bit code, B or W or node)
[ komprese = 26% = 66/256 ]
TopZTRATOVA METODA
Princip: Vyhledava se vzorek obrazku, ktery se vicekrat opakuje v priblizne podobe. Treba pismenko 'A' v textu na BW obrazku, ktere diky nepresnostem pri skenovani ma pixelove trosku odlisnou podobu, se nahradi jednim vzorem. ______ ______ ______ | 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 ! (tri podobne obrazky pismen AAH nahradime kodem pro pismeno A) imageA = 6 * 5 = 30 b AAH = 90 b (inp) charA = 8 b AAA = 24 b (out) [ komprese = 27% = 24/90 ]Top
Princip: Metoda vyuziva toho, ze u videa se nekolik po sobe jdoucich obrazku lisi jen velmi malo od prvniho. Ulozi se tedy prvni obrazek (key frame) a dalsich 8 po nem jako rozdily od prvniho, ktere se komprimuji odlisnou metodou nez prvni.
______ ______ ______ | 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_| ... Frame 1 Frame 2 Frame 3 ______ ______ ______ | xx | | x | | x xxx| | x x | | | | x | | xxxx | | | | | |x x| | xx| | xx| |x____x| |____xx| |____xx| ... KeyFrame Frame 2 Frame 3Top
ZTRATOVA METODA
Princip: Prvni obrazek (frame 1) rozdelite trojuhelniky. Na druhem obrazku (frame 2) muzeme nalezt tytez trojuhelniky, jen posunute, otocene nebo deformovane. Coz treba nastava pri pohybu predmetu ve snimcich videa.
TopZTRATOVA METODA
1. Shape Shapes Approximation (vyplneni obrazce tvary)
Princip: Na obrazku najdeme barevny utvar vyplneny podobnou barvou. Jeho vnitrni plochu nahradime podobou z trojuhelniku
(polynomu, ovalu, ...) vyplnenych prechodem barev. Napr. slunce, oblicej, obloha...
Nebo, muzeme cely obrazek rozdelit na ctverecky.
2. Fractal Approximation (fraktalove vyplneni vzorem, Benoit B. Mandelbrot 1975)
Princip: Kresba se popise rovnici, ktera vystihuje nekonecne spojeni jednoho
vzorku, treba v rozrustajici se spirale. Napr. posekany travnik, listi na stromech, tristici se vlna...
A nebo, rozdelime obrazek na ctverecky. Nejdrive na vetsi s gradientem barev nebo zprumerovanou hodnotou.
Ty pak delime na mensi a mensi. Velke ctverce definuji zakladni barvu a pri zjemnovani
ukladame jen rozdily barev, coz by melo byt dobre komprimovatelne treba pres Zerotree, Quadtree a pod.
Pozn. Muzeme u vetsich ctvercu aplikovat rozpousteni okraju vuci okoli pro dalsi stupen zjemneni, coz
by mohlo snizit hodnoty barev tohoto dalsiho stupne.
-------------------------------- --------------------------------
################### #################
######################### # # ## ### ########
################# ###### ###### # ##### ####
################# ### ###### # ####
###### ###### ###### ####
###### ######
-------------------------------- --------------------------------
(""-/")_.-""""-._ ("`-/")_.-'"``-._
. . ": -._ )-:-._") . . `; -._ )-;-,_`)
(/_.)" _ )"-.\ ""-" (v_,)' _ )`-.\ ``-'
_.- _..-_/ / ((." _.- _..-_/ / ((.'
((..-" ((./ ((,.-' ((,/
-------------------------------- --------------------------------
Pozn. 2D / 3D fraktalove struktury byvaji umelecky zajimave.
https://rosettacode.org/w/index.php?search=fractal
Branching fractals
Pythagoras tree Barnsley Fern (kapradi)
_| |_ _ |/_
\ / \ | |/_
\/ \/ \|//
| |_ | \|/\|///_ | |_
| / | | \|/ / \\ | |/__
|_ _ _/ |__/ \|// | /
/ \ / \ |/_///_ |/___
/ \_ / / \\\ /
/ | / / /
/ / / /
Mandelbrot Asterisks (hvezdicovy, pozn. tvar mi pripomina zelvu nebo tucnaka):
###
#####
# ###
## ###############
######################
##########################
#############################
# #### ############################
########### #############################
############ ############################
############################################
############ ############################
########### #############################
# #### ############################
#############################
##########################
######################
## ###############
# ###
#####
###
Sierpinski Carpet:
# # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # #
# # # # # #
# # # #
# # # # # #
# # # # # # # # #
# # # # # #
# # # # # # # # #
Snow flake: Hilbert curve:
_ _ _ _ _ _ _ _ ________ ________
| |_| | | |_| | | |_| | | |_| | \ \ \ \
|_ _| |_ _| |_ _| |_ _| ________ \____ \ \____ \
_| |_____| |_ _| |_____| |_ \ \ / / /
| ___ ___ | | ___ ___ | \____ \____/ / ____ ____/
|_| _| |_ |_| |_| _| |_ |_| / \ \ \
_ |_ _| _ _ |_ _| _ ____/ ________ \ \ \
| |___| |___| |_| |___| |___| | / \ \ \ /
|_ ___ ___ ___ ___ _| / ____ \____ \ \/
_| |_ |_| _| |_ |_| _| |_ \ \ \ / /
| _ | _ |_ _| _ | _ | \ \ \____/ / ____
|_| |_| | |___| |___| | |_| |_| \ / \ / /
_ _ | ___ ___ | _ _ \/ ________ \/ /
| |_| | |_| _| |_ |_| | |_| | \ \ /
|_ _| _ |_ _| _ |_ _| \____ \____/
_| |___| |___| |___| |___| |_ /
____/
Koch snowflake:
__/\__ __/\__ /\
\ / \ / / \
__/\__/ \__/\__ /_ _\ /____\
\ / \/ __/\__
/_ _\ \ /
\ / __/\__/ \__/\__
__/ \__ \ /
\ / /__ __\
/_ __ __ _\ \ /
\/ \ / \/ __/\__ __/ \__ __/\__
/_ _\ \ / \ / \ /
\/ __/\__/ \__/\__/ \__/\__/ \__/\__
Sierpinski triangle:
*
* *
* *
* * * *
* * Quadratic type 1
* * * * _
* * * * _| |_
* * * * * * * * _| |_
* * _|_ _|_
* * * * _| |_| |_| |_
* * * * _| |_
* * * * * * * * _|_ _|_
* * * * _| |_|_ _ _ _|_| |_
* * * * * * * * _| |_|_|_| |_|_|_| |_
* * * * * * * * _|_ _|_|_ _|_|_ _|_
* * * * * * * * * * * * * * * * _| |_| |_| |_| |_| |_| |_| |_
Vicsek snowflake (Quadratic Cross):
#
# # #
#
# # #
# # # # # # # # #
# # #
#
# # #
#
# # #
# # # # # # # # #
# # #
# # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #
# # #
# # # # # # # # #
# # #
#
# # #
#
# # #
# # # # # # # # #
# # #
#
# # #
#
TopOdkazy:
PackBits kody (Huffman RLE)
https://einstein.informatik.uni-oldenburg.de/rechnernetze/ccitt_t4.htm
CCITT (International Telegraph and Telephone Consultative Committee, fax group) Formaty: Packbits = Huffman RLE kody, 2-12 bitove, pro hodnoty 0-2560 Zip/Deflate = fix/dynamic Huffman (podobne PackBits) + LZW CCITT_RLE = 1D, modified Huffman RLE CCITT Group 3 fax encoding 2D = PackBits, 2D (koduje horizontalne nebo vertikalne) 6:1 (16%); 5:1 to 8:1 / 200-dpi CCITT Group 4 fax encoding 2D (T.6) = PackBits, 2D, kodovani pro oblasti s castym stridanim cerne a bile 25:1 (4%); 15:1 to 20:1 / 200-dpi/A4; 30:1 to 40:1 / 400-dpi/A4 CCITT 4 - Kodovani pro oblasti s castym stridanim cerne a bile (typicke pro pismena textu) Pravidla souboru 1. zacatek kazdeho radku = EOL kod, konec souboru = RTC kod (6x EOL) 2. kazdy radek zacina bilou, jinak je pridan PackBits kod pro delku bila=0 (00110101) ?3. kazda rada pixelu je kodovana jako 0 nebo PackBits kod ?4. ... (nepochopil jsem) EOL = 000000000001 (end of line), RTC = 6x EOL (return-to-control) Tabulka kodu pass 0001 horizontal 001 + m(a0a1) + m(a1a2) (code words of 1D compression ai aj) v(0) 1 vL(1) 010 vR(1) 011 vL(2) 00010 vR(2) 00011 vL(3) 000010 vR(3) 000011 extension 2D 000001xxx extension 1D 00000000xxx v>3 specialni kod pro vzdalenost vL/R = vzdalenost vlevo/vpravo (distance, vertical left/right) +----------------+ +----------------+ | xxxx xxx | line 0 | xxxx xxx | line 0 | xxxx xxx | line 1 z| z z z z | line 0 (z1,z2-start,z3-end,z4-start,z5-end) | xxxx xxx | line 2 | xxxx xxx | line 1 | xxxxxx xxx | line 3 z| z z z z | line 1 (z6,z7,z8,z9,z10) | xxxxx | line 4 | xxxx xxx | line 2 +----------------+ z| z z z z | line 2 (z11,z12,z13,z14,z15) z| z z z z | line 0 | xxxxxx xxx | line 3 N| N N N N | line 1 z| z z z z | line 3 (z16,z17,z18,z19,z20) N| N N N N | line 2 | xxxxx | line 4 N| L R N N | line 3 z| z z| line 4 (z21,z22,z23) N| P L R| line 4 +----------------+ +----------------+ val len code (vybrane kody z tabulky pouzite v obrazku) P pass 0001 N v(0) 1 L vL(1) 010 R vR(1) 011 1. Oznacime prechody z bile na cernou a z cernou na bile (z, changes, white / black) 2. line 0 - resi PackBits kody 3. line 1 a dalsi - urcime polohu prechodu podle prechodu nad nim (line 0 - line 1), kody pro v(0) az vL(3)/vR(3) nebo je to propust (pass) a nebo v>3 z6 je pod z1, len(z6,z1) = 0 ... N z7-z15 ... NNNN NNNNN z16 je pod z11, len(z16,z11) = 0 ... N z17 je nalevo od z12, len(z17,z12) = 1 ... L z18 je napravo od z13, len(z18,z13) = 1 ... R z19 ... N z20 ... N z21 je pod z16, len(z21,z16) = 0 ... N pod z17 ve vzdalenosti 0-3 neni zadny prechod, zpetny prechod z18 nas pak nezajima a oznacime to jako propust (pass) ... P Pokud by z22 neslo navazat na z19, musel by se pouzit kod pro v>3. z22 je pod z19 len(z22,z19) = 1 ... L z23 je pod z20 len(z23,z20) = 1 ... R CCITT4 coding line 0: 3W 4B 4W 3B 2W = 1000 011 1011 10 0111 (17 b, white/black) line 1: N NNNN = 11111 (5 b) line 2: N NNNN = 11111 (5 b) line 3: N LRNN = 101001111 (9 b) line 4: N PLR = 10001010011 (11 b) output = 17+5+5+9+11 (+line0) = 47 b input = line 0-4 = 5x16 = 80 b [ komprese = 59% = 47/80 ] Srovnani s CCITT1 coding line 0: 3W 4B 4W 3B 2W = 1000 011 1011 10 0111 (17 b) line 1: 3W 4B 4W 3B 2W = 1000 011 1011 10 0111 (17 b) line 2: 3W 4B 4W 3B 2W = 1000 011 1011 10 0111 (17 b) line 3: 2W 6B 3W 3B 2W = 0111 0010 1000 10 0111 (18 b) line 4: 11W 5B 1W = 01000 0011 00011 (14 b) output = 83 b Srovnani s QuadTree, obrazek upraven na 16x8 +---------------+---------------+ | | |x|x x|x| | | |x|x x| | | |-o-| |-o-| |-o-| | | | | |x|x x|x| | | |x|x x| | |---o---|---o---|---o---|---o---| | | |x|x x|x| | | |x|x x| | | |-o-| |-o-| |-o-| | | | |x|x|x x|x|x| | |x|x x| | |-------o-------|-------o-------| | | | |x|x|x|x|x| | | | | |-o-|-o-|-o-| | | | | | | | | | | | | |---o---|---o---| | | | | | | | | | | | | | | | | | | | | | +---------------+---------------+ ctverec vlevo : o oWoWBWBWoWBBB oBoBWBWBoBWBB WW ctverec vpravo: o oWoWBWBWoWBWB oBWBW oWoBBWWWW ooBBWWoBWWWWW 112 bitu = 17*2 + 23*2 + 30*1 + 2(first), huffman code: o=10, W=0, B=11 (W=30 B=23 o=17) [ komprese = 88% = 112/128 ]Top
Princip: Metoda cte data znak po znaku (nebo vic) a z kazde nove nalezene kombinace znaku vytvari seznam slov (slovnik). Pokud slovo najde ve slovniku, pouzije kod prirazeni ke slovu ze slovniku.
Moznosti vylepseni:
- slovnik se zapisuje do pameti usporne pomoci kodu BCS (block-based compressed-sensing sampling)
- pri zaplneni max velikosti slovniku se nesmaze cely slovnik, ale jen malo caste kombinace znaku
- kod lze zapsat jako kombinaci 0+kod256, 1+kod256... Omezit slovnik jen na 256 nebo 512 znaku.
- kod lze zapsat jako kombinaci 0+delka+kod. Delka urcije, zda je kod 1 byte, 2 byte, 4 byte...
- predvidani (viz Selhani kodu, dole v prikladu), algoritmus predvida nasledujici kod, zvoli si uspornejsi
variantu zapisu kodu a upravi podle ni slovnik.
Priklad:
Kodovani:
---------
Data = /WED/WE/WEE/WEB/WET ... 19 B
Pojmy:
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 of file)
New kod - sklada se ze znaku pro oznaceni kodu + cisla kodu (2 bajty)
Struktura streamu = End Code + Clear Code + encoded data + End Code
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
NC - cislo noveho kodu
CS - kombinace znaku prirazena k cislu kodu
BCS - uspornejsi verze slovniku pro pamet
Pozn.: Slovnik se uklada jen do pameti, protoze se pri dekomprimaci se da vytvorit.
\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
[ komprese = 89% = 17/19 ]
Postup:
-------
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
Postup:
-------
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)
.......
Ukazka selhani LZW kodovani
Data = JOEYN JOEYN JOEYN JOEY ... 19 bytu
kod 288 = JOEY (tabulka kodu pro LZW, 2 byty/kod)
kod 300 = JOEYN
...
kod 400 = JOEYNJ
kod 401 = JOEYNJO
LZW Code = ... 288 N 300 J OEYN 288 ... 12 bytu (LZW)
Nejlepsi Code = ... 288 N 300 300 288 ... 9 bytu (mLZW)
Pozn. mLZW je vylepseny LZW o detekci opakovani kodu
TopVyuziva cetnosti znaku k vypocitani cisla celkove cetnosti. Tu pak zapise do souboru.
Priklad: Pozn. Pozor, asi pri upravach neco odmazal! Kodovani: --------- Spocitam znaky a vysla mi tato tabulka prob. low - high (range probability) -------------------- 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,899999) D 0,1 <0,9 - 1> (0,9 .. 1) --- 1,0 Ve zkratce, prepocet Low-Hi podle dat, data = ABBC (vysvetleno pozdeji v principu dole) Symb Low High ------------------ A 0 0,4 B 0,16 0,28 B 0,208 0,244 C 0,2332 0,2404 Code = zvolim si cislo z intervalu <0,2332; 0,2404> -> 0,24 -> file (zapisu desetinne cislo do souboru) Princip: -------- 1 - Low = 0 2 - High= 1,0 Range_size = High - Low / cycle for all symbols 3 - | Symbol = Data(new) 4 - | range(Symbol) -> low(Symbol) .. high(Symbol) 5 - | High = Low + Range_size * high(Symbol) 6 - | Low = Low + Range_size * low(Symbol) \ 7 - Select number from range <Low; High> 1 - Low = 0 2 - High= 1,0 Range_size = High - Low = 1 - 0 = 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_size = High - Low = 0,4 - 0 = 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_size = 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_size = High - Low = 0,244 - 0208 = 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 (zvolim si cislo z intervalu <0,2332; 0,2404>) Pozn: Asi je nutne zapsat na kolik desetinnych mist kodujeme? (problem 1) Pozn: A asi je take potrebujeme zapsat tabulku pravdepodobnosti. Pozn: A pripadne i delku puvodnich dat. 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 1 - 0,94444 2 - D <0,9 - 1,0> -> D ...Top
Odkazy:
BTW Coder (javacript)
Je to prehazeni dat za pomoci serazovani a jeho vlastnosti za ucelem mozne
priznivejsi komprese.
Pozn.: Muzeme posunovat znaky nebo v pripade textu i cela slova.
Priklad 1: Data->BWT
Data 1423422 (7) [1-4] = IN
ABCDEFG AG A2G2 i = serazeno podle A
INP 1423422 12 1 2 1
rot+1 2142342 22 2 2 2
rot+2 2214234 24 2 4 3
rot+3 4221423 43 2 4 6
rot+4 3422142 32 3 2 5
rot+5 2342214 24 4 3 4
rot+6 4234221 41 4 1 7 (i G2 = A1[0])
A G AG A2G2 i = index (A2,G2)
sloupec A = inp[AGFE...B] = A1
sloupec G = inp[GFED...A] = G1
rot+1 = 423422x -> x423422
rot+2 = 42342yx -> yx42342 == rot+1(rot+1) x42342y -> yx42342
OUT = G2 + index
OUT = 2244231 + 7 (index for value=1)
Princip:
1. INP porotuji +1, +2... a vyberu jen sloupce A, G (oznacim je A1, G2).
2. Seradim sloupce [A, G] podle sloupce A (oznacim je A2, G2)
3. A najdu v G2[i] prvni hodnotu, ktera je stejna jako A1[0], to je G[i=7].
4. OUT - zapisi sloupec G2, i
Pozn.: !pozor, serazeni musi byt Stabilni! (serazovaci algoritmus nesmi menit
poradi stejnych hodnot)
Jak to jen vysvetlit lepe... Mame-li karticky A3, A5 a seradime je podle prvniho
pismene A, stabilni algoritmus vzdy vypise A3 A5, nestabilni nekdy zmeni poradi
na A5 A3. Cili, zmeni puvodni poradi, ackoliv je seradil spravne podle A a nemelo by
na tom tedy zalezet. Ale tady prave zalezi, jinak selze dekoder.
---
BWT->Data (unBWT)
BWT = 2244231 + 7[1]
sloupec A = (G serazeno) = 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 2: BWT a unBWT strucneji
DATA->BWT
1423422 -> 1423422+7
A = agfed... = 1224324
G = gfed...a = 2243241
seradim [A,G] podle A ASC (od nejmensi hodnoty po nejvetsi)
A = 1222344
G = 2244231
najdu hodnotu A[0] ve sloupci G na pozici 7 (index = 7)
first = G = a (index = 7)
BWT->DATA
2244231+7 -> 1423422
G = 2244231
(serazene G) = A
A = 1222344
index = 7, A[7]=1, G[7]=4
[7] t = 41 (AG, A[7] nastav -1, aby bylo vyrazeno z hledani)
(1) u = 12 (hledej prvni 1=A[u[2]]>0, A(pro 1) nastav -1)
(2) c = 22 (hledej prvni 2=A[v[2]]>0, A(pro 2) nastav -1)
(2) w = 24 (hledej prvni 4=A[w[2]]>0, A(pro 4) nastav -1)
(4) x = 43
(3) y = 32
(2) z = 24
XY
X = 4122432
Y = 1224324 (agfed...)
abcd... = 1423422
Tophttps://en.wikipedia.org/wiki/Byte_pair_encoding Pozn.: Postup se pouziva take jako tokenizovani pro OpenAI GPT-3 (vytvareni tabulek nejcastejsich kombinaci slov). aaabdaaabac (11) X = aa -- dvojice "aa" se opakuje nejcasteji, nahradim novym kodem "X" XabdXabac Y = ab -- nejcasteji XYdXYac Z = XY -- nejcasteji ZdZac (5)Top
Odkazy
DCT-1D 8x8 Coder (javascript)
DCT - uprava pro program
Priklad DCT-1D 16x1
Priklad DCT-2D 4x4
https://planetmath.org/discretecosinetransform
https://fr.wikipedia.org/wiki/JPEG
https://encyclopedia.thefreedictionary.com/Wavelet
https://en.wikipedia.org/wiki/Discrete_cosine_transform
https://www.iosrjournals.org/iosr-jce/papers/Vol17-issue6/Version-5/N017657985.pdf
Princip: Data jsou disktretni hodnoty (body). Propojime je krivkou, ktera se bude do nekonecna periodicky opakovat v case. Periodickou krivku pak lze spocitat integraly jako soucet mensich a mensich kosinu.
Fourrierova transformace (FT) je soucet nekonecne rady kosinusovek a sinusovek vytvoreny pro periodicky
se opakujici krivku v periodou opakovani po 2*PI.
Discrete Cosine Transformation (DCT) je FT vypocitana pro body krivky (napriklad pro 64 bodu je
dt = 2*PI/64, t = [0, 1, 2, ... 63] * dt)
Jpeg: Fast Fourrier Transformation (FFT) je DCT pro linii 64 bodu
Jpeg: Discrete Cosine Transformation (DCT) je DCT pro ctverec (matici) 8x8 bodu
Matematicke odvozeni DCT z Fourrierovi transformace (skupina trigonometricky tr.):
S(o) = integral[t=-nekonecno..+nekonecno] ( s(t) * e^(-i * o * t) ) dt
s(t) = (1/(2*pi)) * integral[o=-nekonecno..+nekonecno] ( S(o) * e^( i * o * t) ) do
o = 2 * pi * f | o = omega = angular frequency, f = frequency
f = 1/T
S(T) = integral[t=-nekonecno..+nekonecno] ( s(t) * e^(-i * 2*pi/T * t) ) dt
s(t) = (1/(2*pi)) * integral[f=-nekonecno..+nekonecno] ( S(T) * e^( i * 2*pi/T * t) ) dT
Pozn. Dale budu pro prehlednost oznacovat prevod do FT a zpet na puvodni funkci jako FT a unFT.
FT(l) = X(l) = S(T), unFT(k) = x(k) = s(t)
!!! Pozor, dal uz si nejsem uplne jisty temi upravami, zkopirovano z jineho zdroje.
FT pro diskretni body
FT(l) = suma[k=0..N-1] (yk * e^( 2pi/T * i*k*l) ) l=0,1,..N-1
unFT(k) = suma[k=0..N-1] (xk * e^( 2pi/T * i*k*l) ) k=0,1,..N-1
DFT pro krivku se sin a cos:
e^(-ix) = sin(x) - i * cos(x)
FT(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) )
Sinove slozky pro nase hodnoty (0-255) vyjdou nulove...
FT(t) = suma[k=0..N-1] (ak * cos( (2pi/T)*i*k*t) )
...a nakonec by se z toho melo dostat neco takoveho:
Pozn.: Ruzne upravy DCT: https://planetmath.org/discretecosinetransform
Discrete Cosine Transformation 1D (N=64) [AUDIO]
---------------------------------
DCT(u) = C(i) * suma[i=0..N-1] ( unDCT(i) * cos(PI/(2N)*(2i+1)*u) )
unDCT(i) = * suma[u=0..N-1] ( C(u) * DCT(u) * cos(PI/(2N)*(2u+1)*i) )
z=0: C(z) = (1/Z)^0.5
z>0: C(z) = (2/Z)^0.5
Discrete Cosine Transformation 2D (MxN=8x8) [IMAGES]
---------------------------------
DCT(u,v) = C(i)*C(j) * suma[i=0..M-1] suma[j=0..N-1] (
unDCT(i,j) * cos(PI/(2M)*(2i+1)*u) * cos(PI/(2N)*(2j+1)*v) )
unDCT(i,j) = suma[u=0..M-1] suma[v=0..N-1] ( C(u)*C(v) *
DCT(u,v) * cos(PI/(2M)*(2u+1)*i) * cos(PI/(2N)*(2v+1)*j) )
z=0: C(z) = (1/Z)^0.5
z>0: C(z) = (2/Z)^0.5
Pozn. Melo by to vychazet stejne jako zapis 2/N*c(i)*c(j); x>0:c(x)=1; x=0:c(x)=(1/2)^0.5; M=N=8
Discrete Cosine Transformation 3D (MxNxP=8x8x8) [VIDEO] --------------------------------- DCT (u, v, w) = C(i)*C(j)*C(k) * suma[i=0..M-1] suma[j=0..N-1] suma[k=0..P-1] ( unDCT(i,j,k) * cos(PI/(2M)*(2i+1)*u) * cos(PI/(2N)*(2j+1)*v) * cos(PI/(2P)*(2j+1)*w) ) unDCT (m, n, p) = suma[u=0..M-1] suma[v=0..N-1] suma[w=0..P-1] ( C(u)*C(v)*C(w) * DCT(u,v,w) * cos(PI/(2M)*(2u+1)*i) * cos(PI/(2N)*(2v+1)*j) * cos(PI/(2P)*(2w+1)*j) ) z=0: C(z) = (1/Z)^0.5 z>0: C(z) = (2/Z)^0.5
Jine transformace (vyuzivaji jine krivky) ----------------- WaveLet (DWT - diskretni WT) WLT(s,0) = 1/(s)^0.5 * f(0)*M(0)*s + suma<1..n> f(0)^(1/2)/1!*M(1)*s^2 + O( s^(2+2) ) x! = 1*2*3* ... *x Mp = integral (t^p PSI(t) dt) Hadamard (krivka: kladne trojuhelnikove spicky) X(k) = (1/N)^0.5 * suma[n=0..N-1] ( x(n)*(-1)^( suma[i=0..m-1] ( bi(n) * bi(k) ) 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 bi nevim, co znamena Hartley (krivka: sinus i kosinus, trigonometricke tr.) e^(-ix) = cos(x) - i * sin(x) cas(x) = cos(x) + sin(x) // cas=cosinus-and-sinus X(f) = 1/N * suma[t=0..N-1] ( x(t) * cas(2pi/N * f*t) ) x(t) = suma[f=0..N-1] ( X(f) * cas(2pi/N * f*t) ) (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) Cube (1994 Bijaoui) I(x,y) = cp(x,y) + suma<j=1..p> wj(x,y) wj<j=1..p> cp ... represent the transformation of I cp je velmi rozmazana verze obrazi I Pyramidal (cubic pro 2D) fi(x) = 2 * suma<k> tk * fi(2x-k) psi(x) = 2 * suma<k> hk * fi(2x-k) hk = (-1)^(1-k) * tk tK = (0.5 , 0.5) und hK = (0.5 , -0.5), hk = 1/(4*sqrt(2)) * (1+ sqrt(3), 3+sqrt(3), 3-s(3), 1-s(3) Discrete wavelets Beylkin (18) Biorthogonal nearly coiflet (BNC) Coiflet (6, 12, 18, 24, 30) Cohen-Daubechies-Feauveau (Daubechies biorthogonal, krivka: vlnky) [JPEG2000] Daubechies (2, 4, 6, 8, 10, 12, 14, 16, 18, 20, etc.) Binomial-QMF (Daubechies) Haar (krivka: kladne i zaporne trojuhelnikove spicky, nebo obdelnikove +-1) Mathieu Legendre Villasenor Symlet Continuous wavelets - Real-valued Beta Hermitian Hermitian hat Meyer Mexican hat Poisson Shannon Spline Stromberg Addison Hilbert-Hermitian wavelet Continuous wavelets - Complex-valued Complex Mexican hat fbsp Morlet Shannon Modified Morlet Mallat Hamming Walsh Walsh-Hadamard Chebyshev (polynomialní tr.) Zolotarev Mapped real Transform Karhunen-LoeveTop
Odkazy
Zerotree Coder 8x8 (javascript)
http://www.polyvalens.com/wavelets/ezw/
Modifikace: MEZW-2006?, NMEZW-2013, EZW-3D (for video frames), RMF-EZW (Modified, New Modified, requirements management packages)
Postup kodovani:
Koeficienty DCT propojime do stromu (viz ZeroTree scan order, dole). A pak urcujeme
hodnoty 'D' (dominant pass) a 'S' (subordinate pass) hodnoty.
T (treshold) je urcen jako nasobek dvou pro nejvyssi absolutni hodnotu z koeficientu.
T0 = 2 ^ floor(log2(max(abs(DCT values))))
T0 = 2 ^ floor(log2(63)) = 2 ^ floor(5.977) = 2 ^ 5 = 32 (v mem pripade)
T(n) = T(n-1) / 2
D(p/n) = Absolutni hodnota koeficientu je vetsi nebo rovna T, pak je to kod 'p' nebo 'n'.
'p', kdyz je koeficient kladny. 'n' je zaporny. A pro dalsi D-cykly je nahrazen nulou ('iz').
D(iz/t) = Absolutni hodnota koeficientu je mensi nez T, pak je to kod 'iz' nebo 't'.
Pokud maji vsichni potomci stromu abs. hodnoty koeficientu mensi nez T, pak je to
kod 't' (zero tree), jinak 'iz' (izolated zero). A kdyz nema potomky, tak je to 'z'
(zero), napr. to muze nastat pro E1, E2, E3, E4.
Pozn. 'iz' a 'z' budeme oznacovat stejne, jako 'z'.
(Nebo je mozne puvodni 'z' (pro E1, E2, E3, E4...) oznacovat jako 't' a 'iz' nemenit.)
S-1/0 = Urcuje, zda je absolutni hodnota koeficientu vetsi nebo rovna souctu hodnot
predchozich T + aktualni T/2. Cili, stred intervalu <sumaT, sumaT+T)
Pri rekontrukci (unEZW) ziskame hodnotu jako soucet jednotlivych T v kazdem cyklu,
od doby, kdy byl koeficient uznan za hodny pozornosti ('p' nebo 'n') a 1/2 posledniho T
(pokud uvazujeme mensi presnost nez nejvetsi).
Pozn. Cislo muze vyjit i vetsi nez puvodni koeficient.
63: Byl urcen jako 'p' pri T=32, 'p' znamena, ze ma znamenko +
t = [32 16 8 4 2 1]
S = [ x 1 1 1 1 1]
value = znamenko * (T0 + S1 * T1 + S2 * T2 + ... + 0.5 * Tn)
Pokud uvazujeme presnost jen D1S1-D3S3
t = [32 16 8 4]
S = [ x 1 1 1]
value = +1 * (32 + 1 * 16 + 1 * 8 + 1 * 4 + 0.5 * 4) = +62 (viz R3, dole)
Vysvetleni stromu
strom = otec a potomci
strom pro A: A + B,C,D + BE,BF,BG,BH + CI,CJ... (vsech 64 koeficientu)
strom pro B: B + BE,BF,BG,BH + E1,E2,E3,E4 + F1,F2,F3,F4 + G1,G2,G3,G4 + H1,H2,H3,H4
strom pro BE: BE + E1,E2,E3,E4
DCT data ZeroTree scan order (EZW)
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
s-step 1 21 321
val D1 S1 R1 D2 S2 R2 D3 S3 R3 ... D4S4-D6S5
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 -34 (in source is R3=-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 0 E1234-P1234
E2 13 T <32 0 .
E3 3 T <32 0 .
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
max(abs(DCT values)) = 63
T0 = 2 ^ floor(log2(max(abs(DCT values)))) = 2 ^ floor(log2(63)) = 2 ^ floor(5.977) = 32
T = array(32,16,8,4,2,1)
1. D1: (T = 32) (vypocet hodnot pro D1)
A: c= 63, abs(c)>=T (PN) & c=+63 je kladny ... P
A neni T:
B: c=-34, abs(c)>=T (PN) & c=-34 je zaporny ... N
C: c=-31, abs(c)<T (TZ), ale, jeden z potomku (J2: c=47) neni < T ... IZ (Z)
(CI,CJ,CK,CL + I1,I2,I3,I4 + J1,J2,J3,J4 + K1,K2,K3,K4 + K1,K2,K3,K4)
D: c= 23, abs(c)<T (TZ) & vsichni potomci jsou < T ... T
B neni T:
BE: c= 49, abs(c)>=T (PN) & c je kladny ... P
BF,BG,BH
c , abs(c)<T (TZ) & potomci < T ... TTT
C neni T:
CI: c= 15, abs(c)<T (TZ) & potomci < T ... T
CJ: c= 14, abs(c)<T (TZ) & potomci > T ... Z
CK,CL
c , abs(c)<T (TZ) & potomci < T ... TT
D je T. Jeho potomci se pro D1 nezapisuji.
BE neni T:
E1,E2,E3,E4
c , abs(c)<T (TZ) & potomci < T ... TTTT
CJ neni T:
J1: c= -1, abs(c)<T (TZ) & potomci < T ... T
J2: c= 47, abs(c)>=T (PN) & c je kladny ... P
J3: c= -3, abs(c)<T (TZ) & potomci < T ... T
J4: c= 2, abs(c)<T (TZ) & potomci < T ... T
Vsechny P/N budou mit pro dalsi 'D' c=0.
2. S1: (T = 32) (vypocet hodnot pro S1)
'S' se pocita pro predchozi 'S' a pak pro kazde nove 'D' (P, N).
interval [left, right):middle
old S: prevT = prevT
new S: prevT = T ... P/N: abs(c)>T
compute: left0=32=prevT , right0=48=left0+T/2, middle0=40=(left0+right0)/2
compute: left1=48=right0, right1=64=left1+T/2, middle1=56=(left1+right1)/2
new S: (prevT = T) 0=[32,48):40 1=[48,64):56
A: abs(c)(63)>=left1(48) ... 1 new_prevT=48=left1 (R1[ A]=sign*middle1=+56)
B: abs(c)(34)<left1(48) ... 0 new_prevT=32=prevT (R1[ B]=sign*middle0=-40)
BE: abs(c)(49)>=left1(48) ... 1 new_prevT=48=left1 (R1[BE]=sign*middle1=+56)
J2: abs(c)(47)<left1(48) ... 0 new_prevT=32=prevT (R1[J2]=sign*middle0=+40)
3. D2: (T = 16)
A: 0 & potomci >= T ... Z
B: 0 & potomci < T ... T (BE=0, viz -D1-)
C: c=-31, abs(c)>=T (PN) & c je zaporny ... N
D: c= 23, abs(c)>=T (PN) & c je kladny ... P
C neni T:
CI,CJ,CK,CL
c , abs(c)<T (TZ) & potomci < T ... TTTT
D neni T:
DM,DN,DO,DP
c , abs(c)<T (TZ) & potomci < T ... TTTT (J2=0, viz -D1-)
4. S2: (T = 16)
old S: (prevT = prevT) [32,40):36 [40,48):44 [48,56):52 [56,64):60
A: abs(c)(63)>=left1(56) ... 1 new_prevT=56=left1 (R1[ A]=sign*middle1=+60) [48,56):52 [56,64):60
B: abs(c)(34)<left1(40) ... 0 new_prevT=32=prevT (R1[ B]=sign*middle0=-36) [32,40):36 [40,48):44
BE: abs(c)(49)<left1(56) ... 0 new_prevT=48=prevT (R1[BE]=sign*middle0=+52) [48,56):52 [56,64):60
J2: abs(c)(47)>left1(40) ... 1 new_prevT=40=left1 (R1[J2]=sign*middle0=+44) [32,40):36 [40,48):44
new S: (prevT = T) 0=[16,24):20 1=[24,32):28
C: abs(c)(31)>=left1(24) ... 1 new_prevT=24=left1 (R1[ A]=sign*middle1=-28)
D: abs(c)(23)<left1(24) ... 0 new_prevT=16=prevT (R1[ B]=sign*middle0=+20)
D1: pnzt pttttztttttttptt (20 codes) (+ Arithmetic coding)
S1: 1010
D2: ztnp tttttttt
S2: 1001 10 (Shapiro PDF end with S2)
D3: zzzz zppnppnttnnp tpttnttttttttptttptttttttttptttttttttttt
S3: 1001 11 01111011011000
D4: zzzzzzztztznzzzzpttptpptpnptntttttptpnpppptttttptptttpnp
S4: 1101 11 11011001000001 110110100010010101100
D5: zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt
S5: 1011 11 00110100010111 110101101100100000000 110110110011000111
D6: zzzttztttztttttnnttt
( http://www.polyvalens.com/wavelets/ezw/ )
( code source1: T=0, Z=10, P=111, N=1100, end_code=1101)
( code source2: T=0, Z=10, N=110, P=1110, end_of_bit_stream=11111)
mEZW: P or N above zerotree
D1: p (-4 codes)
n z t
P ttt | t z tt |
.... | tptt
D2: z (-8 codes)
t N | P
.... | ....
D3: z (-20 codes)
z z z
z p P n | p P n t | t N N P
tptt nttt .... tptt | tptt .... tttp | .... .... ....
nmEZW: P or N above zerotree + pair/triple T
D1: p (-8 codes)
n z t
P U.. | t z T. |
.... | tpT.
D2: z (-8 codes)
t N | P
.... | ....
D3: z (-27 codes)
z z z
z p P n | p P n t | t N N P
tpT. nU.. .... tpT. | tpT. .... U..p | .... .... ....
(count: t=120 z=39 p=42 n=19; mycode: T=0 Z=10 P=110 N=111 / 0=0 1=1)
input = 64*8 = 512
D1S1-D6S5: 120*1+39*2+42*3+19*3+4+4+2+4+2+14+41+59+2 = 512 (t=120 z=39 p=42 n=19 1=69 0=61)
[ komprese = 99.8% = 511 / 512 ]
D1S1-D3S3: 60*1+ 8*2+13*3+ 7*3+4+4+2+4+2+14 = 166 (t=60 z=8 p=13 n=7 1=17 0=13)
[ komprese = 32% = 166 / 512 ] (pro mensi kvalitu)
Vysvetlivky:
D = dominant pass (P=positive, N=negative, T=ZeroTree, IZ=Izolated zero, Z=zero)
S = subordinate pass
R = zpetne dekodovana hodnota (reconstructed value)
T = treshold
c = cislo z DCT matice (coefficient)
abs(c) = absolutni hodnota c, abs(+5) = +5, abs(-5) = +5
P/N: abs(c)>=T/2; P: c>0, N: c<0
T/Z/IZ: T: abs(c)<T/2 + vsichni potomci maji abs(c)<T/2,
IZ: abs(c)<T/2 a alespon 1 potomek neslnuje podminku pro T
Z: abs(c)<T/2 (napr. E1 uz nema potomky)
(pro zjednoduseni lze IZ a Z povazovat za totez)
TopPozn.: Melo by jit o DCT a EZW pro 3d. A odnekud mam tuto tabulku kodu.
R1: 100110 10000110000010010100000 F1: R2: 11100000000000 00000 F2: 1011 R3: 1010110101011000 101111101101000100010001010001110000101000 F3: 101110 R4: 110000110000101001010100000 110111010111011100110100 010001010100010101110 F4: 10111111001111111111 R5: 01110101001011100101010111011111001001010 F5: 11111111011011111111100101111111111111111 R6: 1101100; F6: 10111110100111111111111101011111 111111111101101111001000111 R = channel code?, rate distribution?, Refinement pass?, rate region?, distortion vector?Top
Odkazy
Jpeg header decoder (javascript)
Jpeg decoder (javascript)
https://fr.wikipedia.org/wiki/JPEG
https://www.opennet.ru/docs/formats/jpeg.txt
https://publications.lib.chalmers.se/records/fulltext/198978/198978.pdf
https://en.wikipedia.org/wiki/JPEG_File_Interchange_Format
https://www.fileformat.info/format/jpeg/egff.htm
https://code.google.com/archive/p/fjcore/source/default/source (fjcore/trunk/FJCore/.svn/text-base/DecodedJpeg.cs)
http://www.cs.sfu.ca/CourseCentral/365/li/material/notes/Chap4/Chap4.2/Chap4.2.html
http://web.nchu.edu.tw/~jrliao/class/multimedia/handoutsix04.pdf
JPEG - Obvykle pouziva ztratovou DCT
Lossless JPEG (neztratovy JPEG) - Nepouziva ztratovou DCT. Metoda porovnava nekolik
sousednich pixelu k jednomu a zapise pouze rozdilne hodnoty od prvniho. Obvykle vznikne spousta
malych cisel, ktere lze dale komprimovat treba pomoci LZW.
Jbig - Multi stranky (vice obrazku za sebou, jako animovany gif, video); efektivni
pro cernobile obrazky
Progressive JPEG - Ma nekolik urovni kvality obrazku, v nizke az po vysokou. To
bylo pry vyhodne pro stahovani pres internet, ze se obrazek pri stahovani postupne doostruje a
nezustava bila plocha, nez se dostahuje.
JPEG 2000 - sdruzuje mnoho dalsich metod zpracovani obrazku
Procesy v JPEG:
- On/Off Barevna transformace
- On/Off Posun hodnot
- On/Off Rozdil hodnot od predchoziho pixelu
- On/Off Podvzorkovani (Subsampling)
- On/Off WaveLet transformace (DCT)
- On/Off Uprava kvantizacni tabulkou
- On/Off Uprava preusporadanim hodnot
- Finalni uprava a komprese - Huffman/Arithmetic/EZW ZeroTree/LZW Zip/jina
Barevna transformace a posun hodnot Barevna transformace - prevod RGB do barevneho modelu UWB (YCbCr) nebo jineho. Posun hodnot - snizi to naroky na vypocet DCT Y = 0,299 * R + 0,587 * G + 0,114 * B Cb = 0,5643 * (B - Y) Cr = 0,7133 * (R - Y) S upravou pro posun hodnot Y = 16 + ( 65.481 * R' + 128.553 * G' + 24.966 * B') Cb = 128 + (-37.797 * R' - 74.203 * G' + 112.0 * B') Cr = 128 + (112.0 * R' - 93.786 * G' - 18.214 * B') Y - je v podstate obrazek prevedeny do odstinu sede barvy (jasova slozka, lidske oko je citlive na zeleno-zlutou) Cb, Cr - jsou informace o barve Pozn.: Pri transformaci muzou vzniknou male ztraty, pokud nepocitame presne. Podvzorkovani (Subsampling) Vyuziva faktu, ze je lidske oko citlive na zeleno-zlutou, to je jasova slozka Y, a barvy uz si umi domyslet. Barevne slozky Cb Cr nemusi mit tedy hodnoty tak presne a prumeruji se 2 az 4 hodnoty. Nejcastejsi kombinace: 4:4:4 - bez podvzorkovani (1:1:1) 4:2:2 - Cb a Cr jsou horizontálně podvzorkovány na polovinu (2 po sobe jdouci pixely se spoji) 4:1:1 - Cb a Cr jsou horizontálně podvzorkovány na čtvrtinu (4 po sobe jdouci pixely se spoji) 4:2:0 - Cb a Cr (4 pixely ve ctverci se spoji) (4:4:0 - Cb a Cr - 2 pixely pod sebou se spoji) https://en.wikipedia.org/wiki/Chroma_subsampling Rozdil hodnot od predchoziho pixelu Predpoklada se, ze jsou na obrazku useky, ktere maji velmi blizke barvy (obloha, barva kuze). Rozdilem sousednich hodnot lze ziskat radu cisel nizkych hodnot. To se bude libit algoritmum pro neztratovou kompresi (LZW, Aritmeticke kodovani) nebo BWT. obloha rgb (135 206 235) R: 135 137 136 136 134 135... => 135 -2 +1 0 +2 -1... B: 235 236 236 234 237 235... => 235 -1 0 +2 -3 +2... G: 206 206 204 205 207 206... => 205 0 +2 0 -1 +1... WaveLet transformace (DCT) Viz teorie DCT nahore. A Priklady dole a na konci stranky. DCT-1D 8x8 Coder (javascript) Uprava kvantizacni tabulkou (Quantization) Prvni koeficienty DCT (hodnoty z tabulky po DCT) vytvareji hlavni vlnu krivky, ty ostatni jen mirne meni zakriveni. Takze, nejsou tak vyznamne a muzeme je zaokrouhlit delenim, idealne na nulu. (takhle, toto tvrdi literatura, v pozdejsich clancich se za vyznamne oznacuji take koeficienty horizontalni -, vertikalni | a na uhlopricce z prvniho koeficientu \) The Luminance Quantization Table q(u, v) The Chrominance Quantization Table q(u, v) Tabulka volena intuitivne Tabulka volena intuitivne 16 11 10 16 24 40 51 61 17 18 24 47 99 99 99 99 12 12 14 19 26 58 60 55 18 21 26 66 99 99 99 99 14 13 16 24 40 57 69 56 24 26 56 99 99 99 99 99 14 17 22 29 51 87 80 62 47 66 99 99 99 99 99 99 18 22 37 56 68 109 103 77 99 99 99 99 99 99 99 99 24 35 55 64 81 104 113 92 99 99 99 99 99 99 99 99 49 64 78 87 103 121 120 101 99 99 99 99 99 99 99 99 72 92 95 98 112 100 103 99 99 99 99 99 99 99 99 99 Uprava preusporadanim hodnot (Scan order) Obvykle byva prvnich 16 hodnot vyrazne vetsich nez ostatni, takze je vyhodne si tech 64 hodnot preusporadat tak, aby tech 16 bylo na zacatku a pak prevazne jen nuly. Zig-zag alternate scan Zig-zag line scan 00-01 05-06 14-15 27-28 00 04 06 20 22 36 38 52 00-01 04-05 08-09 12-13 / / / / / / / | |/ | |/ | |/ | | / / / / / / / 02 04 07 13 16 26 29 42 01 05 07 21 23 37 39 53 02-03 06-07 10-11 14-15 |/ / / / / / /| | / / / | 03 08 12 17 25 30 41 43 02 08 19 24 34 40 50 54 16-17 20-21 24-25 28-29 / / / / / / / | | | | | | | | / / / / / / / 09 11 18 24 31 40 44 53 03 09 18 25 35 41 51 55 18-19 22-23 26-27 30-31 |/ / / / / / /| / / / / / 10 19 23 32 39 45 52 54 10 17 26 30 42 46 56 60 32-33 36-37 40-41 44-45 / / / / / / / | | | | | | | | / / / / / / / 20 22 33 38 46 51 55 60 11 16 27 31 43 47 57 61 34-35 38-39 42-43 46-47 |/ / / / / / /| | | | | | | | | 21 34 37 47 50 56 59 61 12 15 28 32 44 48 58 62 48-49 52-53 56-57 60-61 / / / / / / / | | | | | | | | / / / / / / / 35-36 48-49 57-58 62-63 13-14 29 33 45 49 59 63 50-51 54-55 58-59 62-63 Morton Morton-Raster 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 Finalni uprava a komprese - Huffman/Arithmetic/ZeroTree/LZW/jina Po skenovani si zvolime metodu komprese. Huffman - Huffman Coding (viz nahore). LZW - Zip Coding (viz nahore). Arithmetic - Arithmetic Coding (viz nahore). EZW - Embedded Zerotree Wavelet (viz nahore) + Successive-approximation quantization (SAQ) nebo nmZW a nebo Arithmetic Coding Jine metody kodovani: SPIHT (Set Partitioning in Hierarchical Trees) Coding SPIHT-3D (for video frames) MSPIHT (modified SPIHT) SPECK Coder (Set Partitioned Embedded Block Coding) BCWT (backward coding of wavelet trees) EBCOT (Embedded Block Coding with Optimized Truncation) WDR (Wavelet Difference Reduction) ASWDR (Adaptively Scanned Wavelet Difference Reduction SFQ (Space - Frequency Quantization) EPWIC (Embedded Predictive Wavelet Image Coding) CREW (Compression with Reversible Embedded Wavelet) Coding SR (Stack-Run) GW (Geometric Wavelet Coding) STW (spatial orientation tree Wavelet) LVL_MMC (Subband thresholding of coefficients and Huffman encoding, Wavelet level metropolis Monte Carlo) GBL_MMC_H (Global thresholding of coefficients and Huffman encoding) GBL_MMC_F (Global thresholding of coefficients and fixed encoding) AVDZ (adaptive variable degree-k zero-trees) STCHE GTCFE GTCHE (ground truth color hints extracted) PCSM (Progressive Coding Significant Methods) ECDQ (entropy-coded dithered quantizer) MR-ECDQ (multi-resolution ECDQ)Top
Odkazy:
Biting Coder (javascript)
Priklad: Priklad srovnani chyb pro kodovani DCT ruznymi i vlastnimi metodami
DCT data DCT * Q Q table (quantization)
63 -34 49 10 7 13 -12 7 3 -3 4 0 0 0 0 0 16 11 10 16 24 40 51 61
-31 23 14 -13 3 4 6 -1 -2 1 1 0 0 0 0 0 12 12 14 19 26 58 60 55
15 14 3 -12 5 -7 3 9 1 1 0 0 0 0 0 0 14 13 16 24 40 57 69 56
-9 -7 -14 8 4 -2 3 2 0 0 0 0 0 0 0 0 14 17 22 29 51 87 80 62
-5 9 -1 47 4 6 -2 2 0 0 0 0 0 0 0 0 18 22 37 56 68 109 103 77
3 0 -3 2 3 -2 0 4 0 0 0 0 0 0 0 0 24 35 55 64 81 104 113 92
2 -3 6 -4 3 6 3 6 0 0 0 0 0 0 0 0 49 64 78 87 103 121 120 101
5 11 5 6 0 3 -4 4 0 0 0 0 0 0 0 0 72 92 95 98 112 100 103 99
Zerotree: 63,-34,-31,23,49,10,14,-13,15,14,-9,-7,3,-12,-14,8,7,13,3,4,-12,7,6,-1,5,-7,4,-2,
3,9,3,2,-5,9,3,0,-1,47,-3,2,2,-3,5,11,6,-4,5,6,4,6,3,-2,-2,2,0,4,3,6,0,3,3,6,-4,4
Zig-zag : 63,-34,-31,15,23,49,10,14,14,-9,-5,-7,3,-13,7,13,3,-12,-14,9,3,2,0,-1,8,5,4,-12,7,
6,-7,4,47,-3,-3,5,11,6,2,4,-2,3,-1,9,3,6,3,-4,5,6,3,-2,-2,2,2,0,6,0,3,3,4,6,-4,4
1. Chyba vznikla kvantizaci DCT a mensi presnosti u EZW a myBiting (musite srovnavat s puvodni DCT)
Rekonstrukce DCT pro kvantizaci Rekontrukce DCT pro EZW, 3 vrtsvy Rekontrukce pro myBiting, 3 vrtsvy
48 -33 40 0 0 0 0 0 62 -34 50 10 0 14 -14 0 60 -36 52 12 0 12 -12 0
-24 12 14 0 0 0 0 0 -30 22 14 -14 0 0 0 0 -28 20 12 -12 0 0 0 0
14 13 0 0 0 0 0 0 14 14 0 -14 0 0 0 10 12 12 0 -12 0 0 0 12
0 0 0 0 0 0 0 0 -10 0 -14 10 0 0 0 0 -12 0 -12 10 0 0 0 0
0 0 0 0 0 0 0 0 0 10 0 46 0 0 0 0 0 12 0 44 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 12 0 0 0 0 0 0
2. Uspora kodu pri pouziti ruzneho skenovani (hodnot pro DCT * Q)
Realne Jpegy mivaji kompresi 10%-15% bez viditelne ztraty kvality.
Skenovanim dostavame rekneme 11 kodu, to je komprese 17% = 11/64, bez dalsiho kodovani.
Raster : 3, -3, 4, 0, 0, 0, 0, 0,-2, 1, 1, 0, 0, 0, 0, 0, 1, 1, eob (eob = zero-to-end)
Zig-zag : 3, -3, -2, 1, 1, 4, 0, 1, 1, eob
Zig-zag line : 3, -3, -2, 1, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, eob
Morton : 3, -3, -2, 1, 4, 0, 1, 0, 1, 1, eob
Zerotree : 3, -3, -2, 1, 4, 0, 1, 0, 1, 1, eob
alternate : 3, -2, 1, 0,-3, 1, 4, 1, 1, eob
Morton-raster: 3, -3, -2, 1, 4, 0, 1, 0, 1, 1, eob
Raster + huff: 3, -3, 4,-2, 1, 1, 1, 1 + 10101011 10101011 10100000
0+value code (repeat zero + value)
1 10
01 01
001 0011
0001 0010
00001 0001
00000 11 (nebo by slo pouzit 5-zero = 110, 10-zero = 111)
eob 0000
3. DCT s vyssi presnosti ruznymi metodami
EZW DS1-DS3:
pnzt pttttztttttttptt 1010 ztnp tttttttt 100110
zzzz zppnppnttnnp tpttnttttttttptttptttttttttptttttttttttt 10011101111011011000
206 = (60+8+13+7)*2 + (17+13)*1 (t=60 z=8 p=13 n=7 1=17 0=13)
[ komprese = 40% = 206 / 512
EZW DS1-DS3 + huff (T=0, Z=10, P=111, N=1100, eob=1101):
pnzt pttttztttttttpE 1010 ztnpE 100110
zzzz zppnppnttnnp tpttnttttttttptttptttttttttpE 10011101111011011000
163 = 38*1 + 8*2 + 13*3 + 7*4 + 3*4 + (17+13)*1 (t=38 z=8 p=13 n=7 1=17 0=13 E=3 1=17 0=13)
[ komprese = 32% = 163 / 512 ]
nmEZW DS1-DS3: (P=Pt, N=Nt, Z=Zt, T=TT, U=TTT)
pnzt PUtzTtpT 1010 ztNP 100110
zzzz zpPnpPnttNNP tpTnUtpTtpTUp 10011101111011011000
165 = (9+8+8+5+5+4+3+3)*3 + (17+13)*1 (1=17 0=13 t=9 p=8 z=8 P=5 T=5 n=4 U=3 N=3)
[ komprese = 32% = 165 / 512 ]
myBiting (zig-zag, prvni bity, rle-huff, T>=32,16,8 (viz dalsi priklad)
[ komprese = 22% = 112 / 512 ]
myBiting - Proc tak slozite pres EZW? Muzou rovnou vypsat prvni bity a pak to zakodovat treba RLE-huff.
DCT data
63 -34 49 10 7 13 -12 7 1 10
-31 23 14 -13 3 4 6 -1 01 01
15 14 3 -12 5 -7 3 9 001 0011
-9 -7 -14 8 4 -2 3 2 0001 0010
-5 9 -1 47 4 6 -2 2 00001 0001
3 0 -3 2 3 -2 0 4 5-zero 110
2 -3 6 -4 3 6 3 6 10-zero 111
5 11 5 6 0 3 -4 4 eob 0000 (eob = zero-to-end)
Zig-zag : 63,-34,-31,15, 23,49,10,14, 14,-9,-5,-7, 3,-13,7,13, 3,-12,-14,9, 3,2,0,-1, 8,5,4,-12,
7,6,-7,4, 47,-3,-3,5, 11,6,2,4, -2,3,-1,9, 3,6,3,-4, 5,6,3,-2, -2,2,2,0, 6,0,3,3, 4,6,-4,4
c>=0 : 10011111 10001011 10011110 11101101 10011111 01011110 11100111 11111101 (64) znamenko (0 false, 1 true)
D>=32: 11000100 00000000 00000000 00000000 10000000 00000000 00000000 00000000 (abs(c)-S > T; S=0, new_S=suma(bit*T))
D>=16: 10101100 00000000 00000000 00000000 00000000 00000000 00000000 00000000
D>=8 : 10110011 11000101 01110000 10010000 10001000 00010000 00000000 00000000
D>=4 : 10111001 10110111 01100000 01111111 10010101 00000101 11000000 10001111 (64)
D>=2 : 11111011 10011010 10101100 00001110 11101110 11001110 01111110 10110100 (64)
D>=1 : 10111100 01111111 10011001 01001010 11111000 01111010 10100000 00110000 (64)
Rekneme, ze zakodujeme jen D>=32 D>=16 D>=8
(kdyz by to vychazelo vic nez 64, tak nastavime stop-byte na T a dale uz budeme
kopirovat jen 64 bitu, nebudeme je huffmanovat)
c>=0 : 10011111100100110111 (20) znamenko (0 false, 1 true)
D>=32: 10100010111111110010000 (23)
D>=16: 100101100000 (12)
D>=8 : 1001100011101010001001011010000100110001001011010 (49)
input = 64*8 = 512
output = 8 (stop-bite=0) + 20 (sign) + 23 + 12 + 49 = 112
[ komprese = 22% = 112 / 512 ]
value code
non-zero 1+value
8xzero 0
all-non-zero 1+block
one-non-zero 0+block
c>=0 : 10011111100100110111 (20) znamenko (0 false, 1 true)
D>=32: 0 111000100 0 0 0 110000000 0 0 0 (25)
D>=16: 0 110101100 0 0 0 0 0 0 0 (17)
D>=8 : 0 110110011 111000101 101110000 110010000 110001000 100010000 0 0 (57)
output = 20 (sign) + 25 + 17 + 57 = 119
[ komprese = 23% = 119 / 512 ]
Hlavne, ten algoritmus je jednodussi v tom, ze nemusime testovat pokazde podstrom jako v EZW.
Dalo by se to rozsirit o posledni S3 bity jako u EZW a pak by meli byt rekontrukce stejne.
TopPozn. Berte to jen jako zajimave myslenky. Vic v tom nehledejte. Shannon-Fano pro binarni retezce viz Huffman Coding & Shannon-Fano Coding, Priklad 4: Shannon-Fano pro binarni retezce XOR transformace Xor ma na vystupu jednicku, kdyz je pocet jednicek vstupu lichy. Take ma sikovnou vlastnost, ze jeden vstupu nebo vystup lze dopocitat xorovanim ostatnich. A pro kompresi ma peknou vlastnost, ze bud zvysi nebo snizi pocet nul. Experimentoval jsem i s tim, ze jsem do xor zahrnoval predchozi vystup, OUT(n) = xor( OUT(n-1), IN(n) ). Ukazky pravdivostnich tabulek pro XOR abcd|e e = a xor b xor c xor d 0000|0 0001|1 abc|d d = a xor b xor c 0010|1 000|0 0011|0 001|1 0100|1 010|1 0101|0 011|0 0110|0 100|1 0111|1 101|0 1000|1 110|0 1001|0 111|1 1010|0 1011|1 ab|c c = a xor b 1100|0 00|0 b = c xor a 1101|1 01|1 a = c xor b 1110|1 10|1 1111|0 11|0 https://web.stanford.edu/class/cs103/tools/truth-table-tool/ Sort komprese Princip: Mate mix 256 znaku. Seradite je. A zapisete na vystup typ operace, mensi nebo rovna / vetsi. Podminky: Idealni by bylo, teda, kdyby slo o blok 256 znaku a kazdy znak by byl jen 1x. V opacnem pripade je nutne zapsat pocet opakovani znaku. ABDCBBAADDCDDABD AAAABBBBCCDDDDDD seradim (blok = 16, znaky = 4, 2 bity/znak) (16 * 2 = 32 bitu) 0000111100111111 + 1111 pocet opakovani - binarne (16 + 4 bity) Stridam 1 a 0 + 1 bit za kazdy znak (aby bylo mozne vyjadrit i nulovy pocet opakovani. K tomu jeste bity z porovnavacich operaci serazovaciho algoritmu (0 vetsi nez, 1 mensi nebo rovno). Nejmensi pocet operaci serazovaciho algoritmu se ridi vztahem On = n * (ln(n) / ln(2) - 1) + 1, kde n je pocet prvku. n = 16: On = 16 * (2.77 / 0.69 - 1) + 1 = 16 * (4-1) + 1 = 49 bitu Celkem = 16 + 4 + 49 = 69 bitu [ komprese = 216% = 69 / 32 ] (nevyhodne!) AAAABBBBCCDDDDDD seradim (blok = 16, znaky = 256, 8 bitu/znak) (16 * 8 = 128 bitu) 0000111100111111 + 1111 + 000... (256-4) * 1 za kazdy znak, ktery tam neni (16 + 256 bitu) n = 16: On = 49 bitu Celkem = 16 + 256 + 49 = 321 bitu [ komprese = 205% = 321 / 128 ] (nevyhodne!) AAAAAAAABBBBBBBBCCCCDDDDDDDDDDDD (32 * 8 = 256 bitu) 00000000111111110000111111111111 + 256 * 1 (32 + 256 bitu) n = 32: On = 32 * (5-1) + 1 = 128 + 1 bitu Celkem = 32 + 256 + 128 + 1 = 417 bitu [ komprese = 163% = 417 / 256 ] (nevyhodne!) AAAAAAAABBBBBBBBCCCCDDDDDDDDDDDD (32*8 = 256 bitu) 00000000111111110000 + 256 * 1 (20 + 256 bitu) Opakovani posledniho prvku neni treba zapisovat, pokud vime, ze je jich 32. n = 32: On = 32 * (5-1) + 1 = 128 + 1 bitu Celkem = 20 + 256 + 128 + 1 = 417 bitu [ komprese = 158% = 405 / 256 ] (nevyhodne!) DABC (4*2 bity) ABCD serazeno Neni treba zapisovat pocet opakovani, protoze se vsechny opakuji 1x (to jsme nejakym algoritmem predem nastavili) n = 4: On = 4 * (2-1) + 1 = 5 bitu [ komprese = 62% = 5 / 8 ] (Ha! A ted to zacina byt zajimave, ze?) ! Ale, musite zapsat take delku mapy serazovacich operaci, pokud pouzijete serazovaci algoritmus, kde delka kolisa. Delka v tomto pripade spolkne 3 bity. FDAEBCHG (8*3 bity) ABCDEFGH serazeno 0 bitu n = 8: On = 8 * (3-1) + 1 = 17 bitu (+5 bitu v pripade kolisaveho serazovaciho algoritmu) [ komprese = 71% = 17 / 24 ] Eliminace a zmena dimenze - postupne snizovani poctu bitu Princip: Mate 256 znaku, kazdy jen 1x. kdyz zapiseme 50% bloku, tak klesne pocet unikatnich znaku na polovinu a je tedy mozne zmenit dimenzi z 8 na 7 bitu, ze 7 na 6, atd. Podminky: Idealni by bylo, teda, kdyby slo o blok 256 znaku a kazdy znak by byl jen 1x. V opacnem pripade je nutne zapsat pocet opakovani znaku. A navic, misto 50% je treba zapsat vetsi pocet znaku v 8-bitech. Podminky: Mame nahodile promichane znaky bez opakovani. Delka bloku dat je 256, kazdy znak se vyskytuje jen 1x. 2048 bitu = 256*8 (puvodni 256-blok dat) 1793 bitu = 128*8 + 64*7 + 32*6 + 16*5 + 8*4 + 4*3 + 2*2 + 1*1 (delka pri snizovani poctu bitu) [ komprese = 87.5% = 1793 / 2048 ] Prakticky je dost problem takovou skupinu dat nalezt. Komprimovany zip soubor obsahuje 2-3 opakovani a stav pro eliminaci nastava az treba 7 znaku od konce 256-bloku. [ komprese = 2041 / 2048 = 99,7%; 2041 = (256-7)*8 + 7*7 ] Vyhodou je rychlost, ze vsechny ostatni znaky lze proste jen zkopirovat. Slo by vybrat jen useky, kde se znaky neopakuji. Mapa poctu unikatnich znaku vsak zabira 256 bitu, mapa s opakovanim 512 bitu! Slo by vybirat i jen pro 4-bitove useky. Huffman jako transformace pro komprimovany soubor 11 01 00 10 (8 b) 00 1 Huffman pro 2 bity 01 01 10 001 11 000 Spekulace: Pokud je vstupni soubor komprimovany, treba zip soubor, bity jsou rovnomerne rozmistene. Takze, pri kodovani 8 bitu bychom meli dostat 9. Coz je spis anti komprese. Ale, muj cil je jiny. Ulozim si prvni bity kodu oddelene s docilim toho, ze prvni skupina bude mit pomer nul ku jednickam, v idealnim pripade 3:1, druha 2:1, treti 1:1. A s tim uz se by mozna dalo neco podniknout. 11 01 00 10 (8 b) 000 01 1 001 (9 b) normalne by se to zakodovalo takto 0010 010 01 (9 b) ale tady zapisi prvni bity zvlast (prvni skupina obsahuje pomer nuly:jednickam 3:1, druha 2:1, treti 1:1) (abc ab a abc -> aaaa bbb cc) Huffman zrychleni komprese 00 1 Huffman pro 2 bity 01 01 10 001 11 000 Kdyz mame pred kodovanim pocet bitu 8, nahodnych hodnot 0/1. Po kodovani jich muzeme mit 4 az 12. A, kdyz budeme cist data po 16 bitech, ziskame na vystupu 8 bitu + (0 az 16) dalsich bitu. Muzeme si vytvorit tabulku, ktera koduje 16 bitu na 8 bitu ihned. A jinou, ktera koduje ty ostatni pomalejsim zpusobem. Odhad: 8 bitu se zapise rychlosti 300% a ostatnich bude treba 12 pri rychlosti 100%. (8 * 300 + 12 * 100) / 20 = (36 / 20) * 100 = neco kolem 180% (pro rozdil rychlosti 300%) (8 * 500 + 12 * 100) / 20 = (52 / 20) * 100 = neco kolem 260% (pro rozdil rychlosti 500%) To uz stoji za uvahu mit temer 2x rychlejsi huffmanuv koder, ze? Podobny princip by sel mozna pouzit i pro aritmeticke kodovani. Omezit blok na malou delku nebo jen par bitu. Transformace eliminaci (neni to uplne nejvystiznejsi nazev) Spekulace: Pokud se nam neopakuji nebo jen malo, pak muze byt vyhodne, zmenit jejich kod na posledni. A ostatnim kod snizit. Tim by slo docilit to, ze se zvysi pocet opakovani nizkych nebo vysokych kodu AFGEHCDB (A=1, B=2, C=3...) 'A' zapiseme na vystup a prepocitame tabulku (A=256, B=0, c=1, D=2...) Nebo, naopak, muzeme mu dat nejnizsi kod. AFGEHCDB (A=1, B=2, C=3...) 'A' zapiseme na vystup jako 'A' a prepocitame tabulku (A=1, B=2, C=3...) 'F' zapiseme na vystup jako 'F' a prepocitame tabulku (F=1, A=2, B=3, C=4...) Pokud se F znovu objev, zapise jej nyni jako 1. Nebo, muzeme proste pouzit swap s hodnotou n, n-1... AFGEHCDB (A=1, B=2, C=3...) 'A' zapiseme na vystup jako 'A' (A=256, 256=A; vymenim A s poslednim znakem) 'F' zapiseme na vystup jako 'F' (F=255, 255=F; vymenim F s predposlednim znakem) Cili, pokud se znaky nebudou vicekrat opakovat, tak by nekolik znaku s vysokym kodem mohlo ziskat kod nizky. Coz muze byt vyhodne pro dalsi kompresni algoritmus. Nebo muzeme pri opakovani znaku ho dat na zacatek tabulky. Vsechny znovu opakujici znaky tedy ziskaji nizke kody, napriklad 1-10. Coz muze byt opet vyhodne pro dalsi kompresi. Konkretne, tohle by fungovalo na ZIP soubory. Analyza textu text The Life and Adventures of Robinson Crusoe (1808), by Daniel Defoe (https://www.gutenberg.org/cache/epub/12623/pg12623.txt) program Text analyser (https://www.online-utility.org/text/analyzer.jsp) Count Letter Frequency (https://www.browserling.com/tools/letter-frequency) Letter Frequency TAOINHSRDLUWMFCYGPBEVKXJQZ Number of characters (including spaces znaku): 1261407 Number of characters (without spaces; znaku): 961467 Number of words (slov): 239578 Number of unique words (unikatnich slov): 8948 Number of sentences (vet): 4688 Number of syllables (slabik): 324135 Nejcastejsi dvojice slov (top 10) of the 1560, i had 1055, in the 1047, to the 838, i was 705, it was 675, that i 541, as i 538, to be 532, and the 498 Nejcastejsi slova (top 20) the 11602 , and 9532, to 8318, i 7471, of 6883, a 4368, in 3893, that 3813, was 3484, it 3313, had 2858, my 2855, as 2804, they 2711, for 2504, them 2323, with 2232, but 2201, he 2179, not 2010 Znaky textu podle cetnosti: EN26 ETAOINHSRDLMWUFCYGBPVKXJQZ (zdroj: kniha Robinson Crusoe, 624.000 znaku) EN26 TAOINSHRDLCUMWFGEYPBVKJXQZ (zdroj: algoritmy.net) EN26 TAOINSHRDLCUMWFGYEPBVKJXQZ (zdroj: dcode.fr) EN26 ETAOINHSRDLUFWCYMGPBKVJXQZ (zdroj: kniha Creatures that once were men, 140.000 znaku) CZ26 EOAINTSRVULKCDPMZYHJBFGXWQ (zdroj: algoritmy.net) CZ26 EAOILSNTRMUKVJDPZCYHBGFXWQ (spojene povidky, odstranena diakritika, 900.000 znaku)Top
Terminating Code word
l White Black l White Black
------------------------------------------------------------
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
l White Black l White Black
------------------------------------------------------------
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
l = lenght, pocet hodnot stejne barvy
color = Black, lenght = 960: code = 0000001110011 (black length=960)
color = Black, lenght = 1984: code = 0000110111 (black=0) + 000000010010 (any color length=1984)
Top
Discrete Cosine Transformation (DCT) 1D (N 64, Fast Fourrier Transformation - FFT)
DCT(u) = C(i) * suma[i=0..N-1] ( unDCT(i) * cos(PI/(2N)*(2i+1)*u) )
unDCT(i) = * suma[u=0..N-1] ( C(u) * DCT(u) * cos(PI/(2N)*(2u+1)*i) )
z=0: C(z) = (1/Z)^0.5
z>0: C(z) = (2/Z)^0.5
--- rozdeleni operaci (pro N = 64) ---
DCT(u) = constant1(i) * suma[i=0..63] unDCT(i) * cosinus1(i,u)
unDCT(i) = suma[u=0..63] DCT(u) * cosinus3(u,i)
z=0: C(z) = (1/N)^0.5 = 0.125
z>0: C(z) = (2/N)^0.5 = 0.177
constant1(i) = C(i)
constant2(u) = C(u)
cosinus1(i,u) = cos(PI/128*(2i+1)*u)
cosinus2(u,i) = cos(PI/128*(2u+1)*i)
cosinus3(u,i) = constant2(u) * cosinus2(u,i)
Discrete Cosine Transformation (DCT) 2D (MxN 8x8)
DCT(u,v) = C(i)*C(j) * suma[i=0..M-1] suma[j=0..N-1]
( unDCT(i,j) * cos(PI/(2M)*(2i+1)*u) * cos(PI/(2N)*(2j+1)*v) )
unDCT(i,j) = suma[u=0..M-1] suma[v=0..N-1]
( C(u)*C(v) * DCT(u,v) * cos(PI/(2M)*(2u+1)*i) * cos(PI/(2N)*(2v+1)*j) )
z=0: C(z) = (1/Z)^0.5
z>0: C(z) = (2/Z)^0.5
--- rozdeleni operaci (pro M = N = 8) ---
DCT(u,v) = constant1(i,j) * suma[i,j=0..7] unDCT(i,j) * cosinus1(i,j,u,v)
unDCT(i,j) = suma[u,v=0..7] DCT(u,v) * cosinus3(u,v,i,j)
i=0, j=0 : C(i) * C(j) = (1/M)^0.5 * (1/N)^0.5 = 0.125
i=0, j>0 : C(i) * C(j) = (1/M)^0.5 * (2/N)^0.5 = 0.177
i>0, j=0 : C(i) * C(j) = (2/M)^0.5 * (1/N)^0.5 = 0.177
i>0, j>0 : C(i) * C(j) = (2/M)^0.5 * (2/N)^0.5 = 0.25
constant1(i,j) = C(i)*C(j)
constant2(u,v) = C(u)*C(v)
cosinus1(u,v,i,j) = cos(PI/16*(2i+1)*u) * cos(PI/16*(2j+1)*v)
cosinus2(i,j,u,v) = cos(PI/16*(2u+1)*i) * cos(PI/16*(2v+1)*j)
cosinus3(u,v,i,j) = constant2(u,v) * cosinus2(i,j,u,v)
TopPozn. Pro zobrazeni na web jsem cisla zaokrouhloval, ale pocital jsem je ve vysoke presnosti. Pozn. Je to jen na ukazku, jak to zhruba vychazi. 1. Input1 (Image data) | 1. Input2 (Output1) 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 | 2. DCT1 | 2. DCT2 = Input2 * Q 373.3 -164.7 -27.3 20.3 | 368 -165 -30 16 -10.5 -72.5 -1.6 -2.1 | -12 -72 0 0 -53.8 68.5 70.1 -6.1 | -56 65 64 0 -58.7 83.6 -69.8 -62.5 | -56 85 -66 -58 | 3. Output1 = DCT1 / Q | 3. Output2 = unDCT2 (Image data) 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 ---------------------------------------------------------------- Rozdily Input-Output2 4 5 -2 7 -3 -4 1 5 -3 4 3 0 4 2 -2 3 ---------------------------------------------------------------- constant1 (N=16) = constant2 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 z=0: C(z) = (1/Z)^0.5 = 0.25 z>0: C(z) = (2/Z)^0.5 = 0.354 Q (nahodne zvolena quantizacni tabulka, protoze pro 16x1 neznam) 16 11 10 16 12 12 14 19 14 13 16 24 14 17 22 29 table1 (dct without constant) 14 = table1[0][ 0] = Input1[ 0] * cos[0][ 0] = 14 * 1.0 = 14 8 = table1[0][ 4] = Input1[ 4] * cos[0][ 4] = 8 * 1.0 = 8 -114 = table1[1][12] = Input1[12] * cos[1][12] = 147 * -0.773 = -114 (cos[2][13]=-0.8, presnejsi -0.773) -466 = suma[1] = suma(table[1][0..15]) = suma (14,16,43,94, 5,26,19,12, -2,-64,-77,-56, -114,-78,-187,-120) 373.3 = DCT[0] = suma[0] * constant1[0] = 1493 * 0.250 = 373.3 -164.7 = DCT[1] = suma[1] * constant1[1] = -466 * 0.354 = -164.7 1493 -466 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 10*cos (cosDCT, nasobeno 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 table2 -4 = table2[3][4] = DCT2[4] * constant2[4] * cos[3][4] = -12 * 0.354 * -0.924 = 4 (3.92; cos[3][4]=-0.9, presnejsi -0.924) 115 = Output2[3] = suma(table2[3][0..15]) = suma (92,-45,-2,-3, 4,24,0,0, -14,23,19,0, 8,-27,23,13) 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 10*cos (cosUnDCT, nasobeno 10x) 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 -1Top
Pozn. Pro zobrazeni na web jsem cisla zaokrouhloval, ale pocital jsem je ve vysoke presnosti.
Pozn. Je to jen na ukazku, jak to zhruba vychazi.
1. Input1 (Image data) | 1. Input2 (Output1)
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
|
2. DCT1 | 2. DCT2 = Input2 * Q
373.3 -99.3 -53.8 -5.2 | 368 -99 -50 0
-145.9 -56.4 65.9 -47.0 | -144 -60 70 -38
3.2 8.1 81.3 73.8 | 0 13 80 72
29.9 12.0 -80.6 -44.1 | 28 17 -88 -58
|
3. Output1 = DCT1 / Q | 3. Output2 = unDCT2 (Image data)
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
----------------------------------------------------------------
Rozdily Input-Output2
-1 5 1 3
-4 15 -8 -5
4 -6 5 2
0 2 4 4
----------------------------------------------------------------
constant1 (M=N=4)
j\i 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
z=0: C(z) = (1/Z)^0.5 = 0.25
z>0: C(z) = (2/Z)^0.5 = 0.354
i=0, j=0 : C(i) * C(j) = (1/M)^0.5 * (1/N)^0.5 = 0.25
i=0, j>0 : C(i) * C(j) = (1/M)^0.5 * (2/N)^0.5 = 0.354
i>0, j=0 : C(i) * C(j) = (2/M)^0.5 * (1/N)^0.5 = 0.354
i>0, j>0 : C(i) * C(j) = (2/M)^0.5 * (2/N)^0.5 = 0.5
Q (nahodne zvolena quantizacni tabulka, protoze pro 4x4 neznam)
16 11 10 16
12 12 14 19
14 13 16 24
14 17 22 29
-----------------------------------------
table (dct without constant)
14 = table[0][ 0] = Input1[ 0] * cos[0][ 0] = 14 * 1.0 = 14
8 = table[0][ 4] = Input1[ 4] * cos[0][ 4] = 8 * 1.0 = 8
136 = table[1][12] = Input1[12] * cos[1][12] = 147 * 0.924 = 136 (135.828; cos[1][12]=0.9, presnejsi 0.924)
-281 = suma[1] = suma(table[1][0..15]) = suma (13,7,-19,-113, 7,21,-26,-112, 17,84,-62,-81, 136,34,-75,-112)
-99.3 = dct[1] = suma[1] * constant1[1] = -281 * 0.3535539 = -99.3 (constant1[1]=0.354, presnejsi 0.3535539)
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
10*cos (cosDCT, nasobeno 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
table2
-47 = table2[3][4] = DCT2[4] * constant2[4] * cos[3][4] = -144 * 0.354 * 0.924 = -47 (47.1; cos[3][4]=0.9, presnejsi 0.924)
119 = Output2[3] = suma(table2[3][0..15]) = suma (92,32,-13,0, -47,26,23,7, 0,-4,20,-10, 4,-3,-12,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
10*cos (cosUnDCT, nasobeno 10x)
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
TopMuze byt vyhodne - Algoritmus pouzit na bity vstupu, kombinace bitu, znaky, kombinace znaku, slova, slovo + mezera. - Pro novy kod pouzit kombinaci huffman + bin kod pro cislo (poradi kombinace). - Pouzit organizovani do bloku stejne velikosti. A zaznamenat delku bloku po zakodovani pro moznost soucasne dekodovani na vice procesorech (treba pro huffmanuv kod, kde je delka po zakodovani promenliva). - U Textu pouzit pevnou tabulku kodu stejnou pro stejny jazyk a nezapisovat ji do vystupu, jen cislo tabulky. - U textu se da udela slovnik se slov nebo nejcastejsich kombinaci 2-3 znaku. - U obrazku provest rozdil bytu s predchozim bytem a PackBits kody. - U obrazku provest transformaci z RGB na YCbCr barevny model. - U videa provest rozdil bytu a rozdil s predchozim obrazkem.Top
| Data_compression_methods (wikipedia.org) | |||||||
|---|---|---|---|---|---|---|---|
| Lossless |
|
||||||
| Lossy |
|
||||||
| Audio |
|
||||||
| Image |
|
||||||
| Video |
|
||||||
| Theory | |||||||