图像比较-快速算法

image algorithm comparison computer-vision

280650 观看

9回复

10212 作者的声誉

我正在寻找创建图像的基本表,然后将其与任何新图像进行比较,以确定新图像是否与基础完全相同(或近似)。

例如:如果您想减少同一图像的存储100次,则可以存储它的一个副本并提供指向它的参考链接。输入新图像后,您想与现有图像进行比较以确保它不是重复的...想法吗?

我的一个想法是缩小到小缩略图,然后随机选择100个像素位置并进行比较。

作者: meade 的来源 发布者: 2009 年 5 月 9 日

回应 (9)


2

10488 作者的声誉

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

作者: jdigital 发布者: 09.05.2009 08:26

3

1802 作者的声誉

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

您可以尝试将它们缩小,然后如果它们相同,则在更大的尺寸上进行另一个比较-可能是速度和准确性的完美结合...

作者: HarryM 发布者: 09.05.2009 08:31

6

712 作者的声誉

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

寻找接近图像的起点可能在这里。CG公司使用此工具来检查修改后的图像是否仍显示基本相同的场景。

作者: Tobiesque 发布者: 09.05.2009 08:47

441

8573 作者的声誉

决定

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

  • 第一种是计算机视觉,关键点匹配的标准方法。这可能需要一些背景知识来实施,并且可能很慢。

  • 第二种方法仅使用基本图像处理,并且可能比第一种方法更快,并且易于实现。但是,它在可理解性上获得的东西却缺乏鲁棒性-在缩放,旋转或变色的图像上匹配失败。

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

关键点匹配

比选择100个随机点好得多,而是选择100个重要点。图像的某些部分比其他部分(尤其是在边缘和角落)具有更多信息,而这些正是您要用于智能图像匹配的部分。Google的“ 关键点提取 ”和“ 关键点匹配 ”,您会发现很多关于该主题的学术论文。如今,SIFT关键点可以说是最受欢迎的,因为它们可以匹配不同比例,旋转和光照下的图像。一些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方法对旋转,缩放和照明的不变性,这是直方图方法缺少的一个重要功能。

更新

我的错误-Semantic Texton Forests论文不是专门针对图像匹配,而是针对区域标注。进行匹配的原始论文是: 使用随机树进行关键点识别。此外,以下论文继续发展这些思想并代表了最新技术水平(约2010年):

作者: Kyle Simek 发布者: 09.05.2009 09:27

6

362 作者的声誉

我有一个主意,它可以奏效,而且很有可能很快。您可以以80x60分辨率或类似分辨率对图像进行二次采样,然后将其转换为灰度(二次采样后速度会更快)。处理要比较的两个图像。然后运行两个图像(查询图像以及来自db的每个图像)之间的平方差的平方和,或者运行更好的归一化互相关,如果两个图像相似,则响应接近1。然后,如果图像相似,则可以继续使用更复杂的技术来验证它是否为相同图像。显然,就您的数据库中的图像数量而言,此算法是线性的,因此即使在现代硬件上,它每秒将非常快地达到10000个图像。如果您需要旋转不变,则可以为这个小图像计算一个主要梯度,然后可以将整个坐标系旋转到规范方向,尽管这样会更慢。不,这里没有缩放的不变性。

如果您想要更通用的东西或使用大型数据库(上百万张图片),则需要研究图片检索理论(最近五年出现了大量论文)。在其他答案中有一些指针。但这可能是过大的,建议的直方图方法可以胜任。尽管我认为将许多不同的快速方法结合起来会更好。

作者: Denis C 发布者: 11.06.2009 09:22

5

173 作者的声誉

我认为,将图像的大小降低到几乎是图标的大小(例如48x48),然后转换为灰度,然后考虑像素之间的差异,即Delta,应该很好。因为我们是在比较像素颜色的变化,而不是实际像素颜色的变化,所以图像的亮度是多少还是暗一点都不重要。大的变化将很重要,因为像素太亮/太暗将丢失。您可以将其应用于一行,也可以根据需要将其应用到任意行中以提高准确性。您最多需要进行47x47 = 2,209次减法,以形成可比较的Key。

