Regular Articles

Modified set partitioning in hierarchical trees algorithm based on hierarchical subbands

[+] Author Affiliations
Humberto de J. Ochoa Domínguez, Osslan O. Vergara Villegas, Vianey G. Cruz Sanchez

Universidad Autónoma de Ciudad Juárez, Signal Processing Group, Electrical and Computer Engineering Department, Av. del Charro 450 Norte, Ciudad Juárez, Chihuahua, 32310 México

J. Electron. Imaging. 24(3), 033004 (May 08, 2015). doi:10.1117/1.JEI.24.3.033004
History: Received November 7, 2014; Accepted April 14, 2015
Text Size: A A A

Open Access Open Access

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.

Figures in this Article

It has been proven that image compression algorithms based on the discrete wavelet transform (DWT) provide high coding efficiency for natural images.16 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.812 SPIHT-based image compression can achieve rate scalability and high coding performance.1320 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 property2326 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,2931 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.

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): Display Formula

Thmax=log2(max(i,j)χ{|cs(i,j)|}),(1)
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.

Graphic Jump Location
Fig. 1
F1 :

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

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.

Graphic Jump Location
Fig. 2
F2 :

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.

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): Display Formula

C=M×Nl=0L1122(Ll)k=13Il,k,(2)
Display Formula
Il,k={1,Thc>Thl,k0,otherwise,(3)
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 Display Formula
Il,k={ThmaxThl,k,Thc>Thl,k0,otherwise.(4)

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.

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): Display Formula

Il,k={1,ThcThl,k0,otherwise.(5)

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

Table Grahic Jump Location
Algorithm 1Modified SPIHT

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. Display Formula

Thl,k=log2(max(i,j)sl,k{|csl,k(i,j)|}),(6)
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): Display Formula

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

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. Display Formula

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

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): Display Formula

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

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.

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 (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.

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 Grahic Jump Location
Table 1Total number of comparison operations versus sorting passes for Lena, Barbara, and Mandrill.

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.

Graphic Jump Location
Fig. 3
F3 :

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

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 Grahic Jump Location
Table 2Bit rate versus number of sorting passes.

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.

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.

Graphic Jump Location
Fig. 4
F4 :

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.

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 Grahic Jump Location
Table 3Execution time comparison (in milliseconds).

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 Grahic Jump Location
Table 4Improvement in the speed of compression (in %) with respect to SPIHT.

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.

PSNR Results

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

PSNR=10log10(2552MSE)dB.(10)

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.

Graphic Jump Location
Fig. 5
F5 :

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.

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.

Graphic Jump Location
Fig. 6
F6 :

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.

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.

Graphic Jump Location
Fig. 7
F7 :

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.

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 Grahic Jump Location
Table 5Comparison of peak signal-to-noise ratio (in dB).
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 Grahic Jump Location
Table 6Structural similarity index measure.

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.

Antonini  M.  et al., “Image coding using the wavelet transform,” IEEE Trans. Image Process.. 1, , 205 –220 (1992). 1057-7149 CrossRef
Shapiro  J. M., “Embedded image coding using zerotrees of wavelet coefficients,” IEEE Trans. Signal Process.. 41, , 3445 –3462 (1993). 1053-587X CrossRef
Grgic  S., , Grgic  M., and Zovko-Cihlar  B., “Performance analysis of image compression using wavelets,” IEEE Trans. Ind. Electron.. 48, , 682 –695 (2001). 0278-0046 CrossRef
Grgic  S., , Kers  K., and Grgic  M., “Image compression using wavelets,” in  Proc. IEEE Int. Symp. on Industrial Electronics , pp. 99 –104 (1999).
Taubman  D. S., and Marcellin  M. W., JPEG2000: Image Compression: Fundamentals, Standards and Practice. ,  Kluwer Academic Publishers ,  Boston, Massachusetts  (2002).
Yang  S.  et al., “Evolutionary clustering based vector quantization and SPIHT coding for image compression,” Elsevier Pattern Recognit. Lett.. 31, , 1773 –1780 (2010). 0167-8655 CrossRef
Lee  T., and Shen  H., “Efficient local statistical analysis via integral histograms with discrete wavelet transform,” IEEE Trans. Vis. Comput. Graph.. 19, (12 ), 2693 –2702 (2013). 0018-9448 CrossRef
Cavero  E.  et al., “SPIHT-based echocardiogram compression: clinical evaluation and recommendations of use,” IEEE J. Biomed. Health Inform.. 17, (1 ), 103 –112 (2013).CrossRef
Xinjun  Z., and Xingyuan  W., “Chaos-based partial encryption of SPIHT coded color images,” Elsevier J. Signal Process.. 93, , 2422 –2431 (2013). 0165-1684 CrossRef
Ma  J., , Fei  J., and Chen  D., “Rate-distortion weighted SPIHT algorithm for interferometer data processing,” J. Syst. Eng. Electron.. 22, , 547 –556 (2011). 1004-4132 CrossRef
Christophe  E., , Mailhes  C., and Duhamel  P., “Hyperspectral image compression: adapting SPIHT and EZW to anisotropic 3-D wavelet coding,” IEEE Trans. Image Process.. 17, , 2334 –2346 (2008). 1057-7149 CrossRef
Manikandan  M. S., and Dandapat  S., “Effective quality-controlled SPIHT-based ECG coding strategy under noise environments,” Electron. Lett.. 44, , 1182 –1183 (2008). 0013-5194 CrossRef
Pearlman  W. A.  et al., “Efficient, low-complexity image coding with a set-partitioning embedded block coder,” IEEE Trans. CSVT. 14, , 1219 –1235 (2004). 1051-8215 CrossRef
Said  A., and Pearlman  W. A., “A new fast and efficient image codec based on set partitioning in hierarchical trees,” IEEE Trans. CSVT. 6, , 243 –250 (1996). 1051-8215 CrossRef
Yushin  C., and Pearlman  W. A., “Hierarchical dynamic range coding of wavelet subbands for fast and efficient image decompression,” IEEE Trans. Image Process.. 16, , 2005 –2015 (2007). 1057-7149 CrossRef
Chang  S., and Carin  L., “A modified SPIHT algorithm for image coding with a joint MSE and classification distortion measure,” IEEE Trans. Image Process.. 15, , 713 –725 (2006). 1057-7149 CrossRef
Ochoa  H.  et al., “Set Partitioning in hierarchical frequency bands (SPHFB),” in  Proc. of IEEE Data Compression Conf. , p. 463,  (2009).
Zhu  J., , Dansereau  R. M., and Cuhadar  A., “Error-resilient and error concealment 3-D SPIHT video coding with added redundancy,” Lec. Notes Comput. Sci.. 6134, , 351 –358 (2010). 0302-9743 CrossRef
Khelifi  F., , Bouridane  A., and Kurugollu  F., “On the SPIHT based multispectral image compression,” in  Proc. IEEE Int. Symp. on Signal Processing and Information Technology , pp. 359 –363 (2006).
Higgins  G.  et al., “Lossy compression of EEG signals using SPIHT,” IET Electron. Lett.. 47, , 1017 –1018 (2011). 0013-5194 CrossRef
Pan  H., , Siua  W., and Lawa  N., “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). 0923-5965 CrossRef
Fang  Z.  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).CrossRef
Jin  Y., , Lee  Y., and Lee  H.-J., “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).
Jin  Y., , Lee  Y., and Lee  H.-J., “A block-based pass-parallel SPIHT algorithm,” IEEE Trans. Circuits Syst. Video Technol.. 22, , 1064 –1075 (2012). 1051-8215 CrossRef
Zhu  J., and Dansereau  R., “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). 1051-8215 CrossRef
Xiang  T., , Qu  J., and Xiao  D., “Joint SPIHT compression and selective encryption,” Appl. Soft Comput.. 21, , 159 –170 (2014). 1568-4946 CrossRef
Rubio  O., , Alesanco  A., and Garcia  J., “Secure information embedding into 1D biomedical signals based on SPIHT,” J. Biomed. Inform.. 46, , 653 –664 (2013). 1532-0464 CrossRef
Isaa  S.  et al., “The effect of electrocardiogram signal compression using beat reordering and SPIHT on automatic sleep stage classification,” Eng. Procedia. 41, , 888 –896 (2012). 1877-7058 CrossRef
Nandi  A., and Banakar  R., “Throughput efficient parallel implementation of SPIHT algorithm,” in  Proc. of Int. Conf. on Very Large Scale Integrated Design , pp. 718 –725 (2008).
Zhang  N.  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).
Sudhakar  R., and Jayaraman  S., “A new video coder using multiwavelets,” in  Proc. of Int. Conf. on Signal Processing, Communications and Networking , pp. 259 –264 (2007).
“The USC—SIPI image database,” http://sipi.usc.edu/database/ ( February  2013).
Cohen  A., , Daubechies  I., and Feauveau  J. C., “Biorthogonal bases of compactly supported wavelets,” Commun. Pure Appl. Math.. 45, , 485 –560 (1992). 0010-3640 CrossRef
Said  A., and Pearlman  W. A., “SPIHT program,” http://www.cipr.rpi.edu/research/SPIHT/spiht3.html#mat-spiht ( January  2013).
Wang  Z.  et al., “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process.. 13, , 600 –612 (2004). 1057-7149 CrossRef

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.

© The Authors. Published by SPIE under a Creative Commons Attribution 3.0 Unported License. Distribution or reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.

Citation

Humberto de J. Ochoa Domínguez ; Osslan O. Vergara Villegas and Vianey G. Cruz Sanchez
"Modified set partitioning in hierarchical trees algorithm based on hierarchical subbands", J. Electron. Imaging. 24(3), 033004 (May 08, 2015). ; http://dx.doi.org/10.1117/1.JEI.24.3.033004


Figures

Graphic Jump Location
Fig. 2
F2 :

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.

Graphic Jump Location
Fig. 1
F1 :

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

Graphic Jump Location
Fig. 6
F6 :

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.

Graphic Jump Location
Fig. 3
F3 :

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

Graphic Jump Location
Fig. 4
F4 :

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.

Graphic Jump Location
Fig. 7
F7 :

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.

Graphic Jump Location
Fig. 5
F5 :

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.

Tables

Table Grahic Jump Location
Algorithm 1Modified SPIHT
Table Grahic Jump Location
Table 2Bit rate versus number of sorting passes.
Table Grahic Jump Location
Table 1Total number of comparison operations versus sorting passes for Lena, Barbara, and Mandrill.
Table Grahic Jump Location
Table 3Execution time comparison (in milliseconds).
Table Grahic Jump Location
Table 4Improvement in the speed of compression (in %) with respect to SPIHT.
Table Grahic Jump Location
Table 5Comparison of peak signal-to-noise ratio (in dB).
Table Grahic Jump Location
Table 6Structural similarity index measure.

