Similarity retrieval of iconic image database

The perception of spatial relationships among objects in a picture is one of the important selection criteria to discriminate and retrieve the images in an iconic image database system. The data structure called 2D string, proposed by Chang et al., is adopted to represent symbolic pictures. The 2D string preserves the objects' spatial knowledge embedded in images. Since spatial relationship is a fuzzy concept, the capability of similarity retrieval for the retrieval by subpicture is essential. In this paper, similarity measure based on 2D string longest common subsequence is defined. The algorithm for similarity retrieval is also proposed. Similarity retrieval provides the iconic image database with the distinguishing function different from a conventional database.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

Adaptive image segmentation for region-based object retrieval using generalized Hough transform

Finding an object inside a target image by querying multimedia data is desirable, but remains a challenge. The effectiveness of region-based representation for content-based image retrieval is extensively studied in the literature. One common weakness of region-based approaches is that perform detection using low level visual features within the region and the homogeneous image regions have little correspondence to the semantic objects. Thus, the retrieval results are often far from satisfactory. In addition, the performance is significantly affected by consistency in the segmented regions of the target object from the query and database images. Instead of solving these problems independently, this paper proposes region-based object retrieval using the generalized Hough transform (GHT) and adaptive image segmentation. The proposed approach has two phases. First, a learning phase identifies and stores stable parameters for segmenting each database image. In the retrieval phase, the adaptive image segmentation process is also performed to segment a query image into regions for retrieving visual objects inside database images through the GHT with a modified voting scheme to locate the target visual object under a certain affine transformation. The learned parameters make the segmentation results of query and database images more stable and consistent. Computer simulation results show that the proposed method gives good performance in terms of retrieval accuracy, robustness, and execution speed.     

FOCUS: A system for searching for multi-colored objects in a diverse image database

We describe a new multi-phase, color-based image retrieval system (FOCUS) which is capable of identifying multi-colored query objects in an image in the presence of significant, interfering backgrounds. The query object may occur in arbitrary sizes, orientations, and locations in the database images. Scale and rotation invariant color features have been developed to describe an image, such that the matching process is fast even in the case of complex images. The first phase of processing matches the query object color with the color content of an image computed as the peaks in the color histogram of the image. The second phase matches the spatial relationships between color regions in the image with the query using a spatial proximity graph (SPG) structure designed for the purpose. Processing at coarse granularity is preferred over pixel-level processing to produce simpler graphs, which significantly reduces computation time during matching. The speed of the system and the small storage overhead make it suitable for use in large databases with online user interfaces. Test results with multi-colored query objects from man-made and natural domains show that FOCUS is quite effective in handling interfering backgrounds and large variations in scale. The experimental results on a database of diverse images highlights the capabilities of the system.     

Θℜ-string: A geometry-based representation for efficientand effective retrieval of images by spatial similarity

A spatial similarity algorithm assesses the degree to which the spatial relationships among the domain objects in a database image conform to those specified in the query image. In this paper, we propose a geometry-based structure for representing the spatial relationships in the images and an associated spatial similarity algorithm. The proposed algorithm recognizes both translation, scale, and rotation variants of an image, and variants of the image generated by an arbitrary composition of translation, scale, and rotation transformations. The algorithm has Θ(n log n) time complexity in terms of the number of objects common to the database and query images. The retrieval effectiveness of the proposed algorithm is evaluated using the TESSA image collection     

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     

Image database design based on 9D-SPA representation for spatial relations

Spatial relationships between objects are important features for designing a content-based image retrieval system. We propose a new scheme, called 9D-SPA representation, for encoding the spatial relations in an image. With this representation, important functions of intelligent image database systems such as visualization, browsing, spatial reasoning, iconic indexing, and similarity retrieval can be easily achieved. The capability of discriminating images based on 9D-SPA representation is much more powerful than any spatial representation method based on minimum bounding rectangles or centroids of objects. The similarity measures using 9D-SPA representation provide a wide range of fuzzy matching capability in similarity retrieval to meet different user's requirements. Experimental results showed that our system is very effective in terms of recall and precision. In addition, the 9D-SPA representation can be incorporated into a two-level index structure to help reduce the search space of each query processing. The experimental results also demonstrated that, on average, only 0.1254 percent /spl sim/ 1.6829 percent of symbolic pictures (depending on various degrees of similarity) were accessed per query in an image database containing 50,000 symbolic pictures.     

