i am trying to implement a JPEG decoder. i was following JPEG standard T.81. i understand how the JPEG file is structured, different marker, etc.
the type of images i am dealing with is lossless, grayscale image, and i am now focusing on Huffman coded images only.
i am not able to understand how Huffman tables work in JPEG. i was able to read the DHT marker and get the BITS and HUFFVAL. i was trying to understand it from Annex C of T.81 but not able to visualize it.
once we read the BITS and HUFFVAL from the DHT marker, what is the next step?
how we build the symbol and code table using these values?
how will the Huffman table look like in the end?
It is important to understand Huffman compression well and how codes are generated to appreciate the DHT segment. I advise you start there first.
In a nutshell, Huffman is a prefix code. Given a bitstream and a Huffman decoding binary tree, you navigate down the tree until you arrive at a leaf, which would be the decoded value. You navigate by following the bitstream bit-by-bit, going left on 0 and right on 1.
Hence, to decode, you need the Huffman decoding binary tree, which is what the DHT segment specifies. It tries to do this in as few bits as possible, which is why it is confusing.
L_i specify the number of codes for each code length. You generate the tree with these lengths. Start with
n = 0for length 1 codes andn <- n + 1for each code of the same length. When going to the next code length,n <- n * 2.An example:
begets
then you can match these with the Vij values also specified in the DHT segment. This is the basic Huffman compression used in JPEG to get another code which you have to further process.
There is much more to the decoding than this. I suggest you read T-81 more thoroughly and/or look for sample JPEG source code for more information.