💻 Best viewed on desktop (1920×1080 or larger) for optimal experience

← Back to Projects


Project 3: (Auto)stitching and Photo Mosaics

CS 180 Project 3 · Song-Ze Yu

Part A: Image Warping and Mosaicing

Manually select correspondences, compute homographies, warp images, and blend them into seamless panoramas.

Part B: Feature Matching for Autostitching

Automatically detect Harris corners, extract MOPS descriptors, match features using Lowe's ratio test, and robustly compute homographies with RANSAC.

Part A.1: Shoot the Pictures

I captured two sets of images with projective transformations by fixing the center of projection (COP) and rotating the camera while keeping the same position.

FOCAL LENGTH:

iPhone 14 Pro 1× lens

(avoid barrel distortion by not using fisheye)

OVERLAP:

40~70%

Too little overlap makes registration harder.

Scene 1: [INDOOR] International House Library

This is where I spent most of my time during my exchange year in UC Berkeley.

Scene 2: [OUTDOOR] CNMAT Lab

This location is meaningful to me as it's where I conducted my undergraduate research.

Part A.2: Recover Homographies

Compute the homography matrix H that maps points from one image to another.

Mathematical Formulation

For each correspondence pair (x, y) ↔ (u, v), we construct two linear equations:

  • h₁x + h₂y + h₃ - h₇ux - h₈uy = u
  • h₄x + h₅y + h₆ - h₇vx - h₈vy = v

With n correspondence points, we build the system Ah = b where:

  • A is a 2n × 8 matrix containing the coordinates and their products
  • h is an 8 × 1 vector of unknown homography coefficients
  • b is a 2n × 1 vector of target coordinates

We solve this using least-squares: h = (AᵀA)⁻¹Aᵀb, then reconstruct the 3×3 homography matrix with h₉ = 1.

Homography derivation notes
Mathematical derivation

Implementation

▼ Main Function: computeH
# File: part2_homography.py:69-92

def computeH(pts1, pts2):
    n = len(pts1)
    A = np.zeros((2*n, 8))
    b = np.zeros((2*n, 1))

    for i in range(n):
        x, y = pts1[i]
        u, v = pts2[i]

        A[2*i] = [x, y, 1, 0, 0, 0, -u*x, -u*y]
        b[2*i] = u

        A[2*i+1] = [0, 0, 0, x, y, 1, -v*x, -v*y]
        b[2*i+1] = v

    h, _, _, _ = np.linalg.lstsq(A, b, rcond=None)

    H = np.zeros((3, 3))
    H[0, :] = h[:3].flatten()
    H[1, :] = h[3:6].flatten()
    H[2, :2] = h[6:].flatten()
    H[2, 2] = 1

    return H, A, b
Helper Functions (in part2_homography.py)
  • select_correspondences() — Interactive point selection using matplotlib ginput
  • visualize_correspondences() — Draws correspondences on image pairs
  • save_correspondences(), load_correspondences() — Save and load selected points in json to avoid re-selecting
  • verify_homography(), print_system() — Displays the linear system and compute reprojection error for website demo
Interactive Script (part2_exec.py)

An interactive CLI to detect the scene from images folder, choose which two images to process, decide how many correspondence points to mark, automatically save correspondences for future use

Demo: IHouse-Library

Using the interactive script, by selecting "ihouse-library" folder and picture 1 and 2, we manually click the points:

IHouse-Library correspondences visualization

Then, we get the (x,y) and (u,v), which can be written as the form matrix A (16×8) and b (16×1). Let's do computeH():

First 4 rows of A:
[[ 1.305e+03  1.229e+02  1.000e+00  0.000e+00 0.000e+00  0.000e+00 -7.926e+05 -7.462e+04]
 [ 0.000e+00  0.000e+00  0.000e+00  1.305e+03 1.229e+02  1.000e+00 -2.245e+05 -2.113e+04]
 [ 1.578e+03  9.773e+01  1.000e+00  0.000e+00 0.000e+00  0.000e+00 -1.306e+06 -8.086e+04]
 [ 0.000e+00  0.000e+00  0.000e+00  1.578e+03 9.773e+01  1.000e+00 -3.111e+05 -1.926e+04]
                                        ...                                             ]