图像中物体空间关系的表示及在检索中的应用

基于图像中物体之间的空间关系的图像检索往往受困于待处理的图像中物体种类和空间位置难以自动准确地获取。文中基于物体识别算法的输出,提出一种对物体空间关系的三元组表示法,给出基于这种表示方法对图像索引、相似度计算和检索排序的方法及允许用户使用查询词和空间关系表达查询需求的二维输入界面,并实现原型系统。这种表示法具有良好的鲁棒性,可容忍物体识别算法一定程度的误差,将物体识别得到的置信度加入三元组表示法置信度计算和排序算法中,减少物体识别结果误差对检索性能的影响。在原型系统上的实验表明,该系统在实验中对包含物体位置关系的检索给出更准确的结果,在NDCG@m、MAP、F@m上均优于现有系统。     

监视图像的采集与特征值的存储检索策略

针对示例图像的监视对象，就CCD采集图像数字化后，如何快速地在示例人面图像库中检索目标的问题，提出了一种基于非等长特征值的图像描述方法，并采用类聚的邻接有序链表存储结构来存储图像特征值。实验给出了具有控制匹配算法效率的阈值M和查准率的关系表，探讨了图像匹配检索中特征值存储的一种新方法，为示例监视的快速检索研究提供了一种新的思路。     

Ranking consistency for image matching and object retrieval

The goal of object retrieval is to rank a set of images by the similarity of their contents to those of a query image. However, it is difficult to measure image content similarity due to visual changes caused by varying viewpoint and environment. In this paper, we propose a simple, efficient method to more effectively measure content similarity from image measurements. Our method is based on the ranking information available from existing retrieval systems. We observe that images within the set which, when used as queries, yield similar ranking lists are likely to be relevant to each other and vice versa. In our method, ranking consistency is used as a verification method to efficiently refine an existing ranking list, in much the same fashion that spatial verification is employed. The efficiency of our method is achieved by a list-wise min-Hash scheme, which allows rapid calculation of an approximate similarity ranking. Experimental results demonstrate the effectiveness of the proposed framework and its applications.     

一种基于对象空间关系的图像检索模型

介绍一种基于空间相似的图像数据库检索模型，提出了空间相似度计算的算法，对对象的空间方位、拓扑关系、数量和空间关系局部高度相似等因素都作了全面考虑，详细阐述空间相似度与局部相似对象簇的求解过程，建立的模型不仅能识别经平移、缩放和旋转交换的图像，而且能识别图像的对称变换，通过实验验证，表明检索模型的图像搜索效率高。     

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     

Spatial inference and similarity retrieval of an intelligent image database system based on object's spanning representation

In this paper, we presented a novel image representation method to capture the information about spatial relationships between objects in a picture. Our method is more powerful than all other previous methods in terms of accuracy, flexibility, and capability of discriminating pictures. In addition, our method also provides different degrees of granularity for reasoning about directional relations in both 8- and 16-direction reference frames. In similarity retrieval, our system provides twelve types of similarity measures to support flexible matching between the query picture and the database pictures. By exercising a database containing 3600 pictures, we successfully demonstrated the effectiveness of our image retrieval system. Experiment result showed that 97.8% precision rate can be achieved while maintaining 62.5% recall rate; and 97.9% recall rate can be achieved while maintaining 51.7% precision rate. On an average, 86.1% precision rate and 81.2% recall rate can be achieved simultaneously if the threshold is set to 0.5 or 0.6. This performance is considered to be very good as an information retrieval system.     

Image database indexing using JPEG coefficients

Image database indexing is used for efficient retrieval of images in response to a query expressed as an example image. The query image is processed to extract information that is matched against the index to provide pointers to similar images. We present a technique that facilitates content similarity-based retrieval of jpeg-compressed images without first having to uncompress them. The technique is based on an index developed from a subset of jpeg coefficients and a similarity measure to determine the difference between the query image and the images in the database. This method offers substantial efficiency as images are processed in compressed format, information that was derived during the original compression of the images is reused, and extensive early pruning is possible. Initial experiments with the index have provided encouraging results. The system outputs a set of ranked images in the database with respect to the query using the similarity measure, and can be limited to output a specified number of matched images by changing the threshold match.     

Efficient image retrieval through vantage objects

We describe a new indexing structure for general image retrieval that relies solely on a distance function giving the similarity between two images. For each image object in the database, its distance to a set of m predetermined vantage objects is calculated; the m-vector of these distances specifies a point in the m-dimensional vantage space. The database objects that are similar (in terms of the distance function) to a given query object can be determined by means of an efficient nearest-neighbor search on these points. We demonstrate the viability of our approach through experimental results obtained with two image databases, one consisting of about 5200 raster images of stamps, the other containing about 72,000 hieroglyphic polylines.     

Image Indexing and Retrieval Using Object-based Point Feature Maps

Multimedia data such as audios, images, and videos are semantically richer than standard alphanumeric data. Because of the nature of images as combinations of objects, content-based image retrieval should allow users to query by image objects with finer granularity than a whole image. In this paper, we address a web-based object-based image retrieval (OBIR) system . Its prototype implementation particularly explores image indexing and retrieval using object-based point feature maps. An important contribution of this work is its ability to allow a user to easily incorporate both low- and high-level semantics into an image query. This is accomplished through the inclusion of the spatial distribution of point-based image object features, the spatial distribution of the image objects themselves, and image object class identifiers. We introduce a generic image model, give our ideas on how to represent the low- and high-level semantics of an image object, discuss our notion of image object similarity, and define four types of image queries supported by the OBIR system. We also propose an application of our approach to neurological surgery training.     

Spatial reasoning and similarity retrieval for image database systems based on RS-strings

In this paper, we propose a rotation-invariant spatial knowledge representation called RS-string. Then we present the string generation algorithm to automatically generate RS-strings for segmented pictures. We also propose the spatial reasoning and similarity retrieval algorithms based on RS-strings. The similarity retrieval algorithm is much more flexible than all previous 2D string representations because our approach can consider every possible view of a query picture. Thus the system does not require the user to provide a query picture which must have the same orientation as that of a database picture. Finally, we provide several examples to demonstrate the capabilities of spatial reasoning and similarity retrieval based on the RS-string representation.     

Content-based image retrieval based on a fuzzy approach

A typical content-based image retrieval (CBIR) system would need to handle the vagueness in the user queries as well as the inherent uncertainty in image representation, similarity measure, and relevance feedback. We discuss how fuzzy set theory can be effectively used for this purpose and describe an image retrieval system called FIRST (fuzzy image retrieval system) which incorporates many of these ideas. FIRST can handle exemplar-based, graphical-sketch-based, as well as linguistic queries involving region labels, attributes, and spatial relations. FIRST uses fuzzy attributed relational graphs (FARGs) to represent images, where each node in the graph represents an image region and each edge represents a relation between two regions. The given query is converted to a FARG, and a low-complexity fuzzy graph matching algorithm is used to compare the query graph with the FARGs in the database. The use of an indexing scheme based on a leader clustering algorithm avoids an exhaustive search of the FARG database. We quantify the retrieval performance of the system in terms of several standard measures.     

Utilizing similarity relationships among existing data for high accuracy processing of content-based image retrieval

Retrieving similar images based on its visual content is an important yet difficult problem. We propose in this paper a new method to improve the accuracy of content-based image retrieval systems. Typically, given a query image, existing retrieval methods return a ranked list based on the similarity scores between the query and individual images in the database. Our method goes further by relying on an analysis of the underlying connections among individual images in the database to improve this list. Initially, we consider each image in the database as a query and use an existing baseline method to search for its likely similar images. Then, the database is modeled as a graph where images are nodes and connections among possibly similar images are edges. Next, we introduce an algorithm to split this graph into stronger subgraphs, based on our notion of graph’s strength, so that images in each subgraph are expected to be truly similar to each other. We create for each subgraph a structure called integrated image which contains the visual features of all images in the subgraph. At query time, we compute the similarity scores not only between the query and individual database images but also between the query and the integrated images. The final similarity score of a database image is computed based on both its individual score and the score of the integrated image that it belongs to. This leads effectively to a re-ranking of the retrieved images. We evaluate our method on a common image retrieval benchmark and demonstrate a significant improvement over the traditional bag-of-words retrieval model.