在Ok188bet金宝搏官网Cupid,我们有时会遇到用户和机器人是重新使用之前我们已经看到了同样的照片。虽然有时我们可以简单地检查,如果照片已被看到(和禁止)之前,我们经常会碰到一个地方被取缔的照片已略有操纵的情况下 - 这样一个确切的比较将无法工作。即使图像中轻微的转变将彻底毁了精确匹配。这是我们几年前发现的问题,我们不得不使用一个简单的知觉哈希函数的部分解决方案。然而,多年来,我们已经熟悉了现行制度的缺陷。需要一个更强大的方式放大,一旦我们取得的照片为新用户的要求。

有几种方法可以解决这个问题,但是最常用的方法是使用一个感性的哈希值。对于外行,在一般的散列是(根据全能维基百科)一种“可用于将任意大小的数据映射到固定大小的数据的函数”,例如将一幅图像转换成代表该图像的位串。

传统上,这意味着一种加密哈希(例如MD5、SHA-256),在这种哈希中,输入的最轻微变化将导致输出的剧烈变化。然而,出于我们的目的,我们想要的是几乎相反的——输入的微小变化(比如,稍微移动或旋转图像)应该在输出中产生很少的变化或没有变化。这就是感知图像哈希的想法。

最终,感知图像散列寻求保持很大程度不变在它的输出到输入的轻微变化,同时产生一个小的(即,可管理的)输出。有了这些功能,我们就可以检查上传到网站上的照片是否与为了避免精确的图像检查而稍微改变的照片相同。

这篇文章的其余部分详细介绍了适合这种格式的四种不同的感知哈希算法,在哪些转换下它们不能保持不变,以及总体上哪一种表现更好。虽然我们已经有了一个感知哈希系统,但是是时候进行升级了!

评价

在这篇博客文章的其余部分,我们将讨论感知图像哈希函数,它采用任意图像并生成固定大小的位字符串。这允许我们使用汉明距离在我们计算的位字符串之间。理论上,感知哈希可以产生图像的密集表示(即浮点向量),但这使得比较更加复杂。

还有,我们在这里探讨两两件事:

  1. 图像变换(或攻击),即攻击者会运用什么转换为图像,以试图愚弄检测系统
  2. 感知哈希函数精度

这个评估的目标是确定感知散列在完全不同的图像对和仅仅是图像及其转换版本的图像对之间的区别有多好。

评价概述

我们将其设置为在两种情况下测量距离:

  1. 正的情况——图像和这些图像的变换版本之间的距离
  2. 负的情况——不同的原始图像之间的距离

我们在网站上使用了大约10k的图像样本,以平衡在合理的时间和统计显著性的情况下完成这项工作,从这个样本中,我们对这些图像分别进行了10次试验。对于负的情况,我们实际上采样了1k个图像对(并得到它们的哈希距离),而对于正的情况,我们只计算了大量的变换及其距离,然后采样到1k个例子。这让我们了解到每个度量的可靠性——尽管通常我们没有观察到太多显著的变化。

在这里增加一个重要的事情是,这些图像被刻意过滤,以确保他们没有从垃圾邮件发送者,以防止重新使用垃圾邮件的照片被视为不同的图像对来了。此外,我们采取删除任何非唯一照片的额外步骤(通过比较它们的确切哈希值)。

转换

我们确定了五种典型的图像转换,这是我们勤劳、不知疲倦的审核团队在处理垃圾邮件发送者时最常见的。

  • 旋转(绕原点)
  • 作物
  • 伽马校正
  • 添加边框(或反向作物)
  • 椒盐噪音
转换 温和的 媒介 极端的 单位
回转 1 - 5 6-15 30
作物 95 - 99 85 - 94 60 - 84 保存图像百分比
伽马校正 1±0.01 - -0.25 1±0.26 - -0.5 1±0.51-1 γ
边境 1 - 5 6-15 16-50 px
标准普尔噪声 0.5 - -2.5 2.6 - 5 -10 - 5.1 %的图像

图像转换

