Theory of Interpolation - 2023.1 English

Vitis Libraries

Release Date
2023-12-20
Version
2023.1 English

Introduction

Interpolation is an operation which is used to create new data points given a discrete set. Those new points should represent a curve, or a set of curves, which binds all the given discrete points altogether (in case of upsampling). Following an example:

In red we have the fixed point given and in blue the line which consists in the new point created by the interpolation operation. It is going to be detailed it better later, but the image example is what you actually will find implemented in the library, a B-Spline constructed from a variant of the Splines called Catmull-Rom.

Interpolation in Ultrasound

Interpolation is used because of the virtual sources, if the sampling density which returns us the values is not high enough, generates a significant sidelobes in the point of spread, which result in a significant downgrade of the final image resolution. This process cannot be overcomed in any way (excepting from rising the sampling density, which is not necessarily possible) but to the use of interpolation. This construct in fact allows to generate the intermediate missing points from the samples without increasing the sampling density. The interpolation which can be used in ultrasound application is an enormous variety with different outcomes with respect to the technique chosen. The most popular studied interpolation scheme could be regroup in 5 categories:

  1. Nearest Neighbour (which consists in the application of the apodization on the valid samples selected);
  2. Linear;
  3. Spline;
  4. Matched Filter;
  5. Polynomial;

Definitely the best choices (but at the cost of a high number of computational resources) are Matched Filter and Spline. Linear Interpolation suffers from high sidelobes energy, which results in a poor final contrast (which is essential for a good quality image in ultrasound beamforming). Polynomial interpolation (especially for high rank ones) suffers from Runge’s phenomena and thus it might yield some singular points. Before entering the details of the interpolation chosen, the spline, we detail why it is a suitable choice for a generic interpolation application.

Spline Interpolation

A bit of hystory may give an understanding of the validity of splines. Before computers were used for creating engineering designs, designer employed drafting tools and drawing by hand. To draw curves, especially for shipbuilding, draftsmen often used long, thin, flexible strips of wood, plastic, or metal called “Splines”. The splines were held in place with lead weights. The elasticity of the spline material combined with the constraint of the control points, or knots, would cause the strip to take the shape that minimized the energy required for bending it between the fixed points, this being the smoothest possible shape.

To visualise why the Splines are better than another type of interpolation let us compare the previous image obtained with a B-Spline with the one we would end up using linear interpolation:

What we look for, when we interpolate in this type of application, is a smooth curve which connects the points with the minimum curvature possible. If we compare Linear interpolation with the previous B-Spline it is immediately evident how the Linear interpolation does not provide any curvature and thus the result of the process is just a strict connection between the point which is not what we are aiming for. As for the physical Spline the interpolator Spline, has the property of interpolating two points between each other with a curve that has the least curvature possible. For this peculiar property, the Spline has been chosen among the other possible interpolation scheme.

Implemented Spline

In the Ultrasound library, it is proposed as an interpolation scheme a variant of Catmull-Rom Spline where the knot parameter (alpha in figure 19) is fixed a priori to 0 to avoid the re-computation of the interpolant vector every time a set of four points is passed to the function.

How does Catmull-Rom Spline works? Catmull-Rom splines works by selecting 4 points and find the best point between the median point of the four. Given the following 4 points:

The result of the interpolation between the median points is the following:

As it is easy to see the extreme points are used in the interpolation but not interpolated, and thus to include them in the interpolation process the initial and final point of rf-dataset are augmented with padding.

The formulation of the Catmull-Rom used is the one provided by Barry and Goldman, explained in the following two images: