home | news | contact | about
Bilinear Image Scaling
27 June 2009, 08:22 AM
Bilinear image scaling is about the same as nearest neighbor image scaling except with interpolation. Instead of copying the neighboring pixels (which often results in jaggy image), interpolation technique based on surrounding pixels is used to produce much smoother scaling.

Although bilinear scaling is not exactly complicated, it is a composite algorithm based on other more basic function. As the name might have suggested, the algorithm is a combination of two linear interpolations. It is not mandatory to know what linear interpolation is but doing is not really that bad. I suggest the reader to follow through at least the brief explanation.

Linear Interpolation (a brief explanation)
Linear interpolation is a method to estimate an arbitrary point between two other points. Consider two points of colors on a canvas, red and green. Imagine a straight line between the dots, and somewhere on this imaginary line put a new dot. What is a suitable color for this new dot? Any color is fine really, but we are talking about interpolation so we should be doing that. Putting our little imaginary line in perspective,

linear.png
Figure 1: What is a suitable color for Y?

In this illustration, a yet unknown color dot Y is placed somewhere between A (red) and B (green). Other only known thing is the distance between A and B which is L and the distance between A and Y which is l. This information is sufficient to construct the so called linear interpolation function.

lieq.gif
Figure 2: Linear interpolation equation.

This function will be able to tell what Y's color is. If you are interested to know the expected color for Y, check the full article for Linear Interpolation.

Texture
Going back to the original topic, the other trivial but still important term is the texture. This is not about the whole image itself but only a small portion of it. In the simplest of bilinear scaling, the usual texture dimension is only two by two, a texture containing only four pixels. The illustration below should help with getting the idea for this,

2by2.png
Figure 3: 2 by 2 texture.

That small texture with A, B, C, and D is what we are talking about. Keep in mind there will be many smaller textures like this composing the entire image. This also means the algorithm has many smaller textures to work with.

The algorithm
Scaling an image goes in two ways, making it larger or to make it smaller. By enlarging an image, some new pixels are constructed by means of interpolation. By shrinking, we are tempted to think the right pixels are selected to keep while the others are thrown away, but this is not the case. Unlike nearest neighbor shrinking where pixels are thrown, bilinear shrinking estimates a smaller resolution of the original image. Even though details are lost, almost all the new pixels in the shrunk image do not come directly from their original, but interpolated, indirectly keeping the properties of lost pixels. It should be understood this is not always the case, shrinking image to half size (and smaller) significantly reduce image quality – not much different from nearest neighbor shrinking. This also applies to sizing up more than double the original size.

enlarge.png
Figure 4: Enlarged image introduces 'white spaces'.

For the purpose of this article, explanation will follow the making-it-larger path because that is probably why people are reading this anyway. So we start by enlarging a small texture such as shown in figure 4. Note: this is not to be mistaken as a requirement to enlarge every single texture found in an image. The objective is finding the colors for all white spaces, including i, j, and Y. Here linear interpolation comes into play, first find the relation between A, i, and B. Using linear interpolation function that we derived at the beginning (figure 2), we get this equation,

eq1.gif

Do the same for C, j, and D and we get,

eq2.gif

Now we have two linear interpolation equations. Next is to combine the two equations forming a single equation that is called the bilinear function.

eq3.gif

Substituting equation 1 and 2 into 3 we get,

bilineareq.gif

Using this last equation, all white spaces can now be interpolated!! That's it!!

Java Implementation
Yeah right. Putting the idea on paper is all nice and convenient but actually doing it is an entirely different thing. This time we discuss how a basic implementation is worked out.

Two things must be understood before we proceed, first is the actual code for scaling the image. Secondly is the code for interpolation process. These two are distinct, the first as mentioned is for the enlargement and at the same time introducing all the white spaces. The second part which is the interpolation process decides the color for these white spaces. Nearest neighbor algorithm share similar code for scaling, just missing the interpolation part.

Here is a Java snippet for 1 channel (grayscale) bilinear image scaling. Each pixel is an int and has a range from 0 to 255.

/**
 * Bilinear resize grayscale image.
 * pixels is an array of size w * h.
 * Target dimension is w2 * h2.
 * w2 * h2 cannot be zero.
 * 
 * @param pixels Image pixels.
 * @param w Image width.
 * @param h Image height.
 * @param w2 New width.
 * @param h2 New height.
 * @return New array with size w2 * h2.
 */
