A remark on NP-completeness of picture matching (Q1183400)

One of the most relevant features in the design of advanced image data- base systems is the retrieval of pictures using the spatial relations among the objects contained in the pictures to be retrieved \textit{N. S. Chang} and {K. S. Fu} [Query-by-pictorial-example, IEEE Trans. Software Eng. 6, 519-524 (1980)], \textit{S. -K. Chang} and \textit{S. -H. Liu} [IEEE Trans. Pattern Anal. and Mach. Intell. 6, No. 4, 475-484 (1984; Zbl 0542.68077)]. Corresponding to different levels of strictness in checking for spatial constraints, three types of picture matching are defined in \textit{S. -K. Chang} and \textit{S. -H. Liu} [loc. cit]. We prove the NP-completeness of the two less strict types of matching.