Name
Abstract | ||
|---|---|---|
We present an efficient pixel-sampling technique for histogram-based search. Given a template image as a query, a typical histogram-based 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 probability-product kernels as the similarity measures, and show that the computation of histograms and the evaluation of the kernel-based similarities can be integrated through a sampling approach. Specifically, we present a square-root 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 memory-efficient. 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/CVPR.2010.5540056 | CVPR |
Keywords | Field | DocType |
image representation,square-root sampling,time complexity,approximation theory,probability-product kernel,image query,histogram-based algorithm,fast histogram-based search,feature histogram,memory requirement,approximation algorithm,computational complexity,image sampling,image retrieval,pixel-sampling technique,search accuracy,template image,kernel-based similarity,similarity measure,probability,approximation algorithms,histograms,testing,sampling technique,indexes,kernel,sampling methods,pixel | Histogram,Pattern recognition,Similarity measure,Computer science,Histogram matching,Adaptive histogram equalization,Artificial intelligence,Balanced histogram thresholding,Image histogram,Time complexity,Standard test image | Conference |
Volume | Issue | ISSN |
2010 | 1 | 1063-6919 |
ISBN | Citations | PageRank |
978-1-4244-6984-0 | 5 | 0.46 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Huang-Wei Chang | 1 | 344 | 13.93 |
| Hwann-Tzong Chen | 2 | 826 | 52.13 |