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.     

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     

2D C-Tree Spatial Representation for Iconic Image

The 2D string approaches provide a natural way of constructing iconic indexing for images. The 2D C-string representation with an efficient cutting mechanism is more characteristic of spatial knowledge and efficient in the representation of iconic images. However, the computation of object ranks in a 2D C-string might make the inference of spatial reasoning somewhat complicated. This shortcoming is overcome by the 2D C-tree representation. The 2D C-tree not only keeps the comprehensive spatial knowledge in the original 2D C-string, but also the ordered labeled tree is more suitable for spatial reasoning and image retrieval. The spatial knowledge can be derived directly from the inference rules embedded in the characteristic structure of the 2D C-tree representation.     

2D Z-string: A new spatial knowledge representation for image databases

The knowledge structure called the 2D C⁺-string, proposed by Huang et al., to represent symbolic pictures allows a natural way to construct iconic indexes for images. According to the cutting mechanism of the 2D C⁺-string, an object may be partitioned into several subparts. The number of partitioned subparts is bounded to O(n²), where n is the number of objects in the image. Hence, the string length is also bounded to O(n²). In this paper, we propose a new spatial knowledge representation called the 2D Z-string. Since there are no cuttings between objects in the 2D Z-string, the integrity of objects is preserved and the string length is bounded to O(n). Finally, some experiments are conducted to compare the performance of both approaches.     

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.     

A fractal-based clustering approach in large visual database systems

Large visual database systems require effective and efficient ways of indexing and accessing visual data on the basis of content. In this process, significant features must first be extracted from image data in their pixel format. These features must then be classified and indexed to assist efficient access to image content. With the large volume of visual data stored in a visual database, image classification is a critical step to achieve efficient indexing and retrieval. In this paper, we investigate an effective approach to the clustering of image data based on the technique of fractal image coding, a method first introduced in conjunction with fractal image compression technique. A joint fractal coding technique, applicable to pairs of images, is used to determine the degree of their similarity. Images in a visual database can be categorized in clusters on the basis of their similarity to a set of iconic images. Classification metrics are proposed for the measurement of the extent of similarity among images. By experimenting on a large set of texture and natural images, we demonstrate the applicability of these metrics and the proposed clustering technique to various visual database applications.     

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

Inference and retrieval of facial images

Attempts have been made to extend SQL to work with multimedia databases. We are reserved on the representation ability of extended SQL to cope with the richness in content of multimedia data. In this paper we present an example of a multimedia database system, Computer Aided Facial Image Inference and Retrieval system (CAFIIR). The system stores and manages facial images and criminal records, providing necessary functions for crime identification. We would like to demonstrate some core techniques for multimedia database with CAFIIR system. Firstly, CAFIIR is a integrated system. Besides database management, there are image analysis, image composition, image aging, and report generation subsystems, providing means for problem solving. Secondly, the richness of multimedia data urges feature-based database for their management. CAFIIR is feature-based. A indexing mechanism,iconic index, has been proposed for indexing facial images using hierarchical self-organization neural network. The indexing method operates on complex feature measures and provides means for visual navigation. Thirdly, special retrieval methods for facial images have been developed, including visual browsing, similarity retrieval, free text retrieval and fuzzy retrieval.     

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.     

An efficient iconic indexing strategy for image rotation and reflection in image databases

Spatial relationships are important issues for similarity-based retrieval in many image database applications. With the popularity of digital cameras and the related image processing software, a sequence of images are often rotated or flipped. That is, those images are transformed in the rotation orientation or the reflection direction. However, many iconic indexing strategies based on symbolic projection are sensitive to rotation or reflection. Therefore, these strategies may miss the qualified images, when the query is issued in the orientation different from the orientation of the database images. To solve this problem, some researchers proposed a function to map the spatial relationship to its transformed one. However, this mapping consists of several conditional statements, which is time-consuming. Thus, in this paper, we propose an efficient iconic indexing strategy, in which we carefully assign a unique bit pattern to each spatial relationship and record the spatial information based on the bit patterns in a matrix. Without generating the rotated or flipped image, we can directly derive the index of the rotated or flipped image from the index of the original one by bit operations and matrix manipulation. In our performance study, we analyze the time complexity of our proposed strategy and show the efficiency of our proposed strategy according to the simulation results. Moreover, we implement a prototype to validate our proposed strategy.     

Iconic pictorial retrieval using multiple attributes and spatial relationships

