Is there a mathematical property which could help "sum up" information from certain matrix areas?

Question

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

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.