US4399467A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for image data compression and decompression
Assignee: NCR Canada Ltd
•
Filing: 1981-10-13
•
Granted: 1983-08-16
•
Expires: 2001-10-13
Abstract
Abstract A data compression system which generates several types of symbols from bands of data derived from the digital image. Each group of data bits located in the same bit position across the data band is represented by a mode symbol, which signifies the decimal value of the binary combination of the data contained in that group. The mode symbol is followed by a run symbol, which represents the number of times or incremental positions that the same mode occurs successively until a different mode is generated. Mode and run symbols are transmitted in alternation, with each mode symbol followed by its corresponding run symbol, to an encoder, which generates variable length code words that are transmitted to a receiving station and decoded to provide symbols which are used to form a facsimile image. In one embodiment of this system, the mode and run symbols are combined to form a different type of symbol, known as a ternary octade symbol, to further improve the compression performance of the system.
Inventors
- 👤 Ambati Subramaniam
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 04:38
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/415
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
169 words
An apparatus for the processing of digital data derived from an image, comprising: means for separating said digital data into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; first means for generating a plurality of first symbols, with each of said first symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; second means for generating a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated first symbol; third means for generating a plurality of third symbols, with each of said third symbols comprising a section of data representing a first symbol and a section of data representing a second symbol, where said second symbol is associated with said first symbol; and means for generating a plurality of code words representative of each of said third symbols.
Claim 2
Independent Claim
169 words
An apparatus for the processing of digital data derived from an image, comprising: means for separating said digital data into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; first means for generating a plurality of first symbols, with each of said first symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; second means for generating a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated first symbol; third means for generating a plurality of third symbols, with each of said third symbols comprising a section of data representing a first symbol and a section of data representing a second symbol, where said second symbol is associated with said first symbol; and means for generating a plurality of code words representative of each of said third symbols.
Claim 3
Dependent Claim
29 words
The apparatus of claim 1, wherein said separating means includes a plurality of first storage means, each capable of storing a predetermined number of scan lines from said image.
Claim 4
Dependent Claim
44 words
The apparatus of claim 1, wherein said first means includes second storage means for storing a single first symbol, and comparison means, coupled to the input and output of said second storage means, for generating a first signal when successive first symbols are identical.
Claim 5
Dependent Claim
21 words
The apparatus of claim 3, wherein said second means is incremented upon generation of said first signal from said comparison means.
Claim 6
Dependent Claim
15 words
The apparatus of claim 1, wherein said first and second symbols consist of binary digits.
Claim 7
Dependent Claim
37 words
The apparatus of claim 1, wherein said third means includes first ternary encoding means for transforming said first symbols into first ternary symbols, and second ternary encoding means for transforming said second symbols into second ternary symbols.
Claim 8
Dependent Claim
57 words
The apparatus of claim 6, wherein said third means further includes means for generating a third ternary symbol, with each of said third ternary symbols comprising a section of data representing a first ternary symbol and a section of data representing a second ternary symbol, where said second ternary symbol is associated with said first ternary symbol.
Claim 9
Independent Claim
234 words
An apparatus for the processing of digital data derived from an image, comprising: means for separating said digital data into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; first formation means, coupled to said separating means, for forming a plurality of first symbols, with each of said first symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; counting means, responsive to said first formation means, for generating a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated first symbol within said first formation means; second formation means, coupled to said first formation means and said counting means, for forming a plurality of third symbols, with each of said third symbols comprising a section of data representing a first symbol from said first formation means and a section of data representing a second symbol from said counting means, where said second symbol is associated with said first symbol; first storage means for storing a plurality of code words which are representative of each of said third symbols; means for causing the generation of code words from said first storage means; and means for outputting said generated code words over a transmission medium.
Claim 10
Independent Claim
234 words
An apparatus for the processing of digital data derived from an image, comprising: means for separating said digital data into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; first formation means, coupled to said separating means, for forming a plurality of first symbols, with each of said first symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; counting means, responsive to said first formation means, for generating a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated first symbol within said first formation means; second formation means, coupled to said first formation means and said counting means, for forming a plurality of third symbols, with each of said third symbols comprising a section of data representing a first symbol from said first formation means and a section of data representing a second symbol from said counting means, where said second symbol is associated with said first symbol; first storage means for storing a plurality of code words which are representative of each of said third symbols; means for causing the generation of code words from said first storage means; and means for outputting said generated code words over a transmission medium.
Claim 11
Dependent Claim
29 words
The apparatus of claim 8, wherein said separating means includes a plurality of second storage means, each capable of storing a predetermined number of scan lines from said image.
Claim 12
Dependent Claim
45 words
The apparatus of claim 8, wherein said first formation means includes third storage means for storing a single first symbol, and comparison means, coupled to the input and output of said third storage means, for generating a first signal when successive first symbols are identical.
Claim 13
Dependent Claim
21 words
The apparatus of claim 10, wherein said counting means is incremented upon generation of said first signal from said comparison means.
Claim 14
Dependent Claim
15 words
The apparatus of claim 8, wherein said first and second symbols consist of binary digits.
Claim 15
Dependent Claim
38 words
The apparatus of claim 8, wherein said second formation means includes first ternary encoding means for transforming said first symbols into first ternary symbols, and second ternary encoding means for transforming said second symbols into second ternary symbols.
Claim 16
Dependent Claim
58 words
The apparatus of claim 13, wherein said second formation means further includes means for generating a third ternary symbol, with each of said third ternary symbols comprising a section of data representing a first ternary symbol and a section of data representing a second ternary symbol, where said second ternary symbol is associated with said first ternary symbol.
Claim 17
Dependent Claim
14 words
The apparatus of claim 14, wherein said third ternary symbol comprises sixteen data bits.
Claim 18
Dependent Claim
27 words
The apparatus of claim 15, wherein said second formation means further includes means for compressing said third ternary symbol from sixteen data bits to thirteen data bits.
Claim 19
Dependent Claim
17 words
The apparatus of claim 16, wherein said compression means comprises a plurality of two bit full adders.
Claim 20
Dependent Claim
197 words
The apparatus of claim 8, further comprising: means for receiving said code words from said transmission medium; means, responsive to said receiving means, for storing said code words; symbol storage means for storing a plurality of fourth symbols which are representative of each of said code words, wherein each of said fourth symbols comprises a section of data representing said first symbol, and a section of data representing said second symbol; means for separating said fourth symbols into said first symbols and said second symbols; first conversion means for converting each of said first symbols into a series of data bits indicative of the data contained in a specific bit position in each of said scan lines within a data band; second conversion means for converting each of said second symbols to a number indicative of the consecutive occurrences of its associated first symbol within said first formation means; means for outputting from said first conversion means each of said series of data bits, wherein each of said series is outputted once for a number equal to the quantity stored within said second conversion means; and means for converting said data bits into a digital data image.
Claim 21
Dependent Claim
17 words
The apparatus of claim 18, wherein said means for separating said fourth symbols comprises a MODULO-3 adder.
Claim 22
Independent Claim
233 words
An apparatus for the processing of digital data derived from an image, comprising: means for separating said digital data into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; first formation means, coupled to said separating means, for forming a plurality of mode symbols, with each of said mode symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; counting means, responsive to said first formation means, for generating a plurality of run symbols, with each of said run symbols representing a number indicative of consecutive occurrences of an associated mode symbol within said first formation means; second formation means, coupled to said first formation means and said counting means, for forming a plurality of combination symbols, with each of said combination symbols comprising a section of data representing a mode symbol from said first formation means and a section of data representing a run symbol from said counting means, where said run symbol is associated with said mode symbol; first storage means for storing a plurality of code words which are representative of each of said combination symbols; means for causing the generation of code words from said storage means; and means for outputting said generated code words over a transmission medium.
Claim 23
Independent Claim
233 words
An apparatus for the processing of digital data derived from an image, comprising: means for separating said digital data into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; first formation means, coupled to said separating means, for forming a plurality of mode symbols, with each of said mode symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; counting means, responsive to said first formation means, for generating a plurality of run symbols, with each of said run symbols representing a number indicative of consecutive occurrences of an associated mode symbol within said first formation means; second formation means, coupled to said first formation means and said counting means, for forming a plurality of combination symbols, with each of said combination symbols comprising a section of data representing a mode symbol from said first formation means and a section of data representing a run symbol from said counting means, where said run symbol is associated with said mode symbol; first storage means for storing a plurality of code words which are representative of each of said combination symbols; means for causing the generation of code words from said storage means; and means for outputting said generated code words over a transmission medium.
Claim 24
Independent Claim
159 words
A method of processing digital data derived from an image, comprising the steps of: (a) separating said digital data into data bands, wherein each of said data bands comprises a predetermined number of scan lines from said image; (b) generating a plurality of first symbols, with each of said first symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; (c) generating a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated first symbol; (d) generating a pluralty of third symbols, with each of said third symbols comprising a section of data representing a first symbol and a section of data representing a second symbol, where said first symbol is associated with said second symbol; and (e) generating a plurality of code words representative of each of said third symbols.
Claim 25
Independent Claim
159 words
A method of processing digital data derived from an image, comprising the steps of: (a) separating said digital data into data bands, wherein each of said data bands comprises a predetermined number of scan lines from said image; (b) generating a plurality of first symbols, with each of said first symbols representative of a binary value of a series of data bits contained within a specific bit position in each of said scan lines within said data band; (c) generating a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated first symbol; (d) generating a pluralty of third symbols, with each of said third symbols comprising a section of data representing a first symbol and a section of data representing a second symbol, where said first symbol is associated with said second symbol; and (e) generating a plurality of code words representative of each of said third symbols.
Claim 26
Independent Claim
244 words
A method of processing digital data derived from an image, comprising the steps of: (a) receiving a continuous stream of data bits which are derived from said image; (b) storing a plurality of said data bits in a first storage means, wherein said first storage means separates said data bits into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; (c) forming a plurality of first symbols using said data bits from said first storage means, with each of said first symbols representing a binary value of a series of data bits contained in a specific bit position in each of said scan lines within said first storage means; (d) forming a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated second symbol within said first storage means; (e) forming a plurality of third symbols from said first and second symbols, where each of said third symbols contain a section of data representing said first symbol and a section of data representing said second signal, where said second signal is associated with said first symbol; (f) inputting each of said third symbols to a second storae means as an address thereof; (g) outputting from said second storage means a code word representative of each of said third symbols which are inputted; and (h) transmitting said code words over a transmission medium.
Claim 27
Independent Claim
244 words
A method of processing digital data derived from an image, comprising the steps of: (a) receiving a continuous stream of data bits which are derived from said image; (b) storing a plurality of said data bits in a first storage means, wherein said first storage means separates said data bits into a plurality of data bands, with each of said data bands comprising a predetermined number of scan lines from said image; (c) forming a plurality of first symbols using said data bits from said first storage means, with each of said first symbols representing a binary value of a series of data bits contained in a specific bit position in each of said scan lines within said first storage means; (d) forming a plurality of second symbols, with each of said second symbols representing a number indicative of consecutive occurrences of an associated second symbol within said first storage means; (e) forming a plurality of third symbols from said first and second symbols, where each of said third symbols contain a section of data representing said first symbol and a section of data representing said second signal, where said second signal is associated with said first symbol; (f) inputting each of said third symbols to a second storae means as an address thereof; (g) outputting from said second storage means a code word representative of each of said third symbols which are inputted; and (h) transmitting said code words over a transmission medium.
Claim 28
Dependent Claim
50 words
The method of claim 22, wherein the step of storing a plurality of said data bits in said first storage means comprises the step of further separating said data bits into a plurality of third storage means, each capable of storing a predetermined number of scan lines from said image.
Claim 29
Dependent Claim
29 words
The method of claim 23, wherein the step of forming a plurality of first symbols includes the steps transforming said first symbols into a plurality of first ternary symbols.
Claim 30
Dependent Claim
30 words
The method of claim 24, wherein the step of forming a plurality of second symbols includes the step of transforming said second symbols into a plurality of second ternary symbols.
Claim 31
Dependent Claim
53 words
The method of claim 25, wherein the step of forming a plurality of third symbols includes the steps of: (a) transforming said third symbols into a plurality of third ternary symbols, each of which contain sixteen data bits; (b) and compressing said third ternary symbols from sixteen data bits to thirteen data bits.
Claim 32
Dependent Claim
172 words
The method of claim 22, further comprising the steps of: (i) receiving said code words from said transmission medium, (j) storing said code words as they are received; (k) inputting said code words to a fourth storage means as an address thereof; (l) outputting from said fourth storage means a fourth symbol representative of each of said code words which are inputted; (m) separating each of said fourth symbols into a section representing said first symbol and an associated section representing said second symbol; (n) converting each of said first symbols into a series of data bits indicative of the data contained in a specific bit position in each of said scan lines within a data band; (o) converting each of said second symbols to a number indicative of the consecutive occurrences of its associated first symbol within said first storage means; (p) outputting once each of said series of data bits for each number of consecutive occurrences obtained in step (o); and (q) converting said data bits into a digital image.
References Cited (Backward Citations)
US3993862A
Cited
US4070694A
Cited
US4056828A
Cited
US4096526A
Cited
US4096520A
Cited
US4163260A
Cited
US4136363A
Cited
US4254438A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1986-08-15 | 1987-02-14 | 1987-08-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-08-15 | 1991-02-14 | 1991-08-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-08-15 | 1995-02-14 | 1995-08-16 | $7700.00 | Window Closed / Lapsed |