图像比较-快速算法

如果你有大量的图像，查看布隆过滤器，它使用多个散列来获得一个概率性但有效的结果。如果图像的数量不是很大，那么像md5这样的加密散列应该足够了。

选择100个随机点可能意味着相似(有时甚至不相似)的图像将被标记为相同，我认为这不是您想要的。如果图像格式不同(png、jpeg等)、大小不同或元数据不同，MD5哈希就无法工作。将所有图像缩小到一个更小的尺寸是一个不错的选择，只要你使用的是一个好的图像库/快速的语言，做一个像素对像素的比较不应该花费太长时间，而且尺寸足够小。

你可以试着让它们变得很小，然后如果它们是一样的，就在更大的尺寸上进行另一次比较——这可能是速度和准确性的良好结合……

正如卡特曼所指出的，您可以使用任何类型的哈希值来查找精确的重复项。

找到近距离图像的一个起点可以是在这里。这是CG公司用来检查修改后的图像是否仍然显示本质上相同的场景的工具。

下面是解决这个问题的三种方法(还有很多其他方法)。

• 第一个是计算机视觉中的标准方法，关键点匹配。这可能需要一些背景知识才能实现，而且可能很慢。

• 第二种方法只使用基本的图像处理，可能比第一种方法更快，并且易于实现。然而，它获得了可理解性，但缺乏健壮性——匹配在缩放、旋转或变色图像上失败。

• 第三种方法既快速又健壮，但可能是最难实现的。

关键点匹配

选100个重要的点比选100个随机点更好。图像的某些部分具有比其他部分更多的信息(特别是在边缘和角落)，这些部分是您希望用于智能图像匹配的部分。谷歌"关键点提取"和"关键点匹配"，你会发现相当多关于这个主题的学术论文。如今，筛选要点可以说是最受欢迎的，因为它们可以在不同的尺度、旋转和光照下匹配图像。一些SIFT实现可以在在这里中找到。

关键点匹配的一个缺点是简单实现的运行时间:O(n^2m)，其中n是每张图像中的关键点数量，m是数据库中的图像数量。一些聪明的算法可能会更快地找到最接近的匹配，比如四叉树或二进制空间分区。

备选方案:直方图法

另一种不太健壮但可能更快的解决方案是为每张图像构建特征直方图，并选择直方图最接近输入图像直方图的图像。我在本科时实现了这个，我们使用了3个颜色直方图(红、绿、蓝)，以及两个纹理直方图，方向和比例。我将在下面给出详细信息，但我应该指出，这只适用于匹配与数据库图像非常相似的图像。用这种方法，重新缩放、旋转或变色的图像可能会失败，但像裁剪这样的小变化不会破坏算法

计算颜色直方图很简单——只需为直方图桶选择一个范围，对于每个范围，计算该范围内颜色的像素数。例如，考虑“绿色”直方图，假设我们为直方图选择4个桶:0-63、64-127、128-191和192-255。然后，对于每个像素，我们查看绿色值，并将计数添加到适当的存储桶中。当我们完成计数时，我们将每个桶的总数除以整个图像中的像素数，以得到绿色通道的标准化直方图。

对于纹理方向直方图，我们首先对图像进行边缘检测。每个边点都有一个垂直于边方向的法向量。我们将法向量的角度量化为0到PI之间的6个桶之一(因为边有180度对称，我们将-PI到0之间的角度转换为0到PI之间的角度)。在计算每个方向上的边缘点数量后，我们有一个表示纹理方向的非归一化直方图，我们通过将每个桶除以图像中边缘点的总数来归一化直方图。

为了计算纹理尺度直方图，对于每个边缘点，我们测量到具有相同方向的下一个最近边缘点的距离。例如，如果边缘点A的方向是45度，算法就会沿着这个方向走，直到找到另一个方向为45度的边缘点(或在合理偏差范围内)。在计算每个边缘点的距离后，我们将这些值转储到直方图中，并通过除以边缘点的总数来归一化。

现在每张图像有5个直方图。要比较两张图像，需要取每个直方图桶之间差值的绝对值，然后将这些值相加。例如，为了比较图像A和B，我们将计算

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1|

对于绿色直方图中的每个桶，并对其他直方图重复，然后将所有结果相加。结果越小，匹配越好。对数据库中的所有图像重复此操作，结果最小的匹配者获胜。您可能希望有一个阈值，超过这个阈值，算法就会得出没有找到匹配的结论。

