I have a matrix

$$A= \begin{pmatrix} 2 & -1 & 4 \\ -3 & 8 & -5\\ 12 & -7 & 16 \end{pmatrix} $$

and I would like to create the matrix

$$B= \begin{pmatrix} 6 & 5 & 6 \\ 11 & 26 & 15\\ 10 & 21 & 12 \end{pmatrix} $$

where each entry of B is the sum of its surrounding cells in $A$. So the first entry of $B$ is $2-1-3+8=6$. The $3\times 3$ matrix and the summing "radius" are a simplification, the question aims at $m \times n$ matrices along with arbitrary rectangular areas to be measured.

Is there some mathematical property which could help avoid having to implement something along the lines of $$b_{kl}=\sum_{l-a}^{l+b}\sum_{k-c}^{k+d}a_{kl} ~~~\text{given that the entries exist}$$ ? Special case: would things be easier if the entries only consisted of a fixed amount of $0$ and $1$?

  • $\begingroup$ You are going to have to do a lot of adding up however you approach it. If $m\times n$ is large and adjacent rectangles have substantial overlap you could take advantage of that (by just calculating the difference). $\endgroup$
    – almagest
    Commented Jun 12, 2016 at 19:17
  • $\begingroup$ Why? Programming what? $\endgroup$
    – Will Jagy
    Commented Jun 12, 2016 at 21:04
  • $\begingroup$ @WillJagy Minesweeper and possible generalizations. $\endgroup$ Commented Jun 12, 2016 at 22:03

1 Answer 1


Your example is essentially a convolution of $2$-dim array of data using a $3 \times 3$ kernel.

For really large array and arbitrary kernel, one can use discrete fourier transform to speed up the computation.

In the case where the kernel is not too big, rectangular and binary ( i.e weight $1$ if inside rectangle, $0$ otherwise), one can use the trick of sum table to compute the sum.

Given any array of data $a_{xy}$, define $$\Delta(x_0,y_0;x_1,y_1) = \sum_{x = x_0}^{x_1} \sum_{y = y_0}^{y_1} a_{xy} \quad\text{ and }\quad \Delta_0(x,y) = \Delta(0,0;x,y)$$ These functions satisfy: $$\begin{align} \Delta(x_0,y_0;x_1,y_1) &= \Delta_0(x_1,y_1) - \Delta_0(x_0-1,y_1) - \Delta_0(x_1,y_0-1) + \Delta_0(x_0-1,y_0-1)\\ \Delta_0(x_0,y_0) &= \Delta_0(x_0,y_0-1) + \sum_{x=0}^{x_0} a_{xy_0} \end{align} $$ Let's say you have an $N_1 \times N_2$ array of data and you want to convolute it with a $M_1 \times M_2$ rectangular binary kernel. You can build the sum table $\Delta_0$ by scanning along the rows, storing the most recent seen $M_2+1$ rows of $\Delta_0$ and compute the $\Delta$ using row sums from current row and the previous $M_2+1$-th row. In this way, you can compute all the $\Delta$ sums in $O(N_1 \times N_2)$ steps using $O(N_1 \times M_2)$ working storage.

You should browse over the questions tagged with convolution on dsp.SE (Signal processing) to see whether there are some library you can use.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .