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?

  • $\begingroup$ are you sure that there will only be one match, or might there be multiple matches? you might be able to halt processing on each potential match if you've already found a better match elsewhere? $\endgroup$ – endolith Sep 17 '14 at 19:30

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.

  • $\begingroup$ Thank you for your input. Is there any trick operated in time domain to speed up the correlation a little bit(probably not necessary a reduction of time complexity, perhaps just an avoidance of some of the calculations)? $\endgroup$ – ChuNan Jul 4 '14 at 13:00
  • $\begingroup$ Have a look at this paper. It goes over a slew of available algorithms. Overlap-save (OLS), overlap-add (OLA), just to name a few. You haven't really mentioned if you're planning on doing this on a GPU or CPU, which makes a difference. $\endgroup$ – porten Jul 4 '14 at 15:59
  • 1
    $\begingroup$ You can also use the pyramid approach, i.e. do the cross-correlation on smaller image to determine search boundaries for higher resolution. This approach may however result in finding local minima in some images with very spikey response (e.g. consider correlation of checkerboad patterns) so sampling factor and number of levels need to be considered as well. $\endgroup$ – Libor Sep 17 '14 at 18:26

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".

  • $\begingroup$ oh, your template is smaller, so you should zero-pad the template to be, with the padding, the same size as the image. FFT them both, complex conjugate one of those resulting FFTs, multiply those together, and iFFT that product image. the result should be your cross-correlation. you might have to also zero-pad the image a little (maybe by the size of the template before padding). $\endgroup$ – robert bristow-johnson Sep 17 '14 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.