1

I have a Huffman table from pixel intensities in an image. I need to store this in a binary file as in the DHT format for jpeg images. The receiver can then extract these values but I am at a loss how to reconstruct the table. I describe in great detail exactly how I generated and stored my table in case any sorting sequence affects the end result.

Generate the table

  • In a list make pairs of (frequency, intensity) for each intensity [0,255] and then remove any pairs with 0 frequency.

  • Sort this list in ascending order of frequency. Where multiple pairs have the same frequency, they are sorted by intensity, e.g. [ (1, 7), (1, 55), (1, 107), (2, 4), (2, 19), etc ]

  • Pop the two firstmost pairs, with the first being the left child and the second the right child, put them in a parent node and sort the list again. When sorting the list, for the same frequency first put the individual pairs and then the parent nodes in ascending length order, e.g. [ (1, 107), (2, 4), (2, 19), (2, ((1, 7), (1, 55))) etc ]

  • Iterate to build the whole tree and then walk though it to get the codes.

Store the table

To store the table, the header is formed sequentially by the following:

  • The number of levels in the tree (tends to be 16 anyway)

  • For each level (1-16) how many codes there are, e.g. 0 (for 1), 2 (for 2), 1 (for 3), etc

  • Then just write the intensities in order, e.g. 2 for level 2, 1 for level 3, etc.

  • In order to make sure there have been no mix ups, the codes for each level had initially been sorted numerically, e.g. for level 6: 000100, 000101, 001000, 001001, 001011

Codes after the extraction

So now I can extract these and I get the values in the table below. I've read that this is all one needs to reconstruct the codes but I don't understand the process. For example, my level 2 codes are supposed to be 10 and 11. How do I know that it's not 00 and 01 instead? I have provided the first few levels and I would really appreciate it if you could explain the process just to get me going.

bits | number
-----+--------
1    |    0
2    |    2
3    |    1
4    |    1
5    |    2
6    |    5
7    |    6
8    |    6
9    |   17
etc
Reti43
  • 9,656
  • 3
  • 28
  • 44
  • Are you targeting any specific language? – jedwards Apr 05 '13 at 22:20
  • You might also consider reading about [Canonical Huffman codes](http://en.wikipedia.org/wiki/Canonical_Huffman_code). – jedwards Apr 05 '13 at 22:25
  • No specific language. At the moment I'm writing it in Python because I'm comfortable with the language but I plan converting it to C++ once the whole project is finished. Canonical Huffman codes was indeed the answer to my problem. What an embarrassing mistake of mine. I had come across the idea before and had thought that my code had been canonical, but on closer inspection... – Reti43 Apr 06 '13 at 20:54

1 Answers1

1

All you need to send are the number of bits in the code for each symbol. Zero can indicate that the symbol is not present and so was not coded. The number of bits can itself be Huffman coded and run-length encoded, as done in the deflate format.

Given that set of code lengths, you just need to make sure that the bit sequences are assigned the same way on both ends. This is done using a canonical Huffman code, where the codes are assigned in symbol order within each bit length.

Community
  • 1
  • 1
Mark Adler
  • 101,978
  • 13
  • 118
  • 158