An image compression method for spatial search

The maintenance of large raster images under spatial operations is still a major performance bottleneck. For reasons of storage space, images in a collection, such as satellite pictures in geographic information systems, are maintained in compressed form. Instead of performing a spatially selective operation on an image by first decompressing the compressed version, we propose to perform queries directly on the compressed version of the image. We suggest a compression technique that allows for the subsequent use of a spatial index structure to guide a spatial search. In response to a window query, our algorithm delivers a compressed partial image, or the exact uncompressed requested image region. In addition to the support of spatial queries on compressed continuous tone images, the new compression algorithm is even competitive in terms of the compression ratio that it achieves, compared to other standard lossless compression techniques.