1
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 ! $\endgroup$ – PepperTiger Dec 31 '20 at 16:30
  • $\begingroup$ 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 ;) $\endgroup$ – Uskebasi Dec 31 '20 at 17:11

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.