First 4 rows of b:
[607.18
 171.96
 827.34
 197.12
  ...  ]
→

[[ 2.916e+00]
 [-1.578e-01]
 [-2.272e+03]
 [ 6.617e-01]
 [ 2.247e+00]
 [-7.104e+02]
 [ 1.153e-03]
 [-1.504e-04]]


Mean error: 2.45 pixels
Max error:  3.22 pixels

Part A.3: Warp the Images

In this part, we apply our Homography transformation in Part A.2 and warp two additional rectangle items using inverse warping with nearest neighbor and bilinear interpolation for vertification.

Inverse Warping

For each pixel (u, v) in our desired output image, we compute the corresponding source location using:

  • [x_i, y_i, 1]ᵀ = H⁻¹ · [u, v, 1]ᵀ
  • Normalize: (x, y) = (x_i/w, y_i/w) where w is the homogeneous coordinate

Nearest Neighbor

Round to the nearest integer coordinates:

  • x' = round(x), y' = round(y)
  • Sample: output[u,v] = input[y', x']

Bilinear Interpolation

Weighted average of 4 neighboring pixels:

  • Get floor coordinates: x₀ = ⌊x⌋, y₀ = ⌊y⌋
  • Compute weights: dx = x - x₀, dy = y - y₀
  • Four corner weights:
    • w₀₀ = (1-dx)(1-dy)
    • w₀₁ = (1-dx)·dy
    • w₁₀ = dx·(1-dy)
    • w₁₁ = dx·dy
Inverse warping and interpolation notes
Mathematical derivation and visual explanation

Implementation

▼ Main Function: warpImageNearestNeighbor
def warpImageNearestNeighbor(im, H, output_shape=None):
    h, w = im.shape[:2]
    has_color = len(im.shape) == 3

    if output_shape is None:
        out_h, out_w, offset = compute_output_bounds(im.shape, H)
        T_offset = np.array([
            [1, 0, -offset[0]],
            [0, 1, -offset[1]],
            [0, 0, 1]
        ])
        H_adjusted = T_offset @ H
    else:
        out_h, out_w = output_shape
        H_adjusted = H

    if has_color:
        out_im = np.zeros((out_h, out_w, im.shape[2]))
    else:
        out_im = np.zeros((out_h, out_w))
    alpha = np.zeros((out_h, out_w))

    H_inv = np.linalg.inv(H_adjusted)

    y_coords, x_coords = np.meshgrid(np.arange(out_h), np.arange(out_w), indexing='ij')
    coords = np.stack([x_coords, y_coords, np.ones_like(x_coords)], axis=-1)

    src_h = coords @ H_inv.T
    denom = src_h[..., 2]

    with np.errstate(divide='ignore', invalid='ignore'):
        src_coords = src_h[..., :2] / denom[..., np.newaxis]

    safe_denom = np.isfinite(src_coords).all(axis=-1)

    src_x = np.round(src_coords[..., 0]).astype(int)
    src_y = np.round(src_coords[..., 1]).astype(int)

    valid = safe_denom & (src_x >= 0) & (src_x < w) & (src_y >= 0) & (src_y < h)
    out_im[valid] = im[src_y[valid], src_x[valid]]
    alpha[valid] = 1

    if has_color:
        result = np.zeros((out_h, out_w, 4), dtype=out_im.dtype)
        result[..., :3] = out_im
        result[..., 3] = alpha
    else:
        result = np.zeros((out_h, out_w, 2), dtype=out_im.dtype)
        result[..., 0] = out_im
        result[..., 1] = alpha

    return result
