Answers.Body: <p>You can think about the problem in the following way (without padding, as the padding case is a simple extension of base case with <span class="math-container">$\tilde{W}:=W + 2P$</span>).<br />
  You want to know how many windows are necessary to cover an image of size <span class="math-container">$W$</span>, given a window of size <span class="math-container">$K$</span> and stride <span class="math-container">$S$</span>. So your image is a vector with indices <span class="math-container">$1, 2\dots, W$</span>; as you put the first window on the image, the window will cover the indices from <span class="math-container">$1$</span> to <span class="math-container">$K$</span>. As we apply stride (meaning that we translate the window), we will  get a sequence considering the last covered index. The first element of this sequence is <span class="math-container">$i_1=K$</span>, where the <span class="math-container">$1$</span> indexing <span class="math-container">$i$</span> is not the number of times we apply stride but the number of covering windows we have. So in this first case applying no stride and we have 1 covering window. Applying stride once to our window, the window will cover the indices form <span class="math-container">$S$</span> to <span class="math-container">$K+S$</span>, so <span class="math-container">$i_2=K+(2 -1 )S$</span>. In general you get <span class="math-container">$i_n=K+(n-1)S$</span>.<br />
  Now, if we can exactly cover <span class="math-container">$W$</span> then there is a number <span class="math-container">$N$</span> such that <span class="math-container">$i_N=W$</span>. This means <span class="math-container">$$K+(N-1)S=W,$$</span> which rearranging gives <span class="math-container">$$N=\frac{W-K}{S} + 1.$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T16:30:29.717Z
Answers.Text: Thanks a lot for the answer, I guess I've been taking this problem in the wrong way from the begining. Your explanation makes a lot of sense !
Answers.UserDisplayName: PepperTiger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T17:11:12.247Z
Answers.Text: You are welcome @PepperTiger! I tried the same approach (induction + number of overlaps) the first time but I didn't get that far. This way is much cleaner and simpler ;)
Answers.UserDisplayName: Uskebasi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T16:13:03.287Z
Answers.LastActivityDate: 2020-12-31T16:13:03.287Z
Answers.UserDisplayName: Uskebasi
Body: <p>As I've been dabbling into the sliding window concept, I stumbled on a question that asked me to find the number of windows needed on a 1D image of <span class="math-container">$W$</span> size, knowing the window size <span class="math-container">$K$</span> and the stride <span class="math-container">$S$</span>.</p>
  <p>As much as I tried, I couldn't find a formula by myself (the closest I got was this one : <span class="math-container">$N=\frac{W + x(K-S)}{K}$</span> where <span class="math-container">$x$</span> was the number of overlapping rectangle zones, which seemed to be <span class="math-container">$x=N-1$</span> but the reccurence wasn't what I was looking for and it could be wrong as I was reasoning through induction).</p>
  <p>I find the right formula on Internet at last (this one : <span class="math-container">$N=\frac{W-K+2P}{S}+1$</span> with <span class="math-container">$P$</span> the padding but my problem didn't needed one) but I can't find the proof of it.</p>
  <p>Is there any place where I could find the proof ?</p>
  
Tags: <neural-networks><convolutional-neural-networks>
Title: Output volume proof for convolutional neural network
UserDisplayName: PepperTiger
ThreadText: # Output volume proof for convolutional neural network
  
  (Asked by: username_0 on 2020-12-31)
  
  As I've been dabbling into the sliding window concept, I stumbled on a question that asked me to find the number of windows needed on a 1D image of $W$ size, knowing the window size $K$ and the stride $S$.
  
  As much as I tried, I couldn't find a formula by myself (the closest I got was this one : $N=\frac{W + x(K-S)}{K}$ where $x$ was the number of overlapping rectangle zones, which seemed to be $x=N-1$ but the reccurence wasn't what I was looking for and it could be wrong as I was reasoning through induction).
  
  I find the right formula on Internet at last (this one : $N=\frac{W-K+2P}{S}+1$ with $P$ the padding but my problem didn't needed one) but I can't find the proof of it.
  
  Is there any place where I could find the proof ?
  
  **Tags:** neural-networks, convolutional-neural-networks
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-31. Score: 2 | Accepted answer
  
  You can think about the problem in the following way (without padding, as the padding case is a simple extension of base case with $\tilde{W}:=W + 2P$).  
  You want to know how many windows are necessary to cover an image of size $W$, given a window of size $K$ and stride $S$. So your image is a vector with indices $1, 2\dots, W$; as you put the first window on the image, the window will cover the indices from $1$ to $K$. As we apply stride (meaning that we translate the window), we will get a sequence considering the last covered index. The first element of this sequence is $i\_1=K$, where the $1$ indexing $i$ is not the number of times we apply stride but the number of covering windows we have. So in this first case applying no stride and we have 1 covering window. Applying stride once to our window, the window will cover the indices form $S$ to $K+S$, so $i\_2=K+(2 -1 )S$. In general you get $i\_n=K+(n-1)S$.  
  Now, if we can exactly cover $W$ then there is a number $N$ such that $i\_N=W$. This means $$K+(N-1)S=W,$$ which rearranging gives $$N=\frac{W-K}{S} + 1.$$
  
  > **Comments:**
  > **username_0**: Thanks a lot for the answer, I guess I've been taking this problem in the wrong way from the begining. Your explanation makes a lot of sense !  
  > **username_1**: You are welcome @PepperTiger! I tried the same approach (induction + number of overlaps) the first time but I didn't get that far. This way is much cleaner and simpler ;)  
  
  ---
  
  