On Self-Indexing Images --- Image Compression with Added Value
Veli Mäkinen and Gonzalo Navarro
Recent advances in compressed data structures have led to the new concept of
self-indexing;
it is possible to represent a sequence of symbols compressed in a form that
enables fast queries on the
content of the sequence. This paper studies different analogies of
self-indexing on images.
First, we show that a key ingredient of many self-indexes for sequences,
namely the wavelet tree,
can be used to obtain both lossless and lossy compression with random access
to pixel values.
Second, we show how to use self-indexes for
sequences as a black-box to provide self-indexes for images with
filtering-type query capabilities. Third,
we develop a tailor-made self-index for images by showing how to compress
two-dimensional suffix arrays.
Experimental results are provided to compare the compressibility to standard
compression methods.