iv-D Iteration over Color Sets

To help prune the iteration over the great number of possible color sets we utilize two additional thresholds in the iteration system. The algorithm back-projects only those color sets that meet minimum support constraints. The color set is back-projected onto the image only if thresholds are met that predict whether the back-projection will produce new and desirable regions.

iv-D.1 Threshold

The threshold corresponds to the image's support for each color in the color set. A color set used for the back-projection only if for m such that c[m] = 1 there are at least pixels in the image of color m. In other words, if color m is selected in the color set then color m must be present in the global histogram with a support of samples.

iv-D.2 Threshold

The threshold corresponds to the un-allocated colors from the global histogram. After a color set is back-projected and regions are extracted, the colors from the extracted regions are subtracted from the global image histogram. A color set is used for the back-projection only if for m such that c[m] = 1 there are at least pixels in the global residue histogram of the color m. In other words, if a color set includes color m then samples of color m must be still be un-allocated to previously extracted regions. This threshold works well when the color sets are explored in order of increasing magnitude. For example, single color - color sets are explored first, followed by two color - color sets, etc. This gives desirable results because color regions are extracted in order of dominance.

If is not met then contains colors that are not represented sufficiently by any region. The back-projection of this and all its super-sets are non-generative. If is met while is not met then at query time a color region containing all of the colors in can be reconstructed using subsets of and spatial composition. Therefore, exploration of and its super-sets generates redundant information. The color set iteration procedure is summarized as follows:

1. Single color - color sets
   1. Given the image histogram H[m] find all where .
   2. For each construct unit length where c[k] = 1 for and c[k] = 0 otherwise. Back-project each onto image R[m,n] and extract regions. For each region n record the local region histogram .
   3. Compute residue histogram .
2. Two color - color sets
   1. Find all and where , , and , .
   2. For each pair and construct where c[k] = 1 for or and c[k] = 0 otherwise. Back-project each onto image R[m,n] and extract regions. For each region n record the local region histogram .
   3. Update residue histogram .
3. Three color - color sets, etc., repeat above.