MATLAB Implementation of Advanced SPIHT with Huffman coding.

We have Published MATLAB Implementation of SPIHT (Set Partitioning in Hierarchical Trees) in previous blog post. You can see this here. This consists of DWT, Quantization and SPIHT encoding. At the end of these processes we will get final compressed code stream.  

Advanced SPIHT with Huffman: 

Transmitter:

Transmitter:

For Detailed description of DWT, Quantization and SPIHT encoding steps visit this post.

Basic principles of Huffman Coding:

Huffman coding is a popular lossless Variable Length Coding (VLC) scheme, based on the following principles:

1. Shorter code words are assigned to more probable symbols and longer code words are assigned to less probable symbols.

2. No code word of a symbol is a prefix of another code word. This makes Huffman coding uniquely decodable.

3. Every source symbol must have a unique code word assigned to it.

In image compression systems Huffman coding is performed on the quantized symbols. Quite often, Huffman coding is used in conjunction with other lossless coding schemes, such as run-length coding. In terms of Shannon’s noiseless coding theorem, Huffman coding is optimal for a fixed alphabet size, subject to the constraint that the source symbols are coded one at a time. 

Assigning Binary Huffman codes to a set of symbols

We shall now discuss how Huffman codes are assigned to a set of source symbols of known probability. If the probabilities are not known a priori, it should be estimated from a sufficiently large set of samples. The code assignment is based on a series of source reductions and we shall illustrate this with reference to the example. The steps are as follows:

Step 1: Arrange the symbols in the decreasing order of their probabilities.

 

Table: Arrangement of symbols according to probabilities.

For this example, we can compute the average code word length.  

Table: Assigned codes for symbols  

Encoding a string of symbols using Huffman codes

After obtaining the Huffman codes for each symbol, it is easy to construct the encoded bit stream for a string of symbols. For example, if we have to encode a string of symbols

a4 a3 a5 a4 a1 a4 a2

We shall start from the left, taking one symbol at a time. The code corresponding to the first symbol a₄is 0, the second symbol a₃ has a code 1110 and so on. Proceeding as above, we obtain the encoded bit stream as 0111011110100110.

In this example, 16 bits were used to encode the string of 7 symbols. A straight binary encoding of 7 symbols, chosen from an alphabet of 5 symbols would have required 21 bits (3 bits/symbol) and this encoding scheme therefore demonstrates substantial compression.

Receiver:

Decompression is the reverse to the compression technique. After SPIHT+Huffman, it is necessary to transform data to the original domain (spatial domain), to do this the inverse wavelet transform is applied first in columns and secondly in rows.

Decoding a Huffman coded bit stream 

Since no code word is a prefix of another codeword, Huffman codes are uniquely decodable. The decoding process is straightforward and can be summarized below: 

Step 1: Examine the leftmost bit in the bit stream. If this corresponds to the codeword of an elementary symbol, add that symbol to the list of decoded symbols, remove the examined bit from the bit stream and go back to step-1 until all the bits in the bit stream are considered. Else, follow step-2.

Step 2: Append the next bit from the left to the already examined bit(s) and examine if the group of bits correspond to the codeword of an elementary symbol. If yes, add that symbol to the list of decoded symbols, remove the examined bits from the bit stream and go back to step-1 until all the bits in the bit stream are considered. Else, repeat step-2 by appending more bits.

In the encoded bit stream example of Section-3.6, if we receive the bit stream 0111011110100110 and follow the steps described above, we shall first decode a₄ (“0”), then a₃ (“1110”), followed by a₅ (“1111”), a₄ (“0”),a₁ (“10”), a₄ (“0”) and a₂ (“110”). This is exactly what we had encoded.

MATLAB Implementation of Advanced SPIHT:

GUI window for compression using SPIHT+Huffman

 

GUI window for decompression using SPIHT+Huffman 

if you want this code then contact us on....

Contact

Mobile Number: +91-9637253197

Whatsup Number: +91-9637253197

Email ID: matlabprojects07@gmail.com

Transmitter:

Transmitter: