Handling Multiple Instances of Symbols in Pictorial Queries by Image Similarity

A method is presented for processing pictorial query specifications that consist of a query image and a similarity level that must hold between the query image and database images. The similarity level specifies the contextual similarity (how well does the content of one image match that of another) as well as the spatial similarity (the relative locations of the matching symbols in the two images). This method allows more than one instance of each object in the database image (while still requiring only one instance of each object in the query image). The algorithm tries to satisfy the contextual similarity first and then tries to satisfy the spatial constraints using an auxiliary graph data structure. The running time of this method is exponential in the number of objects in the query image.