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