📘

Linear Interpolation

EasyInterpolation 📚 CV: Motion Estimation

Implement a function to perform linear interpolation between two given values at different times. This task is crucial in frame interpolation, where the goal is to generate intermediate frames between two known frames to create smooth transitions.

The concept of linear interpolation is based on the idea of estimating a value at an intermediate time $t$ using the values at the start and end times, $v_0$ and $v_1$ respectively. This is a fundamental technique in motion estimation and computer vision.

Here are the steps to achieve this:

Define the start and end values, $v_0$ and $v_1$ , and the interpolation factor $t$ .
Use the interpolation factor $t$ to compute the weighted average of $v_0$ and $v_1$ .

v_t = (1 - t) \cdot v_0 + t \cdot v_1

This technique is widely used in animation and video processing to create smooth transitions between frames.

Example:

Input:

v0 = 0, v1 = 100, t = 0.5

Output:

50.0

Reasoning:

Applying linear interpolation:

v_t = (1 - t) × v0 + t × v1
v_t = (1 - 0.5) × 0 + 0.5 × 100
v_t = 0.5 × 0 + 0.5 × 100
v_t = 0 + 50
v_t = 50.0
At t=0.5 (halfway), we get the midpoint value.

Constraints:

v0 and v1 are values at frames 0 and 1
t is the interpolation factor (0 to 1)
Return interpolated value rounded to 4 decimal places

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

Background Knowledge

Linear interpolation is a simple way to estimate a value between two known values by assuming the change between them is linear over time. If you know a quantity at time 0 ( $v_0$ ) and at time 1 ( $v_1$ ), you treat the path from $v_0$ to $v_1$ as a straight line and pick the point on that line corresponding to fraction $t$ of the way. Mathematically, this is:

v_t = (1 - t)\,v_0 + t\,v_1,\quad t \in [0,1]

In computer vision and graphics (e.g., frame interpolation, animation), $v_0$ and $v_1$ might be pixel intensities, positions, or motion values at two frames. The interpolation factor $t$ represents how far the intermediate frame is between them in time (e.g., $t = 0.5$ is exactly in the middle). This same idea generalizes to vectors (e.g., 2D/3D coordinates) and even colors; the formula is applied component-wise.

Algorithm/Approach

The general pattern:

Interpret the problem as: given two end values and a factor $t$ , compute the in-between value on the straight line connecting them.
Use the linear interpolation formula directly:
Either in the standard form: $v_t = (1 - t)\,v_0 + t\,v_1$
Or equivalently: $v_t = v_0 + t\,(v_1 - v_0)$
If values are multi-dimensional (e.g., RGB, $(x,y)$ ), apply the same formula independently to each component.

Step-by-Step Strategy

Assuming scalar or simple numeric types:

Read inputs:

Start value $v_0$
End value $v_1$
Interpolation factor $t$ (or compute $t$ from times if needed)

Optionally clamp $t$ to $[0,1]$ if required by the problem:

t = max(0.0, min(1.0, t))

Compute the interpolated value using either form:

v_t = (1 - t) * v0 + t * v1
# or
v_t = v0 + t * (v1 - v0)

Return or print the result in the format required by the problem (e.g., integer vs float, rounding if specified).

If the problem gives discrete times (e.g., at times $t_0$ and $t_1$ and you want value at $t^*$ ), first convert to the normalized factor:

t = \frac{t^* - t_0}{t_1 - t_0}

then use the same interpolation formula.

Common Pitfalls

Not normalizing time: If the problem gives absolute times (e.g., frames 10 and 20, and you want frame 15), you must convert to a $t \in [0,1]$ before applying the lerp formula.
Type issues:
Integer division when you need floating-point (e.g., 1/2 vs 1.0/2.0).
Rounding vs truncation: check whether the problem expects floor, round, or exact float output.
Out-of-range $t$ : Some tasks assume extrapolation is not needed; ensure $t$ is within [0,1] if specified.
Precision: For very small/large values, floating-point precision might matter; usually not an issue in “easy” problems, but be aware.

Time & Space Complexity

Time complexity:
$O(1)$ — only a constant number of arithmetic operations.
Space complexity:
$O(1)$ — you use a fixed amount of extra memory (a few variables), independent of input size.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.