Huffman Coding on Image

Encode and Decode Image using Huffman Coding, a concept in Digital Image Processing

Introduction

In this article, we will cover Huffman Coding Algorithm and Its application in compressing an image. We will first go through the algorithm, later code it in python, and test it on an image.

Huffman Coding is one of the lossless compression algorithms, its main motive is to minimize the data’s total code length by assigning codes of variable lengths to each of its data chunks based on its frequencies in the data. High-frequency chunks get assigned with shorter code and lower-frequency ones with relatively longer code, making a compression factor ≥ 1.

In Information Theory, Shannon’s source coding theorem expresses that an independent and identically distributed random variable data code rate (average code length for symbols) cannot be smaller than the Shannons entropy. It is proven that Huffman Coding Algorithm provides optimality following Shannon’s source coding theorem, ie after encoding it provides the lowest possible bit rate.

Huffman Coding

Following are the two steps in Huffman Coding

• Building Huffman Tree
• Assigning codes to Leaf Nodes

Building Huffman Tree

First Compute probabilities for all data chunks, build nodes for each of the data chunks and push all nodes into a list. Now pop the least two probabilistic nodes and create a parent node out of them, with probability as the sum of both their probabilities, now add this parent node to the list. Now repeat the process with the current set of nodes until you create a parent with probability = 1.

Assigning codes to Leaf Nodes

By following the tree build from the above procedure, at an arbitrary node assign its child nodes with child_word = current encoded-word + ‘0’ / ‘1’ to its left/right nodes. Apply this procedure from the root node.

Image Compression using Huffman Coding

Digital Image is nothing but a 3D matrix, the data we need to encode are the dimensions of the image and intensities of each pixel. Let there are r rows, c columns, and d channels for the image, then we need to encode r*c*d +3, ie r*c*d intensities and 3 dimensions r,c,d.

Follow the below Python code implementation of Huffman Coding

• Image and Node Class

• Image read and Initialisation

self.r, self.c, self.d indicates r,c,d of an image. self.image_data contains sets of values that need to be encoded, so it contains all intensity values of all pixels in addition to r,c,d of the image, so its length will be r*c*d+3 as discussed earlier. self.hist creates histogram and self.freqs contains non-zero frequency values from self.hist. To store the mapping of probabilities with data values self.prob_dict is used.

Note that self.hist, self.freqs and self.prob_dict interprets same information in diffrent formats, ie for example if self.image_data = [ 2, 3, 9, 2, 7] then self.hist = [0,0,2,1,0,0,0,1,0,1] (9-sized histogram) , self.freqs = [2,3,7,9] , self.prob_dict = {2 : 2/5 , 3 : 1/5 , 7 : 1/9, 9 : 1/9} . For later usage we use self.prob_dict

• Encoding Image Matrix

After the Initialization of data variables in the previous step, we proceed to our main algorithm. As discussed it consists of two main parts Building Huffman Tree (Up Tree) and Assigning codes to Leaf nodes (Down Tree).

In Up Tree we have a sorted list of nodes, our algorithm is to pop the least 2 probabilistic nodes and create a parent out of it. Later proceed until a single node of probability 1 is found and name it as the root node.

In Down Tree, we start at the root node and proceed to children nodes following a convention. In the below code I append ‘0’ to the left node and ‘1’ to the right node

• Sending and Decoding the Compressed File

Now in self.encodedString we have a string of 0’s and 1’s. If we write this entire string directly into a file, you will be amazed that the file size is much much larger than you anticipated. This happens because when you try to insert string of 0’s and 1’s into the file, you are inserting char(0)/char(1) at a time ie 8 bits at a time, but our motive is to insert bit(0)/bit(1) not char(0)/char(1). To tackle this we are using BitArray library to push the string, it internally converts the string of chars to bitarray and later pushes it to the mentioned file.

Now while decoding we are trying to read a list of int(0,1) from the compressed file, for this we used bitarray library. After reading the binary data into a list we will try to decode numbers out of it by traversing from the root node to one of the leaf nodes. we will stop if our length is r*c*d + 3

You may have noticed in the above code, that I have first encoded r,c,d . So we can find r, c, d by looking at the first three decoded integers. After getting the final list of numbers, we create an output matrix with dimensions that are the first 3 integers from the list and use the remaining ones for the intensities of the pixels.

• Final Steps and Final Code

Below I provided full code and a helper function(self.huffmanCode)to carry out all these other functions in order.

• Code Run and Testing

pip3 install bitstring
pip3 install bitarray
python3 code.py