TIP 2012 – Correlation Coefficient Based Fast Template Matching Through Partial Elimination

Arif Mahmood, Sohaib Khan
IEEE Transactions on Image Processing, Vol 21, No 4, April 2012

Abstract

Partial computation elimination techniques are often used for fast template matching. At a particular search location, computations are prematurely terminated as soon as it is found that this location cannot compete already known best-match location. Due to non-monotonic growth pattern of the correlation- based similarity measures, partial computation elimination tech- niques have been traditionally considered inapplicable to speedup these measures. In this work we show that partial elimination techniques may be applied to correlation coefficient by using a monotonic formulation and we propose a basic mode and an extended mode partial correlation elimination algorithm for fast template matching. The basic mode algorithm is more efficient on small template sizes while the extended mode is faster on medium and larger templates. We also propose a strategy to decide which algorithm to use for a given dataset. To achieve a high speed up, elimination algorithms require an initial guess of the peak correlation value. We propose two initialization schemes including coarse-to-fine scheme for larger templates and a two-stage technique for small and medium sized templates. Our proposed algorithms are exact, having exhaustive equivalent accuracy, and are compared with the existing fast techniques using real image datasets on a wide variety of template sizes. While the actual speedups are data dependent, in most of the cases our proposed algorithms have been found to be significantly faster than the other algorithms.

Resources

Download PDF
(Distributed here for timely dissemination of scholarly work. Copyright retained by copyright holders. May not be posted without permission from copyright holders.)

Text Reference

Arif Mahmood, Sohaib Khan
"Correlation Coefficient Based Fast Template Matching Through Partial Elimination"
IEEE Transactions on Image Processing, Vol. 21, No. 4, April 2012

Bibtex Reference

@article{mahmood2012correlation,
  title={Correlation Coefficient Based Fast Template Matching Through Partial Elimination},
  author={Mahmood, A. and Khan, S.},
  journal={IEEE Transactions on Image Processing},
  volume={21},
  number={4},
  pages={2099-2108},
  year={2012},
  publisher={IEEE}
}