Efficient Content-Based and Metadata Retrieval in Image Database

Abstract: Managing image data in a database system using metadata has been practiced since the last two decades. However, describing an image fully and adequately with metadata is practically not possible. The other alternative is describing image content by its low-level features such as color, texture, shape, etc. and using the same for similarity-based image retrieval. However, practice has shown that using only the low-level features can not as well be complete. Hence, systems need to integrate both low-level and metadata descriptions for an efficient image data management. However, due to lack of adequate image data model, absence of a formal algebra for content-based image operations, and lack of precision of the existing image processing and retrieval techniques, no much work is done to integrate the use of low-level and metadata description and retrieval methods. In this paper, we first present a global image data model that supports both metadata and low-level descriptions of images and their salient objects. This allows to make multi-criteria image retrieval (context-, semantic-, and content-based queries). Furthermore, we present an image data repository model that captures all data described in the model and permits to integrate heterogeneous operations in a DBMS. In particular, similarity-based operations (similarity-based join and selection) in combination with traditional ones can be carried out. Finally, we present an image DBMS architecture that we use to develop a prototype in order to support both content-based and metadata retrieval.

Key words: Image Database, Image Data Model, Image Data Repository Model, Multi-criteria Queries, Similarity-Based Operations

Category: H.2.4

1 Introduction

The need for systems that can catalog, stock, and provide efficient retrieval facilities of images of particular interest is becoming very high in different fields such as in medicine, cartography, meteorology, security, visual data communications, etc.

In this respect, a lot of work has been done to integrate image data in the standard data processing environments of different applications [Yoshitaka 99, Rui 99, Grosky 97, Smeulders 98]. Two different approaches used for the representation of images are: the metadata-based and the content-based approaches. The metadata-based representation uses alphanumeric attributes to describe the context and/or the content of an image. This is usually done with human assistance and image retrieval by metadata representation follows the traditional techniques [Sheth 98]. However, such a representation is mostly difficult or not possible to fully or adequately describe an image [Rui 99, Eakins 99, Veltkamp 00]. The other approach for image representation is using the low-level contents of images such as colors, textures, and shapes [Wu 95, Berchtold 97, Veltkamp 00]. The low-level features are derived through feature extraction algorithms. Image retrieval using these features is done by methods of similarity and hence is a non-exact matching. The research efforts exerted in the area of Content-Based Image Retrieval (CBIR), has however made this technique of retrieval promising and an area of high importance [Berchtold 97, Wu 97, Rui 99, Grosky 97, Eakins 99]. For many recent applications, users need selection and join queries that use both content-based and metadata representation of images or salient objects. Hence, the current trend is towards a system that uses both metadata and content-based image retrieval. This need can be demonstrated by the following example.

Consider two image tables SI and EMP, where SI(Photo, F_v¹, Time, Date) is a table created by a surveillance image camera, and EMP(Photo, F_v, Name, Occupation, Address) is an Employee table. For certain investigation scenarios, SI alone can not give complete information. For instance, consider the query: "For pictures of individuals in SI that were taken on September 11, 2001 from 4 to 6 PM, find their most similar images from EMP, with their corresponding name, occupation and address". This query requires a relational selection on the SI table and a "similarity-based join" on SI and EMP tables. Such a "similarity-based join" operation is not much considered in the current systems and prototypes, rather most systems tend to perform only a "similarity-based selection" just for a given query image.

Due to lack of adequate image data model, absence of a formal algebra for content-based image operations, and lack of precision of the existing image processing and retrieval techniques, there is still a lot of work to be done to integrate the use of low-level and metadata description and retrieval methods. In this paper, we first present a global image data model that supports both metadata and low-level descriptions of images and their salient objects. This allows to make multi-criteria image retrieval (context-, semantic-, and content-based queries). Then, we present an image data repository model that captures all the data described in the model and permits to integrate heterogeneous operations in a DBMS. In particular, similarity-based operations (similarity-based join and selection) in combination with traditional ones can be carried out using our model.

2 Related Work

