Linear Interploation Algorithms

Hi,

I was wondering what is most fast and efficient intepolation algorithm that easily adaptable in a Spartan 3 and able to process more than 60 frames per seconds?

I have read a paper about an adaptive Newton interpolation algorithm that suppose to use less resources than the Bicubic and comparable with the image quality of the Bicubic.

The algorithm will be used to scale the output of a LCD driver IC that outputs 18 to 24 bits RGB and FPGA will scale the image less than 18 bits and use on a smaller LCD screen.

Any tips will be very helpful.

Regards P

Reply to
eziggurat
Loading thread data ...

If I had to do it I'd implement the method used by pnmscale. The results are great and would be very easy to implement with integer arithmetic. Source is in the netpbm package, google for it.

The method scales down or up and is accurate. Note that his implementation uses floats the last time I checked, but there is absolutely no reason to do this, integers work fine if you just do some breshenham type tweaks.

Even if you don't end up using this system, it's a worthwhile exercise working though the theory.

Here's some comments from pnmscale.c:

/* Here's how we think of the color mixing scaling operation:

First, I'll describe scaling in one dimension. Assume we have a one row image. A raster row is ordinarily a sequence of discrete pixels which have no width and no distance between them -- only a sequence. Instead, think of the raster row as a bunch of pixels 1 unit wide adjacent to each other. For example, we are going to scale a 100 pixel row to a 150 pixel row. Imagine placing the input row right above the output row and stretching it so it is the same size as the output row. It still contains 100 pixels, but they are 1.5 units wide each. Our goal is to make the output row look as much as possible like the input row, while observing that a pixel can be only one color.

Output Pixel 0 is completely covered by Input Pixel 0, so we make Output Pixel 0 the same color as Input Pixel 0. Output Pixel 1 is covered half by Input Pixel 0 and half by Input Pixel 1. So we make Output Pixel 1 a 50/50 mix of Input Pixels 0 and 1. If you stand back far enough, input and output will look the same.

This works for all scale factors, both scaling up and scaling down.

This program always stretches or squeezes the input row to be the same length as the output row; The output row's pixels are always 1 unit wide.

The same thing works in the vertical direction. We think of rows as stacked strips of 1 unit height. We conceptually stretch the image vertically first (same process as above, but in place of a single-color pixels, we have a vector of colors). Then we take each row this vertical stretching generates and stretch it horizontally. */

-Dave

--
David Ashley                http://www.xdr.com/dash
Embedded linux, device drivers, system architecture
Reply to
David Ashley

That is interesting, i will start with an interpolation algorithm next week ...

where can i find that paper about the adaptive Newton interpolation algorithm?

Thanks in advance,

Kind regards,

Y
Reply to
yttrium

Do You Mean:

formatting link
's_method

?

Aust> snipped-for-privacy@gmail.com wrote:

Reply to
Austin Lesea

If you are going to 'resize' to a different number of pixels, then make sure you do a lowpass _before_ the rescaling, to avoid aliasing. Here, on my site you can see the difference:

formatting link
I do not suggest you use fft and reverse fft, anyways that was a project that ended when DVD burners became available, and the math in rescaler-yuv is not correct.... not finished, purely experimental, will not be finished... But you will perhaps want the lowpass to avoid the aliasing effects.

As for less bit depth.. what is against dropping the lsb[s]?

Reply to
panteltje

The link is

formatting link
for the algorithm.

yttrium wrote:

Reply to
eziggurat

Ahh,

formatting link

Aust> The link is

formatting link

Reply to
Austin Lesea

A few comments to your web page:

  1. It is not uncommon that you get amplitudes after filtering that are higher than the original amplitude. That is no shortcoming of the implementation but inherent in the math. A square wave of amplitude 1 has a sine component of f with an amplitude way above 1. While you subtract energy from the signal the amplitude can rise.
  2. Most image resampling algorithms actually are FIR filters, most of these are low order low pass filters. Even linear interpolation is a low pass, albeit not a very good one. A perfekt low pass equivalent to your fft approach would be sin(x)/x interpolation which is computationally quite expensive but a lot faster than the FFT and gives exactly the same results.
  3. Scaling and filtering can folded and performed in one step. This is true for both approaches: FIR-filters and FFT.

Kolja Sulimma

Reply to
Kolja Sulimma

On a sunny day (Fri, 15 Sep 2006 00:27:10 +0200) it happened Kolja Sulimma wrote in :

Yes, I did ask about this long time ago in sci.math, because of 'ripples' in the output.

As I mentioned I used the FFT for other reasons, the main point is realizing that the normally used open source packages do NOT prevent aliasing, and you can fix that with a lowpass below half the new sample frequency before the resizing, you in fact 're-sample' the signal after all.

I would appreciate if you have a simple C or Verilog or whatever piece of code that I could look at.

It is a very old webpage, but some people may still be using 1/2 D CVD, and for those it would be nice to have a fast alias free resizer. CVD (China Video Disk) is widely spread in the east.

Regards Jan

Reply to
Jan Panteltje

formatting link

Thanks for both links ... i am looking for the best algorithm tradeoff for performance/quality/fpga implementation ...

so i found this site:

formatting link

I will need about 7*3*4 interpolations so it needs to be quite a efficient implementation for space ... that's why the linear intepolation seems the easiest but not the most exact ... that's why i'm looking into some other algo's as well ...

kind regards,

y
Reply to
yttrium

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.