2

在这篇文章中，我找到了一种确定 RGB 颜色亮度的算法：

亮度（某些色彩空间的标准）：（0.2126*R + 0.7152*G + 0.0722*B）

我想使用这个等式，从 开始rgb(0,0,0)，按照从最低到最高亮度的顺序生成所有 RGB 颜色，然后将它们绘制到 4096x4096 画布上。

我的问题是，对于 1670 万种不同的组合，我无法全部生成它们然后对它们进行排序，而不会导致浏览器崩溃或花费数天时间来完成渲染。所以我想找到一种方法来找到每个数字的倍数，这些数字将相加到下一个最小的数字。

例如，从 和 的 rgb 开始0,0,0，亮度将为 0 ( 0.2126*0 + 0.7152*0 + 0.0722*0 = 0)，下一个最小的发光 rgb 值将是0,0,1因为0.2126*0 + 0.7152*0 + 0.0722*1 = .0722，并且没有一组倍数可以相加为更小的数字。

前 19 个连续的亮度值如下（我可能错过了一两个，因为我手动计算了它们，但希望它有助于说明这一点）：

RGB       =>     Luminence

0,0,0     =>     0
0,0,1     =>     .0722
0,0,2     =>     .1444
1,0,0     =>     .2126
0,0,3     =>     .2166
1,0,1     =>     .2848
0,0,4     =>     .2888
1,0,2     =>     .357
0,0,5     =>     .361
2,0,0     =>     .4252
1,0,3     =>     .4292
0,0,6     =>     .4332
2,0,1     =>     .4974
1,0,4     =>     .5014
0,0,7     =>     .5054
2,0,2     =>     .5696
1,0,5     =>     .5736
0,0,8     =>     .5776
3,0,0     =>     .6378

我似乎找不到任何模式，所以我希望那里可能有一个方程式或编码技巧，可以让我找到三个数字的倍数的最小总和，高于前一个总和，而无需蛮力强制它并检查每个可能的值。

编辑：我做了一些额外的研究，看起来解决方案可能在于使用线性丢番图方程。如果我取每个小数并乘以 1000，得到2126, 7152, & 722. 然后 1 乘 1 计数到2,550,000( 2126*255 + 7152*255 + 722*255)，我可以检查每个数字是否是方程的解2126r + 7152g + 722b = n，其中 n 是当前计数的数字，而 r、g 和 b 是未知数。如果我能做到这一点，我可以计算出下一个连续亮度值处所有可能的 rgb 值，甚至不必将重复亮度值的任何值加倍，我只需要进行 255 万次计算而不是 16.77+ 百万次（每种颜色一个）。如果有人知道如何编写这个方程，或者如果有人有更好的解决方案，我将非常感激。谢谢！

4

4 回答 4

1

您可以利用的一个事实是，序列中的每个三元组的 R、G 或 B 值仅比已输出的三元组大一个。

因此，您可以维护一个BinaryHeap（按亮度排序），其中包含在 R、G 或 B 中比已输出的三元组大 1 的所有三元组，并在循环中执行此操作：

  • 从堆中移除最小元素 (r, g, b)
  • 输出它
  • 将 (r+1, g, b), (r, g+1, b) 和 (r, g, b+1) 添加到堆中，但前提是它们是有效的三元组（所有值小于或等于 255 )，并且仅当它们尚未在堆中时。如果可以从（在允许的范围内 r、g 或 b 中少 1 个）生成的替代三元组具有比 (r, g, b) 更高的亮度，则三元组将不会已经在堆中。

例如，如果 (r+1, g-1, b) 的亮度高于 (r, g, b) 或 (r+1, g-1, b)，则仅添加 (r+1, g-1, b)无效的。由于基于 r, g, b 计算亮度的因子是固定的，因此 (r+1, g-1, b) 将始终具有较低的亮度，并且您应该只添加 (r+1, g, b) 如果 ( r+1, g-1, b) 无效，即 g 为 0 时。

在伪代码中，规则如下：

function addTriplets(r, g, b)
{
    if(g < 255)
       pushTripletToHeap(r, g + 1, b);
    if((g == 0) && (r < 255))
       pushTripletToHeap(r + 1, g, b);
    if((g == 0) && (r == 0) && (b < 255))
       pushTripletToHeap(r, g, b + 1);
}

