📘

Flow-Based Frame Warping

MediumInterpolation 📚 CV: Motion Estimation

Implement a frame interpolation technique using optical flow to create an intermediate frame at time $t$ . Given an image and optical flow, the goal is to warp the image using backward warping, which samples each output pixel from the input based on the flow. The optical flow $(u, v)$ at each pixel represents the motion of the pixel in the $x$ and $y$ directions.

For each output pixel at $(x, y)$ , sample from the input at $(x - u \times t, y - v \times t)$ .
Use nearest-neighbor sampling with boundary clamping to handle pixels outside the image bounds.

(x', y') = (x - u \times t, y - v \times t)

This technique is widely used in video processing and computer vision applications.

Example:

Input:

image = [[1,2,3],[4,5,6],[7,8,9]]
flow = [[(1,0),(1,0),(1,0)],
       [(1,0),(1,0),(1,0)],
       [(1,0),(1,0),(1,0)]]
t = 1

Output:

[[1, 1, 2], [4, 4, 5], [7, 7, 8]]

Reasoning:

For each output pixel, sample from (x - ut, y - vt):
Output (0,0): sample from (0-1×1, 0-0×1) = (-1, 0) → clamp to (0, 0) → value 1
Output (0,1): sample from (1-1×1, 0-0×1) = (0, 0) → value 1
Output (0,2): sample from (2-1×1, 0-0×1) = (1, 0) → value 2
Output (1,0): sample from (0-1×1, 1-0×1) = (-1, 1) → clamp to (0, 1) → value 4 ...and so on

Result: [[1,1,2], [4,4,5], [7,7,8]]

The rightward flow (u=1) shifts content left.

Constraints:

image: 2D grayscale image
flow: 2D array of (u, v) flow vectors (same size as image)
t: time factor (0 to 1)
Return warped image using nearest neighbor sampling
Clamp source coordinates to valid range

More from CV: Motion Estimation

Hungarian Algorithm for MOTHard Rolling Shutter CorrectionHard Horn-Schunck Global Optical FlowMedium Intersection over Union (IoU) for TrackingMedium Bilinear Flow WarpingHard

You are given an image and optical flow, and you need to create an intermediate frame by backward warping: for each output pixel at $(x, y)$ , you sample from the input image at $(x - u \cdot t,\, y - v \cdot t)$ , where $(u, v)$ is the flow at that output pixel and $t \in [0, 1]$ .

1. Background Knowledge (Key Concepts)

Optical flow Optical flow is a 2D vector field $(u(x,y), v(x,y))$ that describes how pixels move between frames: $u$ is horizontal motion, $v$ is vertical motion. For a frame at time 0 and a frame at time 1, the flow at pixel $(x, y)$ tells you where that pixel moves to (or comes from), depending on the flow convention. In this problem, you use the flow at coordinates $(x, y)$ of the output to decide where to sample in the input.
Forward vs backward warping
Forward warping: For each input pixel, you “push” it forward to a new location in the output using the flow. This easily creates holes and overlaps.
Backward warping: For each output pixel, you “pull” its value from the input by asking: “Where did this pixel come from?” That is what you implement here. Backward warping is standard in optical-flow–based frame interpolation because it guarantees every output pixel is filled.
Intermediate frame at time $t$ You can think of the flow as describing full motion between time 0 and 1. To get an intermediate frame at time $t$ , you move only a fraction of the flow: sample at coordinates $(x - u \cdot t, y - v \cdot t)$ . For $t = 0$ , you get the original frame; for $t = 1$ , you fully warp according to the flow.

2. Algorithm / General Approach

The algorithm is a per-pixel resampling of the input image using the flow field:

Iterate over all pixel coordinates $(x, y)$ of the output image.
Read the flow vector $(u, v)$ at $(x, y)$ .
Compute the corresponding source coordinate in the input:

x_s = x - u \cdot t,\quad y_s = y - v \cdot t

Because the problem specifies nearest-neighbor sampling with boundary clamping:

Clamp $(x_s, y_s)$ to lie inside the image bounds.
Round to the nearest integer pixel.

Copy the pixel from the input at that clamped, rounded coordinate into the output at $(x, y)$ .

This pattern is common in image warping, texture mapping, and frame interpolation: compute source coordinates, clamp, sample, and assign.

3. Step-by-Step Strategy (Implementation Outline)

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.