Invariant features & image alignment

This page shows how to find the same physical spot in two photos. It then shows how to compute the geometric transformation (translation, rotation, affine, homography) that aligns the photos. The page covers the feature pipeline, the matching metrics (Euclidean, SSD, SAD, NCC, Hamming) and the ratio test. It also covers the full 2D transformation hierarchy with matrices and degrees of freedom.

Feature matching workflow

Image correspondence means finding points or features in two images that show the same physical location or scene element. An example is the same corner of a building seen from two viewpoints. The standard pipeline has three stages:

1. Feature detection: find the interesting points (keypoints).
2. Feature description: represent each point with a vector that summarises the local patch.
3. Feature matching: find which feature in image 1 matches which feature in image 2. Compare the descriptors with Euclidean distance, SSD, NCC, or Hamming distance.

The simplest idea is to scan with a template and compute the SSD or correlation of raw pixel intensities. To make candidate matches, take the patches with the most similar appearance (lowest SSD).

Patch matching and descriptors

Patch matching compares small image regions around a point of interest. A patch is a small window of pixel intensities. Compare a patch from image 1 with the candidate patches in image 2 with a matching metric. Select the best candidate.

To compare patches, convert each patch into a descriptor. Flatten the patch row by row:

Keypoints and descriptors

Keypoints are distinctive points that we can identify across different images. A keypoint gives only a location $(x,y)$, which is not enough for matching. The descriptor is a numerical representation of the local appearance around the keypoint:

Keypoint $\rightarrow$ local neighbourhood (patch) $\rightarrow$ descriptor. Similar features must produce similar descriptors.

• Detectors from the slides: Harris corner detector (finds corners) and SIFT (finds distinctive keypoints across different scales).
• Descriptors: Census, HOG, ORB, BRIEF, BRISK, FREAK, SIFT.
• Distance functions to compare descriptors: Euclidean, SSD, SAD, NCC, Hamming (for binary descriptors).

Harris corners and SIFT in a nutshell (standard background)

Why corners? A flat region looks the same when you slide a window in any direction, so it is not useful. An edge looks the same when you slide along the edge, so it is ambiguous. A corner changes in every direction, so we can localise it exactly.

SIFT (Scale-Invariant Feature Transform) has three steps:

1. Find the extrema of the Difference of Gaussians across scale space. This gives keypoints with a location and a scale.
2. Assign a dominant orientation from a gradient histogram (rotation invariance).
3. Build a descriptor from gradient-orientation histograms in a $4\times4$ grid of cells with 8 bins each. This gives a $4\times4\times8=128$-dimensional vector. Normalise the vector for robustness to illumination.

Compare SIFT descriptors with Euclidean distance.

Harris is rotation invariant but not scale invariant. SIFT is invariant to scale and rotation. It is robust to moderate illumination and viewpoint change.

Brute-force matching and nearest neighbour

The naive strategy assumes that the detected points and their descriptors are known. Compare each feature in $I_1$ with all features in $I_2$ ($N^2$ comparisons for $N$ features per image). Pick the pair with the minimum distance, that is, the closest descriptor.

Euclidean distance

Euclidean distance is the straight-line distance between two descriptor vectors. A smaller distance means more similar. The pair with the smallest distance is the closest match.

Ratio test

The ratio test rejects ambiguous matches. Sometimes the closest candidate is almost as close as the second-closest. Then the match is unreliable, because the descriptor is not distinctive. A good match must be much closer than the runner-up.

Patch similarity metrics: SSD, SAD, NCC

In the slides, $H$ and $F$ denote the left and right patches (or descriptors). The pair $(u,v)$ indexes the pixels in a $(2k+1)\times(2k+1)$ window. The metrics apply to 2D patches or 1D descriptors.

Sum of squared differences (SSD)

Advantages: it is simple and computationally efficient. Limitation: it is sensitive to changes in brightness and contrast.

Sum of absolute differences (SAD)

Normalized cross correlation (NCC)

Advantage: NCC is more robust than SSD to additive brightness changes, because it subtracts the mean. The normalisation also handles contrast scaling. Limitation: viewpoint, rotation, scale and large appearance changes still affect it.

Worked example: SSD, SAD and NCC on the same data

Binary descriptors and Hamming distance

Binary descriptors (BRIEF, ORB, BRISK, FREAK, Census) store each feature as a string of bits. Each bit is the result of a simple intensity comparison. The descriptors are tiny and very fast to compare.

Image transformation and alignment

A grayscale image is a 2D function $f(\mathbf x)$. Here $\mathbf x=(x,y)^T$ is the spatial position, $f(\mathbf x)$ is the intensity at that position, and the domain $D$ is the set of all valid positions.

There are two kinds of image transformation:

A geometric transformation changes the position, orientation or shape of pixels with a mathematical rule. The rules are rotation, translation, uniform scaling, non-uniform scaling, reflection and shearing.

The alignment problem

