Knowledge-based image retrieval with spatial and temporalconstructs

A knowledge-based approach to retrieve medical images by feature and content with spatial and temporal constructs is developed. Selected objects of interest in an image are segmented and contours are generated. Features and content are extracted and stored in a database. Knowledge about image features can be expressed as a type abstraction hierarchy (TAH), the high-level nodes of which represent the most general concepts. Traversing TAH nodes allows approximate matching by feature and content if an exact match is not available. TAHs can be generated automatically by clustering algorithms based on feature values in the databases and hence are scalable to large collections of image features. Since TAHs are generated based on user classes and applications, they are context- and user-sensitive. A knowledge-based semantic image model is proposed to represent the various aspects of an image object's characteristics. The model provides a mechanism for accessing and processing spatial, evolutionary and temporal queries. A knowledge-based spatial temporal query language (KSTL) has been developed that extends ODMG's OQL and supports approximate matching of features and content, conceptual terms and temporal logic predicates. Further, a visual query language has been developed that accepts point-click-and-drag visual iconic input on the screen that is then translated into KSTL. User models are introduced to provide default parameter values for specifying query conditions. We have implemented the KMeD (Knowledge-based Medical Database) system using these concepts     

SemQuery: semantic clustering and querying on heterogeneous features for visual data

The effectiveness of content-based image retrieval can be enhanced using heterogeneous features embedded in the images. However, since the features in texture, color, and shape are generated using different computation methods and thus may require different similarity measurements, the integration of the retrievals on heterogeneous features is a nontrivial task. We present a semantics-based clustering and indexing approach, termed SemQuery, to support visual queries on heterogeneous features of images. Using this approach, the database images are classified based on their heterogeneous features. Each semantic image cluster contains a set of subclusters that are represented by the heterogeneous features that the images contain. An image is included in a semantic cluster if it falls within the scope of all the heterogeneous clusters of the semantic cluster. We also design a neural network model to merge the results of basic queries on individual features. A query processing strategy is then presented to support visual queries on heterogeneous features. An experimental analysis is conducted and presented to demonstrate the effectiveness and efficiency of the proposed approach.     

An object-based image retrieval system for digital libraries

A novel approach to clustering for image segmentation and a new object-based image retrieval method are proposed. The clustering is achieved using the Fisher discriminant as an objective function. The objective function is improved by adding a spatial constraint that encourages neighboring pixels to take on the same class label. A six-dimensional feature vector is used for clustering by way of the combination of color and busyness features for each pixel. After clustering, the dominant segments in each class are chosen based on area and used to extract features for image retrieval. The color content is represented using a histogram, and Haar wavelets are used to represent the texture feature of each segment. The image retrieval is segment-based; the user can select a query segment to perform the retrieval and assign weights to the image features. The distance between two images is calculated using the distance between features of the constituent segments. Each image is ranked based on this distance with respect to the query image segment. The algorithm is applied to a pilot database of natural images and is shown to improve upon the conventional classification and retrieval methods. The proposed segmentation leads to a higher number of relevant images retrieved, 83.5% on average compared to 72.8 and 68.7% for the k-means clustering and the global retrieval methods, respectively.     

CoBase: A scalable and extensible cooperative information system

A new generation of information systems that integrates knowledge base technology with database systems is presented for providing cooperative (approximate, conceptual, and associative) query answering. Based on the database schema and application characteristics, data are organized into Type Abstraction Hierarchies (TAHs). The higher levels of the hierarchy provide a more abstract data representation than the lower levels. Generalization (moving up in the hierarchy), specialization (moving down the hierarchy), and association (moving between hierarchies) are the three key operations in deriving cooperative query answers for the user. Based on the context, the TAHs can be constructed automatically from databases. An intelligent dictionary/directory in the system lists the location and characteristics (e.g., context and user type) of the TAHs. CoBase also has a relaxation manager to provide control for query relaxations. In addition, an explanation system is included to describe the relaxation and association processes and to provide the quality of the relaxed answers. CoBase uses a mediator architecture to provide scalability and extensibility. Each cooperative module, such as relaxation, association, explanation, and TAH management, is implemented as a mediator. Further, an intelligent directory mediator is provided to direct mediator requests to the appropriate service mediators. Mediators communicate with each other via KQML. The GUI includes a map server which allows users to specify queries graphically and incrementally on the map, greatly improving querying capabilities. CoBase has been demonstrated to answer imprecise queries for transportation and logistic planning applications. Currently, we are applying the CoBase methodology to match medical image (X-ray, MRI) features and approximate matching of emitter signals in electronic warfare applications.This work supported by ARPA contract F30602-94-C-0207.     

A semantic modeling approach for image retrieval by content

We introduce a semantic data model to capture the hierarchical, spatial, temporal, and evolutionary semantics of images in pictorial databases. This model mimics the user's conceptual view of the image content, providing the framework and guidelines for preprocessing to extract image features. Based on the model constructs, a spatial evolutionary query language (SEQL), which provides direct image object manipulation capabilities, is presented. With semantic information captured in the model, spatial evolutionary queries are answered efficiently. Using an object-oriented platform, a prototype medical-image management system was implemented at UCLA to demonstrate the feasibility of the proposed approach.     

