Indices in 2D Convolution Operations - Handle Out of Bounds Indices

Question

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.

Answer 1

As shown in your examples, you have used an odded-sized kernel. Those are very common in image processing. Plus, they can ease the visualization of what happens. If the kernel is $(2\kappa+1)\times (2\kappa+1)$, you can think of superimosing the center of the flipped kernel over each pixel, as known on the Matlab 2D convolution:

So the equation becomes:

$$ C(x,y) = \sum_{m =-\kappa}^{m =+\kappa} \sum_{n =-\kappa}^{n =+\kappa} I(x-m,y-n)K(m,n)$$

The center of the kernel at coordinates $(0,0)$ is aligned with the current pixel position $(x,y)$. This way, indices are always well-defined for the kernel. So, what happens to out-of-bound image indices?

Among the most common options, you can assume that:

• one invalid index makes the whole patch invalid (the final image will be smaller)
• each invalid-index pixel is "skipped", this is equivalent to setting the value to zero (the final image could be bigger)
• invalid-index pixel are replaced by other pixels values. The most common are forms of symmetry (like $I(-x,-y)=I(x,y)$, or $I(-x+1,-y+1)=I(x,y)$ depending on the starting indices), or periodicity $I(x+X,y+Y)=I(x,y)$, where $x$ and $Y$ are the dimensions of the image.

Some interesting links with step-to-step visualizations (especially the third one):

• 2d convolution (video)
• 2D convolution
• Example of 2D Convolution

In general, the size of output signal is getting bigger than input signal (Output Length = Input Length + Kernel Length - 1), but we compute only same area as input has been defined. Because we forced to pad zeros where inputs are not defined, such as x[-1,-1], the results around the edge cannot be accurate. Plus, the size of output is fixed as same as input size in most image processing

Answer 2

Answer to the first post

I guess that is pretty much dependent on the problem that you are dealing with. Boundaries are always a problem that needs extra care.

In most applications, it would be an option to set those values to zero (and handle normalization factors of the filter appropriately).

Other options would be to reflect the data, so that the index -1 becomes 1, -2 becomes 2, and so on. Alternatively, there can also be cases where it would make sense to assume that it is periodic, so the index -1 would become N, -2 would bekome N-1 etc.

Hints regarding your update and follow-up doubt

You are right, that does not look right. Honestly, I havn't had a closer look at the formula you provided. However, I wonder if they are correct. I doubt that, honestly. The sums over $m$ and $n$, respectively, are just going in a positive direction. Having said that, it becomes apparent that you won't get a proper result, eg for $C^\prime(1,1)$, since the indices of $I$ are always below 0. That does not look right. Instead of coming up with lots and lots of formula here, I would like to point you to two links:

Quite visual explaination of 2D convolution/filtering

The obligatory Wikipedia link ;)

Nice visualization of the process, yet with bad audio

I like to think about the process in a rather visual way, as described in the first link. In my mind, I place the middle point of the filter ($K$) on the pixel I would like to evaluate. The other filter entries are then over the adjacent image pixels. Everything outside the original filter dimension is zero. Then you multiply this "extended" filter pixelwise with the image, and sum all up. That is the filter value at the given $(x, y)$ coordinate. You then move the filter's mid point by one pixel position and do the same thing again. Repeat this process until you have covered the full input image. See link #3