A SquareRoot Sampling Approach to Fast HistogramBased Search

Abstract

We present an efficient pixelsampling technique for histogrambased search. Given a template image as a query, a typical histogrambased algorithm aims to find the location of the target in another large test image, by evaluating a similarity measure for comparing the feature histogram of the template with that of each possible subwindow in the test image. The computational cost would be high if each subwindow needs to compute its histogram and evaluate the similarity measure. In this paper, we adopt the probabilityproduct kernels as the similarity measures, and show that the computation of histograms and the evaluation of the kernelbased similarities can be integrated through a sampling approach. Specifically, we present a squareroot sampling method to avoid the computation of histograms, and meanwhile, reduce the number of pixels required for evaluating the similarity measure. The proposed approximation algorithm is time and memoryefficient. The time complexity of computing the similarity for each subwindow is $O(1)$. The memory requirement of our algorithm is not in proportion to the size of the template or the number of histogram bins, which allows the use of more distinctive image representations for better search accuracy.
Last updated: 05 May 2010