29
$\begingroup$

I am trying to understand the difference between convolution to cross-correlation. I have read an understood This answer. I also understand the picture below.

But, in terms of signal processing, (a field which I know little about..), Given two signals (or maybe a signal and a filter?), When will we use convolution and when will we prefer to use cross correlation, I mean, When in real life analysing will we prefer convolution, and when, cross-correlation.

It seems like these two terms has a lot of use, so, what is that use?

Covolution

$\endgroup$
21
$\begingroup$

In signal processing, two problems are common:

  • What is the output of this filter when its input is $x(t)$? The answer is given by $x(t)\ast h(t)$, where $h(t)$ is a signal called the "impulse response" of the filter, and $\ast$ is the convolution operation.

  • Given a noisy signal $y(t)$, is the signal $x(t)$ somehow present in $y(t)$? In other words, is $y(t)$ of the form $x(t)+n(t)$, where $n(t)$ is noise? The answer can be found by the correlation of $y(t)$ and $x(t)$. If the correlation is large for a given time delay $\tau$, then we may be confident in saying that the answer is yes.

Note that when the signals involved are symmetric, convolution and cross-correlation become the same operation; this case is also very common in some areas of DSP.

$\endgroup$
  • $\begingroup$ Got it. Thanks a lot for your clear and bright answer! $\endgroup$ – MathBgu Dec 2 '15 at 16:30
  • 1
    $\begingroup$ what I like about the impulse response explanation is you really get an intuition why convolution is "reversed". In discrete terms, the current output is the current input x impulse response at time 0 + residual output from previous inputs impulse responses (input a n-1 * impulse 1 + input n-2 * impulse 2 and so on). $\endgroup$ – Jean-Frederic PLANTE Aug 21 '17 at 20:35
  • $\begingroup$ @Jean-FredericPLANTE yes, that's a good way to explain it. $\endgroup$ – MBaz Aug 21 '17 at 21:44
11
$\begingroup$

The two terms convolution and cross-correlation are implemented in a very similar way in DSP.

Which one you use depends on the application.

If you are performing a linear, time-invariant filtering operation, you convolve the signal with the system's impulse response.

If you are "measuring the similarity" between two signals, then you cross-correlate them.

The two terms come together when you try to produce a matched filter.

Here, you are trying to decide whether a given signal, $s[n]$ contains a known "pulse" (signal), $p[n]$. One way to do that is to convolve the given signal, $s$ with the time-reversal of the known pulse, $p$ : you are now using convolution to perform the cross-correlation of the given signal with the known pulse.


A Side Note

The term "cross-correlation" is (for some) misused in the field of DSP.

For statisticians, a correlation is a value that measures how close two variables are and should be between $-1$ and $+1$.

As you can see from the Wikipedia entry on cross-correlation, the DSP version is used and they state:

cross-correlation is a measure of similarity of two series as a function of the lag of one relative to the other.

The problem with the DSP definition: $$ \sum_{\forall m} x[n] y[n+m] $$ is that this "similarity" measure depends upon the energy in each signal.

$\endgroup$
  • 1
    $\begingroup$ This is extremely helpfull for me. Thank you! $\endgroup$ – MathBgu Dec 2 '15 at 16:30
3
$\begingroup$

In signal processing, the convolution is performed to obtain the output of an LTI system. The correlation (auto, or cross correlation) usually is calculated to be used later to do some other calculations

You have to be careful not to confuse correlation, covariance, and correlation coefficient. The correlation does not necessarily have to be between -1 and 1. The correlation coefficient (https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient) falls between -1 and 1 because it is scaled by the two random variables variances. The thing we have to remember is that the real operation to be done in statistical signal processing to analize how related are two random variables is the "Covariance", not the correlation. But for most applications where a signal is captured by a sensor and transformed into a voltage and the digitized with an ADC, you can assume that the signal is zero mean, hence the correlation is equal to the covariance.

$\endgroup$
  • $\begingroup$ I will have a look in that link. Thank you! $\endgroup$ – MathBgu Dec 2 '15 at 16:31
3
$\begingroup$

@MathBgu I have read all above given answers, all are very informative one thing I want to add for your better understanding, by considering the formula of convolution as follows

$$f(x)*g(x)=\int\limits_{-\infty}^{\infty}f(\tau)g(x-\tau)\,d\tau$$

and for the cross correlation

$$(f\star g)(t)\stackrel{\text{def}}{=}\int\limits_{-\infty}^{\infty}f^*(\tau)g(t+\tau)\,d\tau,$$

