PROJECT SUMMARY
CONTENT-BASED IMAGE RETRIEVAL
In typical query-by-example systems, users query a database, using images as an example of similarity. Typical images contain objects of interest and also irrelevant image areas, or noise. This noise compromises the effectiveness of retrieval in any similarity model that takes the entire example as relevant; unfortunately, many QBE systems are in this category. For instance, an image is traditionally represented using a few tightly integrated feature vectors, making it difficult to exclude noise in a similarity comparison. Recent approaches aim to specify regions of interest using low-level image features. These attempts are hindered by unreliable segmentation schemes and computationally expensive routines.
In fact there is a solution from the signal-processing domain, in which audio waves are down-sampled and represented in a compressed digitized form. To set up a similar representation for images, a 2-D spatial sampling technique for image retrieval must be developed. In [3], we formalize the concepts involved and provide a unified framework in which the necessary properties for image retrieval (such as translational invariance, scaling, semantic constraints, and no false dismissals) are systematically derived and proved. This work sets out the framework for noise-free query processing in a QBE environment [1][6][7]. The system is supported with various routines, including indexing methods [4] and a query preprocessing function [5].
Concept-based retrieval is the next natural level of content-based image retrieval. A major challenge is accurate representation of the concepts involved. The flexibility of the sampling-based approach allows users to define concepts without hindrance by noise. The proposed framework is again the core component in a methodology for query-by-concept image retrieval [2]. The system automatically annotates images based on a set of noise-free training examples, and enables queries to be formulated using concepts such as tree, sky, and building. Experiments have found that the approach achieves very high accuracy in annotating images.
MULTIDIMENSIONAL ACCESS METHODS FOR MULTIMEDIA DATA
Efficient indexing and retrieval of multimedia data are necessary to a successful multimedia system. Fast response time is critical in the success of many applications such as online multimedia retrieval. Most high-performance indexing techniques are not suited to this task, as the requirements of typical multimedia systems often far exceed the specifications of traditional indexing applications. Today's databases can contain thousands of multimedia objects, rendering impractical a complete scan to find relevant objects. The approximate nature of similarity measures in multimedia retrieval means that large returns are required as a result of inaccurate rankings. A search of ten nearest neighbors (k = 10), as in most research studies, is well below what is needed to offset false dismissals. For large k these techniques are out-performed by a simple exhaustive scan.
The main difficulty, as is well known, is the high dimensionality of multimedia data, which are normally represented by hundreds of dimensions (features). Most indexing methods then break down and perform worse than a sequential scan. This is the notorious curse of dimensionality. It refers to the exponential expansion of the data space that consequently becomes very sparse when populated with a data set of practical size. A direct consequence is that the average distance between neighboring points becomes so large that the standard hypercubic approximation of the search sphere returns almost the entire data set.
We believe that efficient multimedia retrieval should be addressed in the larger context of searching in multidimensional space. We therefore reexamined every aspect of the retrieval issue, including the standard hypercubic approximation. Our detailed analysis in [10] exposes some interesting properties of high dimensional spaces and suggests a promising solution to these problems. In particular, we was led to propose a novel partitioning approach using iso-hypersurfaces, including those generated by the means and standard deviations of datapoint vector components. Advantages of this approach include: (i) the search radius can be larger than the linear size of the space; (ii) the number of dimensions can be greatly reduced, so that existing high-performance indexing methods can be employed; and (iii) the resulting approximation is more accurate than those based on hypercubes. Extensive experiments on multimedia data confirm that this technique greatly reduces dimensionality while improving precision across the entire range of search radii [8]. We are currently expanding this method to speed up the retrieval of multimedia [9].