Compute Epipolar Line

easyFREEMultiple CamerasComputer Vision 1

Given a fundamental matrix $F$ and a point $\mathbf{x}_1 = [x, y, 1]^T$ in image 1, compute the corresponding epipolar line $\mathbf{l}_2$ in image 2.

The epipolar line is computed as:

$\mathbf{l}_2 = F \cdot \mathbf{x}_1$

where $\mathbf{l}_2 = [a, b, c]^T$ represents the line $ax + by + c = 0$ in image 2.

Normalization: The line coefficients should be normalized so that:

$\sqrt{a^2 + b^2} = 1$

This ensures the coefficients represent a proper line equation where $c$ gives the signed distance from the origin to the line.

Epipolar lines are fundamental in stereo vision -- they constrain where a corresponding point can appear in the second image, reducing the search from 2D to 1D.

Round each coefficient to 4 decimal places.

Example

Input

F = [[0, 0, 0],
     [0, 0, -1],
     [0, 1, 0]]
x1 = [10, 20, 1]

Output

[0.0, -1.0, 20.0]

Reasoning

F is the $3 \times 3$ fundamental matrix linking the two views; x1 $= [10, 20, 1]^T$ is pixel $(10, 20)$ of image 1 in homogeneous form.
Each line coefficient is one row of $F$ dotted with $\mathbf{x}_1$ : row 1 gives $0$ ; row 2 gives $(-1) \cdot 1 = -1$ ; row 3 gives $1 \cdot 20 = 20$ . So $\mathbf{l}_2 = [0, -1, 20]^T$ .
Normalization factor: $\sqrt{0^2 + (-1)^2} = 1$ , so dividing $a$ , $b$ , $c$ by it changes nothing here. A raw line $[0, -2, 40]$ would shrink to the same $[0, -1, 20]$ .
The output [0.0, -1.0, 20.0] is the line $-y + 20 = 0$ , i.e. the horizontal row $y = 20$ , at distance $|c| = 20$ from the origin.
Notice it is the same row the point sits on in image 1: this $F$ describes a rectified side-by-side stereo pair, where matches lie on the same scanline.

Constraints

F: 3x3 fundamental matrix as list of lists
x1: Point in image 1 as [x, y, 1] (homogeneous coordinates)
Return: Normalized line coefficients [a, b, c] as a list
Normalize so that sqrt(a^2 + b^2) = 1
Round to 4 decimal places

Learn this in

Epipolar Geometry & Stereo Vision3D Computer Vision

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium

Concept primer

Background Knowledge

The problem revolves around the concept of epipolar lines in computer vision, specifically in the context of stereo vision. Epipolar lines are used to constrain the search for corresponding points between two images taken by different cameras. The fundamental matrix $F$ plays a crucial role here, as it encapsulates the geometric relationship between the two cameras. The fundamental matrix is a $3 \times 3$ matrix that can be used to map points from one image to their corresponding epipolar lines in the other image.

The equation $\mathbf{l}_2 = F \cdot$ \mathbf{x} $_1$ is crucial, where $\mathbf{x}_1$ is a point in the first image, and $\mathbf{l}_2$ is the epipolar line in the second image. This equation essentially maps a point in one image to a line in the other, which is the core concept behind epipolar geometry. Understanding how to manipulate and apply this equation is key to solving the problem.

In terms of normalization, ensuring that $\sqrt{a^2 + b^2} = 1$ is important because it standardizes the representation of the line. This normalization step is about making the coefficients of the line equation $ax + by + c = 0$ have a length of 1, which is a common requirement in many geometric computations to avoid scale ambiguities and to ensure that $c$ correctly represents the distance from the origin to the line.

Algorithm/Approach

The general approach to solving this problem involves matrix multiplication and vector normalization. The algorithm pattern includes:

Loading or defining the fundamental matrix $F$ and the point $\mathbf{x}_1$ .
Performing the matrix multiplication $F \cdot$ \mathbf{x} $_1$ to find the epipolar line $\mathbf{l}_2$ .
Normalizing the coefficients of $\mathbf{l}_2$ to satisfy the condition $\sqrt{a^2 + b^2} = 1$ .

Step-by-Step Strategy

Define the Fundamental Matrix $F$ : Ensure $F$ is a $3 \times 3$ matrix.
Define the Point $\mathbf{x}_1$ : Represent $\mathbf{x}_1$ as a $3 \times 1$ vector $[x, y, 1]^T$ .
Matrix Multiplication: Compute $\mathbf{l}_2 = F \cdot$ \mathbf{x} $_1$ to get a $3 \times 1$ vector $[a, b, c]^T$ .
Normalization: Calculate the magnitude of the vector $[a, b]^T$ as $\sqrt{a^2 + b^2}$ .
Scale the Vector: Divide each component of $\mathbf{l}_2$ by the magnitude calculated in step 4 to normalize it.
Rounding: Round each coefficient $a$ , $b$ , and $c$ to 4 decimal places.

Common Pitfalls

Matrix Dimensions: Ensure that the dimensions of $F$ and $\mathbf{x}_1$ are correct for the multiplication.
Normalization: Remember to normalize only the $a$ and $b$ coefficients and not the $c$ coefficient, as $c$ represents the distance from the origin to the line.
Rounding Errors: Be mindful of the rounding step, as it can affect the precision of the final result.

Time & Space Complexity

Time Complexity: The time complexity is $O(1)$ because the operations involve a fixed number of matrix multiplication and vector normalization steps, regardless of the input size.
Space Complexity: The space complexity is also $O(1)$ , as the space required does not grow with the size of the input; it only involves storing the fundamental matrix, the point, and the resulting epipolar line.

solution.py

Python 3.13

Test results