0
$\begingroup$

Background: The question here is related to images in particular and not signal/waveforms.

I have been reading a lot of answers about the difference between convolution and correlation but I am stuck on my doubt as to how are they related to each other while performing operations. Most of the answers are individual answers for each of these terms.

For example:

A statement I am trying to understand says

Here correlation operations are performed by replacing the exhausted convolutions with element-wise multiplications using Discrete Fourier Transform (DFT).

I am not able to relate the individual definitions here. Can anyone please explain this?

$\endgroup$
1
$\begingroup$

What that statement is saying that

a. Correlation is performed the same way as one would perform convolution (you must implicitly know that one of the sequences is conjugated and time reversed to express a correlation as a convolution, as it was not stated there),

and

b. Mathematically the convolution is performed using this relationship

$$x[n]*h[n] = \mathscr{F}^{-1}\left\{\mathscr{F}\left\{x[n]\right\}\cdot\mathscr{F}\left\{h[n]\right\}\right\}$$

Where $*$ denotes convolution, $\mathscr{F}\left\{f[n]\right\}$ denotes the Discrete Fourier Transform of $f[n]$, and $\mathscr{F}^{-1}\left\{F[k]\right\}$ denotes the Inverse Discrete Fourier Transform of $F[k]$.

Note that these operations with Discrete Fourier Transforms actually yield the "circular" convolution of $x[n]$ and $h[n]$, which is equal to the linear convolution of $x[n]$ and $h[n]$ only under a certain condition: there must be enough zero padding to avoid aliasing.

$\endgroup$
  • $\begingroup$ Thank you so much. It really helped me clear a part of my doubt. However, I still have a question. I was studying about matching with correlation (example: using the sum of squared differences). I understand that correlation is done the same way as convolution but why even do convolution if the same thing can be done using correlation. Has it to do with the easiness of computation in Fourier Domain? $\endgroup$ – Sulphur Jul 11 '18 at 21:29
  • $\begingroup$ Why convolution? Discrete convolution is the operation required to implement FIR filtering of a stream of samples of a sampled signal. FIR filters have broad applications. Correlation of a target pattern against a stream of samples is just a special case of an FIR filter known as a matched filter. The matched filter taps are just the time-reversed, conjgated samples of the signal you wish to match. $\endgroup$ – Andy Walls Jul 11 '18 at 22:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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