An efficient algorithm for exhaustive template matching based on normalized cross correlation

This work proposes a novel technique aimed at improving the performance of exhaustive template matching based on the normalized cross correlation (NCC). An effective sufficient condition, capable of rapidly pruning those match candidates that could not provide a better cross correlation score with respect to the current best candidate, can be obtained exploiting an upper bound of the NCC function. This upper bound relies on partial evaluation of the crosscorrelation and can be computed efficiently, yielding a significant reduction of operations compared to the NCC function and allows for reducing the overall number of operations required to carry out exhaustive searches. However, the bounded partial correlation (BPC) algorithm turns out to be significantly data dependent. In this paper we propose a novel algorithm that improves the overall performance of BPC thanks to the deployment of a more selective sufficient condition which allows for rendering the algorithm significantly less data dependent. Experimental results with real images and actual CPU time are reported. © 2003 IEEE.