ENEE631 Building Block 2

1. Lena.pgm
2. Baboon.pgm
3. Test image 512x512: barbara.pgm
4. The PGM file format can be found at
   http://www.dcs.ed.ac.uk/home/mxr/gfx/2d/PGM.txt
5. The standard is introduced in Wallace's article. You can draw the block diagram before you do the programming. It helps you to design the system and debug your program.  Here are some suggestions which may help you.

• Suppose we have implemented the DCT, quantization and zigzag, we obtain a series of AC coefficients in a Block as follows

            

DC	0	7	0	0	0	0	1
0	0	19	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

We can code the AC as (1)[3]7, (4)[1]1, (2)[5]19, EOB.  

1. The symbol, (n) , denotes how many zeros preceding a nonzero AC value
2. [m] denotes how many bit size a nonzero AC coefficient takes ( Check Table. 3 p.13 in Wallace's article). Actually, (n) and [m] consist the symbol 1 in the Wallace' article. 
3. The third number ,such as 7, a and 19, is the symbol 2. (as Sec 7.1 in Wallace').  
4. We code EOB ( end of block) to represent all zeros from this position to the end of the block.

• In JPEG standard, we implement the Huffman coding on the pair of (n), [m].  It is necessary to build up a Table to analyze the distribution. Creating an array, like Table 2 in Wallace's article, is helpful. For example (barbara.pgm 512*512) ,

 

(n)  \  [m]	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	4096	12668	7450	3326	1232	311	6	0	0	0	0	0	0	0	0	0
1	0	3575	1267	304	49	9	0	0	0	0	0	0	0	0	0	0
2	0	1632	418	69	11	1	0	0	0	0	0	0	0	0	0	0
3	0	1004	228	32	13	0	0	0	0	0	0	0	0	0	0	0
4	0	656	152	15	4	0	0	0	0	0	0	0	0	0	0	0
5	0	519	69	5	0	0	0	0	0	0	0	0	0	0	0	0
6	0	451	71	7	0	0	0	0	0	0	0	0	0	0	0	0
7	0	374	43	7	0	0	0	0	0	0	0	0	0	0	0	0
8	0	288	26	3	0	0	0	0	0	0	0	0	0	0	0	0
9	0	200	23	3	0	0	0	0	0	0	0	0	0	0	0	0
A	0	194	28	1	0	0	0	0	0	0	0	0	0	0	0	0
B	0	166	12	0	0	0	0	0	0	0	0	0	0	0	0	0
C	0	128	8	0	0	0	0	0	0	0	0	0	0	0	0	0
D	0	65	5	0	0	0	0	0	0	0	0	0	0	0	0	0
E	0	28	3	0	0	0	0	0	0	0	0	0	0	0	0	0
F	86	26	0	0	0	0	0	0	0	0	0	0	0	0	0	0

                           Figure I Barbara AC zero run length and size distribution Table ( Q=1)

Note the EOB (End of Block, for each block) in (0,0) and ZRL (Zero Run, for number of zero-runs over 15) in (F,0)

• From the figure I, we can build up the Huffman code table

(n)/[m]	code legnth	Huffman Code	(n)/[m]	code length	Huffman Code
01	2	10	D1	9	011100000
02	2	_00	F0	9	011101111
00	3	10	14	10	1100111110
03	4	1110	33	10	0111000010
11	4	1111	72	10	1100111100
04	5	1111	82	10	0110001000
12	5	11000	A2	10	0110001010
21	5	11010	E1	10	0110001001
31	5	01101	43	11	01100010111
41	6	110010	92	11	11001111011
51	6	011001	F1	11	11001111111
05	7	1100110	15	12	011100001110
13	7	0111010	24	12	110011110100
22	7	1101110	34	12	110011111101
32	7	0110000	63	12	011000101101
61	7	1101111	73	12	011000101100
71	7	1101100	B2	12	110011111100
81	7	0111001	C2	12	011100001100
42	8	01110110	06	13	1100111101011
91	8	11011011	44	13	0111000011010
A1	8	11011010	53	13	0111000011111
B1	8	11001110	D2	13	0111000011110
C1	8	01100011	83	14	11001111010101
23	9	011100011	93	14	11001111010100
52	9	011100010	E2	14	01110000110111
62	9	011101110	25	15	011100001101101
			A3	15	011100001101100

                      Figure II Barbara AC zero run length and size Huffman Code Table ( Q=1)

• We can code the intermediate symbol 1 and symbol 2 of AC coefficients according to this table. In the previous example,  (1)[3]7, (4)[1]1, (2)[5]19, EOB,  we can code it as  0111010,111; 110010,1; 011100001101101, 10011; 10. 
• Determine what kind of information should be stored as side-information, thus decoder can decode it. In other words,  a file format is needed.