Ordering Techniques for Coding of Two-Tone Facsimile Pictures

Transmission and/or storage of two-tone (black and white) pictures, such as weathermaps, printed texts, etc., have been receiving considerable attention for some time. The practical importance of this problem is evidenced by the number of facsimile communication systems that are now available. 1 As the cost of electronics decreases faster than transmission costs, it is becoming advantageous to use sophisticated facsimile terminals to reduce transmission costs and time, and, indeed, many of the recent facsimile communication systems have resorted to various source encoding techniques to utilize the statistical redundancy between the spatially close picture elements to reduce the bit rate required for transmission. 2-5 The picture elements along a scan line of a facsimile picture consist of runs of white picture elements (pels) separated by runs of black 1539 picture elements. Values of the spatially close picture elements are significantly correlated. Source coding techniques, which do not reduce the "information content" of the pictures (i.e., it is possible to construct the original picture exactly without any degradation from the coded picture) use the statistical redundancy either along a single scan line or along many scan lines. One-dimensional run-length coding techniques 6 code the runs of black or white elements along a scan line. Development and performance of many different codes to code the runs have been a subject of many papers. 7 - 9 Some of these codes are capable of performing close to the entropy of the run-length statistics.