Linear Interpolation

easyFREEFrame InterpolationInterpolationCV: 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

Inputs: $v_0 = 0$ is the value at frame 0, $v_1 = 100$ is the value at frame 1, and $t = 0.5$ says how far along the way from frame 0 to frame 1 we are (0 = start, 1 = end).
Weights: the start value gets weight $1 - t = 0.5$ and the end value gets weight $t = 0.5$ . The two weights always add up to $1$ , so the result is a weighted average that stays between $v_0$ and $v_1$ .
Combine: $v_t = 0.5 \cdot 0 + 0.5 \cdot 100 = 0 + 50 = 50$ , which rounded to 4 decimal places gives 50.0.
Another view: the same value is $v_0 + t\,(v_1 - v_0) = 0 + 0.5 \cdot 100$ : start at $v_0$ and cover a fraction $t$ of the gap.
Notice: the endpoints reproduce the known frames exactly. $t = 0$ returns $v_0 = 0$ and $t = 1$ returns $v_1 = 100$ , while $t = 0.25$ would land a quarter of the way, at $25$ .

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

Learn this in

Motion EstimationCV Study Plan

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

Concept primer

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