📘

Essential Matrix Epipolar Constraint Check

MediumGeometry, Linear Algebra 📚 Computer Vision 1

The Essential Matrix $E$ encodes the geometric relationship between two calibrated camera views. For perfectly corresponding points $x_1$ and $x_2$ (in normalized camera coordinates), the epipolar constraint states:

$x_2^T \cdot E \cdot x_1 = 0$

In practice, due to noise, this product is rarely exactly zero. Your task is to compute this constraint value for given point correspondences.

Given:

Essential matrix $E$ (3×3)
Point $x_1$ in normalized coordinates from camera 1: $[x, y, 1]$
Point $x_2$ in normalized coordinates from camera 2: $[x, y, 1]$

Compute: $x_2^T \cdot E \cdot x_1$

Return the scalar result rounded to 6 decimal places.

Example:

Input:

E = [[0, 0, -4], [0, 0, 2], [4, -2, 0]]
x1 = [1, 0, 1]
x2 = [1, 0, 1]

Output:

(0.0, True)

Reasoning:

Compute $E \cdot x_1$ : matrix-vector multiplication
Compute $x_2^T \cdot (E \cdot x_1)$ : dot product
Result is a scalar measuring how well points satisfy epipolar geometry

Constraints:

E is a $3 \times 3$ matrix of floats
x1 and x2 are 3x1 vectors in homogeneous coordinates [x, y, 1]
Use tolerance of 1e-4 to determine if constraint holds
Round scalar result to 4 decimal places

More from Computer Vision 1

Semi-Global Matching Cost AggregationHard Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium

1. Background Knowledge

The essential matrix $E$ describes the geometric relationship between two calibrated cameras observing the same 3D scene point. For corresponding points $x_1, x_2 \in \mathbb{R}^3$ in normalized camera coordinates (homogeneous form $[x, y, 1]^T$ ), the epipolar constraint enforces:

x_2^T E x_1 = 0

This arises from the coplanarity of the baseline (line joining camera centers) and the rays from each camera to the 3D point. $E$ has 5 degrees of freedom (rank-2 matrix with scale ambiguity) and decomposes as $E = [t]_\times R$ , where $R$ is rotation, $t$ is translation direction, and $[t]_\times$ is the skew-symmetric matrix.

Normalized coordinates assume intrinsic matrix $K = I$ , so points are in the camera's canonical frame. Noise makes the constraint residual $|x_2^T E x_1|$ non-zero, used for outlier rejection (e.g., threshold $10^{-4}$ ).

Prerequisites: Matrix multiplication, homogeneous coordinates, basic camera geometry.

2. Algorithm Approach

This is a direct matrix-vector computation:

Compute intermediate vector: $v = E x_1$ (3×3 × 3×1 → 3×1)
Scalar product: $x_2^T v$ (1×3 × 3×1 → scalar)

Libraries: NumPy (np.dot), OpenCV (cv2), MATLAB. No iterative solvers needed—pure linear algebra.

For validation, check if $|x_2^T E x_1| < 10^{-4}$ (constraint holds). Related techniques include 5/8-point algorithms for $E$ estimation from correspondences.

3. Step-by-Step Strategy

import numpy as np

def epipolar_constraint(E, x1, x2):
 # E: 3x3 np.array, x1/x2: 3x1 np.array [x, y, 1]
 v = E @ x1 # Matrix-vector: 3x3 * 3x1 -> 3x1
 residual = x2.T @ v # Vector-vector: 1x3 * 3x1 -> scalar
 return np.round(residual[0, 0], 4) # Round to 4 decimals

Verification:

Ensure $x_1, x_2$ end with 1 (homogeneous).
$E$ shape: (3,3).
Test: Perfect matches yield ~0; noise → small non-zero.

Tolerance check: np.abs(result) < 1e-4

4. Common Pitfalls

Coordinate mismatch: Using pixel coordinates instead of normalized ( $K^{-1} \begin{bmatrix} u \\ v \\ 1 \end{bmatrix}$ ).
Transpose errors: $x_2$ must be row vector ( $x_2^T$ ); NumPy @ handles shapes but verify.
Rounding: Problem says "6 decimals" but constraints "4"—use 4 for output.
Non-homogeneous points: Missing $w=1$ breaks constraint.
Matrix orientation: $E$ must match camera order (not $E^T$ ).
Numerical stability: Ill-conditioned $E$ amplifies noise—use double precision.

5. Time & Space Complexity

Time: $O(1)$ fixed-size (3×3 matrix, 3×1 vectors). Matrix multiply: $3 \times 3 = 9$ flops; dot: 3 flops. Total: $O(1)$ .
Space: $O(1)$ (store 3×3 + 2×3×1 = 15 floats).

Scalability: For $N$ correspondences, $O(N)$ total—used in RANSAC for robust $E$ estimation.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.