home | news | contact | about
Trilinear Interpolation Image Scaling
5 July 2009, 07:25 PM
Trilinear interpolation image scaling is an extension for bilinear interpolation image scaling and used in conjunction with Mip Mapping. Scaling image with this method requires two reference images of different size where one of it should be only half of the other. The purpose of trilinear interpolation is to interpolate an image not larger than the first image and not smaller than the other half-sized reference image.

sandwich.png
Figure 1: Interpolated image at the center.

In a nutshell, trilinear interpolation image scaling works by first bilinear downscaling the larger image, then bilinear upsizing the smaller one, and finally linear interpolating both products to form the final interpolated image. Think of it as merging two different sized images.

processes.png
Figure 2: Trilinear interpolation image scaling processes.

The formula
If you are familiar with bilinear image scaling this should be very straightforward. If you’re not, it shouldn’t be too hard to get the gist of it either. All you need is the diagram below, the derived formula, and a little bit of explanation. However if you want to understand more, reviewing bilinear interpolation image scaling can be of big help.

diagram.png
Figure 3: Trilinear interpolation process diagram. We want to find the interpolated pixel Y.

Referring to above diagram, there are two textures where the first is bounded by pixels ABCD originating from the larger reference image, and the second texture is bounded by pixels EFGH originating from the smaller one. The interpolated texture as seen at the middle of both reference textures is smaller than texture ABCD but larger than texture EFGH. It is by this condition trilinear image scaling works, in the event a larger up scaling is required (larger than the largest available reference image), just pick the that largest available reference image and do a bilinear upsizing instead. The same can be said for down sizing too, pick the smallest reference image and just bilinear downsize it. Except we usually use trilinear with mip mapping, and this mean the smallest reference will have a dimension of 1x1. Using algorithm to downsize further is an over kill – you get the idea.

Let’s get back to the math shall we. There are three steps to get the interpolated image. First, bilinear downscale the larger reference image. Secondly, bilinear upsize the smaller reference image, and finally linear interpolate both resized images. The first step can be expressed mathematically as below (from bilinear interpolation),

y1.gif

Take some time validating equation 1 with the diagram in figure 3. Understand how the equation relates with the diagram. Continue with the second step when you are ready (or don’t care validating). The second step is expressed mathematically with the same bilinear interpolation formula to get,

y2.gif

If you took the time relating equation 1 with our little diagram in figure 3, this one should be immediately obvious – it is of the same formula just a different texture. The last step is then to linear interpolate both Y1 and Y2 such as shown below,

ylinear.gif

Check the diagram for h3, it shows the distance between the first larger image and the interpolated image. The value for h3 is not immediately evident but is easily estimated,

h3.gif

Substitute equation 1 and 2 into equation 3 to get the final trilinear scaling formula below. I didn’t show the expansion step from equation 3 to reach the final formula. Perhaps you will do it as an exercise? ;)

trilinear.gif

Yes, quite lengthy indeed. This last equation is the trilinear interpolation formula and is what we need for the next section.

Java implementation
Here is a simple java implementation for trilinear interpolation. Explanation are inline as comments, be sure to read them. You can check on the following samples section to see this java source code in action (of course for the trilinear part).

/**
 * 
 * Trilinear scale two images, pixels and pixels2, to get a new
 * interpolated image with size width * height.
 * pixels is the larger image with size w * h.
 * pixels2 is the smaller image with size w2 * h2.     
 * width must be w >= width >= w2, width != 0
 * height must be h >= height >= h2, height != 0
 * Note: in Mip Mapping pixels2 should be half of pixels in dimension.
 * 
 * @param pixels Larger image pixels.
 * @param w Larger image width.
 * @param h Larger image height.
 * @param pixels2 Smaller image pixels.
 * @param w2 Smaller image width.
 * @param h2 Smaller image height.
 * @param width New width.
 * @param height New height.
 * @return New array with size width * height
 */
