Corresponding frequency domain filter of spatial domain filter in image processing?

Question

My question is: Suppose that we have low pass spatial domain filter that averages 4-connected neighbors of that pixel and it doesn't consider its pixel in averaging. Find its corresponding filter in frequency domain and show that it is a low pass filter.

I know that I must take forward Fourier transform from spatial domain filter and its output is frequency domain filter, but I don't have any idea what is spatial filter is? I think that it is $w(x,y)$ such that $-1 \le x \le 1 $ and $-1 \le y \le 1$ and $w(-1,0) = w(0,-1) = w(0,1) = w(1,0) = 1$ and $w(-1,-1) = w(0,0) = w(1,-1) = w(-1,1) = w(1,1) = 0$ but I don't know how to take Fourier transform from this?

How do I take the Fourier transform of my 3×3 filter kernel?

Answer 1

So, the $M\times N$-DFT is very well-defined to be (aside from the usual ambiguity about the factor up front)

$$ X[k,l] = \frac{1}{\sqrt{MN}}\sum_{n=0}^{N-1} \left(\sum_{m=0}^{M-1}x[m,n]\cdot e^{-jmk\frac{2\pi}{M}}\right)e^{-jnl\frac{2\pi}{N}} $$

In your $M=N=3$ case, that becomes

$$ X[k,l] = \frac{1}{3}\sum_{n=0}^{2} \left(\sum_{m=0}^{2}x[m,n]\cdot e^{-jmk\frac{2\pi}{3}}\right)e^{-jnl\frac{2\pi}{3}} \tag1 $$

Furthermore,

$$ x = \begin{bmatrix} 0 & 1& 0 \\ 1& 0 & 1\\ 0 & 1&0 \\ \end{bmatrix} $$

so that all there's a lot of zeros.

Simply expand the sum from $(1)$, filling in the values of $x$.

$$\begin{array} \,3X[k,l]&=& &\left(e^{-jk\frac{2\pi}3}\right)e^{j0} & \text{first row}\\ && +& \left(e^{-j0}+e^{-jk\frac{4\pi}3}\right)e^{-jl\frac{2\pi}3}& \text{second row}\\ &&+ &\left(e^{-jk\frac{2\pi}3}\right)e^{-jl\frac{4\pi}3}&\text{third row}\\ &=&&e^{-jk\frac{2\pi}3}\\ &&+&e^{-jl\frac{2\pi}3} + e^{-j\frac{2\pi}3\left(l-2k\right)}\\ &&+&e^{-j\frac{2\pi}3\left(k-2l\right)} \end{array}$$

So,

$$X[k,l]=\frac13\left(e^{-jk\frac{2\pi}3}+e^{-jl\frac{2\pi}3} + e^{-j\frac{2\pi}3\left(l-2k\right)}+e^{-j\frac{2\pi}3\left(k-2l\right)}\right)$$

Set in all values for $k$ and $l$, and get your $3\times3$ DFT output .