Bicubic interpolation

[aluminumstudios]

I have a question that I'm hoping some programmers might be able to help me with.

I know purists don't like interpolation, and I always leaned towards the thought that fully calculated is cool.  However, given the processing power constraints that I have, I've opted to try interpolation.  My video will still be a result of mathematics, so I think I can live it with for now

Here is my situation ...  I want to enlarge an image by a small amount.  My software already does some math and for each point in the new, interpolated image, it gives me a floating point floatX, floatY value of the corresponding point in the old image.

If I take the value from round(floatX), round(floatY) in the old image, I am doing nearest neighbor interpolation.  This works but leaves sometimes noticeable lines in the image where pixels were duplicated to enlarge the image.

If I take the average of [ceil(floaty), floor(floatx)] & [ceil(floaty), ceil(floatx)] and [floor(floaty), floor(floatx)] & [floor(floaty), ceil(floatx)] I get an image that is bi-linearly interpolated (as is simply illustrated on this web pagehttp://polymathprogrammer.com/2008/10/06/image-rotation-with-bilinear-interpolation/)

I am only enlarging my image about 5%-10% however bi-linear looks a bit soft.  Can someone give me some pseudocode and help me interpolate a sharper frame given a floating point X and Y value that corresponds to a a point in a frame that I have in memory and am enlarging via interpolation?

I've read about bicubice interpolation taking more samples from around the point.  However, I'm not sure of the exact method and in my mind it seems that more points will give an even softer image (although I know that's not true by using bicubic interpolation in software like Photoshop.)

Any help is appreciated!

Will

[hobold]

Linear interpolation softens your images because it effectively turns a bright disk on a dark background (a flat pixel that covers some surface area) into an infinitesimally small point; namely into the tip of a triangle, with the triangle sides being the linearly interpolated ramps.

As an unscientific but quick fix, you can use S shaped curves rather than linear ramps. That way, the interpolated pixel doesn't turn into a pointed tip, but into a flatter, larger crest of a hill. A simple S curve over [0 .. 1] that smoothly interpolates from zero to one, with zero derivative on both ends, is the polynomial

f(x) = -2x^3 + 3x^2 = (-2x + 3)x^2

This is actually pretty bad as a filter, but might be good enough for a quick and dirty solution to the problem at hand.

[aluminumstudios]

Thanks for the reply.

I fundamentally understand what you are saying, but am a little thin on experience (or maybe just sleep) to understand exactly how to use the curve you've provided me with

Could give some quick pseudo-code please?

[hobold]

When doing linear interpolation, you usually have some fractional parameter t between zero and one that covers the gap between sample points. Let's call the values at those points A and B, so the linear ramp between them can be computed like this:

interpolated(t) = A + t*(B - A)

The above formula contains an invisible interpolation function

f(x) = x

like so:

interpolated(t) = A + f(t)*(B - A)

You just have to replace f with

f(x) = (-2x + 3)x^2

and that should do the trick.

[cKleinhuis]

an s curve is also produced by a simple f(x)=sin(x)

[Timeroot]

an s curve is also produced by a simple f(x)=sin(x)

... a "simple" trig function which is about 10 times slower than (3-2x)x^2, and doesn't even have a zero derivative at x=0.

Bicubic interpolation, if I understood your question correctly, is based on piecewise Bezier curves (or do you want cubic polynomials?). These take four consecutive points, and gives the curve between the center two. Two find the next curve section, you'll need the next part as well. If you have four points p0, p1, p2, and p3, then the curve between p1 and p2 is:

(1-t)^3*p0+3(1-t)^2*t*p1+3(1-t)*t^2*p2+t^3*p3

for each time point t, plug t into that function, and you'll get your "smooth" value.



.....



I reread your question, I think I totally misunderstood. I believe what you want is to take floaty-floor[floaty] and floatx-floor[floatx], and plug (1-them) into some curve like other people suggested. As hobold said, take the resulting values of the function, we'll say f(1-x) and f(1-y), and use the color f(1-x)*f(1-y)*[floor(floatx),floor(floaty)]+f(x)*f(1-y)*[ceil(floatx),floor(floaty)]+f(1-x)*f(y)... etc....

One important thing is to use an interpolation function that satisfies f(1-x)=1-f(x). In fact, I very much recommend you use f(x)=x. It doesn't soften things at all, and gives simple weighting based on how close the other pixels are. In this case, you have as your color:

xfrac=x-floor(x)
yfrac=y-floor(y)
color=(1-xfrac)*(1-yfrac)*Color(floor(x),floor(y))+xfrac*(1-yfrac)*Color(ceil(x),floor(y))+ .....

Good luck, I hope I didn't sound to crazy when I wrote this!

[aluminumstudios]

Thanks for the replies.  I need to do a little reading because I understand the concept of the role of the curves in determining the values, but how the math actually works isn't quite clear to me yet 

It's a starting point though.