У меня есть массив N
HTMLCanvasElements, которые берутся из N кадров видео, и я хочу вычислить «средний холст» в том смысле, что каждый компонент (r, g, b, непрозрачность) каждого пикселя является медианой соответствующего компонент во всех полотнах.
Видеокадры имеют разрешение 1280x720, поэтому данные о пикселях для каждого холста (полученные с помощью canvas.getContext('2d').getImageData(0, 0, canvas.width, canvas.height).data
) представляют собой массив Uint8ClampedArray длиной 3,686,400.
Наивный способ вычисления медианы заключается в следующем:
Но это очень медленно, даже для 4-х полотен.
Есть ли эффективный способ (или существующий код) для этого? Мой вопрос очень похож на Найти медиану списка изображений, но мне нужно сделать это на JavaScript, а не на Python.
Примечание: для б) я использую d3.median(), который, насколько я понимаю, не работает с типизированными массивами, так что подразумевает преобразование в числа, а затем обратное преобразование в Uint8Clamped.
Примечание 2: я не очень хорошо разбираюсь в шейдерах GLSL, но, возможно, использование графического процессора поможет получить более быстрые результаты. Это потребует передачи данных от процессора к графическому процессору, что требует времени, если делать это неоднократно.
Примечание 3: наивное решение есть: https://observablehq.com/@severo/compute-the-приближенное-медианное-изображение-видео
Спасибо за ваш комментарий. Вы правы, моя проблема X состоит не в том, чтобы иметь срединное изображение видео, а в том, чтобы иметь изображение «фона сцены» (дороги) без «движущихся частей» (машин). Медиана всех кадров обычно дает примерно то, что я хочу, но, конечно, могут быть и другие варианты, и я должен просмотреть литературу.
Обратите внимание, что меня также интересует проблема как таковая: она кажется сложной с точки зрения вычислений, и мне интересно, может ли это проблема, в которой может помочь GPU, или ее нелегко распараллелить из-за шага сортировки.
Я только что собрал ответ, предлагающий решение вашей Y-проблемы. Возможно, это уже делает то, что вы ищете.
Вы написали
Я использую
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.
Большое спасибо, это полностью полезно с этими оптимизациями! Спасибо за код, вилку блокнота и объяснение, это отличный ответ.
Обратите внимание, что вы можете «предложить» слияние блокнотов в Observable (observablehq.com/@observablehq/fork-share-merge).
Вся проблема напоминает мне XY-задачу. Вы уверены, что вычисление медианы для всех данных пикселей решит основную проблему? Возможно, стоит сделать шаг назад, чтобы увидеть более широкую картину, вместо того, чтобы пытаться исправить неоптимальное решение. Чего вы пытаетесь достичь с помощью этой медианы? Существуют ли альтернативные подходы к проблеме? Используя среднее значение, т.е.
d3.mean()
— вместо этого светится быстрее по сравнению со средним значением. Однако это компромисс, поскольку он легче искажается экстремальными значениями. Все-таки быстро...