Information extraction from images of paper-based maps

The design of a system to extract information automatically from paper-based maps and answer queries related to spatial features and structure of geographic data is considered. The foundation of such a system is a set of image-analysis algorithms for extracting spatial features. Efficient algorithms to detect symbols, identify and track various types of lines, follow closed contours, compute distances, find shortest paths, etc. from simplified map images have been developed. A query processor analyzes the queries presented by the user in a predefined syntax, controls the operation of the image processing algorithms, and interacts with the user. The query processor is written in Lisp and calls image-analysis routines written in Fortran     

面向存在不确定对象的组最近邻查询方法

组最近邻查询是空间对象查询领域的一类重要查询,通过该查询可找到距离给定查询点集最近的空间对象.由于图像分辨率或解析度的限制等因素,空间对象的存在不确定性广泛存在于某些涉及图像处理的查询应用中.这些对象位置数据的存在不确定性会对组最近邻查询结果产生影响.本文给出面向存在不确定对象的概率阈值组最近邻查询定义,设计了高效的查询处理机制,通过剪枝优化等手段提高概率阈值组最近邻查询效率,并进一步提出了高效概率阈值组最近邻查询算法.采用多个真实数据集对概率阈值组最近邻算法进行了实验验证,结果表明所提算法具有良好的查询效率.     

Pictorial Query Specification for Browsing Through Spatially Referenced Image Databases

A pictorial query specification technique that enables the formulation of complex pictorial queries for browsing through a collection of spatially referenced images is presented. It is distinguished from most other methods by the fact that in these methods the query image specifies a target database image in its entirety whereas in our approach the query image specifies the combination of objects that the target database image should contain rather than being treated as a whole image. The query objects are represented by shape features although other features such as color, texture or wavelets could also be used. Using our technique, it is possible to specify which particular objects should appear in the target images as well as how many occurrences of each object are required. Moreover, it is possible to specify the minimum required certainty of matching between query-image objects and database-image objects, as well as to impose spatial constraints that specify bounds on the distance between objects and the relative direction between them. These spatial constraints can also be used to specify other topological relations such as enclosure, intersection, overlap, etc. Each pictorial query is composed of one or more query images. Each query image is constructed by selecting the required query objects and positioning them according to the desired spatial configuration. Boolean combinations of two or more query images are also possible by use of AND and OR operators. A query image may be negated in order to specify conditions that should not be satisfied by the database images that are retrieved successfully. In addition, a capability is provided to specify whether the same instance of an object is to be used when it appears in more than one of the query images that make up the pictorial query, or whether two different instances are allowed. Several example queries are given that demonstrate the expressive power of this query specification method. An algorithm for retrieving all database images that conform to a given pictorial query specification is presented. The user interface for using this pictorial query specification method to browse the results in a map image database application is described and illustrated via screen shots.     

A NEW METHOD FOR FUZZY QUERY PROCESSING IN RELATIONAL DATABASE SYSTEMS

In this paper, we present a new method for fuzzy query processing in relational database systems based on automatic clustering techniques and weighting concepts. The proposed method allows the query conditions and the weights of query items of users' fuzzy SQL queries to be described by linguistic terms represented by fuzzy numbers. Because the proposed fuzzy query processing method allows the users to construct their fuzzy queries more conveniently, the existing relational database systems will be more intelligent and more flexible to the users.     

A formal framework for image indexing with triples: Toward a concept-based image retrieval

This paper provides a formal specification for concept-based image retrieval using triples. To effectively manage a vast amount of images, we may need an image retrieval system capable of indexing and searching images based on the characteristics of their content. However, such a content-based image retrieval technique alone may not satisfy user queries if retrieved images turn out to be relevant only when they are conceptually related with the queries. In this paper, we develop an image retrieval mechanism to extract semantics of images based on triples. The semantics can be captured by deriving concepts from its constituent objects and spatial relationships between them. The concepts are basically composite objects formed from the aggregation of the constituents. In our mechanism, all the spatial relationships between objects including the concepts are uniformly represented by triples, which are used for indexing images as well as capturing their semantics. We also develop a query evaluation for supporting the concept-based image retrieval. ©1999 John Wiley & Sons, Inc.     

Unsupervised image retrieval framework based on rule base system

This paper introduces unsupervised image retrieval framework based on a rule base system. The proposed framework makes use of geometric moments (GMs) for features extraction. The main advantage with the GMs is that image coordinate transformations can be easily expressed and analyzed in terms of the corresponding transformations in the moment space. These features are used to perform the image mining for acquiring clustering knowledge from a large empirical images database. Irrelevance between images of the same cluster is precisely considered in the proposed framework through a relevant feedback phase followed by a novel clustering refinement model. The images and their corresponding classes pass to a rule base algorithm for extracting a set of accurate rules. These rules are pruning and may reduce the dimensionality of the extracted features. The advantage of the proposed framework is reflected in the retrieval process, which is limited to the images in the class of rule matched with the query image features. Experiments show that the proposed model achieves a very good performance in terms of the average precision, recall and retrieval time compared with other models.     

