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$

2 Answers 2

2
$\begingroup$

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:

Depiction of the 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):

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

$\endgroup$
7
  • $\begingroup$ So effectively what you're saying is, the summation indices are summed from $-k$ to $+k$ (i.e. the summation range is centered at $0$). And also both the image and kernel have an odd number of rows and columns, with the center element having coordinates $(0,0)$, so both the row and column indices are also centered at $0$ and range from something like $-m$ to $+m$. Is that correct? $\endgroup$ Jul 5, 2019 at 13:09
  • $\begingroup$ Not fully, the image has its own size, not necesarilly odd. However each patch of interest on the image is odd-sized, centered "in absolute coordinates" at $(x,y)$. The kernel only is applied "in a relative way" around the center pixel $\endgroup$ Jul 5, 2019 at 13:37
  • 1
    $\begingroup$ I think songho.ca/dsp/convolution/convolution2d_example.html is worth a read, with the zero extension option $\endgroup$ Jul 5, 2019 at 13:51
  • 1
    $\begingroup$ I see. So the image can have typical normal coordinates (i.e. $1$ to $m$ for rows and $1$ to $n$ for columns), BUT the kernel needs to have zero-centered coordinates. And thus the summation range also needs to be zero-centered. Hopefully I'm understanding this correctly? The reason I got so confused in the first place is because the convention that I described in the question has been used in a couple of references for convolutional neural networks that I'm reading. It's much more satisfactory to use the convention you described. $\endgroup$ Jul 5, 2019 at 14:00
  • $\begingroup$ For the first part, the image only need to be uniformly sampled. If your original indices are geographical locations, they don't have to be integers. For the second part, one can easily adapt the equation I gave to non-square, even/odd-sized kernels, just wanted to make notations as simple as possible for the understanding. As Yann LeCun alluded to in a signal/image conference (see the tweet), convolution is sometimes mundanely written $\endgroup$ Jul 5, 2019 at 14:12
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I have a follow-up doubt and have edited the question. Would be really grateful if you could clarify that! $\endgroup$ Jul 5, 2019 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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