we come to know that equation-wise the only difference is that, in convolution, before doing sliding dot product we flip the signal across y-axis i.e we change $(t)$ to $(-t)$, while the cross correlation is just the sliding dot product of two signals.

We use the convolution to get output/result of a system which have two blocks/signals and they are directly next to each other (in series) in the time domain.

$\endgroup$
  • $\begingroup$ Thank you for mentioning thos additionsl clearifying point! $\endgroup$ – MathBgu Dec 16 '15 at 17:11
2
$\begingroup$

There is a lot of subtlety between the meanings of convolution and correlation. Both belong to the broader idea of inner products and projections in linear algebra, i.e. projecting one vector onto another to determine how "strong" it is in the direction of the latter.

This idea extends into the field of neural networks, where we project a data sample onto each row of a matrix, to determine how well it "fits" that row. Each row represents a certain class of objects. For example, each row could classify a letter in the alphabet for handwriting recognition. It's common to refer to each row as a neuron, but it could also be called a matched filter.

In essence, we're measuring how similar two things are, or trying to find a specific feature in something, e.g. a signal or image. For example, when you convolve a signal with a bandpass filter, you're trying to find out what content it has in that band. When you correlate a signal with a sinusoid, e.g. the DFT, you're looking for the strength of the sinusoid's frequency in the signal. Note that in the latter case, the correlation doesn't slide, but you're still "correlating" two things. You're using an inner product to project the signal onto the sinusoid.

So then, what's the difference? Well, consider that with convolution the signal is backwards with respect to the filter. With a time-varying signal, this has the effect that the data is correlated in the order it enters the filter. For a moment, let's define correlation simply as a dot product, i.e. projecting one thing onto another. So, at the start, we're correlating the first part of the signal with the first part of the filter. As the signal continues through the filter, the correlation becomes more complete. Note that each element in the signal is only multiplied with the element of the filter it's "touching" at that point in time.

So then, with convolution, we're correlating in a sense, but we're also trying to preserve the order in time that changes occur as the signal interacts with the system. If the filter is symmetrical, however, as it often is, it doesn't actually matter. Convolution and correlation will yield the same results.

With correlation, we're just comparing two signals, and not trying to preserve an order of events. To compare them, we want them facing in the same direction, i.e. to line up. We slide one signal over the other so we can test their similarity in each time window, in case they're out of phase with each other or we're looking for a smaller signal in a larger one.

In image processing, things are a little different. We don't care about time. Convolution still has some useful mathematical properties, though. However, if you're trying to match parts of a larger image to a smaller one (i.e. matched filtering), you won't want to flip it because then the features won't line up. Unless, of course, the filter is symmetrical. In image processing, correlation and convolution are sometimes used interchangeably, particularly with neural nets. Obviously, time is still relevant if the image is an abstract representation of 2-dimensional data, where one dimension is time - e.g. spectrogram.

So in summary, both correlation and convolution are sliding inner products, used to project one thing onto another as they vary over space or time. Convolution is used when order is important, and is typically used to transform the data. Correlation is typically used to find a smaller thing inside of a larger thing, i.e. to match. If at least of one of the two "things" is symmetrical, then it doesn't matter which you use.

$\endgroup$
0
$\begingroup$

Keep Signal Processing aside, if you just try to understand what is happening in Convolution and Correlation, both are very similar operations. The only difference is in Convolution, one of the variable is inverted(flipped) before performing the accumulation of the product. See that i am not using the word signal anywhere above. I am only talking in terms of the operations performed.

Now, let us come to Signal Processing.

Convolution operation is used to calculate the output of a Linear Time Invariant System (LTI system) given an input singal(x) and impulse response of the system (h). To understand why only Convolution operation is used to get the output of an LTI system, there is big derivation. Please find the derivation here.

http://www.rctn.org/bruno/npb163/lti-conv/lti-convolution.html

Correlation operation is used to find the similarity between the two signals x and y. More the value of correlation, more is the similarity between the two signals.

Understand the difference here,

  • Convolution --> between signal and a system(filter)

  • Correlation --> between two signals

So, from signal analysis point of view, Convolution operation is not used. Only correlation is used from signal analysis point of view. Whereas convolution is used from System analysis point of view.

Best way to understand the operations of convolution and correlation is to understand what happens when two convolution and correlation is done between two continuous variables like shown in the diagrams in the question.

$\endgroup$

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.