Output volume proof for convolutional neural network

Question

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 ?

Answer 1

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