public int[] resizeBilinearGray(int[] pixels, int w, int h, int w2, int h2) {
    int[] temp = new int[w2*h2] ;
    int A, B, C, D, x, y, index, gray ;
    float x_ratio = ((float)(w-1))/w2 ;
    float y_ratio = ((float)(h-1))/h2 ;
    float x_diff, y_diff, ya, yb ;
    int offset = 0 ;
    for (int i=0;i<h2;i++) {
        for (int j=0;j<w2;j++) {
            x = (int)(x_ratio * j) ;
            y = (int)(y_ratio * i) ;
            x_diff = (x_ratio * j) - x ;
            y_diff = (y_ratio * i) - y ;
            index = y*w+x ;

            // range is 0 to 255 thus bitwise AND with 0xff
            A = pixels[index] & 0xff ;
            B = pixels[index+1] & 0xff ;
            C = pixels[index+w] & 0xff ;
            D = pixels[index+w+1] & 0xff ;
            
            // Y = A(1-w)(1-h) + B(w)(1-h) + C(h)(1-w) + Dwh
            gray = (int)(
                    A*(1-x_diff)*(1-y_diff) +  B*(x_diff)*(1-y_diff) +
                    C*(y_diff)*(1-x_diff)   +  D*(x_diff*y_diff)
                    ) ;

            temp[offset++] = gray ;                                   
        }
    }
    return temp ;
}


Here is a Java snippet for 4 channels (color) bilinear image scaling. Each pixel is a packed int containing alpha, red, green, and blue information.

/**
 * Bilinear resize ARGB image.
 * pixels is an array of size w * h.
 * Target dimension is w2 * h2.
 * w2 * h2 cannot be zero.
 * 
 * @param pixels Image pixels.
 * @param w Image width.
 * @param h Image height.
 * @param w2 New width.
 * @param h2 New height.
 * @return New array with size w2 * h2.
 */
public int[] resizeBilinear(int[] pixels, int w, int h, int w2, int h2) {
    int[] temp = new int[w2*h2] ;
    int a, b, c, d, x, y, index ;
    float x_ratio = ((float)(w-1))/w2 ;
    float y_ratio = ((float)(h-1))/h2 ;
    float x_diff, y_diff, blue, red, green ;
    int offset = 0 ;
    for (int i=0;i<h2;i++) {
        for (int j=0;j<w2;j++) {
            x = (int)(x_ratio * j) ;
            y = (int)(y_ratio * i) ;
            x_diff = (x_ratio * j) - x ;
            y_diff = (y_ratio * i) - y ;
            index = (y*w+x) ;                
            a = pixels[index] ;
            b = pixels[index+1] ;
            c = pixels[index+w] ;
            d = pixels[index+w+1] ;

            // blue element
            // Yb = Ab(1-w)(1-h) + Bb(w)(1-h) + Cb(h)(1-w) + Db(wh)
            blue = (a&0xff)*(1-x_diff)*(1-y_diff) + (b&0xff)*(x_diff)*(1-y_diff) +
                   (c&0xff)*(y_diff)*(1-x_diff)   + (d&0xff)*(x_diff*y_diff);

            // green element
            // Yg = Ag(1-w)(1-h) + Bg(w)(1-h) + Cg(h)(1-w) + Dg(wh)
            green = ((a>>8)&0xff)*(1-x_diff)*(1-y_diff) + ((b>>8)&0xff)*(x_diff)*(1-y_diff) +
                    ((c>>8)&0xff)*(y_diff)*(1-x_diff)   + ((d>>8)&0xff)*(x_diff*y_diff);

            // red element
            // Yr = Ar(1-w)(1-h) + Br(w)(1-h) + Cr(h)(1-w) + Dr(wh)
            red = ((a>>16)&0xff)*(1-x_diff)*(1-y_diff) + ((b>>16)&0xff)*(x_diff)*(1-y_diff) +
                  ((c>>16)&0xff)*(y_diff)*(1-x_diff)   + ((d>>16)&0xff)*(x_diff*y_diff);

            temp[offset++] = 
                    0xff000000 | // hardcode alpha
                    ((((int)red)<<16)&0xff0000) |
                    ((((int)green)<<8)&0xff00) |
                    ((int)blue) ;
        }
    }
    return temp ;
}


Caveat
Bilinear scaling performs best when the desired output dimension is no more than double or half its original size. If that is the case however, it might be good to implement additional technique called Mip Mapping on top of the existing algorithm.

Samples
Comparison between bilinear and nearest neighbor,

