Эффективный способ вычисления медианы массива холстов в JavaScript

У меня есть массив N HTMLCanvasElements, которые берутся из N кадров видео, и я хочу вычислить «средний холст» в том смысле, что каждый компонент (r, g, b, непрозрачность) каждого пикселя является медианой соответствующего компонент во всех полотнах.

Видеокадры имеют разрешение 1280x720, поэтому данные о пикселях для каждого холста (полученные с помощью canvas.getContext('2d').getImageData(0, 0, canvas.width, canvas.height).data) представляют собой массив Uint8ClampedArray длиной 3,686,400.

Наивный способ вычисления медианы заключается в следующем:

  • подготовить результат Uint8ClampedArray длиной 3.686.400
  • подготовить временный Uint8ClampedArray длины N
  • цикл от 0 до 3.686.399
    • а) перебрать N холстов, чтобы заполнить массив
    • б) вычислить медиану массива
    • c) сохранить медиану в массиве результатов

Но это очень медленно, даже для 4-х полотен.

Есть ли эффективный способ (или существующий код) для этого? Мой вопрос очень похож на Найти медиану списка изображений, но мне нужно сделать это на JavaScript, а не на Python.

Примечание: для б) я использую d3.median(), который, насколько я понимаю, не работает с типизированными массивами, так что подразумевает преобразование в числа, а затем обратное преобразование в Uint8Clamped.

Примечание 2: я не очень хорошо разбираюсь в шейдерах GLSL, но, возможно, использование графического процессора поможет получить более быстрые результаты. Это потребует передачи данных от процессора к графическому процессору, что требует времени, если делать это неоднократно.

Примечание 3: наивное решение есть: https://observablehq.com/@severo/compute-the-приближенное-медианное-изображение-видео

Вся проблема напоминает мне XY-задачу. Вы уверены, что вычисление медианы для всех данных пикселей решит основную проблему? Возможно, стоит сделать шаг назад, чтобы увидеть более широкую картину, вместо того, чтобы пытаться исправить неоптимальное решение. Чего вы пытаетесь достичь с помощью этой медианы? Существуют ли альтернативные подходы к проблеме? Используя среднее значение, т.е. d3.mean() — вместо этого светится быстрее по сравнению со средним значением. Однако это компромисс, поскольку он легче искажается экстремальными значениями. Все-таки быстро...

altocumulus 11.12.2020 15:59

Спасибо за ваш комментарий. Вы правы, моя проблема X состоит не в том, чтобы иметь срединное изображение видео, а в том, чтобы иметь изображение «фона сцены» (дороги) без «движущихся частей» (машин). Медиана всех кадров обычно дает примерно то, что я хочу, но, конечно, могут быть и другие варианты, и я должен просмотреть литературу.

Sylvain Lesage 11.12.2020 17:45

Обратите внимание, что меня также интересует проблема как таковая: она кажется сложной с точки зрения вычислений, и мне интересно, может ли это проблема, в которой может помочь GPU, или ее нелегко распараллелить из-за шага сортировки.

Sylvain Lesage 11.12.2020 17:48

Я только что собрал ответ, предлагающий решение вашей Y-проблемы. Возможно, это уже делает то, что вы ищете.

altocumulus 11.12.2020 17:50
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
4
4
461
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы написали

Я использую d3.median(), который не работает с типизированными массивами…

Хотя это не совсем так, но ведет в правильном направлении. d3.median() использует метод d3.quantile(), который начинается так:

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

Как видите, здесь действительно используются типизированные массивы, просто это не ваш Uint8ClampedArray , а Float64Array. Поскольку арифметика с плавающей запятой требует гораздо больше вычислительных ресурсов, чем ее целочисленный аналог (включая само преобразование), это оказывает существенное влияние на производительность вашего кода. Выполнение этого около 3 миллионов раз в тесном цикле убивает эффективность вашего решения.

Поскольку вы извлекаете все значения пикселей из Uint8ClampedArray, вы можете быть уверены, что всегда имеете дело с целыми числами. Тем не менее, довольно легко создать собственный function median(values), полученный из d3.median() и 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);
}

Помимо избавления от проблемного преобразования в первой строке, эта реализация дополнительно применяет еще несколько микрооптимизаций, потому что в вашем случае вы всегда ищете 2-квантиль (то есть медиану). Поначалу это может показаться не таким уж большим, но повторение этого несколько миллионов раз в цикле действительно имеет значение.

С минимальными изменениями в вашем собственном коде вы можете назвать это так:

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

Взгляните на мою рабочую вилку вашего блокнота Observable.

Большое спасибо, это полностью полезно с этими оптимизациями! Спасибо за код, вилку блокнота и объяснение, это отличный ответ.

Sylvain Lesage 11.12.2020 18:00

Обратите внимание, что вы можете «предложить» слияние блокнотов в Observable (observablehq.com/@observablehq/fork-share-merge).

Sylvain Lesage 11.12.2020 18:02

Другие вопросы по теме