Efficient multi-resolution histogram matching for fast image/video retrieval

Most content-based image/video retrieval systems use histogram matching method to compute the similarity between two histograms. The matching of two images can be accomplished by matching their corresponding histograms. A good image/video retrieval system requires two factors: fast response time and high accuracy. A fast search algorithm called MRSA was proposed previously by applying a multi-resolution structure to gain speed-up and to have the same retrieval accuracy as the exhaustive search algorithm. In this paper, we improve the retrieving speed of MRSA while maintaining the global retrieval accuracy. The retrieving speed is improved by using the non-uniform quantization method to obtain lower resolution histograms and the non-uniform quantization method is proven to be able to reduce the number of comparisons at lower resolution levels. Furthermore, we not only extend the multi-resolution concept from uniform quantization to non-uniform quantization but also employ another similarity measurement, chi(2) distance, to construct the multi-resolution structure. Due to the thresholding mechanism, the proposed non-uniform quantization based method relieves the over-smooth problem suffering from downsampling. Hence, our method will reduce noticeable unnecessary comparisons at low resolution levels than MRSA by selecting a proper quantization table. The employing of additional similarity measurement and different quantization criterion increases the flexibility and the efficiency of the algorithm. Experiments demonstrate the validity and efficiency of our algorithm in some typical image/video retrieval applications. (C) 2008 Elsevier B.V. All rights reserved.