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

## Image Registration/Matching

Registration is a process by which pixels in two images coincide to the same point in the scene. When we have this, it is possible to fuse the two of them and extract information. Some of the applications of this technique are,
1. Stereo imaging
2. Remote sensing
3. Pattern matching

Consider a template $f$ which is an image of small size and an image $g$ of larger size. Now, we need to know where $f$ is present inside the image $G$. In order words, we need to perform template matching. So, we need different similarity measures for this. So, suppose we need template matching in a particular region $A$. Some examples of metrics can be,
\begin{equation}
\max_A |f(x,y) - g(x,y)|\\ \int \int_A |f(x,y) - g(x,y)|dxdy \\ \int \int_A (f(x,y) - g(x,y))^2dxdy
\end{equation}
These are in analogue cases. In digital form,
\begin{equation}
\max_{i,j \in A} |f(i,j) - g(i,j)|\\ \sum_{i \in A} \sum_{j \in A} [|f(i,j) - g(i,j)|] \\ \sum_{i \in A} \sum_{j \in A} [f(i,j) - g(i,j)]^2
\end{equation}
Regarding the third metric, it is basically the addition of squared error at each point. This can be expanded as,
\begin{equation}
\int\int_A (f(x,y) - g(x,y))^2dxdy = \int\int_A f(x,y)^2dxdy + \int\int_A g(x,y)^2dxdy - 2\int\int_A f(x,y)g(x,y)dxdy
\end{equation}
The LHS is the mismatch measure, whereas the first two terms on RHS are fixed. So, we can take $\int\int_A f(x,y)g(x,y)dxdy$ to be the match measure or similarity measure. The same conclusion can also be drawn using Cauchy - Schwarz inequality, which says,
\begin{equation}
\int\int_A f(x,y)g(x,y)dxdy \leq \sqrt{\int\int_A f(x,y)^2dxdy.\int \int_A g^2(x,y)dxdy}, g(x,y) = cf(x,y)
\end{equation}
Where $c$ is some constant. In digital form,
\begin{equation}
\sum_{i \in A}\sum_{j \in A} f(i,j)g(i,j) \leq \sqrt{\sum_{i \in A}\sum_{j \in A} f(i,j)^2.\sum_{i \in A} \sum_{j \in A} g^2(i,j)}, g(i,j) = cf(i,j) \forall i, j \in A
\end{equation}
This can be written in another form as,
\begin{equation}
\int\int_A f(x,y)g(x + u,y + v)dxdy \leq \sqrt{\int\int_A f(x,y)^2dxdy.\int \int_A g^2(x + u,y + v)dxdy}
\end{equation}
So, similarity between the image and template at a shifted location is calculated. In general,
\begin{equation}
\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty} f(x,y)g(x + u,y + v)dxdy = C_{fg}
\end{equation}
This is known as cross correlation in two dimensions. The normalized cross correlation can be defined as,
\begin{equation}
\frac{C_{fg}}{\sqrt{\int \int_A g^2(x + u,y + v)dxdy}}
\end{equation}
The maximum correlation can be obtained as,
\begin{equation}
\sqrt{\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty} f(x,y)dxdy}, \text{ for some (u,v)}
\end{equation}
Normalized cross correlation is required to avoid false positives that can occur for higher intensity pixels present in the main image, causing a rise in final correlation value. If normalization is done, then the results are valid.

When the degradation is caused by the optical system of camera (they are generally geometric distortions), these can be analyed and corrected by image registration for restoration. We consider the equation to have a polynomial degradation (say from $(x,y) \to (x',y')$) as,
\begin{equation}
x_1 = k_1x + k_2y + k_3xy + k_4 \\ y' = k_5x + k_6y + k_7xy + k_8
\end{equation}
If we find these eight variables, we can find the amount of degradation present. Since there are eight unknows, we need eight equation, therefore, four correspondances.

Sometimes, there is a case, where a particular location will not have intensity at the corresponding pixel. So, we need to go for interpolation techniques in that case.