How can I represent the calculation in this image mathematically?

enter image description here

For example, with the discrete convolution (and Fourier Transform?),

$$(f * g)[n]\ \stackrel{\mathrm{def}}{=}\ \sum_{m=-\infty}^\infty f[m]\, g[n - m]$$

  • $\begingroup$ Not your exact question, but similar: dsp.stackexchange.com/a/7847/35 $\endgroup$
    – datageist
    Apr 7, 2013 at 5:29
  • 1
    $\begingroup$ What is your question? The operation in the movie is a convolution with a particular mask. You already state how this is typically written. The mask is your $g$. $\endgroup$ Apr 7, 2013 at 18:32
  • $\begingroup$ This operation is already $\mathcal{O}(N)$, where $N$ is the number of pixels (i.e. cells); its complexity can't be improved, because every pixel must be visited at least once. The FFT -- or any other Poisson solver -- could come in if you wanted to invert the operation, as the stencil is simply the classic $5$-point stencil for $-\Delta$. $\endgroup$
    – Ben
    Jun 7, 2013 at 16:31

1 Answer 1


From the computational point of view, each element of the final matrix (resulting image) is equal to a operation between the around elements in the initial matrix (input image) and the respective elements of the kernel, so:

$ final_{i,j} = \\ initial_{r(i-1),r(j-1)} OP kernel_{1,1} + initial_{r(i),r(j-1)} OP kernel_{2,1} + initial_{r(i+1),r(j-1)} OP kernel_{3,1} + \\ initial_{r(i-1),r(j)} OP kernel_{1,2} + initial_{r(i),r(j)} OP kernel_{2,2} + initial_{r(i+1),r(j)} OP kernel_{3,2} + \\ initial_{r(i-1),r(j+1)} OP kernel_{1,3} + initial_{r(i),r(j+1)} OP kernel_{2,3} + initial_{r(i+1),r(j+1)} OP kernel_{3,3} \\ $

where the $r(x)$ represents the integer division between the x and the matrix side.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.