第三个选择-关键点+决策树

第三种方法可能比其他两种方法快得多，即使用语义文本森林 (PDF)。这包括提取简单的关键点，并使用集合决策树对图像进行分类。这比简单的SIFT关键点匹配要快得多，因为它避免了代价高昂的匹配过程，而且关键点比SIFT简单得多，因此关键点提取也快得多。但是，它保留了SIFT方法对旋转、缩放和光照的不变性，这是直方图方法所缺乏的重要特性。

更新:

我的错误——语义德克顿森林论文并不是专门关于图像匹配的，而是关于区域标记的。进行匹配的原始文件是这个:使用随机树的关键点识别。此外，下面的论文继续发展的想法，并代表了艺术的状态(c. 2010):

• 快速关键点识别使用随机蕨类 -比Lepetit 06更快，更可扩展
• 二元鲁棒独立初等特征 -不太健壮但非常快-我认为这里的目标是在智能手机和其他手持设备上进行实时匹配

如果你想要更一般的东西或使用大数据库(百万图像)，那么 你需要研究图像检索理论(在过去5年里出现了大量的论文)。 在其他答案中有一些提示。但这可能有点过头了，建议直方图方法就可以了。尽管我认为是多种不同的组合

我相信，将图像的大小降低到接近图标的大小，比如48x48，然后转换为灰度，然后取像素之间的差值，或Delta，应该可以很好地工作。因为我们比较的是像素颜色的变化，而不是实际的像素颜色，所以图像是略亮还是略暗并不重要。大的改变会很重要，因为像素太亮/太暗会丢失。您可以跨一行应用此操作，或任意多行应用此操作，以提高准确性。你最多要做47x47=2,209个减法，才能形成一个类似的Key。

我所知道的最好的方法是使用感知哈希。似乎有一个很好的开源实现这样的散列可用:

< a href = " http://phash.org/ " rel = " noreferrer > http://phash.org/ < / >

其主要思想是，通过识别原始图像文件中的显著特征，并对这些特征进行哈希(而不是直接对图像数据进行哈希)，将每张图像简化为一个小的哈希代码或“指纹”。这意味着，相比简单的方法，如将图像缩小到一个小的拇指指纹大小的图像，并比较拇指指纹，假阳性率大大降低。

Phash提供了几种类型的哈希，可用于图像、音频或视频。

这篇文章是我解决方案的起点，这里有很多好主意，所以我想分享我的结果。主要的见解是，我已经找到了一种方法，通过利用phash的速度来解决基于关键点的图像匹配的缓慢问题。

对于一般的解决方案，最好采用几种策略。每种算法都最适合于某些类型的图像转换，您可以利用这一点。

最上面是最快的算法;底部最慢(虽然更准确)。如果在更快的级别上找到了一个很好的匹配，您可能会跳过慢的级别。

• 基于文件哈希(md5,sha1等)的精确副本
• 用于缩放图像的感知哈希(phash)
• 用于修改图像的基于特征的(SIFT)

我的phash治疗效果很好。该方法对缩放后的图像具有较好的精度。它不适用于(感知上)修改过的图像(裁剪、旋转、镜像等)。为了处理散列速度，我们必须使用磁盘缓存/数据库来维护干草堆的散列。

phash真正的好处是，一旦你建立了哈希数据库(对我来说大约是1000张图片/秒)，搜索可以非常非常快，特别是当你可以把整个哈希数据库保存在内存中时。这是相当实用的，因为哈希只有8个字节。

例如，如果您有100万张图像，则需要100万64位哈希值(8 MB)的数组。在某些cpu上，这适用于L2/L3缓存!在实际使用中，我看到corei7的速度超过1千兆哈姆/秒，这只是CPU内存带宽的问题。一个10亿张图片的数据库在64位CPU(需要8GB内存)上是可行的，搜索不会超过1秒!

对于修改/裁剪的图像，看起来像SIFT这样的变换不变特征/关键点检测器是可行的。SIFT将产生很好的关键点，用于检测裁剪/旋转/镜像等。然而，与phash使用的汉明距离相比，描述符compare非常慢。这是一个主要的限制。有很多比较要做，因为有最大的IxJxK描述符比较查找一个图像(I=num个干草堆图像，J=每个干草堆图像的目标关键点，K=每个针状图像的目标关键点)。

