The Tensor Core bank of the previous section is faster when many templates are searched together. The complementary case – a single template, matched exhaustively against every location in the image – has its own well-suited method, the fast Fourier transform, an approach first published in J.P. Lewis’s Fast Normalized Cross-Correlation.
The numerator SumIT is a cross-correlation of the image
with the template, and the correlation theorem computes a
cross-correlation as a pointwise product in the frequency domain.
Transforming the image and the zero-padded template, multiplying one by
the conjugate of the other, and transforming back yields
SumIT at every shift at once:
\[\text{SumIT} = \text{IFFT}\big(\text{FFT}(I) \cdot \overline{\text{FFT}(T)}\big).\]
cuFFT computes the two forward transforms and the inverse, and a small kernel performs the pointwise multiply-conjugate between them.
Importantly, computing numerators in this way does not depend on the template size. An \(H \times W\) transform is \(O(HW \log HW)\) whether the template is 8×8 or 128×128, while a spatial search does \(O(K)\) work per output pixel and grows with the template area. For a small template, the spatial kernel of Section 15.5 wins easily; as the template grows, its per-pixel cost rises until the FFT, flat across template sizes, overtakes the spatial kernel.
Where the two cross depends on both the template size and which spatial kernel is the baseline. Against the tuned DP4A kernel of Section 15.5, the crossover on a GeForce RTX 3060 sits near a 24×24 template, with the FFT about 2× faster at 32×32 and about 8× faster at 64×64 (Figure 15-6).
Figure 15-6. FFT vs. spatial (DP4A) numerator crossover on a GeForce RTX 3060: the spatial cost grows with template area while the FFT is size-independent, so the FFT overtakes the tuned spatial kernel beyond a ≈24×24 template. Points are the measured reference values; the curve is the template-area growth they imply.
cuFFT works in single precision, so the FFT numerator is approximate – the sample measures a worst-case relative error near \(10^{-6}\) against an exact spatial numerator, immaterial for locating a peak. The denominator, by contrast, must stay exact, and it comes from the summed-area table of the next section. The transform is run on a power-of-two padding of the image, both because cuFFT is fastest at those sizes and because the padding keeps the circular correlation from wrapping across the image edges into the valid search region.
The sample corrFFT.cu extracts a template from the coins
image, runs the full pipeline – FFT numerator, summed-area-table
denominator, coefficient, peak – and confirms the template is localized
to its own position at a coefficient of 1.00000.