A significant aspect of discriminating among images depends on the sizes, spatial locations and relationships of objects or regions. However, introducing multiple image regions and spatial information into the query process greatly complicates the content-based image query approaches. This results from the combinatorial explosion in exhaustively comparing multiple regions or objects.
On the other hand, by representing images symbolically, spatial query methods utilize the locations and spatial relationships of symbols. For example, comparisons based upon 2-D strings [6], spatial quad-trees [7] and graphs [8] provide for flexible and efficient spatial querying. However, these approaches cannot easily accommodate measures of similarity of the ``symbols'' such as those based upon visual features of objects or regions. The problem has only recently been addressed in limited applications, for maps in [9] and for medical images that contain both labeled and unlabeled regions [4].
Figure 1: Image decomposition (a) query image, 
, (b) example target image, (c) target image decomposed into regions that have both feature and spatial properties, 
.