# How do I make an algorithm to take use billear interpolation of an image?

Hi experts,

I have been trying to find some psuedo code or a simple c++ algorithm that uses bilinear interpolation that will input a desired scale factor that is not an integer (e.g. 1.5) and reduce the resolution of image by this factor.
Any help with coming up with such an algorithm would be appreciated. Please do not post a link unless the link demonstrates very clearly the algorithm.

Thanks

Dennis
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
bilinear filtering is pretty straightforward. You take the (relative) coordinates of a pixel in the target image, identify the 4 corresponding neighboring pixels in the original image (using the relative coordinates), and then take a weighted average (for colour, and possibly other pixel attributes) of those 4 pixels.
0
Author Commented:
I would to have a psuedo code please..
0
Author Commented:
like*
0
Commented:
Something like :
``````/* srcImg : source image */
/* dstImg : destination image */

for each pixel in dstImg :
p.x = srcImg.width * (pixel.x / dstImg.width)
p.y = srcImg.height * (pixel.y / dstImg.height)

/* determine 4 source image pixels : (ignore pixels outside of the borders !) */
lr.x = roundToNearestInt(p.x)       /* lower right */
lr.y = roundToNearestInt(p.y)
ll(x, y) = (lr.x - 1, lr.y)         /* lower left */
ur(x, y) = (lr.x, lr.y - 1)         /* upper right */
ul(x, y) = (lr.x - 1, lr.y - 1)     /* upper left */

f.x = p.x - (lr.x - 0.5)
f.y = p.y - (lr.y - 0.5)

/* calculate weights : */
wlr = f.x * f.y                     /* lower right */
wll = (1 - f.x) * f.y               /* lower left */
wur = f.x * (1 - f.y)               /* upper right */
wul = (1 - f.x) * (1 - f.y)         /* upper left */

/* calculate colours using weighted sum : */
pixel.R = wlr * srcImg[lr].R + wll * srcImg[ll].R + wur * srcImg[ur].R + wul * srcImg[ul].R
pixel.G = ...
pixel.B = ...
``````
0
Author Commented:
thanks infinity, how would your code be affected if I was just using a gray scale image?
0
Commented:
Then you'd just have one "colour" to worry about :) The gray scale.
0
Author Commented:
Infinity is this a general case algorithm? Can you explain a little more the code you have posted? Then I will close this question..
0
Commented:
It is one approach to bilinear filtering. It uses the pixel center points to make it a bit nicer (but that does mean you have to take care of the edge cases).

>> Can you explain a little more the code you have posted?

I thought I did. In my first post, I explained the algorithm. And in the code, I added comments to indicate what's happening.

Do you understand the algorithm ?
Which parts do you have trouble with ?
0
Commented:
lr.x = roundToNearestInt(p.x)       /* lower right */
lr.y = roundToNearestInt(p.y)

Shouldn't that be std::ceil(p.x) & std::ceil(p.y)?
0
Commented:
>> Shouldn't that be std::ceil(p.x) & std::ceil(p.y)?

You need to take the 4 pixels from the source image that correspond most closely to the 1 pixel in the destination image. Rounding to nearest achieves that best. Rounding up will give a slightly more skewed result.

It's easiest to look at the 4 pixels as forming a square with a centre point (where the 4 pixels "touch"). You want to find that 4 pixel square in the source image whose centre is closest to the destination pixel.
0
Commented:
umm... isn't that the function of interpolation?
0
Commented:
>> umm... isn't that the function of interpolation?

That's what this question is about, isn't it. I'm a bit confused by your comment. I explained why I used "round to nearest" rather than "round up" ... because apparently that was what you had a doubt about.
0
Commented:
I am using code snippet to illustrate my point (since our formatting options are limited)

``````/*
Let's say p ends up like below.
+---+---+
|   |   |
| 1 | 2 |
|   |p  |
+---+---+
|   |   |
| 3 | 4 |
|   |   |
+---+---+
According to your code, we will end up interpolating between pixels 1, 2 and the ones above those two. This is because you are using nearest (pixel 2) as you lower right.
*/
``````
0
Commented:
I see where I caused the confusion now :)

My pseudo code interprets the int values at the pixel "borders". ie. the first pixel ranges from position 0 to 1, the second pixel from 1 to 2, etc.
So, a point at (1.1,0.9) would round to the nearest (1,1) point, which is the center point of the 4 top-left-most pixels displayed below (marked with x).
``````The pixels for a 4x4 image :

0   1   2   3   4
0+---+---+---+---+
| x | x |   |   |
1+---+---+---+---+
| x | x |   |   |
2+---+---+---+---+
|   |   |   |   |
3+---+---+---+---+
|   |   |   |   |
4+---+---+---+---+
``````
0

Experts Exchange Solution brought to you by