作者: Tanoshimi 发布者: 05.11.2011 01:04

80

4677 作者的声誉

我所知道的最好的方法是使用感知哈希。在以下位置可以找到这种哈希的良好开源实现:

http://phash.org/

主要思想是,通过识别原始图像文件中的显着特征并对这些特征的紧凑表示进行哈希处理(而不是直接对图像数据进行哈希处理),将每个图像简化为小的哈希码或“指纹”。这意味着通过一种简单的方法(例如将图像缩小到很小的指纹大小的图像并比较指纹)可以大大降低误报率。

phash提供了多种类型的哈希,可用于图像,音频或视频。

作者: redcalx 发布者: 09.11.2011 10:17

34

556 作者的声誉

这篇文章是我解决方案的起点,这里有很多好主意,所以我虽然会分享我的结果。我的主要见解是,我找到了一种方法,可以通过利用相位速度来解决基于关键点的图像匹配的缓慢性。

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

最顶端的是最快的算法;在最慢的底部(尽管更准确)。如果在较快的级别找到合适的匹配项,则可以跳过较慢的匹配项。

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

我的phash效果非常好。精度对于重新缩放的图像来说很好。这对(在感觉上)修改过的图像(裁剪,旋转,镜像等)不利。为了处理哈希速度,我们必须使用磁盘缓存/数据库来维护干草堆的哈希值。

关于phash的真正好处是,一旦您构建了哈希数据库(对我而言,它约为1000张图像/秒),搜索就可以非常非常快,特别是当您可以将整个哈希数据库保存在内存中时。这是相当实用的,因为哈希只有8个字节。

例如,如果您有一百万个图像,则将需要一百万个64位哈希值(8 MB)的数组。在某些CPU上,这适合L2 / L3缓存!在实际使用中,我看到corei7的速度超过1 Giga-hamm / sec,这只是CPU的内存带宽问题。一个十亿图像数据库可以在64位CPU(需要8GB RAM)上使用,并且搜索不会超过1秒!

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

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

另一个问题是,SIFT不会以最佳方式分配关键点。如果图像的某个部分的边缘很多,则关键点将聚集在此处,而其他区域则不会有任何关键点。我在OpenCV中使用GridAdaptedFeatureDetector来改善分布。不确定哪种网格尺寸最佳,我使用的是小网格(根据图像方向,为1x3或3x1)。

您可能希望在进行特征检测之前将所有干草堆图像(和针头)缩放到较小的尺寸(我沿最大尺寸使用210像素)。这将减少图像中的噪声(对于计算机视觉算法而言始终是一个问题),还将使检测器专注于更突出的功能。

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

当关键点检测器返回的数量少于您想要的功能数量时,它可能会工作得最好。例如,如果您要求400并取回300,那很好。如果您每次都得到400,那么可能不得不放弃一些出色的功能。

针图像可以比干草堆图像具有更少的关键点,并且仍然可以获得良好的效果。添加更多并不一定能获得巨大收益,例如,在J = 400和K = 40的情况下,我的点击率约为92%。在J = 400和K = 400的情况下,命中率仅上升到96%。

我们可以利用汉明功能的极高速度来解决缩放,旋转,镜像等问题。可以使用多遍技术。在每次迭代中,变换子矩形,重新哈希,然后再次运行搜索功能。

作者: wally 发布者: 01.12.2013 08:21

2

63 作者的声誉

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

我想说的是,我已经在互联网上进行了广泛搜索,试图找到理想的解决方案。我什至开发了自己的边缘检测算法。
我评估了多个模型的速度和准确性。我的图像具有白色背景,在进行相位调整时效果非常好。就像redcalx所说的,我推荐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

希望这可以帮助!

作者: Tanner Clark 发布者: 02.05.2019 08:04
32x32