Q13Digital Image Processing

The 2D DFT of an $M\times N$ image $f(x,y)$ is defined as $F(u,v)={\sum }_{x=0}^{M-1}{\sum }_{y=0}^{N-1}f(x,y)e^{-j2\pi (ux/M+vy/N)}$, transforming the image from the spatial domain to the frequency domain where $u,v$ represent spatial frequency.

• Separability: The 2D DFT kernel can be factored into a product of two 1D kernels, so the transform is computed by first applying a 1D DFT to each row and then a 1D DFT to each resulting column, drastically reducing computation compared to a direct 2D sum.
• Translation: Shifting $f(x,y)$ in the spatial domain multiplies $F(u,v)$ by a complex exponential phase factor but leaves $|F(u,v)|$ unchanged; conversely, multiplying $f(x,y)$ by an exponential shifts the frequency spectrum, which is used to center the spectrum for display.
• Periodicity and Conjugate Symmetry: The DFT and its inverse are periodic with periods $M$ and $N$. For real-valued images, $F(u,v)=F^{\ast }(-u,-v)$, meaning the magnitude spectrum is symmetric about the origin.
• Rotation: Rotating $f(x,y)$ by angle ${\theta }_0$ rotates $F(u,v)$ by the same angle.
• Distributivity and Scaling: The DFT is distributive over addition but not multiplication, and scaling the spatial variables inversely scales the frequency variables.
• Convolution Theorem: Spatial-domain convolution corresponds to point-wise multiplication in the frequency domain, $f(x,y)\ast h(x,y)\iff F(u,v)H(u,v)$, which is the mathematical basis for implementing spatial filters efficiently via FFT.

The convolution theorem property has the greatest practical importance: rather than sliding a spatial mask across every pixel, an equivalent filtering operation can be performed by transforming both the image and the filter kernel to the frequency domain via FFT, multiplying them point-wise, and taking the inverse FFT. For a large mask this frequency-domain approach is computationally cheaper than direct spatial convolution, since the FFT reduces complexity from $O(N^2)$ per pixel to $O(N\log N)$ overall, which is why frequency-domain filtering is preferred for large blur kernels or Gaussian smoothing over sizable neighborhoods.