US4559563A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive prediction for binary encoded documents containing a mixture of text, line drawings and halftones
Assignee: Xerox Corp
•
Filing: 1983-10-11
•
Granted: 1985-12-17
•
Expires: 2003-10-11
Abstract
Abstract This is a circuit and method for adaptively selecting one of a plurality of predictor patterns to encode a stream of image data blocks such as would be output from a raster-input-scanner. A variety of halftone and nonhalftone predictor patterns are used and compared, with the best one being selected to predict the next block. Using this technique, the best predictor pattern is usually selected, predicted data buffering is not needed, and no code need be transmitted with the data to the receiver to specify the predictor to be used in the deprediction process since the same basic information is also available to the receiver.
Inventors
- 👤 Ronald E. Joiner, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 08:17
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/90; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
91 words
A system for adaptively predicting a block of image data comprising: a plurality of predictors, each using a different predictor pattern for predicting the data bits of each image data block, a comparator for each predictor for generating an error code representative of the accuracy of the predictions made, selector means for selecting one of the predictors, based on its performance on one or several previous data blocks, and means responsive to the output of said selector means for outputting the error code for the current block using the selected predictor.
Claim 2
Independent Claim
91 words
A system for adaptively predicting a block of image data comprising: a plurality of predictors, each using a different predictor pattern for predicting the data bits of each image data block, a comparator for each predictor for generating an error code representative of the accuracy of the predictions made, selector means for selecting one of the predictors, based on its performance on one or several previous data blocks, and means responsive to the output of said selector means for outputting the error code for the current block using the selected predictor.
Claim 3
Dependent Claim
63 words
The system according to claim 1 in which said plurality of predictors includes a nonhalftone and halftone predictor class, said nonhalftone predictor class making predictions based on the value of immediately adjacent bits, on the current or previous line, and said halftone predictor class making predictions based on the value of bits which are several positions earlier in the current or previous lines.
Claim 4
Dependent Claim
20 words
The system according to claim 1 wherein said selector means will resolve ties in favor of the predictor previously selected.
Claim 5
Dependent Claim
27 words
The system according to claim 2 wherein said selector means will resolve ties in favor of the predictor of the same class as the predictor previously selected.
Claim 6
Dependent Claim
24 words
The system according to claim 2 in which each halftone predictor pattern is a single bit located several positions earlier in the current line.
Claim 7
Dependent Claim
29 words
The system according to claim 1 in which said means for outputting comprises a multiplexor which uses the current error codes of said prediction means as the data input.
Claim 8
Dependent Claim
52 words
The system of claim 2 wherein said selector means will select a new halftone pattern over a previously selected halftone pattern only if the performance of said new pattern is better than the performance of said previously selected pattern for the two consecutive data blocks immediately prior to the current data block.
Claim 9
Independent Claim
60 words
The method of adaptively predicting a series of blocks of image data comprising the steps of: first using a plurality of predictors for generating error codes for one or a plurality of previous consecutive data blocks, selecting the best predictor based on its performance, and second using said selected predictor for generating the output error code for the current block.
Claim 10
Independent Claim
60 words
The method of adaptively predicting a series of blocks of image data comprising the steps of: first using a plurality of predictors for generating error codes for one or a plurality of previous consecutive data blocks, selecting the best predictor based on its performance, and second using said selected predictor for generating the output error code for the current block.
Claim 11
Dependent Claim
51 words
The method of claim 8 wherein said plurality of predictors includes a nonhalftone class and a halftone class, said nonhalftone predictor class having pattern bits adjacent the current bit on the current or previous lines, said halftone class having pattern bits located several positions earlier in the current or previous lines.
Claim 12
Dependent Claim
17 words
The method of claim 8 in which ties are resolved in favor of the predictor previously selected.
Claim 13
Dependent Claim
24 words
The method of claim 9 in which ties are resolved in favor of the predictor of the same class as the predictor previously selected.
Claim 14
Dependent Claim
23 words
The method of claim 9 in which each halftone predictor pattern is a single bit located several positions earlier in the current line.
Claim 15
Independent Claim
116 words
The method of adaptively predicting a series of blocks of image data comprising the steps of: first using a plurality of halftone predictors to generate error code for a plurality of previous data blocks, second using one or a plurality of nonhalftone predictors to generate error code for the previous data block, selecting; from a group comprising (a) the halftone predictor with the best performance for all of said plurality of previous data blocks, if there is one and (b) all nonhalftone predictors for the previous block; the one with the best performance in generating error code for the previous block, and third using said selected predictor to generate output error code for the current block.
Claim 16
Independent Claim
116 words
The method of adaptively predicting a series of blocks of image data comprising the steps of: first using a plurality of halftone predictors to generate error code for a plurality of previous data blocks, second using one or a plurality of nonhalftone predictors to generate error code for the previous data block, selecting; from a group comprising (a) the halftone predictor with the best performance for all of said plurality of previous data blocks, if there is one and (b) all nonhalftone predictors for the previous block; the one with the best performance in generating error code for the previous block, and third using said selected predictor to generate output error code for the current block.
References Cited (Backward Citations)
US3185824A
Cited
US3769453A
Cited
US3937871A
Cited
US4144547A
Cited
US4141034A
Cited
US4435726A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-12-16 | 1989-06-17 | 1989-12-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-12-16 | 1993-06-17 | 1993-12-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-12-16 | 1997-06-17 | 1997-12-17 | $7700.00 | Window Closed / Lapsed |