Efficient way to compute the median of an array of canvas in JavaScript

I have an array of N HTMLCanvasElements that come from N frames of a video, and I want to compute the "median canvas" in the sense that every component (r, g, b, opacity) of every pixel is the median of the corresponding component in all the canvases.

The video frames are 1280x720, so that the pixels data for every canvas (obtained with canvas.getContext('2d').getImageData(0, 0, canvas.width, canvas.height).data) is a Uint8ClampedArray of length 3.686.400.

The naive way to compute the median is to:

prepare a result Uint8ClampedArray of length 3.686.400
prepare a temporary Uint8ClampedArray of length N
loop from 0 to 3.686.399
- a) loop over the N canvases to fill the array
- b) compute the median of the array
- c) store the median to the result array

But it's very slow, even for 4 canvases.

Is there an efficient way (or existing code) to do that? My question is very similar to Find median of list of images, but I need to to this in JavaScript, not Python.

Note: for b), I use d3.median() which doesn't work on typed arrays, as far as I understand, so that it implies converting to numbers, then converting back to Uint8Clamped.

Note 2: I don't know much of GLSL shaders, but maybe using the GPU would be a way to get faster results. It would require to pass data from the CPU to the GPU though, which takes time if done repeatedly.

Note 3: the naive solution is there: https://observablehq.com/@severo/compute-the-approximate-median-image-of-a-video

Solution

You wrote

I use d3.median() which doesn't work on typed arrays…

Although that is not exactly true it leads into the right direction. Internally d3.median() uses the d3.quantile() method which starts off like this:

export default function quantile(values, p, valueof) {
  values = Float64Array.from(numbers(values, valueof));

As you can see, this in fact does make use of typed arrays, it is just not your Uint8ClampedArray but a Float64Array instead. Because floating-point arithmetic is much more computation-intensive than its integer counterpart (including the conversion itself) this has a dramatic effect on the performance of your code. Doing this some 3 million times in a tight loop kills the efficiency of your solution.

Since you are retrieving all your pixel values from a Uint8ClampedArray you can be sure that you are always dealing with integers, though. That said, it is fairly easy to build a custom function median(values) derived from d3.median() and d3.quantile():

function median(values) {
  // No conversion to floating point values needed.
  if (!(n = values.length)) return;
  if (n < 2) return d3.min(values);
  var n,
      i = (n - 1) * 0.5,
      i0 = Math.floor(i),
      value0 = d3.max(d3.quickselect(values, i0).subarray(0, i0 + 1)),
      value1 = d3.min(values.subarray(i0 + 1));
  return value0 + (value1 - value0) * (i - i0);
}

On top of getting rid of the problematic conversion on the first line this implementation additionally applies some more micro-optimizations because in your case you are always looking for the 2-quantile (i.e. the median). That might not seem much at first, but doing this multiple million times in a loop it does make a difference.

With minimal changes to your own code you can call it like this:

// medianImageData.data[i] = d3.median(arr);   Instead of this use line below.
medianImageData.data[i] = median(arr);

Have a look at my working fork of your Observable notebook.