在开始循环之前将 (0, 0, 0) 三元组推到堆上，并在堆为空时停止循环。

于 2017-01-16T04:40:02.940 回答
1

这是您的问题的算法（忘记了它的名称）：该算法可以列出按某种顺序排序的所有颜色元组 {R,G,B}。在你的情况下，它是亮度上升：color1 < color2 <==> f(color1) < f(color2)，其中 f(color) = 0.2126*R + 0.7152*G + 0.0722*B

  • 初始化：arr = [{r:0, g:0, b:0}]（最小颜色）
  • 重复：
    • 为每个 i 选择 min(iR)：a[iR] = {rR < 255, gR, bR}，并且 cR = {rR + 1, gR, bR} > arr[i]。（选择 arr 中的第一个颜色，如果我们将 1 添加到它的 r 分量，我们会得到一个新颜色，它大于当前 arr 中的所有颜色）
    • iG 和 iB 类似 => 也得到 cG = {rG, gG + 1, bG} 和 cB = {rB, gB, bB + 1}
    • 在cR、cG和cB中选择最小的颜色c
    • 将 c 附加到数组 arr

当找不到这样的 iR、iG 或 iB 时，算法停止。

笔记：

  • arr始终按排序（升序）顺序排列，因为每次将新颜色附加到arr时，它总是大于当前arr中的每个元素。
  • 因为arr是升序的，所以我们只需要比较 cR/cG/cB 和arr的最后一个元素来检查它是否大于arr的每个元素
  • iR、iG 和 iB 通过算法增加
  • 复杂度为 O(N)，其中 N 的颜色数 (2^24) ~ 16M。使用基于堆的算法，复杂度约为 O(NlogN)。

这是我的实现（在 nodejs 6 中测试）

//  use integer to avoid floating point inaccuracy
const lumixOf = {r: 2126, g: 7152, b: 722};

const maxValue = 256;
const components = ['r', 'g', 'b'];

class Color {
  constructor(r, g, b, lum) { 
    this.r = r;
    this.g = g;
    this.b = b;
    this.lum = lum;
  }

  add(component) { 
    const ans = new Color(this.r, this.g, this.b, this.lum);
    if (++ans[component] >= maxValue) return null; // exceed 255
    ans.lum += lumixOf[component];
    return ans;
  }

  greater(color2) {
    // return this.lum > color2.lum;
    if (this.lum !== color2.lum) return this.lum > color2.lum;
    if (this.r !== color2.r) return this.r > color2.r;
    if (this.g !== color2.g) return this.g > color2.g;
    return this.b > color2.b;        
  }
}

let a = [new Color(0, 0, 0, 0)];  //  R, G, B, lumix
let index = {r: 0, g: 0, b: 0};

console.log('#0:', a[0]);
// Test: print the first 100 colors
for (let count = 1; count < 100; ++count) {
  let nextColor = null;
  const len = a.length;
  const currentColor = a[len - 1];
  components.forEach(component => {
    let cIndex = index[component];
    for (; cIndex < len; ++cIndex) {
      const newColor = a[cIndex].add(component);
      if (!newColor || !newColor.greater(currentColor)) continue;

      //  find the minimum next color
      if (nextColor == null || nextColor.greater(newColor)) {
        nextColor = newColor;
      }
      break;
    }
    index[component] = cIndex;
  });

  if (!nextColor) break;  //  done. No more color
  a.push(nextColor);
  console.log('#' + count + ':', nextColor);
}
console.log(a.length);

此实现列出所有 2^24 = 16777216 种颜色（一旦您删除了count < 100主循环中的条件，但您不想打印出这么多行）。如果某些颜色具有相同的亮度值，则将它们按其 R 值排序，然后是 G 值，然后是 B 值。如果每个亮度值只需要一种颜色，请取消注释greater()函数中的第一行 - 然后您将获得 1207615 种具有不同亮度的颜色

于 2017-01-16T15:45:47.930 回答
0

对不起，但我不得不说你在做一些浪费的工作。

RGB 的 8 位量化将在 256 个亮度级别（包括黑色和白色）下产生 1670 万种颜色但是您没有足够的像素在 4K 显示器上显示它们，在 4K 电视标准上将有 3840 x 2160 = 8294400 像素或像 4K 电影标准上的 4096 x 2160 = 8847360。除了 1 像素颜色样本对眼睛的意义是什么，尤其是在 4K 显示器上..？

