How can I represent the calculation in this image mathematically?
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$
$\endgroup$
3
-
$\begingroup$ Not your exact question, but similar: dsp.stackexchange.com/a/7847/35 $\endgroup$– datageistApr 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$– Wolfgang BangerthApr 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$– BenJun 7, 2013 at 16:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
