Linear interpolation is probably one of the most proliferated data processing algorithms in the world. From simple drawing of a straight line, through rescaling of images and last but not least performing affine transformations of volumetric data – all of these can be accomplished by some implementation of linear interpolation. Today I would like to present a pretty specialised variant of tri-linear interpolation which is useful in computations requiring transformations expressed by a 3×3 matrix. Another assumption I make is that the output is sampled using a grid of the same dimensions as the input volume. Both of the above conditions can be easily generalised to include translation and different sampling resolutions. Nevertheless for demonstration purposes (and special cases) I will present a code subject to the above-mentioned restrictions. Now I can proceed to mention what makes dssi particularly useful. The input volume is interpolated into the output volume dice-by-dice rather than simply having the output volume sample the entire input volume at once according to the inverse transform. It might sound convoluted during the first reading but it actually makes perfect sense. Why would anyone do something like this? Well, if you have the capacity to scale your RAM according to the demand without limits, you might be better off with regular interpolation. The diced approach serves to allocate only the big output volume and process the input volume as a series of dices, therefore arbitrarily reducing the amount of memory required to store the input volume (dices can be as small as 1x1x1). I will present below the function invocation as used from MATLAB. It will be more explanatory than going through parameters without an example.
output_vol = nan(128,128,128); dice = rand(32,32,32); xform = roty(45); invxform = roty(-45); % or invxform = inv(xform) if you like dssi(size(output_vol), size(dice), [0, 32, 64], dice, xform, invxform, output_vol);
The above code says that a 32x32x32 dice refers to a dice starting at corner position [0, 32, 64] in a hypothetical source volume of 128x128x128 voxels (same as the output volume) and that dice should be subjected to the transformation xform and put into volume output_vol. The inverse transform is used by the algorithm to move back and forth between the source and destination volume spaces – it’s necessary and I preferred to leave it to the user to make the inversion. You can run the code above and then look across the output_vol to see where the dice has ended up. Trust me – this is useful, you can run memory-hungry algorithms with less RAM (basically “less” could read “almost half”). If you need a practical example – take a look into high resolution back-projection. The download is available below under the usual 2-clause BSD License. Please enjoy this early Christmas gift 🙂
DOWNLOAD: dssi.zip