The Correspondence Problem

Constraints

Apply constraints to reduce the number of possible correspondences.

Uniqueness Constraint

For opaque objects, each point in the left image should have at most one match in the right image.

For transparent objects, two features may be visible in the right image but instantaneously aligned in the left image.

Ordering Constraint

Corresponding points lying on the surface of an opaque object will be ordered identically in the left & right images.

Forbidden Zone

Disparity Gradient Constraint

Disparity: difference in location between corresponding points. If the surface is smooth, then disparities must be locally smooth. Impose a limit on the allowable spatial derivatives of disparity.

Normalized Cross-Correlation (NCC)

Given a feature point $$x_i$$ in an image, a patch $$P(x_i)$$ centered at $$x_i$$ defined, then its NCC with a patch $$P(x'_j)$$ centered at each feature point $$x'_j$$ in another image:

$$ NCC(x_i, x'_j) = \frac{(P(x_i) - \bar{P}(x_i)) \cdot (P(x'_j) - \bar{P}(x'_j))}{|P(x_i) - \bar{P}(x_i)| |P(x'_j) - \bar{P}(x'_j)|}

Best match to $$x_i$$ is the feature point $$x'_j$$ that maximizes NCC.

Problem
- Unreliable since image intensities are viewpoint dependent

Dynamic Programming

Minimize a cost function for primitive matching between images.

Corresponding Epipolar Lines

Identify edge pixels on each line
Match intervals between them

With the intensity profiles of the epipolar lines & the edge pixels, find a sequence of segments from start to end that minimizes the cost function:

Apply constraints to restrict the kinds of paths allowed:

Ordering constraint
- Paths are monotonous
  - (i, i') and (j, j') are successive points on the path iff i < j and i' < j' or i = j and i' < j' or i < j and i' = j'
Uniqueness constraint
- (i, i') and (j, j') are successive points on the path iff i < j and i' < j'

Cost $$c(m, m')$$ of a segment between two points should measure:

Similarity of features at the edge pixels
1. E.g. orientation, intensity contrast, etc.
Similarity of intensities & lengths of the intervals

Then recursively define cost $$C(m)$$ of path from $$m_s$$ to $$m$$ :

$$ C(m) = min_{p \in V_m}(C(p) + c(p, m))

where $$V_m = {(i-1, i'-1), (i-1, i'), (i, i'-1)}$$.

The recursive structure replaces the minimization of a function of MN - 2 variables by a minimization of MN-1 functions of 1 variable.

Structure Recovery

Unguided matching
1. With local search & NCC, obtain a small number of seed matches
Fundamental matrix estimation
1. With seed matches & robust algorithms (e.g. RANSAC), estimate $$F$$ to restrict matches to a narrow band around epipolar lines
  1. Matches not consistent are outliers
Guided matching
1. With estimated $$F$$ & constraints & search algorithm (e.g. dynamic programming), obtain a large number of matches
Fundamental matrix re-estimation
1. With large number of matches & robust algorithms, re-estimate $$F$$
Camera poses recovery
1. With $$F$$, construct $$E$$, decompose into $$R$$ and $$T$$
Structure recovery
1. Triangulate matched points

Affine Stereo

Affine camera: depth variations in the scene are small compared with the viewing distance.

$$ \begin{bmatrix} ui \ v_i \end{bmatrix} = \begin{bmatrix} p{00} & p{01} & p{02} & p{03} \ p{10} & p{11} & p{12} & p_{13} \end{bmatrix}\begin{bmatrix} X_i \ Y_i \ Z_i \ 1 \end{bmatrix}

$$ Each observed point provides a pair of equations in three unknowns.

With 2 calibrated affine cameras, recover the structure by linear least squares:

$$ \begin{bmatrix} p{00} & p{01} & p{02}\ p{10} & p{11} & p{12}\ p'{00} & p'{01} & p'{02}\ p'{10} & p'{11} & p'{12}\ \end{bmatrix}\begin{bmatrix} Xi \ Y_i \ Z_i \end{bmatrix} = \begin{bmatrix} u_i - p{03}\ vi - p{13}\ u'i - p'{03}\ v'i - p'{13} \end{bmatrix}

Epipolar Constraint

W.l.o.g. assume left camera is aligned with the world coordinate system, i.e. $$R = I$$.

The left camera matrix reduces to:

$$ \begin{bmatrix} u \ v \end{bmatrix} = \begin{bmatrix} p{00} & 0 & 0 & p{03} \ 0 & p{11} & 0 & p{13} \end{bmatrix}\begin{bmatrix} X \ Y \ Z \ 1 \end{bmatrix}\ X = \frac{u - p{03}}{p{00}}\ Y = \frac{v - p{13}}{p{11}}

Hence $$X$$ and $$Y$$ can be substituted into the right camera matrix, which arrives at:

$$ \begin{bmatrix} u' \ v' \end{bmatrix} = \begin{bmatrix} p'{00}\frac{u - p{03}}{p{00}} + p'{01}\frac{v - p{13}}{p{11}} + p'{03} \ p'{10}\frac{u - p{03}}{p{11}} + p'{01}\frac{v - p{13}}{p{11}} + p'{13} \end{bmatrix} + Z\begin{bmatrix} p'{02} \ p'{12} \end{bmatrix}

$$ i.e.

$$ w' = a(w) + Zb

Properties
- $$b$$ gives the orientation of the epipolar line
- Since $$b$$ is independent of $$w$$, all epipolar lines are parallel under affine stereo

Stereo Vision III