Why zero padding the 2-d DFT interpolates images in spatial domain?

Question

I was applying different image interpolation techniques and I came know to about interpolation in frequency domain. In this technique we first take 2d DFT of an image, pad it with zeros and take the inverse DFT. The magnitude of inverse DFT gives interpolated image. It is working quite well!

Now my question is that how can it interpolate image in spatial domain when we are just padding zeros in frequency domain? How it constructs data points? And why only use zero padding?

Now I know about Shannon interpolation theorem (sinc interpolation) in which we can ideally reconstruct continuous signal from its discrete counterpart (if the sampling frequency is greater than Nyquist frequency). We can construct unknown values by sinc interpolation, but I can not understand how inverse DFT is constructing values for interpolated signal?

Answer 1

For the sake of simplicity, I'll explain the 1-D case; the 2-D case is completely analogous. Let $x[n]$ be a finite length sequence with $n\in[0,N-1]$. Its discrete Fourier transform (DFT) is

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N} kn}\tag{1}$$

The sequence $x[n]$ can be obtained from $X[k]$ via the inverse DFT (IDFT):

$$x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}kn}\tag{2}$$

Note that the sequences defined by $(1)$ and $(2)$ are periodic with period $N$. Let's use $\tilde{X}[k]$ to denote the periodic sequence of DFT coefficients. For odd $N$, $\tilde{X}[k]$ just equals (the periodic continuation of) $X[k]$. For even $N$, we split the coefficient $X[N/2]$ in two equal terms $\frac12 X[N/2]$, such that for even $N$, the periodic sequence $\tilde{X}[k]$ is defined as

$$\tilde{X}[k]=\\\big[\ldots ,\underbrace{X[0],X[1],\ldots,\frac12 X[N/2],\frac12 X[N/2],\ldots,X[N-1]}_{N+1\textrm{ elements}},\ldots\big]\tag{3}$$

With that definition, the period of $\tilde{X}[k]$ is always odd. Let's denote that odd period by $2K+1$. For odd $N$ we have $K=(N-1)/2$, and for even $N$ we get $K=N/2$.

Using $\tilde{X}[k]$ and $K$ as defined above, we can rewrite $(2)$ as

$$x[n]=\frac{1}{N}\sum_{k=-K}^{K}\tilde{X}[k]e^{j\frac{2\pi}{N}kn}\tag{4}$$

With these preparations we can now interpret the coefficients $\tilde{X}[k]$ as Fourier coefficients of a continuous periodic function $x_c(t)$ with period $NT_s$, where $T_s$ is an arbitrary sampling interval:

$$x_c(t)=\frac{1}{N}\sum_{k=-K}^{K}\tilde{X}[k]e^{j\frac{2\pi}{NT_s}kt}\tag{5}$$

The sequence $x[n]$ can be obtained by sampling $x_c(t)$:

$$x[n]=x_c(nT_s)\tag{6}$$

But we can also obtain other, more densely sampled sequences by sampling $x_c(t)$. We choose the new sampling interval such that the new sequence is also periodic with period $M>N$:

$$\hat{x}[m]=x_c\left(m\frac{NT_s}{M}\right)=\frac{1}{N}\sum_{k=-K}^{K}\tilde{X}[k]e^{j\frac{2\pi}{M}km}\tag{7}$$

The new length $M$ sequence $\hat{x}[m]$ can be interpreted as an interpolated version of the original length $N$ sequence $x[n]$.

Note that $(7)$ can be written as a length $M$ IDFT with a zero-padded sequence $\tilde{X}_0[k]$:

$$\begin{align}\hat{x}[m]&=\frac{M}{N}\left(\frac{1}{M}\sum_{k=0}^{M-1}\tilde{X}_0[k]e^{j\frac{2\pi}{M}km}\right)\\&=\frac{M}{N}\cdot \textrm{IDFT}_M\big\{\tilde{X}_0[k]\big\}[m]\tag{8}\end{align}$$

with

$$\tilde{X}_0[k]=\big[\tilde{X}[0],\ldots,\tilde{X}[K],\underbrace{0,\dots,0}_{M-2K-1\textrm{ zeros}},\tilde{X}[K+1],\ldots,\tilde{X}[2K]\big]\tag{9}$$

In terms of the original DFT coefficients $X[k]$, the zero-padded sequence $\tilde{X}_0[k]$ is given by

$$\tilde{X}_0[k]=\big[X[0],\ldots,X[(N-1)/2],\underbrace{0,\dots,0}_{M-N\textrm{ zeros}},\\\qquad X[(N+1)/2],\ldots,X[N-1]\big]\tag{10}$$

for odd $N$, and by

$$\tilde{X}_0[k]=\big[X[0],\ldots,\frac12 X[N/2],\underbrace{0,\dots,0}_{M-N-1\textrm{ zeros}},\\\qquad \frac12 X[N/2],\ldots,X[N-1]\big]\tag{11}$$

for even $N$.