Figure 7: From the luma quantisation matrix to the Huffman tree

both bitmap (high resolution) and text/HTML versions are provided to ease graphical reworks/redrawing/editing. HTML was written and tested with Mozilla/Netscape and i made screenshots that can be reused.

Figure 9: From the luma quantisation matrix to the Huffman tree


Q[8][8]=

	A	B	C	D	E	F	G	H
A	16	11	10	16	24	40	51	51
B	12	12	14	19	26	58	60	55
C	14	13	16	24	40	57	69	56
D	14	17	22	29	51	87	80	62
E	18	22	37	56	68	109	103	77
F	24	35	55	64	81	104	113	92
G	49	64	78	87	103	121	120	101
H	72	92	95	98	112	100	103	99

a) The original division matrix





65536/Q=

\	A	B	C	D	E	F	G	H
A	4096	5958	6554	4096	2731	1638	1285	1285
B	5461	5461	4681	3449	2521	1130	1092	1191
C	4681	5041	4096	2731	1638	1150	949	1170
D	4681	3855	2979	2260	1285	753	819	1057
E	3641	2979	1771	1170	964	601	636	851
F	2731	1872	1191	1024	809	630	580	712
G	1337	1024	840	753	636	542	546	649
H	910	712	690	669	585	655	636	662

b) Modified, multiplication matrix
(65536 was chosen as an arbitrary scaling constant, it does not change the resulting tree's topology)

The 2-dimensional Huffman algorithm

\	A	B	C	D	E	F	G	H
A	4096	5958	6554	4096	2731	1638	1285	1285
B	5461	5461	4681	3449	2521	1130	2041	1191
C	4681	5041	4096	2731	1638	1150	(13)	2227
D	4681	3855	2979	2260	1285	1572 (10)		(16)
E	3641	2979	1771	2194	1773	1237 (4)		1563
F	2731	1872	1191	(14)	(12)	1210 (2)		(8)
G	2361 (15)		1593 (11)		1221	1088 (1)		1311
H	1622 (9)		1359 (7)		(3)	1291 (5)		(6)
	00000	00000	00000	00000	00000	00000	00000	00000

c) First Huffman pass

\	A	B	C	D	E	F	G	H
A	4096	5958	6554	4096	2731	2923 (24)		2476
B	5461	5461	4681	3449	2521	2280		(19)
C	4681	5041	4096	4991	2923	(18)	4268 (30)
D	4681	3855	2979	(31)	(23)	2809
E	3641	4851	2962	3887		(22)
F	2731	(29)	(20)	(28)		2298		2874
G	3983		2952			(17)		(25)
H	(27)		(26)		2512 (21)
	00000	00000	00000	00000	00000	00000	00000	00000

d) 2nd Huffman pass

\	A	B	C	D	E	F	G	H
A	9557	5958	6554	6827 (36)		5399 (34)
B	(44)	5461	8130 (41)		4801 (33)
C	4681	5041	9087 (43)				4268
D	4681	6834 (40)
E	6372			6810 (38)		5683 (37)
F	(35)
G	8834 (42)		5914 (39)		4810 (32)
H
	00000	00000	00000	00000	00000	00000	00000	00000

e) 3rd Huffman pass

\	A	B	C	D	E	F	G	H
A	9557	12512 (51)		12226 (49)
B		10502	8130
C	9362	(48)				9069 (45)
D	(46)	15921 (53)
E
F	15206		12724 (50)			10493
G	(52)				(47)
H	00000	00000	00000	00000	00000	00000	00000	00000

f) 4th Huffman pass

\	A	B	C	D	E	F	G	H
A		23014		12226
B	18919	(57)	17199 (54)
C	(55)
D		31127 (58)
E
F			23217 (56)
G
H	00000	00000	00000	00000	00000	00000	00000	00000

g) 5th Huffman pass

\	A	B	C	D	E	F	G	H
A
B	41933		29425 (59)
C	(60)
D		31127
E
F			23217
G
H	00000	00000	00000	00000	00000	00000	00000	00000

h) 6th Huffman pass

\	A	B	C	D	E	F	G	H
A
B
C	73060
D	(62)
E			52642 (61)
F
G
H	00000	00000	00000	00000	00000	00000	00000	00000

i) 7th Huffman pass

The resulting 1-dimensional tree

PASS 1

PASS 2

PASS 3

PASS 4

PASS 5

PASS 6

PASS 7

PASS 8

[C,A]=6554 -

- 12512 (51) -

. 23014 .
(57)

