The Prague Stringology Conference 2002

Sergio De Agostino

A Work-Optimal Parallel Implementation of Lossless Image Compression by Block Matching

Storer suggested that fast encoders are possible for two-dimensional lossless compression by showing a square greedy matching LZ1 heuristic for bi-level images, which can be implemented by a simple hashing scheme. In this paper, we show a work-optimal parallel algorithm using a rectangle greedy matching technique requiring O(log M log n) time on the PRAM EREW model, where n is the size of the image and M the maximum size of a rectangle.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF