Answers.Body: <p>It takes a little bit of time to fully understand the 2D <a href="https://ai.stackexchange.com/q/21999/2444">convolution/cross-correlation</a> 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.</p>
  <p><span class="math-container">$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n) \label{1}\tag{1}$$</span></p>
  <ol>
  <li><p><span class="math-container">$S$</span> is the function that is the cross-correlation of the functions <span class="math-container">$K$</span> and <span class="math-container">$I$</span>, so <span class="math-container">$S(i, j)$</span> is the cross-correlation of <span class="math-container">$K$</span> and <span class="math-container">$I$</span> at the pixels <span class="math-container">$i$</span> and <span class="math-container">$j$</span></p>
  </li>
  <li><p>The symbol <span class="math-container">$*$</span> in <span class="math-container">$K*I$</span> is the <a href="https://en.wikipedia.org/wiki/List_of_mathematical_symbols_by_subject" rel="nofollow noreferrer">cross-correlation/convolution symbol</a>, but sometimes the cross-correlation/convolution is also denoted as <span class="math-container">$\circledast$</span></p>
  </li>
  <li><p><span class="math-container">$K*I$</span> is the function that results from the cross-correlation of <span class="math-container">$K$</span> and <span class="math-container">$I$</span>, i.e. <span class="math-container">$S$</span>, so <span class="math-container">$(K*I)(i,j)$</span> is the value of the function <span class="math-container">$S$</span> (the cross-correlation of <span class="math-container">$K$</span> and <span class="math-container">$I$</span>) at the inputs (or pixels) <span class="math-container">$i$</span> and <span class="math-container">$j$</span>. In other words, <span class="math-container">$(K*I)(i,j)$</span> is just another way of writing <span class="math-container">$S(i,j)$</span> that emphasizes that we took the cross-correlation of <span class="math-container">$K$</span> and <span class="math-container">$I$</span>, but they are exactly the same thing.</p>
  </li>
  <li><p>The double summation <span class="math-container">$\sum_m \sum_n$</span> is because we are computing the <strong>2D</strong> cross-correlation, i.e. over the <span class="math-container">$x$</span> and <span class="math-container">$y$</span> dimensions of the image and kernel. This is just the definition of the 2D cross-correlation.</p>
  </li>
  <li><p>The <span class="math-container">$m$</span> and <span class="math-container">$n$</span> are the indices of the summations, one across the <span class="math-container">$x$</span>-axis and the other across the <span class="math-container">$y$</span>-axis. Let <span class="math-container">$m = x$</span> and <span class="math-container">$n = y$</span>, so we can rewrite equation \ref{1} as follows.
  <span class="math-container">$$S(i, j) =(K*I)(i, j) = \sum_x \sum_y I(i + x, j + y)K(x, y) \label{2}\tag{2}$$</span>
  Now, it should be clearer that we are indexing across the <span class="math-container">$x$</span> and <span class="math-container">$y$</span> dimensions.</p>
  </li>
  <li><p>Now, let me further restrict the range of the summations. Let's say from <span class="math-container">$x=-1$</span> to <span class="math-container">$x=1$</span> and from <span class="math-container">$y=-1$</span> to <span class="math-container">$y=1$</span>, then we can rewrite equation \ref{2} as follows
  <span class="math-container">$$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}$$</span>.</p>
  </li>
  <li><p>Why do I want to do this? Let me explain why. Consider now the following kernel <span class="math-container">$K$</span> (which happens to be a <a href="https://en.wikipedia.org/wiki/Kernel_(image_processing)" rel="nofollow noreferrer">Gaussian kernel</a>)
  <span class="math-container">$$
  K = \begin{bmatrix}\ \ \color{blue}{\frac {1}{16}} &amp;\ \ \frac {1}{8} &amp;\ \ \frac {1}{16} \\\ \ \frac {1}{8} &amp;\ \ \frac {1}{4} &amp;\ \ \color{red}{ \frac {1}{8}} \\\ \ \frac {1}{16} &amp;\ \ \frac {1}{8} &amp;\ \ \frac {1}{16}\end{bmatrix}
  $$</span>
  Note that this is the output of the function <span class="math-container">$K$</span> or, more precisely, its <a href="https://encyclopediaofmath.org/wiki/Support_of_a_function" rel="nofollow noreferrer">support</a>. Let's assume that <span class="math-container">$\frac {1}{4}$</span> is at the index/pixel <span class="math-container">$(0, 0)$</span>. Then, for example, the top-left <span class="math-container">$ \color{blue}{\frac {1}{16}} $</span> is at index/pixel <span class="math-container">$(-1, -1)$</span> and the middle-right <span class="math-container">$\color{red}{ \frac {1}{8}}$</span> at pixel <span class="math-container">$(1, 0)$</span></p>
  </li>
  <li><p>Now, consider any image <span class="math-container">$I$</span> represented as a 2D matrix (i.e. its support), with, for example, dimensions <span class="math-container">$U \times V$</span>. For concreteness, let <span class="math-container">$U = 5$</span> and <span class="math-container">$V=5$</span>. Moreover, the middle pixel of the image is at index <span class="math-container">$(0, 0)$</span>, as for the kernel. Let's say the image is the following
  <span class="math-container">$$
  I = 
  \begin{bmatrix}
  0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\
  1 &amp; 1 &amp; 0 &amp; 1 &amp; 1 \\
  0 &amp; 0 &amp; \color{green}{0} &amp; 1 &amp; 1 \\
  1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
  0 &amp; 1 &amp; 0 &amp; 1 &amp; 1 \\
  \end{bmatrix}
  $$</span>
  So, <span class="math-container">$\color{green}{0}$</span> is at index/pixel <span class="math-container">$(0,0)$</span>.</p>
  </li>
  <li><p>Now, let's say that <span class="math-container">$i = 0$</span> and <span class="math-container">$j=0$</span> in equation \ref{3}. This means that we compute the cross-correlation between <span class="math-container">$I$</span> and <span class="math-container">$K$</span> at the index <span class="math-container">$(0, 0)$</span>, where, in the case of the image <span class="math-container">$I$</span>, the value is <span class="math-container">$\color{green}{0}$</span>.</p>
  </li>
  <li><p>With these settings, it should be clearer now that equation \ref{3} means that the cross-correlation between <span class="math-container">$K$</span> and <span class="math-container">$I$</span> at index/pixel <span class="math-container">$i=0$</span> and <span class="math-container">$j=0$</span> is a 2D dot (or scalar) product. If it is not clear, then let be take the <span class="math-container">$3\times 3$</span> submatrix of <span class="math-container">$I$</span> centered at <span class="math-container">$(i, j) = (0, 0)$</span> (below, <span class="math-container">$(0, 0)^{3 \times 3}$</span> is just the notation that I came up with to indicate that).
  <span class="math-container">$$
  I_{(0, 0)^{3 \times 3}} = 
  \begin{bmatrix}
  1 &amp; 0 &amp; 1 \\
  0 &amp; \color{green}{0} &amp; 1  \\
  1 &amp; 0 &amp; 0 
  \end{bmatrix}
  $$</span>
  Then the cross-correlation in equation \ref{3} is just
  <span class="math-container">$$
  S(i, j) = S(0, 0) = (K * I)(0, 0) = 
  \sum
  \begin{bmatrix}
  1 \frac {1}{16} &amp; 0 \frac {1}{8} &amp; 1 \frac {1}{16} \\
  0 \frac {1}{8} &amp; \color{green}{0} \frac {1}{4}  &amp; 1 \frac {1}{8}  \\
  1 \frac {1}{16} &amp; 0 \frac {1}{8} &amp; 0 \frac {1}{16} 
  \end{bmatrix},
  $$</span>
  where <span class="math-container">$\sum$</span> is a sum across all elements, i.e.
  <span class="math-container">\begin{align}
  S(0, 0) 
  &amp;= 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}  \\
  &amp; = \frac {1}{16} + \frac {1}{16} + \frac {1}{8} + \frac {1}{16} \\
  &amp; = \frac {3}{16} + \frac {1}{8} \\
  &amp;= \frac {5}{16} 
  \end{align}</span></p>
  </li>
  </ol>
  <p>Now, to answer your questions/concerns more directly.</p>
  <blockquote>
  <p>Are they the dimensions of the kernel along the height and width dimensions?</p>
  </blockquote>
  <p>No. They are the indices that determine the neighbourhood around <span class="math-container">$i$</span> and <span class="math-container">$j$</span> where you want to compute the cross-correlation.</p>
  <blockquote>
  <p>So, for the input image <span class="math-container">$I$</span> and kernel <span class="math-container">$K$</span>, we take the sum product of <span class="math-container">$I*K$</span></p>
  </blockquote>
  <p>In this case, the symbol <span class="math-container">$*$</span> does <strong>not</strong> denote the product, but the cross-correlation. Maybe by &quot;sum product&quot; you meant the cross-correlation (or 2D dot product), but I'm not sure.</p>
  <blockquote>
  <p>How is the input image <span class="math-container">$I$</span> indexed?</p>
  </blockquote>
  <p>The input image is indexed with <span class="math-container">$m$</span> and <span class="math-container">$n$</span>, but you start at <span class="math-container">$i$</span> and <span class="math-container">$j$</span>, that's why you use the actual indices <span class="math-container">$i+m$</span> and <span class="math-container">$j+n$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-23T13:22:28.920Z
