Monagi Alkinani, Fall 2011, "Context-Based Multiple Dictionaries LZ Image Compression", Computer Science Department, University of Western Ontario, Canada.

M.Sc. Thesis Abstract

Dictionary-based encoding depends on similarity between characters. When encoding strings, encoder replaces string by a much shorter bytes that is a reference to a previous similar encoded string. Lempel and Ziv (LZ) 1977&1978 algorithms are considered the foundation of the dictionary-based encoding.

Many algorithms have been presented to improve the performance of the LZ algorithms. LZR, LZSS, LZB, LZH, Improved-LZSS, LZFG, LZRW, SA-LZ77, Fixed-LZ77, LZAC, LZFFG-PM, DifLZ, LZP, LZGT, LZW and CSD are modifications to improve the speed and/or the compression ratio of LZ. Perhaps the best LZ improvement includes, LZP which combining LZ algorithms with prediction by partial matching encoding (PPM).

LZ algorithms are originally used for text compressions. Pixels in images are highly correlated with their neighbouring pixels. Properly extending LZP to encode images, where the 2D nature of image is exploited, would produce better compression results. We have run several experiments to study one of LZ78 improvements, which is sub-dictionaries ethod (CSD). CSD uses multiple dictionaries instead of just one (though it is a 1st order PPM), more compression ratios were achieved.

In our presentation, In this presentation, we will talk about the various LZ modifications. We will discuss the efficiency of these modifications based on the result of each modification when running Calgary Corpus standard test. We will also talk about the experiments which we run to show the improvement in LZ78, and how the usage of 2D in images can improve the compression ratio.