  Template matching is widely used for many applications in image and signal
processing and usually is time-critical. Traditional methods usually focus on
how to reduce the search locations by coarse-to-fine strategy or full search
combined with pruning strategy. However, the computation cost of those methods
is easily dominated by the size of signal N instead of that of template K. This
paper proposes a probabilistic and fast matching scheme, which computation
costs requires O(N) additions and O(K \log K) multiplications, based on
cross-correlation. The nuclear idea is to first downsample signal, which size
becomes O(K), and then subsequent operations only involves downsampled signals.
The probability of successful match depends on cross-correlation between signal
and the template. We show the sufficient condition for successful match and
prove that the probability is high for binary signals with K^2/log K >= O(N).
The experiments shows this proposed scheme is fast and efficient and supports
the theoretical results.
