2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
0

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.