Abstract: In this study, we present an algorithm of SPIHT to compress an image using various wavelet filters by way of bior 4.4, Coif1, Daubechies families, Sym 3 and rbio 4.4. Compression methods are important in telemedicine applications to amply represent an image by decreasing the amount of bits per pixel. Data storage requirements are reduced and transmission efficiency is improved because of compressing the image. This algorithm is real and computationally efficient in case of coding an image. In recent years, a technique to decompose an image using wavelets has obtained a big deal of reputation. Apart from the performance of good compression, we may obtain good quality of image even if truncation of bit stream happened at any point of time. All the standard filters of wavelet are used and the results are compared with two different images (Lena and lifting body) in the encoding section. Bit rate versus PSNR simulation results are tabulated with different wavelet filters. Finally Bi-orthogonal (bior 4.4) filter of wavelet family given better results.
INTRODUCTION
A simple notion of compressing an image is try to represent an image sufficiently by decreasing amount of bits per pixel. This compression of an image is immediately required in case of large medical/satellite images, together for decreasing the requirement of storage and for increasing efficiency of transmission. Other main applications of image compression are multimedia databases, digital still cameras, printers and scanners etc. Since there is a raising ultimatum for multimedia applications, an effective scalable image and audio-visual compression techniques are mandatory.
A progressive image transmission is supported by the embedded coding. The coding of a given image at a definite bitrate by an entrenched way accumulates entire codes of low rate by the side of the starting stream of bits. Normally encoding process can be stopped either in advance or when a target bit rate is come across. In the same way, at any instant in a stream of bits, the decoder disturbs the process of decoding and can reconstruct images of any lesser rate (Munteanu et al., 1999). In case of images, the term scalability is normally obtained by means of progressive transmission based on coding of multi resolution. Numerous state-of-the-art coders of multi resolution images are building based on the notions bring together by Shapiro (1993).
Multi resolutionAnalysis is the design method of most of the practically relevant DWTs. A two dimensional DWT process is applied to an image proceeding a tile-by-tile basis for sub band coding. For different directions and resolution levels, different wavelet filters are used (Venkateswaran and Rao, 2007). Although the convolutions in the DWT can still be calculated competently on data of blocks, dividing of an image is not essential in wavelet coding. So, the advantage is that the distinctive obstructive errors, similar to ones happening in JPEG, are eluded.
Generally the ringing errors are lower than JPEG blocking errors, at high compression ratios. Recently several waveletbased new algorithms for image compression have been implemented. The practical advances due to these methods yielded such as: compression of constant-tone compression, dual mode compression, resolution and pixel accuracy transmission in a progressive way, ROI coding, low bit rate superior performance others. SPIHT algorithm (Ding and Yang, 2008) is a best technique that fulfils the above objectives. This algorithm signifies a stage on the way to understanding fewer budgets in regard to estimation and difficulty of compression, such as planned in JPEG and JPEG 2000, to obtain greater firmness results (Pennebaker and Mitchell, 1992; Adams, 2002; Taubman, 2000).
METHODOLOGY SUBBAND CODING
A filter bank system of analysis and synthesis for Digital Signal Processing (DSP) has been developed by the principle of splitting a discrete time signal into a number of sub band signals into final output signal.
| Fig. 1: | Sub band coding using QMF |
A QMF (Quadrature Mirror Filter) of two channels can be used as sub band coder/decoder (codec) as shown in Fig. 1. A two-band analysis filter bank comprising a LPF and HPF through which a input signal is passed. The sub band signals are decimated (down sampled) by a factor 2. Since the frequency range at the filter output is lower than the frequency range at the filter input, we can decrease the samples number at the filter output (Sayood, 2000). Based on an energy level and perceptual importance, each decimated sub band signal is encoded/quantized. Filtering and sub-sampling is termed as analysis stage. The decoded sub bands are interpolated (up sampled) to achieve the reconstruction and appropriate synthesis filters are applied to produce the final output signal which is so called synthesis stage. The filters in a filter bank can be impulse response of Finite (FIR) or infinite (IIR). Finite impulse response filters are generally used in most applications because of their design simplicity and better stability. Sub bands formulation itself does not create any image compression. But the sub bands can be encoded more efficiently than the source image (Logashanmugam and Ramachandran, 2008). This process can be repeatedly used to obtain a larger number of bands. The 2 D-DWT can be applied to an image to the rows and columns. The procedure (Li and Drew, 2004) for the two-dimensional DWT for an N by N input image is:
| • | Convolve each row of the image with analysis filters; remove the obtaining arrays of odd-numbered columns and combining them to make a transformed row |
| • | Convolve each column of the result with analysis filters, again remove the odd-numbered rows and concatenate the result |
Figure 2 shows that the one level and two levels transform discrete wavelet transform to an image.
| Fig. 2 (a-b): | Two-dimensional DWT, (a) One-level transform and (b)Two-level transform |
SPIHT algorithm: This is a one of the best image compression algorithm. It uses a sub band coder which comprises of a powerful complementary high pass and low pass filters, this finally yields a pyramid structure. So finally it generates four sub levels (Antonini et al.,1992) namely LL, LH, HL and HH. Then the yielded LL sub level is once more operated as the same previous manner depending on levels as shown in Fig. 2.
| • | H(p,q): Complete tree roots coordinates set at the peak level of the pyramid |
| • | D(p,q): All descendants coordinates set (p,q) |
| • | O(p,q): The off-spring coordinates set (p,q) |
| • | L(p,q) = D(p,q)-O(p,q) |
Step 1: Initialization: First consider all elements in H as significant pixels list. Initially significant pixels list should be empty. Consider all roots of descendants as insignificant sets list, then Compute’t’ value as log2(max|coeff|).
Step 2: Sorting pass (significance map encoding) Process LIP (list of insignificant pixels): Calculate “St” value to all coefficients in insignificant pixels list as:
Where:
If “St” value is 1, then assign sign of corresponding coefficient as ‘+’ (significant)/ ’-‘ (insignificant). Then shift that coefficient to the significant pixels list. Continue this procedure to all the coefficients.
Process LIS (list of insignificant sets): Consider every set in the insignificant sets list, if it is comes under all Descendants coordinates set type then find “St” value. If “St” = 1, then for each set belongs to offspring’s coordinates sets find “St” value.
If “St” = 1, then move that pixel to the Significant pixel lists and assign sign of corresponding coefficient as ‘+’ (significant)/’-‘(insignificant).
If “St” = 0, at that moment transfer that pixel to the last place of insignificant pixels list.
Else, if it is comes under all descendants except the offspring type, find “St” value. If “St” = 1 then move every pixel belongs to offspring’s coordinates sets to the end of the Insignificant sets list as an entry of all descendants coordinates set type. Then eliminate that pixel from the insignificant sets list. Continue the same procedure until the same type and also up to the completion of insignificant sets list.
Step 3: Refinement pass process LSP (list of significant pixels): Consider every set in the significant pixels list except the pixels just came in above process then output the coefficient of tth MSB. So end the process whenever LSP is over.
Step 4: Update: Now ‘t’ value should be decreased by 1, then move to step 2.
So, in this obtained pyramid structure there occurs a robust spatial relationship between the top of the pyramid wavelet coefficients with their children. This algorithm continuously searching for significant pixels throughout the pyramid and stores this information in the form of 3 different lists. They are significant pixels list, insignificant pixels list and insignificant sets list. In a pyramid structure, a wavelet coefficient at location (p,q) has four descendants of direct mode (off springs) at locations:
| (1) |
This arrangement is generally termed as spatial Positioning tree. The Resemblance Surrounded by sub bands within the levels of a wavelet region is shown in Fig. 3. If any coefficient at a position (p,q) has a preferable magnitude then few of their descendants may be considerable. So, this uses an algorithm of binary search to find the wavelet coefficients of significant type.
| Fig. 3: | Pyramid structural off-spring dependencies |
Features of SPIHT algorithm: At any time, the compression algorithm can be stopped and an approximate of the original image can be obtained at the decoder section. According to the incoming bit stream, the same algorithm can be run at the decoder to reconstruct the coefficients. It has the advantages of lower bandwidth and algorithm simplicity. This technique provides a very good compression performance results. For this performance it doesn’t requires any training and any code books. There is no need of any prior knowledge of image source. This method is well organized, fully embedded, rate control in an accurate manner, self-adaptive, fast and simple.
Calculation of MSE and PSNR: The two performance metrics used to evaluate the MSE and PSNR are x and x’, then MSE is defined by:
| (2) |
where, x [n1, n2], x’ [n1, n2] are the original and reconstructed images correspondingly and N1 and N2 are the dimensions of the image and the PSNR is defined by:
| (3) |
SIMULATION RESULTS
Wavelet families can be classified into two main categories, orthogonal and bi -orthogonal wavelets. Each set have the different properties of basic functions. The redundancy can be minimized by the orthogonality which decorrelates the transform coefficients. The symmetry property achieves the linear phase and minimizes border errors. A compact support, regularity, symmetry and degree of smoothness are the other important properties of wavelet functions.
| Fig. 4(a-d): | Lena image, (a) Original image, (b) DWT 1st level image, (c) IDWT 1st level image and (d) Reconstructed image |
| Fig. 5(a-d): | Lifting body image, (a) Original image, (b) DWT 1st level image, (c) IDWT 1st level image and (d) Reconstructed image |
We provide the results using both orthogonal and biorthogonal wavelet filters for the 512X512 Lena image and Fig. 4. Lifting body image Fig. 5 using SPIHT algorithm by the bit rate of 0.35, 0.55 and 1 (Table 1, 2).
| Table 1: | Bitrate versus PSNR for the image ‘Lena512.bmp’ |
| Table 2: | Bitrate versus PSNR for the image ‘Lifting body 512.bmp’ |
CONCLUSION
Simulation Results show that ‘bior 4.4’ wavelet filter of wavelet family obtain a better PSNR result and correspondingly ‘dmey’, ‘Daubechies’ wavelet family, ‘sym3’, ‘coif1’, ‘rbio4.4’ obtain a better PSNR result. The ‘haar’ wavelet gives poor results. But an important property that the orthogonality which makes them energy preserving is useful for compression. So, finally the combination of birothogonal (bior 4.4) wavelet with SPIHT algorithm gives good reconstructed image with better results.