Coding of Two-Level Pictures by Pattern Matching and Substitution

Conventional two-level picture coding techniques are based on the statistical dependence between neighboring picture elements (pels). 1 T h e calculation of entropies, according to a local source model, gives the maximum achievable bit rates. Run length or predictive coding techniques or a combination of them takes advantage of the statistical dependence between neighboring pels and leads to bit rates close to the entropy. Each exploits what can be called the microscopic (pel) properties of a facsimile. Pattern-recognition coding techniques exploit macroscopic proper* Bell Laboratories. Copyright 1983, American Telephone & Telegraph Company. Photo reproduction for noncommercial use is permitted without payment of royalty provided that each reproduction is done without alteration and that the Journal reference and copyright notice are included on the first page. The title and abstract, but no other portions, of this paper may be copied or distributed royalty free by computer-based and other information-service systems without further permission. Permission to reproduce or republish any other portion of this paper must be obtained from the Editor. 2513 e