Nathanael J. Brittain, September 2003--April 2005, "Two
Dimensional Dictionary Based Image Compression", degree
conferred on Spring 2005 convocation, Computer Science
Department, University of Western Ontario, Canada.
M.Sc. Thesis Abstract
Dictionary-based compression methods are a popular form of
data file compression. LZ77, LZ78 and their variants are
likely the most famous of these methods. These methods are
implemented to reduce the one-dimensional correlation in
data, since they are designed to compress text. Therefore,
they do not take advantage of the fact that, in images,
adjacent pixels are correlated in two dimensions. Previous
attempts have been made to linearize images in order to make
them suitable for dictionary-based compression, but results
show that no single linearization is best for all images.
Other attempts have been made to adapt dictionary-based
compression schemes to consider data in two dimensions, but
only for binary images.
In this thesis, a two-dimensional dictionary-based lossless
image compression scheme for grayscale images is introduced.
The proposed scheme reduces correlation in image data by
finding two-dimensional blocks of pixels that are repeated
throughout the data and replacing them with short codewords.
Test results show that the compression performance of the
proposed scheme outperforms and surpasses any other existing
dictionary-based compression scheme. The results also show
that it is comparable in compression performance to JPEG-LS
and JPEG-2000 (when it operates in its lossless mode), where
JPEG-2000 and JPEG-LS are the current image compression