关于算法：跟进：通过独特性对颜色进行”排序”

Followup: “Sorting” colors by distinctiveness

原始问题

如果为您提供了N种最大距离的颜色(以及一些相关的距离度量标准)，您是否可以提出一种将这些颜色按某种顺序进行排序的方法，以使前M个也可以合理地接近最大不同的颜色集？铅>

换句话说，给定一堆不同的颜色，提出一个顺序，这样我就可以从开始就使用任意数量的颜色，并可以有把握地保证它们都是不同的，并且附近的颜色也非常不同(例如，蓝红色不紧跟红蓝色)。

随机化是可以的，但肯定不是最佳选择。

说明：给定一些大的，视觉上不同的颜色(例如256或1024)，我想对它们进行排序，这样当我使用第一个(例如16种)时，我会得到一个相对视觉上相对明显的颜色子集。大致上，这相当于说我要对1024个列表进行排序，以便视觉上各个颜色越接近，它们在列表中的距离就越远。

可以将N个最大距离的颜色视为3维(彩色)空间中一组分布良好的点。如果可以从Halton序列生成它们，则任何前缀(前M个颜色)也将包含分布良好的点。

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

与sRGB进行转换可能会很痛苦，但是在您的情况下，它实际上可以使算法更简单，而且，它还能在大多数情况下适用于色盲！

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

在我看来，这听起来像某种电阻图，您尝试在其中绘制出最小电阻的路径。如果您颠倒了要求，即最大电阻的路径，则可能会使用它来生成一组，从一开始就产生最大的差值，直到结束时才开始返回更接近其他值的值。

例如，这是一种也许可以做您想要的事情的方法。

计算每种颜色到所有其他颜色的距离(请参阅您的其他文章)

总结每种颜色的距离，这可以指示该颜色与所有其他颜色的总距离

按距离排序列表，向下排序

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

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

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

使用欧几里得颜色距离：

1
2
3
4
5
6
7
8
9
10
11
12

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);
}

尽管您可以将其替换为所需的任何东西。它只需要一个色距例程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
}
}
}
}

从两个列表开始。 CandidateColors(最初包含您的不同颜色)和SortedColors(最初为空)。

选择任何颜色并将其从CandidateColors中删除，然后将其放入SortedColors中。这是第一种颜色，并且将是最常见的颜色，因此它是选择适合您的应用程序的颜色的好地方。

对于CandidateColors中的每种颜色，计算其总距离。总距离是从CandidateColor到SortedColors中每种颜色的距离之和。

删除与CandidateColors的总距离最大的颜色，并将其添加到SortedColors的末尾。

如果CandidateColors不为空，请返回到步骤3。

此贪婪算法应会给您带来良好的效果。

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

通过另一种方式，将最初的N种颜色视为一个连接所有颜色的大型无向图，您希望找到访问任何M个节点的最长路径。

恐怕我无法解决NP完全图的问题，但是您可以尝试运行简单的物理模拟：

在色彩空间中生成M个随机点

计算每个点之间的距离

计算每个点的排斥向量，以使其远离所有其他点(使用1 /(距离^ 2)作为向量的大小)