Trilinear Interpolation Image Scaling

5 July 2009, 07:25 PM

*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.

*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.

*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),

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,

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,

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,

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? ;)

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 */`

publicint[] trilinearImageScaling(int[] pixels,intw,inth,`// larger image`

int[] pixels2,intw2,inth2,`// smaller image`

intwidth,intheight) {int[] temp =newint[width*height] ;intindex, index2, A, B, C, D, E, F, G, H ;floatx, y, x2, y2, w_diff, h_diff, w2_diff, h2_diff, red, green, blue ;`// find ratio for larger image`

floatw_ratio = ((float)(w-1))/width ;floath_ratio = ((float)(h-1))/height ;`// find ratio for smaller image`

floatw2_ratio = ((float)(w2-1))/width ;floath2_ratio = ((float)(h2-1))/height ;`// estimate h3 distance`

floath3_diff = (w - width)/(float)(w - w2) ;intoffset = 0;for(inti=0;i<height;i++) {for(intj=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; } }returntemp ; }

**Samples**

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

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.

Last edited on 5 July 2009

### Comments

Post a comment~

Lee, 26 October 2012, 09:57 AM