MATLAB Implementation of SPIHT (Set Partitioning in Hierarchical Trees).

Traditional image coding technology mainly uses the statistical redundancy between pixels to reach the goal of compressing. The research on wavelet transform image coding technology has made a rapid progress. Because of its high speed, low memory requirements and complete reversibility, digital wavelet transform (IWT) has been adopted by new image coding standard, JPEG 2000. The embedded zero tree wavelet (EZW) algorithms have obtained not bad effect in low bit-rate image compression. Set Partitioning in Hierarchical Trees (SPIHT) is an improved version of EZW and has become the general standard of EZW.

Transmitter:

Input Image:

The input image is a grayscale image. File type of that image is .bmp (Bitmap file format) or RAW (Raw image format).These formats are uncompressed hence they are large.

Discrete wavelet transforms:

The purpose served by the Wavelet Transform is that it produces a large number of values having zero, or near zero, magnitudes.

One of the most efficient algorithms in the area of image compression is the Set Partitioning in Hierarchical Trees (SPIHT). In essence it uses a sub-band coder, to produce a pyramid structure where an image is decomposed sequentially by applying power complementary low pass and high pass filters and then decimating the resulting images. These are one-dimensional filters that are applied in cascade (row then column) to an image whereby creating four-way decomposition: LL (low-pass then another low pass), LH (low pass then high pass), HL (high and low pass) and finally HH (high pass then another high pass). The resulting LL version is again four-way decomposed, as shown in Figure 1. This process is repeated until the top of the pyramid is reached. The SPIHT algorithm sends the top coefficients in the pyramid structure using a progressive transmission scheme. This scheme is a method that allows obtaining a high quality version of the original image from the minimal amount of transmitted data. Upper leftmost square represents the smooth information (lowest frequency) i.e. blurred version of image. Other squares represent detail information (edges) in different directions (horizontal, diagonal &vertical) and at different scale.

Quantization

After the wavelet transform, the coefficients are scalar-quantized to reduce the number of bits to represent them, at the expense of quality. The output is a set of integer numbers which have to be encoded bit-by-bit. The parameter that can be changed to set the final quality is the quantization step: the greater the step, the greater is the compression and the loss of quality. With a quantization step that equals 1, no quantization is performed (it is used in lossless compression). 

Set Partitioning in Hierarchical Trees (SPIHT)

Rules for Set Partitioning

The set partitioning rule is designed to work in the subband hierarchy. The objective of the set partitioning algorithm should be such that the subsets expected to be insignificant contain larger number of elements and the subsets expected to be significant should contain only one element.

We first define the following sets before presenting the set partition rules:

O (n1, n2): The offspring set. It contains the coordinates of the pixels, which are offspring of the node (n1, n2)

D (n1, n2): The descendants’ set. It contains all the coordinates of the pixels which are descendants of the node (n1, n2)

L (n1, n2): It is the difference set of D (n1, n2) & O (n1, n2).It therefore contains the descendants of the node (n1, n2) other than the offspring.

H: This set includes the co-ordinates of all spatial orientation tree roots, which belong to the highest level of pyramid, that is, the LL subband.

Based on the above set definitions, the set partitioning rules are presented below:

Rule-1

The initial partition contains D (n1, n2) for each (n1, n2) H.

Rule-2

If D (n1, n2) is found significant, partition it into L (n1, n2) plus four single sets with      (i, j)  O (n1, n2).

Rule-3

If L (n1, n2) is found significant, partition it into four sets of D (i,j),

Where (i, j)  O (n1, n2)

SPIHT ENCODING:

The SPIHT algorithm applies the set partitioning rules, as defined above on the subband coefficients. The algorithm is identical for both encoder and decoder and no explicit transmission of ordering information, as needed in other progressive transmission algorithms for embedded coding, are necessary. This makes the algorithm more coding efficient as compared to its predecessors. Both the encoder and decoder maintain and continuously update the following three lists, viz.

List of Insignificant Pixels (LIP)

The list of insignificant pixels (LIP) contains individual coefficients that have magnitudes smaller than the threshold.

List of Significant Pixels (LSP)

The list of significant pixels (LSP) is a list of pixels found to have magnitudes larger than the threshold (significant).  

List of Insignificant Sets (LIS)

The list of insignificant sets (LIS) contains sets of wavelet coefficients that are defined by tree structures and are found to have magnitudes smaller than the threshold (insignificant). The sets exclude the coefficients corresponding to the tree and all sub tree roots and they have at least four elements.

RECEIVER:

MATLAB Implementation of SPIHT:

GUI window for compression using SPIHT

GUI window for Decompression using SPIHT

 if you want MATLAB code then mail us on......... matlabprojects07@gmail.com