▼ Main Function: warpImageBilinear
def warpImageBilinear(im, H, output_shape=None):
    h, w = im.shape[:2]
    has_color = len(im.shape) == 3

    if output_shape is None:
        out_h, out_w, offset = compute_output_bounds(im.shape, H)
        T_offset = np.array([
            [1, 0, -offset[0]],
            [0, 1, -offset[1]],
            [0, 0, 1]
        ])
        H_adjusted = T_offset @ H
    else:
        out_h, out_w = output_shape
        H_adjusted = H

    if has_color:
        out_im = np.zeros((out_h, out_w, im.shape[2]))
    else:
        out_im = np.zeros((out_h, out_w))
    alpha = np.zeros((out_h, out_w))

    H_inv = np.linalg.inv(H_adjusted)

    y_coords, x_coords = np.meshgrid(np.arange(out_h), np.arange(out_w), indexing='ij')
    coords = np.stack([x_coords, y_coords, np.ones_like(x_coords)], axis=-1)

    src_h = coords @ H_inv.T
    denom = src_h[..., 2]

    with np.errstate(divide='ignore', invalid='ignore'):
        src_coords = src_h[..., :2] / denom[..., np.newaxis]

    safe_denom = np.isfinite(src_coords).all(axis=-1)

    src_x = src_coords[..., 0]
    src_y = src_coords[..., 1]

    x0 = np.floor(src_x).astype(int)
    x1 = x0 + 1
    y0 = np.floor(src_y).astype(int)
    y1 = y0 + 1

    valid = safe_denom & (x0 >= 0) & (x1 < w) & (y0 >= 0) & (y1 < h)

    dx = src_x - x0
    dy = src_y - y0

    w00 = (1 - dx) * (1 - dy)
    w01 = (1 - dx) * dy
    w10 = dx * (1 - dy)
    w11 = dx * dy

    if has_color:
        out_im[valid] = (
            w00[valid, np.newaxis] * im[y0[valid], x0[valid]] +
            w01[valid, np.newaxis] * im[y1[valid], x0[valid]] +
            w10[valid, np.newaxis] * im[y0[valid], x1[valid]] +
            w11[valid, np.newaxis] * im[y1[valid], x1[valid]]
        )
    else:
        out_im[valid] = (
            w00[valid] * im[y0[valid], x0[valid]] +
            w01[valid] * im[y1[valid], x0[valid]] +
            w10[valid] * im[y0[valid], x1[valid]] +
            w11[valid] * im[y1[valid], x1[valid]]
        )

    alpha[valid] = 1

    if has_color:
        result = np.zeros((out_h, out_w, 4), dtype=out_im.dtype)
        result[..., :3] = out_im
        result[..., 3] = alpha
    else:
        result = np.zeros((out_h, out_w, 2), dtype=out_im.dtype)
        result[..., 0] = out_im
        result[..., 1] = alpha

    return result
▼ Helper Function: compute_output_bounds
def compute_output_bounds(im_shape, H):
    h, w = im_shape[:2]
    corners = np.array([
        [0, 0, 1],
        [w-1, 0, 1],
        [0, h-1, 1],
        [w-1, h-1, 1]
    ])

    warped_corners = (H @ corners.T).T
    warped_corners = warped_corners[:, :2] / warped_corners[:, 2:3]

    min_x_i = int(np.floor(warped_corners[:, 0].min()))
    min_y_i = int(np.floor(warped_corners[:, 1].min()))
    max_x_i = int(np.ceil(warped_corners[:, 0].max()))
    max_y_i = int(np.ceil(warped_corners[:, 1].max()))

    out_w = (max_x_i - min_x_i) + 1
    out_h = (max_y_i - min_y_i) + 1

    offset = np.array([min_x_i, min_y_i])

    return out_h, out_w, offset
Interactive Script Usage

Similar to Part A.2, we used part2_computeH and the CLI script to select the four corners of rectangular objects for rectification.

Demo: Inverse Warping Comparison

We demonstrate both interpolation methods on a sample image. Notice the difference in edge quality:

Demo 1

🖱️ Click to enlarge

Demo - Nearest Neighbor
Nearest Neighbor (Runtime: 0.117s)
Fast but produces jagged edges

🖱️ Click to enlarge

Demo - Bilinear
Bilinear Interpolation (Runtime: 0.260s)
Smoother, anti-aliased results

Demo 2

🖱️ Click to enlarge

Demo 2 - Nearest Neighbor
Nearest Neighbor (Runtime: 0.039s)
Fast but produces jagged edges

🖱️ Click to enlarge

Demo 2 - Bilinear
Bilinear Interpolation (Runtime: 0.088s)
Smoother, anti-aliased results

Results: Image Rectification

Below are rectified and cropped images from two different scenes, including nearest neighbor and bilinear interpolation methods.

Scene 1: Rectification Comparison

Scene 1 - Nearest Neighbor
Nearest Neighbor
Visible pixelation and jagged edges
Scene 1 - Bilinear
Bilinear Interpolation
Smooth transitions and clean edges

Scene 2: Rectification Comparison

Scene 2 - Nearest Neighbor
Nearest Neighbor
Sharp but aliased appearance
Scene 2 - Bilinear
Bilinear Interpolation
Natural, artifact-free result

Part A.4: Blend the Images into a Mosaic

Reusing Components
  1. Part A.2: Using saved correspondences and homographies that we manually clicked and stored.
  2. Part A.3: Warping the left and right images onto the middle image using the verified bilinear interpolation.
Implementation Approach

After aligning all images, we implemented weighted averaging to blend them together instead of simply overlapping.

In Part A.3, we already created an alpha mask for each image to define its visible region. The alpha values are further smoothed using a distance transform, giving higher weights near the image center and gradually fading toward the edges.

Implementation

▼ Distance Transform: create_distance_alpha
def create_distance_alpha(alpha_mask):
    """Convert binary alpha mask to distance-weighted alpha values"""
    dist = scipy.ndimage.distance_transform_edt(alpha_mask)
    max_dist = dist.max()
    if max_dist > 0:
        return dist / max_dist
    return alpha_mask.astype(float)
▼ Weighted Blending: blend_images_weighted
def blend_images_weighted(images_with_alpha, use_distance_blend=True):
    """Blend multiple images using distance-weighted alpha blending"""
    ref_h, ref_w = images_with_alpha[0].shape[:2]
    has_color = len(images_with_alpha[0].shape) == 3 and images_with_alpha[0].shape[2] == 4

    if has_color:
        output = np.zeros((ref_h, ref_w, 3))
    else:
        output = np.zeros((ref_h, ref_w))

    total_weight = np.zeros((ref_h, ref_w))

    for img in images_with_alpha:
        if has_color:
            rgb = img[..., :3]
            alpha = img[..., 3]
        else:
            rgb = img[..., 0]
            alpha = img[..., 1]

        # Apply distance-based weighting
        if use_distance_blend:
            alpha = create_distance_alpha(alpha > 0) * alpha

        output += rgb * alpha[..., np.newaxis] if has_color else rgb * alpha
        total_weight += alpha

    # Normalize by total weight
    valid = total_weight > 0
    if has_color:
        output[valid] /= total_weight[valid, np.newaxis]
    else:
        output[valid] /= total_weight[valid]

    return output
▼ Mosaic Creation: create_mosaic
def create_mosaic(images, H_list, ref_idx=0, use_distance_blend=True):
    """Create a mosaic from multiple images with computed homographies"""
    # Compute the bounding box for all warped images
    mosaic_h, mosaic_w, offset = compute_mosaic_bounds(images, H_list, ref_idx)

    # Adjust homographies to account for offset
    T_offset = np.array([[1, 0, -offset[0]], [0, 1, -offset[1]], [0, 0, 1]])

    warped_images = []

    # Warp each image to the common reference frame
    for i, im in enumerate(images):
        if i == ref_idx:
            H_adjusted = T_offset
        else:
            H_adjusted = T_offset @ H_list[i]

        warped = warpImageBilinear(im, H_adjusted, (mosaic_h, mosaic_w))
        warped_images.append(warped)

    # Blend all warped images
    mosaic = blend_images_weighted(warped_images, use_distance_blend)

    return mosaic, offset
