The Prague Stringology Conference 2002
A Work-Optimal Parallel Implementation of Lossless Image Compression by Block Matching
| Abstract: |
| 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: |  |
 |
| PostScript |