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" Milo.jpg



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: Slide1.jpg

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

Slide2.jpg


[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

Sin bad.jpg

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

Sin up.jpg

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

Sin good.jpg

  • 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

Milo original.jpg

  • 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

Milo downsampled.jpg

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

Milo up.jpg 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.

Milo final.jpg

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

Further Reading


**Learning and Failing is better than no Learning at all.--"Lisa Simpson"

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett