8 May 2015 Modified set partitioning in hierarchical trees algorithm based on hierarchical subbands
Author Affiliations +
J. of Electronic Imaging, 24(3), 033004 (2015). doi:10.1117/1.JEI.24.3.033004
Abstract
This paper introduces a modified set partitioning in hierarchical trees (SPIHT) algorithm that reduces the number of comparison operations and, consequently, the execution time needed to encode an image as compared to the SPIHT algorithm. The threshold of each independent subband is calculated after applying the discrete wavelet transform to the image. Scanning of the sets inside the subbands is determined by the magnitude of the thresholds that establishes a hierarchical scanning not only for the set of coefficients with larger magnitude, but also for the subbands. The algorithm uses the set partitioning technique to sort the transform coefficients. Results show that the modified SPIHT significantly reduces the number of operations and the execution time without sacrificing visual quality and the PSNR of the recovered image.
Ochoa Domínguez, Vergara Villegas, and Cruz Sanchez: Modified set partitioning in hierarchical trees algorithm based on hierarchical subbands

1.

Introduction

It has been proven that image compression algorithms based on the discrete wavelet transform (DWT) provide high coding efficiency for natural images.12.3.4.5.6 DWT has desirable properties, such as efficient multiresolution representation, scalability, vanishing moments, decorrelation, energy compaction, and embedded coding with progressive transmission, which are suitable for image compression.7

Since a few years ago, there has been a growing interest in the set partitioning in hierarchical trees (SPIHT) coder that is an improved version of the embedded zerotree wavelet algorithm.89.10.11.12 SPIHT-based image compression can achieve rate scalability and high coding performance.1314.15.16.17.18.19.20 The encoder makes use of progressive transmission to exploit the self-similarity of the DWT coefficients across different scales. In addition, to iteratively extract the most important information in each subband, SPIHT uses partial ordering by comparing the transformed coefficient’s magnitudes with a set of octave decreasing thresholds.

The coding performance of SPIHT follows close to that of the embedded block coding with optimized truncation, which forms the basis of the JPEG 2000 standard. However, SPIHT has much lower computational complexity. Therefore, there is a great interest to improve its performance.17,21,22 Besides, it provides progressive image transmission, a fully embedded coded file, a simple quantization algorithm, lossless compression, and exact bit rate coding. Furthermore, SPIHT is very useful for applications where the user can quickly inspect the image and decide if it should be downloaded, is good enough to be saved, or needs refinement.

Even when SPIHT is not a standard, it is used in many video applications that use image compression with the embedded coding property2324.25.26 and medical imaging applications with SPIHT as a core.8,20,27,28

One of the main drawbacks of SPIHT is the slow coding speed owing to the dynamic processing order that depends on the image contents.23,2930.31 Efforts to improve the performance have been mostly concentrated in modifying the lists used to store the sets coordinates. For example, Pan et al.21 proposed a listless modified SPIHT by taking advantage of the lifting wavelet scheme and weighted the transform coefficients according to the human visual system. Perceptual significance reordering allows higher peak signal-to-noise ratio (PSNR) values and better visual-quality images. The system reduces the complexity by suppressing the need of lists, but introduces a context-based arithmetic coder to the bit stream to gain more compression. However, substantial improvement is shown only for very low bit rates.

The work presented by Fang et al.22 introduces a new interpolation-based lifting wavelet scheme combined with the Lagrange interpolation to transform the image. The technique also uses lists but considers coefficients higher than the threshold of four as important. Therefore, if D-sets in the list of insignificant sets (LIS) are important, the scanning procedure of the SPIHT is modified to reduce the unnecessary scans. Otherwise, traditional SPIHT is used. However, for high bit rates, the algorithm does not assure to have the same performance as that of SPIHT.

Set partitioning in hierarchical frequency bands (SPHFB)17 uses the set partitioning technique to sort the transform coefficients. The threshold of each subband is calculated, and the subbands scanning sequence is determined by the magnitude of the thresholds. Therefore, the scanning sequence depends on the image content. Previous knowledge of the maximum bit depth of the subbands allows the encoder to find fast the subbands with more energy.

In SPIHT, the main task during a sorting pass is to find significant coefficients. Each coefficient in a subband has to be compared with a threshold even though all the coefficients inside the subband are not significant to the threshold. This search could exacerbate the coding time. Therefore, reducing the number of comparison operations, during sorting passes, is important to reduce the coding time.

In this paper, a modified SPIHT algorithm for image coding, which combines the SPIHT lists and hierarchical subband scanning to save comparison operations during sorting passes, is proposed. The threshold of each independent subband is calculated to find its maximum depth in bits. The sets inside a subband are scanned according to the magnitude of its subband threshold. The scanning of a spatial orientation tree stops if the threshold of a subband containing descendants is less than the current threshold. Hence, sets inside subbands with a higher threshold are scanned first. Two major modifications are proposed: (1) the calculation of one threshold per subband to impose a hierarchical scanning of sets with higher energy and, in contrast to the SPIHT, (2) the LIS must be initially empty and is populated with coordinates of sets in the subbands of higher hierarchy to avoid unnecessary entries to the list. The two modifications allow to outperform the performance in time of SPIHT, listless modified (LM)SPIHT, and Fang et al.22 methods. Along the text, the terms method and algorithm are used indistinctly.

The remainder of the paper is organized as follows. Section 2 gives a theoretical model of the comparison operations of SPIHT. Section 3 describes the modified SPIHT. Section 4 shows the experimental results. Conclusions are drawn in Sec. 5.

2.

Modeling Comparison Operations of SPIHT

SPIHT operates on a hierarchical pyramidal structure χ that is produced by transforming an image by using a DWT implemented with a filter bank.14 The energy compaction is one of the most important metrics in the evaluation of filters used in the transform coding schemes. It refers to the property of how the energy in the transform domain is distributed among its coefficients. For encoding purposes, it is required that most of the energy of an image is concentrated in a few coefficients. In this work, the 9-7 tap biorthogonal wavelet filter bank—Cohen-Daubechies-Feauveau (CDF 9/7)—is used because it is better than others in terms of energy compaction.7 After transformation, the highest-frequency subband has the finest samples and lies at the bottom right of the pyramid. The lowest-frequency subband has the coarsest samples and lies at the top left of the pyramid. At each scale l, the three high-frequency subbands capture the horizontal, vertical, and diagonal directions. The last scale of decomposition yields four subbands including the lowest-frequency subband. Therefore, if the image is decomposed using L scales, a total of 3L+1 subbands are obtained.

