International Journal of Applied Engineering Research, ISSN 0973-4562 Vol.10 No.70 (2015) © Research India Publications; httpwww.ripublication.comijaer.htm
A Novel Technique for Multi-Spectral Image Compression Using SPIHT Algorithm R. Kavin Rajesh, PG Student, St. Joseph’s College of Engineering, Old Mahabalipuram Road, Chennai, India.
[email protected]
C.Heltin Genitha, Associate Professor, St. Joseph’s College of Engineering, Old Mahabalipuram Road, Chennai, India.
[email protected]
Abstract- In this paper, we have proposed a novel image compression technique to compress the multi-spectral satellite images. Here, Discrete Wavelet Transform (DWT), Set Partitioning in Hierarchical Tree (SPIHT) and Huffman coding techniques are used to compress the multi-spectral images. Wavelets allow complex information such as images and patterns to be decomposed into elementary forms at different positions and scales; and subsequently reconstructed with high precision. SPIHT is an intensive progressive capability, and it can interrupt the decoding (or coding) at any time and a result of maximum possible detail can be reconstructed with one-bit precision. Huffman coding is based on the frequency of occurence of a data item (pixel in images) and the principle is to use a lower number of bits to encode the data that occurs more frequently. Experiments are carried with the multi-spectral IKONOS satellite imagery and the results showed that there is an increase in compression ratio and less loss of 0.3dB in PSNR. Keywords: Discrete Wavelet Transform, Set Partitioning in Hierarchical Tree, Huffman coding, Multi-spectral images. I. INTRODUCTION
The current trend of airborne sensors is towards an increase in spatial resolution, spectral channels, and radiometric calibration accuracy, leading to a larger image size. It will greatly increase the computer processing requirements for image analysis and processing. In addition, since multi-spectral images are collected on remote acquisition platforms such as satellites and aircrafts, the transmission of such data to remote reception sites can be a critical issue. Thus, compression schemes oriented to the task of remote transmission are becoming increasingly of interest in multi-spectral applications. A number of approaches have been proposed for compressing multi-spectral images in recent years. These approaches can be grouped into predictive coding, vector quantization and transform-based coding [7]. The most popular method is predictive coding because of its superior lossless performance. Predictive coding requires complicated calculations and relies on sided information to implement the sophisticated predictors that produce the optimal differences between predicted and actual values. However, the high complexity of the optimal coding method might not be feasible onboard. On the contrary, the transform-based coding compresses a transformed image without requiring any prior information and complicated mathematics. In addition, transform-based coding is more efficient and simpler because of the useful properties of energy compaction and decorrelated data in the transformed image. Overall, transform-based coding is a good candidate for onboard muti-spectral data. Thus, in the proposed work, a transform based coding algorithm called Set Partitioning in Hierarchical Trees was implemented for multi-spectral satellite image compression. The following section explains about remote sensing applications and its challenges toward image compression. A. Remote Sensing Remote sensing is the science of deriving information about the earth’s surface from a great distance using optical sensors without physical contact with the object. Landsat program was initiated for the study of the Earth’s surface and resources. Its space-based sensor, called a multispectral scanner (MSS), allowed it to acquire four-band multispectral imagery on agricultural and forestry resources, geology and mineral resources, hydrology and water resources, geography and marine resources, and meteorological phenomena. The IKONOS imagery is suitable for applications requiring a high level of detail and accuracy, such as mapping, and urban planning. B. Need for Multi-Spectral Image Compression The processing of the images, called spectral analysis, allows for the identification of the specific mineralogical and agricultural elements which compose an image. This work explains the advantages and details specific to processing in order to maximize the ability of compression algorithms and to operate on the image with minimal loss in image utility. It also 298
International Journal of Applied Engineering Research, ISSN 0973-4562 Vol.10 No.70 (2015) © Research India Publications; httpwww.ripublication.comijaer.htm
presents new challenges to image analysts, to deal with its enormous data volume effectively while still achieving their desired goals. C. Previous Work In [1], an adequate multi-resolution analysis with the Lifting-Scheme framework was discussed for image compression. Then, it is compared with the classical wavelet transform within both multi-2D and full-3D compression strategies. The two strategies are combined with a PCA decorrelation stage to optimize the performance. The results showed that it achieves better compression ratios for images with higher dimensions. However, the complexity of this technique is more when compared to other techniques. Compression of remote-sensing images can be necessary for on-board a satellite before transmission to the ground station. Although on-board CPU power is quite limited, it is now possible to implement sophisticated real-time compression techniques, provided that complexity constraints are taken into account at design time. In [2], compression of multispectral images by spectral classification and transform coding is discussed. In addition to that a technique was developed to allow its use in real time with limited hardware resources. Experiments are carried out on several multispectral images show that the resulting unsupervised coder has a fully acceptable complexity, and a rate– distortion performance which is superior to that of the original supervised coder. However, it must be pointed out that results would be less striking with other applications or segmentation techniques, but spectral clustering is probably the single most frequent processing step used in the analysis of such images. The existing image compression algorithms have the problem of high time-space complexity and inadequate usage of spectral characteristics. To overcome this problem, an inter-spectrum sparse equivalent representation of multispectral image and its clustering realization ways were studied [3]. In addition, a new multispectral image compression algorithm based on spectral adaptive clustering and wavelet transform was designed. The affinity propagation clustering was utilized to generate inter-spectrum sparse equivalent representation which can remove inter-spectrum redundancy under low complexity, twodimensional wavelet transform was used to remove spatial redundancy, and set partitioning in hierarchical trees (SPIHT) was used to encode. The quality of reconstructed images was improved by error compensation mechanism [3]. Experimental results show that it achieves good performance in time-space complexity, the peak signal-to-noise ratio (PSNR) is significantly higher than that of similar compression algorithms under the same compression ratio, and it is a generic and effective algorithm. However, this algorithm cannot be applied for images with different dimensions. In [4], a novel segmentation technique is proposed for multispectral satellite image compression. A segmentation decision rule composed of the principal eigenvectors of the image correlation matrix is derived to determine the similarity of image characteristics of two image blocks. Based on the decision rule, eigen region-based segmentation technique is developed. The segmentation technique divided the original image into some eigen regions according to their local terrain characteristics. To achieve better compression efficiency, each eigen region image is then compressed by an efficient compression algorithm, eigen region-based eigen subspace transform (ER-EST). Before performing EST, the dimension of transformation matrix of EST is estimated by an information criterion. Simulation tests are performed on SPOT and Landsat TM images and it is suitable for multispectral satellite image [4]. In [5], the authors carried out low bit-rate compression of multispectral images by means of the Said and Pearlman's SPIHT algorithm, suitably modified to taken into account the interband dependencies [5]. Two techniques are proposed: in the first, a three-dimensional (3D) transform is taken (wavelet in the spatial domain, Karhunen-Loeve in the spectral domain) and a simple 3D SPIHT is used; in the second, after taking a spatial wavelet transform, spectral vectors of pixels are vector quantized and a gain-driven SPIHT is used. Numerous experiments on two sample multispectral images show very good performance for both algorithms [5].
In [6], the authors presented a hybrid difference pulse code modulation (DPCM) and wavelet transform (WT) approach to lossy compression of multi-spectral remotely sensed images. First, the Karhunen-Loeve Transform removes the interband correlation to produce the principal components of the multispectral images. Each component is decomposed in to 16 subbands by the wavelet transform using the uniform subband decomposition. Then, the lowest-fequency subband is coded with the lossless DPCM, and all other subbands coded is designed for each subband. The experimental results showed that it provides a low bit-rate and high quality of the reconstructed image. II. METHODOLOGY
The block diagram of the compression algorithm is shown in Figure 1. In this work, the multispectral image is given as input to wavelet transform block. Wavelet compression is a form of data compression well suited for image compression (sometimes also video compression and audio compression). The goal is to store image data in as little space as possible in a file. A wavelet series is a representation of a function by certain orthonormal series generated by a wavelet. Nowadays, wavelet transformation is one of the most popular candidates of the time-frequency-transformations. Then, the output of the wavelet transform is give as input to SPIHT algorithm and it is encoded using Huffman coding. 299
International Journal of Applied Engineering Research, ISSN 0973-4562 Vol.10 No.70 (2015) © Research India Publications; httpwww.ripublication.comijaer.htm
Input Image
Wavelet Transform
SPIHT
Huffman Encoding Bit Stream
Reconstructed image Inverse Wavelet Transform
SPIHT Decoding
Fig.1. Block diagram of compression algorithm The SPIHT (Set Partitioning in Hierarchical Trees) algorithm can perform better at higher compression ratios for a wide variety of images [8]. The algorithm uses a partitioning of the trees in a manner that tends to keep insignificant coefficients together in larger subsets. At this step, the compressed multi-spectral image is generated. In the decompression step, the reverse of the compression stages are performed. That is, the bit stream of compressed image is given as input to SPIHT decoding block. Then, the inverse wavelet transform is performed. Thus, the reconstructed or decompressed image is generated with minimum compression error .The performance of the algorithm is evaluated by comparing the original image with the reconstructed image. The performance is also evaluated quantitatively using the size of the compressed multi-spectral images. III. WAVELET TRANSFORM
Wavelet analysis is an exciting new method for solving difficult problem in image processing, pattern recognition, computer graphics. Wavelets allow complex information such as images and patterns to be decomposed into elementary forms at different positions and scales and subsequently reconstructed with high precision. The Fourier transform is an useful tool to analyze the frequency components of the signal. However, the length of window limits the resolution in frequency. Wavelet transform seems to be a solution to the above problem. Wavelet transforms are based on small wavelets with limited duration. The DWT (Discrete Wavelet Transform) of a signal x is calculated by passing it through a series of filters. First the samples are passed through a low pass filter with impulse response resulting in a convolution of the two. The signal is also decomposed simultaneously using a high-pass filter h. The filter outputs are then sub sampled. This decomposition has halved the time resolution since only half of each filter output characterizes the signal. However, each output has half the frequency band of the input so the frequency resolution has been doubled. This decomposition is repeated to further increase the frequency resolution and the approximation coefficients decomposed with high and low pass filters and then downsampled. This is represented as a binary tree with nodes representing a sub-space with different time-frequency localization. The tree is known as a filter. The scaled-version wavelets allow to analyze the signal in different scale. Wavelets as a family of functions constructed from translations and dilations of a single function called the "mother wavelet" ψ(t). They are defined by
(1) The parameter ‘a’ is the scaling parameter or scale, and it measures the degree of compression. The parameter ‘b’ is the translation parameter which determines the time location of the wavelet. If |a| < 1, then the wavelet in (1) is the compressed version of the mother wavelet and corresponds mainly to higher frequencies. On the other hand, when |a| > 1, then has a larger time-width than ψ and corresponds to lower frequencies. Thus, wavelets have time-widths adapted to their frequencies. Using a wavelet transform, the wavelet compression methods are adequate for representing transients, such as percussion sounds in audio, or high-frequency components in two-dimensional images. This means that the transient elements of a data signal can be represented by a smaller amount of information than would be the case if some other transform, such as the more widespread discrete cosine transform, had been used.
300
International Journal of Applied Engineering Research, ISSN 0973-4562 Vol.10 No.70 (2015) © Research India Publications; httpwww.ripublication.comijaer.htm IV. SPIHT ALGORITHM
SPIHT uses three lists – the List of Significant Pixels (LSP), List of Insignificant Pixels (LIP) and List of Insignificant Sets (LIS). These are coefficient location lists that contain the coordinates. The explanation of the SPIHT algorithm [8] is shown in Table 1. Table 1. SPIHT Algorithm 1) Initialization: i. Output n=[log2max{│ C(i,j)│}]; ii. Set LSP= Ø ; iii. Set LIP= (i,j) H; iv. Set LIS=(i,j) H, where D(i,j) ≠ Ø and set each entry in LIS as type A; 2) Sorting Pass: i. for each entry (i, j) in the LIP do: output Sn(i, j), if Sn(i, j)=1 then move (i, j) to the LSP, and output the sign of c(i,j). ii. for each entry (i, j) in the LIS do: if the entry is of type A then output Sn(D(i, j)), if Sn(D(i, j)) = 1 then for each (k,l) O(i, j) do: output Sn(k, l), if Sn(k, l) = 1 then add (k,l) to the LSP, output the sign of c(k,l) , if Sn(k,l)=0 then add (k, l) to the end of the LIP, if L(i, j)!= 0 then move (i, j) to the end of the LIS, as an entry of type B, go to Step (iii). Otherwise remove entry (i, j) from the LIS, iii. if the entry is of type B output Sn(L(i, j)), if Sn(L(i, j)) = 1 then add each hm to the end of the LIS as an entry of type A, remove (i,j) from the LSP, 3) Refinement Pass: For each entry (i, j) in the LSP, except those included in the last sorting pass, output the nth most significant bit of | ci,j |; 4) Quantization Pass: Decrement n by 1 and go to Step 2. After the initialization, the algorithm takes two stages for each level of threshold – the sorting pass (in which lists are organized) and the refinement pass (which does the actual progressive coding transmission). The result is in the form of a bitstream. SPIHT algorithm is an intensive progressive capability – it can interrupt the decoding (or coding) at any time and a result of maximum possible detail can be reconstructed with one-bit precision [8]. This is very desirable when transmitting files over the internet, since users with slower connection speeds can download only a small part of the file, obtaining much more usable result when compared to other codec such as progressive JPEG. Second advantage is a very compact output bit stream with large bit variability – no additional entropy coding or scrambling has to be applied. It is also possible to insert a watermarking scheme into the SPIHT coding domain and this watermarking technique is considered to be very strong regarding to watermark invisibility and attack resiliency. V. HUFFMAN ENCODING
Huffman coding is based on the frequency of occurance of a data item (pixel in images). The principle is to use a lower number of bits to encode the data that occurs more frequently. Codes are stored in a code book which may be constructed for each image or a set of images. In all cases the code book plus encoded data must be transmitted to enable decoding. 301
International Journal of Applied Engineering Research, ISSN 0973-4562 Vol.10 No.70 (2015) © Research India Publications; httpwww.ripublication.comijaer.htm VI. RESULTS AND DISCUSSION
The performance of this work is evaluated by Peak signal-to-noise ratio. It is the ratio between the maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation. PSNR is most commonly used to measure the quality of reconstruction of lossy compression. The signal in this case is the original data, and the noise is the error introduced by compression. When comparing compression codecs, PSNR is an approximation to human perception of reconstruction quality. Although a higher PSNR generally indicates that the reconstruction is of higher quality. Compressing an image is significantly different than compressing raw binary data. The general purpose compression programs can be used to compress images, but the result is less than optimal. This is because images have certain statistical properties which can be exploited by encoders specifically designed for them. Also, some of the finer details in the image can be sacrificed for the sake of saving a little more bandwidth or storage space. The design criterion used to develop a compression technique and the performance criterion used to evaluate the effectiveness of a specified compression technique in performance. While these two types of criteria are considered as separate criteria, they are generally correlated to each other. Specifically, a performance criterion is always a major driving force to determine what design criterion should be selected to design a desired compression. The original multispectral image for image compression is shown in Figure 2. This IKONOS multi-spectral image is given as input to wavelet transform, and then to SPIHT algorithm. The output from the SPIHT is the compressed image. This compressed image is once again compressed using Huffman coding algorithm and the bitstreams are generated. The IKONOS multispectral image after compression is shown in Figure 3.
. Fig 2. Original IKONOS image for compression
Fig 3. Compressed IKONOS image
302
International Journal of Applied Engineering Research, ISSN 0973-4562 Vol.10 No.70 (2015) © Research India Publications; httpwww.ripublication.comijaer.htm
The output of the SPIHT decoding stage is given as input to inverse wavelet transform stage. The inverse wavelet transform is the inverse operation of wavelet transform which is done at the first stage of this compression operation. Finally, the reconstructed hyperspectral image is generated. The reconstructed multispectral IKONOS image is shown the Figure 4. Experiments are carried with the multi-spectral IKONOS satellite imagery and the results showed that there is an increase in compression ratio and less loss of 0.3dB in PSNR.
Fig 5. Reconstructed IKONOS image VII. CONCLUSION
In this work, the multi spectral image is compressed using the wavelet transform, SPIHT algorithm and Huffman coding. In addition, the original image is reconstructed using the inverse operation, which is performed during the image compression stage. Performance is evaluated by comparing the reconstructed image with the original image. Here, a better performance is achieved by implementing the novel SPIHT algorithm for image compression. In future, the hyperspectral image with multiple band will be used for image compression. Moreover, the SPIHT algorithm has its disadvantages. That is, SPIHT is very vulnerable to bit corruption, as a single bit error can introduce significant image distortion depending of its location. SPIHT also offers several possibilities for processing color information and can marginally be found in digital video or 3D image processing. Thus, in the future work, an improved algorithm will be formulated for multi-spectral as well as hyperspectral image compression. REFERENCE [1]Jonathan Delcourt, Alamin Mansouri, Tadeusz Sliwa, Yvon Voisin, (2010), ” An Adaptive Multiresolution-Based Multispectral Image Compression Method”, International Journal of Future Generation Communication and Networking, 3(4), pp. 1-10. [2]Marco Cagnazzo, Luca Cicala, Giovanni Poggi, Luisa Verdoliva, (2006), “Low-complexity compression of multi-spectral images based on classified transform coding ”, Signal Processing: Image Communication, 21, pp. 850–861. [3]Liang W, Zeng P, Zhang H, Luo XM, (2013), “Multispectral image compression algorithm based on clustering and wavelet transform”, US National Library of Medicine National Institutes of Health, 33(10), pp. 2740-2741. [4]Lena Chang, “Multispectral image compression using eigenregion-based segmentation”, Pattern Recognition Vol. 37, No. 6, pp. 1233–1243, 2004. [5]Dragotti, P.L., Poggi, G., Ragozini, A.R.P., (2000), “Compression of multispectral images by three-dimensional SPIHT algorithm” IEEE Transactions on Geoscience and Remote Sensing, 38(1), pp. 416-428. [6]Chairat Rittirong, Yuttapong Rangsanseri, and Punya Thitimajshima, (1999), “Multispectral Image Compression using Median Predictive Coding and Wavelet Transform”, ACRS. [7]B. Aiazzi, P. Alba, L. Alparone and S. Baronti, (1999), "Lossless compression of multi/hyper-spectral imagery based on a 3-D fuzzy prediction", IEEE Transactions on Geoscience and Remote Sensing,37(37), pp. 2287-2294. [8]Vidhi Dubey, Rahul Dubey (2013), “A new Set Partitioning in Hierarchical (SPIHT) Algorithm and Analysis with Wavelet Filters”, International Journal of Innovative Technology and Exploring Engineering, 3(3), pp. 125-128.
303