显著特征融合的主颜色聚类分割算法*

针对颜色密度聚类分割模型容易产生误分割的问题,提出基于视觉显著性调节的主颜色聚类分割算法.首先,根据空间颜色信息和Mean-shift算法平滑结果分别计算图像的全局显著特征和区域显著特征,并融合2类显著特征作为特征空间聚类的约束项.然后,采用核密度估计方法计算图像主颜色作为初始类,并将显著特征作为调节因子进行聚类分割.最后,进行区域合并.在标准的分割图像库上进行实验并与多种算法对比,结果表明,文中算法具有更高的区域轮廓准确度,并且有效利用图像显著特征,降低密度聚类形成的区域不一致性,提高像素聚类的精度和分割的鲁棒性.     

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.     

Spatial query processing for fuzzy objects

Range and nearest neighbor queries are the most common types of spatial queries, which have been investigated extensively in the last decades due to its broad range of applications. In this paper, we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS communities. Existing research on fuzzy objects mainly focuses on modeling basic fuzzy object types and operations, leaving the processing of more advanced queries largely untouched. In this paper, we propose two new kinds of spatial queries for fuzzy objects, namely single threshold query and continuous threshold query, to determine the query results which qualify at a certain probability threshold and within a probability interval, respectively. For efficient single threshold query processing, we optimize the classical R-tree-based search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To enhance the performance of continuous threshold queries, effective pruning rules are developed to reduce the search space and speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques is verified with an extensive set of experiments using both synthetic and real datasets.     

Object-based visual query suggestion

State-of-the-art visual search systems allow to retrieve efficiently small rigid objects in very large datasets. They are usually based on the query-by-window paradigm: a user selects any image region containing an object of interest and the system returns a ranked list of images that are likely to contain other instances of the query object. User’s perception of these tools is however affected by the fact that many submitted queries actually return nothing or only junk results (complex non-rigid objects, higher-level visual concepts, etc.). In this paper, we address the problem of suggesting only the object’s queries that actually contain relevant matches in the dataset. This requires to first discover accurate object’s clusters in the dataset (as an offline process); and then to select the most relevant objects according to user’s intent (as an on-line process). We therefore introduce a new object’s instances clustering framework based on a major contribution: a bipartite shared-neighbours clustering algorithm that is used to gather object’s seeds discovered by matching adaptive and weighted sampling. Shared nearest neighbours methods were not studied beforehand in the case of bipartite graphs and never used in the context of object discovery. Experiments show that this new method outperforms state-of-the-art object mining and retrieval results on the Oxford Building dataset. We finally describe two object-based visual query suggestion scenarios using the proposed framework and show examples of suggested object queries.     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

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.     

Efficient processing of spatial joins with DOT-based indexing

A spatial join is a query that searches for a set of object pairs satisfying a given spatial relationship from a database. It is one of the most costly queries, and thus requires an efficient processing algorithm that fully exploits the features of the underlying spatial indexes. In our earlier work, we devised a fairly effective algorithm for processing spatial joins with double transformation (DOT) indexing, which is one of several spatial indexing schemes. However, the algorithm is restricted to only the one-dimensional cases. In this paper, we extend the algorithm for the two-dimensional cases, which are general in Geographic Information Systems (GIS) applications. We first extend DOT to two-dimensional original space. Next, we propose an efficient algorithm for processing range queries using extended DOT. This algorithm employs the quarter division technique and the tri-quarter division technique devised by analyzing the regularity of the space-filling curve used in DOT. This greatly reduces the number of space transformation operations. We then propose a novel spatial join algorithm based on this range query processing algorithm. In processing a spatial join, we determine the access order of disk pages so that we can minimize the number of disk accesses. We show the superiority of the proposed method by extensive experiments using data sets of various distributions and sizes. The experimental results reveal that the proposed method improves the performance of spatial join processing up to three times in comparison with the widely-used R-tree-based spatial join method.     

Content-based facial image retrieval using constrained independent component analysis

Content-based image retrieval (CBIR) is a method of searching, browsing, and querying images according to their content. In this paper, we focus on a specific domain of CBIR that involves the development of a content-based facial image retrieval system based on the constrained independent component analysis (cICA). Originating from independent component analysis (ICA), cICA is a source separation technique that uses priori constraints to extract desired independent components (ICs) from data. By providing query images as the constraints to the cICA, the ICs that share similar probabilistic features with the queries from the database can be extracted. Then, these extracted ICs are used to evaluate the rank of each image according to the query. In our approach, we demonstrate that, in addition to a single image-based query, a compound query with multiple query images can be used to search for images with compounding feature content. The experimental results of our CBIR system tested with different facial databases show that our system can improve retrieval performance by using a compound query. Furthermore, our system allows for online processing without the need to learn query images.