Image Database Indexing Techniques

Image Database Indexing Techniques

Michael Vassilakopoulos (University of Central Greece, Greece), Antonio Corral (University of Almería, Spain), Boris Rachev (Technical University of Varna, Bulgaria), Irena Valova (University of Rousse, Bulgaria) and Mariana Stoeva (Technical University of Varna, Bulgaria)
Copyright: © 2009 |Pages: 8
DOI: 10.4018/978-1-59140-995-3.ch003
OnDemand PDF Download:
$37.50

Abstract

Image Databases (IDBs) are a kind of Spatial Databases where a large number of images are stored and queried. In this chapter, techniques for indexing an IDB for efficiently processing several kinds of queries, like retrieval based on features, content, structure, processing of joins, and queries by example are reviewed. The main indexing techniques used in IDBs are either members of the R-tree family (data driven structures), or members of the quadtree family (space driven structures). Although, research on IDB indexing counts several years, there are still significant research challenges, which are also discussed in this chapter. IDBs and their indexing structures bring together two different disciplines (databases and image processing) and interdisciplinary research efforts are required. Moreover, dealing with the semantic gap (successful integrated retrieval based on low-level features and high-level semantic features) and querying between images and other kinds of spatial data are also significant future research directions.
Chapter Preview
Top

Introduction

Image Databases (IDBs) are a special kind of Spatial Databases where a large number of images are stored and queried. IDBs have a plethora of applications in modern life, for example in medical, multimedia, and educational applications. In the framework of Geographical Information Systems (GIS), digital images (raster data) may represent changes in cultivations, sunny areas, and the discrimination between urban environments and country sides.

Apart from the raster format, GIS data may be stored in vector format (points, line segments, polygons, etc.). Each of these data formats has certain advantages making a choice between them a challenge. Raster data leads to faster computing for several operations (e.g., overlays) and are well suited for remote sensing. On the other hand, they have a fixed resolution leading to limited detail. In this article, we focus on raster data (image databases) and their indexing techniques.

Since the start of the 1980s several structures for spatial objects have been proposed in the literature for efficient storage and retrieval of image collections. Based on these methods, many kinds of useful queries on image data may be processed efficiently. These include:

  • Queries about the content of additional properties (descriptive information) that have been embedded for each image (e.g., which images have been used in the book cover of children’s books?).

  • Queries about the characteristics/features of the images like color, texture, shape etc. (e.g., find the images that depict vivid blue sky.).

  • Queries for retrieving images with specified content (e.g., find the images that contain the sub-image of a specified chair.).

  • Queries by example or sketch (e.g., a sample image is chosen, or drawn by the user and images similar to this sample are sought.).

  • Structural queries (e.g., find the images that contain a number of specific objects in a specified arrangement.).

  • Image Joins (e.g., find the cultivation areas that reside in polluted atmosphere areas.).

  • Queries that combine regional data and other sorts of spatial data (e.g., find the cities represented by point data that reside within 5km from cotton cultivations.).

  • Temporal Queries on sequences of evolving images (e.g., find if there has been an increase in the regions of wheat cultivations in this prefecture during the last two years.).

The importance of image indexing and querying techniques led major Database Management Systems’ manufacturers to embed related extensions to the core engine of their products, (e.g., DB2 has embedded QBIC technology) (Flickner et al. 1995) and Oracle provides Content-Based Image Retrieval (CBIR) based on Virage (Annamalai et al. 2000).

Top

Background

A digital image is a representation of a two-dimensional image as a finite set of digital values, called picture elements or pixels. In a binary image, each pixel can be either black, or white, while in a greyscale (color) image each pixel corresponds to a shade of gray (to a color), among a set of permitted greyscale (color) values.

Each image represents a scene containing objects and regions. An IDB is an organized collection of digital images aiming at the management and the efficient processing of queries on this image collection. There are numerous publications in the literature related to the processing of queries on image features like color (e.g., distribution of colors, dominant colors, and color moments), texture (the pattern of the image surface change, usually expressed by a combination of characteristics like coarseness, contrast, directionality, uniformity, regularity, density, frequency, etc.) and shape (the physical structure of objects, or the geometric shapes present in the image). In several of these publications (emerging from the image processing/computer vision community) the term indexing refers to the features corresponding to each image and to the algorithm used for computing the similarity between them (the algorithm often works by an exhaustive comparison with all the images present in the databases). In this article, indexing is used in the context of databases and corresponds to the access methods (data structures) used to speed up query processing.

Key Terms in this Chapter

Color Features of an Image: Characteristics of an image related to the presence of color information, like distribution of colors, dominant colors, or color moments.

