NeTra: A toolbox for navigating large image databases

We present here an implementation of NeTra, a prototype image retrieval system that uses color, texture, shape and spatial location information in segmented image regions to search and retrieve similar regions from the database. A distinguishing aspect of this system is its incorporation of a robust automated image segmentation algorithm that allows object- or region-based search. Image segmentation significantly improves the quality of image retrieval when images contain multiple complex objects. Images are segmented into homogeneous regions at the time of ingest into the database, and image attributes that represent each of these regions are computed. In addition to image segmentation, other important components of the system include an efficient color representation, and indexing of color, texture, and shape features for fast search and retrieval. This representation allows the user to compose interesting queries such as “retrieve all images that contain regions that have the color of object A, texture of object B, shape of object C, and lie in the upper of the image”, where the individual objects could be regions belonging to different images. A Java-based web implementation of NeTra is available at http://vivaldi.ece.ucsb.edu/Netra.     

Integrated spatial and feature image query

We present a new system for querying for images by regions and their spatial and feature attributes. The system enables the user to find the images that contain arrangements of regions similar to those diagrammed in a query image. By indexing the attributes of regions, such as sizes, locations and visual features, a wide variety of complex joint spatial and feature queries are efficiently computed. In order to demonstrate the utility of the system, we develop a process for the extracting color regions from photographic images. We demonstrate that integrated spatial and feature querying using color regions improves image search capabilities over non-spatial content-based image retrieval methods.     

Comparing images using joint histograms

Color histograms are widely used for content-based image retrieval due to their efficiency and robustness. However, a color histogram only records an image's overall color composition, so images with very different appearances can have similar color histograms. This problem is especially critical in large image databases, where many images have similar color histograms. In this paper, we propose an alternative to color histograms called a joint histogram, which incorporates additional information without sacrificing the robustness of color histograms. We create a joint histogram by selecting a set of local pixel features and constructing a multidimensional histogram. Each entry in a joint histogram contains the number of pixels in the image that are described by a particular combination of feature values. We describe a number of different joint histograms, and evaluate their performance for image retrieval on a database with over 210,000 images. On our benchmarks, joint histograms outperform color histograms by an order of magnitude.     

Advancing content-based image retrieval by exploiting image color and region features

In this paper, we propose a novel system that strives to achieve advanced content-based image retrieval using seamless combination of two complementary approaches: on the one hand, we propose a new color-clustering method to better capture color properties of the original images; on the other hand, expecting that image regions acquired from the original images inevitably contain many errors, we make use of the available erroneous, ill-segmented image regions to accomplish the object-region-based image retrieval. We also propose an effective image-indexing scheme to facilitate fast and efficient image matching and retrieval. The carefully designed experimental evaluation shows that our proposed image retrieval system surpasses other methods under comparison in terms of not only quantitative measures, but also image retrieval capabilities.     

Color indexing for efficient image retrieval

Content based image retrieval is an active area of research. Many approaches have been proposed to retrieve images based on matching of some features derived from the image content. Color is an important feature of image content. The problem with many traditional matching-based retrieval methods is that the search time for retrieving similar images for a given query image increases linearly with the size of the image database. We present an efficient color indexing scheme for similarity-based retrieval which has a search time that increases logarithmically with the database size.In our approach, the color features are extracted automatically using a color clustering algorithm. Then the cluster centroids are used as representatives of the images in 3-dimensional color space and are indexed using a spatial indexing method that usesR-tree. The worst case search time complexity of this approach isOn _q log(N^* n_avg)), whereN is the number of images in the database, andn _q andn _avg are the number of colors in the query image and the average number of colors per image in the database respectively. We present the experimental results for the proposed approach on two databases consisting of 337 Trademark images and 200 Flag images.     

Intelligent multimedia data: data + indices + inference

In this paper, we present a novel approach for multimedia data indexing and retrieval that is machine independent and highly flexible for sharing multimedia data across applications. Traditional multimedia data indexing and retrieval problems have been attacked using the central data server as the main focus, and most of the indexing and query-processing for retrieval are highly application dependent. This precludes the use of created indices and query processing mechanisms for multimedia data which, in general, have a wide variety of uses across applications. The approach proposed in this paper addresses three issues: 1. multimedia data indexing; 2. inference or query processing; and 3. combining indices and inference or query mechanism with the data to facilitate machine independence in retrieval and query processing. We emphasize the third issue, as typically multimedia data are huge in size and requires intra-data indexing. We describe how the proposed approach addresses various problems faced by the application developers in indexing and retrieval of multimedia data. Finally, we present two applications developed based on the proposed approach: video indexing; and video content authorization for presentation.     

