| 摘要 |
<p>An apparatus is disclosed for compressing a p x 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 x q predictive error array and a p x 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. This 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 positioned range of D(T,v)?q<(j-n) not exceeding some limit m (where m, n, q, r and s are positive integers). By adding the referencing codewords to a conventional run-length code word set, the compression code word relative frequency distribution is improved at only a small increase in alphabet size. The improvement causes more peaking of the relative frequency vs. codeword size distribution with a resulting lower entropy per codeword. This novel extension of reference encoding (using cross-array encoding to a location event array) permits this optimization for lower entropy per codeword independent of the use of high-order prediction to simultaneously reduce the number of codewords. These two improvements in combination result in improved compression over the prior art.</p> |
