0
$\begingroup$

picture_1 : Gaussian function(Placing the peak at the top-left element and wrapping around)

picture_2: Gaussian function(Placing the peak in the middle)

There are two square 2-D signals with the same size $m \times m$, if the result of convolution of those two signals is first picture, And the result of cross-correlation of those two signals is second picture.How to prove it in mathematics?

$\endgroup$
  • $\begingroup$ seems like there is an offset issue of $\frac{m}{2}$ to me. they should be the same except one would be upside-down of the other. that means both left-right and up-down are flipped. but with the symmetry you have, flipping is not an issue. so the two should be the same. $\endgroup$ – robert bristow-johnson May 2 '18 at 4:57
  • $\begingroup$ are you performing circular cross-correlation and circular convolution? that is, with the assumption in both the $x$ and $y$ dimensions, that both 2-D signals repeat with a period of $m$? that is $$ f(x+m, y) = f(x, y) \qquad \forall x,y $$ and $$ f(x, y+m) = f(x, y) \qquad \forall x,y $$ ? $\endgroup$ – robert bristow-johnson May 2 '18 at 5:05
  • $\begingroup$ @robertbristow-johnson Thanks for your comment.Yes, the response of picture_1 can be reversed to the response of picture_2.But I don't know why the convolution result is picture_1 while the cross-correlation result is picture_2? I want to prove it in mathematics but I failed. $\endgroup$ – yang9264 May 2 '18 at 5:11
  • $\begingroup$ @robertbristow-johnson Yes,the convolution is circular convolution,but the cross-correlation is something like the convolution layer in CNN, pading and sliding window. $\endgroup$ – yang9264 May 2 '18 at 5:16
  • $\begingroup$ it's not just reversed. if $m$ is the width and height of the pictures, the pics you have shown are offset by $\frac{m}{2}$ in each of the $x$ and $y$ dimensions. $\endgroup$ – robert bristow-johnson May 2 '18 at 5:17
1
$\begingroup$

okay, let's associate the symbols $u$ and $v$ with the dimensions of $x$ and $y$ with respect to each.

and let's assume periodicity in both the $x$ and $y$ dimensions for both pictures. $f(x,y)$ and $g(x,y)$.

$$ f(x+m,y) = f(x,y) \qquad \forall x,y $$ $$ f(x,y+m) = f(x,y) \qquad \forall x,y $$ $$ g(x+m,y) = g(x,y) \qquad \forall x,y $$ $$ g(x,y+m) = g(x,y) \qquad \forall x,y $$

then 2-D Cross-Correlation is:

$$ R_{f,g}(u,v) = \sum\limits_{x=0}^{m-1} \sum\limits_{y=0}^{m-1} f(x,y) \cdot g(x+u,y+v) $$

and 2-D circular convolution is:

$$ (f\circledast \hat{g})(u,v) = \sum\limits_{x=0}^{m-1} \sum\limits_{y=0}^{m-1} f(x,y) \cdot \hat{g}(u-x,v-y) $$

if $\hat{g}(x,y) = g(-x,-y)$, then the cross-correlation and the circular convolution are the same. if $\hat{g}$ is an upside-down copy of $g$, the the correlation and convolution are the same.

or maybe they are upside-down of each other. i think it's:

if $\hat{g}(x,y) = g(-x,-y)$, then

$$ (f\circledast \hat{g})(u,v) = R_{f,g}(-u,-v) $$

that looks about right. someone needs to check this.

$\endgroup$

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