Compressed-Domain Image Retrieval Based on Colour Visual Patterns

Introduction

With the recent enormous increase in digital image collections there is no doubt that effective image retrieval techniques are desperately needed. Fortunately, this problem has been subject of extensive research for over a decade. In 1991 Swain and Ballard (1991) published results of their work on colour indexing. Their method of finding similar images - while being very simple - performed extremely well. They quantised colour space into bins, creating a 3-dimensional colour histogram. All pixels are scanned, allocated to the bins that they correspond to and then the number (or percentage) of pixels in each bin is extracted. Comparing two images is done by finding the L₁ norm between their respective histograms.

Although colour information is very important in object recognition, it is often not sufficient, especially if colour descriptors are extracted globally for a whole image. This was soon realised and techniques which also address texture and shape properties investigated (Smeulders et al., 2000). Although these methods are usually not as efficient as colour-based algorithms, incorporating several feature types provides improved performance.

All these methods have one common factor that can be regarded as their weakness. Storage space is very limited when compared to the enormous amount of images that we keep on producing. Moreover, the ability to transfer these pieces of information is still limited by bandwidths of networks (especially the Internet). Many different compression algorithms have been developed to enable us to store more data using less storage space. In fact, these highly effective techniques are now being used extensively and virtually all image data now exists in compressed form. Many of the original uncompressed images are not kept or indeed never existed as compression is typically performed on-the-fly inside digital cameras. Many others never even existed in their uncompressed form, because virtually all digital cameras compress images to increase their capacity. Despite the fact that almost all images are compressed, image retrieval techniques are based on the uncompressed pixel bitmap domain, meaning that two pictures have to be first uncompressed to enable comparing them on-line which clearly is a limitation. While features can be extracted off-line and stored separately, this conflicts with the original intention of compression as the features may require a significant amount of storage space. Despite these limitations, only relatively little research has been done in the area of retrieval in the compressed domain of images (Mandal, Idris, & Panchanathan, 1999).

In this chapter we show that so-called midstream content access (Picard, 1994) can indeed be achieved to provide effective and efficient image retrieval. Colour visual pattern image coding (CVPIC) is one of the first so-called 4^th criterion image compression algorithms (Schaefer, Qiu, & Luo, 1999; Schaefer & Qiu, 2000). A 4^th criterion algorithm allows - in addition to the classic three image coding criteria of image quality, efficiency, and bitrate - the image data to be queried and processed directly in its compressed form; in other words the image data are directly meaningful without the requirement of a decoding step (Picard, 1994). The data that are readily available in CVPIC compressed images is the colour information of each of the 4x4 blocks the image has been divided into, and information on the spatial characteristics of each block, including whether a given block is identified as a uniform block (a block with no or little variation) or a pattern block (a block where an edge or gradient has been detected).