每一个转换都有一个参数来控制操作的强度——例如旋转多少度。为了便于分析,我们将这些参数分别指定为三个桶:温和的、中等的和极端的。每当应用转换时,就会指定bucket,并且从该bucket中统一采样参数(参见上表中的那些bucket)。在大多数这些分析中,每个转换/桶要分别计算三次,因为数据越多越好。

但是等一下,还有mirr…ore!对于每个转换应用程序,我们翻转一个隐喻性的硬币,并在其垂直轴上反射转换后的图像。我们跳过横轴,因为它在野外并不常见——人们可能会认为颠倒的图片是一个非常明显的垃圾邮件。

感知哈希函数

在这篇文章中,我们不会过多地讨论每个感知哈希函数的细节,因为它们在提供的参考资料中已经很详细了。为了简单起见,我们只计算四个常见的感知哈希函数:

这里使用的实现都是由Johannes Buchner的优秀而方便的Python提供的ImageHash图书馆

规范化的汉明距离

由于每个哈希函数都将图像压缩为位字符串,所以我们使用汉明距离来比较它们。这是一种很奇特的方式来表示我们只需要测量每个哈希值之间有多少位不同。

为了比较产生不同大小的位串的散列函数,我们也反对正常化产生的位串的长度(因为我们没有比较散列函数,它不会作出了很大的意义反正间位串)。因此,例如,当你看的更远直方图向下行,请注意该距离(即x轴)是从零到一。实际上,这是是两个位串的那些位串的长度之间的不同比特的比率。

指标

我们如何度量一个感知哈希函数的质量?我们评估这些函数的主要范例是通过观察特定情况下正情况和负情况下的距离分布。本质上,我们想要的是每一种情况下距离的分布(或直方图)是相当独立的。有几种方法可以实现这一点,但我们只考虑三个指标:

  • EMD距离(所有从事深度学习的人开始神秘地称它为瓦瑟斯坦距离)。我们想让它变大。
  • 两个直方图的相交过合并(IoU)。我们希望它非常小。
  • 最大F1-score在一个最佳的距离阈值。我们想让它接近于1。

EMD可能是这里最一致的测量方法,因为,假设你有两个独立的直方图,并且想要将它们与两个独立但距离更远的直方图进行比较。在最优F1评分和IoU评分下,两种情况都是最优的,但EMD更倾向于后者。

我们引入f1得分来给我们一个阈值,稍后将对此进行更多讨论。考虑这个问题最简单的方法是沿着x轴滑动阈值,然后找到最优地分离直方图的方法。

直方图IoU作为额外的比较提供,基本上直接测量每个直方图与另一个直方图有多少重叠。

结果

一般比较

比方说,我们设置它,使我们正在评估所有的参数桶,所有的哈希,所有的转换。在这种情况下 - 如果你正在寻找一个快速的答案在这里 - 最好的选择根据指标似乎要么是平均哈希,要么是小波哈希,每个执行差不多。

哈希 EMD距离 直方图欠条 最优F1-Score @最优阈值
average_hash 12.54 0.20 0.79 0.41
diff_hash 8.79 0.25 0.70 0.46
dct_hash 8.03 0.30 0.69 0.52
wavelet_hash 12.23 0.21 0.77 0.39

但是,这可能是骗人的——每个哈希函数求值的直方图说明了这一点(重叠越少越好)。

小波散列所有 平均散列 DIFF哈希所有 Dct散列所有

作为一个基准,看看哈希分布,当你使用密码散列(这是非常有帮助寻找调试这样的评价时的)。

确切的哈希所有

在本例中,我们可以看到加密哈希产生了以0.5为中心的完全重叠的正态分布,这是意料之中的。我建议从这个角度来解释其它的直方图——负类应该像这样的分布,正的阶级理想上会完全向左移动。

所以乍一看,你可以看到为什么指标有利于小波和平均哈希 - 这是很明显的,无论是感性与差异散列有消极和积极的距离更显著的重叠。然而,我们必须考虑实际应用 - 如果我们要找到最接近的哈希给定图片的哈希值,我们想从误报尽可能地为绝缘。这意味着,在小波和平均哈希看到负距离的传播可能的情况下产生更多的误报,我们正试图找到最接近的匹配,以给定的图像!