为了解决速度问题，我尝试在每个找到的关键点周围使用phash，使用特征大小/半径来确定子矩形。使此工作良好的技巧是增加/缩小半径以生成不同的子矩形水平(在针图像上)。通常情况下，第一个级别(未缩放)将匹配，但通常需要更多。我不是100%确定为什么这是有效的，但我可以想象它可以实现对phash来说太小的功能(phash将图像缩小到32x32)。

另一个问题是SIFT不能最优地分配关键点。如果图像中有一个区域有很多边缘，那么关键点就会聚集在那里，而在其他区域则不会出现任何边缘。我在OpenCV中使用GridAdaptedFeatureDetector来改进分发。不知道什么网格大小是最好的，我使用一个小网格(1x3或3x1取决于图像方向)。

你可能想要在特征检测之前将所有的草堆图像(和针)缩放到更小的尺寸(我在最大尺寸上使用210px)。这将减少图像中的噪声(一直是计算机视觉算法的一个问题)，也将探测器聚焦在更突出的特征上。

对于人物图像，您可以尝试面部检测并使用它来确定要缩放的图像大小和网格大小(例如最大的人脸缩放为100px)。特征检测器考虑多个等级(使用金字塔)，但它将使用多少等级是有限制的(当然这是可调的)。

关键点检测器可能在返回的特性数量少于您想要的特性数量时工作得最好。例如，如果你要求400，得到300，那很好。如果你每次都能拿回400块，那么一些好的功能就会被忽略掉。

针状图像可以比干草堆图像拥有更少的关键点，但仍然可以获得良好的结果。增加更多并不一定能让你获得巨大的收益，例如当J=400和K=40时，我的命中率约为92%。当J=400和K=400时，命中率只能上升到96%。

我们可以利用汉明函数的极快速度来解决缩放、旋转、镜像等问题。可以使用多通道技术。在每次迭代中，转换子矩形，重新散列，并再次运行搜索函数。

我的公司每个月都有来自制造商的大约2400万年图像。我正在寻找一个快速的解决方案，以确保我们上传到我们的目录的图像是新图像。

对于phash/ahash，检查这个:imagehash

我想通过发布我的代码和准确性来扩展*redcalx的帖子。

工作内容:

from PIL import Image
from PIL import ImageFilter
import imagehash


img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
img2=img2.resize((img1.width,img1.height))
else:
img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

以下是我的一些结果:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

希望这能有所帮助!

1. 确切的副本
2. 接近精确重复。(图像的轻微编辑等)
3. 重复(相同的内容，但不同的视角，相机等)

<李>确切副本 使用感知哈希度量可以找到精确的重复项。 phash库在这方面做得很好。我经常用它来清洁 训练数据。 用法(来自github网站)简单如:

from PIL import Image
import imagehash


# image_fns : List of training image files
img_hashes = {}


for img_fn in sorted(image_fns):
hash = imagehash.average_hash(Image.open(image_fn))
if hash in img_hashes:
print( '{} duplicate of {}'.format(image_fn, img_hashes[hash]) )
else:
img_hashes[hash] = image_fn

<李>接近精确重复 在这种情况下，您必须设置一个阈值，并比较它们之间距离的哈希值 其他。这必须通过对图像内容的试错来完成

from PIL import Image
import imagehash


# image_fns : List of training image files
img_hashes = {}
epsilon = 50


for img_fn1, img_fn2 in zip(image_fns, image_fns[::-1]):
if image_fn1 == image_fn2:
continue


hash1 = imagehash.average_hash(Image.open(image_fn1))
hash2 = imagehash.average_hash(Image.open(image_fn2))
if hash1 - hash2 < epsilon:
print( '{} is near duplicate of {}'.format(image_fn1, image_fn2) )

我认为值得在此添加一个我构建的phash解决方案，我们已经使用了一段时间:图片::PHash。它是一个Perl模块，但主要部分是用c语言编写的。它比phash.org快几倍，并且为基于dct的phash提供了一些额外的特性。

我们在MySQL数据库中已经索引了数千万张图片，所以我想要一种快速的方法，同时也想要一种使用MySQL索引的方法(它不适用汉明距离)，这导致我使用了“;用于直接匹配的哈希值，模块文档对此进行了讨论。

使用起来很简单:

use Image::PHash;


my $iph1 = Image::PHash->new('file1.jpg');
my $p1   = $iph1->pHash();


my $iph2 = Image::PHash->new('file2.jpg');
my $p2   = $iph2->pHash();


my $diff = Image::PHash::diff($p1, $p2);