US4837848A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for selecting a reference line for image data compression
Assignee: CMCE DATACOM Inc
•
Filing: 1987-03-27
•
Granted: 1989-06-06
•
Expires: 2007-03-27
Abstract
Abstract An apparatus for selecting a reference line for image data compression including a plurality of mutually connected reference selector chips for selecting a reference scan line from vertical mode coding of image data. The reference selector chips select a reference scan line from a plurality of preceding scan lines in exclusive or combination of the image data of each candidate reference scan line with the image data from the input scan line. The candidate reference scan line that has the lowest number of dissimilar bits is selected as the reference scan line. Each candidate reference scan line has associated therewith a register having bit positions arranged from the highest order bit position to a lowest order bit position for storing a binary sum of the number of dissimilar bits. When the sums are compared, the binary value and successive bit positions are compared from the highest order bit position to the lowest order bit position. When the binary value for a compared bit position of a register is greater than the binary value in the corresponding bit position of another register, each reference selector chip generates a losing signal for indicating that the register lost the arbitration. When the lowest order bit position of a register is not greater than the lowest order bit position of any other register and no losing signal was generated for the register, the associated chip generates a winning signal for indicating which candidate reference scan line had the least number of bits dissimilar to the corresponding bits in the input scan line. Each chip further includes a circuit for establishing a priority among the candidate reference scan lines so that two registers both having the smallest binary sum will not create a deadlock.
Inventors
- 👤 Alex E. Henderson
- 👤 Frederick L. Drain
- 👤 Lawrence G. Roberts
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 20:12
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417; H04N1/4175
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
227 words
In an image processing system wherein an image is represented by a series of image scan lines, each image scan line in turn being represented by a series of bits, and wherein an image scan line is communicated from one image processing element to another image processing element by encoding the image scan line in a compressor using a reference image scan line, an apparatus for selecting a reference image scan line from a plurality of candidate reference image scan lines comprising: means for receiving a plurality of candidate reference image scan lines; means for receiving an image scan line to be encoded; means for simultaneously comparing the bits from the image scan line to be encoded with corresponding bits from a plurality of candidate reference image scan lines; means, connected to the comparing means, for counting the number of bits in each candidate image scan line unequal to the corresponding bits in the image scan line to be encoded; means, connected to the counting means, for determining which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded; and means, connected to the determining means, for indicating which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 2
Dependent Claim
227 words
In an image processing system wherein an image is represented by a series of image scan lines, each image scan line in turn being represented by a series of bits, and wherein an image scan line is communicated from one image processing element to another image processing element by encoding the image scan line in a compressor using a reference image scan line, an apparatus for selecting a reference image scan line from a plurality of candidate reference image scan lines comprising: means for receiving a plurality of candidate reference image scan lines; means for receiving an image scan line to be encoded; means for simultaneously comparing the bits from the image scan line to be encoded with corresponding bits from a plurality of candidate reference image scan lines; means, connected to the comparing means, for counting the number of bits in each candidate image scan line unequal to the corresponding bits in the image scan line to be encoded; means, connected to the counting means, for determining which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded; and means, connected to the determining means, for indicating which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 3
Dependent Claim
63 words
The apparatus according to claim 1 further comprising: means for establishing a unique priority for each candidate reference image scan line; and wherein the indicating means includes means, connected to the priority establishing means, for indicating the highest priority candidate reference image scan line having a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 4
Dependent Claim
26 words
The apparatus according the claim 2 wherein the candidate reference image scan lines comprise the 10 image scan lines preceding the image scan to be encoded.
Claim 5
Dependent Claim
67 words
The apparatus according to claim 2 wherein the counting means includes a register associated with each candidate reference image scan line and having bit positions arranged from the highest order bit position to a lowest order bit position for storing a binary sum of the number of bits in each candidate image scan line unequal to the corresponding bits in the image scan line to be encoded.
Claim 6
Dependent Claim
46 words
The apparatus according to claim 4 wherein the indicating means includes means for indicating when a prescribed register corresponds to the highest priority candidate reference image scan line having a least number of bits unequal to the corresponding bits in the image scan to be encoded.
Claim 7
Dependent Claim
22 words
The apparatus according to claim 3 further comprising: means for selectively placing a binary value into a bit position of each register.
Claim 8
Dependent Claim
20 words
The apparatus according to claim 4 wherein the determining means includes means for comparing a binary sum in each register.
Claim 9
Dependent Claim
39 words
The apparatus according to claim 7 wherein the binary sum comparing means includes means for sequentially comparing the binary value in successive bit positions of each register from the highest order but position to the lowest order bit position.
Claim 10
Dependent Claim
49 words
The apparatus according to claim 8 wherein the binary sum comparing means includes means for generating a losing signal for a selected register when the binary value in a compared bit position of that register is greater than the binary value in a compared bit position of another register.
Claim 11
Dependent Claim
51 words
The apparatus according to claim 9 wherein the indicating means includes means for generating a winning signal when the binary value in the lowest order bit position of a register is not greater than the lowest order bit position of another register and no losing signal was generated for that register.
Claim 12
Dependent Claim
61 words
The apparatus according to claim 10 further comprising means, connected to the image scan line receiving means, to the candidate reference image scan line receiving means, and to the indicating means for communicating to the compressor the image scan line to be encoded and the candidate reference image scan line corresponding to the register for which a winning signal is generated.
Claim 13
Dependent Claim
36 words
The apparatus according to claim 9 wherein the losing signal generating means generates the losing signal for the selected register for each successive bit position comparison after the losing signal is initially generated for that register.
Claim 14
Dependent Claim
67 words
The apparatus according to claim 1 further comprising means, connected to the image scan line receiving means, to the candidate reference image scan line receiving means, and to the indicating means, for outputting both the image scan line to be encoded and a candidate reference image scan line having a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 15
Dependent Claim
187 words
In an image processing system wherein an image is represented by a series of image scan lines, each image scan line in turn being represented by a series of bits, and wherein an image scan line is communicated from one image processing element to another image processing element by encoding the image scan line in a compressor using a reference image scan line, a method of selecting a reference image scan line from a plurality of candidate reference image scan lines comprising the steps of: simultaneously comparing the bits from the image scan line to be encoded with corresponding bits from a plurality of candidate reference image scan lines; counting the number of bits in each candidate reference image scan line unequal to the corresponding bits in the image scan line to be encoded; determining which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded; and indicating which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 16
Dependent Claim
187 words
In an image processing system wherein an image is represented by a series of image scan lines, each image scan line in turn being represented by a series of bits, and wherein an image scan line is communicated from one image processing element to another image processing element by encoding the image scan line in a compressor using a reference image scan line, a method of selecting a reference image scan line from a plurality of candidate reference image scan lines comprising the steps of: simultaneously comparing the bits from the image scan line to be encoded with corresponding bits from a plurality of candidate reference image scan lines; counting the number of bits in each candidate reference image scan line unequal to the corresponding bits in the image scan line to be encoded; determining which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded; and indicating which candidate reference image scan line has a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 17
Dependent Claim
50 words
The method according to claim 14 further comprising the steps of: establishing a unique priority for each candidate reference image scan line; and indicating the highest priority candidate image scan line having a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 18
Dependent Claim
45 words
The method according to claim 15 further comprising the step of indicating when a prescribed register corresponds to the highest priority candidate reference image scan line having a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
Claim 19
Dependent Claim
23 words
The method according to claim 16 further comprising the step of selectively placing a binary value into a bit position of each register.
Claim 20
Dependent Claim
18 words
The method according to claim 16 further comprising the step of comparing a binary sum in each register.
Claim 21
Dependent Claim
34 words
The method according to claim 18 further comprising the step of comparing a binary value in successive bit positions of each register from the highest order bit position to the lowest order bit position.
Claim 22
Dependent Claim
45 words
The method according to claim 19 further comprising the step of generating a losing signal for a selected register when the binary value in a compound bit position of that register is greater than the binary value in a compared bit position of another register.
Claim 23
Dependent Claim
49 words
The method according to claim 20 further comprising the step of generating a winning signal when the binary value in the lowest order bit position of a register is not greater than the lowest order bit position of another register and no losing signal was generated for that register.
Claim 24
Dependent Claim
37 words
The method according to claim 21 further comprising communicating to the compressor the image scan line to be encoded and the candidate reference image scan line corresponding to the register of which a winning signal is generated.
Claim 25
Dependent Claim
35 words
The method according to claim 20 further comprising the step of generating the losing signal for the selected register for each successive bit position comparison after the losing signal is initially generated for that register.
Claim 26
Dependent Claim
46 words
The method according to claim 14 further comprising the step of outputting both the image scan line to be encoded and a candidate reference image scan line having a least number of bits unequal to the corresponding bits in the image scan line to be encoded.
References Cited (Backward Citations)
US4204232A
Cited
US4288782A
Cited
US4439840A
Cited
US4513440A
Cited
US4566128A
Cited
US4651341A
Cited
US4654719A
Cited
US4630306A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-06-05 | 1992-12-05 | 1993-06-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-06-05 | 1996-12-05 | 1997-06-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-06-05 | 2000-12-05 | 2001-06-06 | $7700.00 | Window Closed / Lapsed |