# What do the variables in the cross-correlation formula mean?

I understand what cross-correlation does given a kernel and an input image, but the formula confuses me a little. Given here in Goodfellow's Deep Learning (page 329), I can't quite understand what $$m$$ and $$n$$ are. Are they the dimensions of the kernel along the height and width dimensions?

$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n)$$

So, for the input image $$I$$ and kernel $$K$$, we take the sum product of $$I*K$$, but what do the $$m$$ and $$n$$ represent? How is the input image $$I$$ indexed?

It takes a little bit of time to fully understand the 2D convolution/cross-correlation and to relate it to the usual diagrams of the convolution operation, so, before addressing your questions, let me first try to break the definition of the 2D cross-correlation down, from the left to right.

$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n) \label{1}\tag{1}$$

1. $$S$$ is the function that is the cross-correlation of the functions $$K$$ and $$I$$, so $$S(i, j)$$ is the cross-correlation of $$K$$ and $$I$$ at the pixels $$i$$ and $$j$$

2. The symbol $$*$$ in $$K*I$$ is the cross-correlation/convolution symbol, but sometimes the cross-correlation/convolution is also denoted as $$\circledast$$

3. $$K*I$$ is the function that results from the cross-correlation of $$K$$ and $$I$$, i.e. $$S$$, so $$(K*I)(i,j)$$ is the value of the function $$S$$ (the cross-correlation of $$K$$ and $$I$$) at the inputs (or pixels) $$i$$ and $$j$$. In other words, $$(K*I)(i,j)$$ is just another way of writing $$S(i,j)$$ that emphasizes that we took the cross-correlation of $$K$$ and $$I$$, but they are exactly the same thing.

4. The double summation $$\sum_m \sum_n$$ is because we are computing the 2D cross-correlation, i.e. over the $$x$$ and $$y$$ dimensions of the image and kernel. This is just the definition of the 2D cross-correlation.

5. The $$m$$ and $$n$$ are the indices of the summations, one across the $$x$$-axis and the other across the $$y$$-axis. Let $$m = x$$ and $$n = y$$, so we can rewrite equation \ref{1} as follows. $$S(i, j) =(K*I)(i, j) = \sum_x \sum_y I(i + x, j + y)K(x, y) \label{2}\tag{2}$$ Now, it should be clearer that we are indexing across the $$x$$ and $$y$$ dimensions.

6. Now, let me further restrict the range of the summations. Let's say from $$x=-1$$ to $$x=1$$ and from $$y=-1$$ to $$y=1$$, then we can rewrite equation \ref{2} as follows $$S(i, j) =(K*I)(i, j) = \sum_{x=-1}^1 \sum_{y=-1}^1 I(i + x, j + y)K(x, y) \label{3}\tag{3}$$.

7. Why do I want to do this? Let me explain why. Consider now the following kernel $$K$$ (which happens to be a Gaussian kernel) $$K = \begin{bmatrix}\ \ \color{blue}{\frac {1}{16}} &\ \ \frac {1}{8} &\ \ \frac {1}{16} \\\ \ \frac {1}{8} &\ \ \frac {1}{4} &\ \ \color{red}{ \frac {1}{8}} \\\ \ \frac {1}{16} &\ \ \frac {1}{8} &\ \ \frac {1}{16}\end{bmatrix}$$ Note that this is the output of the function $$K$$ or, more precisely, its support. Let's assume that $$\frac {1}{4}$$ is at the index/pixel $$(0, 0)$$. Then, for example, the top-left $$\color{blue}{\frac {1}{16}}$$ is at index/pixel $$(-1, -1)$$ and the middle-right $$\color{red}{ \frac {1}{8}}$$ at pixel $$(1, 0)$$

8. Now, consider any image $$I$$ represented as a 2D matrix (i.e. its support), with, for example, dimensions $$U \times V$$. For concreteness, let $$U = 5$$ and $$V=5$$. Moreover, the middle pixel of the image is at index $$(0, 0)$$, as for the kernel. Let's say the image is the following $$I = \begin{bmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & \color{green}{0} & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix}$$ So, $$\color{green}{0}$$ is at index/pixel $$(0,0)$$.

9. Now, let's say that $$i = 0$$ and $$j=0$$ in equation \ref{3}. This means that we compute the cross-correlation between $$I$$ and $$K$$ at the index $$(0, 0)$$, where, in the case of the image $$I$$, the value is $$\color{green}{0}$$.

10. With these settings, it should be clearer now that equation \ref{3} means that the cross-correlation between $$K$$ and $$I$$ at index/pixel $$i=0$$ and $$j=0$$ is a 2D dot (or scalar) product. If it is not clear, then let be take the $$3\times 3$$ submatrix of $$I$$ centered at $$(i, j) = (0, 0)$$ (below, $$(0, 0)^{3 \times 3}$$ is just the notation that I came up with to indicate that). $$I_{(0, 0)^{3 \times 3}} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & \color{green}{0} & 1 \\ 1 & 0 & 0 \end{bmatrix}$$ Then the cross-correlation in equation \ref{3} is just $$S(i, j) = S(0, 0) = (K * I)(0, 0) = \sum \begin{bmatrix} 1 \frac {1}{16} & 0 \frac {1}{8} & 1 \frac {1}{16} \\ 0 \frac {1}{8} & \color{green}{0} \frac {1}{4} & 1 \frac {1}{8} \\ 1 \frac {1}{16} & 0 \frac {1}{8} & 0 \frac {1}{16} \end{bmatrix},$$ where $$\sum$$ is a sum across all elements, i.e. \begin{align} S(0, 0) &= 1 \frac {1}{16} + 0 \frac {1}{8} + 1 \frac {1}{16} + 0 \frac {1}{8} + \color{green}{0} \frac {1}{4} + 1 \frac {1}{8} + 1 \frac {1}{16} + 0 \frac {1}{8} + 0 \frac {1}{16} \\ & = \frac {1}{16} + \frac {1}{16} + \frac {1}{8} + \frac {1}{16} \\ & = \frac {3}{16} + \frac {1}{8} \\ &= \frac {5}{16} \end{align}

Now, to answer your questions/concerns more directly.

Are they the dimensions of the kernel along the height and width dimensions?

No. They are the indices that determine the neighbourhood around $$i$$ and $$j$$ where you want to compute the cross-correlation.

So, for the input image $$I$$ and kernel $$K$$, we take the sum product of $$I*K$$

In this case, the symbol $$*$$ does not denote the product, but the cross-correlation. Maybe by "sum product" you meant the cross-correlation (or 2D dot product), but I'm not sure.

How is the input image $$I$$ indexed?

The input image is indexed with $$m$$ and $$n$$, but you start at $$i$$ and $$j$$, that's why you use the actual indices $$i+m$$ and $$j+n$$.