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.     

A knowledge-based approach for retrieving images by content

A knowledge based approach is introduced for retrieving images by content. It supports the answering of conceptual image queries involving similar-to predicates, spatial semantic operators, and references to conceptual terms. Interested objects in the images are represented by contours segmented from images. Image content such as shapes and spatial relationships are derived from object contours according to domain specific image knowledge. A three layered model is proposed for integrating image representations, extracted image features, and image semantics. With such a model, images can be retrieved based on the features and content specified in the queries. The knowledge based query processing is based on a query relaxation technique. The image features are classified by an automatic clustering algorithm and represented by Type Abstraction Hierarchies (TAHs) for knowledge based query processing. Since the features selected for TAH generation are based on context and user profile, and the TAHs can be generated automatically by a clustering algorithm from the feature database, our proposed image retrieval approach is scalable and context sensitive. The performance of the proposed knowledge based query processing is also discussed     

SEE: a Spatial Exploration Environment based on adirect-manipulation paradigm

The need to provide effective tools for analyzing and querying spatial data is becoming increasingly important with the explosion of data in applications such as geographic information systems, image databases, CAD, and remote sensing. The SEE (Spatial Exploration Environment) is the first effort at applying direct-manipulation visual information seeking (VIS) techniques to spatial data analysis by visually querying as well as browsing spatial data and reviewing the visual results for trend analysis. The SEE system incorporates a visual query language (SVIQUEL) that allows users to specify the relative spatial position (both topology and direction) between objects using direct manipulation. The quantitative SVIQVEL sliders (S-sliders) are complemented by the qualitative active-picture-for-querying (APIQ) interface that allows the user to specify qualitative relative position queries. APIQ provides qualitative visual representations of the quantitative query specified by the S-sliders. This increases the utility of the system for spatial browsing and spatial trend discovery with no particular query in mind. The SVIQUEL queries are processed using a k-Bucket index structure specifically tuned for incremental processing of the multidimensional range queries that represent the class of queries that can be expressed by SVIQUEL. We have also designed a tightly integrated map visualization that helps to preserve the spatial context and a bar visualization that provides a qualitative abstraction of aggregates     

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     

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     

Filtering Data Streams for Entity-Based Continuous Queries

The idea of allowing query users to relax their correctness requirements in order to improve performance of a data stream management system (e.g., location-based services and sensor networks) has been recently studied. By exploiting the maximum error (or tolerance) allowed in query answers, algorithms for reducing the use of system resources have been developed. In most of these works, however, query tolerance is expressed as a numerical value, which may be difficult to specify. We observe that in many situations, users may not be concerned with the actual value of an answer, but rather which object satisfies a query (e.g., "who is my nearest neighbor?”). In particular, an entity-based query returns only the names of objects that satisfy the query. For these queries, it is possible to specify a tolerance that is "nonvalue-based.” In this paper, we study fraction-based tolerance, a type of nonvalue-based tolerance, where a user specifies the maximum fractions of a query answer that can be false positives and false negatives. We develop fraction-based tolerance for two major classes of entity-based queries: 1) nonrank-based query (e.g., range queries) and 2) rank-based query (e.g., k-nearest-neighbor queries). These definitions provide users with an alternative to specify the maximum tolerance allowed in their answers. We further investigate how these definitions can be exploited in a distributed stream environment. We design adaptive filter algorithms that allow updates be dropped conditionally at the data stream sources without affecting the overall query correctness. Extensive experimental results show that our protocols reduce the use of network and energy resources significantly.     

Visual image retrieval by elastic matching of user sketches

Effective image retrieval by content from database requires that visual image properties are used instead of textual labels to properly index and recover pictorial data. Retrieval by shape similarity, given a user-sketched template is particularly challenging, owing to the difficulty to derive a similarity measure that closely conforms to the common perception of similarity by humans. In this paper, we present a technique which is based on elastic matching of sketched templates over the shapes in the images to evaluate similarity ranks. The degree of matching achieved and the elastic deformation energy spent by the sketch to achieve such a match are used to derive a measure of similarity between the sketch and the images in the database and to rank images to be displayed. The elastic matching is integrated with arrangements to provide scale invariance and take into account spatial relationships between objects in multi-object queries. Examples from a prototype system are expounded with considerations about the effectiveness of the approach and comparative performance analysis     

Spatial inverse query processing

Traditional spatial queries return, for a given query object q, all database objects that satisfy a given predicate, such as epsilon range and k-nearest neighbors. This paper defines and studies inverse spatial queries, which, given a subset of database objects Q and a query predicate, return all objects which, if used as query objects with the predicate, contain Q in their result. We first show a straightforward solution for answering inverse spatial queries for any query predicate. Then, we propose a filter-and-refinement framework that can be used to improve efficiency. We show how to apply this framework on a variety of inverse queries, using appropriate space pruning strategies. In particular, we propose solutions for inverse epsilon range queries, inverse k-nearest neighbor queries, and inverse skyline queries. Furthermore, we show how to relax the definition of inverse queries in order to ensure non-empty result sets. Our experiments show that our framework is significantly more efficient than naive approaches.     

Evaluating refined queries in top-k retrieval systems

