Envoyé par
extrait du readme
8) The final step === Huffman coding
-------------------------------------
First an IMPORTANT note : Instead of storing the actual value , the JPEG standard
specifies that we store the minimum size in bits in which we can keep that value
(it's called the category of that value) and then a bit-coded representation
of that value like this:
Values Category Bits for the value
0 0 -
-1,1 1 0,1
-3,-2,2,3 2 00,01,10,11
-7,-6,-5,-4,4,5,6,7 3 000,001,010,011,100,101,110,111
-15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111
-31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111
-63,..,-32,32,..,63 6 .
-127,..,-64,64,..,127 7 .
-255,..,-128,128,..,255 8 .
-511,..,-256,256,..,511 9 .
-1023,..,-512,512,..,1023 10 .
-2047,..,-1024,1024,..,2047 11 .
-4095,..,-2048,2048,..,4095 12 .
-8191,..,-4096,4096,..,8191 13 .
-16383,..,-8192,8192,..,16383 14 .
-32767,..,-16384,16384,..,32767 15 .
In consequence for the previous example:
(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-8) ; (2,1) ; (0,0)
let's encode ONLY the right value of these pairs, except the pairs that are
special markers like (0,0) or (if we would have) (15,0)
57 is in the category 6 and it is bit-coded 111001 , so we'll encode it
like (6,111001)
45 , similar, will be coded as (6,101101)
23 -> (5,10111)
-30 -> (5,00001)
-8 -> (4,0111)
1 -> (1,1)
And now , we'll write again the string of pairs:
(0,6), 111001 ; (0,6), 101101 ; (4,5), 10111; (1,5), 00001; (0,4) , 0111 ;
(2,1), 1 ; (0,0)
The pairs of 2 values enclosed in bracket paranthesis, can be represented on a
byte because of the fact that each of the 2 values can be represented on a nibble
(the counter of previous zeroes is always smaller than 15 and so it is the
category of the numbers [numbers encoded in a JPG file are in range -32767..32767]).
In this byte, the high nibble represents the number of previous 0s, and the
lower nibble is the category of the new value different by 0.
The FINAL step of the encoding consists in Huffman encoding this byte, and then
writing in the JPG file, as a stream of bits, the Huffman code of this byte,
followed by the remaining bit-representation of that number.
For example, let's say that for byte 6 ( the equivalent of (0,6) ) we have a
Huffman code = 111000;
for byte 69 = (4,5) (for example) we have 1111111110011001
21 = (1,5) --- 11111110110
4 = (0,4) --- 1011
33 = (2,1) --- 11011
0 = EOB = (0,0) --- 1010
The final stream of bits written in the JPG file on disk for the previous example
of 63 coefficients (remember that we've skipped the first coefficient ) is
111000 111001 111000 101101 1111111110011001 10111 11111110110 00001
1011 0111 11011 1 1010
décodage JPEG : arbres de Huffman
Répondre avec citation
Partager