Image retrieval using efficient local-area matching

We present an efficient and accurate method for retrieving images based on color similarity with a given query image or histogram. The method matches the query against parts of the image using histogram intersection. Efficient searching for the best matching subimage is done by pruning the set of subimages using upper bound estimates. The method is fast, has high precision and recall and also allows queries based on the positions of one or more objects in the database image. Experimental results showing the efficiency of the proposed search method, and high precision and recall of retrieval are presented. Received: 20 January 1997 / Accepted: 5 January 1998     

Analyzing scenery images by monotonic tree

Content-based image retrieval (CBIR) has been an active research area in the last ten years, and a variety of techniques have been developed. However, retrieving images on the basis of low-level features has proven unsatisfactory, and new techniques are needed to support high-level queries. Research efforts are needed to bridge the gap between high-level semantics and low-level features. In this paper, we present a novel approach to support semantics-based image retrieval. Our approach is based on the monotonic tree, a derivation of the contour tree for use with discrete data. The structural elements of an image are modeled as branches (or subtrees) of the monotonic tree. These structural elements are classified and clustered on the basis of such properties as color, spatial location, harshness and shape. Each cluster corresponds to some semantic feature. This scheme is applied to the analysis and retrieval of scenery images. Comparisons of experimental results of this approach with conventional techniques using low-level features demonstrate the effectiveness of our approach.     

Spatial Color Indexing Using Rotation,Translation, and Scale Invariant Anglograms

As color plays an essential role in image composition, many color indexing techniques have been studied for content-based image retrieval. This paper examines the use of a computational geometry-based spatial color indexing methodology for effective and efficient image retrieval. In this scheme, an image is evenly divided into a number of M * N non-overlapping blocks, and each individual block is abstracted as a unique feature point labeled with its spatial location and dominant colors. For each set of feature points labeled with the identical color, we construct a Delaunay triangulation and then compute the feature point histogram by discretizing and counting the angles produced by this triangulation. The concatenation of all these feature point histograms serves as the image index, the so-called color anglogram. An important contribution of this work is to encode the spatial color information using geometric triangulation, which is rotation, translation, and scale invariant. We have compared the proposed approach with two of the best performing of recent spatial color indexing schemes, Color-WISE and the color correlogram approaches, respectively, at image block and pixel levels of different granularity. Various experimental results demonstrate the efficacy of our techniques.     

Expert system for color image retrieval

Recently, as Web and various databases contain a large number of images, content-based image retrieval (CBIR) applications are greatly needed. This paper proposes a new image retrieval system using color-spatial information from those applications.First, this paper suggests two kinds of indexing keys to prune away irrelevant images to a given query image: major colors' set (MCS) signature related with color information and distribution block signature (DBS) related with spatial information. After successively applying these filters to a large database, we get only small amount of high potential candidates that are somewhat similar to a query image. Then we make use of the quad modeling (QM) method to set the initial weights of two-dimensional cell in a query image according to each major color. Finally, we retrieve more similar images from the database by comparing a query image with candidate images through a similarity measuring function associated with the weights. In that procedure, we use a new relevance feedback mechanism. This feedback enhances the retrieval effectiveness by dynamically modulating the weights of color-spatial information. Experiments show that the proposed system is not only efficient but also effective.     

Query by video clip

Typical digital video search is based on queries involving a single shot. We generalize this problem by allowing queries that involve a video clip (say, a 10-s video segment). We propose two schemes: (i) retrieval based on key frames follows the traditional approach of identifying shots, computing key frames from a video, and then extracting image features around the key frames. For each key frame in the query, a similarity value (using color, texture, and motion) is obtained with respect to the key frames in the database video. Consecutive key frames in the database video that are highly similar to the query key frames are then used to generate the set of retrieved video clips. (ii) In retrieval using sub-sampled frames, we uniformly sub-sample the query clip as well as the database video. Retrieval is based on matching color and texture features of the sub-sampled frames. Initial experiments on two video databases (basketball video with approximately 16,000 frames and a CNN news video with approximately 20,000 frames) show promising results. Additional experiments using segments from one basketball video as query and a different basketball video as the database show the effectiveness of feature representation and matching schemes.     

