The New CCSDS Image Compression Recommendation Pen-Shu Yeh', Philippe Armbruster2,A aron Kiely3, Bart Nasschelein4, Gilles Moury', Christoph Schaefer6 'NASA;GSFC:USA; 'ESA/ESTEC, The Netherlands; %A_S_A-UPrPL, US-4; 4-WC, Be!gixq 'CNJ3S Toulouse, France; %ADS/Astrium, Germany Abstract- The Consultative Committee for Space Data applications. The working goup agreed that a suitable Systems (CCSDS) data compression working group has compressor must meet the requirements listed in Table 1, recently adopted a recommendation for image data which were intended to reflect the envisioned application for compression, wah a final release expected in 2005. The real-time hardware compression onboard a spacecraft. algorithm adopted in the recommendation consists of a tn70- dimensional discrete wavelet transform of the image, Table 1. CCSDS Image Data Compression Requirements followed by progressive bit-plane coding of the transformed data. The algorithm can provide both lossless and lossy Process both frame and non-frame (push- compression, and allows a user to directly control the compressed data volume or the fidelity with which the Offer adjustable coded data rate or image wavelet-transformed data can be reconstructed. The to a lossless mode algorithm is suitable for both frame-based image data and Accommodate from 4-bit up to 16-bit input scan-based sensor data, and has applications for near-Earth Dixels and deep-space missions. The standard will be accompanied Provide real-time processing with space by free software sources on a hture web site. An qualified electronics (220 Msamples/sec, SI Application-Specific Integrated Circuit (ASIC) waWsamples/sec, based on year 2000 space implementation of the compressor is currently under electronics technology) development. This paper descriies the compression Require minimum ground operation algorithm along with the requirements that drove the Limit the effects of a packet loss to a small selection of the algorithm Performance results and region of the image. comparisons with other compressors are given for a test set of space images. Apart from the requiremerrts listed in Table 1, perhaps the biggest consideration in the algorithm selection process was to npti-&7e rate-distdon perfomme. %e ability tc 1. INTRODUCTION perfonn progressive compression was viewed as a highly desirable feature, but not mandatory. It was the hope of the The benefits of data compression to space missions include working group that if any patents were included in the increasing the abdity to collect science data, and reductions recommendation, a royalty-free license could be offered to in onboard storage and telemetry bandwidth requirements. all CCSDS member agencies. Because of these benefits, the Consultative Committee for Space Data Systems (CCSDS) has been engaged in The working group also assembled a set of 20 test images recommending data compression standards for space ranging from Earth observations to star field, galaxies and applications. solar images. The dynamic ranges of the test images include %bit, 10-bit, 12-bit and a 16-bit radar image. The hrst CCSDS data compression recommendation, adopted in 1997, standardized a version of the lossless Rice Candidate algorithms were proposed, and performance compression algorithm [I]. Space missions benefiting from evaluations were conducted based on both quantitative rate- this recommendation range from deep space probes to near distortion evaluations and subjective assessments of image Earth observatories. quality. In addition, implementation architecture studies were performed to assess the real-time processing In 1998, the CCSDS data compression workmg group began capabilities of the proposed algorithms. A consensus was to assess the feasibility of establishing an image reached in 2003, and a wavelet-based compression compression recommendation suitable for spaceborne algorithm was selected. The selected algorithm combined 1 Research perfod by Yeh for this paper was conducted for the U. S. Government. Pornons of the research described in this paper were carried out by Kiely at Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronatuics and Space Administration. 1 c elements from different algorithms that were initially convention. The two filters differ in the need for floating- proposed, along with modifications to reduce complexity. point arithmetic. The floating-point filter [4] requires floating-point calculations and gives improved performance In Section 2, we describe the compression algorithm. at low bit rates, while the integer filter [5] permits lossless Compression performance results of the algorithm on the compression and requires no floating-point operations. test images are given in Section 3. Section 4 describes the There are many variations in methods for computing integer current status of the recommendation. and floating point 917 DWTs, and the reader is encouraged to refer to [6] for exact specifications of the forward and inverse transforms that are to be used with this 2. ALGORITHDME SCRIPTION recommendation. A single-stage two-dimensional DWT is computed by fnst The recommended algorithm consists of two functional applying the one-dimensional DWT to the rows of the modules as depicted in Figure 1: a Discrete Wavelet image, and then to the columns of the transformed image, as Transform (DWT) module that perfom decorrelation, and illustrated in Figure 2. Subsequent stages of decomposition a Bit-Plane-Encoder (BPE) that encodes the decorrelated are applied to the low-pass horizontal / low-pass vertical data. This general image compression approach is widely subband output from the previous stage, producing the used, see, for example, references [2,3,4]. pyramidal decomposition described in [7]. The standard calls for 3 stages of DWT decomposition, decomposing an image into 10 subbands, as illustrated in Figure 3. Fewer r - - - - - - - - - - - - than three levels of DWT decomposition would yield smaller blocks with less intra-block correlation to exploit Wavelet Bit-Plane with the applied entropy coding. More than three levels Transform Encoder would be expensive to implement in hardware, due to the - - - - - - - - - - - - - I larger dimensions of each block and the more extensive code tables required. Figure 1 - The Two Functional Modules of the Algorithm The BPE described in Section 2.2 is used to encode the subbands produced by the two-dimensional DWT 2. I Discrete Wavelet Transform decomposition. For effective operation, the BPE relies on The recommendation specifies two DWTs that may be used. the same bit plane in each of the subbands having the same When applied to one-dimensional data, both transforms relative priority in terms of contribution to overall image effectively use 9 filter taps to compute low-pass output, and distortion. For the integer transform, thls requires the 7 filter taps to compute high-pass output. Each filter is thus subbands to be scaled. The scaling factors are chosen to be referred to as a “917” DWT under the usual naming powers of two so that scaling can be performed using bit- I-d DWT of each rh igh-pass, vertical row * low-pass horizontal horizontal low-pass, high-pass vertica I vertical high-pass high-pass Figure 2 - Single Level Two-Dimensional DWT Decomposition of an Image 2 I original image Figure 3 - Example of 3-Level Two-Dimensional DWT Decomposition of an Image shift operations. Under the floating-point DWT, no scaling Segments with few blocks on the other hand are convenient is performed, but D W coefficients are rounded to the to implement by requiring small code buffer sizes. nearest integer. Within a segment, the BPE first encodes a quantized version 2.2 Bit Plane Encoder of the DC coefficients for the segment by applying the Rice coding algorithm to differences between successive The Bit Plane Encoder (BPE) processes wavelet coefficients quantized coefficients. Bits providing further DC coefficient in groups of 64 coefficients referred to as a block. A block resolution are included as part of the subsequent bit-plane loosely corresponds to a localized region in the original coding process. image. A block consists of a single coefficient from the lowest spatial frequency subband, referred to as the DC rJext- &e BPE sltttessive!y ezccdes bit plaoes sf caeEcicxit coeficiertl, and 63 AC co@cients, as iilustrated in Figure 4. magnitudes in a segment, proceeding from most-sigdicant Blocks are processed in raster scan order, i.e., rows of to least-sigmficant bit plane, inserting AC coefficient sign blocks are processed from top to bottom, and proceeding bit values at appropriate points in the encoded data stream. !?om left to right horizontally within a row. The resulting encoded bitstream constitutes an embedded data format that provides progressive transmission within a This structure is used to jointly encode information segment; DWT coefficient resolution effectively improves pertaining to groups of coeEcients within the block because by a factor of 2 as encoding proceeds from one bit plane to they exhibit significant statistical correlation. Corresponding the next. parent, chddren and grandchild coefficients are correlated in that their absolute values usually decrease in that order. Coefficients within a block are arranged in groups, each with They are correlated in the sense that the binary words at most 4 coefficients. Conceptually, at a given bit plane, a that describe updates to sets of coefficients are not binary word can be used to describe an update to each distriiuted uniformly. coefficient in the group for which all more sigmiicant ma-gnitude bits are zero. These words are entropy coded A segment is defmed as a group of consecutive blocks. using one of a handfid of variable-length binary codes; the Coding of DWT coefficients proceeds segment-by-segment specific code is selected adaptively. The entropy coded data and each segment is coded independently of the others. The are arranged so that all parent coefficients in the segment are number of blocks in a segment can be assigned by the user updated first, followed by children, and then grandchldren to any value between 16 and 2" inclusive; the value might coefficients. Finally, the segment includes (uncompressed) be chosen based on the memory available to store. the update bits for the coefficients in the segment for whch segment. Segments with many blocks have the desirable more significant magnitude bits are not all zero. property of producing a code stream which is embedded globally. This means that the distortion of the decompressed image will be uniform on a global scale despite the inevitable presence of locally variable compressibility. DC coefficient parents I grandchildren wavelet-transformed image a single block - Figure 4 In this schematic of a wavelet-transformed image, the 64 shaded pixels comprise a single block. The tradeoff between reconstructed image quality and Table 2. List of Test Images compressed data volume for each segment can be controlled by specifjmg the maximum number of bytes in each Size I Bits/ I compressed segment, and a “quality” limit that constrains the amount of DWT coefficient information to be encoded. Compressed output for a segment is produced until the byte Pathfinder: limit or quality limit is reached, whichever comes fust. The encoded bitstream for a segment can be fiuther truncated 500x500 (or, equivalently, coding can be terminated early) at any /band3 I Spot-panchromatic SPOT Imaging 51 point to further reduce the data rate, at the price of reduced band I image quality for the corresponding segment. Forest I I band 1h and4 I 2048x2048 lo Ice NOOryidar I I band 1h and4 2048x2048 lo 3. PERFORMANCE India NOAA Polar band 1 hand4 Orbiter The quantitative performance of the new recommen,.ition North Atlantic NOAA Polar has been evaluated on the test image available at Band 1h and4 Orbiter h~://~~~.~~sds.orddocu/dscgi/ds.pyNiewlCollec13t ion-6 Ocean NOAA Polar with image size and depth information summarized in Table band 1 hand4 Orbiter 2. The set of images has widely varying statistics as can be Solar Big Bear Solar seen from two examples given in Figure 5. Observatory Sunspot Big Bear Solar 5 12x5 12 Observatory WFPC Hubble Space Telescope 4 FOC Hubble Space Telescope SAR ERS- 1 5 12x512 4 - Figure 5 Examples of Test Images: (a) SPOT Panchromatic Image and (b) Wide Field Planetary Camera Image As an indication of compression perfonnance, we compare the two DWT options of the recommendation with the 4. STATUS PEG2000 standard when used with the 917 floating-point DWT. For this comparison, we simulate performance for A first version draft of the new image compression “push-broom” spacecraft compression applications. In the recommendation (known as a red book in CCSDS parlance) case of the CCSDS recommendation, this means defining a has been approved for agency review.’ The data segment of blocks to correspond to the image width, and compression working goup will issue a second draft after kiposiag zi 5xcd ratc coriisait on each compressed takmg into account review comments from different segment. Similar constraints are imposed on the PEG2000 agencies. Following agency review of the second red book, coder by using the scan-based mode introduced by SAIC it is expected that a formal recommendation, (a blue book), and CNES with 8-he precincts [8]. We evaluated the will be released in 2005. performance at bit rates ranging from 114 up to 2 bitslpixel. The compression working group is also producing a green Table 3 shows the Peak-Signal-To-Noise Ratio (PSNR) in book which is not part of the recommendation, but will serve dB and the maximum absolute error averaged over images as an user’s guide for implementers. The green book wdl with the same dynamic range. It is seen from these results cover subjects such as system issues relating to error that the new CCSDS recommendation has performance propagation and rate control, implementation schemes for similar to that of the PEG2000 standard when both methods wavelet transform using localized transform, and detailed use the floating point 9/7 DWT under the “push-broom’’ study results. constraints described above. As one might expect, use of the integer 9/7 DWT results in more than 1 dB loss in Several implementations are being pursued concurrently performance at hgher bit rates. both for the purpose of validating the recommendation, and also to provide a technology demonstration for space Implementation complexity played a significant role in the implementation. Software implementations have been final algorithm selection. In particular, an early analysis of produced at JPL and GSFC. Additional software ASIC implementation complexity suggested that the implementations are under development at the University of PEG2000 coder was at least a factor of two more complex Idaho, in an effort led by Prof. Gary Malu, and the than other coding options being considered. For spacecraft applications, h s could have a significant impact on the ’ achievable processing rate. The CCSDS web site, wvw.ccsds.org, describes the meaning of the different books and mcludes downloadable versions of CCSDS recommendations. 5 I Table 3. Performance Comparison for Push-Broom Mode Average for 10-bit images I I 1 I I I 2.00 54.70 53.26 54.92 26.00 23.50 18.30 1.00 47.76 47.10 47.80 63.20 53.40 53.90 0.50 42.97 42.60 42.90 115.50 95.10 113.20 0.25 39.36 39.12 39.32 204.80 188.30 195.30 University of Nebraska in an effort led by Prof. Khalid Sayood. These codecs are written in C and are in the process 5. CONCLUSION of cross-verification. A JAVA implementation based on earlier documentation was developed at the University of The CCSDS data compression worlung group has finalized Barcelona under the direction of Prof. Joan Serra. This an algorithm for image data compression, intended for version did not include the full BPE specification for pattern onboard compression. The algorithm yields nearly the coding, but could be used to estimate performance. A demanding rate-distortion performance of the commercial hardware ASIC implementation is being developed at the JPEG2000 standard but significantly alleviates on-board University of Idaho’s Center for Advanced Microelectronics implementation complexity. On-board operation has been and Biomolecular Research (CAMBR) facility3 where the eased by relieving the user of selecting data-dependent Radiation-Hardness-By-Design (RHBD) technique [9] has encoding tables for optimum compression performance. been developed and is being applied to the algorithm to produce high-speed space-qualified circuits. The projected The recommendation makes use of 917 DWTs. An integer throughput is over 20 Msampleslsec. Th~sim plementation DWT can be used for applications requiring lossless separates the DWT and BPE into two ASICs. compression, good performance at high rates, or to avoid floating point operations in the DWT calculation. A The software development and verification is expected to be floating-point DWT can be used for improved performance completed before the publication of the green book, which at low bit rates. will then include an open-source website for users to download and execute the codes. The ASIC flight hardware The DWT is followed by a bit-plane encoder that produces will be available commercially. an encoded bitstream providing progressive transmission within a coded segment. The algorithm is applicable to a variety of imaging instruments, and is suitable for push-broom sensors requiring immediate processing of data. The final recommendation is expected to be released in 3 www.cambr.uldaho.edu 2005. An open source C software implementation is 6 1 expected to be available soon, and an ASIC hardware implementation is currently under development. [I] CCSDS 121.0-B-1, Lossless Data Compression, CCSDS, 1997. [2] ISOLEC FCD15444-1, Information technology - JPEG2000 Image Coding System, Final Cormnittee Dmft Version 1.0 [3] A. Said and W. Pearlman, “A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees,” IEEE Transactions on Circuits and Systems for Video Technology,v ol. 6, no. 3, pp. 24S250, June 1993. [4] JPEG2000: Image Compression Fundamentals, Standards and Practice, D. Taubman, M. Marcellq Kluwer Academic Publishers, 2002. [5] A. R Calderbank, I Daubechies, W. Sweldens, B.-L. Yeo, ‘Wavelet Transforms that Map Integers to Integers,” Appl. Cornput. Harmon. Anal., vol. 5, pp. 332-369, July 1998. [6] CCSDS 122.0-R-1, Image Data Compression, CCSDS, 2004 [7] S. G. Mallat, “A Theory for Multiresolution Signal Decomposition: The Wavelet RepresentatioR” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 7, pp. 674-693, July 1989. [8] P.3. Ye4 G. Moury, and P. Armbruster, “The CCSDS Data Compression Recommendations: Development and Status,” Proc. SPIE Application of Digital Image Processing, July 7-10,2002, Seattle, WA. [9] J. Gambles and G. Maki, “Radiation Effects and Hardening Techniques for Spacecraft System Microelecironics,” IAF World Space Congress, Reference IAC-02-1.05.08, October, 2002. 7