We now define the strategy for processing the color set queries, which is an important building block in the overall image query process. The color set query compares only the color content of regions or images. Spatial queries are considered in the next section. Given query , the best match to Q is target , where,
A straightforward way to process the query is to compute exhaustively for all j using Eq. 10. In this case, the computation of requires M'+1 additions per target and no multiplications, where M' is the number of non-zero colors in . This provides for drastic improvement over the original histogram quadratic form. The complexity of this approach, where M= size of color set (histogram) and N= number of images in the database, is O((M'+1)N), where M' << M, gives the number of non-zero colors in the query color set. Compare this to a naive computation of quadratic histogram distance, which is . In QBIC, the computation is reduced by the technique in [5] to , where typically, M'' = 3, and C << N. We note that the technique in [5] can be combined with the color set technique to further reduce complexity.
Given the query color set: find the best match to color set , where defines the maximum tolerance for color set distance, the following range queries produce the best match:
As this query strategy illustrates, color region matching is accomplished by performing several range queries on the query color set's colors, taking the intersection of these lists and minimizing the sum of attributes in the intersection list. The best match minimizes the color set distance. Since this strategy merely provides efficient indexing of the terms in the decomposed quadratic color set distance equation, the query strategy provides for no false dismissals. The final candidate image list has false alarms which are removed through the final minimization which requires only additions in the computation of . Using a similar indexing strategy for retrieving images using color histograms in a database of 750,000 images, the computation of the 60 best matches takes less than two seconds [16].