Image compression using efficient scan patterns

Prior to this work, lossless image compression schemes implicitly assumed that an image is scanned in a particular order. Clearly, depending on the picture, a different scanning pattern may give better compression. In this dissertation we introduce the notion of a prediction tree for an image. A traversal of any prediction tree defines a connected scan. The set of prediction trees defines a family of connected scans of an image. A minimum entropy prediction tree is then connected scan from this family, that minimizes the zero order entropy of intensity differences encountered. We show that given a weighted graph, the problem of computing a minimum entropy tree is NP-Hard. However, we give efficient heuristics for computing low entropy prediction trees. We identify conditions under which the heuristics would yield an optimal result. The conditions are reasonable and in fact characteristic of most real life images. Due to the very large number of prediction trees, the cost of encoding an optimal tree turns out to be prohibitively high. This leads to the need for a trade-off between minimizing the number of bits needed to encode the shape of a tree and the entropy of the weights on the tree. Depending on the application, there are many ways to strike a favorable trade-off. One such approach is to use a codebook of prediction trees. We design compression schemes based on static, semi-adaptive and adaptive codebooks. Compression schemes based on a few other novel approaches are also presented. We give implementation results for all the schemes presented on a set of test images. The bit rates achieved compare favorably with the JPEG still compression standard for lossless coding