Abstract
In this paper, a new variant of an algorithm for normalized cross-correlation (NCC) is proposed in the context of template matching in images. The proposed algorithm is based on the precomputation of a template image approximation, enabling more efficient calculation of approximate NCC with the source image than using the original template for exact NCC calculation. The approximate template is precomputed from the template image by a split-and-merge approach, resulting in a decomposition to axis-aligned rectangular segments, whose sizes depend on per-segment pixel intensity variance. In the approximate template, each segment is assigned the mean grayscale value of the corresponding pixels from the original template. The proposed algorithm achieves superior computational performance with negligible NCC approximation errors compared to the well-known Fast Fourier Transform (FFT)-based NCC algorithm, when applied on less visually complex and/or smaller template images. In other cases, the proposed algorithm can maintain either computational performance or NCC approximation error within the range of the FFT-based algorithm, but not both.
Abstract (translated)
本文提出了一种新的算法变体，用于图像模板匹配中的归一化互相关（NCC）计算。所提出的算法基于对模板图像的预近似计算，使得与使用原始模板进行精确NCC计算相比，可以更高效地与源图像进行近似NCC计算。通过分裂和合并的方法从模板图像中预先计算出近似的模板，在此过程中将其分解为轴对齐的矩形段，这些段的大小取决于每个片段内像素强度方差。在近似模板中，每个分段被分配其对应于原始模板中相应像素的平均灰度值。 所提出的算法在应用于视觉复杂程度较低和/或较小的模板图像时，与著名的基于快速傅立叶变换（FFT）的NCC算法相比，在计算性能上表现出更优的表现，并且几乎不会产生NCC近似误差。而在其他情况下，所提出的方法可以在计算性能或者NCC近似误差中保持在一个范围之内，但无法同时在两者之间实现平衡。
URL
https://arxiv.org/abs/2502.01286
