0
$\begingroup$

Given the 2D DFT of an image i.e. a NxM matrix of complex numbers, with some missing lines (or even partial lines), considering we have zeros in the missing positions.

Any suggestions for an algorithm to "interpolate"/reconstruct the missing values?

$\endgroup$
  • $\begingroup$ are the values missing in the original image or in the DFT? $\endgroup$ – Marcus Müller Aug 14 at 15:33
  • $\begingroup$ In the DFT, the idea here is really to consider we only have a corrupted DFT matrix and we want to rebuild in DFT in order to then go to image space with inverse DFT later $\endgroup$ – Machupicchu Aug 14 at 15:51
  • $\begingroup$ What's the use case for this? because I don't see rows of DFT matrices getting corrupted often, and the easiest fix for that would probably be something that you would do in spatial domain (windowing, to be concrete), just as you would window the frequency domain if you were missing spatial rows. A DFT is about the "cheapest" operation you can do on an image, so it's usually not something you avoid first. $\endgroup$ – Marcus Müller Aug 14 at 17:04
  • $\begingroup$ well for example in MRI, maybe you don't know it, but the image is acquired in the Fourier domain, you have to ifft2 it to recover the actual image $\endgroup$ – Machupicchu Aug 14 at 17:25
  • $\begingroup$ then you'd interpolate it from the neighboring rows $\endgroup$ – Marcus Müller Aug 14 at 17:40
1
$\begingroup$

For simplicity I will show an approach Id' use on 1D signal (A row of real world image).
You will be able to extend it and I will add few remarks on how you can even gain from having 2D data.

The general idea is as sketched in Estimate the Discrete Fourier Series of a Signal with Missing Samples. The trick here is to exploit prior information.
In our case we'll use the smoothness prior of images by utilizing the Total Variation prior.

Problem Formulation

So let't define our problem. We have the data to estimate $ x \in \mathbb{R}^{n} $ and the DFT samples $ y \in \mathbb{C}^{m} $ where $ n > m $. Let $ F \in \mathbb{C}^{m \times n} $ be the partial DFT matrix such that $ F x = y $, namely it transforms the to be estimated data into the given DFT samples.

This allows us to write the optimization problem as following:

$$ \arg \min_{x} \frac{1}{2} {\left\| F x - y \right\|}_{2}^{2} + \lambda {\left\| D x \right\|}_{1} $$

Where $ D \in \mathbb{R}^{\left( n - 1 \right) \times n} $ is the Forward Finite Differences Operator (Numerical approximation of the Derivative).

By intuition, we're looking for a vector $ x $ which its partial DFT is similar to $ y $ and it obeys local smoothness as real world images do. The parameter $ \lambda $ balances between the two.

Solving this is pretty easy using Proximal Gradient Method or ADMM. But even straight forward Sub Gradient Descent Method will do the trick here with the Gradient given by:

$$ \frac{\partial}{\partial x} \frac{1}{2} {\left\| F x - y \right\|}_{2}^{2} + \lambda {\left\| D x \right\|}_{1} = {F}^{H} \left( F x - y \right) + \lambda {D}^{T} \operatorname{sign} \left( D x \right) $$

Results

I used the Lena image and chose the 130th row:

enter image description here

I removed 3 random from the DFT of the row and estimated the row using that as a starting point.

The estimation after 1000 iterations:

enter image description here

The RMSE is about the value of 1 pixel Namely it is usually go unnoticed.

MATLAB Code

The MATLAB code is available at my StackExchange Signal Processing Q60119 GitHub Repository.

Pay attention one need to handle the fact the data to be estimated is Real while operations create Complex data. I used abs() in MATLAB to generate real data from the complex data.

How to Extend to 2D Data

Well, you could just do as above per row of the image. but since you have 2D information you should use that for better results.
The trick is to apply the Total Variation prior in both directions.

By the way, on noisy image, if you don't want to apply any smoothing solve this as Least Squares problem (Just do $ \hat{x} = {\left( {F}^{H} F \right)}^{-1} {F}^{H} y $).

$\endgroup$
  • $\begingroup$ Great answer, thanks. Unfortunately the line to your GitHub seems to be broken? (I get a HTTP 404 error) $\endgroup$ – Machupicchu Aug 14 at 19:15
  • $\begingroup$ Oh your last equation reminds me of the Moore-Penrose pseudo inverse, right? I have used the M-P pseudo inv to find solutions to overdetermined sys of equations or find the parameters of a linear regression problem if i recall correclty. $\endgroup$ – Machupicchu Aug 14 at 19:19
  • $\begingroup$ I guess for some reason my commit didn't work. I will push it within few hours when I'm back to that computer. Indeed the last equation is the Pseudo Inverse which is a specific case of the Moore Penrose. $\endgroup$ – Royi Aug 15 at 2:10
  • $\begingroup$ Thanks, that would be great! $\endgroup$ – Machupicchu Aug 15 at 9:10
  • $\begingroup$ It should work now. $\endgroup$ – Royi Aug 15 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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