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.     

Symbolic picture retrieval by relative–metric spatial relations

Symbolic pictures can be used for iconic indexing, spatial reasoning, and similarity retrieval in the design of intelligent image database systems. [S. K. Chang, C. W. Yan, Donald C. Dimitroff, and Timothy Arndt, IEEE Trans. Software Engineering 1988, 14, 681–688; S.‐K. Chang, Principles of Pictorial Information Systems Design, Prentice‐Hall, New York, 1989.] However, previous approaches to designing such systems usually ignore relative‐metric information on symbolic pictures and cause several deficiencies in indexing, spatial reasoning, and retrieval. In our approach, we extract relative‐metric information from symbolic pictures and use such information to help establish indexes based on an improvement from a minimal perfect hashing scheme. As a result, more accurate picture retrieval can be achieved through our indexing mechanism. Capabilities in spatial reasoning and query representation/processing are also improved. By utilizing relative‐metric spatial relations, an image database system becomes more flexible and intelligent. ©2000 John Wiley & Sons, Inc.     

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.     

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.     

Graph-based representation for similarity retrieval of symbolic images

Image retrieval from an image database by the image objects and their spatial relationships has emerged as an important research subject in these decades. To retrieve images similar to a given query image, retrieval methods must assess the similarity degree between a database image and the query image by the extracted features with acceptable efficiency and effectiveness. This paper proposes a graph-based model SRG (spatial relation graph) to represent the semantic information of the contained objects and their spatial relationships in an image with no file annotation. In an SRG graph, the image objects are symbolized by the predefined class names as vertices and the spatial relations between object pairs are represented as arcs. The proposed model assesses the similarity degree between two images by calculating the maximum common subgraph of two corresponding SRG’s through intersection, which has quadratic time complexity owing to the characteristics of SRG. Its efficiency remains quadratic regardless of the duplication rate of the object symbols. The extended model SRG_T is also proposed, with the same time complexity, for the applications that need to consider the topological relations among objects. A synthetic symbolic image database and an existing image dataset are used in the conducted experiments to verify the performance of the proposed models. The experimental results show that the proposed models have compatible retrieval quality with remarkable efficiency improvements compared with three well-known methods LCS_Clique, SIM_R, and 2D Be-string, where LCS_Clique utilizes the number of objects in the maximum common subimage as its similarity function, SIM_R uses accumulation-based similarity function of similar object pairs, and 2D Be-string calculates the similarity of 2D patterns by the linear combination of two 1D similarities.     

Spatial match retrieval based on direction signatures using multiple key hashing scheme

The spatial relationships among pictorial objects are important spatial characteristics in image database systems. Based on the concept of 9-DLT representation, we propose a new method for effective storage utilization and picture retrieval. First, we transform a symbolic picture into a set of triples associated with pairwise spatial relationships among objects. Then, an associated normalized signature record with nine attributes is specified. Finally, each normalized record of this image database can be well allocated by using our proposed multiple key hashing scheme and can be fast accessed for spatial match retrieval. The performance formula for spatial picture retrieval is presented and the theoretically optimal solutions to the bit lengths of all the attributes are derived in certain case. Also, we give a systematic method to solve the feasible bit lengths for the attributes based on the method proposed by Chang. © 1997 John Wiley & Sons, Inc.     

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     

Signature file as a spatial filter for iconic image database

The problems of efficient data storage and data retrieval are important issues in the design of image database systems. A data structure called a 2-D string, which represents symbolic pictures preserving spatial knowledge, was proposed by Chang et al. It allows a natural way to construct iconic indexes for pictures. We proposed a data structure 2-D B-string to characterize the spatial knowledge embedded in images. It is powerful enough to describe images with partly overlapping or completely overlapping objects without the need of partitioning objects. When there exist a large volume of complex images in the image database, the processing time for image retrieval is tremendous. It is essential to develop efficient access methods for retrieval. In this paper, access methods, to different extents of precision, for retrieval of desired images encoded in 2-D B-strings are proposed. The signature file acting as a spatial filter of image database is based on disjoint coding and superimposed coding techniques. It provides an efficient way to retrieve images in image databases.     

Virtual images for similarity retrieval in image databases

We introduce the virtual image, an iconic index suited for pictorial information access in a pictorial database, and a similarity retrieval approach based on virtual images to perform content-based retrieval. A virtual image represents the spatial information contained in a real image in explicit form by means of a set of spatial relations. This is useful to efficiently compute the similarity between a query and an image in the database. We also show that virtual images support real-world applications that require translation, reflection, and/or rotation invariance of image 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.     

Reasoning about pictures and similarity retrieval for image information systems based on SK-set knowledge representation

Spatial reasoning and similarity retrieval are two important functions of any image information system. Good spatial knowledge representation for images is necessary to adequately support these two functions. In this paper, we propose a new spatial knowledge representation, called the SK-set based on morphological skeleton theories. Spatial reasoning algorithms which achieve more accurate results by directly analysing skeletons are described. SK-set facilitates browsing and progressive visualization. We also define four new types of similarity measures and propose a similarity retrieval algorithm for performing image retrieval. Moreover, using SK-set as a spatial knowledge representation will reduce the storage space required by an image database significantly.     

Θℜ-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     

基于长期学习的多媒体数据库相似性检索

基于内容的相似性检索是多媒体数据库研究的重要内容之一.近年来,利用用户相关反馈技术改善检索性能的研究成为新的热点.但是,在传统的相关反馈方法中,系统积累的反馈历史数据未得到充分利用.为了进一步提高检索系统的性能,提出了一种对相关反馈序列日志进行协同过滤在线分析的相关反馈检索方法.该方法使用编辑距离对用户的反馈序列进行相似性度量,并根据协同过滤的思想对数据库中的媒体对象与当前检索的语义相关性进行预测,从而改善检索的效果.实现了一个图像数据库检索原型系统.对11 000幅图像数据库进行的实验表明,与传统相关反馈技术相比,该方法对检索性能有明显的改善.     

A content based image retrieval system for a biological specimen collection

Digital photography and decreasing cost of storing data in digital form has led to an explosion of large digital image repositories. Since the number of images in image databases can be large (millions in some cases) it is important to develop automated tools to search them. In this paper, we present a content based image retrieval system for a database of parasite specimen images. Unlike most content based image retrieval systems, where the database consists of objects that vary widely in shape and size, the objects in our database are fairly uniform. These objects are characterized by flexible body shapes, but with fairly rigid ends. We define such shapes to be FleBoRE (Flexible Body Rigid Extremities) objects, and present a shape model for this class of objects. We have defined similarity functions to compute the degree of likeness between two FleBoRE objects and developed automated methods to extract them from specimen images. The system has been tested with a collection of parasite images from the Harold W. Manter Laboratory for Parasitology. Empirical and expert-based evaluations show that query by shape approach is effective in retrieving specimens of the same class.