建议一种针对大型已知集进行颜色模式匹配的算法
Suggest an algorithm for color pattern matching against a large known set
我有一个要求，要求将颜色值样本集与已知值集进行匹配，以找到完全匹配或在可接受距离内的匹配。我不完全确定哪种算法最适合这个，我正在寻找建议。
我考虑过使用 SQL 查询，因为我认为这是一种直接的方法，但是，理想情况下，这将在应用程序服务器上的内存中完成，甚至在 GPU 上完成以获得最大速度。
示例:
假设我们得到一组三个 RGB 颜色值，两个蓝色和一个橙色：
样本集：
颜色 1：81,177,206（蓝色）
颜色 2：36、70、224（蓝色）
颜色 3：255、132、0（橙色）
这组 3 个颜色值必须与更大的一组颜色值进行匹配，以查看该组是否存在于其中，或者 3 种颜色中的每一种都具有完全相同的 RGB 值 - 或者 - 如果有任何模式存在于颜色的 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]
在这种情况下，当我们 运行 我们的样本集针对它时，我们会发现零匹配，因为 none 已知颜色的颜色 1 与我们的样本集值很接近.但是，让我们向已知集添加另一种颜色，将 return 为正匹配：
Sample F: [81,177,206], [36, 70, 224], [255, 132, 0]
如果已知集中存在具有这些值的样本 F，我们将获得正命中，因为它与样本集中颜色 1 的 RGB 值完全相同。此外，我们需要接受 RGB 值的不同程度的差异，因此以下也会 return 正命中，因为每个 RGB 值与样本集中颜色 1 的值相差 3 位数以内：
正面点击：（记住颜色 1 是：81,177,206）
样本F：80,177,206（红色通道距离1个数字）
样本 F: 81,175,204（绿色和蓝色通道 2 位数）
样本F：82,179,208（三个通道都在3位数以内）
但是，如果距离太大，则无法找到匹配项。任何 RGB 分量必须在 3 位数以内才能触发肯定结果。因此，如果样本 F 如下所示，我们将 不会 得到肯定的结果，因为距离太大：
负命中：
样本F：85,177,206（红色通道4位数）
样本F: 81,170,206（绿色通道7位数）
样本F：81,177,200（蓝色通道相距6位）
到目前为止，我们只考虑了样本集中的颜色 1。但是，该要求要求考虑整个样本集。因此，如果没有找到颜色 1 的正匹配，那么我们假设根本没有匹配并且不考虑样本集中的颜色 2 和 3。
但是，如果我们找到颜色 1 的正结果，假设 80,177,206 在红色通道 80 与 81 中仅相差 1 个数字，那么我们 do 继续处理颜色2，如果我们找到正匹配，那么我们处理颜色 3 等等。
对于最适合该问题的算法，您有何建议？我需要一些可以让 Known Set 扩展得非常大而不会对性能造成太大影响的东西。规模化的已知集中可能会有 1M+ 个样本。
我考虑过使用哈希表，每个颜色一个来构造已知集。所以我可以测试颜色 1 上的匹配项，如果找到，则测试颜色 2 的哈希表，并在我找不到更多匹配项时停止。如果我通过所有 3 colors/hashtables 并获得正面匹配，那么我将获得总体正面匹配，否则我不会。但是，这种方法不允许每种颜色的每个 RGB 通道中所需的差异。组合太多，无法构建哈希表来容纳所有组合。
提前致谢并感谢您阅读到这里！
保留一个排序列表。使用稳定排序对其进行 3 次排序，首先按 B，然后按 G，然后按 R。这使其按 RGB 顺序排序。根据您的输入，使用二进制搜索找到第一个和最后一个可接受的 R 的索引。然后在该范围内搜索可接受的 G，然后在再次缩小的范围内搜索 B。整个事情应该是 O(lgN).
--
除非我遗漏了某些东西，否则此解决方案概括为匹配一组 3 种颜色、10 种颜色或 k 种颜色。在您的颜色集列表中生成一个索引数组。为准备，如上所述对索引进行稳定排序 3*k 次。要寻找，以相反的顺序进行 3*k 次二进制搜索。
（假设颜色固定在列中。如果不是，您仍然可以使用此方法，但您的索引列表变为 N*k 大小：它需要 A1、A2、A3 的条目。并且在末尾添加一个检查你是否匹配了每列中的一个。）
根据您在问题中的描述和评论中的对话，为什么不使用简单的存储过程和用户定义的类型？通过适当的索引，应该没有性能问题。假设您要比较的颜色集包含多组 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
最后，在试验了 SQL 和 GPU 编程 (Cudafy) 之后，最快、最简单和最可调试的解决方案是使用 Parallel.For() 简单地遍历数据。这种方法在 18 毫秒内处理了 150 万个样本（总字节数为 90M）。
我有一个要求，要求将颜色值样本集与已知值集进行匹配，以找到完全匹配或在可接受距离内的匹配。我不完全确定哪种算法最适合这个，我正在寻找建议。
我考虑过使用 SQL 查询，因为我认为这是一种直接的方法，但是，理想情况下，这将在应用程序服务器上的内存中完成，甚至在 GPU 上完成以获得最大速度。
示例:
假设我们得到一组三个 RGB 颜色值，两个蓝色和一个橙色：
样本集：
颜色 1：81,177,206（蓝色）
颜色 2：36、70、224（蓝色）
颜色 3：255、132、0（橙色）
这组 3 个颜色值必须与更大的一组颜色值进行匹配，以查看该组是否存在于其中，或者 3 种颜色中的每一种都具有完全相同的 RGB 值 - 或者 - 如果有任何模式存在于颜色的 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]
在这种情况下，当我们 运行 我们的样本集针对它时，我们会发现零匹配，因为 none 已知颜色的颜色 1 与我们的样本集值很接近.但是，让我们向已知集添加另一种颜色，将 return 为正匹配：
Sample F: [81,177,206], [36, 70, 224], [255, 132, 0]
如果已知集中存在具有这些值的样本 F，我们将获得正命中，因为它与样本集中颜色 1 的 RGB 值完全相同。此外，我们需要接受 RGB 值的不同程度的差异，因此以下也会 return 正命中，因为每个 RGB 值与样本集中颜色 1 的值相差 3 位数以内：
正面点击：（记住颜色 1 是：81,177,206）
样本F：80,177,206（红色通道距离1个数字）
样本 F: 81,175,204（绿色和蓝色通道 2 位数）
样本F：82,179,208（三个通道都在3位数以内）
但是，如果距离太大，则无法找到匹配项。任何 RGB 分量必须在 3 位数以内才能触发肯定结果。因此，如果样本 F 如下所示，我们将 不会 得到肯定的结果，因为距离太大：
负命中：
样本F：85,177,206（红色通道4位数）
样本F: 81,170,206（绿色通道7位数）
样本F：81,177,200（蓝色通道相距6位）
到目前为止，我们只考虑了样本集中的颜色 1。但是，该要求要求考虑整个样本集。因此，如果没有找到颜色 1 的正匹配，那么我们假设根本没有匹配并且不考虑样本集中的颜色 2 和 3。
但是，如果我们找到颜色 1 的正结果，假设 80,177,206 在红色通道 80 与 81 中仅相差 1 个数字，那么我们 do 继续处理颜色2，如果我们找到正匹配，那么我们处理颜色 3 等等。
对于最适合该问题的算法，您有何建议？我需要一些可以让 Known Set 扩展得非常大而不会对性能造成太大影响的东西。规模化的已知集中可能会有 1M+ 个样本。
我考虑过使用哈希表，每个颜色一个来构造已知集。所以我可以测试颜色 1 上的匹配项，如果找到，则测试颜色 2 的哈希表，并在我找不到更多匹配项时停止。如果我通过所有 3 colors/hashtables 并获得正面匹配，那么我将获得总体正面匹配，否则我不会。但是，这种方法不允许每种颜色的每个 RGB 通道中所需的差异。组合太多，无法构建哈希表来容纳所有组合。
提前致谢并感谢您阅读到这里！
保留一个排序列表。使用稳定排序对其进行 3 次排序，首先按 B，然后按 G，然后按 R。这使其按 RGB 顺序排序。根据您的输入，使用二进制搜索找到第一个和最后一个可接受的 R 的索引。然后在该范围内搜索可接受的 G，然后在再次缩小的范围内搜索 B。整个事情应该是 O(lgN).
-- 除非我遗漏了某些东西，否则此解决方案概括为匹配一组 3 种颜色、10 种颜色或 k 种颜色。在您的颜色集列表中生成一个索引数组。为准备，如上所述对索引进行稳定排序 3*k 次。要寻找，以相反的顺序进行 3*k 次二进制搜索。
（假设颜色固定在列中。如果不是，您仍然可以使用此方法，但您的索引列表变为 N*k 大小：它需要 A1、A2、A3 的条目。并且在末尾添加一个检查你是否匹配了每列中的一个。）
根据您在问题中的描述和评论中的对话，为什么不使用简单的存储过程和用户定义的类型？通过适当的索引，应该没有性能问题。假设您要比较的颜色集包含多组 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
最后，在试验了 SQL 和 GPU 编程 (Cudafy) 之后，最快、最简单和最可调试的解决方案是使用 Parallel.For() 简单地遍历数据。这种方法在 18 毫秒内处理了 150 万个样本（总字节数为 90M）。