Correlation Coefficient Based Fast Template Matching Through Partial Elimination

Arif Mahmood, Sohaib Khan

Download our paper here.

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 correlation-based similarity measures, partial computation elimination techniques 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 to large templates. We also propose a strategy to decide on 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 large templates and a two-stage technique for small to 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 many cases our proposed algorithms have been found to be faster by more than an order of magnitude.

Executables, Bat Files and Datasets

Experiments with Basic Mode PCE Algorithm

• Block Matching For Motion Estimation Experiment
  1. Eleven Video Datasets
  2. Bat file with complete script of full experiment
  3. Readme File containing Explanation of Input Parameters
  4. Executable files compiled by Visual C++ 2008 Express Edition, installed on 64 bit Windows 7 OS, for FFTW3, Spatial Domain (SPAT), PCE Basic Mode (PCE), ZNccEbc for Block Matching, and Sum of Absolute Differences (SAD) with PDE and SEA optimizations.
  5. Detailed result files with match location, execution times and total blocks matched in each frame
     Click to Download the Complete Folder
• Feature Matching Experiment for Point Correspondence
  1. UAV Dataset and Feature Files created by KLT Feature Tracker
  2.  Bat file with complete script of full experiment
  3. Readme File containing Explanation of Input Parameters
  4. Executable files compiled by Visual C++ 2008 Express Edition, installed on 64 bit Windows 7 OS, for FFT, FFTW3, Spatial Domain, PCE Basic Mode (PCE_simple), and ZNccEbc.
  5. Detailed result files with match location and execution times
     Click to Download the Complete Folder