¿Existe una propiedad matemática que podría ayudar a "resumir" la información de ciertas áreas de la matriz?

Question

Tengo una matriz de

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

y me gustaría crear la matriz

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

donde cada elemento de B es la suma de sus células circundantes en $A$. Así que la primera entrada de $B$$2-1-3+8=6$. El $3\times 3$ de la matriz y de la suma del "radio" son una simplificación, la pregunta apunta a $m \times n$ matrices, junto con diferentes áreas rectangulares a ser medido.

¿Hay alguna propiedad matemática que podría ayudar a evitar tener que implementar algo a lo largo de las líneas de $$b_{kl}=\sum_{l-a}^{l+b}\sum_{k-c}^{k+d}a_{kl} ~~~\text{given that the entries exist}$$ ? Caso especial: las cosas serán más fáciles si las entradas sólo consistía en una cantidad fija de $0$$1$?

Answer 1

Su ejemplo es esencialmente una convolución de $2$-dim matriz de datos utilizando un $3 \times 3$ kernel.

Para realmente matriz grande y arbitrarias del kernel, uno puede utilizar la transformada de fourier discreta para acelerar el cálculo.

En el caso de que el kernel no es demasiado grande, rectangular y binarias ( he.de peso e $1$, si el interior de rectángulo, $0$ lo contrario), se puede utilizar el truco de la suma de la tabla para calcular la suma.

Dada cualquier matriz de datos $a_{xy}$, definir $$\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{ y }\quad \Delta_0(x,y) = \Delta(0,0;x,y)$$ Estas funciones satisfacen: $$\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} $$ Digamos que usted tiene un $N_1 \times N_2$ matriz de datos y desea contortos con un $M_1 \times M_2$ rectangular binario del kernel. Usted puede construir la suma de la tabla de $\Delta_0$ por la exploración a lo largo de las filas, almacenar el más reciente visto $M_2+1$ filas de $\Delta_0$ y calcular el $\Delta$ usando sumas de fila de la fila actual y la anterior $M_2+1$-ésima fila. De esta manera, usted puede calcular todas las $\Delta$ suma $O(N_1 \times N_2)$ uso de $O(N_1 \times M_2)$ memoria de trabajo.

Usted debe navegar a través de las preguntas marcadas con de convolución en la dsp.SE (procesamiento de la Señal) para ver si hay algunos de la biblioteca se puede utilizar.