Trajectory Smoothing Filter

mediumPROVideo StabilizationStabilizationCV: Motion Estimation

Implement camera trajectory smoothing for video stabilization. This task involves reducing the jitter in a video by smoothing the camera's motion trajectory between frames.

Video stabilization is crucial for enhancing the viewing experience, and it relies on accurately estimating the homography between consecutive frames, which describes the transformation of the camera's motion. The accumulation of these transformations yields the camera's trajectory over time. However, this trajectory is often noisy and needs to be smoothed to remove unwanted jitter.

Here are the key steps:

Estimate the camera motion between frames using homography estimation techniques.
Accumulate the transformations to obtain the camera trajectory.
Apply a smoothing filter to the trajectory.

T_{smooth}(t) = \sum_i w_i \cdot T(t+i)

This technique is widely used in handheld camera recordings and action cameras to reduce shakiness.

Task

Implement smooth_trajectory(trajectory, window_size). The trajectory is already given (steps 1–2 are done for you); implement step 3 as a centred moving average:

Smooth each component ( $x$ , $y$ , angle) independently.
For frame $t$ , average the frames from $t-h$ to $t+h$ with equal weights, where $h = \lfloor \text{window\_size} / 2 \rfloor$ .
Near the start and end, the window is truncated to the frames that exist, and the average is taken over only those frames.
Return a list with one (x, y, angle) tuple per input frame (same length as the input), each value rounded to 2 decimal places. The tests print the tuples, so the values are expected as NumPy float64 scalars, e.g. (np.float64(3.33), np.float64(0.0), np.float64(0.0)).

Example

Input

trajectory = [(0,0,0), (1,1,0.1), (0,2,0), (2,1,0.05), (1,2,0)]
window_size = 3

Output

Smoothed trajectory with reduced jitter

Reasoning

trajectory holds one camera pose $(x, y, \theta)$ per frame, five frames here. With window_size = 3, each frame is averaged with $h = 1$ neighbour on each side, all weighted equally.
Each component is smoothed on its own. Frame 2 uses frames 1, 2, 3: $x = \frac{1+0+2}{3} = 1.0$ , $y = \frac{1+2+1}{3} \approx 1.33$ , $\theta = \frac{0.1+0+0.05}{3} = 0.05$ .
Frame 1 uses frames 0–2: $x = \frac{1}{3} \approx 0.33$ , $y = 1.0$ , $\theta = \frac{0.1}{3} \approx 0.03$ . Frame 3 gives $(1.0, 1.67, 0.02)$ the same way.
At the ends the window is cut short to two frames: frame 0 gives $(0.5, 0.5, 0.05)$ and frame 4 gives $(1.5, 1.5, 0.025)$ . In binary, $0.025$ sits just under the halfway point, so it rounds to $0.02$ .
The result is a smoothed trajectory with reduced jitter: (0.5, 0.5, 0.05), (0.33, 1.0, 0.03), (1.0, 1.33, 0.05), (1.0, 1.67, 0.02), (1.5, 1.5, 0.02). That's one pose per input frame, rounded to 2 decimal places.
Notice that raw $x$ jumps $0, 1, 0, 2, 1$ (swings of up to 2), while smoothed $x$ never moves more than $0.67$ between frames.

Constraints

trajectory: List of (x, y, angle) camera positions per frame
window_size: Smoothing window
Return: Smoothed trajectory

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 primerPREVIEW

Background Knowledge

Video stabilization tries to remove unwanted high‑frequency camera shake while preserving the intended low‑frequency camera motion (pans, tilts, zooms). The camera motion between two frames is often modeled as a 2D transform: translation, rotation, scale, or a full homography $H \in \mathbb{R}^{3\times 3}$ . By chaining these inter‑frame transforms, you get a camera trajectory over time (e.g., trajectory of camera pose parameters or homographies).

This trajectory is typically noisy: hand shake appears as rapid, small oscillations in the parameter curves over time. Stabilization works by smoothing these parameter trajectories with a temporal filter (moving average, Gaussian, low‑pass, etc.). The smoothed trajectory $T_{$ \text{smooth} $}(t)$ describes how the virtual stabilized camera should move. You then compute a per‑frame correction transform $C(t)$ that maps the original view at time $t$ to where it would be if the camera had followed the smoothed path instead of the original shaky one.

Algorithm / Approach Pattern

General pattern for trajectory‑based stabilization:

Estimate inter‑frame motion: For each pair of consecutive frames, estimate a 2D transform $M_t$ (e.g., homography) from frame $t$ to $t+1$ .
Accumulate to get trajectory: Compose the transforms to obtain a global camera transform $T(t)$ for each frame (relative to a reference frame).
Smooth the trajectory: Apply a temporal filter to the sequence $\{T(t)\}$ (or to its parameter vectors) to get $\{T_{$ \text{smooth} $}(t)\}$ .
Compute correction transforms: For each frame, compute $C(t) = T_{$ \text{smooth} $}(t) \cdot T(t)^{-1}$ .
Warp frames: Apply $C(t)$ to frame $t$ to render the stabilized video.

Your problem focuses on steps 3–4: given $T(t)$ , implement the smoothing and compute $C(t)$ .

Step‑by‑Step Strategy

Assume your input is a list/array of transforms $T, T, \dots, T[N-1]$ (each could be a 3×3 homography or a parameter vector like $(dx, dy, \theta, s)$ ).

Step 1: Choose representation to smooth

Common and simpler: convert each transform $T(t)$ to a parameter vector:
For example, from a 3×3 homography restricted to similarity/affine or from a known model:
translation: $(dx_t, dy_t)$
rotation: $\theta_t$
scale: $s_t$
Then you get 1D time series for each parameter: $\{dx_t\}, \{dy_t\}, \{\theta_t\}, \{s_t\}$ .

This avoids problems with directly averaging matrices.

Step 2: Design the smoothing filter

Given your formula

T_{\text{smooth}}(t) = \sum_i w_i \cdot T(t+i),

you are conceptually doing a finite impulse response (FIR) filter with weights $w_i$ over a temporal window.

For parameters:

# Example: uniform moving average with window size 2k+1
w = [1.0 / (2*k + 1)] * (2*k + 1) # or Gaussian weights normalized to sum to 1

For each frame index t, you’ll combine values from t-k to t+k with weights w[i].

Step 3: Apply smoothing per parameter

For each time $t$ :

For each parameter $p \in \{dx, dy, \theta, s\}$ :

p_{\text{smooth}}(t) = \sum_{i=-k}^{k} w_i \, p(t + i)

with boundary handling when $t+i$ is outside $[0, N-1]$ (e.g., clamp indices or shrink window).

In code (sketch):

PRO

Continue the full explanation

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

PRO

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