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

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. _{4}is 0, the second symbol a_{3 }has a code 1110 and so on. Proceeding as above, we obtain the encoded bit stream as 0111011110100110.**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

_{4 }(“0”), then a_{3 }(“1110”), followed by a_{5 }(“1111”), a_{4 }(“0”),a_{1 }(“10”), a_{4 }(“0”) and a_{2 }(“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:

## No comments:

## Post a Comment