# Epipolar geometry and the fundamental matrix

###### tags: `cvdl2020`

## What is epipolar gemoetry ?
Epipolar geometry is the **intrincic projective geometry** between two views. It's independent of scene structure, and only depends on the **camera's internal parameters** and **relative pose**.

The epipolar gemetry between two views is essentially the geometry of the **intersection of the image planes** with the **pencil of planes** with the pencil of planes having the **baseline as axis**. Notice the **baseline is the line joining the camera centers**.

## Epipolar geometry
Suppose a point $X$ in 3D world is imaged in two views, at $x$ in the first view, and $x'$ in the second. What's the relation between the corresponding image points $x$ and $x'$ ?


Notice the image points $x,x'$, and 3D world point $X$, and the camera center are **epipolar**, these three points form a plane $\pi$.
:::info
The rays back-projected from $x$ and $x'$ intersect at 3D point $X$, and the rays are coplanar, lying in $\pi$.
:::

Suppose we only know $x$, we may ask how the corresponding point $x'$ is constrained.

The plane $\pi$ is determined by the baseline and the ray defined by $x$. We then know that the ray corresponding to the unknown point $x'$ lies in plane $\pi$.

Hence, the point $x'$ lies on the line of intersection $l'$ of $\pi$ with the second image plane.

This line $l'$ is the image in the second view of the ray back-projected from $x$. It is the **epipolar line** corresponding to $x$.

In terms of a stereo correspondence algorithm the benefit it that the search for the point corresponding to $x$ need not cover the entire image plane but can be restricted to the line $l'$.


:::info
Given different 3D point $X$ the epipolar plances "rotate" about the baseline. This family of planes is known as an **epipolar pencil**. All epipolar lines intersect at the **epipole**
:::

:::info
The **epipole** is the point of intersection of the line joining the camera centers (baseline) with the image plane. The epipole is the image in one view of the camera center of the other.
:::

:::info
An **epipolar plane** is a plane containing the baseline.
:::

:::info
An **epipolar line** is the intersection of an epipolar plane with the image plane. All epipolar lines intersect at the epipole. An epipolar plane intersects the left and right image planes in epipolar lines, and defines the correspondence between the lines.
:::

## Fundamental matrix $F$
The fundamental matrix is the algebric representation of epipolar geometry.

### Overview
Given a pair of images, it was seen that for each point $x$ in one image, there exists a corresponding epipolar line $l'$ in the other image. Any point $x'$ in the second image matching the point $x$ must **lie on the epipolar line $l'$**.

The epipolar line is the projection in the second image of the **ray from the point $x$ through the camera center $C$ of the first camera**.

Thus, there's a map $$x \rightarrow l'$$ from a point in one image to its corresponding epipolar line in the other image.

It turns out that **this mapping is a (singular) correlation**, that is a projective mapping from poinst to lines, which is represented by a matrix F, the **fundamental matrix**.

### Geometric derivation

There're two steps to derive **the mapping from a point in one image to a corresponding epipolar line in the other image**

- **Point transfer via a plane**
- In this step, the point $x$ is mapped to some point $x'$ in the other image lying on the epipolar line $l'$
- Consider a plane $\pi$ in space NOT passing through either of the two camera centers. （不再兩相機的終點連線上）
- The ray through the first camera cneter corresponding to the point $x$ meets the plane $\pi$ in a point $X$.
- This point $X$ is then projected to a point $x'$ in the second image.
- Since $X$ lies on the ray corresponding to $x$, the projected point $x'$ must lie one the epipolar line $l'$ corresponding to the image of this ray.
- The point $x$ and $x'$ are both images of the 3D point $X$ lying on a plane.
- The set of all such points $x_i$ in the first image and the corresponding point $x_i'$ in the second image are **projectively equivalent**.
- Since they are each projectively equivalent to the planar point set $X_i$. Thus, there is a **2D homography $H_{\pi}$ mapping $x_i$ to $x_i'$**

- **Constructing the epipolar line**
- Given the point $x'$, the epipolar line $l'$ passing through $x'$ and the epipole $e'$ can be written as $l'=e' \times x'$
- Since $x'$ can be written as $x'=H_{\pi}x$, we have $$l' = e' \times H_{\pi} x = Fx$$ where define the fundamental matrix as $F=e' \times H_{\pi}$

### Algebric interpretation
:::success
The fundamental matrix F may be written as $F=e' \times H_{\pi}$ is the transfer mapping from one image to another via nay plane $\pi$. Since $e'$ has rank 2 and $H_{\pi}$ has rank 3, $F$ is a matrix of rank 2. (by 維度定理)
:::

:::danger
$F$ represents a mapping from the 2-dimensional projectie plane $P^2$ of the first image to the **pencil** of epipolar lies through the epipole $e'$. Thus, it represents a mapping from a 2-dimensional onto a 1-dimensional projective space, and hence must have rank 2.
:::

### Correspondence condition
:::success
The fundamental matrix satisfies the condition that for any pair of corresponding points $x \leftrightarrow x'$ in the two images $$x'^{T}Fx=0$$
:::

This is true because if points $x$ and $x'$ are corresponded, then $x'$ lies on the epipolar line $l'=Fx$ corresponding to the point $x$. In other words $0=x'^{T}l'=x'^{T}Fx$. Conversely, if image points satisfy the relation $x'Fx=0$ then the rays defined by these points are coplanar.

The importance of the relation of this result is that it gives a way of characterizing the fundamental matrix WITHOUT reference to the camera matrices. This enables F to be comptued from image correspondences ALONE.

### Properties of the fundamental matrix
Suppose we have two images acquired by cameras with non-conincident centers, the the **fundamental matrix F** is the unique 3x3 **rank 2 homogeneous matrix** which satisfies $$x'Fx=0$$ for all corresponding points $x \leftrightarrow x'$.

The important properties of fundamental matrix are listed below:
- Transpose
- If F is the fundamental matrix of the pair of cameras $(P,P')$, then $F^T$ is the fundamental matrix of the pair in the opposite order $(P',P)$
- Epipolar lines
- For any point $x$ in the first image, the corresponding epipolar line is $l'=Fx$. Similarly, $l=F^T x'$ represents the epipolar line corresponding to $x'$ in the second image.
- Epipole
- For any point $x$ the epipolar line $l'=Fx$ contains the epipole $e'$.
- Thus, $e'$ satisfies $$e'^{T}(Fx) = (e'^{T}F)x=0$$ for all $x$. It follows that $e'^{T}F = 0$, then $e'$ is the left null vector of matrix $F$/
- Similarly, $Fe=0$ so $e$ is the right null vector of matrix $F$
- F has 7 dof
- A 3x3 homogeneous matrix has **8** independent ratios (nine elements). However, matrix $F$ also satisfies the constraint $det F = 0$ whcih removes **one dof**

:::success
F is a rank 2 homogeneous matrix with 7 dof
:::

:::success
If $x$ and $x'$ are corresponding image points, then $x'^{T}Fx = 0$
:::

:::success
Epipolar lines:
- $l'=Fx$ is the epipolar line corresponding to $x$
- $l=F^{T}x'$ is the epipolar line corresponding to $x'$
:::

:::success
Epipoles:
- $Fe=0$
- $F^{T}e'=0$
:::