Bilinear interpolation to enlarge raster images

Question

I am a student and I was instructed to optimize bilinear interpolation of the images, causing parallelism from CUDA.

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

Now I need to perform bilinear interpolation in the array. I don’t understand the math behind it (even after going through the wiki article and other google results). Because of this, I cannot come up with an algorithm.

Is there anyone who can help me with a link to an existing bilinear interpolation algorithm on a one-dimensional array? Or perhaps a link to an open source image processing library that uses bilinear and bicubic interpolation to scale images?

Answer 1

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

This first number should give you memories of high school math. Given some location a in which we want to know f (a) , we take the neighboring “known” values ​​and set a line between them.

So, we used the old high school equations y = mx + b and y-y1 = m (x-x1). Nothing unusual.

We basically transfer this concept to two-dimensional in order to obtain bilinear interpolation. We can attack the problem of finding f (a, b) for any a, b by doing three interpolations. Carefully read the following figure. Do not be alarmed by all the shortcuts. This is actually quite simple.

For bilinear interpolation, we again use 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 calculate two (one-dimensional!) Interpolating lines.

• f (a, y _j ) , where y _{j is} kept constant
• f (a, y _{j + 1} ) , where y _{j + 1 is} kept constant.

Now there is only one last step. You take two points calculated by you, f (a, y _j ) and f (a, y _{j + 1} ) , and set a line between them. The fact that blue goes from left to right in the diagram goes through f (a, b) . Interpolation on this last line gives the final answer.

I will leave the math for the 2-D case for you. It is not difficult if you are working with a chart. And after going through this, you yourself can find out what is happening.

One small note, no matter which side you choose for the first two interpolations. You could select the top and bottom, and then make a third interpolation line between the two. The answer would be the same.

Answer 2

When you enlarge the image by scaling the sides by the integral coefficient, you can consider the result as the original image with additional pixels inserted between the original pixels.

See the images in the IMAGE EXAMPLE .

The formula f(x,y)=... in this Wikipedia article gives you a method for calculating the color f inserted pixel:

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

Original pixels are displayed in red. The inserted pixel is displayed in green.

What an idea.

If you scale the sides with a non-integer factor, the formulas are still preserved, but now you need to recalculate all the pixel colors, since you cannot just take the original pixels and just insert extra pixels between them.

Answer 3

Don't get stuck with the fact that 2D arrays in C are really 1D arrays. This is an implementation detail. Mathematically, you still have to think about 2D arrays.

Think of linear interpolation on a 1D array. You know the value at 0, 1, 2, 3, ... Now suppose I am requesting a value at 1.4 . You will give me a balanced combination of values ​​in 1 and 2 : (1 - 0.4)*A[1] + 0.4*A[2] . Just right?

Now you need to go to 2D. No problems. 2D interpolation can be decomposed into two one-dimensional interpolations along the x axis, and then along the y axis. Let's say you want (1.4, 2.8) . Get 1D interpolation between (1, 2)<->(2,2) and (1,3)<->(2,3) . This is your x axis step. Now 1D interpolates between them with the corresponding weights for y = 2.8 .

This should be simple for mass concurrency. Just calculate each interpolated pixel separately. When using access to the original image, access to the shared memory you will do only read, so no problems with synchronization.