References

Antonini  M.  et al., “Image coding using the wavelet transform,” IEEE Trans. Image Process.. 1, , 205 –220 (1992). 1057-7149 CrossRef
Shapiro  J. M., “Embedded image coding using zerotrees of wavelet coefficients,” IEEE Trans. Signal Process.. 41, , 3445 –3462 (1993). 1053-587X CrossRef
Grgic  S., , Grgic  M., and Zovko-Cihlar  B., “Performance analysis of image compression using wavelets,” IEEE Trans. Ind. Electron.. 48, , 682 –695 (2001). 0278-0046 CrossRef
Grgic  S., , Kers  K., and Grgic  M., “Image compression using wavelets,” in  Proc. IEEE Int. Symp. on Industrial Electronics , pp. 99 –104 (1999).
Taubman  D. S., and Marcellin  M. W., JPEG2000: Image Compression: Fundamentals, Standards and Practice. ,  Kluwer Academic Publishers ,  Boston, Massachusetts  (2002).
Yang  S.  et al., “Evolutionary clustering based vector quantization and SPIHT coding for image compression,” Elsevier Pattern Recognit. Lett.. 31, , 1773 –1780 (2010). 0167-8655 CrossRef
Lee  T., and Shen  H., “Efficient local statistical analysis via integral histograms with discrete wavelet transform,” IEEE Trans. Vis. Comput. Graph.. 19, (12 ), 2693 –2702 (2013). 0018-9448 CrossRef
Cavero  E.  et al., “SPIHT-based echocardiogram compression: clinical evaluation and recommendations of use,” IEEE J. Biomed. Health Inform.. 17, (1 ), 103 –112 (2013).CrossRef
Xinjun  Z., and Xingyuan  W., “Chaos-based partial encryption of SPIHT coded color images,” Elsevier J. Signal Process.. 93, , 2422 –2431 (2013). 0165-1684 CrossRef
Ma  J., , Fei  J., and Chen  D., “Rate-distortion weighted SPIHT algorithm for interferometer data processing,” J. Syst. Eng. Electron.. 22, , 547 –556 (2011). 1004-4132 CrossRef
Christophe  E., , Mailhes  C., and Duhamel  P., “Hyperspectral image compression: adapting SPIHT and EZW to anisotropic 3-D wavelet coding,” IEEE Trans. Image Process.. 17, , 2334 –2346 (2008). 1057-7149 CrossRef
Manikandan  M. S., and Dandapat  S., “Effective quality-controlled SPIHT-based ECG coding strategy under noise environments,” Electron. Lett.. 44, , 1182 –1183 (2008). 0013-5194 CrossRef
Pearlman  W. A.  et al., “Efficient, low-complexity image coding with a set-partitioning embedded block coder,” IEEE Trans. CSVT. 14, , 1219 –1235 (2004). 1051-8215 CrossRef
Said  A., and Pearlman  W. A., “A new fast and efficient image codec based on set partitioning in hierarchical trees,” IEEE Trans. CSVT. 6, , 243 –250 (1996). 1051-8215 CrossRef
Yushin  C., and Pearlman  W. A., “Hierarchical dynamic range coding of wavelet subbands for fast and efficient image decompression,” IEEE Trans. Image Process.. 16, , 2005 –2015 (2007). 1057-7149 CrossRef
Chang  S., and Carin  L., “A modified SPIHT algorithm for image coding with a joint MSE and classification distortion measure,” IEEE Trans. Image Process.. 15, , 713 –725 (2006). 1057-7149 CrossRef
Ochoa  H.  et al., “Set Partitioning in hierarchical frequency bands (SPHFB),” in  Proc. of IEEE Data Compression Conf. , p. 463,  (2009).
Zhu  J., , Dansereau  R. M., and Cuhadar  A., “Error-resilient and error concealment 3-D SPIHT video coding with added redundancy,” Lec. Notes Comput. Sci.. 6134, , 351 –358 (2010). 0302-9743 CrossRef
Khelifi  F., , Bouridane  A., and Kurugollu  F., “On the SPIHT based multispectral image compression,” in  Proc. IEEE Int. Symp. on Signal Processing and Information Technology , pp. 359 –363 (2006).
Higgins  G.  et al., “Lossy compression of EEG signals using SPIHT,” IET Electron. Lett.. 47, , 1017 –1018 (2011). 0013-5194 CrossRef
Pan  H., , Siua  W., and Lawa  N., “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). 0923-5965 CrossRef
Fang  Z.  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).CrossRef
Jin  Y., , Lee  Y., and Lee  H.-J., “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).
Jin  Y., , Lee  Y., and Lee  H.-J., “A block-based pass-parallel SPIHT algorithm,” IEEE Trans. Circuits Syst. Video Technol.. 22, , 1064 –1075 (2012). 1051-8215 CrossRef
Zhu  J., and Dansereau  R., “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). 1051-8215 CrossRef
Xiang  T., , Qu  J., and Xiao  D., “Joint SPIHT compression and selective encryption,” Appl. Soft Comput.. 21, , 159 –170 (2014). 1568-4946 CrossRef
Rubio  O., , Alesanco  A., and Garcia  J., “Secure information embedding into 1D biomedical signals based on SPIHT,” J. Biomed. Inform.. 46, , 653 –664 (2013). 1532-0464 CrossRef
Isaa  S.  et al., “The effect of electrocardiogram signal compression using beat reordering and SPIHT on automatic sleep stage classification,” Eng. Procedia. 41, , 888 –896 (2012). 1877-7058 CrossRef
Nandi  A., and Banakar  R., “Throughput efficient parallel implementation of SPIHT algorithm,” in  Proc. of Int. Conf. on Very Large Scale Integrated Design , pp. 718 –725 (2008).
Zhang  N.  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).
Sudhakar  R., and Jayaraman  S., “A new video coder using multiwavelets,” in  Proc. of Int. Conf. on Signal Processing, Communications and Networking , pp. 259 –264 (2007).
“The USC—SIPI image database,” http://sipi.usc.edu/database/ ( February  2013).
Cohen  A., , Daubechies  I., and Feauveau  J. C., “Biorthogonal bases of compactly supported wavelets,” Commun. Pure Appl. Math.. 45, , 485 –560 (1992). 0010-3640 CrossRef
Said  A., and Pearlman  W. A., “SPIHT program,” http://www.cipr.rpi.edu/research/SPIHT/spiht3.html#mat-spiht ( January  2013).
Wang  Z.  et al., “Image quality assessment: from error visibility to structural similarity,” IEEE Trans. Image Process.. 13, , 600 –612 (2004). 1057-7149 CrossRef

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.