Using NumPy for Fast Interpolation

Question

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]

When you go from 9 frames to 24 frames, are the frames evenly spaced, or do they have their own frame timestamp? — Quang Hoang
– Quang Hoang, Commented Mar 19, 2020 at 13:53
Yes, so if you had 9 frames, they would be spaced at [0,0.125,0.250,0.375,0.500,0.625,0.750,0.875,1] and if we had 25 frames to interpolate to, it would try to interpolate these values: [0, 0.04, 0.08, ... , 0.92, 0.92, 1] (This is an example where the values are between 0 and 1, but they could also be between 0 and 9, doesn't matter) — Amit
– Amit, Commented Mar 19, 2020 at 14:42

Quang Hoang · Accepted Answer · 2020-03-19 15:37:55Z

2

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)

answered Mar 19, 2020 at 15:37

Quang Hoang

151k11 gold badges64 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Amit Over a year ago

Thank you. It might be an accumulation of the things around it then. For example, I didn't know I can do it the way you showed, instead, I did it row by row. The reason I'm doing it that way is because I have a masked array, and not a full numpy array. so like my example, I sometimes want to skip some indexes. Do you know if there is a way to incorporate that fact in your solution?

ev-br · Accepted Answer · 2020-03-21 07:40:22Z

1

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.

edited Mar 21, 2020 at 7:40

answered Mar 20, 2020 at 5:23

ev-br

26.3k9 gold badges68 silver badges84 bronze badges

1 Comment

Amit Over a year ago

Thanks, can't avoid masked arrays, this is the format of my data

Collectives™ on Stack Overflow

Using NumPy for Fast Interpolation

Note!

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Note!

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related