Moving Average Path Smoothing

You can think of this problem as taking a noisy 1D camera path (per-Frame translation/rotation parameters) and applying a low‑pass filter (moving average) to remove fast jitter while keeping slow, intentional movement.

---

1. Background Knowledge

In video stabilization, you typically estimate a camera motion trajectory: for each frame $i$, you have parameters like translation $x_i, y_i$ and rotation $\theta_i$. Hand‑held or moving cameras produce a trajectory with high‑frequency noise: tiny, rapid changes from frame to frame that look like jitter. The goal of stabilization is to smooth the motion path so that the visual motion appears more continuous and deliberate.

A moving average filter is a simple discrete-time smoothing filter. For each index $i$, you replace the original value $x_i$ with the average of values in a local window $W$ around $i$. This attenuates high‑frequency variations (fast changes) and preserves low‑frequency variations (slow trends). In this problem, the filter is symmetric (looks both backward and forward around $i$) and the window shrinks near the boundaries instead of padding with fake values.

---

2. Algorithm / General Approach

Pattern to solve this type of problem:

• For each position $i$:
• Determine the valid window indices around $i$ (respecting array boundaries).
• Compute the average of all samples in that window.
• Store that average as the smoothed value $\bar{x}_i$.

Key points:

• Window is centered at $i$, e.g. for radius $r$: from $i - r$ to $i + r$.
• Near the start or end, you clip the window to stay inside $[0, n-1]$.
• You do not pad with extra values and do not wrap around the array.

This is essentially a 1D convolution with a box kernel, with special casing at the edges.

---

3. Step‑by‑Step Strategy

Assume:

• Input path as array x[0..n-1].
• Window size W is given (often odd), and let r = W // 2 be the radius.

Steps:

1. Parse inputs

• Read the path array (could be 1D or multiple components; conceptually treat each component separately).
• Read the window size W, compute r = W // 2.

2. Initialize output

• Create an output array y of length n for the smoothed path.

3. For each index i (0 to n-1):

• Compute window boundaries:
• start = max(0, i - r)
• end = min(n - 1, i + r)
• Compute window length:
• len = end - start + 1
• Compute sum over this window:
• sum = x[start] + x[start+1] +... + x[end]
• Set:
• y[i] = sum / len

4. Return the smoothed path y

• If you have multi-dimensional parameters (e.g., x, y, theta), apply the same logic to each dimension.

A simple implementation will use a nested loop (outer over i, inner over j in the window). An optimized version can use a running sum (sliding window) to achieve linear time.

Example (naive 1D version):

def smooth_path(x, W):
 n = len(x)
 r = W // 2
 y = [0.0] * n

 for i in range(n):
 start = max(0, i - r)
 end = min(n - 1, i + r)
 total = 0.0
 count = 0
 for j in range(start, end + 1):
 total += x[j]
 count += 1
 y[i] = total / count

 return y

---

4. Common Pitfalls

• Incorrect edge handling:
• Using a fixed window size everywhere and then indexing out of bounds.
• Padding with zeros or repeating edge values when the problem explicitly says: use available samples, don’t pad or wrap.
• Off‑by‑one errors:
• Forgetting +1 when converting start/end to count: window length is end - start + 1.
• Miscomputing r for even window sizes.
• Integer division:
• If the path values are integers, be sure to convert to float before division, or you’ll get truncated averages in some languages.
• Modifying input in place:
• Don’t overwrite x while still needing original values later; use a separate output array.
• For multi‑component paths:
• Forgetting to smooth all components consistently (e.g., smoothing x but not y).

---

5. Time & Space Complexity

Let:

• $n$ = number of frames (length of path).

• $W$ = window size.

• Naive implementation:

• For each of $n$ positions, you sum up to $W$ elements.

• Time: $O(n \cdot W)$

• Space: $O(n)$ for the output array.

• Optimized sliding window (if used):

• You maintain a running sum and update it in $O(1)$ per step.

• Time: $O(n)$

• Space: $O(n)$

For most coding challenge constraints and medium window sizes, the naive $O(nW)$ solution is usually acceptable unless otherwise stated.