suitexture.png

Downsizing comparison between bilinear and nearest neighbor. Original image is too big and not shown.

firefox.png

Last edited on 28 June 2009

Comments

~Lucas, 28 December 2009, 04:27 PM
Hello,

Is it possible for this algorithm to work and keep quality using only integrers like it is in nearest neigbour scaling?
~John, 3 January 2010, 03:15 AM
Hi Lucas,

Yes and no. It is possible to have this working with integer only variables however it will not be the same i.e. accuracy is reduced. The four weight factors,

1. x_diff * y_diff
2. y_diff * (1 - x_diff)
3. x_diff * (1 - y_diff)
4. (1 - x_diff) * (1 - y_diff)

determine the final color and changing that is surely to affect the final color as well.
~Lucas, 3 January 2010, 02:15 PM
Thanks, I have actually tried to use this with just integrers, and it turned out to have same quality as Nearest, just it was slower.

The reason I was asking was that I was trying to implement this on an non-FPU ARM device, which seems to totally hate floats =P
~Pepito, 6 June 2010, 11:01 AM
The optimized version based only on integers (no floating point calculation) doesn't changed quality. Color sample have an error tolerance of one point. Lucas mistakes when he said that the quality of the optimized version is the same that the "nearest neighbor" algorithm.

An optimized version of grayscale bilinear image scaling :

public int[] resizeBilinearGray(int[] pixels, int w, int h, int w2, int h2) {
int[] temp = new int[w2*h2];
int A, B, C, D, index, y_index, xr, yr, gray;
long x, y = 0, x_diff, y_diff, one_min_x_diff, one_min_y_diff;
int x_ratio = (int) (((w - 1) << 16) / w2);
int y_ratio = (int) (((h - 1) << 16) / h2);
int offset = 0;
for (int i=0;i<h2;i++) {
yr = (int) (y >> 16);
y_diff = y - (yr << 16);
one_min_y_diff = 65536 - y_diff;
y_index = yr * w;
x = 0;
for (int j=0;j<w2;j++) {
xr = (int) (x >> 16);
x_diff = x - (xr << 16);
one_min_x_diff = 65536 - x_diff;
index = y_index + xr;

// range is 0 to 255 thus bitwise AND with 0xff
A = pixels[index] & 0xff ;
B = pixels[index+1] & 0xff ;
C = pixels[index+w] & 0xff ;
D = pixels[index+w+1] & 0xff ;

// Y = A(1-w)(1-h) + B(w)(1-h) + C(h)(1-w) + D(w)(h)
gray = (int) ((
A*one_min_x_diff*one_min_y_diff +
B*x_diff*one_min_y_diff +
C*y_diff*one_min_x_diff +
D*x_diff*y_diff
) >> 32);

temp[offset++] = gray;

x += x_ratio;
}
y += y_ratio;
}
return temp ;
}
~John, 7 June 2010, 02:46 AM
Thanks for posting an optimized version Pepito, I haven't tested it yet though.
On another note, I guess I'll need to implement something like a source-code tag to make codes much more readable in the comment section.
~vijay, 19 August 2010, 01:37 AM
This was very helpful in understanding bilinear interpolation. Thanks a lot.
~PISIT, 7 September 2010, 07:21 PM
Reading your article gives me an idea of how to implement Bilinear algorithm. Unlike others, your article has the practical example and provide additional basic knowledge. Cheer!!!! and thank you.
~PISIT, 7 September 2010, 08:00 PM
// range is 0 to 255 thus bitwise AND with 0xff
A = pixels[index] & 0xff ;
B = pixels[index+1] & 0xff ;
C = pixels[index+w] & 0xff ;
D = pixels[index+w+1] & 0xff ;

Hello, I'm apologize for my understanding level. What will happen if the value of a index result to be the last elments in pixels[] and,still, the program try to find next B C and D by plus the interger to it. Isn't it the array out of bound error?

Thank you
~m4D, 22 October 2010, 06:27 AM
It seems to me, Pepito's integer version doesn't work (armv4, x86). Looks like something is wrong with color calculation using such weight factors. Can anyone help?
~raya, 1 November 2010, 03:35 AM
Sometimes this algorithm works well, but another time (for some new width and new height) I get corrupted image.
For example 352x240 to 500x300 works, but 352x240 to 498x300 distorts the image and colors.
~DM, 3 January 2012, 05:51 AM
Thanks! this was very helpful.
I modified/adapted the code for my solution of Harvard\'s CS50 pset5/hacker5 assignment ;) (a free online C course)

