Bilinear interpolation to enlarge bitmap images

Question

I'm a student, and I've been tasked to optimize bilinear interpolation of images by invoking parallelism from CUDA.

The image is given as a 24-bit .bmp format. I already have a reader for the .bmp and have stored the pixels in an array.

Now I need to perform bilinear interpolation on the array. I do not understand the math behind it (even after going through the wiki article and other Google results). Because of this I'm unable to come up with an algorithm.

Is there anyone who can help me with a link to an existing bilinear interpolation algorithm on a 1-D array? Or perhaps link to an open source image processing library that utilizes bilinear and bicubic interpolation for scaling images?

Solution 1

The easiest way to understand bilinear interpolation is to understand linear interpolation in 1D.

This first figure should give you flashbacks to middle school math. Given some location a at which we want to know f(a), we take the neighboring "known" values and fit a line between them.

So we just used the old middle-school equations y=mx+b and y-y1=m(x-x1). Nothing fancy.

We basically carry over this concept to 2-D in order to get bilinear interpolation. We can attack the problem of finding f(a,b) for any a,b by doing three interpolations. Study the next figure carefully. Don't get intimidated by all the labels. It is actually pretty simple.

For a bilinear interpolation, we again using the neighboring points. Now there are four of them, since we are in 2D. The trick is to attack the problem one dimension at a time.

We project our (a,b) to the sides and first compute two (one dimensional!) interpolating lines.

• f(a,y_j) where y_j is held constant
• f(a,y_j+1) where y_j+1 is held constant.

Now there is just one last step. You take the two points you calculated, f(a,y_j) and f(a,y_j+1), and fit a line between them. That's the blue one going left to right in the diagram, passing through f(a,b). Interpolating along this last line gives you the final answer.

I'll leave the math for the 2-D case for you. It's not hard if you work from the diagram. And going through it yourself will help you really learn what's going on.

One last little note, it doesn't matter which sides you pick for the first two interpolations. You could have picked the top and bottom, and then done the third interpolation line between those two instead. The answer would have been the same.

Solution 2

When you enlarge an image by scaling the sides by an integral factor, you may treat the result as the original image with extra pixels inserted between the original pixels.

See the pictures in IMAGE RESIZE EXAMPLE.

The f(x,y)=... formula in this article in Wikipedia gives you a method to compute the color f of an inserted pixel:

For every inserted pixel you combine the colors of the 4 original pixels (Q11, Q12, Q21, Q22) surrounding it. The combination depends on the distance between the inserted pixel and the surrounding original pixels, the closer it is to one of them, the closer their colors are:

The original pixels are shown as red. The inserted pixel is shown as green.

That's the idea.

If you scale the sides by a non-integral factor, the formulas still hold, but now you need to recalculate all pixel colors as you can't just take the original pixels and simply insert extra pixels between them.

Solution 3

Don't get hung up on the fact that 2D arrays in C are really 1D arrays. It's an implementation detail. Mathematically, you'll still need to think in terms of 2D arrays.

Think about linear interpolation on a 1D array. You know the value at 0, 1, 2, 3, ... Now suppose I ask you for the value at 1.4. You'd give me a weighted mix of the values at 1 and 2: (1 - 0.4)*A[1] + 0.4*A[2]. Simple, right?

Now you need to extend to 2D. No problem. 2D interpolation can be decomposed into two 1D interpolations, in the x-axis and then y-axis. Say you want (1.4, 2.8). Get the 1D interpolants between (1, 2)<->(2,2) and (1,3)<->(2,3). That's your x-axis step. Now 1D interpolate between them with the appropriate weights for y = 2.8.

This should be simple to make massively parallel. Just calculate each interpolated pixel separately. With shared memory access to the original image, you'll only be doing reads, so no synchronization issues.

Comments

[pezcode]

Great pictures and nicely explained

[blahman]

Thank you! This, and @Alex's answer together were really instructive in how bilinear interpolation works.