For C
dir
<C
FFT
, we require:
N
2
m
2
< 4N
2
logN +N
2
(3.22)
If the direct implementation of template matching is faster than its Fourier implementation, we
need to choose m so that
m
2
< 4 logN +1 (3.23)
This implies that, for a 256 ×256 image, a direct implementation is fastest for 3 ×3 and 5 × 5
templates, whereas a transform calculation is faster for larger ones. An alternative analysis
(Campbell, 1969) has suggested that (Gonzalez and Wintz, 1987) ‘if the number of non-zero
terms in (the template) is less than 132 then a direct implementation is more efficient than
using the FFT approach’. This implies a considerably larger template than our analysis suggests.
This is in part due to higher considerations of complexity than our analysis has included.<