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 '13 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 '13 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 '13 at 16:31

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, privacy policy and cookie policy

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