Patent US3813485A successfully refreshed from Google Patents.
US3813485A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for compression of digital data
Assignee: International Business Machines Corp
•
Filing: 1972-01-05
•
Granted: 1974-05-28
•
Expires: 1992-01-05
Abstract
Abstract A system for compressing or compacting data that is representative of scanned images. Involved are predictive coding of two level pictorial data, followed by run-length coding characterized by an infinite overflow capability. The predictive stage utilizes an nth-order exhaustive, causal predictor which looks at adjacent points of previous lines and preceding points of present lines to predict what color (black or white) the predictive is. If the prediction is in error, a binary one is transmitted. Alternatively, if the prediction is correct, a binary zero is transmitted. The run-length coding is adapted to code the run-lengths of binary zero between binary one errors using a dual-base counting system, where p represents one base (the number of low order subword states) and n represents a second base (the number of high order subword states) with a subword length, L, of log2 (p + n) bits. Mutually exclusive states in this run-length counting system provide an automatic comma for separating variable-length words (groups of subwords). A significant advantage of this type of run-length number system is that it provides a practical run-length encoding technique with the flexibility of variable-length overflow. The overall data compacting system also achieves a relatively high compression ratio for line drawings and other related type printed matter.
Inventors
- 👤 R Arps
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 06:13
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417; G; G06; G06T; G06T9/00; G06T9/004; G06T9/005
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
212 words
A system for compressing a stream of digital data representing an original image, said system comprising: an input stream of digital data representing said original image; an exhaustive, non-linear predictor stage having its input connected to said stream for predicting the value of a current picture element represented by said digital data, based on the values of adjacent previous picture elements represented by said digital data, said predictor stage including: means for comparing the output value of said predictor with the actual value of the current picture element, thereby to provide a stream of digital data representing a new image corrElated to errors produced by said predictor: and a run length encoder stage connected to the output of said predictor stage for encoding the new error correlated image, said run length encoder stage using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p+n) bits, where: p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords; and a buffer for receiving and storing the digital data after said data has been processed by said predictor and said run length encoder stages.
Claim 2
Independent Claim
212 words
A system for compressing a stream of digital data representing an original image, said system comprising: an input stream of digital data representing said original image; an exhaustive, non-linear predictor stage having its input connected to said stream for predicting the value of a current picture element represented by said digital data, based on the values of adjacent previous picture elements represented by said digital data, said predictor stage including: means for comparing the output value of said predictor with the actual value of the current picture element, thereby to provide a stream of digital data representing a new image corrElated to errors produced by said predictor: and a run length encoder stage connected to the output of said predictor stage for encoding the new error correlated image, said run length encoder stage using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p+n) bits, where: p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords; and a buffer for receiving and storing the digital data after said data has been processed by said predictor and said run length encoder stages.
Claim 3
Dependent Claim
13 words
The system of claim 1 wherein the subword length unit is 4 bits.
Claim 4
Dependent Claim
44 words
The system of claim 1 wherein said run-length encoding stage additionally includes: a first binary counter to the base p having a carry output, and a cascaded series of binary counters connected to said carry output, thereby providing an overflow capability for said stage.
Claim 5
Dependent Claim
13 words
The system of claim 1 wherein the subword length unit is 3 bits.
Claim 6
Dependent Claim
13 words
The system of claim 1 wherein the subword length unit is 5 bits.
Claim 7
Independent Claim
255 words
A system for compressing a stream of digital data representing an original image, said system comprising: an input stream of digital data representing said original image; an exhaustive, non-linear predictor stage having its input connected to said stream, said predictor stage including: first, second, and third registers for holding bits representative of adjacent picture elements of a previous scan line, a fourth register for holding bits representative of a picture element preceding a predictable picture element of a current scan line, a predictor unit for logically predicting the value of the predictable picture element of said current scan line based on the binary values of the bits held in the first, second, third and fourth registers of the predictor stage, a predictor register for receiving the output of said predictor logic unit, and means for comparing the output value of said predictor register with the actual value of said predictable picture element thereby to provide a stream of digital data representing a new image correlated to errors produced by said predictor stage; a run length encoder using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p+n) bits, where: p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords; and a buffer for receiving and storing the digital data after said data has been processed by said predictor and said run length encoder stages.
Claim 8
Independent Claim
255 words
A system for compressing a stream of digital data representing an original image, said system comprising: an input stream of digital data representing said original image; an exhaustive, non-linear predictor stage having its input connected to said stream, said predictor stage including: first, second, and third registers for holding bits representative of adjacent picture elements of a previous scan line, a fourth register for holding bits representative of a picture element preceding a predictable picture element of a current scan line, a predictor unit for logically predicting the value of the predictable picture element of said current scan line based on the binary values of the bits held in the first, second, third and fourth registers of the predictor stage, a predictor register for receiving the output of said predictor logic unit, and means for comparing the output value of said predictor register with the actual value of said predictable picture element thereby to provide a stream of digital data representing a new image correlated to errors produced by said predictor stage; a run length encoder using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p+n) bits, where: p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords; and a buffer for receiving and storing the digital data after said data has been processed by said predictor and said run length encoder stages.
Claim 9
Dependent Claim
18 words
The system of claim 6 wherein p 12, n 4, and the subword length unit is 4 bits.
Claim 10
Dependent Claim
18 words
The system of claim 6 wherein p 10, n 6, and the subword length unit is 4 bits.
Claim 11
Dependent Claim
34 words
The system of claim 6 additionally comprising: logic means connected to said run length encoder stage for selecting a predetermined otherwise unused subword combination in response to detection of a totally errorless scan line.
Claim 12
Dependent Claim
18 words
The system of claim 6 wherein p 5, n 3, and the subword length unit is 3 bits.
Claim 13
Independent Claim
178 words
A method for compressing digital data representative of images, said method comprising the steps of: generating an input stream of digital data representative of an original image, exhaustively and non-linearly predicting the value of a current picture element represented by said digital data, based on the value of at least one previous picture element represented by said digital data, comparing the output value of the Predicted current picture element with the actual value of the current picture element, thereby to provide a stream of digital data representing a new image correlated to errors produced by the output value of the predicted current picture element, and encoding the run lengths of errors to obtain an encoded new error correlated image, said encoding step using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p + n) bits, where: p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords.
Claim 14
Independent Claim
178 words
A method for compressing digital data representative of images, said method comprising the steps of: generating an input stream of digital data representative of an original image, exhaustively and non-linearly predicting the value of a current picture element represented by said digital data, based on the value of at least one previous picture element represented by said digital data, comparing the output value of the Predicted current picture element with the actual value of the current picture element, thereby to provide a stream of digital data representing a new image correlated to errors produced by the output value of the predicted current picture element, and encoding the run lengths of errors to obtain an encoded new error correlated image, said encoding step using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p + n) bits, where: p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords.
Claim 15
Dependent Claim
23 words
The method of claim 11, including the additional step of storing said predicted and run-length encoded data for selective reproduction of said images.
Claim 16
Independent Claim
216 words
A system for compressing a stream of digital data representing an original image, said system comprising: an input stream of digital data representing said original image; an exhaustive, non-linear causal predictor stage having its input connected to said stream for predicting the value of a current picture element represented by said digital data, based on the value of at least one previous picture element represented by said digital data, said predictor stage including: means for comparing the output value of said predictor with the actual value of the current picture element, thereby to provide a stream of digital data representing a new image correlated to errors produced by said predictor; and a run length encoder stage connected to the output of said predictor stage for encoding the new error correlated image, said run length encoder stage using a variable word length, which is a multiple of subwords of length L whose 2L possible stages are divided into two mutually-exclusive, unequal groups such that L log2 (p + n) bits, where p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords; and a buffer for receiving and storing the digital data after said data has been processed by said predictor and said run-length encoder stages.
Claim 17
Independent Claim
216 words
A system for compressing a stream of digital data representing an original image, said system comprising: an input stream of digital data representing said original image; an exhaustive, non-linear causal predictor stage having its input connected to said stream for predicting the value of a current picture element represented by said digital data, based on the value of at least one previous picture element represented by said digital data, said predictor stage including: means for comparing the output value of said predictor with the actual value of the current picture element, thereby to provide a stream of digital data representing a new image correlated to errors produced by said predictor; and a run length encoder stage connected to the output of said predictor stage for encoding the new error correlated image, said run length encoder stage using a variable word length, which is a multiple of subwords of length L whose 2L possible stages are divided into two mutually-exclusive, unequal groups such that L log2 (p + n) bits, where p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords; and a buffer for receiving and storing the digital data after said data has been processed by said predictor and said run-length encoder stages.
Claim 18
Dependent Claim
20 words
The system of claim 13 wherein subword the length unit for the (p, n) number system is any integer value.
Claim 19
Independent Claim
98 words
A method of compressing digital data representative of images, comprising the steps of: providing a stream of digital data representing an image, encoding the run lengths of said stream of data, by using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p + n) p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords, and storing said run-length encoded data for selective reproduction of said images.
Claim 20
Independent Claim
98 words
A method of compressing digital data representative of images, comprising the steps of: providing a stream of digital data representing an image, encoding the run lengths of said stream of data, by using a variable word length, which is a multiple of subwords of length L whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2 (p + n) p the number of states in the lowest order subwords n the number of states in successive higher and highest order subwords, and storing said run-length encoded data for selective reproduction of said images.
Claim 21
Dependent Claim
80 words
The method of claim 15 wherein: said encoding step specifically comprises using a variable word length, which is a multiple of said subwords of length L, wherein said length L comprises 4 binary bits, whose 2L possible states are divided into two mutually-exclusive, unequal groups such that L log2(p+n) bits, where: p 10, which is the number of states in the lowest order subwords and n 6, which is the number of states in successive higher and highest order subwords.
Claim 22
Dependent Claim
43 words
The method of claim 16 further comprising the additional steps of: specifically encoding special events from said data stream with predetermined unused subword combinations from said encoding step, said special events including ''''end of scan line,'''' ''''blank scan line'''' and ''''end of page.''''
Claim 23
Dependent Claim
52 words
The method of claim 17 wherein: said specially encoding step additionally comprises encoding another special event from said data stream with another predetermined unused subword combination from said encoding step to denote ''''totally errorless scan line/jump to to end of scan line'''' in place of the last run code in a line.
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) | 1977-05-27 | 1977-11-26 | 1978-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-05-27 | 1981-11-26 | 1982-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-05-27 | 1985-11-26 | 1986-05-28 | $7700.00 | Window Closed / Lapsed |