next up previous
Next: SUMMARY AND FUTURE WORK Up: VisualSEEk: a fully automated Previous: Multiple Regions Query Strategy

QUERY EVALUATION

 

We now present some example color/spatial queries and provide some initial evaluations.

Query Formulation

The joint color/spatial queries are formulated graphically by using the VisualSEEk user tools as illustrated in Figure 13. The user sketches regions, positions them on the query grid and assigns them properties of color, size and absolute location. The user may also assign boundaries for location and size.

  figure762
Figure 13:   VisualSEEk user interface

Unconstrained Image Queries

We illustrate the power and flexibility of the VisualSEEk query system over non-spatial techniques in Figure 14. In Figure 14(a) (top left), a VisualSEEk query is diagrammed that specifies two regions (outer is orange and inner is yellow) and their spatial layout with the goal of retrieving images of sunsets. The best matches to the color/spatial query (left) have a similar arrangement of similarly colored regions. In Figure 14(b), a typical sunset image is used (top right), and the best matches (right) are found that have the most similar color histograms to the query image. We see that the global color histogram query process gives the user little control in specifying the query and more readily returns images that are not desired.

  figure770
Figure 14:   Sample ``sunset'' queries (a) VisualSEEk query using diagrammed query at top left, (b) color histogram query using query image at top right. Best matches are listed from top to bottom.

In Figure 15(a) (top left), a VisualSEEk query is diagrammed that specifies three regions (from top to bottom: light blue, tan and green) and their spatial layout. The best matches to the query have a similar arrangement of the three colored regions. In Figure 15(b), the first VisualSEEk image match is used (top right = second left). The best matches are found that have the most similar color histograms to the query image. We see that the color histogram matches have little similarity to the regions in the query image. We note that for the color/spatial queries in Figure 14(a) and Figure 15(a), the query response time is approximately 1-2 seconds.

  figure779
Figure 15:   Sample ``nature'' queries (a) VisualSEEk query using diagrammed query at top left, (b) Color histogram query using query image at top right. Best matches are listed from top to bottom.

Synthetic Image Queries

To test the color/spatial query system, we generated 500 synthetic images by selecting, manipulating and compositing single color regions into the synthetic images. Some examples are illustrated in Figure 16. While the synthetic images appear quite different from real images, the composition of regions is still difficult to decipher. For example, in the images in Figure 16 (bottom), the original composited regions cannot be extracted exactly because of occlusion and aggregation of the regions.

The region library consists of twelve elementary shapes, illustrated at the top of Figure 17. To construct each synthetic image, shapes were selected at random from the library, and were randomly rotated, scaled, colored and composited, as illustrated in Figure 17. The control factors, such as color, size, and location of regions, were used to establish a ground truth database.

  figure789
Figure 16:   Examples of the synthetic images, query images (top), target images (bottom), used for evaluating the joint color/spatial query system.

The synthetic image query experiment was conducted as follows: 100 synthetic query images were generated, which have from one to three randomly selected regions in each, i.e., see Figure 16 (top); 500 target images were generated as described above, i.e., see Figure 16 (bottom). For each query image, all of the target images were assigned a similarity score using the ground truth database and using an exhaustive comparison and distance minimization over all query and target regions (Query GT). The target images from each Query GT were sorted by closest distance to the query image. The target images were assigned a relevance to each query based upon rank in the sorted list as follows: if rank = 1 to 5, relevance = 1; if rank = 6 to 10, relevance = 0.5; if rank = 11 to 500, relevance = 0.

  figure795
Figure 17:   Generation of synthetic images and ground truth database and process for evaluating effectiveness of joint color/spatial queries.

Using the target image relevances obtained from Query GT, the queries were next evaluated using several methods and compared to the Query GT. In Query Q1, the region indexing and distance computation strategy outlined in the paper was carried out on the ground truth database. In Query Q2, the same query strategy was carried out on a region database that was generated automatically from the target images using color set back-projection. Finally, In Query Q3, the combined color histogram of the query regions was matched to the combined region color histogram of each target image as the basis for image retrieval.

  figure799
Figure 18:   Average retrieval effectiveness of 100 randomly generated queries on database of synthetic images, with the four query methods defined as above.

We see in Figure 18 that the color/spatial query strategy (Query Q2) performs much better than color histograms (Query Q3) in retrieving image matches. We also see that Query Q1 performs better than Query Q2. The difference represents the loss of information in the process of automated region extraction through color set back-projection. Furthermore, the drop in retrieval effectiveness in Queries Q1 and Q2 from the ground truth Query GT results from the color/spatial indexing strategies.

In computing the similarity between the query and target images in Query GT, all regions in the target are considered. In this way, some target images are identified as matches even when only two out of three regions are close matches. These configurations are considered only because Query GT conducts an exhaustive search on all target regions. In the indexing strategy outlined in the paper, candidate target images are required to possess regions which are all sufficiently close to the query regions. This restriction, which allows the gain in retrieval efficiency over exhaustive search, explains the retrieval effectiveness drop compared to Query GT.

Evaluation of Color Sets

In order to evaluate the impact of the loss of information in using color sets instead of color histograms, we compared their performance in retrieving images by global color content. This experiment does not evaluate the color/spatial query system, rather, it compares color sets directly to color histograms.

  figure805
Figure 19:   Retrieval of 83 lion images from a database of 3,100 images: D1= color histogram quadratic distance, D2= color set quadratic distance.

In an image database of 3,100 images, we measured the ability of color sets and color histograms to retrieve the 83 images of lions using an example lion image. Figure 19 depicts the retrieval effectivenesses in the retrieval of images of lions. The experiment shows that retrieval effectiveness degrades only slightly using color sets and the quadratic distance measure (Eq. 10) compared to color histograms using the quadratic distance measure (Eq. 6). This indicates that the perceptually significant color information is retained in the color sets.

Example VisualSEEk Queries

We now illustrate the range of color/spatial queries that are possible in VisualSEEk. In the first example, see Figure 20(a), the query (top) specifies the absolute location of a single region. The retrieved image (bottom) has the best match in color and size to the query region and falls within the ``zero-distance'' bound diagrammed in the query. In Figure 20(b), the query specifies two regions. The retrieved image has two color match regions located at the positions in the query image. In Figure 20(c), the query specifies the spatial relationships of three regions. The retrieved image has three regions that best match the colors of the query regions and their spatial relationship satisfies that specified in the query. In Figure 20(d), the query specifies both absolute and relative locations of regions. In this query, the match to the region positioned by absolute location (top left region in query image) considers both the color and location of this region. The match to the other regions (bottom two regions in query image) at first considers only the colors of these regions. In the last stage of the query, the spatial relationships of the regions are evaluated to determine the match.

 

figure817


Figure 20:   Example VisualSEEk queries (a) region with absolute location, (b) two regions with absolute locations, (c) multiple regions with relative locations, (d) multiple regions with both absolute and relative locations.


next up previous
Next: SUMMARY AND FUTURE WORK Up: VisualSEEk: a fully automated Previous: Multiple Regions Query Strategy

John Smith
Wed Sep 18 11:16:33 EDT 1996