Lossless image compression using generalized LZ1-type methods

Lossless image compression has traditionally employed techniques quite separate from those used for text compression or lossy image compression; most standards employ modeling followed by coding (e.g., the JBIG standard, the IBM Q-coder, CCITT Group 4). Constantinescu and Storer [1994] presented a lossy image compression scheme that can be viewed as a generalization of lossless dynamic dictionary compression (“LZ2” type methods) to two dimensions with approximate matching; Constantinescu and Storer [1995] have experimented with this approach for lossless image compression with great success. Here we generalize “LZ1” type methods to lossless image compression. We examine complexity issues and 2D implementations