## 1. Introduction

SPIHT (** Set Partitioning In hierachical trees**), being an efficient coding method for wavelet coefficients, has acquired more and more widely application, especially in image/video compression fields. But, conventional SPHIT have some obvious limitions. For example, when for the color image compression, polarmetric SAR image compression, or multi-spectrum image compression and other multi-channel image compression, there are only very limited image planes(R,G,B for color image, HH, HV,VVfor polarmetric SAR images) but there exist large amount of information redundancy among the image planes. So, considering the support length of discrete wavelet transform, we can’t use the set 8-partition methods such as 3D-SPIHT which has been used for video compression. Another example, when the input image is unsymmetrical such as 16x512 image block even only one line image content, which is very common in hardware design, because it means the larger final chip die size for the many line buffers. But, the traditional SPIHT codec can acquire the best compression performances only for the image is symmetrical in horizontal and vertical dimension. To the above specific applications, I will discuss several kinds of modified SPIHT in this chapter, most of them are the author’s newly research result.

In the following section, We will give a simple description about the traditional SPIHT codec, then, we will take the polarimetric SAR intensity image compression as example and give some specific compression method for multi-channel image compression. Certainly, before encoding for the wavelet coefficients, we need a 3D matrix transform to remove the information redundancy among the image plane and in each image plane. For the unsymmetrical image compression used in hardware design, an unsymmetrical SPIHT codec is detailed addressed, at the time, its specific case for only 1 line image compression, 1D SPIHT codec is also given.

## 2. Traditional SPIHT codec[1]

SPIHT can be used to compress the traditional image, but it need 2D discrete wavelet transform (DWT) before encode the wavelet coefficients. The correlation of DWT coefficients not only exist in each subband inside but also among different subbands. Conventional SPIHT codec is to encode coefficients by SOT (Spatial Orientation Tree), which utilize the correlation of the same subband and different subbands. Conventional SPIHT codec, having many advantages such as simpleness, embedded code stream when compared with other encoders, is a very efficient compression method.

According the SOT structure, the set partitioning can be defined as:

Here,

Conventional SPIHT encoding process can be divided into sorting pass and refinement pass. During the encoding process, 3 lists are used to record the corresponding encoding information, which include List of insignificant set (LIS), list of insignificant pixel (LIP) and list of significant pixel (LSP). The basic operation is significance test and the significance test function is just as the following:

The encoding process can be simply described as:

Output the initialized threshold

For a spatial orientation tree

Sorting pass is for every element

Decrease the n and continue the sorting pass and refinement pass until meet the required bit number or the end of encoding.

The decoding process is same to the encoding process, which, compared with EZW, make it un-necessary to transmit position information because the position information is embedded in the encoding process.

## 3. Multi-channel image compression

SPIHT, utilizing the information redundancy of 2D wavelet coefficients and adopting set 4 division, can be used to compress 2D image data. Naturally, it can be enlongated to 3D video compression, that is to say, if we adopt 3D DWT to remove the information redundancy of video data and choose set 8-partition instead of set 4-partition to encode 3D wavelet transform coefficients, this method is called 3D-SPIHT. But at some cases, we only need to compress multi-channel image, such as color images (R,G, B), polarimetric SAR image (HH,HV,VV), multi-spectrum image, ect. Because the third dimension usually have only limited image planes and can’t be processed by supported discrete wavelet transform, however there exist much information redundancy among each image channel. In this case, consider it’s simplity, 2D DWT for each image plane and 1D DCT can be used to remove the information redundancy. In the following section 3.1-3, taking polarimetric SAR image as example, 3D matrix transform and the related compression method including bit allocation based encoding method and 3D SPIHT Embedded method will be addressed.

### 3.1. 3D matrix transform for multi-channel image

At first, 3D-matrix [2-3] is adopted to represent the multi-polarimetric SAR intensity images. The 1^{st}, 2^{nd} and 3^{rd} planes represent the HH, HV and VV polarimetric SAR intensity image respectively. Assuming the image dimensions are:

Because there are only 3 components in polarimetric channel and KLT is dependent on the statistic properties of data, DCT other than DWT or KLT or other linear transforms is chosen to remove the redundancy of polarimetric channels. According to DCT transform definition, the DCT transform can be represented as:

The 3D-matrix can be composed in other orders, such as HH, VV, HV acted as the 1^{st}, 2^{nd} and 3^{rd} planes respectively. The components of like-polarimetric(HH and VV) have strong correlation, while the components of cross-polarimetric (HH/VV and HV) have weak correlation. Both the DCT theory and experiment results prove that the DCT coefficients of the matrix composed of HH, HV and VV are the most concentrated and that the decoded images have the least loss at the same coding rate