In many applications, users specify target values for certain attributes/features without requiring exact matches to these values in return. Instead, the result is typically a ranked list of "top k" objects that best match the specified feature values. User subjectivity is an important aspect of such queries, i.e., which objects are relevant to the user and which are not depends on the perception of the user. Due to the subjective nature of top-k queries, the answers returned by the system to an user query often do not satisfy the users need right away, either because the weights and the distance functions associated with the features do not accurately capture the users perception or because the specified target values do not fully capture her information need or both. In such cases, the user would like to refine the query and resubmit it in order to get back a better set of answers. While there has been a lot of research on query refinement models, there is no work that we are aware of on supporting refinement of top-k queries efficiently in a database system. Done naively, each "refined" query can be treated as a "starting" query and evaluated from scratch. We explore alternative approaches that significantly improve the cost of evaluating refined queries by exploiting the observation that the refined queries are not modified drastically from one iteration to another. Our experiments over a real-life multimedia data set show that the proposed techniques save more than 80 percent of the execution cost of refined queries over the naive approach and is more than an order of magnitude faster than a simple sequential scan.     

A theory of translation from relational queries to hierarchicalqueries

In a heterogeneous database system, a query for one type of database system (i.e., a source query) may have to be translated to an equivalent query (or queries) for execution in a different type of database system (i.e., a target query). Usually, for a given source query, there is more than one possible target query translation. Some of them can be executed more efficiently than others by the receiving database system. Developing a translation procedure for each type of database system is time-consuming and expensive. We abstract a generic hierarchical database system (GHDBS) which has properties common to database systems whose schema contains hierarchical structures (e.g., System 2000, IMS, and some object-oriented database systems). We develop principles of query translation with GHDBS as the receiving database system. Translation into any specific system can be accomplished by a translation into the general system with refinements to reflect the characteristics of the specific system. We develop rules that guarantee correctness of the target queries, where correctness means that the target query is equivalent to the source query. We also provide rules that can guarantee a minimum number of target queries in cases when one source query needs to be translated to multiple target queries. Since the minimum number of target queries implies the minimum number of times the underlying system is invoked, efficiency is taken into consideration     

A fully spatial personalized differentially private mechanism to provide non-uniform privacy guarantees for spatial databases

Spatial databases are essential to applications in a wide variety of domains. One of the main privacy concerns when answering statistical queries, such as range counting queries, over a spatial database is that an adversary observing changes in query answers may be able to determine whether or not a particular geometric object is present in the database. Differential privacy addresses this concern by guaranteeing that the presence or absence of a geometric object has little effect on query answers. Most of the current differentially private mechanisms for spatial databases ignore the fact that privacy is personal and, thus, provide the same privacy protection for all geometric objects. However, some particular geometric objects may be more sensitive to privacy issues than others, requiring stronger differential privacy guarantees. In this paper, we introduce the concept of spatial personalized differential privacy for spatial databases where different geometric objects have different privacy protection requirements. Also, we present SPDP-PCE, a novel spatial personalized differentially private mechanism to answer range counting queries over spatial databases that fully considers the privacy protection requirements of geometric objects in the underlying geometric space in both steps of noise addition and consistency enforcement. Our experimental results on real datasets demonstrate the effectiveness of SPDP-PCE under various total privacy budgets, query shapes, and privacy level distributions.     

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.     

Filter Image Browsing: Interactive Image Retrieval by Using Database Overviews

Human-computer interaction is a decisive factor in effective content-based access to large image repositories. In current image retrieval systems the user refines his query by selecting example images from a relevance ranking. Since the top ranked images are all similar, user feedback often results in rearrangement of the presented images only.For better incorporation of user interaction in the retrieval process, we have developed the Filter Image Browsing method. It also uses feedback through image selection. However, it is based on differences between images rather than similarities. Filter Image Browsing presents overviews of relevant parts of the database to users. Through interaction users then zoom in on parts of the image collection. By repeatedly limiting the information space, the user quickly ends up with a small amount of relevant images. The method can easily be extended for the retrieval of multimedia objects.For evaluation of the Filter Image Browsing retrieval concept, a user simulation is applied to a pictorial database containing 10,000 images acquired from the World Wide Web by a search robot. The simulation incorporates uncertainty in the definition of the information need by users. Results show Filter Image Browsing outperforms plain interactive similarity ranking in required effort from the user. Also, the method produces predictable results for retrieval sessions, so that the user quickly knows if a successful session is possible at all. Furthermore, the simulations show the overview techniques are suited for applications such as hand-held devices where screen space is limited.     

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

No IFs,ANDs, or ORs: A study of database querying

The difficulty of expressing database queries was examined as a function of the language used. Two distinctly different query methods were investigated. One used a standard database query language, SQL, requiring users to express an English query using a formal syntax and appropriate combinations of boolean operators. The second used a newly designed Truth-table Exemplar-Based Interface (TEBI), which only required subjects to be able to choose examplars from a system-generated table representing a sample database. Through users' choices of critical exemplars, the system could distinguish between interpretations of an otherwise ambiguous English query. Performance was measured by number correct, time to complete queries, and confidence in query correctness. Individual difference analyses were done to examine the relationship between subjects' characteristics and ability to express database queries. Subjects' performance was observed to be both better, and more resistant to variability in age and levels of cognitive skills, when using TEBI than when using SQL to specify queries. Possible reasons for these differences are discussed.     

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.     

Visual interaction using an iconic system

IBS (Icon Based System) is an experimental graphical query language based on icons. It demonstrates the capabilities of a workstation environment by integrating the aspects of database programming in one graphical setting. Namely, it allows direct manipulation of objects dealing with pictorial data as well as alphanumeric data. We point out the interaction techniques between users and database systems. Then we describe the design of IBS, illustrate its features, and show how queries are formulated in a medical context.