Adaptive prediction for binary encoded documents containing a mixture of text, line drawings and halftones

• US 4,559,563 A
• Filed: 10/11/1983
• Issued: 12/17/1985
• Est. Priority Date: 10/11/1983
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Joiner, Ronald E. Jr.
• Primary Examiner(s): Britton, Howard W.
• Assistant Examiner(s): Peng, John K.
• Application Number:
  US06/540,950
• Time in Patent Office: 798 Days
• Field of Search: 358/283, 358/260, 358/135, 382/56
• US Class Current: 382/238
• CPC Class Codes: H04N 1/417 using predictive or differential encoding
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

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.

Claims

1. 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.

2. 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.

3. The system according to claim 1 wherein said selector means will resolve ties in favor of the predictor previously selected.

4. 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.

5. The system according to claim 2 in which each halftone predictor pattern is a single bit located several positions earlier in the current line.

6. 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.

7. 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.

8. 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.

9. 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.

10. The method of claim 8 in which ties are resolved in favor of the predictor previously selected.

11. The method of claim 9 in which ties are resolved in favor of the predictor of the same class as the predictor previously selected.

12. The method of claim 9 in which each halftone predictor pattern is a single bit located several positions earlier in the current line.

13. 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.