---
tags: Digital Image Processing
disqus: hackmd
---
# Part 5

## Interpolation and Resampling

Consider a $3 \times 3$ sized image with elements $I_{ij}$, where $i, j \in \{0,1,2\}$. What if the image has to be scaled by some constant (say, 3)? In such a case, the $3 \times 3$ image is converted to $9 \times 9$ image, by $S_x = S_y = 3$. Therefore,

\begin{equation}
\begin{bmatrix}
\hat{x} \\ \hat{y}
\end{bmatrix}=
\begin{bmatrix}
S_x & 0 \\ 0 & S_y
\end{bmatrix}
\begin{bmatrix}
x \\ y
\end{bmatrix}
\end{equation}
After this, the pixels shall be scattered by multiples of $3$, to make the overall image $9 \times 9$. It is seen that some of the pixel locations have void and don't denote any form of intensity. They are like padding to each scaled pixel. Not only scaling operations. In case the image is rotated by some angle. In that case, some of the pixel locations have voids.
\begin{equation}
\begin{bmatrix}
\hat{x} \\ \hat{y}
\end{bmatrix}=
\begin{bmatrix}
\cos \theta & \sin \theta \\ -\sin \theta & \cos \theta
\end{bmatrix}
\begin{bmatrix}
x \\ y
\end{bmatrix}
\end{equation}
However another problem in case of rotation is that in case of rotation of pixels, the coordinate values are not discrete integer values, therefore, they are truncated to the lower integer value. This also results in loss of some pixel values since some of them might occupy the same pixel location.

For these cases, now, the intensity values to be filled must be approximated in such a way that when the inverse transformation is performed, the padded image shall yield the original image. Here comes the idea of interpolation, where those voids shall be padded by interpolating. After interpolation, the approximate intensity value should be calculated to approximate the intensity value at that point.

### Properties of Interpolation

1. Finite region of support.
2. Smooth Interpolation.
3. Shift Invariant.

One of the example of such a function is known as B - spline function. The function is defined as,

\begin{equation}
x(t) = \sum_{i = 1}^{n}p_i B_{i,k}(t)
\end{equation}
$n + 1$ are the number of samples. $p_i$ are the control values and $B_{i,k}$ is the normalized B - spline of order $k$. Also,
1. $B_{i,1}(t) = 1$, for $t_i \leq t \leq 1$, otherwise it is $0$. The higher order B - splines can be found out as,

\begin{equation}
B_{i,k}(t) = \frac{(t - t_i)B_{i,k - 1}(t)}{t_{i + k - 1} - t_i} + \frac{(t_{i + 1} - 1)B_{i + 1,k - 1}(t)}{t_{i + k} - t_{i + 1}}
\end{equation}

So, if the value of $B_{0,k}(t)$ is known, in that case, the value of $B_{i,k}(t)$ can be calculated as $B_{0,k}(t - i)$.

We can define $B_{0,1}(t) = 1 \forall \text{ }0 \leq t \leq 1$ and $0$ otherwise. Similarly, $B_{0,2}(t) = t \forall \text{ } 0 \leq t \leq 1$, $2 - t \forall \text{ } 1 \leq t < 2$ and $0$ otherwise.

Similarly, $B_{0,3}(t) = \frac{t^2}{2} \forall \text{ }0 \leq t \leq 1$, $-t^2 + 3t - 1.5 \forall \text{ }1 \leq t \leq 2$, $\frac{(3 - t)^2}{2} \forall \text{ }2 \leq t < 3$ and $0$ otherwise.

Similarly, $B_{0,4}(t) = \frac{t^3}{6} \forall \text{ }0 \leq t \leq 1$, $\frac{-3t^3 + 12t^2 - 12t + 4}{6} \forall 1 \leq t \leq 2$, $\frac{3t^3 - 24t^2 + 60t - 44}{6} \forall \text{ } 2 \leq t \leq 3$, $\frac{(4 - t)^3}{6} \forall 3 \leq t < 4$ and $0$, otherwise. Here $k$ is the order of the B - spline function.

Their normalized form is shown in the figure above.

For constant B - spline,
For the linear B - spline,
However, it is seen that for a point given, weight given to the before previous point is given more than that of the just previous case, which does not seen very practical. Therefore, instead of taking the usual formula, some shift can be done as,
\begin{equation}
x(t) = \sum_{i = 1}^{n}p_i B_{i-s,k}(t)
\end{equation}
Where $s = 0.5$ for $k = 1$, $s = 1$ for $k = 2$, $s = 2$ for $k = 4$. Here, it is seen that $k = 3$ interpolation has not been seen since it produces asymmetric interpolation.

Therefore, if this is performed for cubic interpolation case $k = 4$, the function will look somewhat like,

In case of an image, consider the two-dimensional case. Instead of performing constant, linear or cubic interpolation, we perform the bilinear or bicubic interpolation.
The figure below shows the case for constant interpolation for images,