Patent US4729034A successfully refreshed from Google Patents.
US4729034A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for selection of a coding reference line for two-dimensional coding of image data representing screened images
Assignee: CMCE DATACOM Inc
•
Filing: 1985-06-27
•
Granted: 1988-03-01
•
Expires: 2005-06-27
Abstract
Abstract A method and apparatus for selecting a reference scan line for two-dimensional image coding preferably compatible with known facsimile transmission equipment are disclosed. Selection of a reference scan line in accordance with the method and apparatus of the invention allows data compression for facsimile transmission so that the cost for use of the communication link is reduced. More than one previous scan line is considered as a candidate reference scan line. A reference scan line is selected from among a plurality of previous scan lines, for example, the immediately preceding ten scan lines. The preselected or adaptively selected scan line among the multiple prior scan lines, more particularly, the previous scan line which is most similar to the current scan line to be coded, is selected as the reference scan line. The reference scan line is then fed with the current scan line to be coded to a two-dimensional data compression coding process so as to yield optimum data compression. This reduces the amount of image data transmitted and lowers the cost of operation of the facsimile transmission apparatus. The method and apparatus are particularly effective for compressing image data representing screened pictorial images.
Inventors
- 👤 Lawrence G. Roberts
- 👤 Alex E. Henderson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 04:13
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; H04N1/4105; H04N1/411; H04N1/413; H04N1/417; H04N1/4175
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
157 words
A method for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first scan line, a second scan line immediately preceding said first scan line, and a third scan line preceding said first scan line, said method comprising the steps of: establishing said first scan line as a current scan line; and selecting a reference scan line while examining said image data on the bases of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among said preceding second scan line and said preceding third scan line, and said current scan line and said reference scan line being for use in connection with a two-dimensional image coding process wherein data compression is directly related to a pattern relationship between said current scan line and said reference scan line.
Claim 2
Independent Claim
157 words
A method for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first scan line, a second scan line immediately preceding said first scan line, and a third scan line preceding said first scan line, said method comprising the steps of: establishing said first scan line as a current scan line; and selecting a reference scan line while examining said image data on the bases of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among said preceding second scan line and said preceding third scan line, and said current scan line and said reference scan line being for use in connection with a two-dimensional image coding process wherein data compression is directly related to a pattern relationship between said current scan line and said reference scan line.
Claim 3
Dependent Claim
90 words
The method of claim 1 wherein said selecting step comprises: comparing said current scan line with each one of at least two candidate scan lines selected from ones of said input scan lines preceding said current scan line to obtain pattern relationship criteria, said candidate scan lines including said preceding second scan line and said preceding third scan line; and choosing as said reference scan line the one of said candidate scan lines which yields a most desired one of said pattern relationship criteria relative to said current scan line.
Claim 4
Dependent Claim
26 words
The method of claim 2 wherein said pattern relationship criteria are correlations between recurring image patterns in said candidate scan lines and said current scan line.
Claim 5
Dependent Claim
20 words
The method of claim 2 wherein said pattern relationship criteria are metrics indicative of code representations of said image data.
Claim 6
Dependent Claim
100 words
The method of claim 4 wherein said comparing step comprises: applying a vertical mode coding technique to said current scan line using each of said candidate scan lines as a coding reference for said current scan line to obtain compressed image data comprising output bits; and determining the number of output bits obtained in said applying step by using each of said candidate scan lines as a coding reference for said current scan line; and wherein said choosing step comprises: selecting as said reference scan lines the candidate scan line for which the least number of outputs bits was obtained.
Claim 7
Dependent Claim
53 words
The method of claim 2 wherein said comparing step comprises: summing differences between image data of said current scan line and corresponding image data for each said candidate scan line; and wherein said choosing step comprises: selecting as said reference scan line the candidate scan line yielding the least number of said differences.
Claim 8
Dependent Claim
30 words
The method of claim 6 wherein said comparing step further comprises: exclusive-OR combining image data of each said candidate scan line with corresponding image data of said current scan line.
Claim 9
Dependent Claim
49 words
The method of claim 7 wherein said selecting step includes selecting as said reference scan line the candidate scan line producing said least number of said differences and which more closely precedes said current scan line than any other candidate scan line producing said least number of said differences.
Claim 10
Independent Claim
158 words
An apparatus for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first scan line, a second scan line immediately preceding said first scan line, and a third scan line preceding said first scan line, said apparatus comprising: means for establishing said first scan line as a current scan line; and means for selecting a referene scan line while examining said image data on the basis of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among said proceeding second scan line and said preceding third scan line, and said current scan line and said reference scan line being for use in connection with a two-dimensional image coding process wherein data compression is directly related to a pattern relationship between said current scan line and said reference scan line.
Claim 11
Independent Claim
158 words
An apparatus for processing image data for data compression, said image data comprising pixels and representing a two-dimensional screened image, said image data defining successive input scan lines, including a first scan line, a second scan line immediately preceding said first scan line, and a third scan line preceding said first scan line, said apparatus comprising: means for establishing said first scan line as a current scan line; and means for selecting a referene scan line while examining said image data on the basis of the size or frequency of occurrence of said pixels of said image data, said reference scan line being selected from among said proceeding second scan line and said preceding third scan line, and said current scan line and said reference scan line being for use in connection with a two-dimensional image coding process wherein data compression is directly related to a pattern relationship between said current scan line and said reference scan line.
Claim 12
Dependent Claim
94 words
The apparatus of claim 9 wherein said selecting means comprises: means for comparing said current scan line with each one of at least two candidate scan lines selected from ones of said input scan lines preceding said current scan line to obtain pattern relationship criteria, said candidate scan lines including said preceding second scan line and said preceding third scan line; and means for choosing as said reference scan line the one of said candidate scan lines which yields a most desired one of said pattern relationship criteria relative to said current scan line.
Claim 13
Dependent Claim
26 words
The apparatus of claim 10 wherein said pattern relationship criteria are correlations between recurring image patterns in said candidate scan lines and said current scan line.
Claim 14
Dependent Claim
20 words
The apparatus of claim 10 wherein said pattern relationship criteria are metrics indicative of code representations of said image data.
Claim 15
Dependent Claim
105 words
The apparatus of claim 10 wherein said comparing means comprises: means for applying a vertical mode coding technique to said current scan line using each of said candidate scan lines as a coding reference for said current scan line to obtain compressed image data comprising output bits; and means for determining the number output bits obtained by said applying means by using each of said candidate scan lines as a coding reference for said current scan line; an wherein said choosing means comprises means for selecting as said reference scan line the candidate scan line for which the least number of output bits was obtained.
Claim 16
Dependent Claim
57 words
The apparatus of claim 10 wherein said comparing means comprises: means for summing differences between image data of said current scan line and corresponding image data for each said candidate scan line; and wherein said choosing means comprises: means for selecting as said reference scan line the candidate scan line yielding the least number of said differences.
Claim 17
Dependent Claim
34 words
The apparatus of claim 18 wherein said comparing means further comprises: exclusive-OR means operative to combine image data of each said candidate scan line with corresponding image data of each said current scan line.
Claim 18
Dependent Claim
51 words
The method of claim 15 wherein said selecting means includes means for selecting as said reference scan line the candidate scan line producing said least number of said difference and which more closely precedes said current scan line than any other candidate scan line producing said least number of said differences.
References Cited (Backward Citations)
US4144547A
Cited
US4215375A
Cited
US4425582A
Cited
JPS57190461A
Cited
US4511213A
Cited
US4571634A
Cited
JPS592485A
Cited
US4633325A
Cited
US4559563A
Cited
US4667251A
Cited
US4631521A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-03-01 | 1991-08-31 | 1992-03-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-03-01 | 1995-08-31 | 1996-03-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-03-01 | 1999-08-31 | 2000-03-01 | $7700.00 | Window Closed / Lapsed |