# - Acharya T.

ISBN 0-471-48422-9

**Download**(direct link)

**:**

**26**> 27 28 29 30 31 32 .. 100 >> Next

8. The following input index 5 corresponds to the pattern a 6 and hence the decoder outputs a b and inserts the new pattern baba in the dictionary to index 9. This pattern baba is formed by concatenating the first character a of the current output a 6 at the end of the previous output bab.

The next input index 7 corresponds to the pattern cb. The decoder outputs cb and obviously inserts the new pattern a6c in the dictionary and stops. At this point the final dictionary is exactly identical to the final dictionary that was formed during the encoding process, as shown in Table 2.11 in the previous example.

2.6 SUMMARY

In this chapter, we presented some of the key source coding algorithms widely used in data and image compression. First we described the run-length coding scheme with an example. We described the popular Huffman coding scheme that is used in various image and data compression techniques. We discussed the modified Huffman coding scheme to enhance its efficiency. Arithmetic coding is an alternative approach for an efficient entropy encoding and it achieves compression efficiency very close to the entropy limit. We discussed the basic principles of arithmetic coding with an example and the implementation issues. We described the binary arithmetic coding with an example. Binary arithmetic coding is a key algorithm for bilevel image compression. Variations of adaptive implementation of binary arithmetic coding algorithm have been adopted in different image compression standards—JBIG, JBIG2, JPEG, JPEG2000. We discussed the QM-coder algorithm for implementation of an adaptive binary arithmetic coding, which has been adopted in the JBIG standard for bilevel image compression and also in a mode of JPEG standard. A variation of QM-coder called the MQ-coder is the basis of the entropy encoding of the new JPEG2000 standard for still picture compression. We also described dictionary-based coding, especially the key algorithms in the popular Ziv-Lempel family of algorithms that are mainly used in text compression.

REFERENCES 53

REFERENCES

1. D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE, Vol. 40, No. 9, pp. 1098-1101, 1952.

2. R. G. Gallagher, “Variations on a Theme by Huffman,” IEEE Transactions on Information Theory, IT-24, Vol.6, pp. 668-674, November 1978.

3. R. Hunter and A. H. Robinson, “International Digital Facsimile Standard,” Proceedings of IEEE, Vol. 68, No. 7, pp. 854-867, 1980.

4. I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic Coding for Data Compression,” Communications of the ACM, Vol. 30, No. 6, June 1987.

5. W. B. Pennebaker, J. L. Mitchell, G. G. Langdon, Jr., and R. B. Arps, “An Overview of the Basic Principles of the Q-Coder Adaptive Binary Arithmetic Coder,” IBM Journal of Research and Development, Vol. 32, pp. 717-726, November 1988.

6. S. Lei, “Efficient Multiplication-Free Arithmetic Codes,”IEEE Transactions on Communications, Vol. 43, No. 12, December 1995.

7. B. Fu and K. K. Parhi, “Generalized Multiplication-Free Arithmetic Codes,” IEEE Transactions on Communications, Vol. 45, No. 5, May 1997.

8. W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard. Chapman & Hall, New York, 1993.

9. ISO/IEC JTC 1/SC 29/WG 1 WG1N1878, “JPEG2000 Verification Model

8.5 (Technical Description),” September 13, 2000.

10. J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Trans, on Info. Theory, IT-23, Vol. 3, pp. 337-343, May, 1977.

11. J. Ziv and A. Lempel, “Compression of Individual Sequences Via Variablerate Coding,” IEEE Trans, on Info. Theory, IT-24, Vol. 5, pp. 530-536, September 1978.

12. T. Welch, “A Technique for High-Performance Data Compression,” IEEE Computer, Vol. 17, No. 6, 1984.

13. J. A. Storer and T. G. Syzmanski, “Data Compression via Textual Substitution,” Journal of the ACM, Vol. 29, pp. 928-951, 1982.

This Page Intentionally Left Blank

3

JPEG: Still Image Compression Standard

3.1 INTRODUCTION

JPEG is the first international image compression standard for continuous-tone still images—both grayscale and color images [1]. JPEG is the acronym for Joint Photographic Experts Group. This image compression standard is a result of collaborative efforts by the International Telecommunication Union (ITU), International Organization for Standardization (ISO), and International Electrotechnical Commission (IEC). The JPEG standard is officially referred to as ISO/IEC IS (International Standard) 10918-1: Digital Compression and Coding of Continuous-tone Still Images and also ITU-T Recommendation T.81. The goal of this standard is to support a variety of applications for compression of continuous-tone still images of most image sizes in any color space in order to achieve compression performance at or near the state-of-the-art with user-adjustable compression ratios and with very good to excellent reconstructed quality. Another goal of this standard is that it would have manageable computational complexity for widespread practical implementation. JPEG defines four modes of operations:

**26**> 27 28 29 30 31 32 .. 100 >> Next