Spectral covariance and fuzzy regions for image indexing

To improve the discrimination power of color-indexing techniques, we encode a minimal amount of spatial information in the index. We tesselate each image with five partially overlapping, fuzzy regions. In the index, for each region in an image, we store its average color and the covariance matrix of the color distribution. A similiarity function of these color features is used to match query images with images in the database. In addition, we propose two measures to evaluate the performance of image-indexing techniques. We present experimental results using an image database which contains more than 11,600 color images.     

Adaptive image-smoothing using a coplanar matrix and its application to document image binarization

Abstract. For document images corrupted by various kinds of noise, direct binarization images may be severely blurred and degraded. A common treatment for this problem is to pre-smooth input images using noise-suppressing filters. This article proposes an image-smoothing method used for prefiltering the document image binarization. Conceptually, we propose that the influence range of each pixel affecting its neighbors should depend on local image statistics. Technically, we suggest using coplanar matrices to capture the structural and textural distribution of similar pixels at each site. This property adapts the smoothing process to the contrast, orientation, and spatial size of local image structures. Experimental results demonstrate the effectiveness of the proposed method, which compares favorably with existing methods in reducing noise and preserving image features. In addition, due to the adaptive nature of the similar pixel definition, the proposed filter output is more robust regarding different noise levels than existing methods. Received: October 31, 2001 / October 09, 2002 Correspondence to:L. Fan (e-mail: fanlixin@ieee.org)     

Efficient Content-Based Image Retrieval through Metric Histograms

This paper presents a new and efficient method for content-based image retrieval employing the color distribution of images. This new method, called metric histogram, takes advantage of the correlation among adjacent bins of histograms, reducing the dimensionality of the feature vectors extracted from images, leading to faster and more flexible indexing and retrieval processes. The proposed technique works on each image independently from the others in the dataset, therefore there is no pre-defined number of color regions in the resulting histogram. Thus, it is not possible to use traditional comparison algorithms such as Euclidean or Manhattan distances. To allow the comparison of images through the new feature vectors given by metric histograms, a new metric distance function MHD( ) is also proposed. This paper shows the improvements in timing and retrieval discrimination obtained using metric histograms over traditional ones, even when using images with different spatial resolution or thumbnails. The experimental evaluation of the new method, for answering similarity queries over two representative image databases, shows that the metric histograms surpass the retrieval ability of traditional histograms because they are invariant on geometrical and brightness image transformations, and answer the queries up to 10 times faster than the traditional ones.     

Combining multi-visual features for efficient indexing in a large image database

The optimized distance-based access methods currently available for multidimensional indexing in multimedia databases have been developed based on two major assumptions: a suitable distance function is known a priori and the dimensionality of the image features is low. It is not trivial to define a distance function that best mimics human visual perception regarding image similarity measurements. Reducing high-dimensional features in images using the popular principle component analysis (PCA) might not always be possible due to the non-linear correlations that may be present in the feature vectors. We propose in this paper a fast and robust hybrid method for non-linear dimensions reduction of composite image features for indexing in large image database. This method incorporates both the PCA and non-linear neural network techniques to reduce the dimensions of feature vectors so that an optimized access method can be applied. To incorporate human visual perception into our system, we also conducted experiments that involved a number of subjects classifying images into different classes for neural network training. We demonstrate that not only can our neural network system reduce the dimensions of the feature vectors, but that the reduced dimensional feature vectors can also be mapped to an optimized access method for fast and accurate indexing. Received 11 June 1998 / Accepted 25 July 2000 Published online: 13 February 2001     

A multi-level abstraction and modeling in video databases

In this paper, we propose a multi-level abstraction mechanism for capturing the spatial and temporal semantics associated with various objects in an input image or in a sequence of video frames. This abstraction can manifest itself effectively in conceptualizing events and views in multimedia data as perceived by individual users. The objective is to provide an efficient mechanism for handling content-based queries, with the minimum amount of processing performed on raw data during query evaluation. We introduce a multi-level architecture for video data management at different levels of abstraction. The architecture facilitates a multi-level indexing/searching mechanism. At the finest level of granularity, video data can be indexed based on mere appearance of objects and faces. For management of information at higher levels of abstractions, an object-oriented paradigm is proposed which is capable of supporting domain specific views.     

