Patent US4028731A successfully refreshed from Google Patents.
US4028731A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for compression coding using cross-array correlation between two-dimensional matrices derived from two-valued digital images
Assignee: International Business Machines Corp
•
Filing: 1975-09-29
•
Granted: 1977-06-07
•
Expires: 1995-09-29
Abstract
Abstract An apparatus is disclosed for compressing a p × q image array of two-valued (black/white) sample points. The image array points are serially applied to the apparatus in consecutive raster scan lines. In response, the apparatus simultaneously forms two matrices respectively representing a high order p × q predictive error array and a p × q array of location events (such as the raster leading edges of all objects in the image). Improved compression is achieved by selecting between the more compression efficient of two methods for encoding the position of errors in the prediction error array. These alternative methods are conventional run-length coding and a novel form of reference encoding, used selectively but to significant advantage. Thus, a run-length compression codeword is formed from the count C of non-errors between consecutive errors (in response to the occurrence of each error in the jth bit position of the ith scan line of the predictive error array) upon either C≦T, where T is a threshold, or C>T and there being no occurrence of a line difference encoding for the error (where i, j, C and T have positive integers). A line difference codeword with difference value v is generated upon the joint event of C>T and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B≦r≦(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening location events, s, within the bit position range of D(T,v)≦q<(j-n) not exceeding some limit m (where m, n, q, r and s are positive integers).
Inventors
- 👤 Ronald Barthold Arps
- 👤 Lalit Rai Bahl
- 👤 Arnold Weinberger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 12:17
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; G06T9/004; H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
182 words
An apparatus for compression coding a p × q array of Boolean coded points applied to the apparatus in consecutive raster scan lines, said apparatus comprising: means (10, 12, 9) for forming a high-order p × q prediction error array and an auxilliary p × q array of location events from the consecutive raster scan lines of the p × q array of Boolean coded points; means (8, 12, 61, 65, 63) for counting runs C between consecutive pairs of errors in the prediction error array; means (14) for forming a line difference codeword with difference value v upon the joint event of C>T where T is a threshold and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B≦r≦(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening location events, s, within the bit position range from search start position D(T,v)≦q<(j-n) not exceeding some limit m, where m, n, q, r and s are positive integers; and
Claim 2
Independent Claim
182 words
An apparatus for compression coding a p × q array of Boolean coded points applied to the apparatus in consecutive raster scan lines, said apparatus comprising: means (10, 12, 9) for forming a high-order p × q prediction error array and an auxilliary p × q array of location events from the consecutive raster scan lines of the p × q array of Boolean coded points; means (8, 12, 61, 65, 63) for counting runs C between consecutive pairs of errors in the prediction error array; means (14) for forming a line difference codeword with difference value v upon the joint event of C>T where T is a threshold and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B≦r≦(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening location events, s, within the bit position range from search start position D(T,v)≦q<(j-n) not exceeding some limit m, where m, n, q, r and s are positive integers; and
Claim 3
Dependent Claim
66 words
means (14) for forming a compression code word from the run-length count C between consecutive errors, in response to the occurrence of each error in the jth bit position of the ith scan line of the prediction error array upon either C≦T or C>T and there being no occurrence of a line difference encoding for the error, where i, j, C and T are positive integers.
Claim 4
Dependent Claim
66 words
means (14) for forming a compression code word from the run-length count C between consecutive errors, in response to the occurrence of each error in the jth bit position of the ith scan line of the prediction error array upon either C≦T or C>T and there being no occurrence of a line difference encoding for the error, where i, j, C and T are positive integers.
Claim 5
Dependent Claim
11 words
An apparatus according to claim 1, wherein said apparatus further comprises;
Claim 6
Dependent Claim
57 words
means (9,13,16) for generating line difference codes with value v (-n,-(n-1), -1,0, +1, (n-1), n) responsive to the correlation between the pel position between a location event in the ith-1 scan line of the location event array and an error in the ith scan line of the error array within a predetermined number n of pel positions.
Claim 7
Dependent Claim
57 words
means (9,13,16) for generating line difference codes with value v (-n,-(n-1), -1,0, +1, (n-1), n) responsive to the correlation between the pel position between a location event in the ith-1 scan line of the location event array and an error in the ith scan line of the error array within a predetermined number n of pel positions.
Claim 8
Dependent Claim
8 words
An apparatus according to claim 1, where D(T,v)=(j-C+T+l).
Claim 9
Dependent Claim
102 words
An apparatus according to claim 1, wherein the means for generating the prediction error array comprises: memory means (10) for storing consecutive raster scan lines of the original p × q array; means (75) for reading the neighboring pel values of the present and previous raster scan lines from the memory (10) for predicting the jth pel value for the ith scan line; means (71) for generating a binary 1 given the noncorrespondence between the actual pel value for the jth position of the ith scan line of the original array and the predicted value and for generating a binary 0 otherwise.
Claim 10
Dependent Claim
18 words
An apparatus according to claim 4 wherein the means for high-order prediction includes a third order pel predictor.
Claim 11
Independent Claim
208 words
An apparatus for compression coding a p × q array of Boolean coded points, termed "pels", said coded points or pels being applied to the apparatus in consecutive raster scan lines, said apparatus comprising: means for deriving from the p × q array of Boolean coded points, a p × q array of high-order prediction errors; and an auxilliary p × q array of location events such as raster leading edges of all the objects in the image; means for counting run-lengths C between consecutive pairs of errors in the prediction error array; means responsive to each high-order prediction error for variable length encoding the most compression efficient of a first codeword and a second codeword, or in the absence of a first codeword encoding with the second codeword; means for forming a first codeword upon there being an unambiguous correlation between a prediction error in the ith scan line of the prediction error array and a location event in the ith or ith -1 scan line of the location event array within a predetermined number of pel positions from the prediction error; and means for forming a second codeword from the run-length C between a prediction error and the preceding prediction error in the same scan line.
Claim 12
Independent Claim
208 words
An apparatus for compression coding a p × q array of Boolean coded points, termed "pels", said coded points or pels being applied to the apparatus in consecutive raster scan lines, said apparatus comprising: means for deriving from the p × q array of Boolean coded points, a p × q array of high-order prediction errors; and an auxilliary p × q array of location events such as raster leading edges of all the objects in the image; means for counting run-lengths C between consecutive pairs of errors in the prediction error array; means responsive to each high-order prediction error for variable length encoding the most compression efficient of a first codeword and a second codeword, or in the absence of a first codeword encoding with the second codeword; means for forming a first codeword upon there being an unambiguous correlation between a prediction error in the ith scan line of the prediction error array and a location event in the ith or ith -1 scan line of the location event array within a predetermined number of pel positions from the prediction error; and means for forming a second codeword from the run-length C between a prediction error and the preceding prediction error in the same scan line.
Claim 13
Dependent Claim
42 words
An apparatus according to claim 6, wherein the means responsive to each high-order prediction error for variable length encoding the most compression efficient of a first and a second codeword includes: means for selecting the shorter of said first and second codewords.
Claim 14
Dependent Claim
128 words
An apparatus according to claim 6, wherein the means for deriving from the p × q array of Boolean coded points, a p × q prediction error array and a p × q location event array comprise: means for dimensioning each derived array into p rows and q+n+1 columns by including in the n+1 extra positions, columns of dummy errors or location events respectively; said means for forming the first codewords being responsive to the occurrence of dummy errors and location events in the n+1 extra pel positions of the ith and ith-1 scan lines of the respective error and event arrays for increasing the relative frequency of first word encodings of those error array scan lines otherwise encoded as a second codeword at the end of line.
Claim 15
Independent Claim
214 words
An apparatus for compression coding of a p × q array of Boolean coded points, the array points being serially applied to the apparatus in consecutive raster scan lines comprising: means responsive to the consecutive raster scan lines for deriving a respective high-order and low-order p × q prediction error location event array; means (14) for forming a line difference codeword with difference value v upon the joint event of C>T where T is a threshold and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B≦r≦(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening events, s, within the bit position range from search start position D(T,v)≦q<(j-n) not exceeding a limit m, where m, n, q, r and s are positive integers; and means (14) for forming a compression code word from the run-length count C between consecutive errors, in response to the occurrence of each error in the jth bit position of the ith scan line of the prediction error array upon either C≦T or C>T and there being no occurrence of a line difference encoding for the error, where i, j, C and T are positive integers.
Claim 16
Independent Claim
214 words
An apparatus for compression coding of a p × q array of Boolean coded points, the array points being serially applied to the apparatus in consecutive raster scan lines comprising: means responsive to the consecutive raster scan lines for deriving a respective high-order and low-order p × q prediction error location event array; means (14) for forming a line difference codeword with difference value v upon the joint event of C>T where T is a threshold and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B≦r≦(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening events, s, within the bit position range from search start position D(T,v)≦q<(j-n) not exceeding a limit m, where m, n, q, r and s are positive integers; and means (14) for forming a compression code word from the run-length count C between consecutive errors, in response to the occurrence of each error in the jth bit position of the ith scan line of the prediction error array upon either C≦T or C>T and there being no occurrence of a line difference encoding for the error, where i, j, C and T are positive integers.
Claim 17
Independent Claim
175 words
An apparatus (FIGS. 2) for decoding compression code words so as to reconstruct a p × q array of Boolean coded points in consecutive raster scan lines, said apparatus comprising: memory means (10') for storing a p × q array of Boolean coded points; means (7', 77', 75') for generating a p × q prediction array from the memory stored array; means (7', 77', 9') for generating a p × q location event array from the memory stored array means (14', 67') responsive to successive compression code words for generating a p × q prediction error array; means (71') coupling the prediction array and predictive error array generating means for generating a p × q array of Boolean coded points wherein each Boolean coded point at array coordinates i, j represents a value of a first kind upon there being a mismatch of values at corresponding i, j coordinates between the prediction and predictive error arrays, and a value of a second kind upon there being a match of values at said array coordinates; and
Claim 18
Independent Claim
175 words
An apparatus (FIGS. 2) for decoding compression code words so as to reconstruct a p × q array of Boolean coded points in consecutive raster scan lines, said apparatus comprising: memory means (10') for storing a p × q array of Boolean coded points; means (7', 77', 75') for generating a p × q prediction array from the memory stored array; means (7', 77', 9') for generating a p × q location event array from the memory stored array means (14', 67') responsive to successive compression code words for generating a p × q prediction error array; means (71') coupling the prediction array and predictive error array generating means for generating a p × q array of Boolean coded points wherein each Boolean coded point at array coordinates i, j represents a value of a first kind upon there being a mismatch of values at corresponding i, j coordinates between the prediction and predictive error arrays, and a value of a second kind upon there being a match of values at said array coordinates; and
Claim 19
Dependent Claim
16 words
means (2') for updating the memory from the output of the Boolean coded array generating means.
Claim 20
Dependent Claim
16 words
means (2') for updating the memory from the output of the Boolean coded array generating means.
Claim 21
Dependent Claim
35 words
An apparatus according to claim 10, wherein the means for generating a p × q location event array include: means (9') for detecting the leading edge of an object disposed in the memory stored array.
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) | 1980-06-06 | 1980-12-06 | 1981-06-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1984-06-06 | 1984-12-06 | 1985-06-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1988-06-06 | 1988-12-06 | 1989-06-07 | $7700.00 | Window Closed / Lapsed |