There are two major approaches of image data description and retrieval in the literature: the metadata oriented and the content-based oriented. The metadata-oriented approach has been practiced since the last two decades in different fields of applications such as in medicine, in GIS, on the web, etc. Since subjectivity, ambiguity and imprecision are usually associated with specifying the context and semantic content of images, metadata descriptions are mostly incomplete [Sheth 98]. On the other hand, the work on content-based image analysis, representation and retrieval attracted a large number of researchers for more than a decade. As a result, promising works for a representation and content-based retrieval of image data by the low-level features of color, texture, shape, etc. have been performed [Wu 95, Yoshitaka 99, Rui 99, Grosky 97, Eakins 99]. However, these systems mainly focus on retrieval by the low-level features and give less or no emphasis to the role of metadata-based image retrieval. A useful initiative however is that a number of these systems support the use and identification of salient objects for a more efficient retrieval performance.

To support content-based image retrieval in the standard DBMS, a number of initiatives exist both in the research and commercial environments [Yoshitaka 99, Eakins 99]. DISIMA is an object-oriented system that even considers salient objects of images in the query system [Oria 00]. The common feature of these systems is that, given a query image, they search its most similar images from a list of images using their respective content-based image retrieval engines. The main drawback of these works is not to adequately support a combination of metadata and content-based operations. For instance, operations such as the "similarity-based join" are not supported by the current systems. For an efficient image database management, one needs to consider both approaches. To realize this, a good representation and repository model crucial. The better the features of the image data are represented, the more the image retrieval is able to satisfy complex queries. In the literature, several image data models have been proposed [Grosky 00, Mechkour 95]. However, these models lack an appropriate representation of all the necessary image related data for different applications. The work in [Grosky 00] for example, doesn't consider content and semantic representations of salient object related data and the relationship between salient objects. The works in [Mechkour 95] are restricted because they do not allow the integration of the low-level image features. Hence, a convenient image data model that supports most of the necessary operations on image content is a primary requirement. In this paper, we will address this issue and will consider the implementation architecture that supports both methods of retrieval.

3 Modeling Image Database

For an efficient combination of content-based and metadata retrieval in an image database, we propose here an original image data model able to integrate different types of features. We also present an extension of our repository model proposed to integrate salient objects of images and the most commonly required similarity-based operations.

3.1 An Image Data Model

Our novel image data model considers both the information associated to the image and its salient objects (Figure 1). Hence, it captures the semantic and contextual information of both an image and its salient objects in addition to their physical or low-level features. Furthermore, it considers various relations between salient objects. The model describes an image data in several levels of abstraction. It has two main spaces: the external space that captures the general information associated to the image data that are external to the content of the image, and the content space that describes the content of the image not only using content-based representation, but also using metadata description. The content space consists of physical, spatial and semantic features. The same representation is inherited by the salient object descriptions. The content space maintains different types of relations (directional, topological, and semantic) between the salient objects, and the salient objects and the image. The model proposed here is designed in a manner that considers the visual features description of a still image suggested in MPEG-7 standard.

3.2 The Repository Models

Modeling the image repository is a fundamental requirement for an effective storage, retrieval and a convenient integration of image data into the current popular DBMSs. We therefore present here the image data repository model we presented in [Atnafu 01] and its novel extension in order that it can conveniently support both metadata and content-based operations on images and its salient objects under an Object Relational (OR) paradigm.

3.2.1 The Image Data Repository Model

An image data repository model (or an image table model) M(id, O, F, A, P) is a table of five components where:

3.2.2 Salient object Repository

Considering salient objects for similarity-based image retrieval is a need for the purpose of efficiency and precision in many applications. For a salient object repository, we propose a schema of three components S(ids, Fs, As), where:

Figure 2 shows the content of S and its liaison with M for a medical application. Only the feature vector representations of the salient objects are stored in F_s. The tumor is an object of interest that is extracted from the image.

3.3 Database Schema

Integrating the image data model with the image data repository models, we define the following schematic structure for an image database.

Consider the model M(id, O, F, A, P), we describe the contents of the components F and A of M as:

F(Descriptor, Model, Value):

• Descriptor: is the type of representation (such as Color Histogram, Color distribution, Texture Histogram, etc.),
• Model: is the description format (such as RGB, RHV, etc.),
• Value: is the content descriptor. This component contains both the Physical and Spatial Feature data;

A(ES, Sem_F, R):

• ES: is the External Space descriptions (consisting of Context-Oriented, Domain-Oriented, and Image-Oriented sub-spaces) as indicated in the image data Model,
• Sem_F: is the Semantic Feature of the Content Space of M that tells the significance and interpretation (keywords, legend, etc.) of the image, and
• R: is the component that captures the relations between either two salient objects or a salient object and the image;

Sem_F(Type, Description):

