5
$\begingroup$

SEE: http://www.songho.ca/dsp/convolution/convolution2d_example.html "First, flip the kernel, which is the shaded box, in both horizontal and vertical direction"

Why do we need to flip the kernel in 2D convolution in the first place? So, why can't we leave it unflipped?

Improve this question
$\endgroup$
10
$\begingroup$

The convolution operation is defined by this flip, e.g. for 1D

$$(f * g )(t)\ \stackrel{\mathrm{def}}{=} \int_{-\infty}^\infty f(\tau)\, g(t-\tau)\, d\tau$$

If there was no flipping it would be called cross-correlation, in 1D this is

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

You don't have to do the flipping if the resulting kernel is no different, e.g. an isometric filter.

One reason convolution is used instead of cross-correlation is that convolution is a simple multiplication in the fourier domain, e.g. from wikipedia

$$\mathcal{F}\{f * g\} = k\cdot \mathcal{F}\{f\}\cdot \mathcal{F}\{g\}$$

where $k$ is a constant depending on the normalisation constant of the Fourier transform used.

Proof can be found on wikipedia here:

http://en.wikipedia.org/wiki/Convolution_theorem

Cross-correlation (no flipping) can also be done in the Fourier domain, e.g.

$$\mathcal{F}\{f\star g\}=(\mathcal{F}\{f\})^* \cdot \mathcal{F}\{g\}$$

where $(\mathcal{F}\{f\})^*$ is the complex conjugate of $\mathcal{F}\{f\}$

Another nice property of convolution is that the operation is commutative, e.g.

$$f(x) * g(x) = g(x) * f(x)$$

whereas for cross-correlation it is not.

Even nicer is that convolution of a signal with a dirac delta returns the original signal, shifted, where as for cross-correlation a flipped, shifted, signal is returned.

More information on wikipedia here:

http://en.wikipedia.org/wiki/Cross-correlation

Although it is just a simple flip, convolution and cross-correlation can give quite different results, e.g.:

convolution vs correlation

(note that change in y axes range). The cross-correlation result has a peak exactly at the centre where the two unflipped functions match. Normalised cross-correlation is often used for template matching. The convolution result is different.

See also:

https://dsp.stackexchange.com/questions/2654/what-is-the-difference-between-convolution-and-cross-correlation

The mathematicians take: https://math.stackexchange.com/questions/353272/whats-the-difference-between-convolution-and-crosscorrelation

Improve this answer
$\endgroup$
5
  • $\begingroup$ Could you provide proof that convolution is only multiplication in Fourier domain, when the flipping occurs. So, that multiplication in Fourier domain is not convolution, when there's no flipping $\endgroup$ – user1095332 Apr 25 '13 at 16:09
  • 1
    $\begingroup$ Have updated answer $\endgroup$ – geometrikal Apr 25 '13 at 23:55
  • $\begingroup$ So, what kind of terrible thing can happen, if you don't flip the kernel? $\endgroup$ – user1095332 Apr 26 '13 at 17:54
  • $\begingroup$ Good question, see difference in the graph above. Would like to hear of specific cases where not flipping really stuffs things up. All I know is that for more complex signal processing methods, if the method has been developed, mathematically, using convolution operators and you implement it using cross-correlation the results will be different, especially for methods that give geometric (2D) or phase (1D and 2D) information. $\endgroup$ – geometrikal Apr 26 '13 at 23:10
  • $\begingroup$ @user1095332 is this enough info? If so, please accept my answer. $\endgroup$ – geometrikal Apr 29 '13 at 22:51

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.