Calculating the middle value of a canvas array in JavaScript in the most effective manner

Question

Calculating the middle value of a canvas array in JavaScript in the most effective manner

My task involves working with an array of N HTMLCanvasElements that represent frames from a video. I aim to calculate the "median canvas" where every pixel's components (r, g, b, opacity) are the median values from all the canvases.

Each video frame is sized 1280x720, resulting in pixel data for each canvas (retrieved using

canvas.getContext('2d').getImageData(0, 0, canvas.width, canvas.height).data

) being a Uint8ClampedArray with a length of 3,686,400.

The traditional method to find the median includes:

Create a result Uint8ClampedArray with a length of 3,686,400
Create a temporary Uint8ClampedArray with a length equal to N
Loop through 0 to 3,686,399
- a) Iterate over the N canvases to populate the array
- b) Calculate the median of the array
- c) Store the median in the result array

This approach is sluggish, especially when dealing with just 4 canvases.

I am looking for a more efficient method or existing code to achieve this. While my question is similar to Find median of list of images, I specifically need a solution in JavaScript, not Python.

Note: For step b), I am using d3.median(). However, it doesn't support typed arrays, so conversion to numbers and then back to Uint8Clamped type becomes necessary.

Note 2: Although I lack expertise in GLSL shaders, perhaps exploring GPU utilization could lead to quicker results. This approach may involve transferring data from CPU to GPU, which might incur time if done frequently.

Note 3: The basic solution can be found here:

javascript d3.js canvas glsl median

Answer 1

Answer №1

Your statement

Using d3.median() can be problematic with typed arrays...

While this may have been the assumption, it's not entirely accurate. The d3.median() function internally relies on the d3.quantile() method which starts by utilizing:

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

The use of a Float64Array in this context is crucial for precise calculations. However, if your data is stored as integers in a Uint8ClampedArray, the frequent conversions to floating point values can significantly impact performance.

To address this issue, a custom function median(values) can be crafted based on d3.median() and d3.quantile():

function median(values) {
  // Avoid unnecessary conversion to floating point.
  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);
}

This optimized version eliminates the need for immediate conversion and introduces enhancements tailored specifically for calculating the median value efficiently within a loop.

To implement this improvement, adjust your code as follows:

// Replace line below:
// medianImageData.data[i] = d3.median(arr);

// With:
medianImageData.data[i] = median(arr);

You can explore a functioning example in my modified version of your original Observable notebook.

Answer 2

Your statement

Using d3.median() can be problematic with typed arrays...

While this may have been the assumption, it's not entirely accurate. The d3.median() function internally relies on the d3.quantile() method which starts by utilizing:

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

The use of a Float64Array in this context is crucial for precise calculations. However, if your data is stored as integers in a Uint8ClampedArray, the frequent conversions to floating point values can significantly impact performance.

To address this issue, a custom function median(values) can be crafted based on d3.median() and d3.quantile():

function median(values) {
  // Avoid unnecessary conversion to floating point.
  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);
}

This optimized version eliminates the need for immediate conversion and introduces enhancements tailored specifically for calculating the median value efficiently within a loop.

To implement this improvement, adjust your code as follows:

// Replace line below:
// medianImageData.data[i] = d3.median(arr);

// With:
medianImageData.data[i] = median(arr);

You can explore a functioning example in my modified version of your original Observable notebook.

Calculating the middle value of a canvas array in JavaScript in the most effective manner

Answer №1

Similar questions

Experiencing a problem with obtaining the .offset().top value of an element within an iframe resulting in an

Adding an array field to MongoDB documents using MongoClient in Node.js by referencing another field

Top method for utilizing render props in React

Delayed synchronization between CSS animation timing and JavaScript carousel interval causes a slight lag

Expanding size on hover without affecting the alignment of surrounding elements

Filtering content using a checkbox

Inserting data into a JavaScript database

Using a for loop in JavaScript to dynamically display TextBoxFor(model=> model[i].prop) in an MVC application

Ways to determine the completion of the compilation process in Angular using the $compile service

Determine the frequency of keys and transform the data into an array of objects, with each object corresponding to a key and its frequency

Step-by-step guide for properly transferring PHP MySQL data to ChartJs

XMLHTTP is not accessible in the Department of Health

Exploring the ins and outs of HTML event handlers with JavaScript

"Troubleshooting: Android - getSharedPreferences method not Resolving

Uncovering a hidden div tag in Listview ASP.NET with the power of Javascript

The term "Require" is undefined. The Object.crypto and object.url

Leverage the power of Shopify API to retrieve a list of all products by making a request through

Strategies for aligning the initial lines of text vertically within a table cell

Tips for adding a scroll-to-top button on a page with only a vertical scroll bar

Manipulate and edit an array using JavaScript