# Flipping the kernel in 2D convolution?

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?

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.

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.: (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.