algorithm - 跟进：按独特性“排序”颜色

Question

如果给你 N 个最大距离的颜色（以及一些相关的距离度量），你能想出一种方法来将这些颜色排序成某种顺序，使第一个 M 也合理地接近最大不同的集合吗？

换句话说，给定一堆不同的颜色，想出一个排序，这样我就可以从一开始就使用我需要的尽可能多的颜色，并合理地确保它们都是不同的，并且附近的颜色也非常不同（例如，蓝红色不在红蓝色旁边）。

随机化是可以的，但肯定不是最优的。

澄清：给定一些大型且视觉上不同的颜色集（比如 256 或 1024），我想对它们进行排序，以便当我使用第一个，比如 16 种颜色时，我得到一个视觉上相对不同的颜色子集。这大致相当于说我想对这个 1024 的列表进行排序，以便单个颜色在视觉上越接近，它们在列表中的距离越远。

score 3 · Accepted Answer

在我看来，这听起来也像是某种阻力图，您可以在其中尝试绘制出阻力最小的路径。如果您反转要求，最大阻力的路径，它也许可以用来产生一个从一开始就产生最大差异的集合，并且到最后开始回到更接近其他值的值。

例如，这是一种可能做你想做的事的方法。

计算从每种颜色到所有其他颜色的距离（参考您的其他帖子）
将每种颜色的距离相加，这可以指示该颜色与所有其他颜色的总距离
按距离排序列表，向下

这似乎会产生一个列表，该列表以距离所有其他颜色最远的颜色开始，然后向下，接近列表末尾的颜色通常更接近其他颜色。

编辑：阅读您对我的第一篇文章的回复，关于空间细分，不完全符合上述描述，因为接近其他颜色的颜色会落在列表的底部，但假设您在某处有一组颜色，在该集群中的至少一种颜色将位于列表的开头附近，并且通常是与所有其他颜色最远的颜色。如果这是有道理的。

score 3 · Accepted Answer

这个问题被称为颜色量化，并且有许多众所周知的算法： http://en.wikipedia.org/wiki/Color_quantization 我知道有人实施了八叉树方法，效果很好。

score 3 · Accepted Answer

感觉对您来说似乎很重要，在这种情况下，您可能需要考虑使用感知色彩空间，例如 YUV、YCbCr 或 Lab。每次我使用它们时，它们给我的结果都比单独使用 sRGB 好得多。

与 sRGB 相互转换可能会很痛苦，但在您的情况下，它实际上可以使算法更简单，并且作为奖励，它也主要适用于色盲！

score 3 · Accepted Answer

N 个最远的颜色可以被认为是 3 维（颜色）空间中分布良好的一组点。如果您可以从Halton 序列中生成它们，那么任何前缀（前 M 个颜色）也由分布良好的点组成。

score 2 · Accepted Answer

您可以根据与任何索引颜色的最小距离的最大距离对候选颜色进行排序。

使用欧几里得颜色距离：

public double colordistance(Color color0, Color color1) {
    int c0 = color0.getRGB();
    int c1 = color1.getRGB();
    return distance(((c0>>16)&0xFF), ((c0>>8)&0xFF), (c0&0xFF), ((c1>>16)&0xFF), ((c1>>8)&0xFF), (c1&0xFF));
}

public double distance(int r1, int g1, int b1, int r2, int g2, int b2) {
    int dr = (r1 - r2);
    int dg = (g1 - g2);
    int db = (b1 - b2);
    return Math.sqrt(dr * dr + dg * dg + db * db);
}

虽然你可以用你想要的任何东西替换它。它只需要一个颜色距离例程。

public void colordistancesort(Color[] candidateColors, Color[] indexColors) {
    double current;

    double distance[] = new double[candidateColors.length];
    for (int j = 0; j < candidateColors.length; j++) {
        distance[j] = -1;
        for (int k = 0; k < indexColors.length; k++) {
            current = colordistance(indexColors[k], candidateColors[j]);
            if ((distance[j] == -1) || (current < distance[j])) {
                distance[j] = current;
            }
        }
    }

    //just sorts.
    for (int j = 0; j < candidateColors.length; j++) {
        for (int k = j + 1; k < candidateColors.length; k++) {
            if (distance[j] > distance[k]) {
                double d = distance[k];
                distance[k] = distance[j];
                distance[j] = d;

                Color m = candidateColors[k];
                candidateColors[k] = candidateColors[j];
                candidateColors[j] = m;
            }
        }
    }
}

score 2 · Accepted Answer

如果我正确理解了这个问题，您希望在给定一些距离函数d的情况下获得颜色之间平均距离最大的M颜色子集。

换句话说，将最初的N个颜色集合视为一个大型的无向图，其中所有颜色都相互连接，您希望找到访问任何M个节点的最长路径。

恐怕解决 NP 完全图问题超出了我的范围，但您可以尝试运行一个简单的物理模拟：

在色彩空间中生成M个随机点
计算每个点之间的距离
计算将其从所有其他点移开的每个点的排斥向量（使用 1 /（距离^ 2）作为向量的大小）
将每个点的排斥向量相加
根据求和的斥力向量更新每个点的位置
约束任何超出范围的坐标（例如亮度变为负值或高于一）
从步骤 2 开始重复，直到点稳定
对于每个点，从N的原始集合中选择最接近的颜色

它远非高效，但对于小M而言，它可能足够高效，并且会给出接近最佳的结果。

如果您的颜色距离函数很简单，则可能有一种更确定的方式来生成最佳子集。

score 2 · Accepted Answer

从两个列表开始。CandidateColors，最初包含您的不同颜色和 SortedColors，最初是空的。
选择任何颜色并将其从 CandidateColors 中删除，然后放入 SortedColors。这是第一种颜色，也是最常见的颜色，因此是选择适合您的应用程序的颜色的好地方。
对于 CandidateColors 中的每种颜色，计算其总距离。总距离是从 CandidateColor 到 SortedColors 中每种颜色的距离之和。
从 CandidateColors 中删除总距离最大的颜色，并将其添加到 SortedColors 的末尾。
如果 CandidateColors 不为空，请返回步骤 3。

这个贪心算法应该会给你很好的结果。

score 1 · Accepted Answer

你的意思是从一组 N 种颜色中，你需要选择 M 种颜色，其中 M < N，使得 M 是 M 空间中 N 种颜色的最佳表示？

作为一个更好的例子，将真彩色（24 位色彩空间）减少到 8 位映射色彩空间（GIF？）。

对此有量化算法，例如ImageMagic 使用的自适应空间细分算法。

这些算法通常不只是从源空间中挑选现有颜色，而是在目标空间中创建最接近源颜色的新颜色。作为一个简化示例，如果您在原始图像中有 3 种颜色，其中两种是红色（具有不同的强度或蓝色等），第三种是蓝色，并且需要减少到两种颜色，则目标图像可能具有红色那是原始图像中原始两个红色+蓝色的某种平均值。

如果您需要其他内容，那么我不明白您的问题:)

score 1 · Accepted Answer

您可以将它们拆分为 RGB HEX 格式，以便您可以将 R 与不同颜色的 R 进行比较，与 G 和 B 相同。

与 HTML 格式相同

XX XX XX
RR GG BB

00 00 00 = black
ff ff ff = white
ff 00 00 = red
00 ff 00 = green
00 00 ff = blue

因此，您唯一需要决定的是您希望颜色有多接近，以及对于被视为不同的段而言，可接受的差异是多少。

algorithm - 跟进：按独特性“排序”颜色

9 回答 9

Related

Reference