所以要带走一些主要发现从这个评价一切开启(即最困难的情况下),我们看到了积极的情况下:

  • dct_hashdiff_hash有双峰正距离分布,显然被我们所做的事情愚弄了,因为其中一个模态接近期望随机距离。
  • wavelet_hashaverage_hash看起来像是长尾距离分布,随着距离的增加质量更少,这意味着更少的变换“迷惑”它们。

对于消极的情况:

  • dct_hashdiff_hash两者都在0.5标记附近有紧密分布,其行为类似于加密哈希情况。
  • wavelet_hashaverage_hash它们的分布虽然都是正态分布,并且以预期随机距离为中心,但在两个方向上都扩散得相当远。对于为什么会发生这样的事情,我没有一个很好的答案,但我最好的猜测是,通过捕捉它们所做的信息,它们实际上在检查更高层次的图像相似度(例如相似的调色板)方面做得更好。这可能值得进一步研究。

基于以上,我认为进行分类是公平的dct_hashdiff_hash作为(相对)高精度,低召回感知散列和wavelet_hashaverage_hash作为高召回,低精度哈希。

某些哈希在哪些变换上失败?

假设我们非常关心负情况距离的扩散,想知道我们需要做什么牺牲dct_hashdiff_hash代替。

不变性,镜像

首先,我们可能需要接受的是镜像操作,通过比较变换后的图像被镜像为正时和未被镜像时的中值距离可以看出。

哈希 镜像关闭 反映在
average_hash 0.04 0.37
diff_hash 0.09 0.48
dct_hash 0.09 0.50
wavelet_hash 0.04 0.38

看起来,虽然每个散列在转换后的映像未镜像时都有显著的改善,diff_hashdct_hash似乎完全被他们接近期望随机距离的中值距离愚弄了。

因此,与这一点,事实上,你真的只能镜上的图像一次,我们可以接受一个缺乏镜像。如果没有镜像,我们得到的直方图,它可以查找这两个低召回哈希更加合理。

ih phash nomirror IH dhash nomirror

然而,随着镜像的移除,下表显示了其他散列的指标也得到了显著的提高——当然,负情况分布的问题仍然存在。

哈希 EMD距离 直方图欠条 最优F1-Score @最优阈值
average_hash 19.38 0.06 0.93 0.31
diff_hash 16.60 0.08 0.91 0.42
dct_hash 15.92 0.10 0.89 0.43
wavelet_hash 19.28 0.07 0.93 0.32

打倒香料水平

这里要考虑的另一件事是,这些计算都在所有转换参数桶上运行。如果我们假设所有攻击者都不希望将图像旋转超过5度或裁剪到图像的95%以下,该怎么办?对镜子过敏吗?

哈希 EMD距离 直方图欠条 最优F1-Score @最优阈值
average_hash 22.49 0.00 1.00 0.22
diff_hash 20.79 0.00 1.00 0.36
dct_hash 20.53 0.00 1.00 0.40
wavelet_hash 22.39 0.01 0.99 0.22

看看上面那些度量!看起来他们中的一些人已经成功了完整的可分性!

在这种情况下,我们可以清楚地看到,diff_hashdct_hash在他们的指标上得到显著的提升。因为(当然)对于负的情况,这不会改变距离的分布,如果我们只关心温和的转换情况,那么我们可能有一个像样的阈值来工作,这不会产生太多的假阳性!

为了简便起见,我们将重点关注diff_hash为讨论这个,因为我发现,dct_hash类似的行为。下面是轻微情况下的距离直方图比较。

这是一个温和的名字

阈值

我们可以通过优化f1值来使用给定的距离阈值,从而为我们提供一个截止值(对于那些需要截止值的应用程序),这样距离低于该阈值的任何图像对都被认为是相同的,而高于该阈值的任何图像都是不同的图像。

