4
$\begingroup$

Assume you have a grid as below:

enter image description here

The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the window should not cross the boundaries of the grid.)

For each such position I want to calculate the sum of the cells in the window. I'd like to be able to do this with different sizes of windows as well. More specifically, given some range for the possible widths and possible heights of windows, I want to calculate and store all the sums over the cells in the window, for all positions of the window, and for all possible width/height combinations.

As an example: if the possible widths are 2 and 3 and the possible heights are 4, 5 and 6, then there are 6 combinations: $2 \times 4$, $2 \times 5$, $2 \times 6$ $3 \times 4$, $3 \times 5$, $3 \times 6$ and for each such sliding window size, I want to store the sums over cells in the sliding window for all possible positions of the sliding window.

What would be an efficient way to do this?

Cheers

$\endgroup$
5
$\begingroup$

One possible way would be to store the sum of all the submatrices of the form $((0,0),(i,j))$. You can compute each of these sums in $O(1)$ time per entry (by using the previous entries).

If you then want to know the sum of the submatrix $((x,y),(i,j))$, you can compute this in $O(1)$ from the stored sums using inclusion-exclusion. If we let $S$ denote such a sum, then

$$S((x,y),(i,j))=S((0,0),(i,j))-S((0,0),(x,j))-S((0,0),(i,y))+S((0,0),(x,y))$$

$\endgroup$
  • $\begingroup$ This problem is covered in Computer Vision by the Viola-Jones algorithm used for face detection. There's a nice description of the algorithm on Wikipedia. $\endgroup$ – Photon Feb 18 '15 at 12:35
  • $\begingroup$ I ended up using this approach. Thank you. $\endgroup$ – fiftyeight Apr 6 '15 at 13:50

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.