3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ But how is it "creating information" for those zeros in spatial domain? Is sinc interpolation is being used in which every interpolated point is calculated through whole sequenc? $\endgroup$
    – user_3pij
    Sep 12, 2019 at 12:45
  • $\begingroup$ @Naeem: There is no new information, it's all in the DFT coefficients. They completely define a continuous band-limited periodic function from which you can take as many samples as you like. $\endgroup$
    – Matt L.
    Sep 12, 2019 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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