• Type: defines the type of the semantic feature (keyword, scene, etc.),
• Description: is a textual representation.

R(id_s, id, Relation):

• ids: identifies the identifier of a salient object,
• id: is the identifier of either an image or a salient object,
• Relation: represents the spatial (directional, metrical, topological) or semantic relations between them.

For the salient object repository model S(ids, Fs, As), the contents of the components F_s and A_s are described below.

F_s(Descriptor, Model, Value):

• Descriptor: is the type of representation (such as Color Histogram, Color distribution, Texture Histogram, etc.),
• Model: is the description format (such as RGB, RHV, etc.)¸.
• Value: is the content descriptor. This component contains both the Physical and Spatial Feature data;

A_s(Type, Description):

• Type: defines the type of the semantic feature (name, state, etc.),
• Description: is a textual representation.

With this schema, we can support both relational and similarity-based operations. When a query deals with relational operations, it operates on the attributes of component A of M and/or As of S. For a similarity-based operation, the operation is performed on the F component of M and/or on the Fs component of S. Thus, a combination of relational and similarity-based operations can be supported with our schema. The object O of M is mostly required as a resource from which the salient objects and some annotations are extracted and as an image object that can be displayed as a result of retrieval.

4 The Similarity-Based Operators

Two major methods are practiced for content-based image retrieval: the Nearest Neighbor (k-NN) search and the Range query. For the purpose of efficiency and optimization, we adopt the use of range query. The reasons of this choice are discussed in [Atnafu 01]. Below, we give the definition of range query in the way we adopted it for similarity-based operations on image tables.

Range Query:

Let S be a set of images, q be a query image where both are represented by their feature vectors. Let be a positive real distance value. A similarity-based range query of q with respect to S and , denoted by is given as:

where ||o' - q|| denotes the distance between o' and q.

Based on this basic definition, we can then state how we defined the similarity-based selection and similarity-based join operators.

The Similarity-Based Selection Operator:

Given an image query object x, an image table M and > 0, a similarity-based selection operation denoted by is a unary operator on an image table M performed on the component F that is given by:

where (M,x) denotes the range query of object x with respect to M and

The Similarity-Based Join Operator:

Let M₁(id₁,o₁,f₁,a₁,p₁) and M₂(id₂,o₂,f₂,a₂,p₂) be two image tables and let be a positive real number. The similarity-based Join operator, denoted by M₁ M₂, is a binary operator on image tables M₁ and M₂ given by:

where (i.e. the ids contained by the projection on the id component of the associated instances of M₂). Figure 3 shows how the similarity-based join is managed in our approach. Since we are dealing with image data, that is large in size compared to the traditional alphanumeric data, we use a pointer based join when we deal with similarity-based join.

This approach reduces the large amount of memory and storage requirement on the resulting table.

More related operators that are useful for content-based image retrieval in a DBMS are given in [Atnafu 01]. The similarity-based operators defined on M can also be applied on S because we adopt the same structure.

5 An Architecture for Image DBMS

Considering the above image data model, the data repository models, and the database schema, we propose here a general architecture for an image DBMS in an OR paradigm. We show that our proposals work in association with the existing image management systems. To realize this, we extend an existing ORDBMS so that it provides efficient image retrieval by supporting content-based operations on images and their salient objects. The architecture is composed of several components as shown in Figure 4. The Standard Query Processor (SQP) component exists in any of the current DBMS. It involves of the components such as the parser, rewriter, the algebraic rules and protocols, and a query optimizer. To achieve these tasks, the SQP interacts with the Image and Salient Object Processing Routines that provide certain routines as used in many DBMSs such as Oracle 9i to enhance its image management capabilities. The Image Query Processor (IQP) extends the query system with all possible similarity-based image query-processing operations that we proposed. The IQP consists of the novel similarity-based operators, the image processing engines, the content-based query optimizer, the ambiguity resolver, etc. The Data Repository Manager (DRM) is the component that is responsible for storing the image related data in a convenient way in the ORDBMS. The DRM also tracks the association between the image tables with the similarity-based operators.

6 Conclusion

For efficient image data retrieval, a good model that: captures adequate amount of image related data, considers salient objects, and supports a combined use of relational and similarity-based operators are very important in different application domains. However, current systems lack to address all these issues adequately.

