On consistency checking of spatial relationships in content-based image database systems. (English) Zbl 1110.68377

Zhang, Qinglong; Chang, Shikuo; Yau, Stephen S.-T.

Commun. Inf. Syst. 5, No. 3, 341-366 (2005).

Summary: We investigate the consistency problem for spatial relationships in content-based image database systems. We use the mathematically simple matrix representation approach to present an efficient (i.e., polynomial-time) algorithm for consistency checking of spatial relationships in an image.
It is shown that, there exists an efficient algorithm to detect whether, given a set SR of absolute spatial relationships, the maximal set of SR under \({\mathcal R}\) contains one pair of contradictory spatial relationships. The time required by it is at most a constant multiple of the time to compute the transitive reduction of a graph or to compute the transitive closure of a graph or to perform Boolean matrix multiplication, and thus is always bounded by time complexity \(O(n^3)\) (and space complexity \(O(n^2))\), where \(n\) is the number of all involved objects. As a corollary, this detection algorithm can completely answer whether a given set of three-dimensional absolute spatial relationships is consistent.

MSC:

68P15	Database theory
94A08	Image processing (compression, reconstruction, etc.) in information and communication theory