public int[] trilinearImageScaling(
        int[] pixels, int w, int h, // larger image
        int[] pixels2, int w2, int h2, // smaller image
        int width, int height) {

    int[] temp = new int[width*height] ;
    int index, index2, A, B, C, D, E, F, G, H ;
    float x, y, x2, y2, w_diff, h_diff, w2_diff, h2_diff, red, green, blue ;
    // find ratio for larger image
    float w_ratio = ((float)(w-1))/width ;
    float h_ratio = ((float)(h-1))/height ;
    // find ratio for smaller image
    float w2_ratio = ((float)(w2-1))/width ;
    float h2_ratio = ((float)(h2-1))/height ;
    // estimate h3 distance
    float h3_diff = (w - width)/(float)(w - w2) ;
    int offset = 0;
    for (int i=0;i<height;i++) {
        for (int j=0;j<width;j++) {
            // find w1 and h1 for larger image
            x = w_ratio * j ;
            y = h_ratio * i ;
            w_diff = x - (int)x ;            
            h_diff = y - (int)y ;
            index = (int)(y)*w+(int)(x) ;
            A = pixels[index] ;
            B = pixels[index+1] ;
            C = pixels[index+w] ;
            D = pixels[index+w+1] ;
            // find w2 and h2 for smaller image
            x2 = w2_ratio * j ;
            y2 = h2_ratio * i ;
            w2_diff = x2 - (int)x2 ;
            h2_diff = y2 - (int)y2 ;
            index2 = (int)(y2)*w2+(int)(x2) ;
            E = pixels2[index2] ;
            F = pixels2[index2+1] ;
            G = pixels2[index2+w2] ;
            H = pixels2[index2+w2+1] ;           
            
            // trilinear interpolate blue element           
            blue = (A&0xff)*(1-w_diff)*(1-h_diff)*(1-h3_diff) + 
                   (B&0xff)*(w_diff)*(1-h_diff)*(1-h3_diff) +
                   (C&0xff)*(h_diff)*(1-w_diff)*(1-h3_diff) + 
                   (D&0xff)*(w_diff)*(h_diff)*(1-h3_diff) +
                   (E&0xff)*(1-w2_diff)*(1-h2_diff)*(h3_diff) + 
                   (F&0xff)*(w2_diff)*(1-h2_diff)*(h3_diff) +
                   (G&0xff)*(h2_diff)*(1-w2_diff)*(h3_diff) + 
                   (H&0xff)*(w2_diff)*(h2_diff)*(h3_diff);
            
            // trilinear interpolate green element
            green = ((A>>8)&0xff)*(1-w_diff)*(1-h_diff)*(1-h3_diff) + 
                    ((B>>8)&0xff)*(w_diff)*(1-h_diff)*(1-h3_diff) +
                    ((C>>8)&0xff)*(h_diff)*(1-w_diff)*(1-h3_diff) + 
                    ((D>>8)&0xff)*(w_diff)*(h_diff)*(1-h3_diff) +
                    ((E>>8)&0xff)*(1-w2_diff)*(1-h2_diff)*(h3_diff) + 
                    ((F>>8)&0xff)*(w2_diff)*(1-h2_diff)*(h3_diff) +
                    ((G>>8)&0xff)*(h2_diff)*(1-w2_diff)*(h3_diff) + 
                    ((H>>8)&0xff)*(w2_diff)*(h2_diff)*(h3_diff);
            
            // trilinear interpolate red element
            red = ((A>>16)&0xff)*(1-w_diff)*(1-h_diff)*(1-h3_diff) + 
                  ((B>>16)&0xff)*(w_diff)*(1-h_diff)*(1-h3_diff) +
                  ((C>>16)&0xff)*(h_diff)*(1-w_diff)*(1-h3_diff) + 
                  ((D>>16)&0xff)*(w_diff)*(h_diff)*(1-h3_diff) +
                  ((E>>16)&0xff)*(1-w2_diff)*(1-h2_diff)*(h3_diff) + 
                  ((F>>16)&0xff)*(w2_diff)*(1-h2_diff)*(h3_diff) +
                  ((G>>16)&0xff)*(h2_diff)*(1-w2_diff)*(h3_diff) + 
                  ((H>>16)&0xff)*(w2_diff)*(h2_diff)*(h3_diff);

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

    return temp ;
}


Samples
Mip mapped texture. The texture contains 256x256, 128x128, 64x64, 32x32, 16x16, 8x8, 4x4, 2x2, and 1x1 of the same texture.

mipmap.png

Below left is an image trilinear resized at 200x200, apparently using 256x256 and 128x128 as the reference images. Below right is a bilinear resized image using only 256x256 as the reference. Notice trilinear results in a smooth but blurry image.

compare.png
Last edited on 5 July 2009

Comments

~Lee, 26 October 2012, 09:57 AM
This is awesome! It worked perfectly for me and solved my downsizing by less than half issue.
Post a comment~
Name*
algorithm has how many characters?*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.