Helper Function
  • compute_mosaic_bounds() — Warps all image corners to find the bounding box of the final mosaic

Results: Final Mosaics

Below are the final panoramic mosaics created by blending three images from each scene. The distance-weighted alpha blending creates seamless transitions in overlapping regions.

Mosaic 1: CNMAT Lab (Image 1, 2, 3)

CNMAT Lab Mosaic

Mosaic 2: International House Library (Image 2, 3, 4)

IHouse Library Mosaic

Part B.1: Harris Corner Detection

Automatic feature detection using Harris corners and Adaptive Non-Maximal Suppression (ANMS) to identify distinctive points for matching.

Harris Corner Detection

For each pixel, we compute the structure tensor matrix M using image gradients:

M = [
∑I²ₓ    ∑IₓIᵧ
∑IₓIᵧ   ∑I²ᵧ
]

The Harris response is calculated as:

  • R = det(M) / trace(M)
  • R = (M₁₁·M₂₂ - M²₁₂) / (M₁₁ + M₂₂)

Corners have large positive R values, edges have near-zero values, and flat regions have small values.

Adaptive Non-Maximal Suppression

ANMS ensures spatial distribution of corners by:

  • For each corner, find the minimum distance to a stronger corner (response > c × current)
  • Select the n points with largest minimum distances
  • This gives well-distributed features across the image
Intuition: Why does ANMS work?

If a corner point has a large minimum distance to any stronger corner, it means:

  • The point is relatively isolated and unique in its local region
  • It's not surrounded by many other strong corners (which would be redundant)
  • It likely represents a distinctive feature that's important for matching
Algorithm Overview
  1. Gradient Computation: Calculate Iₓ and Iᵧ using Sobel filters
  2. Structure Tensor: Build M matrix within a local window
  3. Response Calculation: Compute R for each pixel
  4. Peak Detection: Find local maxima above threshold
  5. ANMS Selection: Choose spatially distributed subset
Implementation Choice

We use skimage.feature.corner_harris for robustness and efficiency, with custom ANMS implementation for spatial distribution.

Implementation

▼ Harris Corner Detection: get_harris_corners
# from harris.py ref code
def get_harris_corners(im, edge_discard=20, min_dis=1, threshold=None):
    """
    This function takes a b&w image and an optional amount to discard
    on the edge (default is 5 pixels), and finds all harris corners
    in the image. Harris corners near the edge are discarded and the
    coordinates of the remaining corners are returned. A 2d array (h)
    containing the h value of every pixel is also returned.

    h is the same shape as the original image, im.
    coords is 2 x n (ys, xs).
    """
    assert edge_discard >= 20

    # find harris corners
    h = corner_harris(im, method='eps', sigma=1)
    coords = peak_local_max(h, min_distance=min_dis, threshold_rel=threshold)

    # discard points on edge
    edge = edge_discard  # pixels
    mask = (coords[:, 0] > edge) & \
           (coords[:, 0] < im.shape[0] - edge) & \
           (coords[:, 1] > edge) & \
           (coords[:, 1] < im.shape[1] - edge)
    coords = coords[mask].T
    return h, coords
▼ ANMS Implementation: anms
def anms(h, coords, c=0.9, max_pts=500):
    """
    Adaptive Non-Maximal Suppression
    Select spatially distributed corners based on their response values
    """
    if coords.shape[1] <= max_pts:
        return coords

    h_vals = h[coords[0], coords[1]]
    n = coords.shape[1]

    coords_t = coords.T
    dists = dist2(coords_t, coords_t)

    r = np.zeros(n)
    for i in range(n):
        # Find points with stronger response than c * current point
        stronger = h_vals > c * h_vals[i]
        stronger[i] = False  # Exclude self

        if np.any(stronger):
            r[i] = np.min(dists[i, stronger])
        else:
            r[i] = np.inf

    # Handle infinite values
    r[r == np.inf] = np.max(r[r != np.inf]) + 1 if np.any(r != np.inf) else 0

    # Select top max_pts points with largest minimum distances
    selected = np.argpartition(-r, max_pts)[:max_pts]

    return coords[:, selected]
