Communications in Information and Systems

Volume 4 (2004)

Number 2

On Interactability of Spatial Relationships in Content-Based Image Database Systems

Pages: 181 – 190



Stephen S.-T. Yau

Qing-Long Zang


An image stored in image database systems is assumed to be associated with some content-based meta-data about that image, that is, information about objects in the image and absolute/relative spatial relationships among them. An image query for such an image database system can generally be handled in two ways: exact picture matching and approximate picture matching. In this paper we show the intractability of matching of spatial relationships between a query image and an image stored in the database. In particular, our results suggest that one would not expect to have polynomial-time algorithms for finding the exact picture-matching and computing the maximal similarity between a query picture and a database picture, unless P = NP.

Full Text (PDF format)