This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Search for Publication

Year(s) from:  to 
Keywords (separated by spaces):

Bounds for the discrimination power of color indexing techniques

M. Stricker
Storage and Retrieval for Image and Video Databases II
February 1994


Most color indexing techniques proposed in the literature are similar: Images are represented by color histograms, and a metric on the color histogram space is used to determine the similarity of images. In this paper we determine the limits of these color indexing techniques. We propose two functions to measure the discrimination power of indexing techniques: The capacity (how many distinguishable histograms can be stored) and the maximal match number (the maximal number of retrieved images). We derive bounds for these functions. These bounds have two practical aspects. First, they help a user to decide whether color histograms effectively index database images from a given domain. Second, they facilitate the choice of a good threshold for the distance below which histograms are considered similar. Our arguments are based on an analysis of the metrical properties of the histogram space and results from coding theory. The results show that over a large range of reasonable parameters the capacity is very large. Thus, the set of parameters for which color indexing works well can be described as the set of parameters for which the maximal match number is below an application-dependent maximum.

Download in postscript format
  author = {M. Stricker},
  title = {Bounds for the discrimination power of color indexing techniques},
  booktitle = {Storage and Retrieval for Image and Video Databases II},
  year = {1994},
  month = {February},
  pages = {15-24},
  volume = {2185},
  series = {SPIE PUBL_Proceedings Series},
  keywords = {image indexing, color, database}