c# - 建议一种针对大型已知集进行颜色模式匹配的算法

Question

我有一个要求，要求将颜色值样本集与已知值集进行匹配，以找到完全匹配或在可接受距离内的匹配。我不完全确定哪种算法最适合于此，我正在寻找建议。

我考虑过使用 SQL 查询，因为我认为这将是一种简单的方法，但是，理想情况下，这将在应用程序服务器上的内存中完成，甚至在 GPU 上完成以获得最大速度。

示例 :

假设我们有一组三个 RGB 颜色值，两个蓝色和一个橙色:

样本集:

颜色 1:81,177,206(蓝色)

颜色 2:36、70、224(蓝色)

颜色 3:255、132、0(橙色)

这组 3 种颜色值必须与一组更大的颜色值相匹配，以查看其中是否存在该组，或者对于 3 种颜色中的每一种都具有相同的精确 RGB 值 - 或者 - 如果存在任何模式，其中存在 RGB 值颜色的变化在可接受的范围内。让我们假设任何 RGB 分量的值最多可以高 3 位或低 3 位。

假设我们将搜索的大量已知颜色值如下所示:

已知集:

            Color 1          Color 2       Color 3
Sample A: [25, 25, 25],    [10, 10, 10], [100, 100, 100] 

Sample B: [125, 125, 125], [10, 10, 10], [200, 200, 200] 

Sample C: [13, 87, 255],   [10, 10, 10], [100, 100, 100] 

Sample D: [67, 111, 0],    [10, 10, 10], [200, 200, 200] 

Sample E: [255, 255, 255], [10, 10, 10], [100, 100, 100] 

鉴于这种情况，当我们针对它运行我们的样本集时，我们会发现零匹配，因为没有任何已知颜色的颜色 1 与我们的样本集值接近。但是，让我们向已知集添加另一种颜色，该颜色将返回正匹配:

Sample F: [81,177,206], [36, 70, 224], [255, 132, 0]

如果样本 F 在已知集中存在这些值，我们将获得正命中，因为它是样本集中颜色 1 的确切 RGB 值。此外，我们需要接受 RGB 值的不同程度的差异，因此以下内容也将返回正命中，因为每个 RGB 值与样本集中颜色 1 的值在 3 位以内:

正面命中 :(记住颜色1是:81,177,206)

sample F: 80 ,177,206(红色 channel 距离 1 位数)

示例 F:81， 175 , 204 (绿色和蓝色 channel 2 位数远)

sample F: 82,179,208 (三位数之内的所有三个 channel )

但是，如果距离太大，则找不到匹配项。任何 RGB 分量必须在 3 位数以内才能触发阳性结果。因此，如果样本 F 如下所示，我们将 不是 因为距离太大而得到正结果:

否定命中:

sample F: 85 ,177,206(红色 channel 距离 4 位数)

示例 F:81， 170 ,206(绿色 channel 距离 7 位数字)

样本 F:81,177， 200 (蓝色 channel 距离 6 位数字)

到目前为止，我们只考虑了样本集中的颜色 1。然而，要求需要考虑整个样本集。因此，如果找不到颜色 1 的正匹配，那么我们假设根本没有匹配，并且不考虑样本集中的颜色 2 和 3。

但是，如果我们发现颜色 1 的结果为正，假设为 80,177,206，它在红色 channel 80 与 81 中仅相差 1 位数，那么我们 做 继续处理颜色 2，如果我们找到一个正匹配，那么我们处理颜色 3，依此类推。

你对最适合这个问题的算法有什么建议？我需要一些可以让已知集扩展到非常大而不会对性能造成太大影响的东西。已知集中可能有 100 万个以上的样本。

我想过使用哈希表，每个颜色一个来构建已知集。因此，我可以测试颜色 1 是否匹配，如果找到，则测试颜色 2 的哈希表，并在找不到更多匹配项时停止。如果我通过了所有 3 种颜色/哈希表并获得了正面命中，那么我将获得总体正面匹配，否则我不会。但是，这种方法不允许每种颜色的每个 RGB channel 所需的差异。将有太多的组合来允许构建哈希表来保存所有内容。

在此先感谢并感谢您阅读本文!

Answer 1

保留一个排序列表。使用稳定排序对其进行三次排序，首先按 B，然后按 G，然后按 R。这使其按 RGB 顺序排序。根据您的输入，使用二进制搜索找到第一个和最后一个可接受的 R 的索引。然后在该范围内搜索可接受的 G，然后在再次缩小的范围内搜索 B。整个过程应该是 O(lgN)。

——
除非我遗漏了一些东西，否则这个解决方案概括为匹配一组 3 种颜色，或 10 种颜色或 k 种颜色。将索引数组生成到您的颜色集列表中。准备，稳定排序索引 3*k 次，如上。要寻找，请以相反的顺序进行 3*k 次二分搜索。

(这假设颜色固定在列中。如果不是，您仍然可以使用此方法，但您的索引列表将变为 N*k 大小:它需要 A1、A2、A3 的条目。最后添加一个检查您是否从每一列中匹配了一个。)