US4369463A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Gray scale image data compression with code words a function of image history
Assignee: International Business Machines Corp
•
Filing: 1981-06-04
•
Granted: 1983-01-18
•
Expires: 2001-06-04
Abstract
Abstract The present invention relates to a method and apparatus for compacting gray-scale image data which maintains extremely good picture quality and can result in typical images in a compression ratio of 5 to 1 and even better if a final step of arithmetic coding is used. The method is a special application of adaptive differential pulse code modulation (DPCM) which utilizes a prediction of smoothness surrounding a current pel to determine variable length codes to convey the quantized error. Thus, a continuously adaptive variable length code is produced which may be accurately decoded without using any further marker (code indicator) bits. For each pel and "error bit" is generated to indicate to the decoder if the predicted quantization range is adequate. These eroror bits can be further significantly compressed. This method permits the use of a "zero bit" per pel mode for the data transmission (1 "error bit" per pel actually transmitted) and provides for the automatic detection of the particular variable length compression code utilized for transmitting the quantized error (E Y ) for a particular pel. Utilizing the concepts of the present invention the inventors have obtained compression rates of approximately 1.5 bits per pel that produce a gray scale image at the decoding end of such a data transmission or storage system which has excellent quality (equal to 5 bit DPCM). By adding the concept of arithmetic coding to the previously set forth method, due to the nature of the statistical distribution of said special purpose error bit patterns, a compressed data set of less than 1 bit per pel has been achieved. This was produced from an original 8 bit per pel gray scale image.
Inventors
- 👤 Dimitris Anastassiou
- 👤 Joan L. Mitchell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 04:45
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/124; H04N19/50; H04N19/13; H04N19/60; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
114 words
A method for compressing gray scale image data comprising: predicting the gray scale value of a current pel which is to be processed, utilizing the values of previously processed pels. predicting a range of values, by a smoothness determination, which should suffice for coding the current pel's quantized error, determining the minimum range of values which are actually needed to accurately encode the quantized error for the pel, producing a first special purpose code bit when the predicted range of values for coding the quantized error is sufficient and a different bit when it is insufficient, and generating a code word for indicating the required quantization value for modification of the predicted pel value.
Claim 2
Independent Claim
114 words
A method for compressing gray scale image data comprising: predicting the gray scale value of a current pel which is to be processed, utilizing the values of previously processed pels. predicting a range of values, by a smoothness determination, which should suffice for coding the current pel's quantized error, determining the minimum range of values which are actually needed to accurately encode the quantized error for the pel, producing a first special purpose code bit when the predicted range of values for coding the quantized error is sufficient and a different bit when it is insufficient, and generating a code word for indicating the required quantization value for modification of the predicted pel value.
Claim 3
Dependent Claim
45 words
A data compression method as set forth in claim 1, including determining that no quantization of the predicted gray scale value is necessary and producing said first special purpose code bit in response thereto and producing no quantized error code indication of a quantization correction.
Claim 4
Dependent Claim
33 words
A method for compressing gray scale image data as set forth in claim 2 including further compacting the resultant code stream by arithmetically encoding said special purpose bits and the quantized error bits.
Claim 5
Independent Claim
121 words
A method for compressing gray scale image data which comprises the steps of: predicting the gray scale value of a current pel which is to be processed, utilizing the generated gray scale values of previously processed pels, predicting the number of bits which should suffice for encoding the quantized error for correcting the predicted gray scale pel value to approximately the true value of the current pel, determining the minimum number of bits which are actually needed to encode the quantized error, producing a first, special purpose code bit when the predicted number of bits for encoding the quantized error is sufficient and a different bit when it is insufficient, and generating the indicated variable length code for said quantized error.
Claim 6
Independent Claim
121 words
A method for compressing gray scale image data which comprises the steps of: predicting the gray scale value of a current pel which is to be processed, utilizing the generated gray scale values of previously processed pels, predicting the number of bits which should suffice for encoding the quantized error for correcting the predicted gray scale pel value to approximately the true value of the current pel, determining the minimum number of bits which are actually needed to encode the quantized error, producing a first, special purpose code bit when the predicted number of bits for encoding the quantized error is sufficient and a different bit when it is insufficient, and generating the indicated variable length code for said quantized error.
Claim 7
Dependent Claim
57 words
A method for compressing gray scale image data as set forth in claim 4 including determining that no quantized error is necessary for coding a particular pel, producing said first special purpose code bit in response thereto, and proceeding to evaluate the next pel to be transmitted without generating a quantized error code for said previous pel.
Claim 8
Dependent Claim
137 words
A data compression system for compressing gray scale image data which comprises first prediction means for predicting the gray scale value of a current pel which is to be transmitted, utilizing the values of previously transmitted pels. second prediction means for predicting the code which should suffice for transmitting the quantized error for correcting the predicted pel gray scale value to approximately the true value of said pel, means for determining the code which is actually needed to encode the quantized error, means for producing a first special purpose code bit when the predicted range of codes for encoding the quantized error is sufficient and a different bit when it is insufficient, and means for generating a first quantized error code when the predicted range of codes is sufficient and a second code when it is insufficient.
Claim 9
Dependent Claim
137 words
A data compression system for compressing gray scale image data which comprises first prediction means for predicting the gray scale value of a current pel which is to be transmitted, utilizing the values of previously transmitted pels. second prediction means for predicting the code which should suffice for transmitting the quantized error for correcting the predicted pel gray scale value to approximately the true value of said pel, means for determining the code which is actually needed to encode the quantized error, means for producing a first special purpose code bit when the predicted range of codes for encoding the quantized error is sufficient and a different bit when it is insufficient, and means for generating a first quantized error code when the predicted range of codes is sufficient and a second code when it is insufficient.
Claim 10
Dependent Claim
55 words
An image data compression system as set forth in claim 6 wherein said second prediction means includes means for determining what quantized error is necessary to map to the required quantization value of a predetermined quantization characteristic in order to generate the best possible coded approximation of the gray scale value of the current pel.
Claim 11
Dependent Claim
41 words
A data compression system as set forth in claim 6, said means for predicting the gray scale value of the pel including means for storing the generated gray scale values for a plurality of predetermined history pels produced by the system.
Claim 12
Dependent Claim
43 words
A data compression system as set forth in claim 8 wherein said means for predicting the code which should suffice for generating the quantized error includes means for storing the quantized error which was actually generated for said plurality of pre-determined history pels.
Claim 13
Dependent Claim
50 words
A data compresssion system as set forth in claim 9 wherein said means further includes microprocessor means for selecting the largest of the quantized error signals of said history pels and an indication of the range of codes which should suffice for encoding the quantized error for the current pel.
Claim 14
Independent Claim
220 words
A system for compressing and decompressing gray scale image data which comprises, compression means including first prediction means for predicting the gray scale value of a current pel which is to be transmitted, utilizing the values of previously transmitted adjacent pels, second prediction means for predicting the code which should suffice for transmitting the quantized error for correcting the predicted pel gray scale value to approximately the true value of said pel, means for determining the code which is actually needed to encode the quantized error, means for producing a first special purpose code bit when the predicted range of codes for emcoding the quantized error is sufficient and a different bit when it is insufficient, and means for generating a first quantized error code when the predicted range of codes is sufficient and a second code when it is insufficient, and means for decompressing said compressed code comprising a first and second prediction means substantially identical to those in said compression means. means responsive to the output of said first and second prediction means for decoding the quantized error from the compressed message stream, means for producing other required quantization value from the decoded quantized error and, means for generating the decompressed gray scale value Y from the output of said first prediction means and the derived quantization value.
Claim 15
Independent Claim
220 words
A system for compressing and decompressing gray scale image data which comprises, compression means including first prediction means for predicting the gray scale value of a current pel which is to be transmitted, utilizing the values of previously transmitted adjacent pels, second prediction means for predicting the code which should suffice for transmitting the quantized error for correcting the predicted pel gray scale value to approximately the true value of said pel, means for determining the code which is actually needed to encode the quantized error, means for producing a first special purpose code bit when the predicted range of codes for emcoding the quantized error is sufficient and a different bit when it is insufficient, and means for generating a first quantized error code when the predicted range of codes is sufficient and a second code when it is insufficient, and means for decompressing said compressed code comprising a first and second prediction means substantially identical to those in said compression means. means responsive to the output of said first and second prediction means for decoding the quantized error from the compressed message stream, means for producing other required quantization value from the decoded quantized error and, means for generating the decompressed gray scale value Y from the output of said first prediction means and the derived quantization value.
Claim 16
Dependent Claim
43 words
A data compression and decompression system as set forth in claim 11, said means for predicting the gray scale value of the pel including means for storing the generated gray scale values for a plurality of predetermined history pels produced by the system.
Claim 17
Dependent Claim
47 words
A data compression and decompression system as set forth in claim 12 wherein said second prediction means for predicting the code which should suffice for generating the quantized error includes means for storing the quantized error which was actually generated for said plurality of pre-determined history pels.
Claim 18
Dependent Claim
87 words
A data compression and decompression system as set forth in claim 13 wherein said second prediction means includes means for predicting the number of code bits for generating the proper quantized error code for the current pel, means for determining the actual number of bits necessary to generate the proper quantized error code and, means for predicting said first special purpose bit when the predicted number of bits is adequate to encode the proper quantized error whereby a continuously adaptable fixed length quantized error code is produced.
Claim 19
Dependent Claim
37 words
A data compression and decompression system as set forth in claim 14 wherein said means for operating said second quantized error code includes means for generating a variable length compression code representative of the required quantized error.
Claim 20
Dependent Claim
57 words
A data compression and decompression system as set forth in claim 15 wherein said second prediction means further includes microprocessor means for selecting the largest of the quantized error signals of said history pels and for determining as a function thereof the number of bits which should suffice for encoding the quantized error for the current pel.
Claim 21
Dependent Claim
38 words
A method for compressing gray scale image data as set forth in claim 3 including arithmetically coding the special purpose bits using a first probability model and arithmetically coding any quantized error bits using a second probability model.
Claim 22
Dependent Claim
51 words
A method for compressing gray scale image data as set forth in claim 17 including coding said special purpose bits utilizing an adaptive probability determination involving determining the MODE related to the particular special purpose bit and the total image history up to that point where the same MODE was used.
Claim 23
Dependent Claim
33 words
A data compression and decompression system as set forth in claim 16 including means for arithmetically coding and decoding the resultant message comprising the special purpose bits, and bits coding the quantized error.
Claim 24
Dependent Claim
44 words
A data compression and decompression system as set forth in claim 19 wherein said arithmetic coding and decoding means utilizes a first probability model for coding and decoding the special purpose bits and a second model for coding and decoding the quantized error bits.
Claim 25
Dependent Claim
44 words
A data compression and decompression system as set forth in claim 20 wherein said means for arithmetic coding and decoding includes means for maintaining for a particular image, the MODE history statistics for each MODE and for determining the MODE for a current pel.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1986-01-17 | 1986-07-19 | 1987-01-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-01-17 | 1990-07-19 | 1991-01-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-01-17 | 1994-07-19 | 1995-01-18 | $7700.00 | Window Closed / Lapsed |