Reentry into compressed data

Details Reentry into compressed data Reentry into compressed data

2005-09-06

2005-09-06

Au, Amelia M. (Department: 2621)

Image analysis

Image compression or coding

C382S235000

Reexamination Certificate

active

06941019

ABSTRACT:
Apparatus and methods are provided for entering compressed data streams at selected reentry points to initiate decoding thereby allowing efficient manipulation of the compressed data and minimizing storage requirements. The reentry information preferably includes bit-level pointers and sufficient state information to initialize the decoder properly. This enables decoding without having to resume at independently decodable points, such as JPEG restart markers. For example, in the context of a JPEG image, in addition to the typical information available to the decoder that has been passed in earlier markers, the reentry information for a given MCU boundary may include: a bit-level pointer to the first block's DC Huffman code, the position of the output, and a DC predictor for each component of the MCU. This allows decompression to be performed in the appropriate order to accomplish various data manipulation operations, such as rotation, thus significantly reducing buffering requirements. Reentry information into a compressed data stream can be generated during encoding, decoding, partial encoding, partial decoding, entropy encoding, and/or entropy decoding. In addition, a reentry decoder may quickly interpret the compressed data sufficiently to preserve desired reentry information and discard unneeded output of the decoding process and terminate immediately after the last desired reentry point. This enables buffering of pieces of compressed data with associated reentry information rather than buffering the entire decompressed data. Additionally, when a subset of the reconstructed data is needed the step of recompressing the individual pieces can be avoided by saving reentry information with the associated pieces of compressed data.

