On consistency checking of spatial relationships in content-based image database systems
Shi‐Kuo Chang, Stephen S.‐T. Yau, Qinglong Zhang · Communications in Information and Systems · 2005
In this paper 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 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.