The input is a set of matched feature points $\{\mathbf x_i,\mathbf x_i'\}$ (a point in one image and its partner in the other). A transformation function $\mathbf x'=f(\mathbf x;\mathbf p)$ with parameters $\mathbf p$ is also given. Find the best estimate of the parameters $\mathbf p$. This means: fit the parameters of a transformation to a set of matching feature pairs (correspondences). The choice of $f$ (translation, affine, homography...) depends on how the two views are related.

Parametric (global) warping

A transformation $T$ is a coordinate-changing machine: $\mathbf p'=T(\mathbf p)$. It is global if it is the same for every point and a few numbers (parameters) describe it. Examples: translation, rotation, aspect change, affine, perspective. A matrix represents it: $\mathbf p'=M\mathbf p$.

2x2 linear transformations

Scaling

Shearing

Shearing slants the shape. It shifts one coordinate in proportion to the other. It changes the shape of an object, but parallel lines remain parallel.

Rotation about the origin

Derivation from polar coordinates (slide). Write $x=r\cos\phi$, $y=r\sin\phi$. After the rotation by $\theta$: $x'=r\cos(\phi+\theta)$, $y'=r\sin(\phi+\theta)$. Expand with trig identities: $x'=r\cos\phi\cos\theta-r\sin\phi\sin\theta$, $y'=r\sin\phi\cos\theta+r\cos\phi\sin\theta$. Substitute $x=r\cos\phi$, $y=r\sin\phi$ to get the formulas above.

Translation and homogeneous coordinates

Translation by $(t_x,t_y)$: $x'=x+t_x$, $y'=y+t_y$. Example from the slide: $P=(2,3)$ translated by $(4,2)$ gives $P'=(2+4,3+2)=(6,5)$.

This operation needs the addition of a constant. A general $2\times2$ product gives $x'=ax+by$, $y'=cx+dy$. So $x',y'$ depend only on $x,y$ and have no constant term. Hence we cannot write translation as a $2\times2$ matrix.

Fix: homogeneous coordinates. Add a third coordinate: the point $(x,y)$ becomes $(x,y,1)^T$. To convert back from $(x,y,w)^T$, divide by $w$: $(x/w,\ y/w)$.

All basic transforms as 3x3 matrices

To combine scaling, rotation, shearing and translation in one matrix, use homogeneous coordinates.

Matrix composition and order

Do not apply the transformations one after another, $P'=T_2(T_1P)$. Combine them: $P'=(T_2T_1)P$, so the combined matrix is $T=T_2T_1$. If $T_1$ is applied first and $T_2$ second, the later transform is on the left. Example chain: $\mathbf p'=\text{translation}(t_x,t_y)\cdot\text{rotation}(\theta)\cdot\text{scale}(s,s)\cdot\mathbf p$. It scales first, then rotates, then translates. Order matters: $T_2T_1\ne T_1T_2$ in general, because matrix multiplication is not commutative.

Degrees of freedom and the transformation hierarchy

The degree of freedom (DOF) is the number of independent parameters that define a transformation.

• General $2\times2$ linear transformation $\begin{bmatrix}a&b\\c&d\end{bmatrix}$: 4 independent parameters, so 4 DOF. It represents combinations of scaling, rotation and shearing.
• Scaling $\begin{bmatrix}s_x&0\\0&s_y\end{bmatrix}$: 2 parameters, 2 DOF.
• Rotation: one parameter $\theta$ fixes all four entries (for $30^\circ$: $0.866,-0.5,0.5,0.866$), so 1 DOF.
• Translation: $(t_x,t_y)$, 2 DOF.

Affine transformation

An affine transformation combines a general linear transformation (scaling, rotation, shearing) with a translation. It has the form below, with bottom row $(0,0,1)$.

Properties of affine transforms (slide):

• The origin does not necessarily map to the origin.
• Lines map to lines.
• Parallel lines map to parallel lines.
• Ratios (of lengths along a line, and of areas) are preserved.
• Compositions of affine transforms are affine.
• A square becomes a parallelogram.

Projective transformation (homography)

A projective transformation extends the affine transformation with perspective effects. It is also called a homography. It has the form below, with a full $3\times3$ matrix. The last row is not restricted.

Write $H=\begin{bmatrix}a&b&t_x\\c&d&t_y\\g&h&1\end{bmatrix}$. The affine part is translation, rotation, scaling and shearing. The perspective part $(g,h)$ lets parallel lines converge and introduces perspective distortion. $H$ becomes affine when $g=h=0$.

Properties of projective transforms (slide):

• The origin does not necessarily map to the origin.
• Lines map to lines.
• Parallel lines do not necessarily remain parallel. They can meet at a vanishing point, like railway tracks that are parallel in the world but converge in the image.
• Compositions of projective transforms are projective.

The rigid and similarity rows are standard background. The slides cover scaling 2, rotation 1, linear 4, affine 6, projective 8. Each point pair $(\mathbf x,\mathbf x')$ gives 2 equations. So the minimum number of correspondences is DOF$/2$ rounded up.

Estimating the transformation from correspondences

This section is standard background. It completes the "alignment" story from the slides.

Affine from point pairs (least squares)

Each pair $(x,y)\to(x',y')$ gives two linear equations in the 6 unknowns:

$$\begin{bmatrix}x&y&1&0&0&0\\0&0&0&x&y&1\end{bmatrix}\begin{bmatrix}a\\b\\t_x\\c\\d\\t_y\end{bmatrix}=\begin{bmatrix}x'\\y'\end{bmatrix}$$

Three non-collinear pairs give an exact solution. More pairs give an over-determined system. Solve it by least squares.

Homography from 4 point pairs (DLT)

Set $h_{33}=1$. A pair $(x,y)\to(x',y')$ then means $x'=\dfrac{h_{11}x+h_{12}y+h_{13}}{h_{31}x+h_{32}y+1}$, and similarly for $y'$. Multiply out to get two linear equations in the eight unknowns:

$$h_{11}x+h_{12}y+h_{13}-h_{31}xx'-h_{32}yx'=x'$$ $$h_{21}x+h_{22}y+h_{23}-h_{31}xy'-h_{32}yy'=y'$$

Four pairs give 8 equations for 8 unknowns. With more pairs, stack the equations into $A\mathbf h=\mathbf 0$ (no $h_{33}=1$ assumption). Take the SVD smallest singular vector (Direct Linear Transform, DLT). With outlier matches, use RANSAC around this method: fit on 4 random pairs, repeat, and keep the model with the most inliers.

Quick self-test