▼ Distance Calculation: dist2
def dist2(x, c):
    """
    Calculates squared distance between two sets of points.
    Returns M x L matrix where entry (i,j) is squared distance
    from point i in x to point j in c.
    """
    ndata, dimx = x.shape
    ncenters, dimc = c.shape
    assert dimx == dimc, 'Data dimension does not match dimension of centers'

    return (np.ones((ncenters, 1)) * np.sum((x**2).T, axis=0)).T + \
            np.ones((ndata, 1)) * np.sum((c**2).T, axis=0) - \
            2 * np.inner(x, c)
Optimization Strategy

We can significantly improve performance by pre-filtering corners using peak_local_max parameters:

  • threshold_rel — Filters out weak corners below relative threshold
  • min_distance — Ensures minimum spacing between detected corners

This pre-filtering removes noise points and reduces ANMS computation time from 3m 29.9s to just 0.4s for n=500 points.

Demo: Performance Comparison

Comparing Harris corner detection with and without pre-filtering optimization on the same scene.

Without Pre-filtering (Raw Harris Corners)

Harris corners without filtering
Runtime: 3m 29.9s
Many noisy corners detected, ANMS takes significant time to process all points

With Pre-filtering (Optimized)

Harris corners with filtering
Runtime: 0.4s
Pre-filtered corners are higher quality, ANMS runs 500× faster with better spatial distribution

Part B.2: Feature Descriptor Extraction

Based on Section 4 of the MOPS paper, we extract descriptors using a multi-scale approach:

  • 40×40 window centered at each feature point
  • Gaussian blur (σ=1.5) for noise reduction
  • 5× downsampling to create an 8×8 descriptor
  • Normalization for illumination invariance
Why sample from a larger window?
MOPS descriptor extraction

Implementation

▼ Feature Descriptor Extraction: extract_feature_descriptors
def extract_feature_descriptors(im, coords):
    """
    Extract MOPS-style feature descriptors from detected corners.
    Returns 64-dimensional normalized descriptors for each valid corner.
    """
    h, w = im.shape
    blurred = gaussian_filter(im, sigma=1.5)

    descriptors = []
    valid_coords = []

    for i in range(coords.shape[1]):
        y, x = coords[0, i], coords[1, i]

        # Check if 40x40 window fits within image bounds
        if 20 <= y < h-20 and 20 <= x < w-20:
            # Extract 40x40 window centered at corner
            window = blurred[y-20:y+20, x-20:x+20]

            # Downsample by factor of 5 to get 8x8 descriptor
            descriptor = window[::5, ::5][:8, :8].flatten()

            # Normalize descriptor to zero mean and unit variance
            mean, std = descriptor.mean(), descriptor.std()
            descriptor = (descriptor - mean) / std if std > 0 else descriptor - mean

            descriptors.append(descriptor)
            valid_coords.append([y, x])

    return np.array(descriptors), np.array(valid_coords).T

Demo: Feature Extraction Process

For demonstration purposes, we deliberately used relaxed parameters to show both good and bad descriptors: min_dis=3, threshold=None, max_pts=32.

Harris Corners with ANMS (Including Weak Points)

Harris corners including weak points
Detected corners including some weak/noisy points for descriptor analysis
Feature extraction visualization
Complete pipeline: Corner detection → 40×40 patches → Gaussian filter → 8×8 normalized features
Grid of 32 normalized descriptors
Visualization of 32 extracted descriptors (8×8 each), showing variety in texture patterns.
Darker regions indicate lower normalized values, lighter regions indicate higher values.

Part B.3: Feature Matching

Our goal is to find pairs of features that look similar and are thus likely to be good matches between two images.

Lowe's Ratio Test

To distinguish reliable matches from ambiguous ones, we use the ratio test proposed by David Lowe:

  • For each feature in image 1, find its nearest neighbor and second nearest neighbor in image 2
  • Compute the ratio: r = dist(1st NN) / dist(2nd NN)
  • If r < threshold, accept it as a good match

Choosing the Threshold

According to Figure 6(b) from the MOPS paper, we can observe the distribution of matching errors for correct and incorrect matches. The ratio of 1-NN / 2-NN provides a good metric for distinguishing matches:

  • Ratio ≈ 0.7 appears to be a good choice
  • At this threshold, we start to see a small amount of errors mixed in
  • This balance gives us enough matching points without being too conservative
MOPS paper Figure 6
Figure 6 from the MOPS paper showing distribution of matching errors. Graph (b) shows that ratio 1-NN/2-NN is a good metric for distinguishing correct matches.

Implementation

▼ Feature Matching: match_features
# Lowe's ratio test
def match_features(descriptors1, descriptors2, ratio_threshold=0.7):
    """
    Match features using Lowe's ratio test.
    For each feature in descriptors1, find the best and second-best matches
    in descriptors2. Accept the match if the ratio of distances is below threshold.
    """
    if len(descriptors1) == 0 or len(descriptors2) == 0:
        return np.array([]).reshape(0, 2)

    # Compute all pairwise distances
    distances = np.sqrt(dist2(descriptors1, descriptors2))
    matches = []

    for i in range(len(descriptors1)):
        # Find two nearest neighbors
        sorted_indices = np.argsort(distances[i])

        if len(sorted_indices) >= 2:
            # Ratio test: first/second nearest neighbor
            ratio = distances[i, sorted_indices[0]] / distances[i, sorted_indices[1]]

            if ratio < ratio_threshold:
                matches.append([i, sorted_indices[0]])

    return np.array(matches) if matches else np.array([]).reshape(0, 2)

Demo: Feature Matching Results

Below we show the matched features between two images from the IHouse Library scene using different visualization approaches.

All feature matches
All matched features with ratio threshold = 0.7
Visualizes all feature correspondences found between the two images. The many overlapping lines can make it difficult to assess individual match quality.
Top 10 feature matches
Best 10 matches ranked by lowest ratio values
By selecting only the matches with the lowest ratios, we can verify by eye that these correspondences are indeed correct. This demonstrates that lower Lowe ratios correlate with more accurate matches.

Part B.4: RANSAC (Random Sample Consensus)

Even with Lowe's ratio test, some incorrect matches may remain. RANSAC iteratively finds the homography that best fits the largest subset of matches.

RANSAC Algorithm

The algorithm repeatedly samples small subsets of matches to find the best homography:

  1. Select 4 pairs (at random)
  2. Compute homography H
  3. Check how well H explains
    (Count inliers, good matches)
  4. Keep the best H (most inliers)
  5. Recompute H (with all inliers)
Integration with Part A

RANSAC reuses the computeH() function from Part A.2 to compute homographies from point correspondences.

Reprojection Error

error = ||H·p₁ - p₂||

Points with error < threshold are classified as inliers

Implementation

▼ RANSAC Homography: ransac_homography
def ransac_homography(matches, coords1, coords2, n_iters=5000, threshold=3.0):
    """
    Robustly estimate homography using RANSAC.
    Returns the best homography and a boolean mask of inliers.
    """
    if len(matches) < 4:
        return None, np.zeros(len(matches), dtype=bool)

    # Convert (y,x) to (x,y) for computeH
    pts1 = np.array([[coords1[1, m[0]], coords1[0, m[0]]] for m in matches])
    pts2 = np.array([[coords2[1, m[1]], coords2[0, m[1]]] for m in matches])

    best_H = None
    best_inliers = np.zeros(len(matches), dtype=bool)
    max_inliers = 0

    
    for _ in range(n_iters):
        # 1. Randomly sample 4 matches
        idx = np.random.choice(len(matches), 4, replace=False)

        # 2. Compute homography using Part A.2's computeH
        H, _, _ = computeH(pts1[idx], pts2[idx])

        # 3. Compute reprojection errors
        pt1_h = np.column_stack([pts1, np.ones(len(pts1))])
        pt2_proj = (H @ pt1_h.T).T
        pt2_proj = pt2_proj[:, :2] / pt2_proj[:, 2:]
        errors = np.linalg.norm(pt2_proj - pts2, axis=1)

        # 3. Count inliers
        inliers = errors < threshold
        
        # 4. Keep the best H
        if np.sum(inliers) > max_inliers:
            max_inliers = np.sum(inliers)
            best_inliers = inliers
            best_H = H
        
        # 5. Loop back to step 1

    # Refine with all inliers
    if max_inliers >= 4:
        best_H, _, _ = computeH(pts1[best_inliers], pts2[best_inliers])

    print(f"  RANSAC: {max_inliers}/{len(matches)} inliers")
    return best_H, best_inliers