Answers.LastActivityDate: 2021-01-23T13:36:24.733Z
Answers.LastEditDate: 2021-01-23T13:36:24.733Z
Answers.UserDisplayName: nbro
Body: <p>I understand what cross-correlation does given a kernel and an input image, but the formula confuses me a little. Given here in <a href="https://www.deeplearningbook.org/contents/convnets.html" rel="nofollow noreferrer">Goodfellow's Deep Learning</a> (page 329), I can't quite understand what <span class="math-container">$m$</span> and <span class="math-container">$n$</span> are. Are they the dimensions of the kernel along the height and width dimensions?</p>
  <p><span class="math-container">$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n)$$</span></p>
  <p>So, for the input image <span class="math-container">$I$</span> and kernel <span class="math-container">$K$</span>, we take the sum product of <span class="math-container">$I*K$</span>, but what do the <span class="math-container">$m$</span> and <span class="math-container">$n$</span> represent? How is the input image <span class="math-container">$I$</span> indexed?</p>
  
Tags: <deep-learning><convolutional-neural-networks><convolution><notation><cross-correlation>
Title: What do the variables in the cross-correlation formula mean?
UserDisplayName: InvestingScientist
ThreadText: # What do the variables in the cross-correlation formula mean?
  
  (Asked by: username_0 on 2021-01-23)
  
  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](https://www.deeplearningbook.org/contents/convnets.html) (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?
  
  **Tags:** deep-learning, convolutional-neural-networks, convolution, notation, cross-correlation
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-01-23. Score: 2 | Accepted answer
  
  It takes a little bit of time to fully understand the 2D [convolution/cross-correlation](https://ai.stackexchange.com/q/21999/2444) 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](https://en.wikipedia.org/wiki/List_of_mathematical_symbols_by_subject), 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](https://en.wikipedia.org/wiki/Kernel_(image_processing)))
     $$
     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](https://encyclopediaofmath.org/wiki/Support_of_a_function). 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$.
  
  
  ---
  
  