0
$\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$
2
$\begingroup$

A Convolutional filter is a fixed-size filter, in this case 3x3. Therefore it is assumed to be identically 0 outside this range, so for example $K_{0,1}=K_{4,3}=0$. It would be obscenely expensive to sum over these indices, hence people restrict to just the 3x3 window of indices, as all other terms are identically 0.

Also, note that the quota definition uses the mathematical convention of convolution whereas in CS it’s backwards e.g $K(m,n)I(x+m,y+n)$. Take a look at Karpathy’s notes to understand these concepts better: https://cs231n.github.io/convolutional-networks/#overview

$\endgroup$
  • $\begingroup$ 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 10:06
  • $\begingroup$ @Kulhari: it is correct but again the definition of convolution here is not the standard one (see my answer). $\endgroup$ – Alex R. Jul 5 at 17:08

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.