Validation And Implementation Of Spiht For Image Compression(Set Partitioning In Hierarchical Trees ) Part 2

Validation And Implementation Of Spiht For Image Compression(Set Partitioning In Hierarchical Trees )  Part 2

Validation And Implementation Of Spiht For Image Compression (Set Partitioning In Hierarchical Trees ) part 1

If the set is of type £, we add each coordinate in 0(i, j) to the end of the LIS as the root of a set of type D. Again, note that these new entries in the LIS have to be examined during this pass. We then remove (i j) from the LIS.

Once we have processed each of the sets in the LIS (including the newly formed ones), we proceed to the refinement step. In the refinement step we examine each coefficient that was in the LSP prior to the current pass and output the nth most significant bit of |c_ij|. We ignore the coefficients that have been added to the list in this pass because, by declaring them significant at this particular level, we have already informed me decoder of the value of the nth most significant bit.

This completes one pass. Depending on the availability of more bits or external factors, if we decide to continue with the coding process, we decrement n by one and continue. Let's see the functioning of this algorithm on an example.

We will go through three passes at the encoder and generate the transmitted bitstream, then decode this bitstream.

First pass:The value for n in this case is 4. The three lists at the encoder are

LIP:{(0,0)® 26, (0,1) ®6, (1,0) ® -7, (1,1) ®7}

LIS: {(0,1)D, (1,0)D, (1,1)D}

LSP: {}

In the listing for LIP, we have -included the ® # to make it easier to follow the example. Beginning our algorithm, we examine the contents of LIP. The coefficient at location (0,1) is greater than 16. In other words, it is significant; therefore, we transmit a 1, then a 0 to indicate the coefficient is positive and move the coordinate to LSP. The next three coefficients are all insignificant at this value of the threshold; therefore, we transmit a 0 for each coefficient and leave them in LIP. The next step is to examine the contents of LIS. Looking at the descendants of the coefficient at location (0,1) (13, 10, 6, and 4), we see that none of them are significant at this value of the threshold so we transmit a 0. Looking at the descendants of c₁₀ and c₁₁, we can see that none of these are significant at this value of the threshold. Therefore, we transmit a 0 for each set. As this is the first pass, there are no elements from the previous pass in LSP; therefore, we do not do anything in the refinement pass. We have transmitted a total of 8 bits at the end of this pass (10000000), and the situation of the three lists is as follows:

LIP:{(0,1)® 6, (1,0) ® -7, (1,1) ®7}

LIS: {(0,1) D, (1,0) D, (1,1) D}

LSP: {(0,0) ®26}

Second Pass: For the second pass we decrement n by 1 to 3, which corresponds to a thresh­old value of 8. Again, we begin our pass by examining the contents of LIP. There are three elements in LIP. Each is insignificant at this threshold so we transmit three 0s. The next step is to examine the contents of LIS. The first element of LIS is the set containing the descendants of the coefficient allocation (0,1). Of this set, both 13 and 10 are significant at this value of the threshold; in other words, the set P (0,1) is significant. We signal this by sending a 1 and examine the offsprings of cqi. The first offspring has a value of 13, which is significant and positive, so we send a 1 followed by a 0. The same is true for the second offspring, which has a value of 10. So we send another 1 followed by a 0. We move the coordinates of these two to the LSP. The next two offspring are both insignificant at this level; therefore, we move these to LIP and transmit a 0 for each. As £ (0.1) = {}, we remove (0, l) D from LIS. Looking at the other elements of LIS, we can clearly see that both of these are insignificant at this level; therefore, we send a 0 for each. In the refinement pass we examine the contents of LSP from the previous pass. There is only one element in there that is not from the current sorting pass, and it has a value of 26. The third MSB of 26 is 1; therefore, we transmit a 1 and complete this pass. In the second pass we have transmitted 13 bits: 0001101000001. The condition of the lists at the end of the second pass is as follows:

LIP:{(0,1)® 6, (1,0) ® -7, (1,1) ®7, (1,2) ®6, (1,1) ®4}

LIS: {(0,1) D, (1,1) D}

LSP: {(0,0) ®26, (0,2) ®13, (0,3) ®10}

Third Pass: The third pass proceeds with n = 2. As the threshold is now smaller, there are significantly more coefficients that are deemed significant, and we end up sending 26 bits. You can easily verify for yourself that the transmitted bitstream for the third pass is 1011101010|1|101100|1100000|10. The condition of the lists at the end of the third pass is as follows:

LIP: {(3,0)® 2, (3,1) ® -2, (2,3) ®-3, (3,2) ®-2, (3,3) ®0}

LIS: { }

LSP: {(0,0) ®26, (0,2) ®13, (0,3) ®10, (0,1) ®6, (1,0) ®-7, (1,1) ®7, (1,2) ®6,

(1,3) ®4, (2,0) ®4, (2,1) ®-4, (2,2) ®4}

Now for decoding this sequence. At the decoder we also start out with the same lists as the encoder:

LIP:{(0,0), (0,1), (1,0), (1,1)}

LIS: {(0,1) D, (1,0) D, (1,1) D}

LSP: {}

We assume that the initial value of n is transmitted to the decoder. This allows us to set the threshold value at 16. Upon receiving the results of the first pass (10000000), we can see that the first element of LIP is significant and positive and no other coefficient is significant at this level. Using the same reconstruction procedure as in EZW, we can reconstruct the coefficients at this stage as

24	0	0          0 0          0
0	0
0         0 0         0		0          0 0           0

and, following the same procedure as at the encoder, the lists can be updated as

LIP: {(0,1), (1,0), (1,1)}

LIS: {(0,1) D, (1,0) D, (1,1) D}

LSP: {(0,0)}

For the second pass we decrement n by one and examine the transmitted bitstream: 0001101000001. Since the first 3 bits are 0 and there are only three entries in LIP, all the entries in LIP are still insignificant. The next 9 bits give us information about the sets in LIS. The fourth bit of the received bitstream is 1. This means that the set with root at coordinate (0,1) is significant. Since this set is of type D, the next bits relate to its offsprings. The 101000 sequences indicate that the first two offsprings are significant at this level and positive and the last two are insignificant. Therefore, we move the first two offsprings to LSP and the last two to LIP. We can also approximate these two significant coefficients in our reconstruction by 1.5 x 2³ = 12. We also remove (0, 1) D from LIS. The next two bits are both 0, indicating that the two remaining sets are still insignificant. The final bit corresponds to the refinement pass. It is a 1, so we update the reconstruction of the (0,0) coefficient to 24 + 8/2 = 28. The reconstruction at this stage is

and the lists are as follows:

LIP: {(0,1), (1,0), (1,1), (1,2), (1,3)}

LIS: {(1,0) D. (1,1) D}

LSP: {(0,0), (0,2), (0,3)}

For the third pass we again decrement n, which is now 2, giving a threshold value of 4. Decoding the bitstream generated during the third pass (10111010101101100110000010), we update our reconstruction to

and our lists become

LIP: {3,0), (3,1)}

LIS: {}

LSP: {(0,0), (0,2), (0,3), (0,1), (1,0), (1.1), (1,2), (2,0), (2,1), (3,2)}

At this stage we do not have any sets left in LIS and we simply update the values of the coefficients.

Algorithm Of SPIHT:

1)       Initialization:

    output n = |log₂(max_{(i ,j)}{|c_i,j|})|;

set the LSP as an empty list, and add the coordinates (i, j) € 'H to the LIP, and only those with descendants also to the LIS, as type A entries.

2) Sorting Pass:

2.1) for each entry (i, j) in the LIP do:

2.1.1) output Sn,(i, j);

2.1.2) if Sn(i,j) = 1 then move (i, j) to the LSP

and output the sign of c_i,j

2.2) for each entry (i, j) in the LIS do:

2.2.1) if the entry is of type A then

output Sn(D(i,j));

if Sn(D(i,j)) =1 then

* for each (k, l) e O(i, j) do:

output Sn(k, l);

if Sn(k, l) = 1 then add (k, l) to the

LSP and output the sign of c_k,l

if Sn(k, l) = 0 then add (k, l) to the end of the LIP;

* if £(i, j) =/= 0 then move (i, j) to the, end of the LIS. as an entry of type B, and go to Step 2.2.2); otherwise, remove entry (i, j) from the LIS;

2-2.2) if the entry, is of type B then

output Sn(£(i, j));

if Sn(£(i, j)) = 1 then

add each (k, l) e O(i, j) to the end of the US as an entry of type A;

remove (i, j) from the LIS.

3) Refinement. Pass: for each entry (i, j) in the LSP, except those included in the last sorting pass (i.e., with same n), output the nth most significant bit of |c_i,j|.

