Interpolation

Interpolation Methods

To test the effects of various methods of interpolation, three different interpolation algorithms were used:

Nearest Neighbor Interpolation

Given an intermediate point, nearest neighbor interpolation assigns that point the value of the nearest valid data point. This is the equivalent of a zero-order hold and is the simplest algorithm for resizing images. To assign the value in a 3D image it is necessary to know only the value of a single point - that of the nearest neighbor.

Trilinear Interpolation

Trilinear interpolation requires the use of a larger set of data points; specifically, the nearest eight values are used. One can imagine the cube of points surrounding the intermediate point in question; trilinear interpolation assigns the value of the point as a weighted average of the points on the corners of the cube, with higher weight given to points that are closer to the input point. The IEEE published paper by Bai and Wang explains how to implement trilinear interpolation.

Tricubic Interpolation

Cubic interpolation in one dimension places additional constraints on the first and second derivatives at the known data points; as a result, its calculation requires the four nearest data points - in a 3D image this translates to a 3x3 cube with 64 points, one at each vertex (the desired intermediate point is located inside the center cube). The Lekien and Marsden publication explains an efficient implementation of tricubic interpolation. By modeling the interpolation as a linear system it is possible to generate an interpolation matrix which is valid for all points mapping to the same 3x3 cube - this drastically cuts down the calculation time for large outputs.

Currently favored interpolation methods for 3D images include nearest neighbor and trilinear interpolation. This project implements tricubic interpolation as a method of resizing images. All three interpolation methods were implemented in C using the VisionX toolkit.

Nearest Neighbor Visualization

Trilinear Interpolation Visualization

To correctly perform trilinear interpolation, the values of the eight closest points are needed, as shown in the 3D diagram. The interpolated value may be calculated by “flattening” the cube in three dimensions. Tricubic interpolation places additional constraints on the first and second derivatives at these eight points, requiring a total of 64 points (a 3x3 cube) to calculate the interpolated value.

Tricubic Interpolation Visualization