Communications in Information and Systems

Volume 4 (2004)

Number 3

On Completeness of Reasoning about Planar Spatial Relationships in Pictorial Retrieval Systems

Pages: 211 – 234



Stephen S.-T. Yau

Qing-Long Zhang


In this paper we consider the completeness problem of reasoning about planar spatial relationships in pictorial retrieval systems. We define a large class of two-dimensional scenes, the extended pseudo-symbolic pictures. The existing rule system R is proved to be complete for (extended) pseudo-symbolic pictures. We also introduce a new iconic indexing, the (extended) pseudo- 2D string representation, for them. The (extended) pseudo-2D string has the good properties of the 2D string. It is unambiguous, like the augmented 2D string, and has a compact form suitable for image retrieval. We then present efficient algorithms to determine whether a given planar picture is (extended) pseudo-symbolic or not, and if it is, these algorithms also return its (extended) pseudo-2D string representation. Picture retrieval by (extended) pseudo-2D strings is also discussed.

Published 1 January 2004