After 1D-DCT transform, the data power of the 3D-matrix is concentrated into the 1^{st} plane and the redundancy among three data planes decreases greatly. In order to remove the redundancy in every data plane of the 3D matrix, 2D-DWT is chosen. According to the definition of 2D-DWT transform, the image data can be decomposed into horizontal, vertical, diagonal and low frequency components after horizontal and vertical filtering. The low frequency component can be decomposed further. After many level discrete wavelet transform, the data power is concentrated to the low frequency components. After 1D-DCT transform and 2D-DWT transform, the power of the whole 3D-matrix is concentrated onto the top left corner. 3 level wavelet transform is adopted, so each data plane is decomposed into 10 subbands including LL_{3}, HL_{3,} LH_{3} HH_{3}, HL_{2}, LH_{2}, HH_{2,} HL_{1,} LH_{1}, HH_{1.} Of all the subbands, the LL_{3} subband of the 1^{st} plane has the highest power.

The 3D-matrix transform of Multi-polarimetric SAR intensity images (1D-DCT among polarimetric channel and 2D-DWT in each polarimetric plane) is illustrated in Figure.1. The 1D-DCT and 2D-DWT are linear transform, so, the operation 1DCT_{z} and 2DWT_{x,y} can be inverted in sequence, that is:

### 3.2. Bit allocation based on differential entropy encoding

The three mixed coefficient planes have different energy, which means different importance. Different bit allocation scheme will greatly affect the quality of decoding images even at the same mean quantization bit rate. Our aim is to find the optimal quantization bits allocation to make the decoding images have the least distortion, which is a constrained optimal problem. The rate distortion function * R(D)* is unknown in most cases, so its solutions have become a hot research issue. Two variant iterate search [4], Dynamic programming [5] and R/D curve modeling [6] are proposed, but these methods yet haven’t been adopted for its enormous computation complexity or the local optimal not the whole optimal bit allocation searched. In this subsection, a new bit allocation method based on differential entropy is proposed. Compared with the existing bit allocation methods, it is easy to find a better bit allocation in whole with the proposed method. At the same time, the computation is not very complex.

Let

Adopt the Lagrangian multiplier,

we can acquire

According to the inequation of rate distortion function for non-Gauss continuous information source, we have:

where

At high bit rate, the lower bound of the inequation approaches the real rate distortion function for most probability distributed information source. So, we can let the lower bound equal to the real rate distortion function and then acquire:

Further, we can acquire

and

For every mixed coefficient plane:

According to the constrain condition

From formula (14), we can acquire the optimal bit allocation for the three mixed coefficient planes, then the conventional SPIHT can be adopted to encode the coefficients for every plane according to the corresponding allocated bit rate.

### 3.3. 3D-SPIHT embedded encoding

The formula (14) provides a method to compute the bit rate allocation，but the bit allocation accuracy strongly depends on the degree of the lower bound of formula (9) approaches the real rate distortion function. So, in most cases, we only can acquire an approximating optimal bit allocation. In this subsection, a new method named 3D-SPIHT embedded algorithm is proposed, which extends the conventional SPIHT algorithm to 3D case. It avoids bit allocation by adopting 3D-SPIHT to encode the three mixed coefficient plane entirely, so the optimal bit rate allocation can be ensured.

During the 3D-SPIHT encoding process, the following sets and lists will be used:

_{iplane,} LIP_{iplane} and LSP_{iplane} represent the

Just as the conventional SPIHT algorithm, the set splitting procedure for every coefficient plane can be defined as following:

The 3D-SPIHT process can be divided into sorting pass and refinement pass, whose basic operations is also significance test of set just as the conventional SPIHT algorithm. That is，

where

The followings are the coding process:

