Discrete Time Interpolation:Waving the math wand - Rhea

Discrete Time Interpolation

Mathematically, sure. Realistically? Let's find out.

Introduction

My fascination with the concept of discrete time interpolation began, when I asked Prof. Boutin if a discrete time interpolator, can ideally make a low-resolution image, a high resolution one.

The answer was, yes. Ideally, it can.

The equations that led to the concept seemed impeccable and mathematically, it seemed to make perfect sense.

But essentially, all we are doing is:

adding zeros in between samples (the result of which looks horrible by the way)
Low pass filtering,

and Voila! hi-res image. Impossible right?

After 6 hours of MATLAB code, and processing the image of my dog "Milo"(shown below), countless times, I am proud to say, that it is "Almost Possible in the Real World"

Page Map

This page contains

- Application to Actual 1-D signal
- Application to an actual real-world image

Mathematical Basis

To put the math in a nutshell, so that we can get started with the cool stuff, let's consider the diagrams below:

This shows the basic schematic of an interpolator. D in the circle is how many zeros we fill between samples and the Low Pass Filter removes the extraneous copies of the signal beyond W/D shown in the output below.
Let's pretend we waved the math wand and got the frequency domain as below.

[Application to Actual 1-D signal]

Now, let's see if this can be applied to an actual example.
From the introduction, our main aim was to take a badly sampled signal(our friendly sine wave shown below) and make it "good" or sampled at a better resolution
According to the math, this whole process should give the same result,as if we were to take a "good" sampling of the original ct signal

So, let's see what happens with the insertion of zeros

Obviously, the signal now contains more samples, as we can see from the x-axis plot.
Also, the zeros cause the addition of "spikes" in the signal, because now the jumps between samples are higher
So, intuitively, we want to use an LPF (low pass filter) to "remove" these high frequency spikes.

Success!! High-Res Signal
The low pass filter added a few extraneous samples, for those amongst you who are suspicious as to why we have more samples. I used an FIR Parks Mc Clellen filter in MATLAB, and that usually does this.

Application to Real-World Image

Now for the coup de grâce: Working with an actual image

We know we can make 1-D signals work, but images are much more complex
So the way to test if upsampling works, and indeed makes images better is to have a sloppy image in the first place right?
Well,that is kinda hard for our megapixel-jaded generation.
In that case, let's create a low-res image by downsampling a good one
First, let's see the original

As we can see, it is an extremely high res-image with clear details
Now let's down-sample this puppy and see what happens

I downsampled by a factor of 10, so basically, since this was a 2-D matrix in matlab, I went along each row and column and threw out 10 samples after every sample. In other words, if my earlier samples were

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21] They are now [1 11 21]

Writing the double loop made my brain, and MATLAB nearly explode, but to see it finally work was amazing.

Coming back to picture quality, you can see how pixelated Milo's face now is.

- The question now is Can we get the original back?
- Let's find out by interpolating

Interpolation, as we did for the sine wave, involves padding the samples with zero.
Using the [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21] example

They are now [1 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 21] etc.

Let's see how that looks in the image.

As expected, putting a bunch of zeros(solid black) in the image can not really improve it. But it can definitely be improved by low pass filtering

I tried low pass filtering with various frequencies less than pi/d, and failed

The possible reasons could be:
- Not band limiting the decimated signal before downsampling
- Spectral Noise in the signal
- Wrong LPF cutoff frequencies
- Noise components in original sampling

- In any case, even though the LPF'd image looks horrible and makes you dizzy, I'll put it up to see.

Conclusion

- Interpolation is definitely possible for simple signals that have simple frequency spectra and well-defined band-limits
- For images, it is a bit more complicated. If it was possible to convert camera phone pics to hi-res ones, why would people buy $1000 5 MP cameras?
- That said, I am willing to discuss my code for the above,with anyone who is interested. Perhaps we can get a good upsampling reconstruction. Code:Discrete_Time_Interpolation

--Dhruv Lamba

Discrete Time Interpolation:Waving the math wand - Rhea

Contents