Lossless image compression using combinations of simple components.

Abstract

This dissertation proposes three new lossless compressors intended for digitized natural images. These compressors are either simple outright, or are complicated but consist mostly of many simple and similar components. The compressors nevertheless produce low compression rates, and for the most part are competitive in speed and memory use. The proposed compressors code their input images in raster-scan order, one pixel at a time. With one exception, each compressor consists of two parts: a probability mass function that indicates each pixel's probability given that pixel's already-coded neighbors, and an arithmetic coder, which is an algorithm that generates bits to represent pixels. Arithmetic coders generate more bits to represent pixels that the probability mass function says are less likely, so the compressor designer's goal is to devise probability mass functions that assign high probabilities to the pixels that actually occur. The proposed compressors all use single-modal probability mass functions that have two parameters---the mode's location, and the mode's width---and all use a linear function of already-compressed pixels, called the predictor, to calculate the location parameter. The compressors differ in how they determine both that predictor and the width parameter. The first of the proposed compressors (called SLA) always uses the same predictor, but finds its width parameter anew for every pixel by averaging the absolute values of a few nearby prediction errors. A variant (called SG) of this compressor is similar except that it generates bits using a method, Golomb coding, that's faster than arithmetic coding. The second of the proposed compressors (called FSC) calculates both a new predictor and a new width parameter for every pixel. It does this by estimating the best predictor and width parameter for the already-compressed pixels whose neighbors are most similar to the current pixel's neighbors. The last of the proposed compressors (called PLRT) selects a new predictor and width parameter for every pixel by using a tree-based classifier whose input is a vector containing a few of the current pixel's past neighbors, and whose output is one of a precalculated set of predictor/width parameters.