搜索相似的图像，解析一个算法

我最近不得不解决优化重复图像搜索的问题。

现有的解决方案基于H.Chi Wong，Marshall Bern和David Goldberg编写的基于众所周知的Python库Image Match ，该库基于“针对任何图像的图像签名”。

由于多种原因，决定将所有内容重写为Kotlin，同时放弃在ElasticSearch中进行存储和搜索，这需要大量的铁和人力资源来进行支持和管理，而需要在本地内存缓存中进行搜索。

为了理解它的工作原理，我不得不沉迷于“参考” Python代码中，因为原始工作有时并不十分明显，并且在几个地方使我记得“如何绘制猫头鹰”。 实际上，我想分享这项研究的结果，同时讲述一些优化，包括数据量和搜索速度。 也许有人会派上用场。

免责声明：我有可能在某个地方搞砸了，做错了还是不是最佳选择。 好吧，我将很高兴收到任何批评和评论。 :)

运作方式：

1. 图像被转换为​​8位黑白格式（在0-255的值中，一个点是一个字节）
2. 裁剪图像的方式是从四个侧面的每一个中丢弃5％的累积差异（更多信息在下面）。 例如，图像周围的黑框。
3. 选择一个工作网格（默认为9x9），其节点将用作图像签名的参考点。
4. 对于每个参考点，根据其周围的某个区域来计算其亮度。
5. 对于每个参考点，要计算出它比其八个邻居亮/暗多少。 使用了五个渐变，从-2（更暗）到2（更亮）。
6. 所有这些“欢乐”都在一维数组（向量）中展开，并由图像签名调用。

如下检查两个图像的相似性：



d越低越好。 实际上，d <0.3几乎是同一性的保证。

现在更详细。

第一步

我认为谈论转换为灰度毫无意义。

第二步

假设我们有这样的图片：


可以看出，左右两侧有一个3像素的黑框，顶部和底部有一个2像素的黑框，相比之下，我们根本不需要

截止边界由以下算法确定：

1. 对于每一列，我们计算相邻元素的绝对差之和。
   
2. 我们左右修剪对总累积差异的贡献小于5％的像素数。

我们对列也这样做。

一个重要的澄清：如果生成的图像的尺寸不足以进行第4步，则我们不会裁剪！

第三步

好吧，这里的一切都很简单，我们将图片分成相等的部分，然后选择节点。

第四步

锚点的亮度计算为周围方形区域中所有点的平均亮度。 在原始工作中，以下公式用于计算该正方形的边：

第五步

对于每个参考点，计算其亮度与其八个邻居的亮度之差。 对于没有邻居的那些点（上排和下排，左排和右排），差取为0。

此外，这些差异减少为五个等级：


原来是这样的矩阵：

第六步

我认为不需要任何解释。

现在关于优化

在原始工作中，正确地指出，从生成的签名中可以完全消除沿矩阵边缘的零值，因为对于所有图像它们都是相同的。


但是，如果仔细观察，您会发现，对于任何两个邻居，它们的相互渐变将绝对值相等。 因此，实际上，您可以放心地为每个参考点抛出四个重复值，从而将签名的大小减小一半（不包括边零）。


显然，当计算平方和时，对于每个x ，肯定会有一个相等的x'模，并且用于计算范数的公式可以这样写（无需研究重新索引）：


无论是分子还是分母都适用。

此外，在原始工作中，应注意三个位足以存储每个等级。 也就是说，例如，在“无符号长整数”中，将适合21个渐变。 这是一个相当大的节省，但是，另一方面，它在计算两个签名之间的差的平方和时增加了复杂性。 我必须说，这个主意确实让我着迷，直到几天晚上，它突然浮出水面，讲述如何吃鱼 ，这是保存和简化计算的地方。 小心你的手。

我们使用这种方案进行存储，每个等级4位：

是的，只有16个等级适合21个无符号长整数，但是两个特征之差的数组将通过一个xor进行计算，并向右移动15个，并计算每次移位的迭代所设置的位数。 即


该符号对我们而言并不重要，因为所有值都将平方。

另外，如果距离的阈值是预先确定的，我们不再对它的值感兴趣，那么在绕过计算公式后，您可以为简单的一组比特集推导出相当轻量级的过滤条件。

可以在上一篇文章中找到有关此算法优化的更多详细信息以及代码示例。 我另外建议阅读有关它的评论-哈布罗夫斯克居民masyaman提出了几种相当有趣的计算方法，包括使用位魔术将三位灰度打包。

实际上，仅此而已。 谢谢您的关注。 :)