在JavaScript中计算画布数组中位数的有效方法

西尔万·莱斯格

我有一个N来自视频N帧HTMLCanvasElements数组,我想从每个像素的每个分量(r,g,b,不透明度)是相应分量的中位数的意义上计算“中间画布”在所有画布上。

视频帧为1280x720,因此每个画布(通过获取canvas.getContext('2d').getImageData(0, 0, canvas.width, canvas.height).data的像素数据都是长度为3.686.400的Uint8ClampedArray。

计算中位数的简单方法是:

  • 准备一个长度为3.686.400的结果Uint8ClampedArray
  • 准备一个长度为N的临时Uint8ClampedArray
  • 从0循环到3.686.399
    • a)遍历N个画布以填充数组
    • b)计算数组的中位数
    • c)将中位数存储到结果数组

但这非常慢,即使是4张画布也是如此。

是否有一种有效的方法(或现有代码)来做到这一点?我的问题与“查找图像列表的中位数”非常相似,但是我需要使用JavaScript而不是Python来做到这一点。

注意:对于b),据我所知,我使用d3.median()在类型数组上不起作用,因此它意味着转换为数字,然后转换回Uint8Clamped。

注意2:我不太了解GLSL着色器,但是也许使用GPU是获得更快结果的一种方法。但是,这需要将数据从CPU传递到GPU,如果重复进行,则需要花费时间。

注意3:有幼稚的解决方案:https : //observablehq.com/@severo/compute-the-approximate-median-image-of-a-video

高积云

你写了

我使用d3.median()在类型数组上不起作用的方法...

尽管这并非完全正确,但它却朝着正确的方向发展。内部d3.median()使用d3.quantile()这样开始方法:

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

如您所见,实际上这确实利用了类型化数组,它不是您的Uint8ClampedArray而是一个Float64Array因为浮点算术比整数算术(包括转换本身)要消耗更多的计算量,所以这对代码的性能有很大的影响。紧密循环执行此操作大约300万次,会降低解决方案的效率。

由于您是从a检索所有像素值,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);

看看我的可观察笔记本的工作

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章