bilinear interpolation

This is a discussion on bilinear interpolation within the Game Programming forums, part of the General Programming Boards category; Well I took it upon myself to read about linear interpolation today, since I found some 'lerp' code in the ...

  1. #1
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709

    bilinear interpolation

    Well I took it upon myself to read about linear interpolation today, since I found some 'lerp' code in the Irrlicht engine and realised how useful it is in the domain of computer graphics.

    I almost completely understand it too

    Anyway, I read wikipedia's article on bilinear interpolation and sort of understood that too... but what can you use it for in computer graphics? Can you use it in computer graphics? There's a pretty picture in the article.

    I googled 'bilinear interpolation in computer graphics'... what the hell is a 'pyramid filter'? Wikipedia has no answers and the google results for that confuse me.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    The subject of interpolation (in any form) in computer graphics is huge, so I'll try to give a general overview and if you want to know something specific, feel free to ask.

    In general, interpolation helps us to find the value of a data set or a function, between two points, using those points as indicators. In the case of linear interpolation, if you have two points (x1, y1) and (x2, y2), you can calculate the interpolation coefficient alpha which varies between 0 and 1. If the coefficient is 0, you are at the starting point, if the coefficient is 1, you are at the ending point.

    Let's try to find a very basic example for linear interpolation (although the result would be horrific with the linear approach): you want to move an object in 2D along a predefined path, that you can't or don't want to describe at a function. So you go ahead and define a limited number of points, each point has additionally to its coordinates a time value (to see where the object is at what time.
    If you are running your program and the animation begins, each cycle of the loop you'll increment the time value by the time that passed since the last frame and you'll try to calculate the position of the object from there. Let's say we have the following:

    Point1: x1,y1 and t1
    Point2: x2,y2 and t2

    Now during your animation cycle you end up with a time value t, with t1 < t < t2 and you have to find the position of the object. If you calculate for each direction the distance the object has to travel, you'll find:

    distX = x2 - x1;
    distY = y2 - y1;
    or your linear coefficient is between 0 and 1 and its: (t - t1)

    You then see that the object is at:
    objectX = x1 + (t-t1) * distX
    objectY = y1 + (t-t1) * distY

    Of course there are several other ways to calculate this and way more elaborate methods but I hope this is enough as a general idea.

    Now, let's apply this to the wonderful world of pixels. In nearly every operation, resize, rotation, affine transformation, zoom or perspective transformation, you end up with a different "Point of View" as in your last image. In fact, you transformed the camera position from which you are looking at the image. Anyway, there exists a relation R between your source and your destination image (and a relation R-inverse between the destination and the source image).

    Let's take a very easy example, a rotation:
    If you rotate by n*(Pi/2), it is rather simple to find the source pixel value for each destination pixel value in the new image. But what happens if you have another rotation value. If you take your destination coords and you apply the R-inverse relation to find the source pixel value in the source image, you will most of the time end up with a comma value, so instead of finding (2, 3) you will find (2.534, 3.15).

    You have several options:

    nearest neighbor:
    You can forget the values behind the comma and you assume that the pixel you are looking for is (2,3) and not the more exact value. In that case, you take an approximation and the result is of worse quality than the source image.

    Name:  sampling.png
Views: 16497
Size:  9.1 KB

    bilinear interpolation:
    You assume (correctly) that the more exact values have their justified meaning. In fact, it's telling you that the pixel value you are looking for is in between the pixels somewhere, which is the main problem in digital imaging: regardless of how many megapixels we have, we only sample the continuous 2D color function into an array and discard the information in between. We are able to partly reconstruct that missing information using interpolation by saying that the fraction corresponds to a percentage, the percentage of color information we need to take from that pixel.

    Name:  bilin.png
Views: 15438
Size:  6.9 KB

    The formular for bilinear interpolation is the following:

    S = (1-p)(1-q) a + (1-p) q c + p (1-q) b + p q d

    where (p,q) are the coordinates you find by taking the R-inverse transformation of your destination image pixel and a, b, c and d are the color information of the respective pixels (you have to apply red, green and blue seperately).

    As you can see, you use the exact values to create a percentage for the respective surrounding pixels, which is way more exact than the nearest neighbor method.


    A pyramid filter:

    Now this is something completely different. A filter is the iterative application of a filter kernel on a source image (also called convolution). Take for example the blur operation which uses an N*N kernel depending on how much you want to blur. We'll use the gaussian filter for reference:

    Name:  gauss2.gif
Views: 13664
Size:  3.8 KB

    Your create an N*N array and fill it with values using the gaussian formula:

    Name:  eqngaus2.gif
Views: 13480
Size:  777 Bytes

    In this kernel, values further away from the center have a smaller value which means that when you apply them to a pixel, their influence on the result is smaller. usually, the largest value is in the center, since you want to keep the highest percentage of information from the pixel the kernel is applied on.

    Now, if you take not only 1 filter of a fixed size N, but several versions of the same filter, you can construct a pyramid. Probably the most common example is the Laplacian Pyramid where you encode an image by only storing the laplacian difference between the original version and the blurred version. The blurring removes sharp edges and makes it easier to downsample the image, while the several layers of laplacian differences create a pyramid.
    Afterwards, we only have to transmit the lowest sampled image of what we want to reconstruct and the laplacian pyramid and we are able to reconstruct the high-frequency, full-detailled image by iteratively doubling the size and applying the laplacian difference on the blurred image to get the original image back.

  3. #3
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Bubba moved to Luxembourg?

  4. #4
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Quote Originally Posted by Perspective
    Bubba moved to Luxembourg?
    I take that as a compliment

  5. #5
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Whoa. I didn't see this coming, thanks a lot!
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Bubba moved to Luxembourg?
    Hehe. Nope still in the USA and still using interpolation everyday.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 06-14-2006, 03:45 AM
  2. Interpolation in C - Help
    By finnpark in forum C Programming
    Replies: 3
    Last Post: 11-01-2005, 11:44 AM
  3. what's interpolation?
    By jverkoey in forum Game Programming
    Replies: 9
    Last Post: 02-12-2003, 02:55 PM
  4. interpolation sort
    By saigonara in forum C Programming
    Replies: 5
    Last Post: 07-14-2002, 06:58 PM
  5. Super fast bilinear interpolation
    By VirtualAce in forum Game Programming
    Replies: 2
    Last Post: 06-18-2002, 09:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21