📘

Cumulative Camera Motion

EasyStabilization 📚 CV: Motion Estimation

Implement a function to compute the cumulative camera path from given frame-to-frame translations, a crucial step in video stabilization. This process involves calculating the integrated motion of the camera over time.

The concept of cumulative camera motion is rooted in motion estimation, where the goal is to estimate the movement of the camera between consecutive frames. This is often represented as a sequence of translations and rotations. In this case, we focus on the translation component, which can be thought of as the change in position $(dx, dy)$ between two frames.

To compute the cumulative path, we can follow these steps:

Initialize the starting position at the origin $(0, 0)$ .
For each frame-to-frame translation $(dx, dy)$ , update the current position by adding the translation.
Record the updated position at each step.

x_{t+1} = x_t + dx \\ y_{t+1} = y_t + dy

This technique is widely used in handheld camera footage stabilization to reduce jitter and produce smoother video.

Example:

Input:

transforms = [(1, 0), (1, 1), (0, 1)]

Output:

[(0, 0), (1, 0), (2, 1), (2, 2)]

Reasoning:

Starting at origin, accumulate each motion:

Initial: (0, 0) After transform 0: (0+1, 0+0) = (1, 0) After transform 1: (1+1, 0+1) = (2, 1) After transform 2: (2+0, 1+1) = (2, 2)

Path: [(0,0), (1,0), (2,1), (2,2)]

This represents the camera's trajectory over 4 frames.

Constraints:

transforms: list of (dx, dy) frame-to-frame motions
Return cumulative path as list of (x, y) positions
Path starts at (0, 0)
Path length = len(transforms) + 1

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 can view this problem as computing a running sum of 2D (or 3D) translations to reconstruct the camera’s path over time.

1. Background Knowledge

In video stabilization, each pair of consecutive frames is analyzed to estimate how the camera moved between them (e.g., by optical flow or feature matching). This motion is often represented as a simple translation $(\Delta x, \Delta y)$ or as a full 2D transform (e.g., affine or homography). For this problem, we only care about translations.

The camera path is the trajectory of the camera over time. If you know how much the camera moved between frame 0→1, 1→2, 2→3, etc., you can reconstruct its position at each frame by accumulating these incremental motions. Mathematically, this is a discrete version of integration: position at time $t$ is the sum of all previous frame-to-frame motions up to $t$ .

In stabilization, this original path is later smoothed (to remove high-frequency jitter). The difference between the smoothed path and the original path tells you how to shift each frame to appear stable. But before smoothing, you must correctly compute the cumulative path, which is exactly what this task does.

2. Algorithm / General Approach

This is a classic prefix sum / running sum pattern:

Input: list/array of frame-to-frame translations $\Delta p_1, \Delta p_2, \dots, \Delta p_{N-1}$ , where each $\Delta p_i$ is a vector, e.g. $(\Delta x_i, \Delta y_i)$ .
Output: list/array of absolute camera positions $p_0, p_1, \dots, p_{N-1}$ .
Rule:
Start with $p_0 = (0, 0)$ (the origin).
For each subsequent frame: $p_t = p_{t-1} + \Delta p_t$ .

This pattern appears in many contexts: prefix sums, cumulative sums, integrating velocity to get position, computing balances from transactions, etc.

3. Step-by-Step Strategy

Understand the input representation

Clarify the shape:
If there are $N$ frames, you typically have $N-1$ translations: one for each pair (frame t → frame t+1).
Each translation is a vector:
2D: [dx, dy]
3D: [dx, dy, dz]

Initialize the output

Create an array path to store the cumulative positions for each frame.
Set the starting position:

path = [0, 0] # or [0, 0, 0] for 3D

Iterate and accumulate

For each frame index t from 1 to N-1:
Add the translation from frame t-1 → t to the previous position:

path[t] = path[t-1] + translation[t-1]

Here + is element-wise vector addition.

Return the cumulative path

After the loop, path contains the camera’s position at each frame.
This can then be passed to the smoothing step in a full stabilization pipeline.

4. Common Pitfalls

Off-by-one errors
Confusing whether translations array length is N or N-1.
Correct pattern: if there are N frames, there are N-1 frame-to-frame translations.
Wrong initialization
Forgetting to start at the origin ([0, 0]) or inadvertently starting with the first translation as the first position.
Overwriting instead of accumulating
Doing path[t] = translation[t-1] instead of path[t] = path[t-1] + translation[t-1].
Mutating in-place incorrectly
If you reuse arrays or references, make sure each path[t] is a new vector or correctly copied, not an alias to the same object.

5. Time & Space Complexity

Time complexity:
You do one pass over the translations, with $O(1)$ work per translation.
$O(N)$ , where $N$ is the number of frames (or translations).
Space complexity:
You store one position vector per frame.
$O(N)$ additional space for the output path (ignoring the input, which is given).

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.