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.