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

Question

我要求调用将颜色值的样本集与已知的值集匹配,以找到完全匹配或匹配在可接受的距离内.我不完全确定哪种算法最适合这个,我正在寻找建议.

我考虑使用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] 

在这种情况下,当我们运行我们的样本集时,我们会发现零匹配,因为没有任何已知颜色的颜色1接近我们的样本集值.然而,让我们的另一种颜色添加到组已知这将返回正匹配:

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

如果样本F在已知集合中存在这些值,我们将获得正面命中,因为它是我们的样本集中的颜色1的确切RGB值.此外,我们需要接受RGB值的不同程度的差异,因此以下也会返回正命中,因为每个RGB值都来自样本集的Color 1值的3位数:

积极点击 :(记住颜色1是:81,177,206)

样品F:80,177206(红色通道是1位的距离)

样品F:81,175,204(绿色和蓝色通道2位的距离)

样本F:82,179,208(距离3位数内的所有三个频道)

但是,如果距离太远,则无法找到匹配项.任何RGB分量必须在3位数内才能触发正结果.因此,如果样本F看起来如下,我们就不会得到积极的结果,因为距离太大了:

否定命中:

样品F:85,177206(红色通道为4位的距离)

样品F:81,170,206(绿色通道为7位的距离)

样品F:81177,200(蓝色通道是6位外)

到目前为止,我们刚刚从样本集中考虑了颜色1.但是,该要求要求考虑整个样品组.因此,如果没有找到颜色1的正匹配,那么我们假设根本没有匹配,并且不考虑样本集中的颜色2和3.

然而,如果我们找到颜色1阳性结果,假设80177206这仅仅是1个位数关在红色通道80 VS 81,那么我们就继续处理颜色2,如果我们找到一个积极的比赛,然后我们处理颜色3等等.

您对最适合此问题的算法有何建议？我需要的东西可以让Known Set在没有太多性能影响的情况下进行扩展.大规模的Known Set中可能会有1M +样本.

我想过使用哈希表,每个颜色一个来构造已知集.所以我可以测试Color 1上的匹配,如果找到,测试颜色2的哈希表,并在找不到更多匹配时停止.如果我通过所有3种颜色/哈希表得到肯定的命中,那么我会有一个整体正面匹配,否则我不会.然而,该方法不允许每种颜色的每个RGB通道中所需的方差.将有太多组合允许构造哈希表来保存它.

在此先感谢,感谢您阅读这篇文章!

Answer 1

最后，在尝试 SQL 和 GPU 编程 (Cudafy) 后，最快、最简单且最可调试的解决方案是使用 Parallel.For() 简单地迭代数据。这种方法在 18 毫秒内处理了 150 万个样本（总共 90M 字节）。