Interpolation

What if, for reasons that will become apparant later, we want to know the values of points in between the sampled points (pixels) available in the image? Mathematically: given only image \(f\), how do we define everything in between, for example, \(f(5,5)\) and \(f(5,6)\)?

Nearest Neighbor Interpolation

Just find the nearest sampled point (pixel) and use that. For mathematical notation we can use the floor operation:

\[\hat f (x) = f(\lfloor x + \frac{1}{2} \rfloor) \]
Linear interpolation

Go about it in a bit more of a sophisticated way: fit a linear function (of the form \(ax + b\)) to the gap and fill in the desired value. Between two sample points next to each other, \(k\) and \(k+1\):

\[\hat f(x) = f(k) + (x-k) \left(f(k+1) - f(k)\right) \]

Although it would not happen in images, if the sample points are not adjacent, \(k_1\) and \(k_2\), we would have to divide out the difference to get a proper rise over run multiplier for the slope:

\[\hat f(x) = f(k_1) + (x-k_1) \frac{f(k_2) - f(k_1)}{k_2 - k_1} \]
Cubic Interpolation

Extending the idea of fitting a function to nearby points, instead of taking only 2 sample points to fit a linear equation, you may take 4 and fit a cubic one;

\[\hat f (x) = ax^3 + bx^2 + cx + d \]

To simplify finding the four unknowns (\(a, b, c, d\)) we set \(x=k\) and have the equation:

\[\begin{bmatrix}f(k-1)\\f(k)\\f(k+1)\\f(k+2)\end{bmatrix} = \begin{bmatrix} -1^3 & -1^2 & -1 & 1\\ 0 & 0 & 0 & 1\\ 1^3 & 1^2 & 1 & 1\\ 2^3 & 2^2 & 2 & 1\\ \end{bmatrix} \begin{bmatrix}a\\b\\c\\d\end{bmatrix}\]

Solving this system of equations we get:

\[\begin{aligned} a &= \frac{1}{6}\left(-f(k-1) + 3f(k) - 3f(k+1) + f(k+2)\right)\\ b &= \frac{1}{2}\left(f(k-1) - 2f(k) + f(k+1)\right)\\ c &= \frac{1}{6}\left(-2f(k-1) - 3f(k) + 6f(k+1) - f(k+2)\right)\\ d &= f(k) \end{aligned}\]

And now we have our cubic function \(\hat f\) in which to plug in our desired point \(x\).

Bilinear Interpolation

We need some way to interpolate points not just on a line between 2 pixels, but in 2D between 4 pixels. Bilinear interpolation is effectively double linear interpolation (hence the name); first computing the blue values, and then interpolating again to find the value at the green point.

For images (where nearby points are never further than \(1\) away), to interpolate a point \((x=i+a, y=j+b)\) then:

\[\begin{aligned} \hat f(x,y) &=(1-a)(1-b)\ f(i,j)\\ &+ (1-a)b\ f(i,j+1)\\ &+ a(1-b)\ f(i+1,j)\\ &+ ab\ f(i+1,j+1) \end{aligned}\]