4) Quantization-Step Update: decrement n by 1 and go to Step 2.

 Bitplane Coding:

In numerous applications such as medical or business documents only the error free compression    is required for doing proper diagnosis. In such cases instead of wavelet coding bitplane coding is used which is an effective technique of encoding to obtain a lossless image.

Bit-plane decompsition:

It becomes very difficult to encode the whole image. The image is therefore divided into the no of bitplanes and each plane is encoded individually. The individual plane is called as a tile. Each tile is divided into the number of code blocks and each code block is compressed individually by using bitplane coding.

For each block an embedded bitstream is created. The bitstream of each block obtained by bitplane coding is embedded and compressed.

Each of these codeblok contains a single coefficient. Bitplane coding does the scanning of the coefficients in the zigzag manner.Bitplane coding uses runlength coding.With the help of bitplane coding we can get upto 20%bit savings.

Bitplane coding:

Following table consists of the absolute values of the coefficients.0 and 1 indicates the sign of these coefficients.Runlength coding is used to indicate how frequently the coefficients appear.

Conclusion:

1.We have presented an algorithm that operates through Set Partitioning In Hierarchical Trees(SPIHT).

2.It accomplishes completely embedded coding i.e. coding and decoding can be stopped at any point and the image can be decompressd and reconstructed.
3.The realization of this principle in matched coding and decoding algorithm is new one and is shown to be more effective than in the previous implementation of EZW technique.

4.The results of this coding algorithm with its embedded code and fast execution are so impressive that it is used for standerdization in many image compression systems.

 Rreferences:

[1] J. M. Shapiro, "Embedded image coding using zerotrees of" wavelet  coefficients," IEEE Trans. Signal Processing, vol. 41. pp. 3445-3462.Dec. 1993

.[2]Vorc, B. Jawerth, and B. J. Lucicr. "Image compression through wavelet transform coding," IEEE Trans. Inform. Theory, vol. 38, pp.719-746. Mar. 1992,

[3] W E, H. Adelson. E. Simoncelli. and R. Hingorani. "Orthogonal pyramid transforms for image coding," in Proc. SPIE. vol. 845, Visual Commun.and Image Proc. !!, Cambridge. MA, Ocl, 1987.

[4]M, Antonini. M, Barlaud. P. Maihieu. and I, Daubcc-hics, "Image codingusing wavelet transform.'' IEEE Trans. Image Processing, vol. 1, pp.205-220, Apr. 1992.

. [5] A. Said and W. A. Pearlman. "Image compression using the spatial orientation tree," in IEEE Int. Symp. Circuits and Synemi, Chicago, IL,May 1993. pp. 279-282.

 [6] P. Srirani and M. W, Marcelin, "Wavelet coding of images using  trellis coded quantization," in SPIE Conf. Visual Inform. Process.,Orlando, FL, Apr. 1992, pp. 238-247

also

[7] "Image coding using wavelet transforms and entropy-constrained trellis quantization." IEEE Trans.

Image Processing, vol. 4, pp. 725-733, June 1995,

[8]. Y. H. Kirn and J. W. Modesino, "Adaptive entropy coded subband coding of images," IEEE Trans. linage Processing, vol. 1, pp. 31-48,Jan. 1992

[9] N. Tanabe and N. Farvardin. "Subband image coding using entropy-constrained quantization over noisy channels," IEEE J. Select. Areas Commun., vol. 10, pp. 926-943, June 1992-

[.10] J. H. Kasner and M. W, Marcellin. "Adaptive wavelet coding of images,"in Proc. 1994 IEEEConf. Image processing Ausiin, TX. Nov. 1994,vol. 3, pp. 358-362,

[11], A, Said snd W. A. Pearlman. "Reversible image compression via multiresolution representation and predictive coding." in Proc. SPSEConf. Vi'ttdt Coin.iiiuniciilions rinl Image Processing '93, Cambridge,MA. Nov. 1993, I'roc. .SPifc 2094. pp. 664-674.

[12] D, P. de Gai-rido. W. A, Pearlinan, ;ind W. A. finamore, "A clustering algorithm for entropy-constra.ined vector quantizer design with appli­cations in coding image pyramids." IEEE Trails. Circuits Syst. VideoTechnol.. vo!, 5. pp. 83-95. Apr. 1995,