Automatic text segmentation and text recognition for video indexing

Efficient indexing and retrieval of digital video is an important function of video databases. One powerful index for retrieval is the text appearing in them. It enables content-based browsing. We present our new methods for automatic segmentation of text in digital videos. The algorithms we propose make use of typical characteristics of text in videos in order to enable and enhance segmentation performance. The unique features of our approach are the tracking of characters and words over their complete duration of occurrence in a video and the integration of the multiple bitmaps of a character over time into a single bitmap. The output of the text segmentation step is then directly passed to a standard OCR software package in order to translate the segmented text into ASCII. Also, a straightforward indexing and retrieval scheme is introduced. It is used in the experiments to demonstrate that the proposed text segmentation algorithms together with existing text recognition algorithms are suitable for indexing and retrieval of relevant video sequences in and from a video database. Our experimental results are very encouraging and suggest that these algorithms can be used in video retrieval applications as well as to recognize higher level semantics in videos.     

Integrating symbolic images into a multimedia database system using classification and abstraction approaches

Symbolic images are composed of a finite set of symbols that have a semantic meaning. Examples of symbolic images include maps (where the semantic meaning of the symbols is given in the legend), engineering drawings, and floor plans. Two approaches for supporting queries on symbolic-image databases that are based on image content are studied. The classification approach preprocesses all symbolic images and attaches a semantic classification and an associated certainty factor to each object that it finds in the image. The abstraction approach describes each object in the symbolic image by using a vector consisting of the values of some of its features (e.g., shape, genus, etc.). The approaches differ in the way in which responses to queries are computed. In the classification approach, images are retrieved on the basis of whether or not they contain objects that have the same classification as the objects in the query. On the other hand, in the abstraction approach, retrieval is on the basis of similarity of feature vector values of these objects. Methods of integrating these two approaches into a relational multimedia database management system so that symbolic images can be stored and retrieved based on their content are described. Schema definitions and indices that support query specifications involving spatial as well as contextual constraints are presented. Spatial constraints may be based on both locational information (e.g., distance) and relational information (e.g., north of). Different strategies for image retrieval for a number of typical queries using these approaches are described. Estimated costs are derived for these strategies. Results are reported of a comparative study of the two approaches in terms of image insertion time, storage space, retrieval accuracy, and retrieval time. Received June 12, 1998 / Accepted October 13, 1998     

Yoda,an adaptive soft classification model: content-based similarity queries and beyond

Abstract. Providing a customized result set based upon a user preference is the ultimate objective of many content-based image retrieval systems. There are two main challenges in meeting this objective: First, there is a gap between the physical characteristics of digital images and the semantic meaning of the images. Secondly, different people may have different perceptions on the same set of images. To address both these challenges, we propose a model, named Yoda, that conceptualizes content-based querying as the task of soft classifying images into classes. These classes can overlap, and their members are different for different users. The “soft” classification is hence performed for each and every image feature, including both physical and semantic features. Subsequently, each image will be ranked based on the weighted aggregation of its classification memberships. The weights are user-dependent, and hence different users would obtain different result sets for the same query. Yoda employs a fuzzy-logic based aggregation function for ranking images. We show that, in addition to some performance benefits, fuzzy aggregation is less sensitive to noise and can support disjunctive queries as compared to weighted-average aggregation used by other content-based image retrieval systems. Finally, since Yoda heavily relies on user-dependent weights (i.e., user profiles) for the aggregation task, we utilize the users' relevance feedback to improve the profiles using genetic algorithms (GA). Our learning mechanism requires fewer user interactions, and results in a faster convergence to the user's preferences as compared to other learning techniques. Correspondence to: Y.-S. Chen (E-mail: yishinc@usc.edu) This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC) and IIS-0082826, NIH-NLM R01-LM07061, DARPA and USAF under agreement nr. F30602-99-1-0524, and unrestricted cash gifts from NCR, Microsoft, and Okawa Foundation.