55
$\begingroup$

I've found on multiple sites that convolution and cross-correlation are similar (including the tag wiki for convolution), but I didn't find anywhere how they differ.

What is the difference between the two? Can you say that autocorrelation is also a kind of a convolution?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ It may be interesting to note that for even, real functions, the cross-correlation and convolution produce the same result. $\endgroup$
    – user5135
    Commented Jul 30, 2013 at 0:06
  • 4
    $\begingroup$ One uses a 5-pointed star ★ and the other uses a 6-pointed star ✶. $\endgroup$
    – endolith
    Commented Apr 9, 2014 at 16:02

5 Answers 5

Reset to default
47
$\begingroup$

The only difference between cross-correlation and convolution is a time reversal on one of the inputs. Discrete convolution and cross-correlation are defined as follows (for real signals; I neglected the conjugates needed when the signals are complex):

$$ x[n] * h[n] = \sum_{k=0}^{\infty}h[k] x[n-k] $$

$$ corr(x[n],h[n]) = \sum_{k=0}^{\infty}h[k] x[n+k] $$

This implies that you can use fast convolution algorithms like overlap-save to implement cross-correlation efficiently; just time reverse one of the input signals first. Autocorrelation is identical to the above, except $h[n] = x[n]$, so you can view it as related to convolution in the same way.

Edit: Since someone else just asked a duplicate question, I've been inspired to add one more piece of information: if you implement correlation in the frequency domain using a fast convolution algorithm like overlap-save, you can avoid the hassle of time-reversing one of the signals first by instead conjugating one of the signals in the frequency domain. It can be shown that conjugation in the frequency domain is equivalent to reversal in the time domain.

Improve this answer
$\endgroup$
6
  • 15
    $\begingroup$ This answer is fine for real signals, but Jason brought up complex-valued signals, in which case it is important to note that it is not quite the case that the "only difference is .... time reversal ..." Indeed, complex conjugates are needed on one of the two signals in the correlation formula (which one is conjugated is a matter of convention - some say to may to and some say to mah to - but both call a fruit a vegetable). On the other hand, neither signal is conjugated in the convolution formula. $\endgroup$
    – Dilip Sarwate
    Commented Jun 20, 2012 at 2:44
  • 3
    $\begingroup$ but what does it mean that they so similar? Using some deep intuitive words! $\endgroup$
    – Diego
    Commented Dec 14, 2012 at 17:20
  • $\begingroup$ I don't see how this is reversing it, rather than shifting it in the opposite direction to what is useful? $\endgroup$
    – Jonathan.
    Commented Dec 16, 2015 at 0:13
  • 1
    $\begingroup$ @Jonathan.: The reversal occurs because the time index $k$ inside of the summation is negated in the case of correlation versus convolution. If you work out the math for an example signal, you'll see the effect. $\endgroup$
    – Jason R
    Commented Dec 16, 2015 at 4:11
  • $\begingroup$ @JasonR, surely this just results in a shift in the opposite direction? I've tried working it out and all that happens is the x input shifts away from the h input and everything ends up as zero. jsfiddle.net/ua5d1uo2 $\endgroup$
    – Jonathan.
    Commented Dec 16, 2015 at 15:03
16
$\begingroup$

For continuous convolution $$[Hf](x) \equiv f(x) * h(x) \equiv \int\mathrm{d}x' h(x-x')f(x')$$ and continuous cross-correlation $$[Gf](x) \equiv f(x) \star h(x) \equiv \int \mathrm{d}x'h^*(x'-x)f(x')$$ It's easy to show that the cross-correlation operator $G$ is the adjoint operator of the the convolution operator $H$.

Also, the convolution operation is commutative$$f(x) * h(x) = h(x) * f(x),$$ while cross-correlation does not have such a property.

$\\\\\\\\$

Improve this answer
$\endgroup$
10
$\begingroup$

As a student I was involved in the same problem as you are. Let me explain to you in the simplest words without any math.

Convolution: It is used to convolve two functions. May sound redundant but I'll put an example: You want to convolve (in a non math term to "combine") a unit cell (which can contain anything you want: protein, image, etc) and a lattice structure. The result would be that this unit cell is organized in each lattice point creating an organized unit cell repeated structure.

Cross-correlation: It is used to identify a cell inside an structure. As an example, you have the image of a small piece of a city and an image of the whole city. With cross-correlation you can determine where that small picture is located inside the whole picture of the city. Saying it more simple, it "scans" until it finds a match. Now the way this is done is by finding a cross-correlation factor that comes from the sum of various multiplications of a value that comes from each picture.

It is very simple. If you want to understand more the math in a friendly way, watch this video. This professor from Caltech explains it in the best way I have ever seen.

https://www.youtube.com/watch?v=MQm6ZP1F6ms

Improve this answer
$\endgroup$
3
$\begingroup$

Wikipedia has a nice diagram to see what's going on here:

enter image description here

Improve this answer
$\endgroup$
2
2
$\begingroup$

Here's a visualization of the two in case it helps with intuition:

http://www.youtube.com/watch?v=Ma0YONjMZLI

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This is a very badly chosen illustration of the difference between the two operations because it leaves the impression that the cross-correlation result is just the time-reverse of the convolution result. $\endgroup$
    – Dilip Sarwate
    Commented Sep 8, 2013 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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