1
$\begingroup$

Referring to the answer here: https://www.quora.com/Why-are-convolutional-nets-called-so-when-they-are-actually-doing-correlations, the equation for a discrete 2D convolution is specified as:

$$C(x,y)=\sum_{m=1}^M\sum_{n=1}^NI(m,n)K(x-m,y-n)$$

or

$$C'(x,y)=\sum_{m=1}^M\sum_{n=1}^NI(x-m,y-n)K(m,n)$$

where $I$ is the image and $K$ is the kernel or filter. I can't understand how the indices work. Let's say I have the image:

$\begin{bmatrix}I_{11} & I_{12} & I_{13} & I_{14} & I_{15}\\ I_{21} & I_{22} & I_{23} & I_{24} & I_{25}\\ I_{31} & I_{32} & I_{33} & I_{34} & I_{35}\\ I_{41} & I_{42} & I_{43} & I_{44} & I_{45}\\ I_{51} & I_{52} & I_{53} & I_{54} & I_{55} \end{bmatrix}$ and kernel $\begin{bmatrix}K_{11} & K_{12} & K_{13}\\ K_{21} & K_{22} & K_{23}\\ K_{31} & K_{32} & K_{33}\end{bmatrix}$

Now by the above definition (in this case $M=3$ and $N=3$) $$C_{11} = I_{11}K_{00}+I_{12}K_{0,-1}+I_{13}K_{0,-2}\\ +I_{21}K_{-1,0}+I_{22}K_{-1,-1}+I_{23}K_{-1,-2}+\\ +I_{31}K_{-2,0}+I_{32}K_{-2,-1}+I_{33}K_{-2,-2}$$

or

$$C'_{11} = I_{00}K_{11}+I_{0,-1}K_{12}+I_{0,-2}K_{13}\\ +I_{-1,0}K_{21}+I_{-1,-1}K_{22}+I_{-1,-2}K_{23}+\\ +I_{-2,0}K_{31}+I_{-2,-1}K_{32}+I_{-2,-2}K_{33}$$

Even if I assume that the indices for $C$ or $C'$ run from $2$ to $4$ (instead of $1$ to $3$), then $$C_{22} = I_{11}K_{11}+I_{12}K_{1,0}+I_{13}K_{1,-1}\\ +I_{21}K_{0,1}+I_{22}K_{0,0}+I_{23}K_{0,-1}+\\ +I_{31}K_{-1,1}+I_{32}K_{-1,0}+I_{33}K_{-1,-1}$$

or

$$C'_{22} = I_{11}K_{11}+I_{1,0}K_{12}+I_{1,-1}K_{13}\\ +I_{0,1}K_{21}+I_{0,0}K_{22}+I_{0,-1}K_{23}+\\ +I_{-1,1}K_{31}+I_{-1,0}K_{32}+I_{-1,-1}K_{33}$$

So no matter how the indices are defined, the indices for either $I$ or $K$ go out of bounds in the expression for convolution. How do I make sense of this? What's meant by terms with negative indices like $I_{-1,-2}$ or $K_{0,-1}$?


Follow-up doubt: So assuming zero-padding, all terms with non-positive indices are assumed to be $0$. From that, given the two formulas for $C_{22}$ and $C'_{22}$ above, they evaluate to just $I_{11}K_{11}$, since all terms involving non-positive indices vanish. But that doesn't sound right, since from my understanding, it should evaluate to:

$$\begin{bmatrix}I_{11} & I_{12} & I_{13}\\ I_{21} & I_{22} & I_{23}\\ I_{31} & I_{32} & I_{33}\end{bmatrix}: \begin{bmatrix}K_{33} & K_{32} & K_{31}\\ K_{23} & K_{22} & K_{21}\\ K_{13} & K_{12} & K_{11}\end{bmatrix}$$

(where $:$ represents Frobenius inner product) since convolution is the same as cross-correlation with a flipped kernel. So I still can't make sense of the formulas for $C_{22}$ and $C'_{22}$ as I wrote above.

$\endgroup$
1
$\begingroup$

From http://www.deeplearningbook.org/contents/convnets.html,

The only reason to flip the kernel is to obtain the commutative property. While the commutative property is useful for writing proofs, it is not usually an important property of a neural network implementation. Instead, many neural network libraries implement a related function called the cross-correlation, which is the same as convolution but without flipping the kernel.

The discrete cross correlation function with 1-based indexing for $$I = U*V\ and\ K=M*N$$ is given by $$C(x,y)=\sum_{m=1}^M\sum_{n=1}^NI(x+m-1,y+n-1)K(m,n)$$

where $$x\in(U-M+1)\ and\ y\in(V-N+1)$$

When applying 2-D convolutions, many neural network implementations will reduce the size of the output. To retain the original size in output and to retain information at the borders, many practical use cases add a padding of zeros to the input image.

Coming back to your specific question, in the case where indices go out of bounds, either on the positive side or on the negative side, (which happens when you try to retain the size of the input in your output), values corresponding to them are usually taken as zeros, which is akin to zero-padding in implementation.

Discrete convolutions are actually given by $$(f * g)[n] = \sum_{m=-\infty}^\infty f[n-m] g[m]$$ In practice the limits are made finite because of the same assumption of zero amplitude signal for out of bound indices.

$\endgroup$
  • $\begingroup$ Thanks so much! But that still does not answer the original question. $\endgroup$ – Shirish Kulhari Jul 4 at 16:32
  • $\begingroup$ Edited to answer the question more specifically. $\endgroup$ – Yash Jakhotiya Jul 4 at 17:14
  • $\begingroup$ Hi Yash, I have a follow-up doubt and have edited the question. Would be really grateful if you could clarify that! $\endgroup$ – Shirish Kulhari Jul 5 at 8:58
  • $\begingroup$ The given formulas seem, at the very best, misleading. First, it has not been mentioned if they follow 1-based or 0-based indexing. Second, in both of these cases, the limits are off. Your understanding of C(2, 2) to be a Frobenius Inner Product of the matrices you mentioned is correct. $\endgroup$ – Yash Jakhotiya Jul 5 at 12:27

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.