Сode for “Fun” Image
Enviado por guitardark001 • 14 de Agosto de 2014 • Informe • 1.206 Palabras (5 Páginas) • 161 Visitas
ode for “Fun” Image
The “Fun” image shown below is a bitmap graphic with 32×16 = 512 pixels using 6 different colors: White, yellow, magenta, blue, black, and red.
If the different pixel colors are encoded using a fixed length binary representation, such as the one shown in the following table:
Color Code White 000 Yellow 001 Magenta 010 Blue 011 Black 100 Red 101
then 3 bits are needed for each pixel. This results in a total size of 32×16×3 = 1536 bits when no data compression is used.
One data compression strategy to reduce the number of bits needed to represent the image is to use short strings to encode colors that occur frequently and longer strings for colors that are occur less frequently. Counting the number of pixels for each color in the “Fun” image yields:
1
Color # of Pixels Probability White 394 394/512 = 0.770 Yellow 42 42/512 = 0.082 Magenta 30 30/512 = 0.058 Blue 22 22/512 = 0.043 Black 18 18/512 = 0.035 Red 6 6/512 = 0.012 Sum 512 1.000
Huffman coding is a recursive procedure to build a prefix-free variable length code with shortest average length from the above table. It works as follows. Start by writing down all the colors, together with their probabilities or the number of times they occur, in increasing numerical order, e.g., from right to left as shown below.
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
Huffman’s algorithm regards each of the quantities listed above as a leaf of a (upside-down) tree. In a first step the two leaves that occur least frequently are joined by branches to an intermediate (or parent) node which gets labeled with the sum of the weights of the joined leaves as shown next.
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
24
Now the procedure is repeated, working with the remaining leaves and the newly created intermediate node. Note that the problem size has now been reduced by one, i.e., from creating a code for 6 quantities to creating a code for 5 quantities in this example. These two features, reduction of the size of the problem in each step, and repetition of the same procedure on the smaller problem, is what characterizes a recursive algorithm. The next step of the Huffman coding algorithm, again combining the two quantities with the lowest weight into an intermediate node, is shown in the figure below.
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
24
46
2
The following three figures show the next steps of building the tree for the Huffman code.
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
24
46
72
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
24
46
72
118
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
24
46
72
118
512
Once the tree is completed, label the two branches emanating from each parent node with different binary symbols, e.g., using 0 for all left branches and using 1 for all right branches, as shown in the next figure
394 white
42 yellow
30 magenta
22 blue
18 black
6 red
24
46
72
118
512
0 1
0
1
0 1
0
1
0
1
The code for each leaf in the tree is now obtained by starting at the root (the node at the top of the upside-down tree) and writing down the branch labels while travelling to the leaf. The result is shown in the figure below.
3
Note that, because all codes are for quantities which are tree leaves (and not intermediate nodes),
...