Abstract: The SPIHT algorithm was powerful, efficient and simple image compression algorithm. By using this algorithm, the highest PSNR values for given compression ratios for a variety of images can be obtained. SPIHT stands for Set Partitioning in Hierarchical Trees. SPIHT was designed for optimal progressive transmission, as well as for compression. The important SPIHT feature is its use of embedded coding. The pixels of the original image can be transformed to wavelet coefficients by using wavelet filters. The problem in SPIHT is that it only implicitly locates the position of significant coefficients. This makes it difficult to perform operations, such as region selection on compressed data. By region selection, selecting a portion of a compressed image which requires increased resolution. Compressed data operations are possible with the Wavelet Difference Reduction (WDR) algorithm. The term difference reduction refers to the way in which WDR encodes the locations of significant wavelet transform values, in this paper I describe about SPIHT and WDR both are compressed algorithm with embedded coding. By experimental approach, I find that WDR is better than SPIHT for high resolution images.
Keywords : image compression, Set Partitioning in Hierarchical Trees, significant and insignificant pixels, Wavelet Difference Reduction, bit plane encoding.
I .COMPRESSION USING SPIHT
One of the defects of SPIHT[1] is that it only implicitly locates the position of significant coefficients. This makes it difficult to perform operations, such as region selection on compressed data, which depend on the exact position of significant transform values. By region selection, also known as region of interest (ROI), we mean selecting a portion of a compressed image which requires increased resolution. The term difference reduction refers to the way in which WDR encodes the locations of significant wavelet transform values. WDR [4] can produce perceptually superior images, especially at high compression ratios.
In a progressive transmission method, the decoder starts by setting the reconstruction image to zero. It then inputs (encoded) transform coefficients, decodes them, and uses them to generate an improved reconstruction image. The main aim in progressive transmission is to transmit the most important image information first. This is the information that results in the largest reduction of the distortion. SPIHT uses the mean squared error (MSE) distortion measure.
--------- (1.1)
where, N is the total number of pixels. So the largest coefficients contain the information that reduces the MSE distortion.
1.1 SPIHT Process
SPIHT sorts the coefficients and transmits their most significant bits first. A wavelet transform has already been applied to the image and that the transformed coefficients are sorted. The next step of the encoder is the refinement pass. The encoder performs a sorting step and a refinement step in each iteration. SPIHT uses the fact that sorting is done by comparing two elements at a time, and each comparison results in a simple yes/no result. The encoder and decoder use the same sorting algorithm, the encoder can simply send the decoder the sequence of yes/no results, and the decoder can use those to duplicate the operations of the encoder. The main task of the sorting pass in each iteration is to select those coefficients that satisfy 2n<=|ci,j |<2n+1. This task is divided into two parts. For a given value of n, if a coefficient ci,j satisfies |ci,j|>=2n, then that it is said as significant; otherwise, it is called insignificant. The encoder partitions all the coefficients into a number of sets Tk and performs the significance test.
----------- (1.2)
On each set Tk. The result may be either "no" This result is transmitted to the decoder. If the result is "yes," then Tk is partitioned by both encoder and decoder, using the same rule, into subsets and the same significance test is performed on all the subsets. This partitioning is repeated until all the significant sets are reduced to size 1. The result, Sn(T), is a single bit that is transmitted to the decoder.
The sets Tk are created and partitioned using a special data structure called a spatial orientation tree. This set partitioning sorting algorithm uses the following four sets of coordinates:
1. The first set contain the set of coordinates of the four offspring of node (i, j) is O(i,j). If node (i, j) is a leaf of a spatial orientation tree, then O(i, j) is empty.
2. The second set contain the set of coordinates of the descendants of node (i, j) called D(i,j).
3. The third set contain the set of coordinates of the roots of all the spatial orientation trees called H(i,j).
4. The forth set is a difference set D(i, j)-O(i, j). This set contains all the descendants of tree node (i, j), except its four offspring it represented as L(i,j).
The spatial orientation trees are used to create and partition the sets Tk. The set partitioning rules are as follows:
1. The initial sets are for all roots of the spatial orientation trees.
2. If set D(i, j) is significant, then it is partitioned into L(i, j) plus the four single element sets with the four offspring of (i, j).
3. If L(i, j) is significant, then it is partitioned into the four sets D(k, l), where (k, l) are the offspring of (i, j). The Fig. 3.1 shows the Spatial Orientation Trees in SPIHT.
Figure 3.1: Spatial Orientation Trees in SPIHT
1.2 SPIHT Coding
It is important to have the encoder and decoder test sets for significance .So the coding algorithm uses three lists called list of significant pixels (LSP) initialized as empty, list of insignificant pixels (LIP) to the coordinates of all the roots (i, j) belongs to root set H, and list of insignificant sets (LIS) to the coordinates of all the roots (i, j) in H that have descendants and considered as type A entries.
Algorithm:
Step 1: Initialization: Set n to target bit rate and transmit n
Step 2: Sorting pass:
2.1 for each entry (i, j) in the LIP do:
Sn(i, j) = 1, move (i, j) to the LSP and output the sign of ci,j ;
2.2 for each entry (i, j) in the LIS do:
2.3 if the entry is of type A, then
if Sn(D(i, j)) = 1, then
for each (k, l) in O(i, j) do:
if Sn(k, l) = 1, add to the LSP, output the sign of ck,l;
if Sn(k, l) = 0, append (k, l) to the LIP;
if L(i, j) <> 0, move (i, j) to the end of the LIS, as a type-B entry, and go to step 2.2. else, remove entry (i, j) from the LIS;
2.4 if the entry is of type B, then
output Sn(L(i, j));
if Sn(L(i, j)) = 1, then
append each (k, l) in O(i, j) to the LIS as a type-A entry:
remove (i, j) from the LIS:
Step 3: Refinement pass: for each entry in the LSP, except those included in the last sorting pass, output the nth most significant bit of |ci,j|;
4. Loop: decrement n by 1 and go to step 2 if needed.
II.COMPRESSION USING WDR
Although WDR can produce perceptually superior images, especially at high compression ratios. The WDR compression and decompression systems are shown in Fig. 2.1 and Fig. 2..2.
Figure 2.1: WDR Compression Steps
Figure 2.2:WDR Decompression Steps The only difference between WDR and the Bit-plane encoding is in the significance pass. In WDR, the output from the significance pass consists of the signs of significant values along with sequences of bits which concisely describe the precise locations of significant values.
2.1 WDR Algorithm
The WDR algorithm is a very simple procedure. A wavelet transform is first applied to the image, and then the bit-plane based WDR encoding algorithm for the wavelet coefficients is carried out. WDR mainly consists of five steps as follows:
Step 1: Initialization: During this step an assignment of a scan order should first be made. For an image with P pixels, a scan order is a one-to-one and onto mapping = Xk , for k =1,2,..., P between the wavelet coefficient () and a linear ordering (Xk). The scan order is a zigzag through sub bands from higher to lower levels. For coefficients in sub bands, row-based scanning is used in the horizontal sub bands, column based scanning is used in the vertical sub bands, and zigzag scanning is used for the diagonal and low-pass sub bands. As the scanning order is made, an initial threshold T0 is chosen so that all the transform values satisfy |Xm|< T0 and at least one transform value satisfies |Xm|>= T0 / 2.
Step 2: Update threshold: Let Tk=Tk-1 / 2.
Step 3: Significance pass: In this part, transform values are significant if they are greater than or equal to the threshold value. The difference reduction method consists of a binary encoding of the number of steps to go from the index of the last significant value to the index of the current significant value. The output from the significance pass is the signs of significant values along with sequences of bits, generated by difference reduction, which describes the precise locations of significant values.
Step 4: Refinement pass: The refinement pass is to generate the refined bits via the standard bit-plane quantization procedure like the refinement process in SPHIT method. Each refined value is a better approximation of an exact transform value.
Step 5: Repeat steps (2) through (4) until the bit budget is reached.
III. Experiment with SPIHT
3.1 Experimental Images
The images Lena, Cameraman and Boat are used for the experiments. The original images are shown in Fig. 3.1(a), Fig. 3.2(a), and Fig. 3.3(a), The results of experiments are used to find the PSNR (Peak Signal to Noise Ratio) values using the formulae
Where P is source imageis image reconstructed by compression, N total no of pixels is range of pixel values. PSNR is the ratio between the maximum possible power of a signal and power of corrupting noise that affect the fidelity of its representation. It expressed by logarithmic decibel scale. It is used to measure the quality of reconstruction of compression codec's. If PSNR is high , then reconstruction of image quality is high. The formulae for finding MSE (Mean Square Error) values for the reconstructed image are given. here P and are noisy approximation of one another. When two images are identical MSE value is zero.
In SPIHT, a wavelet transform is applied to the input image and the wavelet coefficients are got. Then the wavelet coefficients are sorted. Then in each iteration a sorting step and a refinement step can be performed. Embedded coding method is used to encode the coefficients. Then the decoder starts by setting the reconstruction image to zero. It then gets the transform coefficients, decodes them, and generates an improved reconstruction image. The results that got by using SPIHT technique are shown in the Fig. 3.1(b), Fig. 3.2(b), Fig. 3.3(b). Some of the best results highest PSNR values for given compression ratios for the sample images have obtained with SPIHT.
Figure 3.1: (a) Lena Original (b) Reconstructed Lena Image by using SPIHT Compression
IV. Experiment with WDR
4.1 Experimental Images
The images Lena, Cameraman, and Boat are used for the experiments. The original images are shown in Fig. 4.1(a), Fig. 4.2(a) and Fig. 4.3(a),
Figure 3.2: (a) Cameraman Original Image (b) Reconstructed Cameraman Image by using SPIHT Compression
Figure 3..3: (a) Boat Original Image (b) Reconstructed Boat Image by using SPIHT Compression
The results of experiments are used to find the PSNR (Peak Signal to Noise Ratio) values and MSE (Mean Square Error) values for the reconstructed images.WDR employs similar encoding stages to SPIHT. It also conducts a sorting pass and a refinement pass for each bit plane. As the counterparts of the three lists in SPIHT, three sets are defined in WDR, i.e. the set of insignificant coefficients (ICS), the set of significant coefficients (SCS), and the temporary set of significant coefficients (TPS). Since WDR does not utilize the zero tree data structure, it does not have a list of insignificant sets as in SPIHT. Instead of directly concatenating the significant coefficients found in a given bit plane to the SCS, like SPIHT adding such coefficients to the LSP, WDR adds newly identified significant coefficients to the TPS. The TPS is later concatenated to the end of the SCS after the refinement pass. The only difference in bit plane encoding between WDR and SPIHT is in the sorting pass. Instead of using zero trees to represent insignificant coefficients, WDR defines a scan order of wavelet coefficients, which traverses all sub bands in a wavelet pyramid from coarse resolutions to fine resolutions. The results that got by using WDR technique are shown in the Fig. 4.1(b), Fig. 4.2(b) and Fig. 4.3(b). Some of the best results highest PSNR values for given compression ratios for the sample images have obtained with WDR.
Figure 4.1: (a) Lena Original Image (b) Reconstructed Lena Image by using WDR Compression
Figure 4.2: (a) Cameraman Original Image (b) Reconstructed Cameraman Image by using WDR Compression
Figure 4.3: (a) Boat Original Image (b) Reconstructed Boat Image by using WDR Compression
V. Performance Analysis
The PSNR values for the images compressed by SPIHT and WDR are tabulated in Table4.1. The MSE values for the images compressed by SPIHT and WDR are tabulated in Table 4.2. The graphical representation of PSNR and MSE values are expressed as a bar graph are shown in Fig. 4.3 and Fig. 4.4.
TABLE 4.1
PSNR VALUES FOR SPIHT Vs WDR COMPRESSION
Image
SPIHT
WDR
Lena
39.85
32.34
Cameraman
35.56
26.07
Boat
37.59
28.85
Table 4.2
MSE VALUES FOR SPIHT Vs WDR COMPRESSION
Image
SPIHT
WDR
Lena
6.7242
6.1524
Cameraman
18.0679
12.6651
Boat
11.32
9.20
GRAPH 4.3
MSE values for SPIHT and WDR Compression
The SPIHT method provides highest image quality, progressive image transmission, fully embedded coded file, Simple quantization algorithm, fast coding/decoding, completely adaptive, lossless compression, exact bit rate coding and Error protection.
GRAPH 4.4
VI. Conclusion
Furthermore, its embedded coding process proved to be effective in a broad range of reconstruction qualities. From the experiment and performance analysis it was observed that the reconstructed images are having high PSNR values and low MSE values.
It is not hard to see that WDR is of no greater computational complexity than SPIHT. For one thing, WDR does not need to search through quad trees as SPIHT does. The calculations of the reduced binary expansions add some complexity to WDR, but they can be done rapidly with bit-shift operations. WDR provides such good results when compare to SPIHT. From the experiment and performance analysis, it was observed that the PSNR and MSE values are good on the images.
VII.Reference
[1] A. Said, W.A. Pearlman. "A new, fast, and efficient image codec based on set partitioning in hierarchical trees". IEEE Trans. on Circuits and Systems for Video Technology, Vol. 6, No. 3, pp. 243-250, 1996.
[2] Shapiro J.M. "Embedded image coding using zero trees of wavelet coefficients". IEEE Trans. Signal Proc., Vol. 41, No. 12, pp. 3445{3462, 1993.
[3] J. Tian, R.O. Wells. "A lossy image codec based in index coding", IEEE Data Compression Conference, DCC'96, 1996, pp.456.
[4] J. Tian, R.O. Wells, Jr. "Image data processing in the compressed wavelet domain". 3rd International Conference on Signal Processing Proc., B. Yuan and X. Tang, Eds., pp. 978{981, Beijing, China, 1996.
[5] Y. Yuan, M. K. Mandal. "Novel embedded image coding algorithms based on wavelet difference reduction", in: Proceedings of IEEE International Conference on Vision, Image and Signal Processing, vol.152, 2005, pp. 9-19.
[6] Ahmed, N., Natarajan, T., and Rao, K. R. "Discrete Cosine Transform", IEEE Trans. Computers, vol. C-23, Jan. 1974, pp. 90-93.
[7] M. Antonini, M. Bar laud, P. Mathieu, I. Daubechies. "Image coding using wavelet transform". IEEE Trans. Image Proc., Vol. 5, No. 1, pp. 205-220, 1992.
[8] Anil K. Jain, Fundamentals of Digital Image Processing, Englewood Cliff, NJ: Prentice Hall, 1989.
[8] G.M. Davis, A. Nosratinia. "Wavelet-based Image Coding: An Overview. Applied and Computational Control", Signals and Circuits, Vol. 1, No. 1, 1998.