REFERENCES:
patent: 4596039 (1986-06-01), Mitchell et al.
patent: 4610027 (1986-09-01), Anderson et al.
patent: 4627020 (1986-12-01), Anderson et al.
patent: 4646356 (1987-02-01), Anderson et al.
patent: 4658430 (1987-04-01), Anderson et al.
patent: 4689824 (1987-08-01), Mitchell et al.
patent: 4725815 (1988-02-01), Mitchell et al.
patent: 4837845 (1989-06-01), Pruett et al.
patent: 4888645 (1989-12-01), Mitchell et al.
patent: 4891643 (1990-01-01), Mitchell et al.
patent: 4905297 (1990-02-01), Langdon, Jr. et al.
patent: 5327248 (1994-07-01), Miller et al.
patent: 5341440 (1994-08-01), Earl et al.
patent: 5708732 (1998-01-01), Merhav et al.
patent: 5751865 (1998-05-01), Micco et al.
patent: 5867598 (1999-02-01), de Queiroz
patent: 6081211 (2000-06-01), de Queiroz et al.
patent: 6246801 (2001-06-01), Boyce et al.
patent: 6298166 (2001-10-01), Ratnakar et al.
patent: 6381371 (2002-04-01), Epstein et al.
patent: 6690832 (2004-02-01), Mitchell et al.
patent: 1037165 (2000-09-01), None
patent: 02698037 (1992-12-01), None
patent: WO96/36941 (1996-11-01), None
Glen G. Langdon, Jr., “An Introduction to Arithmetic Coding,”IBM J. Res. Develop.28, 135-149 (Mar. 1984).
Joan L. Mitchell, Ph.D., William Pennebaker, Ph.D., “JPEG”,1993 AIIM Show and Conference—Imaging: Transformation at Work,Chicago, Illinois (Apr. 5-8, 1993).
K.L. Anderson, J.L. Mitchell, G. Goertzel, W.B. Pennebaker, “Compression of Bilevel Images.”
P. J. Sementilli, “Image Processing in the Quantized DCT Domain,”IBM Confidential(Nov. 11, 1992).
Joan L. Mitchell, “Facsimile Image Coding,”AFIPS—Conference Proceedings, National Computer Conference,vol. 49, 423-426 (1980).
W.B. Pennebaker, G. Goertzel, J.L. Mitchell, “Recent Advances in Data-Conversion Facsimile Techniques,”Journ. Appl. Photog. Eng.,vol. 6, No. 4, 93-96 (Aug. 1980).
S.T. Klein, Y. Wiseman, “Parallel Huffman Decoding,”IEEE Computer Society Proceedings, Data Compression Conference,Snowbird, Utah (Mar. 28-30, 2000).
W.B. Pennebaker, J.L. Mitchell, “JPEG Still Image Data Compression Standard,” Chapman & Hall, International Thomson Publishing (1993), ISBN 0-442-01272-1, pp. 73-78.
W.B. Pennebaker, J.L. Mitchell, “JPEG Still Image Data Compression Standard,” Chapman & Hall, International Thomson Publishing (1993), ISBN 0-442-01272-1, Chapter 7, JPEG Syntax and Data Organization, pp. 97-120.
W.B. Pennebaker, J.L. Mitchell, “JPEG Still Image Data Compression Standard,” Chapman & Hall, International Thomson Publishing (1993), ISBN 0-442-01272-1, Chapter 8, Entrophy Coding Concepts, pp. 135-147.
W.B. Pennebaker, J.L. Mitchell, “JPEG Still Image Data Compression Standard,” Chapman & Hall, International Thomson Publishing (1993), ISBN 0-442-01272-1, Chapter 9, JPEG Binary Arithmetic Coding, pp. 149-167.
M. Rabbani, P.W. Jones, “Digital Image Compression Techniques,”Tutorial Texts in Optical Engineering,SPIE Optical Engineering Press (1991), ISBN 0-8194-0648-1, vol. TT7, Chapter 3, Variable-Length Codes, pp. 22-32.
“Algorithm for Rotating an Image in Run End Form,”IBM Tech. Disclosure Bulletin(Nov. 1989), pp. 299-302.
K.L. Anderson, F.C. Mintzer, G. Goertzel, J.L. Mitchell, K.S. Pennington, W.B. Pennebaker, “Binary-Image-Manipulation Algorithms in the Image View Facility,”IBM J. Res. Develop.(Jan. 1987), vol. 31, No. 1, pp. 16-31.
J.L. Mitchell, W.B. Pennebaker, “Software Implementations of the Q-Coder,”IBM J. Res. Develop.(Nov. 1988), vol. 32, No. 6, pp. 753-774.
W.B. Pennebaker, J.L. Mitchell, “Probability Estimation for the Q-Coder,”IBM J. Res. Develop.(Nov. 1988), vol. 32, No. 6, pp. 737-752.
J.L. Mitchell, W.B. Pennebaker, “Optimal Hardware and Software Arithmetic Coding Procedures for the Q-Coder,”IBM J. Res. Develop.(Nov. 1988), vol. 32, No. 6, pp. 727-736.
W.B. Pennebaker, J.L. Mitchell, G.G. Langdon, Jr., R.B. Arps, “An Overview of the Basic Principles of the Q-Coder Adaptive Binary Arithmetic Coder,”IBM J. Res. Develop.(Nov. 1988), vol. 32, No. 6, pp. 717-726.
R.B. Arps, T.K. Truong, D.J. Lu, R.C. Pasco, T.D. Friedman, “A Multi-Purpose VLSI Chip for Adaptive Data Compression of Bilevel Images,”IBM J. Res. Develop.(Nov. 1988), vol. 32, No. 6, pp. 775-795.
M.J. Slattery, J.L. Mitchell, “The Qx-coder,”IBM J. Res. Develop.(Nov. 1998), vol. 42, No. 6, pp. 767-784.
T.C. Bell, J.G. Cleary, I.H. Witten, “Text Compression,” Prentice Hall PTR (1990), ISBN 0-13-911991-4, Chapter 8, Dictionary Techniques, pp. 206-243.
J. Banks, “Integrated Circuit Cards (ICCs) and Optical Memory Cards (OMCs) Hold a Lot in Store,”ISO Bulletin(Nov. 1993), vol. 24, No. 11, pp. 9-11.
R. Hunter, A.H. Robinson, “International Digital Facsimile Coding Standards,” (Invited Paper)Proceedings of the IEEE, Special Issue on digital encoding of graphics(Jul. 1980), vol. 68, No. 7, pp. 854-867.
D.A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,”Proceedings of the I.R.E.(Sep. 1952), vol. 40, No. 9, pp. 1098-1101.
W.B. Pennebaker, J.L. Mitchell, “A Fast-Moving International Standard for Still Image Compression,”ISO Bulletin(Nov. 1993), vol. 24, No. 11, pp. 2-8.

Affiliated with

Also associated with

Rating

Reentry into compressed data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reentry into compressed data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reentry into compressed data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3433067