我建议您使用 7 位量化而不是 8 位。这将为您提供 2^21 => 2097152 个颜色样本，它们将在高清监视器/电视上映射为单个像素，在 4K 监视器/电视上映射为 2x2 像素。美丽的。

代码如下；

"use strict";
var allColors = Array(Math.pow(2,21)),           // All 2^21 colors
         cgbl = Array(128).fill().map(e => []);  // Colors gropuped by luminance
for (var i = 0, len = allColors.length; i < len; i++) allColors[i] = [i>>14, (i&16256)>>7, i&127];
allColors.reduce((g,c) => (g[Math.round(c[0]*0.2126 + c[1]*0.7152 + c[2]*0.0722)].push(c),g), cgbl);
cgbl.forEach((y,i) => console.log(y.length,"Colors at luminance level:",i));

但是请记住，您的 RGB 值现在处于 7 位量化状态。由于我们已经将它们分组为 128 个亮度级别，我还建议您将亮度组（子数组）中的每个 RGB 值映射回 8 位，方法是r << 1; g << 1; b << 1;在显示它们之前将它们的值左移 1 位 ( )。通过使用.map()函子，这是一项微不足道的工作。

于 2017-01-17T13:33:46.677 回答
0

因为我的原始答案已经很长了，所以我做出这个答案是为了澄清算法，正如 OP 所要求的

让我们考虑一个类似的问题（但更容易推理）：

  • 设 A 是一组数字，按升序排列，除了 2、3 和 5 之外没有其他素因数 (Ai = 2^x * 3^y * 5^z)
  • 找到 A 的第 n 个数

当然 A1 = 1 = 2^0 * 3^0 * 5^0

假设在某个步骤，我们已经计算了 A1..An，我们需要找到 A[n+1]

  • 如果 A[n+1] 可以被 2 整除，则 A[n+1] = A[i2]*2 其中 1 <= i2 <= n
  • 如果 A[n+1] 可以被 3 整除，则 A[n+1] = A[i3]*3 其中 1 <= i3 <= n
  • 如果 A[n+1] 可以被 5 整除，则 A[n+1] = A[i5]*5 其中 1 <= i5 <= n

（显然 A[n+1] 至少可以被其中一个整除）

证明：A[n+1] = 2^x * 3^y * 5^z。如果 A[n+1] 可被 2 整除，则 x > 0，因此B = A[n+1]/2 = 2^(x-1) * 3^y * 5^z必须在 A 中。由于 B < A[n+1]，它必须在 A 中位于 A[n+1] 之前，因此 B = A [i2]，其中 1 <= i2 <= n。

所以要找到 A[n+1]，我们可以：

  • 求 A[i2]*2 > A[n] 的最小 i2
  • i3 和 i5 类似
  • ==> A[n+1] = min(A[i2]*2, A[i3]*3, A[i5]*5)

让 A1 = 1，运行这些步骤 (n - 1) 次，我们找到 A 的第 n 个数

现在，如果在每次迭代中找到 A[n+1]，我们使用从 1 到 n 的 3 个 for 循环来计算 i2、i3 和 i5，时间复杂度将为 O(N^2)。但是您可以看到每次迭代的 i2、i3 和 i5 永远不会减少（分别小于前一次迭代的值）。所以我们可以保存那些 i2、i3 和 i5 值，并且在每次迭代中我们只需要：

while (A[i2]*2 <= A[n]) ++i2;
while (A[i3]*3 <= A[n]) ++i3;
while (A[i5]*5 <= A[n]) ++i5;

现在时间复杂度变为O(N)：虽然while循环仍然嵌套在主for 1->n循环中，但只有4个变量从1 -> n递增，可以认为是4个独立循环。您可以使用时钟验证 O(N) 属性并测量不同的运行时间N s

将此算法应用于您的问题：

  • 2、3 和 5 变为 R、G 和 B
  • 整数比较变成你定义的颜色比较函数
  • 如果您需要列出所有 2^24 种颜色，请定义比较函数，以便没有 2 种不同的颜色“相等”（如果 C1 和 C2 是 2 种不同的颜色，则 C1 < C2 或 C2 < C1） - 就像我在原始答案
于 2017-01-19T03:33:56.093 回答