Apparatus for compression coding using cross-array correlation between

Abstract

An apparatus is disclosed for compressing a p .times. 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 .times. q predictive error array and a p .times. 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.ltoreq.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.ltoreq.r.ltoreq.(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).ltoreq.q<(j-n) not exceeding some limit m (where m, n, q, r and s are positive integers).