US3833900A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image compaction system
Assignee: International Business Machines Corp
•
Filing: 1972-08-18
•
Granted: 1974-09-03
•
Expires: 1992-08-18
Abstract
Abstract A data compaction system wherein segmented binary data that has redundancy between segments is compacted by means of differential run-length encoding. For compaction of document digitized data, the segments represent lines on the document. Black image points on the document which are represented by a ''''1'''' are coded relative to the position of a 1 appearing in the line above the one being coded. The differential distance between binary 1 bit positions on successive lines are coded in accordance with a compaction code. Codewords having a small number of bits are used for small differentials.
Inventors
- 👤 L Bahl
- 👤 D Barnea
- 👤 H Kobayashi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 02:47
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417; H04N1/4175
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
170 words
A system for encoding a binary message stream having a degree of redundancy comprising: means for segmenting said message stream into continuous blocks, each block having (N) bit positions; first locate means for locating the presence of binary 1''s in a block (i-1) and recording the bit position (j''l) associated with the binary 1''s present in block (i-1); second locate means for locating the presence of binary 1''s in a block (i) and recording the bit position (jk 1) associated with each binary 1 present in said blocK (i); integer generating means for computing an integer (I) as a function of the differential bit position distance between each binary 1 in said block (i) and its associated binary 1 in said block (i-1); codeword generating means receiving said integer (I) from said integer generating means for providing a unique codeword for each possible integer (I); output means for transmitting said codeword to a receiving station whereby the length of said codeword is dependent on the value of said integer I.
Claim 2
Independent Claim
170 words
A system for encoding a binary message stream having a degree of redundancy comprising: means for segmenting said message stream into continuous blocks, each block having (N) bit positions; first locate means for locating the presence of binary 1''s in a block (i-1) and recording the bit position (j''l) associated with the binary 1''s present in block (i-1); second locate means for locating the presence of binary 1''s in a block (i) and recording the bit position (jk 1) associated with each binary 1 present in said blocK (i); integer generating means for computing an integer (I) as a function of the differential bit position distance between each binary 1 in said block (i) and its associated binary 1 in said block (i-1); codeword generating means receiving said integer (I) from said integer generating means for providing a unique codeword for each possible integer (I); output means for transmitting said codeword to a receiving station whereby the length of said codeword is dependent on the value of said integer I.
Claim 3
Dependent Claim
25 words
The system as defined in claim 1 wherein said message represents a digitized document and said continuous blocks are continuous scan lines of said document.
Claim 4
Dependent Claim
185 words
The system as defined in claim 2 wherein said integer generating means comprises: means for computing the quantity (IB) in accordance with the relationship IB N-j''l, where (N) is the last bit position in a scan line and (j''l) is the bit position of a binary 1 in said line (i-1); means for computing the quantity (IA) in accordance with the relationship IA j''l - jk - 1, where jk is the bit position of the previous found binary 1 on line (i); means for computing the quantity (I1) in accordance with the relationship I1 jk 1 - j''l , where jk 1 is bit position of a presently found binary 1 on line (i); means for computing the quantity (I2) by selecting the minimum of the quantities (IA) and (IB); means for computing the integer (I) in accordance with the one of the relationships I 2I1 if I2 > or = I1 and jk 1 > j'' I 2I1 + 1 if I2 > or = I1 and jk 1 < or = j''l I I1 + I2 + 1 if I1 > I2.
Claim 5
Dependent Claim
62 words
The system as defined in claim 3 wherein said codeword generating means comprises: store means having a plurality of variable length codewords each identified with a unique index number; store look-up means for accessing one of said variable length codewords by using said integer (I) as an index to said store means and for providing the accessed codeword to said output means.
Claim 6
Dependent Claim
116 words
The system as defined in claim 4 wherein said receiving station comprises: means for receiving said codewords; means for determining the integer (I) corresponding to each received codeword; means for computing the bit position jk 1 from th integer (I) in accordance with one of the following relationships: jk 1 j''l - (I-1)/2 if I is ODD and I < or = 2I2+1 jk 1 j''l + I/2 if I is EVEN and I < or = 2I2+1 jk 1 j''l - I+I2+1 if IA > IB and I > 2I2+1 jk 1 j''l + I-I2-1 if IA < IB and I > 2I2+1; means for reconstructing the digitized document from said bit position jk 1.
Claim 7
Dependent Claim
134 words
A system as defined in claim 3 wherein said codeword generating means comprises: first shift register means for receiving said integer (I); second shift register means connected to said first shift register; control means for referentially shifting the binary representation of said integer (I) contained in said first shift register into said second shift register until only the high order bit remains in said first shift register; counter means connecTed to said control means for maintaining a count of the number of shifts executed; pulse output means associated with said counter for transmitting a binary 1 for each increment of said counter; means for transmitting a binary 0 after said pulse output means stops; said shift control means shifting the contents of said second shift register onto the output line following said binary 0.
References Cited (Backward Citations)
US2921124A
Cited
US3061672A
Cited
US3051778A
Cited
US3185823A
Cited
US3347981A
Cited
US3474442A
Cited
US3478266A
Cited
US3521241A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1977-09-02 | 1978-03-04 | 1978-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-09-02 | 1982-03-04 | 1982-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-09-02 | 1986-03-04 | 1986-09-03 | $7700.00 | Window Closed / Lapsed |