Some Extensions of the Ordering Techniques for Compression of Two-Level Facsimile Pictures

Coding of two-tone (black and white) facsimile pictures has gained considerable importance in the past few years, as is evidenced by a large number of papers as well as by a variety of facsimile communication systems. More and more sophisticated coding algorithms are being used which depend upon the two-dimensional spatial correlation present in picture data. This trend is understandable when one realizes that the cost of digital circuits and memories is decreasing faster than the cost of transmission. This paper presents some extensions of our ordering schemes 1,2 for efficient coding of facsimile pictures. In the basic ordering scheme we make a prediction of the present element using the surrounding previously transmitted picture elements and classify it as "good" or "bad," depending upon the probability of the prediction being in error, condi3057 tioned on the specific values of the surrounding elements. We then change the relative order of the prediction errors corresponding to picture elements along a scan line using the "goodness" of the prediction in such a way as to increase the average run-length of the black and/or white elements and then transmit the run-lengths. This paper has several objectives. First, we give the entropy results using our earlier ordering schemes on the CCITT (International Telegraph and Telephone Consultative Committee) images. This will allow a comparison with the many coding algorithms proposed by other workers since the CCITT images are widely available.