In this paper, we addressed these issues and presented a novel image data model that effectively supports both metadata- and content-based image descriptions, and utilizes the same for efficient image retrieval in an image database. Through this model, multi-criteria queries (external, content and semantic-oriented) can be expressed. Furthermore, we introduced an image data repository model that facilitates a systematic storage of image related data in addition to its convenience to express a combination of relational and similarity-based operations. These proposals are made in a way that can be integrated with the current Object Relational DBMS. We presented an architecture to illustrate how our proposals can be implemented. Our proposal can be applied for a wide range of image DBMS applications. To demonstrate the validity of our approach, we have chosen an application in the domain of medicine. A major part of the models is tested by a prototype application called MIMS (Medical Image Management System) that we developed on the basis of the proposed architecture [Chbeir 01]. In MIMS, we use an iconic interface to retrieve image on the basis of several types of features (physical, spatial, semantic, etc.). This part of the proposal is in a promising development stage and includes a detailed study to fully support the similarity-based operations and hence a multi-criteria system of operations. Future works include a proposal of a query optimization model.

References

[Atnafu 01] S. Atnafu, L. Brunie and H. Kosch, Similarity-Based Operators and Query Optimization for Multimedia Database Systems International Database Engineering & Applications Symposium (IDEAS'01), July 16-18, 2001, Grenoble, France; IEEE Computer Society Press, pp. 346-355.

[Berchtold 97] S. Berchtold and C. Boehm and B. Braunmueller and D. A. Keim and H. P. Kriegel, Fast Parallel Similarity Search in Multimedia Databases, SIGMOD Conference, AZ, USA, 1997, pp. 1-12.

[Chbeir 01] R. Chbeir, Y. Amghar, and A. Flory: A Prototype for Medical Image Retrieval, International Journal of Methods of Information in Medicine, Schattauer, Issue 3, 2001.

[Eakins 99] J.P. Eakins and M.E. Graham, Content-Based Image Retrieval: A Report to the JISC Technology Applications Programme, January, 1999, Inst. for Image Data Research, Univ. of Northumbria at Newcastle.

[Grosky 00] W.I. Grosky and Peter L. Stanchev, An Image Data Model, Advances in Visual Information Systems, Visual-2000, 4th International Conference, Lyon, France, 2000, pp. 14-25, LNCS 1929, Springer Verlag.

[Grosky 97] W.I. Grosky, Managing Multimedia Information in Database Systems, Communications of the ACM, 1997, Vol. 40, No. 12, pp. 72-80.

[Mechkour 95] M. Mechkour, "EMIR2: An Extended Model for Image Representation and Retrieval", Database and EXpert system Applications (DEXA), Sep. 1995, P. 395-404.

[Oria 00] V. Oria and M.T. Özsu and P. Iglinski and B. Xu and L.I. Cheng, DISMA: An Object Oriented Approach to Developing an Image Database System, ICDE 2000, February, 2000, 16th Int. Conf. on Data Engineering, San Diego, California.

[Rui 99] Y. Rui, T.S. Huang and S.F. Chang, Image Retrieval: Past, Present, and Future, Journal of Visual Comm. and Image Representation, 1999, Vol.10, pp.1-23.

[Sheth 98] A. Sheth and W. Klas, Multimedia Data Management: Using Metadata to Integrate and Apply Digital Media, McGraw-Hill, 1998, San Francisco.

[Smeulders 98] A.W.M. Smeulders and T. Gevers and M.L. Kersten, Crossing the Divide Between Computer Vision and Databases in Search of Image Databases, Visual Database Systems Conf., Italy, 1998, pp. 223-239.

[Veltkamp 00] R.C. Veltkamp, M. Tanase, Content-Based Image Retrieval Systems: A Survey, October, 2000, Technical Report UU-cs-2000-34, Department of Computer Science, Utrecht University.

[Wu 95] J.K. Wu and A.D. Narasimhalu and B.M. Mehtre and C.P. Lam and Y.J. Gao, CORE: A Content-Based Retrieval Engine for Multimedia Information Systems, Multimedia Systems, 1995, Vol. 3, pp. 25-41.

[Wu 97] Jian-Kang Wu, Content-Based Indexing of Multimedia Databases, IEEE TKDE, 1997, Vol. 9, No. 6, pp.978-989.

[Yoshitaka 99] A. Yoshitaka and T. Ichikawa, A Survey on Content-Based Retrieval for Multimedia Databases, IEEE Transactions on Knowledge and Data Engineering, Vol. 11, No. 1, 1999, pp.81-93.