Several Kinds of Modified SPIHT Codec

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:

$$\{\begin{array}{l}T(i,j)=c(i,j)+D(i,j)\\ D(i,j)=O(i,j)+L(i,j)\\ L(i,j)={\displaystyle \sum D(k,l)\begin{array}{cc}& (k,l\end{array}})\in O(i,j)\end{array}$$ E1

Here, $$T(i,j)$$ is spatial orientation tree and $$c(i,j)$$ is a root node of the tree; $$D(i,j)$$ , $$O(i,j)$$ and $$L(i,j)$$ are node $$c(i,j)$$ ’s descendant node set, direct descendant node set and indirect descendant node set. Direct node set $$O(i,j)$$ can be further partitioned into 4 nodes just as the following:

$$O(i,j)\text{ = {}c(2i,2j),c(2i,2j+1),c(2i+1,2j),c(2i+1,2j+1)\text{}}$$ E2

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:

$$S_n\left(T\right)=\{\begin{array}{cc}1,& \underset{\left(i,j\right)\in T}{{\displaystyle \max \left\{\left|c_{i,j}\right|\right\}}}\ge 2^n\\ 0,& otherwise,\end{array}$$ E3

The encoding process can be simply described as:

Output the initialized threshold $n=\lfloor {\log }_2(\max \left|c(i,j)\right|\rfloor$ ; set LSP as NULL; add the root nodes having and no having descendant nodes to LIS and LIP respectively.

For a spatial orientation tree $$T(i,j)$$ , its nodes are partitioned into nodes $$c(i,j)$$ and descendant nodes $$D(i,j)$$ according to formula 1. If node $$c(i,j)$$ is significant, move it from LIP into LSP. If $$D(i,j)$$ is significant, then partition $$D(i,j)$$ into $$O(i,j)$$ and $$L(i,j)$$ . The significant nodes of $$O(i,j)$$ will also be moved to LSP according to the significance test. If $$L(i,j)$$ is significant, then $$L(i,j)$$ will also be partitioned 4 set and test the significance of every set. This process will be continued on.

Sorting pass is for every element $$c(i,j)$$ of LSP; output the $n^{th}$ efficient bit of $$c(i,j)$$ for the current threshold n.

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: $$M\times N$$ , the multi-polarimetric SAR images can be written as a $$M\times N\times 3$$ matrix $$f(x,y,z)$$ $$(x=0,1,2,\cdots M-1;$$ $$y=0,1,2\cdots N-1;z=0,1,2)$$ . In order to remove the redundancy of the matrix, DWT, KLT, DCT and other linear transforms can be used.

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:

$$\begin{array}{l}F(x,y,0)=\frac{1}{\sqrt{3}}{\displaystyle \sum _{z=0}^{2}f(x,y,z)}\\ F(x,y,Z)=\sqrt{\frac{2}{3}}{\displaystyle \sum _{z=0}^{2}f(x,y,z)\cos \frac{(2z+1)Z\pi }{6}}\begin{array}{cc}& \end{array}(Z=1,2)\end{array}$$ E4

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₃, HL_3, LH₃ HH₃, HL₂, LH₂, HH_2, HL_1, LH₁, HH_1. Of all the subbands, the LL₃ 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:

$$1DC{T}_z(2DW{T}_{x,y}(f(x,y,z)))=2DW{T}_{x,y}(1DC{T}_z(f(x,y,z)))$$ E5

Figure 1.

Illustration of 3D-matrix transform of multi-polarimetric SAR intensity images.

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 $R_1$ , $R_2$ , $R_3$ be the optimal bit rate for the three mixed coefficient plane respectively and $R_T$ be the mean bit rate; Let $D(R)$ be distortion rate function. So, the optimal bit allocation problem can be represented as:

$$\{\begin{array}{l}\underset{R_1,R_2,R_3}{\min }(D_1(R_1)+D_2(R_2)+D_3(R_3))\\ \text{subject}\begin{array}{c}\end{array}\text{to}\begin{array}{c}\end{array}{R}_1+R_2+R_3=3R_T\end{array}$$ E6

Adopt the Lagrangian multiplier,

$$F(R_1,R_2,R_3)=D_1(R_1)+D_2(R_2)+D_3(R_3)+\lambda (3R_T-R_1-R_2-R_3)$$ E7

we can acquire

$$\{\begin{array}{l}\frac{\partial D_1(R_1)}{\partial R_1}=\lambda \\ \frac{\partial D_2(R_2)}{\partial R_2}=\lambda \\ \frac{\partial D_3(R_3)}{\partial R_3}=\lambda \end{array}$$ E8

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

$$h(U)-\frac{1}{2}\log 2\pi eD\le R(D)\le \frac{1}{2}\log \frac{{\sigma }^2}{D}$$ E9

where $h(U)$ is the differential entropy of information source and ${\sigma }^2$ is its mean square error.

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:

$$R(D)=h(U)-\frac{1}{2}\log 2\pi eD$$ E10

Further, we can acquire

$$D(R)=\frac{e^{2(h(U)-R)}}{2\pi e}$$ E11

and

$$\frac{\partial D(R)}{\partial R}=\frac{-e^{2(h(U)-R)}}{\pi e}$$ E12

For every mixed coefficient plane:

$$\{\begin{array}{l}{R}_1=h(U_1)-\frac{1}{2}\log (-\pi e\lambda )\\ R_2=h(U_2)-\frac{1}{2}\log (-\pi e\lambda )\\ R_3=h(U_3)-\frac{1}{2}\log (-\pi e\lambda )\end{array}$$ E13

According to the constrain condition $R_1+R_2+R_3=3R_T$ , we can acquire the final bit allocation for every coefficient plane:

$$\{\begin{array}{l}{R}_1=R_T+\frac{2h(U_1)-h(U_2)-h(U_3)}{3}\\ R_2=R_T+\frac{2h(U_2)-h(U_1)-h(U_3)}{3}\\ R_3=R_T+\frac{2h(U_3)-h(U_1)-h(U_2)}{3}\end{array}$$ E14

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:

$H_{iplane}(i,j)$ , $D_{iplane}(i,j)$ , $O_{iplane}(i,j)$ and $L_{iplane}(i,j)$ represent the $iplan{e}^{th}$ coefficient plane’s root node, descendant’s nodes of node(i,j), offspring’s nodes of node(i,j) and indirect offspring’s nodes of node(i,j) respectively. LIS_iplane, LIP_iplane and LSP_iplane represent the $iplan{e}^{th}$ plane’s list of insignificant pixel sets, list of insignificant pixels and list of significant pixels respectively, where $$iplane=1,2,3$$ .

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

$$\{\begin{array}{l}{T}_{iplane}(i,j)=H_{iplane}(i,j)+D_{iplane}(i,j)\\ D_{iplane}(i,j)=O_{iplane}(i,j)+L_{iplane}(i,j)\\ L_{iplane}(i,j)={\displaystyle \sum D_{iplane}(k,l)\begin{array}{cc}& (k,l\end{array}})\in O_{iplane}(i,j)\end{array}$$ E15

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，

$$S_n\left(T_{iplane}\right)=\{\begin{array}{cc}1,& \underset{\left(i,j\right)\in T_{iplane}}{{\displaystyle \max \left\{\left|C_{iplane}(i,j)\right|\right\}}}\ge 2^n\\ 0,& otherwise\end{array}$$ E16

where $C_{iplane}(i,j)$ is the wavelet coefficient of coordinate $(i,j)$ in the $iplan{e}^{th}$ mixed coefficient plane.

The followings are the coding process:

$$\{\begin{array}{l}n\_{\max }_1=\lfloor {\log }_2\left({\max }_{\left(i,j\right)}\left\{\left|C_1(i,j)\right|\right\}\right)\rfloor \\ n\_{\max }_2=\lfloor {\log }_2\left({\max }_{\left(i,j\right)}\left\{\left|C_2(i,j)\right|\right\}\right)\rfloor \\ n\_{\max }_3=\lfloor {\log }_2\left({\max }_{\left(i,j\right)}\left\{\left|C_3(i,j)\right|\right\}\right)\rfloor \\ \begin{array}{c}\end{array}\begin{array}{c}\end{array}n\begin{array}{c}\end{array}\begin{array}{c}\end{array}\begin{array}{c}\end{array}=n\_{\max }_1\end{array}$$ E17

(For the HH HV VV combination, $$n\_{\max }_{\text{1}}n\_{\max }_{3}n\_{\max }_2$$ can always be satisfied)

For every coefficient plane, set list of significant pixels (LSP_iplane) as NULL, then add the coordinate $$(i,j)\in H_{iplane}$$ to LIP_iplane and those that have descendants to LIS_iplane, at the same time, set their type to be A.

Sorting pass

If $n\_{\max }_{3}n$ , only sort $C_1(i,j)$ just as conventional SPIHT algorithm.

If $n\_{\max }_{2}nn\_{\max }_3$ , sort $C_1(i,j)$ and then sort $C_{\text{3}}(i,j)$ in succession.

If $nn\_{\max }_{\text{2}}$ , sort $C_1(i,j)$ and then sort $C_{\text{2}}(i,j)$ , $C_{\text{3}}(i,j)$ in succession.

Refinement pass

If $n\_{\max }_{3}n$ , for any entry (i,j) in $$LS{P}_{\text{1}}$$ except those included in the last sorting pass, output the nth most significant bit of $C_1(i,j)$ .

If $n\_{\max }_{2}nn\_{\max }_3$ , for any entry (i,j) in $$LS{P}_{\text{1}}$$ and $$LS{P}_{\text{3}}$$ except those included in the last sorting pass, output the nth most significant bit of $C_1(i,j)$ and $C_{\text{3}}(i,j)$ .

If $nn\_{\max }_{\text{2}}$ , for any entry (i,j) in $$LS{P}_{\text{1}}$$ , $$LS{P}_{\text{2}}$$ and $$LS{P}_{\text{3}}$$ except those included in the last sorting pass, output the nth most significant bit of $C_1(i,j)$ , $C_{\text{2}}(i,j)$ and $C_{\text{3}}(i,j)$ .

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.

Figure 2.

Code stream illustration for embedded 3D-SPIHT.

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 $$W*H$$ and $$H=h*2^{HLevel}$$ , $$W=w*2^{WLevel}$$ , here $$HLevel$$ , $$WLevel$$ are the highest feasible decomposition level in vertical and horizontal direction respectively. Usually, there exists $$HLevel\ne WLevel$$ when the image size are unsymmetrical. For the conventional SPIHT, the highest feasible decomposition level only can be the lower one of $$HLevel$$ and $$WLevel$$ , so, $$Level=\min (WLevel,HLevel)$$ . But for unsymmetrical SPIHT codec, the highest wavelet decomposition levels in vertical and horizontal direction are $$HLevel$$ and $$WLevel$$ respectively.

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:

$$O(i,j)=\left\{\begin{array}{c}\begin{array}{c}\begin{array}{cc}c(i,2j),c(i,2j+1)\begin{array}{cc}& if\end{array}{H}_0\le i\frac{H}{2}& \end{array}\end{array}\\ \begin{array}{cc}\begin{array}{cc}c(2i,j),c(2i+1,j)& if\end{array}& i{W}_0\le j\frac{W}{2}\end{array}\\ \begin{array}{cc}c(2i,2j),c(2i+1,2j),c(2i,2j+1),c(2i+1,2j+1)& otherwise\end{array}\end{array}\right\}$$ E18

Here, $$H_0=\frac{H}{2^{HLevel-WLevel+1}}$$ ,

$$W_0=\frac{W}{2^{WLevel-HLevel+1}}$$ E19

.

When $$HLevel=WLevel$$ , the unsymmetrical SPIHT codec will completely degenerate into conventional SPIHT codec. When $$HLevel=\text{1}$$ or $$WLevel=\text{1}$$ , only set 2-partitioning are implemented in one direction, the coefficients can be encoded line by line independently. The wavelet transform in another direction is only be used as compacting the image energy. Fig 3 and Fig 4 are the illustrations of conventional SPIHT encoding and unsymmetrical SPIHT encoding at $$HLevel=3$$ or $$WLevel=5$$ .

Figure 3.

The illustration of set partitioning using conventional SPIHT encoding for unsymmetrical image size

Figure 4.

The illustration of set partitioning with unsymmetrical SPIHT encoding for unsymmetrical image size

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.

Figure 5.

The illustration of set partitioning with 1D SPIHT encoding for 1 line image.

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

$$\{\begin{array}{l}T(i)=c(i)+D(i)\\ D(i)=O(i)+L(i)\\ L(i)={\displaystyle \sum D(k)\begin{array}{cc}& (k\end{array}})\in O(i)\end{array}$$ E20

$$O(i)\text{ = {}c(2i),c(2i+1)\text{}}$$ E21

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.

Figure 6.

* mean the corresponding dimension is limited compared other dimensionsFamily of SPIHT and its derivatives.

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.