At the beginning of the SPIHT encoding process, the maximum threshold Thmax of χ is calculated based on the number of bits needed to represent the highest magnitude coefficient cs(i,j), at position (i,j), by using Eq. (1):

(1)

Thmax=log2(max(i,j)χ{|cs(i,j)|}),
where |.| and . are the absolute value and the floor operations, respectively. Thmax becomes the first current threshold Thc and is the only initial information, about the magnitude of all the coefficients, that is sent to the decoder. Figure 1 shows an example of the pyramidal structure for L=2 of the Lena image with seven subbands and a resulting Thmax=9.

Fig. 1

Pyramidal structure of the Lena image after wavelet decomposition with L=2.

JEI_24_3_033004_f001.png

The data structure proposed by Said and Pearlman14 allows the wavelet coefficients to be arranged into 2×2 arrays that are offsprings of a coefficient of a lower-resolution subband, except for the coefficients in the coarsest subband, where all except one of them are root nodes of a spatial orientation tree. To give a more realistic view, the threshold of each independent subband of Fig. 1 can be calculated to plot the three-dimensional structure of Fig. 2. The arrows show how the various levels of the trees are related because of the similarity between the subbands. The numbers represent the thresholds in bits. Observe the different distances between the subbands.

Fig. 2

Three-dimensional plot of the pyramidal structure χ of the Lena image after wavelet decomposition with L=2 (seven subbands) showing the spatial orientation trees. The numbers represent the threshold’s magnitude of each subband in bits.

JEI_24_3_033004_f002.png

The trees are further partitioned into four types of sets of coordinates of coefficients as detailed next.

  • O(i,j): set of coordinates of the four offsprings of node (i,j). For example, in Fig. 2, the set O(1,0) consists of coordinates of the coefficients d1,d2,d3, and d4.

  • D(i,j): set of coordinates of the descendants of node (i,j). For example, in Fig. 2, the set D(1,0) consists of coordinates of the coefficients d1,,d4,,d11,,d44.

  • : set of coordinates of the roots of all spatial orientation trees (essentially 3/4 of the coefficients in the coarsest subband).

  • L(i,j)=D(i,j)O(i,j). For example, in Fig. 2, the set L(1,0) consists of coordinates of the coefficients d11,,d44.

Two important passes, the sorting and refinement passes, are defined. In a sorting pass, the coefficients are compared with Thc. A “1” bit followed by a sign bit is sent to the decoder for every coefficient equal to or larger than Thc. In addition, the coefficient is marked as significant and it will not be scanned again. However, it will be refined in subsequent refining steps. If the coefficient is less than the current threshold, a “0” is sent to the decoder. It is said that the coefficient is insignificant and it will be compared with the next current thresholds in further sorting passes until it is found significant or the encoding process ends. The operation to determine the significance of a coefficient during a sorting pass is called a comparison operation. The sorting passes also divide the set of samples into partitioning subsets of samples. Each coefficient in a set is compared against the current threshold. If no coefficient is significant, a 0 is sent to the decoder to indicate that the entire set is insignificant to that specific threshold.

From Fig. 2, it can be seen that sets of type O(i,j), inside the three directional subbands, at scale 2 may be found significant until the third sorting pass, when Thc=7. Also, the first significant sets of type L(i,j) in the horizontal, vertical, and diagonal subbands may be found significant until the fifth, fourth, and sixth passes, respectively. Notice that the encoding process is blind beyond the current threshold. That is, no information of the subbands is available to the process. Hence, all the descendants in a tree must be tested for significance, even though they belong to subbands with a threshold less than that of the current threshold, thus performing unnecessary comparison operations during a sorting pass. According to Fig. 2, for an image size of M×N, the maximum number of unnecessary comparison operations C in the first sorting pass can be approximated by Eq. (2):

(2)

C=M×Nl=0L1122(Ll)k=13Il,k,

(3)

