Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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.
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.:
(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:
The mathematicians take: https://math.stackexchange.com/questions/353272/whats-the-difference-between-convolution-and-crosscorrelation
