Fast Normalized Cross-Correlation for Template Matching with Rotations
José María Almira Harold Phelippeau Antonio Martinez-Sanchez
Normalized cross-correlation is the reference approach to carry out template
matching on images. When it is computed in Fourier space, it can handle
efficiently template translations but it cannot do so with template rotations.
Including rotations requires sampling the whole space of rotations, repeating
the computation of the correlation each time.
  This article develops an alternative mathematical theory to handle
efficiently, at the same time, rotations and translations. Our proposal has a
reduced computational complexity because it does not require to repeatedly
sample the space of rotations. To do so, we integrate the information relative
to all rotated versions of the template into a unique symmetric tensor template
-which is computed only once per template-. Afterward, we demonstrate that the
correlation between the image to be processed with the independent tensor
components of the tensorial template contains enough information to recover
template instance positions and rotations.
  Our proposed method has the potential to speed up conventional template
matching computations by a factor of several magnitude orders for the case of
3D images.