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 a4is
0, the second symbol a3 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 a4 (“0”), then a3 (“1110”), followed by a5 (“1111”), a4 (“0”),a1 (“10”), a4 (“0”) and a2 (“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