LOW-COMPLEXITY LOSSLESS COMPRESSION OF HYPERSPECTRAL IMAGES USING SCALAR COSET CODES E. Baccaglini , M. Barni , L. Capobianco , A. Garzelli , E. Magli , F. Nencini , R. Vitulli Dip. di Elettronica - Politecnico di Torino Corso Duca degli Abruzzi 24 - 10129 Torino - Italy (enrico.baccaglini,enrico.magli)@polito.it Dip. di Ingegneria dell’Informazione - Universit`a di Siena Via Roma, 56 - 53100 Siena - Italy (barni,capobianco,garzelli,nencini)@dii.unisi.it On-Board Payload Data Processing Section European Space Agency - ESTEC TEC/EDP Noordwijk, The Netherlands
[email protected] ABSTRACT In this paper we propose a new algorithm for lossless compression of remote sensing images, based on distributed source coding. The objective of this algorithm is to achieve low-complexity encoding, with compression performance as close as possible to a full-complexity coder. The complexity reduction is obtained by coding each spectral channel separately, whereas high coding efficiency is achieved through joint decoding. Experimental results on hyperspectral images show that the proposed algorithm has significantly better performance than JPEG-LS, with similar complexity. We also provide profiling results on a LEON-3 architecture. 1. INTRODUCTION AND BACKGROUND In remote sensing systems, a major problem lies in the limited availability of bandwidth and energy for acquisition, processing and transmission of the images related to a given terrestrial area, as acquired by the sensors mounted on an airborne or spaceborne remote platform. Since the spatial, spectral and radiometric resolutions of optical sensors are getting finer and finer, the amount of collected data is huge. As an example, the AVIRIS hyperspectral sensor yields a three-dimensional image of 224 bands and 614 pixels, whose lines are acquired continuously along the aircraft flight path. New-generation sensors aim at increasing this resolution even further; for example, the NASA AIRS (Atmospheric Infrared Sounder) instrument provides an ultraspectral image with 2378 spectral channels. Because of the huge amount of data, powerful compression algorithms are required to match the available channel resources. For lossless compression, which is considered in this paper, predictive techniques are typically employed to exploit the correlation of the data, followed by entropy coding of the prediction error. The simplest algorithms, such as JPEG-LS [1] and CALIC [2], employ non-linear predictors that estimate the value of each This work has been sponsored by ESA-ESTEC under project 20035/06 “Distributed image coding for remote sensing applications”.
sample in a spectral channel based on the neighboring samples of the same channel; JPEG-LS is particularly interesting, because it achieves low-complexity through the use of Golomb-Rice coding, as opposed to the arithmetic coding used by CALIC. However, for hyperspectral data, the performance of these algorithms is not satisfactory, since the predictor does not exploit the correlation between different spectral channels. Instead, the strong spectral redundancy allows to effectively predict the information in a band from the other bands, which in the following we refer to as 3D decorrelation. In [3] it is shown that, for a scheme based on CALIC, the difference between the 2D and 3D decorrelation amounts to about 1.8 bit per pixel (bpp). In contrast, the constrained on-board computational and memory resources call for a low-complexity encoding technique; this makes it difficult to achieve the high compression ratio typical of 3D decorrelation. Distributed source coding (DSC) allows to develop compression algorithms with a low-complexity encoder, while most of the signal modeling is moved to the decoder. This structure is an excellent match to the remote sensing scenario, in which the on-board processing units have limited computational capabilities. In [4] it has been shown that DSC can be employed to achieve better performance than a purely 2D decorrelator. In particular, [4] proposed two DSC algorithms, one based on binary capacityachieving channel codes, and one on simple -ary scalar coset codes. Somewhat surprisingly, the best performance/complexity trade-off was provided by the latter scheme; however, the overall complexity was still significantly higher than JPEG-LS. In [5] hyperspectral images are compressed using a DSC-based algorithm in the wavelet domain, whose complexity is significantly higher than that of predictive lossless coders. This paper provides the following contributions. We give an information theoretic assessment of the application of DSC to hyperspectral data, which is improved with respect to the data in [4], as it considers the entropy of sources on 16 bits, as opposed to bit-planes. This justifies the better performance of a scalar -ary Slepian-Wolf coder as opposed to a vector binary coder. Moreover, we introduce a low-complexity version of the -ary DSC coder of [4], which does not incur any performance loss, and provide ex-
perimental results on hyperspectral AVIRIS data; low-complexity is achieved by identifying the most computationally demanding block, i.e. the cyclic redundancy check (CRC) code, and replacing it with a specific low-complexity CRC; this allows to reduce the computation time by almost a factor 2. Finally, we describe an implementation of the proposed algorithm on a simulator of a LEON-3 processor, for which space-qualified hardware is available. The algorithm proposed in this paper has been developed as part of a research activity sponsored by the European Space Agency (ESA-ESTEC) for innovative compression algorithms. 2. INFORMATION THEORETIC ASSESSMENT DSC amounts to encoding two (or more) correlated sources and without allowing them to communicate with each other; if and are two adjacent bands of a hyperspectral image, the lack of communication implies that spectral decorrelation is not peris formed. Slepian and Wolf proved [6] that the a rate achievable by separate encoding of and , provided that joint decoding of the two sources is performed. Particularly, if is encoded at rate , it is possible to losslessly compress at , although no information about the conditional rate is available during the encoding of . The encoding is typically performed using channel coding techniques, whereby the syndrome of , as opposed to a full description, is communicated to decode to the decoder, which exploits the side information . For remote sensing applications, we consider a compression scheme where each band of the hyperspectral dataset is encoded losslessly, and the decoder generates and uses a side inforcan generally be a function of the previous mation , where losslessly decoded bands . In order to limit the decoder memory requirements, we restrict ourselves to the case where the decoder only employs the previous band to generate the side information. Once we have a pair , we assume at a that S-W coding is ideal, i.e. that the encoder can compress rate exactly equal to , and that the decoder, given , can perfectly reconstruct . We consider binary S-W coders, which by bit-planes, as well as -ary coders, with code for hyperspectral data. Regarding the side information, we have considered the fol, and , where ad lowing cases: are taken in such as way that has the same mean value and standard deviation as , thereby minimizing the noise variance on the virtual channel. Results are reported in Tab. 1 for AVIRIS scenes with 512 lines, 614 pixels, and 224 bands (scene 1 of each image). The and refer to the binary and -ary S-W coders entropies respectively, and are averaged over all spectral channels. Note that all entropies for binary coders are higher than the entropy of the -ary coder. This is due to the fact that the binary coder neglects the correlation among different bit-planes, and hence requires a higher rate to encode the data. For the binary S-W coder, DSC can provide an average performance gain up to 1.8 bpp with respect to an -ary arithmetic coder. More interestingly, the -ary DSC coder has a significantly larger potential gain, up to 4.3 bpp. This clearly indicates that the most effective DSC strategy for these data is to employ an -ary coder, however simple, rather than a binary code. Note that the entropy of the -ary coder does not change when offset/gain compensation is carried out, because this is a memoryless reversible transformation.
Table 1. Entropy and conditional entropy on AVIRIS scenes, with different methods for generating the side information. Cuprite Moffett Jasper 9.53 9.51 9.91 8.36 8.18 8.61 8.09 8.65 8.98 4.05 4.22 4.47 6.47 6.62 7.13 4.05 4.22 4.47
We have also attempted to computing the entropy when more than one previous bands are used as side information, i.e. . This can be done only for small values of , because the computation time quickly becomes intractable. Moreover, only the entropy of a binary S-W coder can be computed, since there are not enough samples in each band to estimate the entropy of the M-ary coder. We have carried out this experiment on Cuprite. The entropy of the binary S-W coder is , as reported in Tab. 1. This decreases to 6.27 6.47 bpp with , and 6.22 bpp for . Hence, the potential gain bpp for is about 0.2-0.25 bpp. This is consistent with the gains achieved in [3] basing the prediction on two previous bands, and shows that a simple yet effective algorithm design should employ an -ary S-W coder that utilizes the previous band as side information, as more bands only provide a marginal gain. 3. PROPOSED ALGORITHM 3.1. Encoding The proposed algorithm is similar to the scheme described in [4]. We focus on two consecutive bands and , where is used as side information; the encoding is performed separately on each 16x16 block of pixels of . We assume that a model , permitfrom those of , is ting to predict the value of the pixels of available, i.e. the value of each pixel in can be written , where is a correlation as noise of known statistics, and is the value of the pixel in . In the proposed scheme, the value of all pixels in a block , is coded by retaining only the least significant bits of where is constant within a block, and its exact value depends on the correlation between the bands, i.e. on the statistics of ; this is equivalent to an -ary scalar coset code. The decoder will have to recover the MSBs on the basis of the side information . Specifically, it chooses the most significant bits so to minimize the distance between the reconstructed pixel value and the predicted . If the number of transmitted bits is chosen propvalue erly, no reconstruction loss is incurred. The structure of the algorithm is as follows. We first split into non-overlapping blocks of size ; then, for each block, and we compute a rough estimate of the maximum value of use it to select for that block. The compressed bitstream for each block contains , the least significant bits of all pixels in the block, and 32 parity-check bits obtained by applying a CRC code to the values of the pixels in the block. For selecting for each block, we observe that, because of the strong correlation, a linear prediction model based on the side information is likely to be a good predictor for the current block to be coded. In particular, let be the average value of the
block. The encoder considers a set of linear predictors leading , to a list of predicted values with , where is the average value of the corresponding block of . The parameter is determined as , where the pixels and are every fourth pixel on the left and upper borders of block . By denoting as x the vector containing all the values of the pixels in the block in raster order, the quantity is norm of the correlation noise taken as a rough estimate of the between the current block and the corresponding block in . This quantity is used to set the number of least significant bits to be retained as ; this is the minimum number of least significant bits to be transmitted for each pixel that ensures lossless recovery at the decoder. Since much of the encoder complexity resides in the CRC computation, it is extremely important to select a fast CRC implementation. However, the CRC must also have good error detection properties, in order to not hinder the decoding process. For example, fast non-CRC error detection codes such as the Internet checksum are not adequate because of the small minimum distance. In the proposed algorithm we have employed the fast implementation , of the 32-bit CRC with polynomial described in [7], which has an average complexity of 5.75 instructions per byte of data. An even faster implementation of this CRC exists, which uses 3.25 instructions/byte; however, the very large look-up table of this latter implementation is likely to make the performance slower than expected in a system where the data cache size is limited, as is the case of many on-board processing systems. 3.2. Decoding In order to exploit the side information to recover the most significant bits of , the decoder needs to know a model to predict the from those in , such that the predicvalues of the pixels in tion error at the decoder is not larger than the maximum prediction error estimated by the encoder. In particular, we use a predictor having the same form as the encoder. However, the decoder adof the current ditionally needs to estimate the average value in the first block, as well as the value of every fourth pixel row and in the first column; it does so by resorting to the pixels of spatially contiguous blocks that have already been decoded, as well as those belonging to the side information . Let us call and the average values of the blocks above and on the left of the current block, and and the corresponding values in the previous band. By assuming that the spatial correlation in is retained in , we use the following estimate for :
A similar expression is used to estimate the values of all the pixels of the first row and the first column of the block to be decoded. These estimates are used to define a set of predictors , which is taken similarly to the encoder, but includes a larger number of and predictors obtained by perturbing the estimated values of those of the border pixels, by adding a number of multiples of a given quantization step. All the candidate predicted values obtained by applying to are combined with the received least significant bits; this results
in a correct reconstruction of the current block if the condition is verified for all the pixels in the block. The decoder checks this by making sure that the CRC bits of the decoded block are equal to the received CRC bits of the original block. 4. RESULTS 4.1. Compression performance The compression performance of the proposed scheme has been compared with that of 2D-CALIC [2], 3D-CALIC [8], JPEG 2000 Part 1 [9], JPEG 2000 Part 2 with the reversible spectral wavelet transform performed on blocks of bands [10], and the CCSDSRice [11] employing the standard predictor and mapper. The results on AVIRIS scenes are reported in Tab. 2. As can be seen, CALIC performs better than JPEG-LS and JPEG 2000, and 3D-CALIC obtains the best performance overall. The proposed scheme outperforms JPEG-LS by more than 1.1 bpp, and 2D-CALIC by almost 1 bpp. However, the performance gap with respect to 3D-CALIC is almost 1 bpp, which is the price to be paid for using a simple scalar -ary S-W coder. For the same decorrelator dimensionality, JPEG 2000 has worse performance than JPEG-LS and CALIC; the CCSDS-Rice has even worse performance, as it employs a 1D decorrelator. Table 2. Coding efficiency of the proposed algorithm on AVIRIS scenes, compared to that of conventional 2D and 3D schemes. algorithm Cuprite Moffett Jasper Average JPEG-LS 6.90 7.65 7.61 7.39 2D-CALIC 6.76 7.56 7.49 7.27 3D-CALIC 5.13 5.23 5.14 5.17 JPEG2K (2D) 7.04 7.85 7.77 7.55 JPEG2K (3D, B=8) 6.06 6.57 6.48 6.37 JPEG2K (3D, B=12) 5.61 6.01 5.91 5.84 CCSDS-Rice 7.51 8.21 8.18 7.97 Proposed 6.10 6.35 6.25 6.23
4.2. Complexity The complexity of several algorithms is reported in Tab. 3, which shows the average running times per band, in milliseconds, measured on a Pentium IV workstation @ 2.5 GHz running Linux. As can be seen, the complexity of the proposed algorithm is very low, only about 60% larger than JPEG-LS. On the other hand, it is much smaller than that of CALIC, specifically about 28% of 2DCALIC and about 6% of 3D-CALIC. As a consequence, the proposed algorithm achieves a good trade-off between performance and complexity. Table 3. Average running AVIRIS scenes. algorithm Cuprite JPEG-LS 45.28 2D-CALIC 250.89 3D-CALIC 1351.74 Proposed 76.38
times per band (milliseconds) on Moffett 46.86 284.77 1315.75 77.63
Jasper 47.95 281.78 1344.73 76.74
Average 46.70 272.48 1337.40 76.92
5. PERFORMANCE EVALUATION ON LEON-3 The algorithm has been ported and tested on a LEON-3 simulator. The LEON3 is a synthesisable VHDL model of a 32-bit processor compliant with the SPARC V8 architecture. The model is highly configurable, and particularly suitable for system-on-a-chip (SOC) designs. A radiation-hardened version of LEON a processor has been developed by Atmel, and is expected to be the heart of future European spacecraft computers. Notable features of the LEON3 processor are a SPARC V8 instruction set with V8e extensions, an advanced 7-stage pipeline, hardware multiply, divide and MAC units, fully pipelined IEEE-754 floating-point unit, separate and configurable instruction and data cache, and symmetric multi-processor support. We used TSIM in order to simulate the performance of the proposed compression algorithm. TSIM is an instruction-level simulator capable of performing cycle-true emulation and profiling of LEON-based computer systems. TSIM was used to simulate a LEON-3 FPGA core, testing two clock frequencies of 50 and 150 MHz, with MAC support enabled. The cache size is 4+4 kBytes of instruction and data memory, with 16 bytes per line; 4 MBytes of RAM and 16 MBytes of SDRAM are available. Tests have been worked out in both presence and absence of a floating-point unit (FPU); in this latter case, floating-point instructions are simulated by the fixed-point processor. The compression algorithm has been tested on the Cuprite, Jasper and Moffett AVIRIS scenes. The original size is 224 bands, 512 lines, 614 pixel per line and 16 bps. We cropped sub-images of these data due to constraints on the on-board buffer size. In pixels (i.e., four particular, we encoded a sub-image of blocks as used by the algorithm) and considered bands (from band to band in order to avoid the water absorption bands). We evaluated performance in terms of encoding time on the target device. Table 4. Execution time (milliseconds) for a when an FPU is present and absent. Clock frequency FPU No FPU Cuprite 50 MHz 0.57 15.54 150 MHz 0.19 5.18 Jasper 50 MHz 0.57 15.43 150 MHz 0.19 5.14 Moffett 50 MHz 0.61 17.20 150 MHz 0.20 5.74
scene,
strategy consists in applying an -ary scalar S-W coder as entropy coding stage. Experimental results on AVIRIS scenes have shown that the proposed algorithm achieves a bit-rate 1.1 bpp smaller than JPEGLS, with a complexity about 60% higher, and 1 bpp smaller than 2D-CALIC, at about 28% of its complexity. The performance loss with respect to 3D-CALIC is about 1 bpp, which suggests that there is still room for improvement; however, the complexity of the proposed algorithm is about 17 times smaller than 3D-CALIC. This shows that this algorithm is suitable for on-board compression, as it allows to capture much of the spectral correlation with low encoding complexity. Tests on a LEON-3 simulator have shown that, at 150 MHz, the proposed algorithm yields a throughput of about 20000 blocks per second on an FPU equipped system, and 700 blocks per second without FPU, where each block has 50 bands. 7. REFERENCES [1] M.J. Weinberger, G. Seroussi, and G. Sapiro, “The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS,” IEEE Transactions on Image Processing, vol. 9, no. 8, pp. 1309–1324, Aug. 2000. [2] X. Wu and N. Memon, “Context-based, adaptive, lossless image coding,” IEEE Transactions on Communications, vol. 45, no. 4, pp. 437–444, Apr. 1997. [3] E.Magli, G.Olmo, and E.Quacchio, “Optimized onboard lossless and near-lossless compression of hyperspectral data using CALIC,” IEEE Geoscience and Remote Sensing Letters, vol. 1, no. 1, pp. 21–25, January 2004. [4] E. Magli, M. Barni, A. Abrardo, and M. Grangetto, “Distributed source coding techniques for lossless compression of hyperspectral images,” EURASIP Journal on Advances in Signal Processing, vol. 2007, 2007. [5] N.-M. Cheung, C. Tang, A. Ortega, and C.S. Raghavendra, “Efficient wavelet-based predictive Slepian-Wolf coding for hyperspectral imagery,” Signal Processing, vol. 86, no. 11, pp. 3180–3195, Nov. 2006. [6] D. Slepian and J.K. Wolf, “Noiseless coding of correlated information sources,” IEEE Transactions on Information Theory, vol. 19, pp. 471–480, July 1973. [7] D.C. Feldmeier, “Fast software implementation of error detection codes,” IEEE/ACM Transactions on Networking, vol. 3, no. 6, pp. 640–651, 1995. [8] X. Wu and N. Memon, “Context-based lossless interband compression - extending CALIC,” IEEE Transactions on Image Processing, vol. 9, no. 6, pp. 994–1001, June 2000.
As can be seen, the encoding time is little dependent on the image, with variations around 7%. The presence of a floatingpoint unit yields an obvious advantage. In summary, for Cuprite, block, with clock frequency encoding of 50 bands of one of 150 MHz, yields a throughput of about 21052 blocks per second using an FPU, and 772 blocks per second without FPU.
[10] JPEG 2000 Part 2 - Extensions, Document ISO/IEC 154442.
6. CONCLUSIONS
[11] CCSDS 121.0-B-1 Blue Book, Lossless Data Compression, May 1997.
We have described a DSC application to on-board lossless compression of hyperspectral images. An information theoretic assessment has shown that, for these data, the most effective DSC
[9] D.S. Taubman and M.W. Marcellin, JPEG2000: Image Compression Fundamentals, Standards, and Practice, Kluwer, 2001.