This work is on the use of multiple attributes or features and spatial relationships, with the help of a user interface based on an iconic paradigm, to retrieve images represented by iconic pictures. An icon has texture, color, and text attributes. Texture is represented by three statistical textural properties, namely, coarseness, contrast, and directionality. For text, the vector space model is used. For color, a representation based on a modified color histogram method which is less storage-intensive is proposed. The final icon similarity is the combination of the attribute similarity values using a proven adaptive algorithm. 2-D strings and its variants are commonly used to represent spatial relationships and perform spatial reasoning. We extended the method to include similarity ranking by using different similarity functions for different spatial relationships and an efficient embedding algorithm. Furthermore, our method solves the problem of query expressiveness which all methods based on 2-D string representations suffer from.     

Information retrieval in document image databases

With the rising popularity and importance of document images as an information source, information retrieval in document image databases has become a growing and challenging problem. In this paper, we propose an approach with the capability of matching partial word images to address two issues in document image retrieval: word spotting and similarity measurement between documents. First, each word image is represented by a primitive string. Then, an inexact string matching technique is utilized to measure the similarity between the two primitive strings generated from two word images. Based on the similarity, we can estimate how a word image is relevant to the other and, thereby, decide whether one is a portion of the other. To deal with various character fonts, we use a primitive string which is tolerant to serif and font differences to represent a word image. Using this technique of inexact string matching, our method is able to successfully handle the problem of heavily touching characters. Experimental results on a variety of document image databases confirm the feasibility, validity, and efficiency of our proposed approach in document image retrieval.     

Arrangement: a spatial relation between parts for evaluatingsimilarity of tomographic section

Medical tomographic images are formed by the intersection of the image plane and an object. As the image plane changes, different parts of the object come in view or drop out of view. However, for small changes of the image plane, most parts continue to remain visible and their qualitative embedding in the image remains similar. Therefore, similarity of part embeddings can be used to infer similarity of image planes. Part embeddings are useful features for other vision applications as well. In view of this, a spatial relation called “arrangement” is proposed to describe part embeddings. The relation describes how each part is surrounded by its neighbors. Further, a metric for arrangements is formulated by expressing arrangements in terms of the Voronoi diagram of the parts. Arrangements and their metric are used to retrieve images by image plane similarity in a cardiac magnetic resonance image database. Experiments with the database are reported which (1) validate the observation that similarity of image planes can be inferred from similarity of part embeddings, and (2) compare the performance of arrangement based image retrieval with that of expert radiologists     

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.     

An intelligent image database system

A prototype intelligent image database system (IIDS) that is based on a novel pictorial data structure is presented. This prototype system supports spatial reasoning, flexible image information retrieval, visualization, and traditional image database operations. A pictorial data structure, based on 2-D strings, provides an efficient means for iconic indexing in image database systems and spatial reasoning. The modular design of IIDS facilitates its implementation. Further extensions of the prototype system are discussed     

改进颜色和小波变换纹理的图像检索方法研究

针对传统图像检索无法体现对检索示例图像中多个不同对象的检索要求程度的问题,提出一种改进颜色特征和小波变换纹理特征的图像检索方法。首先提取出图像的多个感兴趣区域,由感兴趣的不同程度分别赋予不同大小的权值;然后提取颜色特征和纹理特征,分别用对应位置相似度计算、感兴趣区域与检索数据库中图像整体的相似度计算和整体检索示例图像与检索图像数据库中图像相似度计算三种不同方法计算出两幅图像的相似度,取最大的相似度作为两幅图像的最终相似度;对检索示例图像与检索数据库中每个图像的相似度按大小进行排序,选择最相似的图像作为检索结果。实验结果表明,该方法提高了对图像检索的性能,体现了个性化检索,对图像检索具有很好的效果。     

Learning similarity measure for natural image retrieval with relevance feedback

A new scheme of learning similarity measure is proposed for content-based image retrieval (CBIR). It learns a boundary that separates the images in the database into two clusters. Images inside the boundary are ranked by their Euclidean distances to the query. The scheme is called constrained similarity measure (CSM), which not only takes into consideration the perceptual similarity between images, but also significantly improves the retrieval performance of the Euclidean distance measure. Two techniques, support vector machine (SVM) and AdaBoost from machine learning, are utilized to learn the boundary. They are compared to see their differences in boundary learning. The positive and negative examples used to learn the boundary are provided by the user with relevance feedback. The CSM metric is evaluated in a large database of 10009 natural images with an accurate ground truth. Experimental results demonstrate the usefulness and effectiveness of the proposed similarity measure for image retrieval.