建议一种算法来匹配大知识库中的颜色模式。

Question

我有一个需求，需要将一组样本颜色值与已知的颜色值进行匹配，以查找完全匹配或接受范围内的匹配。我不确定哪种算法最适合这个需求，希望能得到建议。

我考虑使用SQL查询，因为我认为这是一种简单明了的方法，但理想情况下，应该在应用服务器或甚至GPU上进行内存处理，以获得最大速度。

例如：假设我们有一组三个RGB颜色值，其中两个是蓝色，一个是橙色：

样本集：

颜色1：81,177,206（蓝色）

颜色2：36, 70, 224（蓝色）

颜色3：255, 132, 0（橙色）

必须将这组由3个颜色值组成的样本集与更大的颜色值集进行匹配，以查看是否存在完全匹配或任何模式匹配，其中颜色的RGB值变化在可接受的范围内。假设任何RGB组件的值都可以高于或低于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] 

考虑到这种情况，我们运行样本集时会发现零个匹配项，因为已知颜色中没有一个颜色的Color 1与我们的样本集数值接近。然而，让我们将另一种颜色添加到已知集合中，它将返回一个正匹配项：

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

如果在 Known Set 中存在以下 RGB 值的 Sample F，则会返回匹配结果，因为它与我们样本集中的 Color 1 的确切 RGB 值相同。此外，我们需要接受 RGB 值的差异程度，所以以下内容也将返回匹配结果，因为每个 RGB 值都与样本集中的 Color 1 的值相差不超过 3 位数字：

正匹配：（请记住，Color 1 是：81,177,206）

Sample F: 80，177，206（红色通道相差 1 位数字）

Sample F: 81，175，204（绿蓝通道相差 2 位数字）

Sample F: 82,179,208（三个通道均相差不超过 3 位数字）

然而，如果距离太大，则无法找到匹配项。任何 RGB 组件必须在 3 位数字内才能触发正匹配结果。因此，如果 Sample F 看起来像下面这样，我们将不会得到正匹配结果，因为距离太大：

负匹配：

Sample F: 85，177，206（红色通道相差 4 位数字）

Sample F: 81，170，206（绿色通道相差 7 位数字）

Sample F: 81，177，200（蓝色通道相差 6 位数字）

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

但是，如果我们发现颜色 1 的正匹配结果，比如 80,177,206，它只在红色通道上与 81 相差 1 位数字，那么我们会继续处理颜色 2，如果我们找到了颜色 2 的正匹配结果，那么我们会处理颜色 3 等等。

您对此问题最适合的算法有何建议？我需要一些允许 Known Set 规模扩大而不会影响性能的东西。在实际应用中，Known Set 中可能会有超过 1 百万个样本。

我考虑使用哈希表，每个颜色一个哈希表来构建 Known Set。因此，我可以测试是否存在颜色 1 的匹配项，如果找到，则测试颜色 2 的哈希表，然后在找不到更多匹配项时停止。如果我在所有 3 个颜色/哈希表上都获得了正匹配结果，则说明总体匹配成功，否则就不会。然而，这种方法不允许在每个颜色的 RGB 通道中进行所需的差异。有太多的组合无法构建哈希表来存储所有可能性。

提前感谢您的回答，并感谢您阅读到这里！

- znelson

---

使用C#和OpenCV？我猜你是在用EmguCV？ - Failed Scientist

如果有几组符合条件的已知颜色集合怎么办？已知集合的更改频率与运行此算法的频率相比如何？允许的偏差大小是固定的还是可以随时间变化？ - Zohar Peled

理想情况下，可以实现。我试图使用SurfFeature演示作为起点，但该示例将图像A与图像B进行比较，而我需要将图像A的特征与数据库中的整个已知集合进行比较。我尚未能够修改SurfFeature示例以实现此目的。如果你能指点我正确的方向，我将不胜感激。 - znelson

只要已知集合中的一个样本匹配（或在测试颜色的一个或多个RGB通道上偏差在内），它就是总体成功。已知集合将随时间而增长。偏差可以稍微上下调整以解决误报/漏报问题。但是，偏差在运行算法方面不会改变。换句话说，如果偏差为3，则每个颜色/样本测试的偏差始终为3，直到有一天我决定更改它。 - znelson

@ZoharPeled 是的，它在一个集合内总是有相同数量的颜色。就 SQL 而言，你是正确的。 - znelson

Answer 1

保留一个已排序的列表。用稳定排序将它排序三次，先按B、再按G、最后按R。这样就使得它按RGB顺序排序。根据您的输入，使用二分查找找到第一个和最后一个可接受的R的索引。然后在该范围内搜索可接受的G，再在减小了的范围内搜索B。整个过程的时间复杂度应为O(lgN)。