(For the HH HV VV combination,

For every coefficient plane, set list of significant pixels (LSP_{iplane}) as NULL, then add the coordinate
_{iplane} and those that have descendants to LIS_{iplane,} at the same time, set their type to be A.

Sorting pass

If

If

If

Refinement pass

If
* n*th most significant bit of

If
* n*th most significant bit of

If
* n*th most significant bit of

Quantization updating

Decrement * n* by 1 and go to step 2 until acquire the desired compression ratio.

The code stream of embedded 3D-SPIHT encoding can be illustrated as figure.2. The decoding process and encoding process are just the same. So, it’s easy to present the decoding process according to the 3D-SPIHT encoding process. The code stream of 3D-SPIHT is more compact and efficient for the three mixed coefficient planes are interleaved during the encoding process.

Additionally, it is necessary to be mentioned that there have been two kinds of 3D-SPIHT algorithms before. One is proposed for video compression by extending the conventional SPIHT algorithm to 3D case directly and encoding the 3D-DWT wavelet coefficients of video data, so the SOF is defined as 8 splitting [7]. The other is proposed for compression of multispectral images, which make some amendments of the conventional SPIHT by adding one spectral child to every baseband coefficient, so its SOF is still 4 splitting [8]. The proposed 3D-SPIHT embedded coding in this book is very different from the two existing 3D-SPIHT algorithms, which encodes 1 or 2 or 3 coefficient planes of the 3 mixed coefficient plane sequentially by adopting 3 independent thresholds.

## 4. Unsymmetrical SPIHT codec

It is easy to find that the set partitioning is keeping on 4 partitioning for conventional SPIHT codec, that is to say the same set partitioning in vertical and horizontal direction. This means that the wavelet decomposition only can be implemented under the constraint of the same decomposition level in vertical and horizontal direction, which will affect the redundancy removing of image data efficiently and the final compression performance. The unsymmetrical SPIHT codec, adopting set 2-partitioning or set 4-partitioning according the requirements, doesn’t require the same decomposition level in vertical and horizontal direction. So, DWT can be implemented with each highest feasible decomposition level in vertical and horizontal direction respectively and then the spatial redundancy can be removed efficiently.

Because the flow chart of unsymmetrical SPIHT codec is very near to conventional SPIHT codec, only the difference is given.

Assume the image dimensions are

All set partitions for conventional SPIHT are set 4 partitioning just as the formula 2, but the set partitions for unsymmetrical SPIHT are set 2-partitioning or set 4-partitioning, just as the following formula:

Here,

When

## 5. 1D SPIHT codec

In section 4, unsymmetrical SPIHT codec is detailed described, which also need 2D image data or image block. But, in real time image transmission or scan display system, the image data are usually transmitted or displayed line by line. In order to use conventional SPIHT or unsymmetrical SPIHT, it needs many line buffers to store the previous image data. In hardware, it is a high burden for the costly RAM. So, 1 line image data compression method will have the precedence over other block based compression methods, such as the 1D DWT followed 1D SPIHT codec which will be addressed in the following.

After 1D DWT, the wavelet coefficient also has the natural pyramid characteristic: every pixel of the high frequency subband has its 2 corresponding pixels in its adjacent level high frequency subbands in position, which means that only set 2-partitioning can adopted. The illustration is given in fig3.

The SOT and set partitioning can be written as formula 19 and 20.

From fig 5 and formula 19 and 20, we can see that 1D SPIHT use set 2 partitioning to encode 1D DWT coefficients, which only need 1 line buffer RAM but leave another dimensional redundancy un-removed.

## 6. Conclusion

In this chapter, SPIHT and it’s derivatives or its modification methods, such as 3D-SPIHT, 3D-SPIHT Embedded method, Unsymmetrical SPIHT and 1D-SPIHT are described, which can overcome the disadvantages of traditional SPIHT codec and meet the specific requirements for the real applications. Fig.6 gives the derivative relationship of traditional SPIHT and its several modified methods. We can see that SPIHT is the foundation for traditional symmetrical image, but it can’t meet the requirements at some specific applications, such as multi-channel image, strip image (unsymmetrical image), even image line. But, its modified version can meet some specific requirements in real applications.

## References

- 1.
Said A. Pearlman W. A. 1996 - 2.
D. E. Dudgen, R. M. Mersereau, Multidimensional digital signal processing, New Jersey：prentice-Hall, Inc., 1984 . - 3.
Zhu Yanqiu，Chen Hexin，Dai Yisong. Compression Coding of color image via 3-D matrix transform [J] ACTA EI ECTRONICA SINICA，1997 25 7 16 21 - 4.
Y. Shoham, A. Gersho, Efficient bit allocation for an arbitrary set of quantizers, IEEE Transaction on Acoustics,Speech, and Signal Processing, 1988 ,36(9):1445-1453 - 5.
P. Prandoni, M. Vetterli, R/D optimal linear predication, IEEE Transaction on Speech and Audio Processing, 2000 ,8(6):646-655. - 6.
Aminlou A. Fatemi O. 2003 2003 112 115 - 7.
Kim B. J. Xiong Z. Pearlman W. A. 3 D set partitioning in hierarchical trees(3-D SPIHT), IEEE Transaction on Circuilt and System for Video technology,2000 - 8.
Dragotti P. L. Poggi G. Ragozini A.R.P. 2000 416 EOF 428 EOF - 9.
W. Zhang C. Y. Wang F. G. Hu H. - 10.
Zhang Zhi-hui, Zhang Jun, Unsymmetrical SPIHT Codec and 1D SPIHT Codec, International Conference on Electrical and Control Engineering (ICECE), 2010 wuhan 2498:2501.