使用索引的寻找相似图片的算法

Question

11

有一些出人意料的图像比较工具，即使图像不完全相同（例如大小、壁纸、亮度/对比度变化）也可以找到相似的图像。以下是一些示例应用程序：

我只试用了第一个，但它们都是为 Windows 开发的，而且不是开源的。Unique Filer 是在 2000 年发布的，主页似乎已经消失了。它非常快（即使在那个年代的电脑上也很快），因为它使用了索引，使用索引比较约 10000 张图像只需要几秒钟时间（而更新索引是可扩展的过程）。

由于这种算法已经存在至少 15 年，并且非常有效，我认为它已经有了文档记录，并且可能已经作为开源库实现了。有没有人知道用于实现这些应用程序的算法或图像检测理论？也许甚至有一个开源实现可用？

我已经查看了这个问题的算法，但它的所有答案都是通过比较一张图片和另一张来解决问题的。对于1000多张图片，这将导致1000^2次比较操作，这不是我要找的。

- Daniel Alder

很明显，仍有人赞同我的问题。感谢大家。但是，stackoverflow只是将我的问题标记为重复的问题，而这个问题并没有回答我的问题（基于索引的算法！）。我本来希望从stackoverflow获得更好的帮助 :-( - Daniel Alder

1

那个“dup”的最新答案已经有3年了，请不要轻易关闭合法的问题。 - OneOfOne

@OneOfOne 这就是为什么你可以在问题上设置赏金的原因。如果你想要对已经提出的问题获得新的答案，只需添加正确的原因和评论来指出答案是否过时或询问回答者是否在此期间提供了更好的解决方案即可。 - Bakuriu

2个回答

2

您所描述的问题通常称为最近邻搜索。由于您要求在大型数据集上实现高效率，因此您需要的是近似最近邻搜索。

其中一种有效的技术是局部敏感哈希（LSH），这些幻灯片提供了一个很好的概述。它的基本思想是使用哈希函数将所有数据投影到低维空间，同时约束相似数据的哈希以高概率碰撞，而不相似的数据以较低概率碰撞。这些概率是算法的参数，可以改变精度和效率之间的平衡。 LSHKIT是LSH的开源实现。

- Florian von Stosch

不幸的是，对于图像来说，魔法和难点在于找到一个真正可用的哈希函数。 - Lothar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Alder · Accepted Answer

与此同时，我分析了UniqueFiler的算法：

尺寸缩小

首先，将所有图像缩小为10x10像素的灰度图像（可能不使用插值）

可能基于4个象限的亮度，进行一些旋转（这一步很危险，因为如果图像过于对称，它有时会“忽略”相似之处）

图像亮度范围完全扩展（最亮 -> 白色，最暗 -> 黑色），然后每像素缩减为2位（4个值）

这些值以每个图像100字节的数组形式存储（加上文件元数据）

...是逐个进行的（对整个数据库进行两个嵌套循环，再加上第三个循环处理100个字节）。今天，我们可能会索引所有4个象限的排序总和，以快速预选出相似的候选项。

通过每两个字节之间的差异进行逐字节比较，但权重小于平方。这100个结果的总和是两个图像之间的最终差异。

我在家里有更详细的信息。如果我有时间，我会将它们添加到这个答案中。我发现这一点后，发现数据库格式实际上是一个没有头文件的gzipped文件，每个图像都包含固定大小的记录。