I want to match a small template to a larger image, that the distance between the template and the subimage with the same size of the template is minimized. It can be solved directly or by applying 2D cross correlation, and both methods have an O(n^4) time complexity. Are there any method to simplify the algorithm by either reducing the complexity or applying pre-processing?
If your template or kernel is small, then straight convolution might be the fastest approach. There's a crossover point when performing convolution in the frequency domain is faster than straight time/spatial domain convolution and it can be hardware dependent, but usually when the kernel (template) approaches 1/4-1/2 the size of the image frequency domain convolution is faster.
If you have a multicore machine you can split the larger image into say 4 quadrants and run the spatial convolution on 4 threads and fuse the results together. That should actually be pretty speedy.
ya know, i've never done 2D signal processing other than using MATLAB's surf( ) function naïvely, but i would bet that if you 2D-FFT your 2D data (possibly doubling both length and width by mirror reflecting the data to reduce edge effects, or maybe you should zero-pad), pointwise multiply the FFT of the data with the complex conjugate of the FFT of the template, and iFFT the result, you will get the 2D cross-correlation. and the first "F" in "FFT" stands for "fast".