# 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}\]