▼ Automatic Stitching Pipeline: stitch_images
def stitch_images(image_paths, ref_idx=None, ratio_threshold=0.7, ransac_iters=5000,
                  ransac_threshold=3.0, max_pts=1000, feather_width=150):
    """
    Fully automatic image stitching pipeline using Harris corners, MOPS descriptors,
    Lowe's ratio test, and RANSAC.
    """
    images = [sk.img_as_float(skio.imread(p)) for p in image_paths]

    if ref_idx is None:
        ref_idx = len(images) // 2

    n = len(images)
    pairwise_H = [[None] * n for _ in range(n)]

    for i in range(n - 1):
        im1_gray = sk.color.rgb2gray(images[i]) if len(images[i].shape) == 3 else images[i]
        im2_gray = sk.color.rgb2gray(images[i+1]) if len(images[i+1].shape) == 3 else images[i+1]

        # B.1 Detect Harris corners
        h1, coords1 = get_harris_corners(im1_gray, edge_discard=20, min_dis=10, threshold=0.01)
        h2, coords2 = get_harris_corners(im2_gray, edge_discard=20, min_dis=10, threshold=0.01)

        # B.2 Apply ANMS
        coords1_anms = anms(h1, coords1, max_pts=max_pts)
        coords2_anms = anms(h2, coords2, max_pts=max_pts)

        # B.2 Extract MOPS descriptors
        descriptors1, coords1_valid = extract_feature_descriptors(im1_gray, coords1_anms)
        descriptors2, coords2_valid = extract_feature_descriptors(im2_gray, coords2_anms)

        # B.3 Match features using Lowe's ratio test
        matches, _ = match_features(descriptors1, descriptors2, ratio_threshold=ratio_threshold)
        print(f"  Matches: {len(matches)}")

        # B.4 Robustly estimate homography using RANSAC
        H, inliers = ransac_homography(matches, coords1_valid, coords2_valid,
                                      n_iters=ransac_iters, threshold=ransac_threshold)

        if H is not None:
            pairwise_H[i][i+1] = H
            pairwise_H[i+1][i] = np.linalg.inv(H)

    # Chain homographies relative to reference image
    H_list = [None] * n
    H_list[ref_idx] = np.eye(3)

    # Left side of reference
    for i in range(ref_idx - 1, -1, -1):
        if pairwise_H[i][i+1] is not None:
            H_list[i] = pairwise_H[i][i+1] @ H_list[i+1]

    # Right side of reference
    for i in range(ref_idx + 1, n):
        if pairwise_H[i][i-1] is not None:
            H_list[i] = pairwise_H[i][i-1] @ H_list[i-1]

    # Create final mosaic using Part A.4's create_mosaic
    mosaic, _ = create_mosaic(images, H_list, ref_idx, use_distance_blend=True,
                             feather_width=feather_width)

    return mosaic

Results: Automatic Image Stitching

Below are panoramic mosaics created using the fully automatic stitching pipeline. Compare these with the manual results from Part A.4 to see the effectiveness of automatic feature matching.

Auto-stitched IHouse Library panorama
Automatically stitched panorama using Harris corners, MOPS descriptors, and RANSAC
Auto-stitched CNMAT Lab panorama
Seamless outdoor panorama created with fully automatic feature matching and alignment
Auto-stitched IHouse Room panorama
Indoor scene panorama demonstrating robust feature matching in challenging lighting conditions