Compress Cryptography Recovery Sortings Ostatni
VE VYSTAVBE!

Principy kompresnich algoritmu pro obrazky

  1. Morse, Morzeovka
  2. DIM, Zmena soustavy (dimenze)
  3. HUF, Huffman & Shannon-Fano
  4. RLE, Run-Length Encoding
  5. QTree, Ctvercovy strom (QuadTree Code)
  6. Patt, Pattern kody (Pattern)
  7. Diff, Difference Mapping
  8. Fract, Fractal kody (Fractal Code)
  9. CCITT, Tiff kody (CCITT)
    Priloha 1 - CCITT3, PackBits
  10. LZW (LZ, LZW) - Lempel-Ziv-Welch
  11. Ari, Aritmericky kod (Arithmetic code)
    Transformace
  12. BWT - Burrows-Wheeler transformace
  13. Wave transformace
  14. Wave: DCT - Kosinova transformace
  15. (nedok) Wave: DWT - WaveLet transformace
  16. (nedok) Wave: Ostatni
    Priloha 2 - JPEG 4x4 DCT 1D
    Priloha 3 - JPEG 4x4 DCT 2D
    Priloha 4 - JPEG 8x8 DCT 2D "dct.htm" (4k) JavaScript program
  17. (nedok) MPEG - Motion Jpeg
  18. (osobni) XOR compression

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

Morzeovka (Morse 1838)


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

DIM - Zmena soustavy (change dimension) [TXT]


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

HUF - Huffman (1952 David Huffman) & Shannon-Fano (1948) [TXT TIFF JPG]


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

RLE - Run-Length Encoding (RLE code T. Huang 1972) [TXT PCX GIF TIFF BMP]


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) (3X=yes/no)
	 (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
	(idealne: 2x2+4x3 / 6/2*(6+1) -> 16/21 = 76%)
	-----------------               
	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 (60 kodu)
	(idealne: 2x2+4x3 / 6/2*(6+1)-1 -> 16/20 = 76% skoro realne)
			(idealne: 4x4+8x5+16x6+32x7 / 60/2*(60+1) -> 379/1830 = 21%)

	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 kodu)
Hlavni menu

QTree - Ctvercovy strom (QuadTree Code) [BW]


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

Patt - Pattern kody (Pattern) [BW TIFF]


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

Difference Mapping [MPEG DIVX JPEG2000]


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

Fract - Fractal kody (Fractal Code) 1977 [MPEG]


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

Tiff kody - CCITT4 [BW]



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

LZW (LZ77 1977, LZW) - Lempel-Ziv-Welch (1979) [GIF ZIP TIFF JPG BW TXT ...]



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

Aritmericky kod (Arithmetic code 1988) [TXT, (JPG), LWF]



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

BWT - Burrows-Wheeler transformace (1983) +Huff; Imp, 777Zip, B2Zip


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		AG = serazeno podle A
	IN	1423422		12 1
	rot+1	2142342 	22 2
	rot+2	2214234 	24 3
	rot+3	4221423 	24 4
	rot+4	3422142 	32 5
	rot+5	2342214 	43 6
	rot+6	4234221 	41 7 (i G2 = A1[in])
	        A     G   	AG i = index (A2,G2)
	A = [in]AGFE...
	G = [in]GFED...
	rot+1 = 423422x -> x423422
	rot+2 = 42342yx -> yx42342 == rot+1(rot+1) x42342y -> yx42342
	!pozor, serazeni musi byt Stabilni! (ABA [123] -> AAB [132] = stabilni, [312] = nestabilni)
	
	OUT = G2 + index
	OUT = 2244231 + 7[1] (8)
	(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 + 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 15: Strucneji
	DATA->BWT
	1423422 -> 1423422+7
		A = agfed... = 1224324
		G = gfed...a = 2243241
		first = G = a (index = 7)
		seradim podle A
		A = 1222344
		G = 2244231
		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
JS BTW crypt
Hlavni menu

Wave Transformace JPEG, EPIC, LWF, Huff/ZeroTree/Ari



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, a┬čkoli ne nutn┼_) rodina z┬ákladu funkce. Ne jako sinusovka, vlnka m┬á jeho energii koncentrovanou v┬čas. Sinusoids jsou u┬žite┬čn─" 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

DCT - Kosinova transformace (diskretni) - JPEG


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 podstate 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.
The Luminance Quantization Table q(u, v)     The Chrominance Quantization Table q(u, v)

----------------------------------           ------------------------------
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
----------------------------------           ------------------------------


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 07 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 09 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.
Pekny zdroj: http://www.cs.sfu.ca/CourseCentral/365/li/material/notes/Chap4/Chap4.2/Chap4.2.html Hlavni menu

DWT - WaveLet Transformation (diskretni)


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

Wave: Ostatni



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

MPEG - Motion Jpeg [MPeg, DivX]


?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 zp┬sob k╦_dov┬án─" videosekvenc─" vhodn─> pro evropskou i americkou televizi s datov─>m proudem kolem 1,5 Mb/s pomoc─" DCT a zp┬sob 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 komunika┬čn─" 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 zp┬sob k╦_dov┬án─" videosekvenc─" vhodn─> pro evropskou i americkou televizi s datov─>m proudem kolem 1,5 Mb/s pomoc─" DCT a zp┬sob 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 komunika┬čn─" 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

XOR compression


Jednoduche a chytre :)
	A: 0 0 1 1 X
	B: 0 1 0 1 O
	---------- R
	C: 0 1 1 0	C = A XOR B
A xor B xor C xor D = 0 => 0A   (2b/4b)
A xor B xor C xor D = 1 => 1ABC (4b/4b) ==> D = 1 xor A xor B xor C
2/3 = 66%

Data =  1010  0100 0101 0000 (16b)
Comp = 1101  1010 1010 00    (14b)
14/16 = 7/8
XXXXXXXXX
not xor error

Hlavni menu

Priloha 1 - CCITT3


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

Priloha 2 - JPEG 4x4 DCT 1D


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

Priloha 3 - JPEG 4x4 DCT 2D


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