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$

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .