有没有更快的方法在浏览器中计算颜色频率？

Question

我正在尝试计算浏览器中图像的颜色频率 table。

我的策略是

加载图像 canvas
遍历图像数据
增加像素颜色的计数

像这样：

 var canvas = document.getElementById('paper'); 
 var ctx = canvas.getContext('2d'); 
 var imgData = ctx.getImageData(0, 0, canvas.width, canvas.height)

 var color_table = function(data){
      var h = {}
     
      for (let i = 0; i < data.length; i += 4) {
           var c = data.slice(i, i + 4).join(':')
           h[c] = h[c] ? h[c] + 1 : 1;
      }
      return h;
 }

这对于大图像来说非常慢。

我正在考虑：

缩小图像并计算精度损失
将工作分配给一些工人并合并结果

这些是最好的策略吗？有没有办法通过 WebGL 将其并行化？

Answer 1

我不确定你想做什么。您的问题是“颜色频率”，但您的代码是“直方图”

该代码为每种唯一颜色生成一个字符串并将其放入一个对象（哈希映射）中。这可能比图像本身多 16 倍的数据。

255:255:255:255中有最长15个字符的字符串。 JavaScript 将字符串存储为每个字符 2 个字节，因此是 30 个字节
有字符串长度
有一个指向字符串的指针
h 对象中的每个条目都有一个指针
对象的哈希映射中的每个桶都有一个桶对象（假设它是作为哈希映射实现的）

除非图像过饱和或过饱和，否则大多数颜色都是独一无二的？因此，您最终会为每个像素生成至少 64 字节的存储空间。对于 4k x 4k 图像，1gig 内存仅用于您的颜色频率 table。

直方图的定义是数值数据分布的近似表示，而您的代码计算的是精确表示。

我很确定 Photoshop 等应用程序会根据通道 and/or 亮度生成直方图。这就是你真正想要的吗？

你还没有定义 large 或者 slow.

这是一张 3k x 4k 的图片。

在我 6 岁的旧笔记本上使用 canvas 做一个常见的每通道 256 级直方图需要 0.4 秒

示例：

function loadImage(url) {
  return new Promise((resolve, reject) => {
    const img = new Image();
    img.onload = () => resolve(img);
    img.onerror = reject;
    img.crossOrigin = 'anonymous'
    img.src = url;
  });
}

async function main() {
  const img = await loadImage('https://i.imgur.com/uPBNblJ.jpg');
  const ctx = document.createElement('canvas').getContext('2d');
  
  const start = performance.now();
  
  ctx.canvas.width = img.width;
  ctx.canvas.height = img.height;
  ctx.drawImage(img, 0, 0);
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  const data = imageData.data;
  const histogram = [
    new Uint32Array(256),
    new Uint32Array(256),
    new Uint32Array(256),
    new Uint32Array(256),
  ];
  for (let i = 0; i < data.length; ++i) {
    ++histogram[i % 4][data[i]];
  }

  const end = performance.now();
  console.log(`image size: ${img.width}x${img.height}, time: ${((end - start) * 0.001).toFixed(2)}s`);
  
  // show it
  drawHistogram(histogram);
  
  document.body.appendChild(img);
}

function drawHistogram(histogram) {
  const ctx = document.querySelector('canvas').getContext('2d');
  const {width, height} = ctx.canvas;
  const colors = [
    '#F00',
    '#0F0',
    '#00F',
  ];
  // only draw r, g, b
  ctx.globalCompositeOperation = 'lighter';
  for (let c = 0; c < 3; ++c) {
    ctx.fillStyle = colors[c];
    const data = histogram[c];
    // hack because there's too much 0 and 255
    data[0] = 0;  data[255] = 0;
    const max = data.reduce((max, v) => Math.max(max, v), 0);
    for (let x = 0; x < width; ++x) {
      const v = data[x * data.length / width];
      const h = v / max * height;
      ctx.fillRect(x, height - h + 1, 1, h);
    }
  }
}

main();

canvas { 
  border: 1px solid black;
  background: #444;
}

img {
  height: 150px;
}

<canvas width="256" height="150"></canvas>

如果我们不分离通道也会更快。

function loadImage(url) {
  return new Promise((resolve, reject) => {
    const img = new Image();
    img.onload = () => resolve(img);
    img.onerror = reject;
    img.crossOrigin = 'anonymous'
    img.src = url;
  });
}

async function main() {
  const img = await loadImage('https://i.imgur.com/uPBNblJ.jpg');
  const ctx = document.createElement('canvas').getContext('2d');
  
  const start = performance.now();
  
  ctx.canvas.width = img.width;
  ctx.canvas.height = img.height;
  ctx.drawImage(img, 0, 0);
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  const data = imageData.data;
  const histogram = new Uint32Array(256 * 4);
  for (let i = 0; i < data.length; ++i) {
    ++histogram[i % 4 + data[i] * 4];
  }

  const end = performance.now();
  console.log(`image size: ${img.width}x${img.height}, time: ${((end - start) * 0.001).toFixed(2)}s`);
  
  // show it
  drawHistogram(histogram);
  
  document.body.appendChild(img);
}

function drawHistogram(histogram) {
  const ctx = document.querySelector('canvas').getContext('2d');
  const {width, height} = ctx.canvas;
  const colors = [
    '#F00',
    '#0F0',
    '#00F',
  ];
  
  // hack because there's too much 0 and 255
  histogram.fill(0, 0, 4);
  histogram.fill(0, histogram.length - 4, histogram.length);
  const numEntries = histogram.length / 4;
  
  function computeMaxForChannel(c) {
    let max = 0;
    for (let i = c; i < histogram.length; i += 4) {
      max = Math.max(max, histogram[i]);
    }
    return max;
  }  
  
  // only draw r, g, b
  ctx.globalCompositeOperation = 'lighter';
  for (let c = 0; c < 3; ++c) {
    ctx.fillStyle = colors[c];
    const max = computeMaxForChannel(c);
    for (let x = 0; x < width; ++x) {
      const v = histogram[x * numEntries / width * 4 + c];
      const h = v / max * height;
      ctx.fillRect(x, height - h + 1, 1, h);
    }
  }
}

main();

canvas { 
  border: 1px solid black;
  background: #444;
}

img {
  height: 150px;
}

<canvas width="256" height="150"></canvas>

如果您真的想要独特颜色的计数，那么您可能还想计算时间排序（不确定未排序的颜色频率计数会有多好）

function loadImage(url) {
  return new Promise((resolve, reject) => {
    const img = new Image();
    img.onload = () => resolve(img);
    img.onerror = reject;
    img.crossOrigin = 'anonymous'
    img.src = url;
  });
}

async function main() {
  const img = await loadImage('https://i.imgur.com/uPBNblJ.jpg');
  const ctx = document.createElement('canvas').getContext('2d');
  
  const start = performance.now();
  
  ctx.canvas.width = img.width;
  ctx.canvas.height = img.height;
  ctx.drawImage(img, 0, 0);
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  // get a view on the data as 32bit values
  const data = new Uint32Array(imageData.data.buffer);
  // just RGB (no Alpha)
  const histogram = new Uint32Array(256 * 256 * 256);
  for (let i = 0; i < data.length; ++i) {
    ++histogram[data[i] & 0xFFFFFF];
  }

  const sortStart = performance.now();
  // NOTE: sort is commented out below. It's way too slow
  const colors = sortHistogram(histogram);

  const end = performance.now();
  log(`image size: ${img.width}x${img.height}, time: ${((end - start) * 0.001).toFixed(2)}s, sortTime: ${((end - sortStart) * 0.001).toFixed(2)}s`);
  
  // show it
  drawHistogram(histogram, colors);
  
  document.body.appendChild(img);
}

function sortHistogram(histogram) {
  const colors = new Uint32Array(256 * 256 * 256);
  // sorting 2^24 values this way takes too long
  // so some other algo would be better. For now
  // move all the non-0 counts to the front and only
  // sort those 
  let front = 0;
  let back = colors.length - 1;
  for (let i = 0; i < colors.length; ++i) {
    if (histogram[i]) {
      colors[front++] = i;
    } else {
      colors[back--] = i;
    }
  }
//  quicksort(histogram, colors, 0, front - 1);
  return colors;
}

function quicksort(values, indices, lo, hi) {
  const todo = [[lo, hi]];
  while (todo.length) {
    const [lo, hi] = todo.pop();
    if (lo < hi) {
      const p = partition(values, indices, lo, hi);
      todo.push([lo, p - 1]);
      todo.push([p + 1, hi]);
    }
  }
}

function partition(values, indices, lo, hi) {
  const pivot = values[indices[hi]];
  let i = lo;
  for (let j = lo; j < hi; ++j) {
    if (values[indices[j]] >= pivot) {
      swap(indices, i, j);
      ++i;
    }
  }
  swap(indices, i, hi);
  return i;
}

function swap(indices, i, j) {
  const temp = indices[i];
  indices[i] = indices[j];
  indices[j] = temp;
}

function drawHistogram(histogram, colors) {
  // top 100 colors
  for (let i = 0; i < 100; ++i) {
    const color = colors[i];
    const count = histogram[color];
    log(`${i.toString().padStart(3)}: color: #${color.toString(16).padStart(6, '0')}, count: ${count}`);
  }
}

function log(...args) {
  const elem = document.createElement('pre');
  elem.textContent = args.join(' ');
  document.body.appendChild(elem);
}

main();

img { height: 150px; }
pre { margin: 0; }

有没有更快的方法在浏览器中计算颜色频率？

Is there a faster way to calculate color frequency in the browser?

javascript

canvas

webgl