In specifying spatial properties of the individual regions in the query, we provide for indexing of region centroids and minimum bounding rectangles.
Figure 7: Region spatial distance (a) fixed spatial distance 
, (b) bounded spatial distance 
, where 
determines the valid spatial bounds.
The spatial distance between regions is given by the euclidean distance of centroids as illustrated in Figure 7(a).
We also give the user flexibility in designating the spatial bounds for each region in the query within which a target region is assigned a spatial distance of zero. When a target region falls outside of the spatial bounds the spatial distance is given by the euclidean distance as illustrated in Figure 7(b). This is useful in many situations when the user does not care about the exact position of matched regions as long as they fall within a designated area.
Figure 8: (a) spatial quad-tree indexes region centroids, (b) r-tree indexes region MBRs (rectangles).
The centroids of the image regions are indexed using a spatial quad-tree on their x and y values as illustrated in Figure 8(a). The quad-tree provides quick access to 2-D data points [7]. A query for region at location 
is processed by first traversing the spatial quad-tree to the containing node, then exhaustively searching the block for the points that minimize . In the case that the user specifies a bounded spatial query, a range of blocks are evaluated such that points within the spatial bounds are all assigned 
.
Since the spatial locations of extracted image regions are not sufficiently represented by centroid locations alone, we also index the region spatial locations by their minimum bounding rectangles (MBRs). The MBR is the smallest vertically aligned rectangle that completely encloses the region. For example, Figure 1(c) illustrates the MBRs for some image regions. In this way, a spatial query may specify a search rectangle and the target regions are found that overlap with it spatially. The MBRs of the regions are indexed using an r-tree as illustrated in Figure 8(b). The r-tree provides a dynamic structure for indexing k-D rectangles [17], here k=2. The r-tree, which consists of a hierarchy of overlapping spatial nodes, is designed to visit only a small number of nodes in a spatial search.