Access Method or Index Structure: A technique of organizing data that allows the efficient retrieval of data according to a set of search criteria.

Structural Features of an Image: The arrangement of the objects depicted in the image.

Content-Based Image Retrieval: Searching for images in image databases according to their visual contents, like searching for images with specific color, texture, or shape properties, for images containing specific objects, or containing objects in a specified arrangement.

Semantic Features of an Image: The contents of an image according to human perception, like the objects present in the image or the concepts / situations related to the image.

Texture Features of an Image: The pattern(s) of the image’s surface change, usually expressed by a combination of characteristics like coarseness, contrast, directionality, uniformity, regularity, density, and frequency.

Query processing: Extracting information from a large amount of data without actually changing the underlying database where the data are organized.

Image Database: An organized collection of digital images aimed at the efficient management and the processing of queries on this image collection

Similarity of Images: The degree of likeness between images according to a number of features, like color texture, shape, and semantic features.

Shape Features of an Image: The physical structure(s) of the objects, or the geometric shapes present in the image.

Complete Chapter List

Search this Book:
Reset
Editorial Advisory Board
Table of Contents
Chapter 1
Jose E. Córcoles, Pascual González
An interesting feature of GML is to consider it as a database, but only in the strictest sense of the term. That is, as a collection of data. As a... Sample PDF
GML as Database: Present and Future
$37.50
Chapter 2
Jose E. Córcoles, Pascual González
As a database format, XML (GML by extension) can be queried. In order to do this, we need a query language (of general use) to retrieve information... Sample PDF
Querying GML: A Pressing Need
$37.50
Chapter 3
Michael Vassilakopoulos, Antonio Corral, Boris Rachev, Irena Valova, Mariana Stoeva
Image Databases (IDBs) are a kind of Spatial Databases where a large number of images are stored and queried. In this chapter, techniques for... Sample PDF
Image Database Indexing Techniques
$37.50
Chapter 4
Patrik Skogster
Geographic information is created by manipulating geographic (or spatial) data (generally known by the abbreviation geodata) in a computerized... Sample PDF
Different Roles and Definitions of Spatial Data Fusion
$37.50
Chapter 5
Carlos Granell, Michael Gould, Miguel Ángel Manso, Miguel Ángel Bernabé
Geographic Information Systems (GIS) are data-centric applications that rely on the input and constant maintenance of large quantities of basic and... Sample PDF
Spatial Data Infrastructures
$37.50
Chapter 6
Trias Aditya, Menno-Jan Kraak
The vision of “created once, used many times” has been spread out across the globe through the development of geospatial data infrastructure (GDI)... Sample PDF
Geoportals and the GDI Accessibility
$37.50
Chapter 7
Hervé Gontran
The development of road database requires the management of continuously growing road databases. Mobile mapping systems can acquire this... Sample PDF
Real-Time Extraction of the Road Geometry
$37.50
Chapter 8
Cognitive Maps  (pages 58-64)
Stephen Hirtle
Cognitive maps are the representations that individuals use to understand, process, and navigate environments. The term cognitive map should not be... Sample PDF
Cognitive Maps
$37.50
Chapter 9
Map Overlay Problem  (pages 65-72)
Maikel Garma de la Osa, Yissell Arias Sánchez
Maps usually contain data from different sources (e.g., population, natural resources, cities, roads, infant mortality rate, etc.) When all the... Sample PDF
Map Overlay Problem
$37.50
Chapter 10
Mahbubur R. Meenar, John A. Sorrentino
Three-dimensional surface modeling has become an important element in the processing and visualization of geographic information. Models are created... Sample PDF
Dealing with 3D Surface Models: Raster and TIN
$37.50
Chapter 11
Yurai Núñez-Rodríguez
Web map services, such as Google Maps and MapQuest, are among the most popular sites on the Internet. One can easily access these services through a... Sample PDF
Web Map Servers Data Formats
$37.50
Chapter 12
Eric Delmelle, Raymond Dezzani
There has been a dramatic increase in the handling of geospatial information, and also in the production of maps. However, because the Earth is... Sample PDF
Overview, Classification and Selection of Map Projections for Geospatial Applications
$37.50
Chapter 13
José Poveda, Michael Gould
In this chapter we present some well-known algorithms for the solution of the point location problem and for the more particular problem of... Sample PDF
About the Point Location Problem
$37.50
Chapter 14
Alina Lazar, Bradley A. Shellito
Support Vector Machines (SVM) are powerful tools for classification of data. This article describes the functionality of SVM including their design... Sample PDF
Classification in GIS Using Support Vector Machines
$37.50
Chapter 15
Network Modeling  (pages 113-121)
Kevin M. Curtin
Network models are some of the earliest and most consistently important data models in GISystems. Network modeling has a strong theoretical basis in... Sample PDF
Network Modeling
$37.50
Chapter 16
Xiaojun Yang
Artificial neural networks are increasingly being used to model complex, nonlinear phenomena. The purpose of this chapter is to review the... Sample PDF
Artificial Neural Networks
$37.50
Chapter 17
Spatial Interpolation  (pages 129-136)
Xiaojun Yang
Spatial interpolation is a core component of data processing and analysis in geoinformatics. The purpose of this chapter is to discuss the concept... Sample PDF
Spatial Interpolation
$37.50
Chapter 18
Bo Huang, Magesh Chandramouli
Integrating spatial and temporal dimensions is a fundamental yet challenging issue in modeling geospatial data. This article presents the design of... Sample PDF
Spatio-Temporal Object Modeling
$37.50
Chapter 19
May Yuan
Temporal Geographic Information Systems (GIS) technology has been a top research subject since late the 1980s. Langran’s Time in Geographic... Sample PDF
Challenges and Critical Issues for Temporal GIS Research and Technologies
$37.50
Chapter 20
Iftikhar U. Sikder
The representation of geographic entities is characterized by inherent granularity due to scale and resolution specific observations. This article... Sample PDF
Rough Sets and Granular Computing in Geospatial Information
$37.50
Chapter 21
Matthew Perry, Amit Sheth, Ismailcem Budak Arpinar, Farshad Hakimpour
The amount of digital data available to researchers and knowledge workers has grown tremendously in recent years. This is especially true in the... Sample PDF
Geospatial and Temporal Semantic Analytics
$37.50
Chapter 22
Yuqi Bai, Liping Di, Aijun Chen, Yang Liu, Yaxing Wei
Three public geospatial image catalog services, FGDC Clearinghouse, NASA ECHO and GMU CSISS CSW, were reviewed, considering the following aspects... Sample PDF
Geospatial Image Metadata Catalog Services
$37.50
Chapter 23
Peisheng Zhao, Liping Di, Wenli Yang, Genong Yu, Peng Yue
The Semantic Web technology provides a common interoperable framework in which information is given a well-defined meaning such that data and... Sample PDF
Geospatial Semantic Web: Critical Issues
$37.50
Chapter 24
Carlos Granell, Michael Gould, Miguel Ángel Esbrí
In the context of Geographic Information System’s evolution from monolithic systems to personal desktop GIS and then to collections of remote... Sample PDF
Geospatial Web Service Chaining
$37.50
Chapter 25
Genong Yu, Liping Di, Wenli Yang, Peisheng Zhao, Peng Yue
Multi-agent system is specialized in studying the collective effects of multiple intelligent agents. An intelligent agent is a computer system with... Sample PDF
Multi-Agent Systems for Distributed Geospatial Modeling, Simulation and Computing
$37.50
Chapter 26
Peng Yue, Liping Di, Wenli Yang, Genong Yu, Peisheng Zhao
In a service-oriented environment, an individual geospatial Web service is not sufficient to solve a complex real-world geospatial problem. Service... Sample PDF
Towards Automatic Composition of Geospatial Web Services
$37.50
Chapter 27
Aijun Chen, Liping Di, Yuqi Bai, Yaxing Wei
The definition of the Grid computing and its application to geoinformatics are introduced. Not only the comparison of power Grid and computing Grid... Sample PDF
Grid Computing and its Application to Geoinformatics
$37.50
Chapter 28
Yaxing Wei, Liping Di, Guangxuan Liao, Baohua Zhao, Aijun Chen, Yuqi Bai
With the rapid accumulation of geospatial data and the advancement of geoscience, there is a critical requirement for an infrastructure that can... Sample PDF
Sharing of Distributed Geospatial Data through Grid Technology
$37.50
Chapter 29
Alexander Klippel, Kai-Florian Richter, Stefan Hansen
This contribution provides an overview of elements of cognitively ergonomic route directions. Cognitive ergonomics, in general, seeks to identify... Sample PDF
Cognitively Ergonomic Route Directions
$37.50
Chapter 30
Péter Hegedüs, Mihály Orosz, Gábor Hosszú, Ferenc Kovács
This chapter details the potential found in combining to different technologies. The two basically different technologies, LBSs in mobile... Sample PDF
Multicast Over Location-Based Services
$37.50
Chapter 31
Routing  (pages 246-253)
Kevin M. Curtin
Routing is the act of selecting a course of travel. Routing problems are one of the most prominent and persistent problems in geoinformatics. This... Sample PDF
Routing
$37.50
Chapter 32
Location Privacy  (pages 254-259)
Matt Duckham
In this chapter, the author raises a number of issues surrounding the ever-growing capabilities of geoinformatics. Location privacy can be defined... Sample PDF
Location Privacy
$37.50
Chapter 33
Vladimir I. Zadorozhny
The author of this chapter considers the location-based approach for performance tuning that significantly facilitates the challenge of utilizing... Sample PDF
Location-Based Performance Tuning in Mobile Sensor Networks
$37.50
Chapter 34
Henrik Hanke, Alf Neumann
The provisioning of Location-Based Services (LBS) follows the chain of determination of a position, mapping this information onto a natural... Sample PDF
Location-Based Services: A Taxonomy on Theory and Practice
$37.50
Chapter 35
Coupling GPS and GIS  (pages 277-284)
Mahbubur R. Meenar, John A. Sorrentino, Sharmin Yesmin
Since the 1990s, the integration of GPS and GIS has become more and more popular and an industry standard in the GIS community worldwide. The... Sample PDF
Coupling GPS and GIS
$37.50
Chapter 36
Wei-Shinn Ku, Haojun Wang, Roger Zimmermann
With the availability and accuracy of satellite-based positioning systems and the growing computational power of mobile devices, recent research and... Sample PDF
Modern Navigation Systems and Related Spatial Query
$37.50
Chapter 37
Muhammad Usman Iqbal, Samsung Lim
Over the past few decades, the technologies of mobile communication, positioning, and computing have gradually converged. The automobile has been a... Sample PDF
Location Privacy in Automotive Telematics
$37.50
Chapter 38
Mohammed A. Quddus
Map matching algorithms integrate positioning data with spatial road network data to support the navigation modules of intelligent transport systems... Sample PDF
Map Matching Algorithms for Intelligent Transport Systems
$37.50
Chapter 39
Andrés Pazos, José Poveda, Michael Gould
In this chapter we present a package-based component architecture for the specific deployment and maintenance of public sector applications... Sample PDF
A Package-Based Architecture for Customized GIS
$37.50
Chapter 40
Magesh Chandramouli, Bo Huang
This article explores the application of virtual environments to 3D geospatial visualization and exploration. VR worlds provide powerful... Sample PDF
Virtual Environments for Geospatial Applications
$37.50
Chapter 41
Iftikhar U. Sikder
Geospatial predictive models often require mapping of predefined concepts or categories with various conditioning factors in a given space. This... Sample PDF
Managing Uncertainty in Geospatial Predictive Models
$37.50
Chapter 42
Arianna D’Ulizia, Fernando Ferri, Patrizia Grifoni
The main issues of spatial databases and Geographic Information System (GIS), concern the representation, the management and the manipulation of a... Sample PDF
Geographic Visual Query Languages and Ambiguities Treatment
$37.50
Chapter 43
Lionel Savary, Georges Gardarin, Karine Zeitouni
GML is a promising model for integrating geodata within data warehouses. The resulting databases are generally large and require spatial operators... Sample PDF
GeoCache: A Cache for GML Geographical Data
$37.50
Chapter 44
Lyn Kathlene
This chapter describes and analyzes the effectiveness of two methodological techniques, cognitive mapping and geographical information systems... Sample PDF
Cognitive Mapping and GIS for Community-Based Resource Identification
$37.50
Chapter 45
Edward Mac Gillavry
The collection and dissemination of geographic information has long been the prerogative of national mapping agencies. Nowadays, location-aware... Sample PDF
Collaborative Mapping and GIS: An Alternative Geographic Information Framework
$37.50
Chapter 46
Iftikhar U. Sikder, Santosh K. Misra
This article proposes a multi-agent based framework that allows multiple data sources and models to be semantically integrated for spatial modeling... Sample PDF
Semantic Interoperability of Geospatial Services
$37.50
Chapter 47
George Kakaletris, Dimitris Varoutas, Dimitris Katsianis, Thomas Sphicopoulos
Broadband communication networks have begun to spread rapidly over fixed networks, with wireless networks following at close distance. The excess... Sample PDF
Biometric Authentication in Broadband Networks for Location-Based Services
$37.50
Chapter 48
Stelios C.A. Thomopoulos, Nikolaos Argyreas
The globally observed recession of mobile services market has pushed mobile network operators into looking for opportunities to provide value added... Sample PDF
Design and Implementation Approaches for Location-Based, Tourism-Related Services
$37.50
About the Contributors