2
$\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$ The convention is that you take all terms with negative indices to be 0; it allows us to write concise formulas like the one above without having to make a bunch of special cases $x\geq m$, $x<m$, etc. $\endgroup$ – Sohom Paul Jul 4 '19 at 19:41
2
$\begingroup$

This is what padding is meant to handle. Indeed, computing convolutions (or correlations, more accurately) near an image edge will always end up "going out of bounds" (since the value at output pixel $(i,j)$ depends on image values within $(i\pm K,j\pm K)$ for a square kernel of size $K$).

The question is what to do when an out-of-bounds is hit. One approach is to simply not compute anything, meaning the output image will be smaller than the input image, with missing edge pixels. Another approach is to use partial convolutions, meaning that out-of-bounds pixels are ignored but that values are still computed for edge pixels (with reweightings to handle the missing pixels). The most popular approach is padding. For instance, constant padding assumes that $I_{\xi\eta}=c$ for out-of-bounds or negative indices $\xi,\eta$ and constant $c\in\mathbb{R}$ ($c=0$ for zero-padding), while replication padding sets a dynamic $c$ that takes on the value of the nearest valid pixel.

Related: Should I pad zero or mean value in a convolution neural network? What about reflective padding? and What are the pros and cons of zero padding in a convolution layer?


Edit in response to question edit (7/5/19):

Ok, so there is an issue with how you've written convolution here. In implementation, indeed, you must index from $1$ (actually $0$) when walking over the kernel. But then the formula has to change accordingly (i.e., the summand will include an additional offset). In other words your notation mixes up the "theoretical" and "computational" formulas.

I suggest writing it in the following way, which is how discrete convolutions tend to be written in theory. Let $K$ be an $M\times N$ zero-padded and zero-centered kernel, so that $K:[-\infty,\infty]^2\subset\mathbb{Z}^2\rightarrow\mathbb{R} $. Zero-padded means the kernel will be defined at any index (including negatives); zero-centered means that the middle of the kernel occurs at index $(0,0)$. (E.g., in your $3\times 3$ example, $K_{22}$ is now $K_{00}$, while $K_{31}$ is now $K_{1,-1}$). Also let $I:[-\infty,\infty]^2\subset\mathbb{Z}^2\rightarrow\mathbb{R}$ be a scalar image array, with some padding (doesn't have to be zero). Note that $I$ is not necessarily zero-centered (i.e., the origin can be in the corner), but it can be. Its indexing structure determines the indexing of the output. Then convolution is written: $$ C(x,y) = (I\ast K)(x,y) = \sum_{\alpha=-\infty}^\infty \sum_{\beta=-\infty}^\infty I(x-\alpha, y-\beta) K(\alpha,\beta) $$ ok, so now, let's not zero-center $I$ (so it's indexing is consistent with yours) and compute $C_{22}$ with a $3\times 3$ kernel: \begin{align} C_{22} &= \sum_{\alpha=-1}^1\sum_{\beta=-1}^1 I(x-\alpha, y-\beta) K(\alpha,\beta) \\ &= I_{2+1,2+1} K_{-1,-1} + I_{2+1,2-0} K_{-1,0} + I_{2+1,2-1} K_{-1,1} \\ &\hspace{0.5in} + I_{2-0,2+1} K_{0,-1} + I_{2-0,2-0} K_{0,0} + I_{2-0,2-1} K_{0,1} \\ &\hspace{0.5in} + I_{2-1,2+1} K_{1,-1} + I_{2-1,2-0} K_{1,0} + I_{2-1,2-1} K_{1,1} \\ &= I_{3,3} K_{-1,-1} + I_{3,2} K_{-1,0} + I_{3,1} K_{-1,1} \\ &\hspace{0.5in} + I_{2,3} K_{0,-1} + I_{2,2} K_{0,0} + I_{2,1} K_{0,1} \\ &\hspace{0.5in} + I_{1,3} K_{1,-1} + I_{1,2} K_{1,0} + I_{1,1} K_{1,1} \\ \end{align} where we note that a $3\times 3$ kernel that is zero-centered (i.e., its origin is in the middle of the filter) has indices running from $-1$ to $1$. To reiterate, $-1$ is a valid index for $K$ (not padded) because we are zero-centered, but anything lower than that will just return zero.

What if the kernel is not zero-centered? Well, let's define a new non-zero-centered kernel for this example: $ F(i,j) := K(i-1,j-1) $, so that $K(a,b)=F(a+1,b+1)$. In other words, $$ \begin{bmatrix} F_{00} & F_{01} & F_{02} \\ F_{10} & F_{11} & F_{12} \\ F_{20} & F_{21} & F_{22} \end{bmatrix} = \begin{bmatrix} K_{-1,-1} & K_{-1,0} & K_{-1,1} \\ K_{0,-1} & K_{0,0} & K_{0,1} \\ K_{1,-1} & K_{1,0} & K_{1,1} \end{bmatrix} $$ If you substitute this into the expression above, you will see that it works just fine too. (Note you don't have to change $I$ at all.)

$\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 '19 at 10:06
  • $\begingroup$ @ShirishKulhari I've edited it now. Basically, if you want to sum from 1 (or 0) as the corner index, you have to use an additional indexing offset. It's easier to change the "origin" of the kernel instead. $\endgroup$ – user3658307 Jul 5 '19 at 10:54
  • $\begingroup$ Thank you so much for the clarity, I understand it perfectly now! $\endgroup$ – Shirish Kulhari Jul 5 '19 at 13:11
  • $\begingroup$ Related: math.stackexchange.com/questions/353712/… $\endgroup$ – user3658307 Jul 14 '19 at 19: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.