Homography warp

Overview

A homography is a projective map between two planes. It is a 3×3 matrix M applied to homogeneous pixel coordinates, followed by division by the third coordinate. Applied to every pixel of an image, it resamples the image into a new view. This is the homography warp. The paper that covers it here fits M from four point pairs: four points in the source image and the four points they should map to 2406.08775 §3.2 §3.3 eq. 2.

The warp is useful when the content of interest lies on one plane, such as a road or a runway, and the view should look straight down on it. ALINA uses exactly this: it maps a user-drawn quadrilateral to a rectangle, so that the painted lines on the ground run in a predictable direction in the output 2406.08775 §3.2 fig. 3. Points found in the warped view are sent back to the original image with the inverse of M 2406.08775 §3.9.

Variants

Four-point ROI-to-rectangle warp

The source is a region of interest (ROI) with four corners, and the target is a fixed rectangle. The authors solve M from the four corner pairs and warp each pixel with the projective map in their equation 3 2406.08775 §3.3 eq. 3. The ROI is drawn once per video and reused for every frame, which the authors contrast with an earlier method that needed a new ROI at each change of scene 2406.08775 §4.5. Card: ALINA: Advanced Line Identification and Notation Algorithm.

Reported cost: the warp stage took 4.41 ms per frame on the authors' CPU, out of about 50 ms for the whole labelling pipeline 2406.08775 tab. 1. This is a single-paper, single-machine figure.

Other variants

No other card in the repository covers this concept. Methods that estimate a homography from matched features, such as RANSAC fitting, are not described in any card for this slug. See Image registration for related alignment work that uses other transforms.

When to use which

The only evidence on this page is one paper with one use case. The paper does not compare the warp with any alternative, so the table does not rank it against other transforms.

Implementation sketch

Language-agnostic outline of the four-point case. The destination rectangle is an input, because the paper does not give one 2406.08775 §3.3.

# Homography warp from four point pairs  [arxiv:2406.08775 §3.2] [§3.3]
# Input:  src (4, 2) ROI corners; dst (4, 2) target rectangle corners
#         image (H, W, C)
# Output: warped image; inverse matrix for mapping points back

def homography_from_four_points(src, dst):
    # Solve the 8 unknowns of M with M[2][2] = 1  [eq. 2]
    # Each point pair gives two linear equations in those unknowns
    A, b = [], []
    for (x, y), (u, v) in zip(src, dst):
        A.append([x, y, 1, 0, 0, 0, -u * x, -u * y]); b.append(u)
        A.append([0, 0, 0, x, y, 1, -v * x, -v * y]); b.append(v)
    h = solve_linear(A, b)
    return [[h[0], h[1], h[2]],
            [h[3], h[4], h[5]],
            [h[6], h[7], 1.0]]

def warp_point(M, x, y):
    # Projective map: multiply, then divide by the third coordinate  [eq. 3]
    # The paper's notation for s and t differs from its definitions
    # [arxiv:2406.08775 §3.3]; check the indices before implementing
    u, v, w = matmul(M, [x, y, 1.0])
    return u / w, v / w

def warp_image(image, M, out_shape):
    # Resample: for each output pixel, look up its source pixel via M inverse
    # [arxiv:2406.08775 §3.3]; use an interpolation rule of your choice
    M_inv = invert(M)
    out = zeros(out_shape)
    for (u, v) in pixels(out_shape):
        x, y = warp_point(M_inv, u, v)
        out[v][u] = sample(image, x, y)  # nearest or bilinear
    return out

# Map detections from the warped view back to the original view  [§3.9]
# Points found in the warped view are sent through the inverse of M
def to_original(points_warped, M):
    M_inv = invert(M)
    return [warp_point(M_inv, u, v) for (u, v) in points_warped]

Where implementations differ: the way the destination is sized, the interpolation used to sample, and whether the output is a set of pixels or a painted mask before mapping back. The paper leaves the first two open and does not describe the third 2406.08775 §3.3 §3.9. The card for ALINA lists how its released code makes these choices.

Contradictions

None known. Only one card covers this concept, so no two papers here disagree. One point to check is the notation: the paper's equation for the projective map uses different letters for the coordinates than its own definitions, and it writes the bottom-right entry of M as 1 in one place and as M₃₃ in another 2406.08775 §3.3 eq. 2 eq. 3. The card treats that entry as 1.

Papers

• ALINA: Advanced Line Identification and Notation Algorithm: applies a four-point homography to a user-drawn ROI for a bird's-eye view of taxiway markings, then maps labelled pixels back to the frame.