Using NumPy for Fast Interpolation

user_5561875 0
Viewed 1045

Given a masked NumPy array of dimensionality (frames, points, 2) representing a video of frames frames, where in each frame points (x, y) points are being tracked.

I would like to interpolate this video from frames frames to any number of frames, very fast, hopefully with a cubic spline, but any other continuous interpolation will work OK too.

The naive solution I have implemented splits the array into 2 arrays of dimensions (frames, points) for the X array and Y array. Then, I transpose the array to (points, frames). For each row (single point over-time) I map it to an index and value, so the array [5, 6, --, 7] becomes:

[{"x": 0, "y": 5}, {"x": 1, "y": 6}, {"x": 3, "y": 7}]

I feed this to a scipy.interp1d, and run on my new array which is for example [0, 0.5, 1, 1.5, 2, 2.5, 3] and get a new x, y array that I then convert back to NumPy.

This process removes the masks for intermittent frames (which is fine with me).

Current performance: Small array of shape (9 frames, 140 points, 2) to (24 frames, 140 points, 2)

  • Cubic interpolation 0.115 seconds
  • Linear interpolation 0.112 seconds

Note!

This is a masked array, like [5, 6, --, 7]. so it is important to incorporate the masks in the interpolation in order to not have 0 values (the data array looks like [5, 6, 0, 7]!

Here is a toy example with data on the desired and undesired behaviors:

import numpy as np
import numpy.ma as ma
from scipy.interpolate import interp1d

points = np.array([1, 2, 3, 4, 0, 6])
mask = [0, 0, 0, 0, 1, 0]
points = ma.array(points, mask=mask)
print(points)  # [1 2 3 4 -- 6]

lin = np.linspace(0, 1, 6)

# Undesired behavior
f = interp1d(lin, points, axis=0, kind='cubic')
print(f(lin))  # [1  2 3 4 -8.8817842e-16 6]

# Desired behavior
compressed_lin = [0, 0.2, 0.4, 0.6, 1]
compressed_points = np.array([1,2,3,4,6])
f = interp1d(compressed_lin, compressed_points, axis=0, kind='cubic')
print(f(lin)) # [1 2 3 4 5 6]
scipy numpy python
2 Answers

I'm not sure you are using scipy.interpolate.interp1d as I do, but my computer shows about 662 µs:

np.random.seed(1)
points = np.random.rand(9,140,2)

f = interp1d(np.linspace(0,1,9), points, axis=0, kind='cubic')
f(np.linspace(0,1,24))

Performance (timeit -n 100):

662 µs ± 111 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
user_42384080

If you need it fast, 1) avoid masked arrays, 2) avoid interp1d. If CubicSpline is not fast enough, you can code up your own cubic interpolation taking into account that your points are equidistant.

EDIT: if you really cannot avoid masked arrays, beware that nothing in scipy.interpolate is numpy.ma-aware, so you'll need to DIY. Alternatively, consider doing some data imputation to fill the masked values.

user_1437650
Related