fast 2D cross correlation algorithm 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.