A method for measuring the complexity of image databases

The state of the art for evaluating image retrieval is quite chaotic: researchers design different algorithms and then test the performance on their own testbeds. The metrics such as precision and recall have been popularly used in the literature but are impractical due to the tedious process of measuring relevance and the human subjectivity. Also, there is no common testbed, and there is no theory on how to compare different testbeds. The lack of an uniform evaluation methodology is clearly a limiting factor in the development of the multimedia retrieval field. In this paper, we present a framework for measuring the complexity of image databases, which characterizes the databases for image retrieval. Motivated from the concept of text corpus perplexity, the complexity of image databases is formulated based on image database statistics and information theory. We propose a quantitative metric which can be used to measure the degree of difficulty to retrieve images based on contents of the database. This metric is independent of queries, hence, it is objective. Experiments on both synthetic and real-world images demonstrate that the proposed measurement is highly effective on quantitatively measuring the contents of image databases for content-based retrieval.