如果我们看看轻微的情况,我们会注意到有一些哈希可以得到近乎完美的F-1分数。这显然只适用于温和的情况,但我们需要做出什么样的转换牺牲来使用这个阈值呢?都是变换吗?或者我们只是失去了一些更极端的变换的不变性而不是所有的?

我们来看看这个diff_hash:当我们把我们从只盯着温和变换参数获得的门槛,有什么积极的情况下,我们结束了治疗对象的不同图像对的转换其余的百分比是多少?

转换 极端的 媒介 温和的
边境 5.80% 0.08% 0.00%
作物 92.52% 31.31% 0.02%
γ 0.01% 0.01% 0.00%
旋转 96.68% 68.10% 1.73%
sp_noise 0.02% 0.02% 0.01%

很明显,当我们旋转超过15度的时候,它就完全崩溃了(例如下面的例子)——同样的道理也适用于裁剪到小于85%的图像。它在中等情况下也做得不好,旋转是从6到15度!

我们看了不同哈希的失败几率average_hashwavelet_hash但在同样的地方失败的几率要小一些——80%而不是96%。

下面是一个简单的例子来说明什么是30个旋转的样子,用爱丽丝的图片 - 我们的支持主管。

旋转的例子

爱丽丝是OkCupid像188bet金宝搏官网汤姆到MySpace。

多久这个反正走?

散列的名字 每幅图像的平均哈希时间(ms) STDDEV
average_hash 29.81 18.97
diff_hash 29.93 19.03
dct_hash 33.97 20.09
wavelet_hash 60.99 22.75

总体来说,最慢的是小波哈希,其余的哈希几乎以相同的时间进行计时。

简单说明一下——通常最慢的步骤之一就是将图像调整到大多数感知哈希使用的小哈希大小。这看起来奇怪,但它是有意义的——所有其他操作通常是在一个小(通过现代计算机标准)16 x16数组,因此,即使是那些时间复杂度高的转换可以没有时间,而即使是优化调整必须与一个大得多的图像。这也可以解释每个哈希所花费的时间差异,因为我们事先没有将图像大小调整到固定大小。

尽管如此,每个散列都是相当快的,所以它不需要太多的关注,特别是当它可以从任何类型的图像上传异步完成时。

其他的笔记

我们还研究了一些其他的东西,但这些东西并不值得在这里单独讨论,所以这里有一些简短的注释:

  • 增加位串长度(或散列大小)导致显著更坏的结果对大多数感知哈希的,可能是因为它只是捕捉太多细节。
  • 对于小波哈希,我尝试了一堆不同的图像尺度和小波策略,除了使用Daubechies小波而不是Haar,它们没有一个真的在度量上有任何显著的不同——它的性能明显地更差。

结论及未来工作

我们从中得到的主要结论是,并不是只有一个哈希算法可以处理我们需要的所有东西。为了得到一个可行的解决方案,我们可能必须明智地组合多个感知散列。然而,计算每一个哈希值都相当便宜(我认为还可以进一步优化),这意味着为每张图像计算多个哈希值可能是构建图像相似度引擎的可行基础。

例如,可以使用一个低精度哈希作为初始检查,然后使用一个高精度哈希来区分可能需要检查的情况和肯定是相同的映像。

对未来工作的几点思考:

  • 有很多更新的有趣的哈希值值得考虑。
  • 有相当多的更多的方式来改变图片,我们看到在野外(例如添加字幕,叠加在其他图像的透明度,压缩失真)其他应当进行评估。
  • 哈希数列之间的相似行为确实有点奇怪。可能有一些有意义的东西值得去研究。
  • 评价/设计一个门控结构如以上简要描述的
  • 我们可以调查什么特征的给定图像对导致低精度哈希不可靠/给他们一个低距离,并使用它来确定哪个算法的哈希距离可以信任的给定图像对。
  • 训练卷积网络嵌入图像的端到端方法,使正/负情况的距离很好地分离,这可能是一种很酷的新hypebeast前进方式。这样做还有一个好处,就是能够处理在训练时想到的任何转换。

188bet金宝搏官网OkCupid正在招聘点击这里了解更多