Il,k={1,Thc>Thl,k0,otherwise,
where Thl,k is the threshold of the subband at scale l and direction k. Il,k indicates subbands with a threshold less than Thc. However, as the number of passes increase, according to the bit rate requirements, Eq. (3) becomes

(4)

Il,k={ThmaxThl,k,Thc>Thl,k0,otherwise.

Equation (4) is an ill-conditioned equation because the number of unnecessary comparison operations depend on the distance of each subband threshold to the maximum threshold. For natural images, subbands with higher resolution have a lower threshold.14 Therefore, the higher the bit rate, the more are the unnecessary operations. Further, there is an increase of the number of bits required to signal the set’s significance, which only increases the bit rate without contributing to an increase in image quality.

3.

Modified SPIHT

In Sec. 2, it was shown that the use of only one threshold leads to a blind encoder. This increases the number of comparison operations during a sorting pass. One way to reduce the number of operations is by inverting the inequality of Eq. (3). Hence, the contribution during the scanning process is only from the subbands with a threshold higher than or equal to the current threshold as shown in Eq. (5):

(5)

Il,k={1,ThcThl,k0,otherwise.

Algorithm 1 defines four steps: (1) initialization, (2) sorting pass, (3) refinement pass, and (4) threshold quantization step.

Algorithm 1

Modified SPIHT

1: Initialization: output Thl,k=log2⌊(max(i,j)∈sl,k{|csl,k(i,j)|})⌋. Set Thc=max{Thl,k}. Set LSP={∅},LIS={∅}. Add the coordinates (i,j)∈ℋ to LIP.
2: Sorting pass:
 1. For each entry (i,j) in the LIP do:
  (a) Output Sl,k(i,j);
  (b) If S(i,j)=1, then move (i,j) to LSP and output δ[csl,k(i,j)]
 2. For each subband threshold Thl,k do:
  (a) If Thl,k=Thc, then allow sets of subband sl,k to be added to the LIS.
 3. For each entry (i,j) in the LIS do:
  (a) If the set is of type A (2×2 coefficients), then
   i. Output Sl,k[D(i,j)];
   ii. If Sl,k[D(i,j)]=1, then
    • For each csl,k(i,j)∈D(i,j) do
     - Output Sl,k(i,j)
     - If Sl,k(i,j)=1, then move the position of csl,k(i,j) to LSP and output δ[csl,k(i,j)]
     - If Sl,k(i,j)=0, then move the position of csl,k(i,j) to LIP
    • Remove D(i,j) from LIS
   (b) If the set is of type B (4×4 or more coefficients), then
    i. Output Sl,k[L(i,j)];
    ii. If Sl,k[L(i,j)]=1, then divide L(i,j) into four subsets and add the result at the end of LIS;
    iii. Remove L(i,j) from LIS.
3: Refinement pass: For each entry (i,j) in the LSP, except those included in the last sorting pass, output the Thc‘th bit of |csl,k(i,j)|
4: Quantization step: Decrement Thc by 1 and go to step 2.

Here, besides the maximum threshold, it is necessary to obtain information about the maximum height of each subband. Therefore, in the modified SPIHT, the encoder calculates the subbands threshold by using Eq. (6) and sends them to the decoder in an orderly manner according to the subband that they represent.

(6)

Thl,k=log2(max(i,j)sl,k{|csl,k(i,j)|}),
where sl,k is the k’th subband at scale l, and csl,k is a coefficient inside the subband. Hence, a short register containing the 3L+1 thresholds must be initialized, with the current threshold Thc initialized to the maximum threshold. It is important to note that, in the initialization stage, the modified algorithm inspects orderly each subband of χ in order to determine the thresholds, contrary to the SPIHT, which inspects all coefficients of χ to compute a single threshold. Hence, the time added by Eq. (1) to the SPIHT process is the same as the time added by Eq. (6) to the modified algorithm process.

Three lists are maintained as in SPIHT: the list of significant pixels (LSP), the list of insignificant pixels (LIP), and the list of insignificant sets (LIS). LIP contains the coordinates of coefficients that have not been significant to the current or previous sorting passes and is initialized with the set . The encoding process begins by examining the coordinates in LIP. Coefficients are tested for significance by using Eq. (7):

(7)

2Thc+1>|csl,k(i,j)|2Thc.

If the coefficient is insignificant, a 0 is sent to the bit stream leaving the LIP unchanged. If the coefficient is significant, a 1 is sent to the bit stream followed by a sign bit obtained by Eq. (8). Then, the coefficient position is removed from the LIP and placed in the LSP. LSP contains the coordinates of coefficients found significant during sorting passes and is initially empty.

(8)

δ(i,j)={0,csl,k(i,j)01,csl,k(i,j)<0.

LIS stores the coordinates of the roots of sets of type D or L that have not been significant to either the current or previous passes. Significance of a set T of type D or L is tested by using Eq. (9):

(9)

Sl,k{T}={1,max(i,j)T{|csl,k(i,j)|}2Thc0,otherwise.

After examining LIP, the list of thresholds is examined. If the subband threshold is less than Thc, the entire subband is insignificant and it is skipped. Otherwise, the subband is significant to the current threshold, and it is allowed to place the sets at the end of LIS to be inspected in the current pass, as follows:

If a set at coordinate (i,j) is significant, a 1 is transmitted. What we do next depends on whether the set is of type D or L as in SPIHT.

If set is of type D, the four descendants O(i,j) are tested; a 1 is transmitted for each significant coefficient, followed by its sign bit. Their coordinates are placed in the LSP. A 0 is transmitted for each insignificant coefficient and the coordinate is added to the LIP. O(i,j) is removed from the LIS, and if the set L(i,j) exists, it must be moved to the end of the LIS.

If set is of type L, each coordinate in O(i,j) is added to the end of the LIS to be treated as the root of a set of type D.

In the modified SPIHT, the LIS is initially empty and is populated with coordinates of sets according to the thresholds of the subband to which they belong. Notice that SPIHT initializes the LIS with the elements of that have descendants, including those inside subbands with a threshold less than the maximum threshold.

Once the LIP and LIS have been processed, the sorting pass ends and starts the refinement step. In the refinement pass, the coefficients in the LSP, resulting from the previous passes, are examined and the output is the Thcth most significant bit of the coefficients in the coordinates of the list. Before starting a new sorting pass, Thc is decremented. The bit rate is controlled by counting the number of bits of the bit stream and by comparing the count with the total bit budget M×N×Bit ratebpp.

The pseudocode of the modified algorithm is shown below. Notice that after inspecting the LIP, the thresholds register is inspected to decide whether to add the subband sets to the LIS, which means that if there are no subband thresholds equal to the current threshold, the only sets inspected are those in the subbands with a threshold greater than Thc that were found in previous passes.

4.

Experimental Results

In this section, the performance of the proposed modified SPIHT is examined and compared with SPIHT, SPHFB, LMSPIHT, and Fang et al.22 methods using the images of Lena, Barbara, and Mandrill at 8 bpp monochrome 512×512 size.32 The pyramidal decomposition was obtained by the CDF 9/7 filter bank33 with a reflection extension to each image and L=6. The bit rate interval tested was from 0.01 to 4 bpp. No entropy coder was used on the resulting bit stream. PSNR, visual quality, performance with respect to the number of comparison operations in sorting passes, and time performance were compared with those obtained with SPIHT (Ref. 34) and with other algorithms. The methods used in this paper were implemented in C language under the Ubuntu operating system, running on a Dell precision T7500 personal computer, with an Intel Xeon quadcore clocked at 2.40 GHz and 8 GB of memory. It is important to mention that the only processes running in the CPU was the method to be analyzed (one at a time). The comparison operations were counted during the sorting passes, and the execution time was taken including the initialization stage up to the end of the encoding process.

4.1.

Comparison Operations

Table 1 shows the total number of comparison operations after each sorting pass for Lena, Barbara, and Mandrill images. Observe that the modified SPIHT starts from a reduced number of comparison operations. Also, note that the number of comparisons to determine whether a subband is significant is negligible. For example, with L=6, the number of comparisons of Thc with each threshold in the register of thresholds is 19 (3L+1). Even if this number is added to the results of the modified SPIHT in Table 1, the ratio of comparison operations between SPIHT and the modified SPIHT remains.

Table 1

Total number of comparison operations versus sorting passes for Lena, Barbara, and Mandrill.

Sorting passLenaBarbaraMandrill
Modified SPIHTSPIHTModified SPIHTSPIHTModified SPIHTSPIHT
164262,14464262,14464262,144
2166786,406168786,408158786,398
33811,572,7973701,572,7862521,572,732
417752,621,48720572,621,6415222,621,194
510,1853,932,82595993,933,19961473,932,515
666,1345,507,71871,1885,509,49269,4345,509,162
7233,2377,349,813463,7247,370,524521,5017,386,749
8656,2619,461,5251,303,7949,544,8181,678,3289,577,864
91,679,10311,848,7032,687,36012,020,5123,469,75412,094,394
103,246,63014,525,1584,612,88514,790,1335,727,59514,929,579
115,394,68217,541,4986,999,25217,850,4848,289,27418,015,098
128,044,44020,934,9689,790,56121,216,89711,000,79021,248,566
1310,906,27524,535,45912,772,82624,767,06613,723,92124,491,770
1413,867,08128,234,92115,804,93628,360,124

Note: SPIHT, set partitioning in hierarchical trees.

To complete the first sorting pass, for the Lena, Barbara, and Mandrill images, SPIHT takes 262,144 comparison operations, while the modified SPIHT takes only 64. As the number of sorting passes increases, the number of comparisons is exacerbated when using SPIHT, because the number of operations accumulates in every pass. For example, to complete eight sorting passes, SPIHT takes 9.5 millions of comparison operations for the Lena, Barbara, and Mandrill images, while the modified SPIHT takes only 656,261 for the Lena, 1,303,794 for the Barbara, and 1,678,328 for the Mandrill. Finally, after the 14th sorting pass, SPIHT takes ~28.4 millions of comparison operations for the Lena and Barbara, while the modified SPIHT takes 13.8 and 15.8 millions, respectively. In the case of Mandrill, SPIHT takes ~24.5 millions of comparison operations, while the modified SPIHT takes 13.7 millions in 13 sorting passes.

Figures 3(a)3(c) show the total number of comparison operations for Lena, Barbara, and Mandrill versus the bit rate. For the sake of visual clarity, the bit rates of 0.01 and 0.75 bpp are not plotted. It is interesting to note that for the Lena, SPIHT takes almost the same number of comparison operations to reach 0.0625 bpp as the modified SPIHT to reach 1.7 and 2 bpp in the cases of Barbara and Mandrill, respectively.

Fig. 3

Number of comparison operations versus bit rates for (a) Lena, (b) Barbara, and (c) Mandrill images. (d) Plot of comparison operations saved.

JEI_24_3_033004_f003.png

Table 2 shows the number of sorting passes needed to obtain a bit rate. Observe that it is necessary to spend at least six sorting passes to reach 0.01 bpp. Because of the embedded characteristic of the code, the current pass depends on previous passes. Therefore, SPIHT starts from a high number of comparison operations since the first sorting pass, while the modified SPIHT starts from a minimum of these operations.

Table 2

Bit rate versus number of sorting passes.

Bit rate (bpp)LenaBarbaraMandrill
Modified SPIHTSPIHTModified SPIHTSPIHTModified SPIHTSPIHT
0.01666666
0.0625888887
0.1998888
0.2510109988
0.51111101099
0.75111110101010
1.0121211111010
2.0131312121111
3.0131313131212
4.0141414141313

Figure 3(d) shows the comparison operations saved for each image. Lena exhibits the highest saving even though from 2 to 3 bpp the plot has an almost constant behavior owing to the fact that most of the encoded bits belong to refinement passes. In the cases of Barbara and Mandrill, there is an almost linear behavior from 1 to 4 bpp. Notice that the comparison operations gain exhibited in the plots of Figs. 3(a), 3(b), and 3(c) approximates to 2:1 as the bit rate approaches to 4 bpp.

Previous works, such as LMSPIHT21 and that reported by Fang et al.,22 do not consider the bit depth of each subband and the search for significant coefficients is carried out in subbands with thresholds less than the current threshold [see Eqs. (3) and (4)], performing about the same number of comparison operations during a sorting pass as in SPIHT. In LMSPIHT, the partitioning structure is modified causing the length of the LIP and LIS lists to be reduced during the first sorting pass. Fang et al.22 consider the case when the current threshold is too large or too small, the sets O(i,j) will be not so important. This improves the speed of compression and the ratio of important coefficients that convey information about the coded image in the bit stream. However, only for low bit rates, the PSNR is the same as SPIHT. The work that considers the hierarchical scanning of subbands is the SPHFB,17 which makes use of Eq. (5), resulting in about the same number of comparison operations as the modified SPIHT.

4.2.

Execution Time

The aim of the modified SPIHT is to reduce the number of comparison operations needed to encode an image and, hence, the number of searches of significant coefficients. This reduction has a direct impact on the execution time that is at least halved as compared to the SPIHT.

Figure 4 shows the plots of the execution time of the modified SPIHT, compared with SPIHT, SPHFB, LMSPIHT, and Fang et al. methods for the Lena, Barbara, and Mandrill images. Additionally, the plot of time saving of the modified SPIHT with respect to SPIHT is depicted.

Fig. 4

Execution time versus bit rates for (a) Lena, (b) Barbara, and (c) Mandrill images. (d) Time saved of the modified set partitioning in hierarchical trees (SPIHT) with respect to SPIHT.

JEI_24_3_033004_f004.png

The numerical results for different bit rates are summarized in Table 3. The ratios SPIHT/modified SPIHT at bit rates of 0.01, 0.25, 0.5, 1, and 4 bpp for the Lena image are 147.65, 23.28, 11.73, 7.52, 5.02, and 2.16. The modified SPIHT takes only 0.67, 8.51, 13.28, 19.91, and 46.1% of the total time needed for SPIHT to encode the image, whereas for the same bit rates, SPHFB takes 0.67, 13.81, 21.91, 32.39, and 66.23%; LMSPIHT takes 57.74, 48.78, 48.92, 49.47, and 71.80%; and Fang et al.22 takes 59.19, 65.59, 74.02, 79.42, and 100.8% of the total time taken by SPIHT.

Table 3

Execution time comparison (in milliseconds).

Bit rate (bpp)ImageModified SPIHTSPIHTSPHFBLMSPIHTFang et al.22
0.01Lena0.41260.830.41233.3036.01
Barbara0.28257.880.28232.1241.63
Mandrill0.57356.550.57329.1438.01
0.1Lena4.378101.904.4549.9263.94
Barbara5.5496.655.7247.3258.81
Mandrill5.0579.745.5339.0651.89
0.25Lena10.68125.3717.3261.1684.75
Barbara10.52110.5220.7754.1672.64
Mandrill12.8293.2420.0445.6769.02
0.5Lena19.53147.0632.2371.95109.80
Barbara18.66130.0132.9465.30102.00
Mandrill19.18109.1138.9253.4588.645
0.75Lena30.63169.4045.482.62133.53
Barbara28.97153.1546.6978.08116.12
Mandrill29.90123.9549.2176.07100.15
1.0Lena35.25177.0257.3587.58140.60
Barbara33.87162.7161.0190.17134.28
Mandrill35.34129.8362.2186.73112.76
2.0Lena68.89220.67108.93129.73197.40
Barbara65.65213.06110.94137.47183.09
Mandrill64.61175.4398.86123.58160.74
4.0Lena140.53304.84201.92218.88307.30
Barbara129.18294.35186.57208.60290.42
Mandrill130.78254.53177.63183.97260.28

Note: SPHFB, set partitioning in hierarchical frequency bands.

Bold values indicate the best result.

For the Barbara image, the ratios are 205.26, 10.49, 6.9, 4.8, and 2.27, taking 0.48, 9.52, 14.35, 20.81, and 43.88% of the total time as compared to SPIHT, while SPHFB takes 0.48, 18.79, 25.33, 37.49, and 63.38%; LMSPHIT takes 55.49, 49.00, 50.22, 55.41, and 70.86%; and Fang et al.22 takes 71.92, 65.72, 78.45, 85.52, and 98.66% compared with the time taken by SPIHT.

For the Mandrill image, the resulting ratios are 98.7, 7.26, 5.68, 3.67, and 1.94, taking only 1.01, 13.75, 17.58, 27.22, and 51.38% of the total time needed by SPIHT, whereas SPHFB takes 1.01, 21.49, 35.67, 47.91, and 69.78%; LMSPIHT takes 51.52, 48.98, 48.98, 66.80, and 72.27%; and Fang et al.22 takes 67.21, 74.02, 81.24, 86.25, and 102.25% of the time taken by SPIHT.

Notice that in SPIHT, the search for significant coefficients exacerbates the execution time. Hence, it is the most time-consuming operation in the coding process.

Table 4 shows the improvement in speed of compression in % for each bit rate, computed on the time difference between SPIHT and each method for a given bit rate, and taking the time of SPIHT as 100%. In LMSPIHT, the percentage is quite constant upto 0.75 bpp, while Fang et al.22 shows a greater decrease in performance than the rest of the methods as the bit rate increases. Notice that the modified SPIHT exhibits the highest improvement and SPHFB follows this method because both are based on hierarchical subbands.

Table 4

Improvement in the speed of compression (in %) with respect to SPIHT.

Bit rate (bpp)ImageModified SPIHTSPHFBLMSPIHTFang et al.22
0.01Lena99.3299.3245.2640.80
Barbara99.5199.5144.5128.08
Mandrill98.9998.9948.4732.79
0.1Lena95.7095.6351.0137.25
Barbara94.2794.0851.0439.15
Mandrill93.6793.0651.0234.93
0.25Lena91.4886.1851.2232.40
Barbara90.4881.2151.0034.27
Mandrill86.2578.5151.0225.98
0.5Lena86.7278.0851.0725.34
Barbara85.6574.6649.7721.54
Mandrill82.4264.3351.0118.76
0.75Lena81.9273.2051.2321.17
Barbara81.0869.5149.0224.18
Mandrill75.8860.3038.6319.20
1.0Lena80.0967.6050.5320.57
Barbara79.1862.5044.5817.47
Mandrill72.7852.0833.2013.15
2.0Lena68.7850.6441.2110.55
Barbara69.1947.9335.4814.07
Mandrill63.1743.6529.568.37
4.0Lena53.9033.7628.20−0.81
Barbara56.1136.6229.131.34
Mandrill48.6230.2127.72−2.26

Note: Bold values indicate the best result.

The significance reordering of the coefficients in LMSPIHT allows to code more significant information earlier. However, for bit rates >0.5bpp, this method lowers its performance because it scans subbands with thresholds above the current threshold. In SPHFB, the use of hierarchical subbands allows to increase the performance in time. However, the number of bits is increased because new bits are added to the bit stream to signal the set type reducing the PSNR as it will be seen in Sec. 4.3.

4.3.

PSNR Results

The distortion between the original and recovered images was measured by using the PSNR formula:

(10)

PSNR=10log10(2552MSE)dB.

MSE is the mean squared error between the original and the reconstructed image. Figure 5(a) shows the original image, Fig. 5(b) the reconstructed image by using SPIHT, Fig. 5(c) the modified SPIHT, Fig. 5(d) SPHFB, Fig. 5(e) LMSPIHT, and Fig. 5(f) Fang et al. at 0.1 bpp. The resulting PSNRs were 29.81 and 29.82, 30.31, 31.21, and 29.81 dB, respectively.

Fig. 5

Lena images obtained at a bit rate of 0.1 bpp: (a) original image, (b) SPIHT peak signal-to-noise ratio (PSNR)=29.81dB, (c) modified SPIHT PSNR=29.82dB, (d) set partitioning in hierarchical frequency bands (SPHFB) PSNR=30.31dB, (e) LMSPIHT PSNR=31.21dB, and (f) Fang et al. PSNR=29.81dB.

JEI_24_3_033004_f005.png

Figure 6 shows the original image [Fig. 6(a)] along with the reconstructed images at 0.25 bpp by using SPIHT [Fig. 6(b)] and the modified SPIHT [Fig. 6(c)], SPHFB [Fig. 6(d)], LMSPIHT [Fig. 6(e)], and Fang et al. [Fig. 6(f)]. The resulting PSNRs were 33.65, 33.65, 34.15, 34.88, and 33.65 dB, respectively.

Fig. 6

Lena images obtained at a bit rate of 0.25 bpp: (a) original image, (b) SPIHT PSNR=33.65dB, (c) modified SPIHT PSNR=33.65dB, (d) SPHFB PSNR=34.15dB, (e) LMSPIHT PSNR=34.88dB, and (f) Fang et al. PSNR=33.65dB.

JEI_24_3_033004_f006.png

Figure 7 shows the original image [Fig. 7(a)] along with the reconstructed images at 0.5 bpp by using the SPIHT [Fig. 7(b)] and the modified SPIHT [Fig. 7(c)], SPHFB [Fig. 7(d)], LMSPIHT [Fig. 7(e)], and Fang et al [Fig. 7(f)]. Notice that the PSNR yielded by most of the methods is 36.78 dB, except LMSPIHT whose PSNR is 36.80 dB.

Fig. 7

Lena images obtained at a bit rate of 0.5 bpp: (a) original image, (b) SPIHT PSNR=36.78dB, (c) modified SPIHT PSNR=36.78dB, (d) SPHFB PSNR=36.78dB, (e) LMSPIHT PSNR=36.80dB, and (f) Fang et al. PSNR=36.78dB.

JEI_24_3_033004_f007.png

Table 5 shows the comparison of PSNRs. Observe that the LMSPIHT yields, on average, higher PSNR for very low bit rates (0.25bpp). For a bit rate of 0.5 bpp, only the Lena image has a PSNR of 0.02 dB above the other methods. On average, for bit rates >0.25bpp, the modified SPIHT and SPIHT yield a higher PSNR. However, for bit rates >1bpp, the modified SPIHT performs slightly better because of Eq. (5).

Table 5

Comparison of peak signal-to-noise ratio (in dB).

Bit rate (bpp)ImageModified SPIHTSPIHTSPHFBLMSPIHTFang et al.22
0.01Lena22.4622.5424.8025.7022.54
Barbara20.0920.0222.5323.3020.02
Mandrill19.2219.1919.7520.1219.19
0.1Lena29.8229.8130.3131.2129.81
Barbara24.1723.9524.5027.0123.95
Mandrill21.1221.1021.7222.1021.10
0.25Lena33.6533.6534.1534.8833.65
Barbara27.4227.0727.2129.1027.07
Mandrill22.8922.8022.9323.2022.80
0.5Lena36.7836.7836.6536.8036.78
Barbara31.2330.8430.0130.3030.84
Mandrill25.0925.0425.3024.7225.04
0.75Lena38.3438.3637.1137.9537.96
Barbara33.9233.5431.3031.2533.34
Mandrill27.0727.0126.8026.1226.01
1.00Lena39.8839.8838.2238.4339.10
Barbara36.0535.8034.5432.6035.10
Mandrill28.5928.5527.4427.1527.72
2.00Lena44.1144.0539.9540.1643.10
Barbara41.9041.7432.6033.2037.27
Mandrill34.0133.9728.1228.5730.80
3.00Lena47.9647.8740.8241.8345.46
Barbara46.2146.0533.9033.6838.96
Mandrill39.1239.0728.5129.6332.25
4.00Lena52.3052.2141.6042.4047.71
Barbara50.4050.2835.0134.5240.10
Mandrill44.5744.5329.3230.2634.53

Note: Bold values indicate the best result.

4.4.

Visual Quality

The visual quality assessment of the recovered images was addressed according to the structural similarity index measure (SSIM).35 The closer the index to 1, the more similar the two compared signals. The recovered images were compared with the original one.

Table 6 compares the SSIM. For very low bit rates (0.25bpp), LMSPIHT has a slight gain over the rest of the methods. For bit rates >0.5bpp, the modified SPIHT and the SPIHT have a higher SSIM. Both methods perform similar to each other except for the Barbara and Mandrill images at high bit rates (>0.5bpp) where the modified SPIHT performs slightly better.

Table 6

Structural similarity index measure.

Bit rate (bpp)ImageModified SPIHTSPIHTSPHFBLMSPIHTFang et al.22
0.01Lena0.62640.63150.68320.71690.6382
Barbara0.51500.50670.55100.64600.5082
Mandrill0.36260.36110.36520.38740.3645
0.1Lena0.89330.89290.89300.89900.8931
Barbara0.79740.78680.79100.80190.7870
Mandrill0.63370.62390.63560.63850.6240
0.25Lena0.95240.95200.95140.95300.9512
Barbara0.89410.88450.89210.89520.8883
Mandrill0.77360.76960.77300.77490.7701
0.5Lena0.97530.97560.97200.97500.9722
Barbara0.95160.94740.94800.94920.0000
Mandrill0.87810.86870.86050.86900.8713
1.0Lena0.98770.98810.98010.98090.9860
Barbara0.98290.98150.97330.97550.9790
Mandrill0.94280.94070.91210.93520.9221

Note: Bold values indicate the best result.

5.

Conclusions

In this paper, a modified SPIHT algorithm that combines the advantages of SPIHT and the hierarchical scanning of the subbands is proposed. Energy compaction and ordering are two essential requirements for good compression. The DWT CDF 9/7 fulfilled the first requirement and the second requirement was improved by scanning the subband sets according to their corresponding hierarchy imposed by the thresholds, thereby reducing the entries to the LIS, making it grow adaptively according to the image characteristics and drastically reducing the number of comparisons and the time taken by the encoder per sorting pass. The modified SPIHT outperforms the performance in time of SPIHT and other methods analyzed. Another advantage is that the use of the subband thresholds ensures that higher magnitude coefficients are found sooner than in the other methods. The 3L+1 thresholds corresponding to each subband are sent to the decoder in an orderly manner as part of the initial header and maintained in a short register during the entire process, to populate the LIS with sets that are inside the significant subbands. The modified SPIHT preserves the visual quality and PSNR yielded by the SPIHT for all bit rates.

References

1. 

M. Antonini et al., “Image coding using the wavelet transform,” IEEE Trans. Image Process. 1, 205–220 (1992).IIPRE41057-7149http://dx.doi.org/10.1109/83.136597Google Scholar

2. 

J. M. Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,” IEEE Trans. Signal Process. 41, 3445–3462 (1993).ITPRED1053-587Xhttp://dx.doi.org/10.1109/78.258085Google Scholar

3. 

S. Grgic, M. Grgic and B. Zovko-Cihlar, “Performance analysis of image compression using wavelets,” IEEE Trans. Ind. Electron. 48, 682–695 (2001).ITIED60278-0046http://dx.doi.org/10.1109/41.925596Google Scholar

4. 

S. Grgic, K. Kers and M. Grgic, “Image compression using wavelets,” in Proc. IEEE Int. Symp. on Industrial Electronics, pp. 99–104 (1999).Google Scholar

5. 

D. S. Taubman and M. W. Marcellin, JPEG2000: Image Compression: Fundamentals, Standards and Practice, Kluwer Academic Publishers, Boston, Massachusetts (2002).Google Scholar

6. 

S. Yang et al., “Evolutionary clustering based vector quantization and SPIHT coding for image compression,” Elsevier Pattern Recognit. Lett. 31, 1773–1780 (2010).PRLEDG0167-8655http://dx.doi.org/10.1016/j.patrec.2010.04.006Google Scholar

7. 

T. Lee and H. Shen, “Efficient local statistical analysis via integral histograms with discrete wavelet transform,” IEEE Trans. Vis. Comput. Graph. 19(12), 2693–2702 (2013).IETTAW0018-9448http://dx.doi.org/10.1109/TVCG.2013.152Google Scholar

8. 

E. Cavero et al., “SPIHT-based echocardiogram compression: clinical evaluation and recommendations of use,” IEEE J. Biomed. Health Inform. 17(1), 103–112 (2013).http://dx.doi.org/10.1109/TITB.2012.2227336Google Scholar

9. 

Z. Xinjun and W. Xingyuan, “Chaos-based partial encryption of SPIHT coded color images,” Elsevier J. Signal Process. 93, 2422–2431 (2013).SPRODR0165-1684http://dx.doi.org/10.1016/j.sigpro.2013.03.017Google Scholar

10. 

J. Ma, J. Fei and D. Chen, “Rate-distortion weighted SPIHT algorithm for interferometer data processing,” J. Syst. Eng. Electron. 22, 547–556 (2011).1004-4132http://dx.doi.org/10.3969/j.issn.1004-4132.2011.04.001Google Scholar

11. 

E. Christophe, C. Mailhes and P. Duhamel, “Hyperspectral image compression: adapting SPIHT and EZW to anisotropic 3-D wavelet coding,” IEEE Trans. Image Process. 17, 2334–2346 (2008).IIPRE41057-7149http://dx.doi.org/10.1109/TIP.2008.2005824Google Scholar

12. 

M. S. Manikandan and S. Dandapat, “Effective quality-controlled SPIHT-based ECG coding strategy under noise environments,” Electron. Lett. 44, 1182–1183 (2008).ELLEAK0013-5194http://dx.doi.org/10.1049/el:20081319Google Scholar

13. 

W. A. Pearlman et al., “Efficient, low-complexity image coding with a set-partitioning embedded block coder,” IEEE Trans. CSVT 14, 1219–1235 (2004).ITCTEM1051-8215http://dx.doi.org/10.1109/TCSVT.2004.835150Google Scholar

14. 

A. Said and W. A. Pearlman, “A new fast and efficient image codec based on set partitioning in hierarchical trees,” IEEE Trans. CSVT 6, 243–250 (1996).ITCTEM1051-8215http://dx.doi.org/10.1109/76.499834Google Scholar

15. 

C. Yushin and W. A. Pearlman, “Hierarchical dynamic range coding of wavelet subbands for fast and efficient image decompression,” IEEE Trans. Image Process. 16, 2005–2015 (2007).IIPRE41057-7149http://dx.doi.org/10.1109/TIP.2007.901247Google Scholar

16. 

S. Chang and L. Carin, “A modified SPIHT algorithm for image coding with a joint MSE and classification distortion measure,” IEEE Trans. Image Process. 15, 713–725 (2006).IIPRE41057-7149http://dx.doi.org/10.1109/TIP.2005.860595Google Scholar

17. 

H. Ochoa et al., “Set Partitioning in hierarchical frequency bands (SPHFB),” in Proc. of IEEE Data Compression Conf., p. 463 (2009).Google Scholar

18. 

J. Zhu, R. M. Dansereau and A. Cuhadar, “Error-resilient and error concealment 3-D SPIHT video coding with added redundancy,” Lec. Notes Comput. Sci. 6134, 351–358 (2010).LNCSD90302-9743http://dx.doi.org/10.1007/978-3-642-13681-8Google Scholar

19. 

F. Khelifi, A. Bouridane and F. Kurugollu, “On the SPIHT based multispectral image compression,” in Proc. IEEE Int. Symp. on Signal Processing and Information Technology, pp. 359–363 (2006).Google Scholar

20. 

G. Higgins et al., “Lossy compression of EEG signals using SPIHT,” IET Electron. Lett. 47, 1017–1018 (2011).ELLEAK0013-5194http://dx.doi.org/10.1049/el.2011.1037Google Scholar

21. 

H. Pan, W. Siua and N. Lawa, “A fast and low memory image coding algorithm based on lifting wavelet transform and modified SPIHT,” J. Signal Process.: Image Commun. 23, 146–161 (2008).SPICEF0923-5965http://dx.doi.org/10.1016/j.image.2008.01.004Google Scholar

22. 

Z. Fang et al., “Interpolation-based direction-adaptive lifting DWT and modified SPIHT for image compression in multimedia communications,” IEEE Syst. J. 5(4), 584–593 (2011).http://dx.doi.org/10.1109/JSYST.2011.2165602Google Scholar

23. 

Y. Jin, Y. Lee and H.-J. Lee, “A new frame memory compression algorithm with DPCM and VLC in a 4×4 block,” EURASIP J. Adv. Signal Process. 2009(1), 1–18 (2009).Google Scholar

24. 

Y. Jin, Y. Lee and H.-J. Lee, “A block-based pass-parallel SPIHT algorithm,” IEEE Trans. Circuits Syst. Video Technol. 22, 1064–1075 (2012).ITCTEM1051-8215http://dx.doi.org/10.1109/TCSVT.2012.2189793Google Scholar

25. 

J. Zhu and R. Dansereau, “Error-resilient and error concealment 3-D SPIHT for multiple description video coding with added redundancy,” IEEE Trans. Circuits Syst. Video Technol. 22, 855–868 (2012).ITCTEM1051-8215http://dx.doi.org/10.1109/TCSVT.2011.2179453Google Scholar

26. 

T. Xiang, J. Qu and D. Xiao, “Joint SPIHT compression and selective encryption,” Appl. Soft Comput. 21, 159–170 (2014).1568-4946http://dx.doi.org/10.1016/j.asoc.2014.03.009Google Scholar

27. 

O. Rubio, A. Alesanco and J. Garcia, “Secure information embedding into 1D biomedical signals based on SPIHT,” J. Biomed. Inform. 46, 653–664 (2013).JBIOBL1532-0464http://dx.doi.org/10.1016/j.jbi.2013.05.002Google Scholar

28. 

S. Isaa et al., “The effect of electrocardiogram signal compression using beat reordering and SPIHT on automatic sleep stage classification,” Eng. Procedia 41, 888–896 (2012).PERNBE1877-7058http://dx.doi.org/10.1016/j.proeng.2012.07.259Google Scholar

29. 

A. Nandi and R. Banakar, “Throughput efficient parallel implementation of SPIHT algorithm,” in Proc. of Int. Conf. on Very Large Scale Integrated Design, pp. 718–725 (2008).Google Scholar

30. 

N. Zhang et al., “Image compression algorithm of high-speed SPIHT for aerial applications,” in Proc. of IEEE Int. Conf. on Communication Software and Networks, pp. 536–540 (2011).Google Scholar

31. 

R. Sudhakar and S. Jayaraman, “A new video coder using multiwavelets,” in Proc. of Int. Conf. on Signal Processing, Communications and Networking, pp. 259–264 (2007).Google Scholar

32. 

“The USC—SIPI image database,” http://sipi.usc.edu/database/ (February 2013).Google Scholar

33. 

A. Cohen, I. Daubechies and J. C. Feauveau, “Biorthogonal bases of compactly supported wavelets,” Commun. Pure Appl. Math. 45, 485–560 (1992).CPMAMV0010-3640http://dx.doi.org/10.1002/(ISSN)1097-0312Google Scholar

34. 

A. Said and W. A. Pearlman, “SPIHT program,” http://www.cipr.rpi.edu/research/SPIHT/spiht3.html#mat-spiht (January 2013).Google Scholar

35. 

Z. Wang et al., “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process. 13, 600–612 (2004).IIPRE41057-7149http://dx.doi.org/10.1109/TIP.2003.819861Google Scholar

Biography

Humberto de J. Ochoa Domínguez received his BS degree in industrial electronics from the Technological Institute of Veracruz, México, his MSc degree in electronics from the Technological Institute of Chihuahua, México, and PhD degree in electrical engineering from the University of Texas at Arlington, USA. He is a full-time professor at the Universidad Autónoma de Ciudad Juárez. His current teaching and research interests include image and video coding, statistical shape analysis, and pattern recognition.

Osslan O. Vergara Villegas earned his BS degree in computer engineering from the Instituto Tecnológico de Zacatepec in 2000, his MSc degree in computer science from Center of Research and Technological Development (CENIDET) in 2003, and his PhD degree in computer science from CENIDET in 2006. He is a full-time professor at the Universidad Autónoma de Ciudad Juárez. He is a senior member of the IEEE. His fields of interest include computer vision, digital image processing, and augmented reality.

Vianey G. Cruz Sanchez earned her BS degree in computer engineering from the Instituto Tecnológico de Cerro Azul in 2000, her MSc degree in computer science from CENIDET in 2004, and her PhD degree in computer science from CENIDET in 2010. She is a full-time professor at the Universidad Autónoma de Ciudad Juárez. Her fields of interest include neurosymbolic hybrid systems, digital image processing, artificial neural networks, and augmented reality.

Humberto de J. Ochoa Domínguez, Osslan O. Vergara Villegas, Vianey G. Cruz Sanchez, "Modified set partitioning in hierarchical trees algorithm based on hierarchical subbands," Journal of Electronic Imaging 24(3), 033004 (8 May 2015). http://dx.doi.org/10.1117/1.JEI.24.3.033004
Submission: Received ; Accepted
JOURNAL ARTICLE
12 PAGES


SHARE
KEYWORDS
Lithium

Image compression

Laser induced plasma spectroscopy

Computer programming

Visualization

Discrete wavelet transforms

Inspection

RELATED CONTENT

Reduced-memory-zerotree-envelop-coding-for-wavelet-image
Proceedings of SPIE (November 15 2007)
Fast-algorithm-of-byte-to-byte-wavelet-transform-for-image...
Proceedings of SPIE (November 27 2002)
Meitei-coding-for-subband-image-compression
Proceedings of SPIE (January 28 2004)
Wavelet-TCQ-submission-to-JPEG-2000...
Proceedings of SPIE (October 01 1998)
Visual-progressive-coding
Proceedings of SPIE (December 28 1998)
Wavelet-based-image-compression-using-subband-threshold
Proceedings of SPIE (November 21 2002)

Back to Top