. 41933 .
(60)

. 73060 .
(62)

. 125702
(63)

[B,A]=5958 -

[B,B]=5461 -

- 10502 (48) -

[B,C]=5041 -

[A,B]=5461 -

- 9557 (44) -

. 18919 .
(55)

[A,A]=4096 -

[A,C]=4681 -

- 9362 (46) -

[A,D]=4681 -

[D,C]=2731 -

- 4991 (31) -

- 9087 (43) -

. 15921 .
(53)

. 31127 .
(58)

[D,D]=2260 -

[C,C]=4096 -

[B,D]=3855 -

- 6834 (40) -

[C,D]=2979 -

[B,E]=2979 -

- 4851 (29) -

- 8834 (42) -

. 15206 .
(52)

[B,F]=1872 -

[A,G]=1337 -

- 2361 (15) -

- 3983 (27) -

[B,G]=1024 -

[A,H]=910 -

- 1622 (9) -

[B,H]=712 -

[A,E]=3641 -

- 6372 (35) -

[A,F]=2731 -

[D,E]=1170 -

- 2194 (14) -

- 3887 (28) -

- 6810 (38) -

. 12724 .
(50)

. 23217 .
(56)

. 52642 .
(61)

[D,F]=1024 -

[E,E]=964 -

- 1773 (12) -

[E,F]=809 -

[E,C]=1638 -

. 2923 .
(23)

[E,D]=1285 -

[C,E]=1771 -

- 2962 (20) -

- 5914 (39) -

[C,F]=1191 -

[C,G]=840 -

- 1593 (11) -

- 2952 (26) -

[D,G]=753 -

[C,H]=690 -

- 1359 (7) -

[D,H]=669 -

[H,E]=851 -

- 1563 (8) -

- 2874 (25) -

- 5683 (37) -

. 10493 .
(47)

[H,F]=712 -

[H,H]=662 -

- 1311 (6) -

[H,G]=649 -

[G,D]=819 -

- 1572 (10) -

- 2809 (22) -

[F,D]=753 -

[G,E]=636 -

- 1237 (4) -

[F,E]=601 -

[F,H]=655 -

- 1291 (5) -

- 2512 (21) -

- 4810 (32) -

[G,H]=636 -

[E,G]=636 -

- 1221 (3) -

[E,H]=585 -

[F,F]=630 -

- 1210 (2) -

- 2298 (17) -

[G,F]=580 -

[G,G]=546 -

- 1088 (1) -

[F,G]=542 -

[E,B]=2521 -

- 4801 (33) -

- 9069 (45) -

. 17199 .
(54)

. 29425 .
(59)

[F,C]=1150 -

- 2280 (18) -

[F,B]=1130 -

[H,C]=1170 -

- 2227 (16) -

- 4268 (30) -

[H,D]=1057 -

[G,B]=1092 -

- 2041 (13) -

[G,C]=949 -

[C,B]=4681 -

- 8130 (41) -

[D,B]=3449 -

[D,A]=4096 -

- 6827 (36) -

. 12226 .
(49)

[E,A]=2731 -

[F,A]=1638 -

- 2923 (24) -

- 5399 (34) -

[G,A]=1285 -

[H,A]=1285 -

- 2476 (19) -

[H,B]=1191 -

j) The sorted and cleaned Huffman tree

	A	B	C	D	E	F	G	H
A	16	11	10	16	24	40	51	51
B	12	12	14	19	26	58	60	55
C	14	13	16	24	40	57	69	56
D	14	17	22	29	51	87	80	62
E	18	22	37	56	68	109	103	77
F	24	35	55	64	81	104	113	92
G	49	64	78	87	103	121	120	101
H	72	92	95	98	112	100	103	99

	A	B	C	D	E	F	G	H
A	16	11	10	16	24	40	51	51
B	12	12	14	19	26	58	60	55
C	14	13	16	24	40	57	69	56
D	14	17	22	29	51	87	80	62
E	18	22	37	56	68	109	103	77
F	24	35	55	64	81	104	113	92
G	49	64	78	87	103	121	120	101
H	72	92	95	98	112	100	103	99

	A	B	C	D	E	F	G	H
A	16	11	10	16	24	40	51	51
B	12	12	14	19	26	58	60	55
C	14	13	16	24	40	57	69	56
D	14	17	22	29	51	87	80	62
E	18	22	37	56	68	109	103	77
F	24	35	55	64	81	104	113	92
G	49	64	78	87	103	121	120	101
H	72	92	95	98	112	100	103	99