(my end result @ http://gotfu.wordpress.com/2012/01/03/harvard-cs50-pset5hacker5-forensics/ )
~stereomatching, 10 June 2012, 08:21 AM
Thanks for your explanation, I have two questions
after study your codes.

1 : Why should we find the ratio with -1?
float x_ratio = ((float)(w-1))/w2 ;
float y_ratio = ((float)(h-1))/h2 ;

but not
float x_ratio = ((float)(w))/w2 ;
float y_ratio = ((float)(h))/h2 ;

2 : Make sure the x and y diff would not more
than 1?
x = (int)(x_ratio * j) ;
y = (int)(y_ratio * i) ;
x_diff = (x_ratio * j) - x ;
y_diff = (y_ratio * i) - y ;

Thanks
~Nicholas, 14 July 2012, 06:52 AM
Hi,

This explanation is the best I have ever encountered.

Can someone explain or direct me to a similar link of how to calculate for DOWN SAMPLING please?

Thanks
~Stuart, 15 December 2012, 03:48 AM
How can I pass int[] pixels into function?
~Alle, 27 February 2013, 10:08 AM
I get the method \'resizeBilinearGray\' and i try di apply the pointers logical.

the trasform methods seems to work done, here is the code

private byte[] resizeBilinear(byte[] pixels, int widthOrig, int heightOrig, float scaling, bool adaptResolution)
{
int widthNew = 0, heightNew = 0;
if (adaptResolution)
{
widthNew = (int)(widthOrig * scaling);
heightNew = (int)(heightOrig * scaling);
}
else
{
widthNew = widthOrig;
heightNew = (int)(heightOrig * scaling);
}

byte[] temp = new byte[widthNew * heightNew];

fixed (byte* startTemp = &temp[0])
{
byte* ptrTemp = startTemp;
byte* ptrPixels = null;

int A, B, C, D, x, y;
float x_ratio = ((float)(widthOrig - 1)) / widthNew;
float y_ratio = ((float)(heightOrig - 1)) / heightNew;
byte x_diff, y_diff;
for (int i = 0; i < heightNew; i++)
{
y = (int)(y_ratio * i);
y_diff = (byte)((y_ratio * i) - y);

fixed (byte* startPixels = &pixels[y * widthOrig])
{
ptrPixels = startPixels;

for (int j = 0; j < widthNew; j++)
{
x = (int)(x_ratio * j);
x_diff = (byte)((x_ratio * j) - x);

ptrPixels = startPixels + x;

// range is 0 to 255 thus bitwise AND with 0xff
A = *ptrPixels & 0xff;
B = *(ptrPixels + 1) & 0xff;
C = *(ptrPixels + widthOrig) & 0xff;
D = *(ptrPixels + widthOrig + 1) & 0xff;

// Y = A(1-w)(1-h) + B(w)(1-h) + C(h)(1-w) + Dwh
*ptrTemp = (byte)(
A * (1 - x_diff) * (1 - y_diff) +
B * (x_diff) * (1 - y_diff) +
C * (y_diff) * (1 - x_diff) +
D * (x_diff * y_diff));

ptrTemp++;
}
}
}
}

return temp;
}
~DigitalMan, 29 April 2013, 08:00 PM
With some minor optimizations and converting to a strictly-integer format, this runs nearly as fast as the strictly-integer nearest-neighbor scaling algorithm also found on this site, with no apparent error in color calculation.

However, since I\'m dealing with a byte array (with 3 or 4 bytes per pixel depending on source), this can have an issue that nearest-neighbor will not - signed numbers. Because multiplication is involved, bytes will need to be converted to a larger number (int is probably fastest), and &\'ed with 0xFF.

Hopefully, that will save someone else a few hours of pointless troubleshooting and a painful facedesk.
~Alex, 2 May 2013, 10:41 AM
What if the pixel whose 4 neighboring pixel is to be considered is an edge pixel in that case there will
be no pixel having the coordinate (x+1,y+1) but still the program works how?
~Amir Hossein, 5 October 2013, 06:54 AM
What does this part do ?

x = (int)(x_ratio * j) ;
y = (int)(y_ratio * i) ;
x_diff = (x_ratio * j) - x ;
y_diff = (y_ratio * i) - y ;
index = y*w+x ;

I\'m trying to convert it to C++ but I don\'t understand this part. for instance if
Post a comment~
Name*
Double of 5 is?*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.