图像比较快速算法

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

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

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

关键点匹配

比随机选取100个点更好的是选取100个点 重要的 keypoint extraction “和” keypoint matching “你会发现很多关于这个主题的学术论文。这些天, SIFT keypoints 可以说,在不同的灯光下,它们可以匹配不同的比例和旋转。可以找到一些SIFT实现 here

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

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

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

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

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

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

对于绿色直方图中的每个桶,重复其他直方图,然后汇总所有结果。结果越小,比赛就越好。对数据库中的所有图像重复此操作,结果最小的匹配将获胜。您可能希望有一个阈值,在该阈值之上,算法会得出没有找到匹配项的结论。

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

semantic texton forests (PDF)。这涉及提取简单的关键点,并使用集合决策树对图像进行分类。这比简单的SIFT关键点匹配要快,因为它避免了昂贵的匹配过程,而且关键点比SIFT简单得多,因此关键点提取要快得多。然而,它保留了SIFT方法对旋转、缩放和照明的不变性,这是直方图方法所缺乏的一个重要特性。

:

我的错误——Semantic Texton Forests论文并不是专门关于图像匹配的,而是关于区域标记的。进行匹配的原始纸张如下所示: Keypoint Recognition using Randomized Trees . 此外,以下论文继续发展这些想法,并代表了最新技术(约2010年):

• Fast Keypoint Recognition using Random Ferns -比Lepett 06更快、更具可扩展性
• BRIEF: Binary Robust Independent Elementary Features -不那么健壮,但速度非常快——我认为这里的目标是在智能手机和其他手持设备上进行实时匹配

我所知道的最好的方法是使用感知散列。这类散列似乎有一个很好的开源实现,位于:

http://phash.org/

phash提供了几种类型的散列,可用于图像、音频或视频。

这篇文章是我解决方案的起点,这里有很多好主意,所以我想我会分享我的结果。主要的见解是,我发现了一种利用phash的速度绕过基于关键点的图像匹配缓慢的方法。

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

• 基于文件哈希(md5、sha1等)的精确副本
• 重缩放图像的感知哈希(PHAH)

我在phash方面取得了很好的成绩。对于重新缩放的图像,精度很高。它不适合(感知地)修改图像(裁剪、旋转、镜像等)。为了解决散列速度问题,我们必须使用磁盘缓存/数据库来维护haystack的散列。

phash真正好的地方是,一旦您构建了哈希数据库(对我来说大约是1000个图像/秒),搜索可以非常非常快,特别是当您可以将整个哈希数据库保存在内存中时。这是相当实用的,因为散列只有8个字节。

例如,如果您有100万个图像,则需要一个包含100万个64位哈希值(8MB)的数组。在某些CPU上,这适合二级/三级缓存!在实际使用中,我看到corei7的比较速度超过了1千兆哈姆/秒,这只是CPU的内存带宽问题。一个10亿的图像数据库在64位CPU上是实用的(需要8GB的RAM),搜索不会超过1秒!

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

为了解决速度问题,我尝试在每个找到的关键点周围使用phash,使用特征尺寸/半径来确定子矩形。使其正常工作的诀窍是增大/缩小半径以生成不同的亚矩形级别(在针图像上)。通常情况下,第一级(无标度)将匹配,但通常需要更多的时间。我不是100%确定为什么会这样,但我可以想象它启用了太小而phash无法使用的功能(phash将图像缩放到32x32)。

另一个问题是,SIFT不会以最佳方式分配关键点。如果图像的某个部分有很多边缘,那么关键点就会聚集在那里,而在另一个区域则不会得到任何关键点。我正在OpenCV中使用GridAdaptedFeatureDetector来改进分布。不确定什么样的网格尺寸最好,我使用的是小网格(1x3或3x1,取决于图像方向)。

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

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

针状图像可以比haystack图像具有更少的关键点,并且仍然可以获得良好的结果。添加更多并不一定会给你带来巨大的收益,例如,当J=400和K=40时,我的命中率约为92%。当J=400和K=400时,命中率仅上升到96%。

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

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

我想说的是,我已经在互联网上进行了广泛的搜索,试图找到一个理想的解决方案。我甚至开发了自己的边缘检测算法。
我已经评估了多个模型的速度和准确性。 红石 说,我推荐phash或ahash。 使用MD5哈希或任何其他加密哈希。除非,否则您只需要精确的图像匹配。图像之间发生的任何大小调整或操作都将产生不同的散列。

对于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

希望这有帮助!

正如cartman指出的,您可以使用任何类型的散列值来查找精确的重复项。

寻找近距离图像的一个起点可能是 here . 这是CG公司用来检查修改后的图像是否仍然显示基本相同的场景的工具。

我有一个想法,它可以工作,它很可能是非常快。 您可以对图像进行子采样,例如80x60分辨率或类似分辨率, 并将其转换为灰度(二次采样后速度会更快)。 处理要比较的两个图像。 或者更好的归一化互相关,如果 然后,如果图像相似,您可以继续使用更复杂的技术 显然,这个算法在数据库中的图像数量方面是线性的 如果需要旋转不变性,则可以计算主导梯度 对于这个小图像,然后整个坐标系可以旋转到标准坐标系

如果您想要更通用的东西或使用大型数据库(数百万张图像),那么 你需要研究图像检索理论(在过去5年中出现了大量的论文)。 快速方法会更好。

我认为,将图像的大小降低到几乎图标大小,比如48x48,然后转换为灰度,然后计算像素之间的差值或增量,应该可以很好地工作。因为我们比较的是像素颜色的变化,而不是实际的像素颜色,所以图像是稍亮还是稍暗都无关紧要。由于像素变得太亮/太暗会丢失,因此大的更改将很重要。您可以在一行或任意多行上应用此选项,以提高精度。为了形成一个可比较的键,最多需要进行47x47=2209的减法运算。

随机选取100个点可能意味着相似(或偶尔甚至不同)的图像将被标记为相同,我认为这不是您想要的。如果图像的格式不同(png、jpeg等),大小不同,或者元数据不同,MD5哈希就不起作用。将所有图像缩小为较小的尺寸是一个不错的选择,只要使用良好的图像库/快速语言,并且尺寸足够小,进行逐像素比较就不会花费太长时间。

如果您有大量图像,请查看 Bloom filter ,它使用多个哈希来获得概率性但有效的结果。如果图像的数量不是很大,那么像md5这样的加密散列就足够了。

1. 精确副本
3. 感知副本(相同的内容,但不同的视图、摄像头等)

一号及;2.比较容易解决。三号。这是非常主观的,仍然是一个研究课题。 我可以为1号和;2. https://github.com/JohannesBuchner/imagehash

1. 精确副本 使用感知散列度量可以找到精确的重复项。 培训数据。 用法(从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

2. 近似精确副本 另外这必须通过对图像内容的反复试验来完成。

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) )