Template Matching using FFT

Can anyone please explain how to perform template matching using FFT. The template is smaller than the original image. 1. Everywhere it states that the template has to be padded with zeros. How 开发者_Python百科it is done. Is it added to the bottom and right of the image or equally around the entire image.

Thanks in advance.

---

You are using the Fourier Transform to calculate the cross correlation; it's as simple as that.

Padding is performed around all sides of the template. This is because a standard Fast Fourier Transform can only operate on data sizes that are 2^n in size therefore your template and the image need to be 2^n * 2^n in size. Since it usually isn't, the template is resized to meet this requirement by padding the outside with zeros. These zeros have no effect on the FFT calculation.

Consider using phase correlation, the extra effort is very small and you can get great results.

---

The chapters 3 and 4 of Gonzalez and Woods, "Digital Image Processing" should help you acquire a better understanding of the theory.

You need to perform a correlation between your image and your template. In some cases, it may be more efficient to perform this correlation in the frequency domain (using FFT), while in others you would want to perform the operation in the spatial domain.

Some software systems make this choice transparent to the users. See for example the function ImageCorrelate in Mathematica (http://reference.wolfram.com/mathematica/ref/ImageCorrelate.html).

---

Here's a great resource, that answers your question and a bunch of related tradeoffs.