A work-optimal parallel implementation of lossless image compression by block matching
Luigi Cinque, Franco Liberati, Sergio De Agostino · IRIS Research product catalog (Sapienza University of Rome) · 2003
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 [Storer 1996]. Rectangle matching improves the compression performance, but it is slower since it requires O(M log M) time for a single match, where M is the size of the match [Storer and Helfgott 1997]. Therefore, the sequential time to compress an image of size n by rectangle matching is Ω(n log M). 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.