Fast Template Matching by Subsampled Circulant Matrix
This work addresses time-critical template matching in image and signal processing, offering a faster alternative to traditional methods, though it is incremental as it builds on cross-correlation with downsampling.
The paper tackles the computational inefficiency of template matching when signal size N dominates cost, proposing a probabilistic scheme that reduces operations to O(N) additions and O(K log K) multiplications by downsampling the signal. Experiments confirm the method is fast and efficient, with high success probability for binary signals under conditions like K^2/log K >= O(N).
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.