Ordering Techniques for Coding of Two-Tone Facsimile Pictures
Arun N. Netravali, F. W. Mounts, E. G. Bowen · Bell System Technical Journal · 1976
This paper describes some techniques for efficient coding of two-tone (black and white) facsimile pictures. These techniques use the two-dimensional correlation present in spatially close picture elements to change the relative order of transmission of elements in a scan line. This ordering increases the average length of the runs of consecutive black or white elements in the ordered line, making the data more amenable to one-dimensional run-length coding. We describe several variations of the ordering scheme, which differ in complexity and coding efficiency and evaluate their coding efficiency. For a variety of 8-1/2 inch by 11-inch typed documents, road maps, and circuit diagrams scanned with 200 lines/inch, these techniques reduce the bit rate by 30 to 50 percent over and above the one-dimensional run-length coding along a scan line; for single-spaced typed material with 100 lines/inch, this reduction is about 25 percent. We compare one of our techniques with a two-dimensional compression technique recently proposed by Preuss. We show that our technique results in an entropy about 10 to 18 percent lower than that obtainable through Preuss' technique.