Method and apparatus for adaptive facsimile compression using a two dimensional maximum likelihood predictor
First Claim
1. A data compression device for information scanned in two dimension and represented by a serial stream of pixel representations, comprising:
- first buffer means for storing at least some of said pixel representations sufficient to represent a portion of said information extending in both said dimensions;
predictor means coupled to said first buffer means for generating, from at least three pixel representations, a predicted pixel representation for a further pixel, said pixels forming a pixel set extending in both said dimensions,selection means responsive to said at least three pixel representations for selecting, or not selecting, said further pixel for compression encoding,comparing means for comparing said predicted representation of a selected pixel with an actual representation of said pixel from said first buffer means, to determine if said prediction is or is not correct,run length encoding means responsive to said comparing means for encoding successive correct predictions and a following incorrect prediction as at least one multibit word, and second buffer means responsive to said run length encoding means and said predictor means for storing said at least one multibit word and at least one unencoded pixel representation corresponding to an unselected pixel.
4 Assignments
0 Petitions
Accused Products
Abstract
Data compression, for either a storage or transmission, of facsimile information is effected employing a two dimensional, non-contiguous prediction matrix. A data stream representing the data to be compressed is input to a buffer which is of a size to store sufficient information for prediction purposes. A predictor is responsive to the buffer for producing a predicted data representation from a plurality of data units comprising a two dimensional matrix. A selector is responsive to the data unit employed in the prediction process for making a select/non-select determination. For those data units which are selected, a comparator compares the predicted status of the data unit with the actual status of the data unit. At least one run length encoder is responsive to the comparator for run length encoding successive correct predictions and a following incorrect prediction. An output buffer is provided for storing the run length encoded output of the run length encoder as well as representations of the non-selected data units. By using plural run length encoders, each can be optimized for the encoded data by correlating prediction difficulty with code length, i.e., easy predictions are encoded by long code words and hard predictions are encoded with short words. Further, the unselected class data units correspond to most difficult predictions and these are not coded.
109 Citations
25 Claims
-
1. A data compression device for information scanned in two dimension and represented by a serial stream of pixel representations, comprising:
-
first buffer means for storing at least some of said pixel representations sufficient to represent a portion of said information extending in both said dimensions; predictor means coupled to said first buffer means for generating, from at least three pixel representations, a predicted pixel representation for a further pixel, said pixels forming a pixel set extending in both said dimensions, selection means responsive to said at least three pixel representations for selecting, or not selecting, said further pixel for compression encoding, comparing means for comparing said predicted representation of a selected pixel with an actual representation of said pixel from said first buffer means, to determine if said prediction is or is not correct, run length encoding means responsive to said comparing means for encoding successive correct predictions and a following incorrect prediction as at least one multibit word, and second buffer means responsive to said run length encoding means and said predictor means for storing said at least one multibit word and at least one unencoded pixel representation corresponding to an unselected pixel. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method of compressing a serial digital data stream representing pixels of an image scanned in two dimensions at a resolution sufficient to negate the importance of single pixel runs comprising the steps of:
-
eliminating single pixel runs, from said serial data stream, selecting a plurality of pixels from a set of pixels representing an image portion extending in two dimensions from which to predict the condition of a last remaining pixel in said set, predicting, from said plurality of pixels, the condition of said remaining pixel and determining whether or not run length encoding is appropriate for said predicted pixel, comparing said predicted pixel with said actual pixel and run length encoding correct/incorrect predictions, filling a buffer with a sequence of run length codes representing run length encoding of said correct/incorrect predictions and following said codes with one or more signals representing pixels for which run length encoding was determined to be inappropriate. - View Dependent Claims (17, 18, 19, 20, 21, 22)
-
-
23. A method of transmitting image representing data in compressed form from a transmitter to a receiver comprising the steps of:
-
raster scanning a field of view in two dimensions and digitizing samples obtained by said scanning to produce a serial stream of digital pixel representations, arranging two independent images in said field aligned so that each line of said raster covers corresponding portions of both said independent images, compression encoding at least some information from said serial stream, to produce a compression encoded stream, transmitting said compression encoded stream to a receiver, compression decoding said compression encoded stream at a receiver, and recreating, at said receiver, at least one of said two independent images. - View Dependent Claims (24, 25)
-
Specification