AP06_6.vp 1 Introduction The development of digital imaging arrays such as charge coupled devices (CCDs) leads to large amounts of data. A single 2048×2048 CCD frame with 16 bit/pixel, for example, generates 8 Mbytes of data. Such large format CCDs are currently used when focusing telescopes, and in many other fields. Scanning astronomical Schmidt plates with automatic plate scanning machines provides a tremendous quantity of data. A single Schmidt plate produces about 2 Gbytes of digi- tal information at 10ěm resolution. These images are not only stored but are also currently transmitted over networks for remote observing, remote browsing or data processing. A par- ticular solution to the transfer problem can be found with high bandwidth transmission links, which are expensive to install and operate. Moreover the problem of image archiving is partially solved with optical disks or very high-density tapes, which do not allow easy access for remote users. A solution can be found by using both data compression and high digital density supports such as CD-ROMs [1]. Many techniques have been developed for compressing astronomical images. A review of these techniques can be found in [2, 3]. Different applications require different data rates for compressed images and different visual qualities for decom- pressed images. In some applications, when browsing is required or transmission bandwidth is limited, progressive transmission is used to send images in such a way that a low quality version of the image is transmitted first at a low data rate [4]. Gradually, additional information is transmitted to progressively refine the image. A progressive image transmis- sion technique allows a full-sized image to be a visualized at any moment during the receiving time. This transmission method is more efficient than a non-progressive image trans- mission scheme, where every element of the transmitted data contains information about only a small piece of the image, and it is displayed by rows or by columns. Progressive image transmission is also a desirable feature because it provides the capability to interrupt transmission when the quality of the image has reached an acceptable level or when the user decides that the received image is not interesting. Similarly, the user at the receiver site can make a decision based on a rough reproduction of the image and can interact with the remote device to obtain a new image, or to recover a higher quality (or even an exact) replica of only a part of the image. A specific coding strategy known as embedded rate scal- able coding is well suited for progressive transmission. In embedded coding, all the compressed data is embedded in a single bit stream. The decompression algorithm starts from the beginning of the bit stream and can terminate at any data rate. A decompressed image at that data rate can then be reconstructed. In embedded coding, any visual quality requirement can be fulfilled by transmitting the truncated portion of the bit stream. To achieve the best performance the bits that convey the most important information need to be embedded at the beginning of the compressed bit stream [5]. RPSWS is an embedded rate scalable wavelet-based image coder. It produces a fully embedded bit stream and encodes the image to exactly the desired bit rate (precise rate control). This paper is investigates the applicability and the reliability of the RPSWS coder for coding astronomical images. RPSWS is well suited for progressive transmission of astronomical images. The remainder of this paper is organized as follows: Section 2 presents a brief description of the RPSWS coder. Section 3 discusses experimental results for various rates and for various astronomical images. Conclusions are presented in Section 4. 2 RPSWS Algorithm Description RPSWS is an embedded rate scalable wavelet-based image coder which can be used to code grayscale images [6] as well as color images [7] in an embedded fashion. For completeness sake, a brief description of RPSWS is presented below. 2.1 General structure of RPSWS The RPSWS algorithm uses the discrete wavelet transform to decompose the original image into sub-bands, where the sub-bands are logarithmically spaced in frequency and repre- sent octave-band decomposition. Each sub-band is encoded and decoded separately in a predefined order known by the encoder and the decoder. The sub-bands are scanned from the lowest frequency to the highest frequency sub-band, as shown in Fig. 1. For an N-scale transform, the scan begins at the lowest frequency sub-band, denoted as LLN, and scans sub-bands HLN, LHN, and HHN, at which point it moves on to scale N�1, etc. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 25 Acta Polytechnica Vol. 46 No. 6/2006 Embedded Coding of Astronomical Images F. I. Y. Elnagahy, A. A. Haroon, Y. A. Azzam, A. El-Bassuny Alawy,H. K. Elminir, B. Šimák Recursive partitioning of significant wavelet sub-bands (RPSWS) is an embedded rate scalable wavelet-based image coding algorithm. The RPSWS coder produces a fully embedded bit stream and encodes the image to exactly the desired bit rate (precise rate control). This paper investigates the applicability and the reliability of the RPSWS coder for coding astronomical images. Various types of astronomical images were compressed at different bit-rates using the RPSWS coder. The results were compared to the set partitioning in hierarchal trees coder (SPIHT), a well known embedded image corder. The comparison of the performance of the two algorithms was based on quantitative rate-distortion evaluations and subjective assessments of image quality. Keywords: Image compression, Color RPSWS, wavelet sub-band partitioning, embedded coding, SPIHT, astronomical images. In order to perform embedded coding in general, multi- ple cycles (iterations) through the sub-bands are adopted. To reduce distortion of the decompressed image, the wavelet coefficients with the largest magnitude should be first en- coded and refined to an additional bit of precision. To achieve this goal of distortion reduction, an initial threshold must first be determined. In the first cycle, the sub-bands are scanned as described above, and the wavelet coefficients that have mag- nitudes larger than the threshold are coded. In the next cycle, the threshold is halved and the coefficients that were coded in the previous cycle are refined to an additional bit of precision. Meanwhile, the transformed coefficients that have magni- tudes larger than the threshold and have not been coded in the previous cycle are coded. This process is repeated until the desired bit rate is achieved. In each cycle, two passes are used to encode/decode and refine the wavelet coefficients of each sub-band. A significance map pass is used to code the position, the sign, and/or the ini- tial reconstructed magnitude value of the significant wavelet coefficients. In the refinement pass some refinement bits are generated to refine the magnitude of the previously encoded coefficients. 2.2 RPSWS code stream A wavelet coefficient that has an absolute value above or equal to the threshold is called a significant coefficient; other- wise it is an insignificant coefficient. An insignificant wavelet coefficient is coded with one bit “0” while a significant wavelet coefficient is coded with two bits. The first bit “1” indicates the significance of the wavelet coefficient and the second bit indicates its sign (“0” for positive and “1” for negative coeffi- cient). A sub-band that has no significant wavelet coefficient is called an insignificant sub-band. As the insignificant sub- -band is entirely coded with one bit, a large number of insignificant coefficients are coded with one symbol (one bit). Coding a large number of insignificant wavelet coefficients with one bit is the main idea of the proposed coding algo- rithm. The encoder sends one bit to inform the decoder about the significance of the sub-band. This bit is called the sub-band significance flag bit (SSF) which is equal to zero for insignificance sub-band SSF. When the decoder receives SSF � 0 it knows that the sub-band is insignificant and hence all coefficients in that band are insignificant. The decoder sets all reconstructed coefficient values in that sub-band to zero. In other words all wavelet coefficients in that band are quantized to zero. For a significant sub-band, the encoder outputs SSF � 1 and the decoder knows that this sub-band contains significant coefficient(s). In this case both the encoder and the decoder partition the sub-band into four blocks and the significance test is then applied to each block. An insignificant block is also coded with one bit “0”. This bit is called the block signifi- cance flag bit (BSF), where the significant block is coded with BSF � 1 and this block is again sub-divided into four new blocks. This block division process continues until the last block contains four coefficients or less, depending on the dimensions of the sub-band. The encoder creates a list to store information about the significant wavelet coefficients. This list is called the coeffi- cients significance list (CSL). Each time the encoder finds a significant wavelet coefficient it appends its coefficient value to the coefficients significance list. The encoder then sets the value of the significant wavelet coefficient to zero in the wave- let coefficients matrix. The coefficients significance list is used during the magnitude refinement pass. The sub-band signifi- cance map coding process mentioned above is implemented in two steps. The first step is called sub-band Or-tree signifi- cance map assignment and the second is sub-band Or-tree significance map coding. 2.3 RPSWS color image coding The general scheme that will be used to code color images in an embedded fashion is described as follows: the RGB color space is first converted to YUV color space. Color space conversion is used to reduce the correlation between the color components. The discrete wavelet transform is then applied to individual YUV components. The transformed wavelet co- efficients of each component are then coded with the RPSWS coding algorithm. Color space conversion and the coding process are described below. 2.3.1 Color Space Conversion The RPSWS coding system accepts the input image in 24-bit RGB color space. Each pixel is represented by the three bytes (red (R), blue (B), and green (G)). A conversion to the YUV color space [8] is performed to reduce the correlation between the color components as follows: Y � 0.3 R�0.6 G�0.1B U � B�Y V � R�Y Where Y is the luminance component, and U and V are two chrominance components. The luminance component provides a grayscale version of the image, while the two chrominance components give additional information that converts the gray image to a color image. The YUV represen- tation is more natural for image and video compression. The corresponding inverse transform is as follows: R � Y�V G � Y�V/2�U/6 B � Y�U 26 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 6/2006 Fig. 1: Sub-bands scanning order 2.3.2 Color Components Coding The discrete wavelet transform is applied to individual YUV components. The resulting wavelet coefficients for Y, U, and V components are respectively Yc, Uc, and Vc. In order to perform embedded color image coding, an initial threshold T is first determined. The initial threshold T is chosen so that T � 2i, where i is computed in such a way that 2i�1>x>2i and x is the maximum absolute value of the Yc-component wavelet coefficients. The significance pass information of the Yc-component (sub-band by sub-band) is encoded, followed by magnitude refinement pass information of the all Yc-com- ponent sub-bands. In the same manner, the Uc-component and the Vc-component are encoded. The threshold T is halved and the process continues until the desired bit rate is achieved. 3 Experimental Results Various types of astronomical images were used to evalu- ate the performance of the SPIHT [9] and RPSWS coders. The images used in this study had been selected from the Hubble space telescope archive (http://heritage.stsci.edu/gal- lery/galindex.html). In the selection we included a variety of types of objects e.g., Galaxy, nebula, open cluster, globular cluster and planets. The color images (512×512– 24bit/pixel) used in the presented results are Cluster (NGC 6397) which is a globular cluster, bright, very large, Galaxy (M51, Whirlpool Galaxy) which is a magnificent (or otherwise interesting) object and great spiral nebula and Mars, as shown on the left of Fig. 2, respectively. The gray scale images (512×512 – 8bit/pixel) are Cluster (M103), which is an open cluster, quite © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 27 Acta Polytechnica Vol. 46 No. 6/2006 Fig. 2: Original 512×512 test images: Color images at 24 bpp (left): Cluster (NGC 6397), Galaxy (M51), and Mars images, respectively. Grayscale images at 8 bpp (right) Cluster (M103), Galaxy (M101), and Nebula (B33) images, respectively large, bright, round and rich in stars of magnitude 10 to 11, Galaxy (M101), which is quite bright, very large, irregularly round, gradually and a very abruptly much brighter middle bright small nucleus and Nebula (B33, Horsehead Nebula), which is a very faint and dark nebula, as shown on the right of Fig. 2, respectively. The SPIHT color results were obtained by applying the SPIHT software (DECDCOLR/CODECOLR) to the color images and using the adaptive arithmetic coding algorithm of [10] with several adaptive models. The SPIHT gray scale results were obtained by applying the SPIHT software (FASTCODE/FASTDECD) to the gray scale images, and these algorithms do not use an adaptive arithmetic coding algorithm. All SPIHT algorithms were obtained from (http://www.cipr.rpi.edu/research/SPIHT/spiht3 .html). In our results, the wavelet transform is implemented with 6-level pyramids constructed with 9/7-tap filters of [11] and using a reflection extension at the image edges. The resulting bit stream of the RPSWS was not entropy coded. Table 1 shows the objective coding results (PSNR in dB) of the SPIHT and RPSWS algorithms for different color images and bit rates. Table 2 shows the results of the gray scale im- ages. Some reconstructed images for both algorithms at dif- ferent bit rates are shown in Fig. 3, 4, 5, 6, 7, and 8. From out results we can conclude that: � The SPIHT objective color coding results (PSNR) are supe- rior to higher than the RPSWS results, for all test images and at all bit rates, as shown in Table 1. This increase in performance is expected, and it is mainly due to the use of arithmetic coding in the SPIHT algorithm. The subjective quality tests showed that there are no significance differ- ences between the reconstructed images of the two algo- rithms at higher bit rates. At lower bit rates, the quality of our reconstructed images for Cluster (NGC 6397) and Gal- axy (M51) is better than the SPIHT reconstructed images. As shown in Fig. 3, bright stars are more defined and have more details for RPSWS than in the case of SPIHT. The fine details of the arms of the galaxy (M51) are more de- fined for RPSWS than in the case of SPIHT, as shown in Fig. 4. For the Mars reconstructed images shown in Fig. 5, the details of Mars are better in the case of SPIHT than in the case of RPSWS at lower bit rates. � The RPSWS objective gray scale coding results (PSNR) are superior to the SPIHT results, for most test images and at most bit rates, as shown in Table 2. The subjective quality tests show that RPSWS reconstructed images are better than SPIHT reconstructed images at lower bit rates, as shown in Fig. 6, 7, and 8. At higher bit rates there are no significance differences in the visual qualities of the SPIHT and RPSWS reconstructed images. 28 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 6/2006 Fig. 3: Reconstructed Cluster (NGC 6397) images at bit rates 0.03125,0.25, and 1 bits/pixel, respectively. SPIHT (left) and RPSWS (right). Fig. 4: Reconstructed Galaxy (M51) images at bit rates 0.03125, 0.25, and 1 bits/pixel, respectively. SPIHT (left) and RPSWS (right) 4 Conclusion This paper presents objective coding results of both SPIHT and RPSWS for coding color astronomical images as well as gray scale images. From the results presented here we conclude that the qualities of RPSWS reconstructed images are better than those of SPIHT reconstructed images at lower bit rates for both color and gray scale images. At higher bit rates there are no significant differences in the visual qualities of the SPIHT and RPSWS reconstructed images. Both SPIHT and RPSWS are embedded rate scalable wavelet-based image coders, and are well suited for astronomical images to be pro- gressively transmitted over networks for remote observing, remote browsing and data processing. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 29 Acta Polytechnica Vol. 46 No. 6/2006 Fig. 5: Reconstructed Mars images at bit rates 0.03125,0.25, and 1 bits/pixel, respectively. SPIHT (left) and RPSWS (right). Fig. 6: Reconstructed Cluster (M103) images at bit rates 0.03125, 0.25, and 1 bits/pixel, respectively. SPIHT (left) and RPSWS (right). Bit rate Compression Cluster(NGC 6397) Galaxy(M51) Mars SPIHT RPSWS SPIHT RPSWS SPIHT RPSWS 1 24:1 29.25 28.07 35.97 35.32 46.94 46.53 0.5 48:1 24.75 24.10 32.51 31.95 43.37 42.94 0.25 96:1 21.54 21.04 29.91 29.15 39.99 39.26 0.125 192:1 19.28 18.62 27.59 27.17 36.15 35.71 0.0625 384:1 17.30 17.13 25.94 25.61 32.19 32.38 0.03125 768:1 16.40 16.24 24.47 24.35 28.78 28.39 0.015625 1536:1 15.62 15.62 23.25 23.09 25.59 25.38 0.0078125 3072:1 15.18 15.15 22.40 22.11 23.89 23.38 Table 1: SPIHT and RPSWS PSNR color results, measured in dB, for various images and bit rates. References [1] Bobichon, Y., Bijaoui, A.: A Regularized Image Restora- tion Algorithm for Lossy Compression in Astronomy. Experimental Astronomy, Vol. 7 (1997), p. 239–255. [2] Elnagahy, F., Šimák, B.: Wavelet-based Astronomical Digital Image Compression. Proceedings of Workshop 2004, Prague: CTU in Prague: CTU Reports, Part A, Special Issue, 8, March 2004, 208–209. 30 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 6/2006 Bit rate Compression Cluster (M103) Galaxy (M101) Nebula (B33) SPIHT RPSWS SPIHT RPSWS SPIHT RPSWS 1 8:1 31.79 31.75 39.53 39.52 40.79 40.70 0.5 16:1 27.59 27.82 36.10 36.05 37.39 37.41 0.25 32:1 24.16 24.38 33.83 33.67 35.31 35.21 0.125 64:1 21.53 21.69 31.85 31.83 33.97 33.95 0.0625 128:1 19.70 19.83 29.90 29.87 32.36 32.41 0.03125 256:1 18.56 18.70 28.22 28.28 30.68 30.90 0.015625 512:1 17.70 17.84 26.74 26.88 29.74 29.89 0.0078125 1024:1 17.32 17.36 25.73 25.84 28.82 28.96 Table 2: SPIHT and RPSWS PSNR gray scale results, measured in dB, for various images and bit rates Fig. 7: Reconstructed Galaxy (M101) images at bit rates 0.03125, 0.25, and 1 bits/pixel, respectively: SPIHT (left) and RPSWS (right). Fig. 8: Reconstructed Nebula (B33) images at bit rates 0.03125, 0.25, and 1 bits/pixel, respectively: SPIHT (left) and RPSWS (right). [3] Louys, M., Starck, J. L., Mei, S., Bonnarel, F., Murtagh F.: Astronomical Image Compression. Astronomy Astrophysics Supplement Series, Vol. 136 (1999), p. 579–590. [4] Rabbani, M., Jones, P. W. : Digital Image Compression Techniques. Bellingham, Washington: SPIE Opt. Eng. Press, 1991. [5] Shapiro, J. M.: Embedded Image Coding using Zero- trees of Wavelets Coefficients. IEEE Transactions on Signal Processing, Vol. 41(1993), No. 12, p. 3445–3462. [6] Elnagahy, F., Šimák, B. : Embedded Rate Scalable Wave- let-based Image Coding Algorithm with RPSWS. Interna- tional Journal of WSCG, Vol. 12 (2004), No. 1, p. 97–104. [7] Elnagahy, F.: Embedded Rate Scalable Wavelet-Based Color Image Coding. In Proceedings of the 8th International Student Conference on Electrical Engineering, POSTER 2004, May 2004, Prague, p. IC12. [8] Westwater, R., Furht, B.: Real-Time Video Compression: Techniques and Algorithms. Kluwer Academic Publisher, 1997. [9] Said, A., Pearlman, W. A.: A New, Fast, and Efficient Im- age Codec Based on Set Partitioning in Hierarchical Trees. IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6 (1996), p. 243–250. [10] Witten, I. H., Neal, R. M., Cleary, J. G.: Arithmetic Cod- ing for Data Compression. Communications of ACM, Vol. 30 (1987), No. 6, p. 520–540. [11] Antonini, M., Barlaud, M., Mathieu, P., Daubechies, I.: Image Coding using Wavelet Transform. IEEE Transac- tions on Image Processing, Vol. 1(1992), No. 2, p. 205–220. Dr. Eng. Farag Ibrahim Younis Elnagahy e-mail: faragelnagahy@hotmail.com Dr. Aly A. Haroon e-mail: alyharoon@hotmail.com Dr. Eng. Yosry Ahmed Azam e-mail: yosryahmed@hotmail.com Assistant Prof. Ahmed El-Bassuny Alawy Email: abalawy@hotmail.com Astronomy Department Dr. Eng. Hamdy K. Elminir e-mail: hamdy_elminir@hotmail.com Solar and Space Research Department National Research Institute of Astronomy and Geophysics (NRIAG) 11421 Helwan, Cairo, Egypt Doc. Ing. Boris Šimák, CSc. e-mail: k332@fel.cvut.cz Department of Telecommunications Engineering Czech Technical University in Prague Faculty of Electrical Engineering Technická 2 166 27 Praha 6, Czech Republic © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 31 Acta Polytechnica Vol. 46 No. 6/2006