TIP 2010 – Exploiting Transitivity of Correlation for Fast Template Matching

Arif Mahmood, Sohaib Khan
IEEE Transactions on Image Processing, Vol 19, N0. 8, Aug 2010

Abstract

Elimination Algorithms are often used in template matching to provide a significant speed-up by skipping portions of the computation while guaranteeing the same best-match location as exhaustive search. In this work, we develop elimination algorithms for correlation-based match measures by exploiting the transitivity of correlation. We show that transitive bounds can result in a high computational speed-up if strong autocorrelation is present in the dataset. Generally strong intrareference local autocorrelation is found in natural images, strong inter-reference autocorrelation is found if objects are to be tracked across consecutive video frames and strong intertemplate autocorrelation is found if consecutive video frames are to be matched with a reference image. For each of these cases, the transitive bounds can be adapted to result in an efficient elimination algorithm. The proposed elimination algorithms are exact, that is, they guarantee to yield the same peak location as exhaustive search over the entire solution space. While the speed-up obtained is data dependent, we show empirical results of up to an order of magnitude faster com- putation as compared to the currently used efficient algorithms on a variety of datasets.

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,
"Exploiting Transitivity of Correlation for Fast Template Matching"
Vol. 19, No. 8, pp. 2190-2200, Aug 2010

Bibtex Reference:

@article{mahmood2010exploiting,
  title={Exploiting transitivity of correlation for fast template matching},
  author={Mahmood, A. and Khan, S.},
  journal={Image Processing, IEEE Transactions on},
  volume={19},
  number={8},
  pages={2190--2200},
  year={2010},
  publisher={IEEE}
}