除非我漏掉了什么，否则此解决方案可以推广到匹配3种颜色、10种颜色或k种颜色。生成一个索引数组，指向您的颜色集列表。为了准备工作，像上面那样稳定地对索引进行3*k次排序。进行搜索时，在相反的顺序中进行3*k个二分查找。 (这假设颜色被固定成列。如果不是这样，您仍然可以使用此方法，但您的索引列表需要达到N*k大小：它需要一个条目A1、A2、A3。最后添加一个检查，以确保您已经匹配了每一列中的一个。)

- AShelly

---

谢谢 - 这只解决了样本集中一个颜色的问题。在上面的例子中，这对于比如颜色1是有效的，但我必须为颜色2和3重复此操作。当我需要测试10种颜色时会发生什么？ - znelson

所以你有一个包含N个集合的大列表，每个集合的大小为k，你只想找到一个集合，其中所有k个值都“足够接近”吗？ - AShelly

我有一个包含N个集合的大列表，每个集合由固定数量的子集（上面例子中的“颜色”）构成。在每个子集中都有三个int值（r、g、b）。我需要找出大列表中哪些集合具有子集，其rgb值与样本集的值相差不超过n位数，但是颜色对颜色进行比较。 - znelson

Answer 2

最终，在尝试使用SQL和GPU编程(Cudafy)后，最快、最简单、最易于调试的解决方案是使用Parallel.For()来迭代数据。这种方法处理了150万个样本(总共9000万字节)，用时18毫秒。

- znelson

Answer 3

根据您在问题描述和评论中的交流，为什么不使用简单的存储过程和用户定义类型呢？通过适当的索引，应该不会出现性能问题。假设您想要比较的颜色集包含多个由3种颜色组成的集合，我可能会这样做：

CREATE TABLE KnownColorSets (
   KC_1_R tinyint NOT NULL,
   KC_1_G tinyint NOT NULL,
   KC_1_B tinyint NOT NULL,
   KC_2_R tinyint NOT NULL,
   KC_2_G tinyint NOT NULL,
   KC_2_B tinyint NOT NULL,
   KC_3_R tinyint NOT NULL,
   KC_3_G tinyint NOT NULL,
   KC_3_B tinyint NOT NULL
)

CREATE TYPE CompareColorSet As TABLE 
(
   CC_1_R tinyint NOT NULL,
   CC_1_G tinyint NOT NULL,
   CC_1_B tinyint NOT NULL,
   CC_2_R tinyint NOT NULL,
   CC_2_G tinyint NOT NULL,
   CC_2_B tinyint NOT NULL,
   CC_3_R tinyint NOT NULL,
   CC_3_G tinyint NOT NULL,
   CC_3_B tinyint NOT NULL
)



CREATE PROCEDURE stpCompareColorSets 
(
    @Exists bit output,
    @CompareColorSet dbo.CompareColorSet readonly
)
AS
  DECLARE @MaxDiviation tinyint = 3 -- This may be taken from a General params table or added as a parameter to the stored procedure
  SET @Exists = 0
  IF EXISTS (
    SELECT 1
    FROM KnownColorSets KC INNER JOIN
    @CompareColorSet CC ON(
      KC_1_R BETWEEN CC_1_R - @MaxDiviation AND CC_1_R - @MaxDiviation
      AND KC_1_G BETWEEN CC_1_G - @MaxDiviation AND CC_1_G - @MaxDiviation
      AND KC_1_B BETWEEN CC_1_B - @MaxDiviation AND CC_1_B - @MaxDiviation

      AND KC_2_R BETWEEN CC_2_R - @MaxDiviation AND CC_2_R - @MaxDiviation
      AND KC_2_G BETWEEN CC_2_G - @MaxDiviation AND CC_2_G - @MaxDiviation
      AND KC_2_B BETWEEN CC_2_B - @MaxDiviation AND CC_2_B - @MaxDiviation

      AND KC_3_R BETWEEN CC_3_R - @MaxDiviation AND CC_3_R - @MaxDiviation
      AND KC_3_G BETWEEN CC_3_G - @MaxDiviation AND CC_3_G - @MaxDiviation
      AND KC_3_B BETWEEN CC_3_B - @MaxDiviation AND CC_3_B - @MaxDiviation
    )
  ) 
  SET @Exists = 1

- Zohar Peled

---

谢谢 - 这正是我现在正在尝试的。我的感觉是，由于表中的总行数将在低百万级别，并且SQL服务器在查询计划方面非常高效，所以我使用这种方法比使用我不熟悉的C#数据结构更有成功的机会。 - znelson

SQL的优势在于处理大量数据，对于一个良好索引的SQL服务器表来说，几百万级别的数据量也不算什么。另一个优点是你不需要自己编写搜索算法。 - Zohar Peled

@znelson 你的表和类型上有任何索引吗？ - Zohar Peled

@ZoharPeled 我尝试了有索引和没有索引的测试。它们确实提高了性能，但时间仍然是250-300毫秒，而 PLINQ 大约是180-200毫秒。 - znelson

@znelson 我猜 PLINQ 是一个更好的解决方案 :-) - Zohar Peled