Decompressing an image with a Huffman tree?
First, an image was compressed using run-length encoding, then a Huffman tree was created for the run-lengths (image below). The Huffman tree is included in the image header and looks like this:
The binary sequence consists of alternating run length and color. According to the task, I was supposed to draw an image, which is shown above. I tried several times, but I could only determine the width (7), height (5), and color depth (3). How do I do it?
(1 votes)
Loading...
In the coded image data there is always alternately a Huffman code which encodes the running length, and a color whose value is three bits long (color depth 3 bit).
So let’s see what Huffman code is at the beginning. For this we begin in the root of the tree. When we read a zero, we go to the left child node when we read one, to the right.
The first bit is a zero, so we go to the left and land at a blade node, so the code is over here. The running length 1 is stored in the blade node. We read the next 3 bits (color depth), which are 000. So we color the next 1 pixels with the color 000.
And now the whole thing from the front: we start again at the root. We read one and go right. We read another one and go right. We read again a 1 and arrived at a blade node that stores the running length 20 . We read the color: 001. So we color the next 20 pixels with the color 001.
Do you have the rest?
Thank you for the answer. At first, the numbers below the leaf nodes have confused me. If I look at this, it looks as if they represent the number of events in the picture (20th episode, for example, only 1 time). I drew the picture from left to right and top to bottom: 1 * 000, 20 * 001, 5 * 100, 1 * 000, 2 * 110, 5 * 100, 1 * 000.
That’s right. Thanks for the star!
No problem!