Multi-Stage Pattern Reduction in Lossless Image Compression

Abstract

Lossless image compression is the process of compressing and subsequently decompressing images without the loss of data. Historically, image compression was carried out by treating images as complex text [13]. Only in recent years have images been treated as data collections that could be processed for compression and decompression in a manner unique to images [1]. Even the best modern lossless image compression techniques, however, yield less than desirable results [5]. The biggest drawback for lossless image compression is that images can only be reduced to about one-third of their original image size. Lossy image compression algorithms, i.e., those techniques for compressing image size where image information is lost upon decompression, are capable of reducing images to one tenth of their actual size with little or no humanly perceptual loss in image detail.

Multi-stage pattern reduction is an emerging approach for encoding data that has recently demonstrated efficient processing in the field of natural-language processing. It relies on the ability to discern small local patterns in a source, recreating a new source using these local patterns and then reapplying the technique over multiple stages. In this thesis, the value of using multi-stage pattern reduction to compress images will be explored. The goal of this thesis is to create a lossless image compression algorithm by employing the techniques of multi-stage pattern reduction and to determine if such an approach can provide better compression on average than the current major competing algorithms in the field.