使用索引查找相似图像的算法

Question

有一些令人惊讶的好图像比较工具,即使它们不完全相同(例如,尺寸,壁纸,亮度/对比度的变化),它们也能找到相似的图像.我在这里有一些示例应用程序:

• Unique Filer 1.4(共享软件):https://web.archive.org/web/20010309014927/http: //uniquefiler.com/
• 快速重复文件查找器(免费软件):http://www.mindgems.com/products/Fast-Duplicate-File-Finder/Fast-Duplicate-File-Finder-About.htm
• 视觉相似性重复图像查找器(付费软件):http://www.mindgems.com/products/VS-Duplicate-Image-Finder/VSDIF-About.htm
• Duplicate Checker(付费软件):http://www.duplicatechecker.com/

我只尝试过第一个,但所有这些都是为Windows开发的,不是开源的.Unique Filer于2000年发布,主页似乎已经消失.它出乎意料地快(即使在当年的计算机上),因为它使用索引并使用索引比较一些10000个图像仅需要几秒钟(并且更新索引是一个可伸缩的过程).

由于这种算法以非常有效的形式存在至少15年,我认为它已被充分记录,并且可能已经作为开源库实现.有谁知道更多关于使用哪种算法或图像检测理论来实现这些应用程序？也许甚至可以使用它的开源实现？

我已经检查了算法找到类似的图像,但所有的答案通过比较一个图像来解决问题.对于1000多张图像,这将导致1000 ^ 2比较操作,这不是我正在寻找的.

Answer 1

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

一种有效的技术是局部敏感哈希 (LSH) ，这些幻灯片对此进行了很好的概述。其基本思想是利用散列函数将所有数据投影到低维空间，约束相似数据的散列以高概率碰撞，不同数据以低概率碰撞。这些概率是算法的参数，可以改变准确性和效率之间的权衡。

LSHKIT是 LSH 的开源实现。