Compute Epipolar Line

Epipolar geometry describes how 3D points project into two different camera views and constrains where correspondences can appear in the second image given a point in the first. The key object is the fundamental matrix $F$, which encodes the relative pose and intrinsics of the two (possibly uncalibrated) cameras and maps a point in one image to a line in the other image – the epipolar line.

For a point $\mathbf{p} = (x, y, 1)^T$ in the first image, all possible matching points in the second image must lie on an epipolar line $\mathbf{l'}$ given by

$$\mathbf{l'} = F \cdot \mathbf{p},$$

where $\mathbf{l'} = (a, b, c)^T$ are the line parameters of the 2D line $ax + by + c = 0$ in the second image. This reduces stereo matching from a 2D search (over the whole second image) to a 1D search along that line, which is crucial for depth estimation and many multi-view geometry tasks.

---

1. Background Knowledge

• Homogeneous coordinates 2D image points are represented as $\mathbf{p} = (x, y, 1)^T$ rather than $(x, y)$. This allows points and lines to be handled uniformly: a 2D line is $\mathbf{l} = (a, b, c)^T$, and the incidence relationship “point lies on line” is simply

$$\mathbf{l}^T \mathbf{p} = 0.$$

• Fundamental matrix $F$ The fundamental matrix is a $3 \times 3$ rank-2 matrix that encapsulates the epipolar geometry between two views. For a corresponding pair of points $\mathbf{p}$ (first image) and $\mathbf{p'}$ (second image), the epipolar constraint is:

$$\mathbf{p'}^T F \mathbf{p} = 0.$$

Geometrically, $F$ maps points in one image to epipolar lines in the other:

• $\mathbf{l'} = F \mathbf{p}$: epipolar line in image 2,

• $\mathbf{l} = F^T \mathbf{p'}$: epipolar line in image 1.

• Epipolar lines and stereo matching For a point in the first image, the 3D ray through the camera and that pixel projects into the second image as a line. Any valid match must lie on this line. In stereo depth estimation, this drastically reduces the search space and makes correspondence and depth estimation more tractable.

---

2. Algorithm / Approach

The general pattern for this type of problem is:

1. Input representation Ensure the input point is in homogeneous coordinates and the fundamental matrix is correctly shaped and typed.

2. Linear mapping Apply a simple matrix-vector multiplication:

$$\mathbf{l'} = F \mathbf{p}.$$

3. Interpretation of the result The output $\mathbf{l'} = (a, b, c)^T$ defines the epipolar line equation $ax + by + c = 0$ in the second image. Optionally, normalize it (e.g., so $\sqrt{a^2 + b^2} = 1$) for numerical stability or easy distance computations.

4. Usage Use $\mathbf{l'}$ for:

• Checking if a candidate point $\mathbf{p'}$ lies close to the line ($\mathbf{p'}^T$\mathbf{l'}$\approx 0$),
• Restricting the search for correspondences along this line.

This problem is a direct application of homogeneous-coordinate algebra and fundamental-matrix multiplication.

---

3. Step-by-Step Strategy

Assume you are given:

• A $3 \times 3$ matrix F (fundamental matrix).
• A 2D point in the first image, e.g. (x, y).

Step 1: Convert to homogeneous coordinates

import numpy as np

p = np.array([x, y, 1.0]) # shape (3,)

Step 2: Multiply by the fundamental matrix

l_prime = F @ p # shape (3,)
a, b, c = l_prime # coefficients of the epipolar line

Now l_prime represents the line a * x' + b * y' + c = 0 in the second image.

Step 3: (Optional) Normalize the line

This is helpful if you later compute distances from points to this line.

norm = np.sqrt(a**2 + b**2)
if norm > 0:
 l_prime = l_prime / norm
 a, b, c = l_prime

Step 4: (Optional) Use the line for checks

To check if a point (x2, y2) in the second image lies on / near the epipolar line:

p2 = np.array([x2, y2, 1.0])
distance = abs(l_prime @ p2) # ~0 if on the line, more if off

In the coding problem, you typically just need to output l_prime.

---

4. Common Pitfalls

• Forgetting homogeneous coordinates Using (x, y) instead of (x, y, 1) will cause dimension mismatch or incorrect results. Always use 3-vectors for both points and lines.

• Wrong multiplication order The line in the second image is $F \mathbf{p}$, not $\mathbf{p}^T F$. In code, it should be F @ p (assuming p is a column-like vector).

• Shape issues Make sure:

• F is 3x3,

• p is length 3,

• Matrix multiplication uses the correct operator / function.

• Not handling numeric scaling Lines in homogeneous coordinates are scale-invariant: $(a, b, c)$ and $(k a, k b, k c)$ represent the same line. If you compare or use distances, normalize the line first.

• Confusing image 1 and image 2

• Point in image 1 → line in image 2: l_prime = F @ p.

• Point in image 2 → line in image 1: l = F.T @ p_prime. Mixing these up will give the line in the wrong image.

---

5. Time & Space Complexity

Let:

• $n$ = number of points for which you compute epipolar lines.

For each point, you perform one $3 \times 3$ matrix–vector multiplication:

• Time complexity:

• Per point: $O(1)$ (constant number of multiplications/additions).

• For $n$ points: $O(n)$.

• Space complexity:

• Fundamental matrix and a few 3D vectors: $O(1)$ extra space.

• If you store all $n$ lines, space is $O(n)$; if you compute and output one at a time, it remains $O(1)$.