使用 Spark, LSH 和 TensorFlow 检测图片相似性

本文为 AI 研习社编译的技术博客,原标题 Detecting image similarity using Spark, LSH and TensorFlow,作者为 Andrey Gusev(Pinterest 工程师,内容质量分析师)。 翻译 | 沈波 张天航 校对 | 余杭 整理 | 凡江

作为一个视觉数据处理平台,拥有从海量图片中学习并理解其内容的能力是非常重要的。为了检测几近重复的相似图片,我们使用了一套基于 Spark 和 TensorFlow 的数据流处理系统——NearDup。这套系统的核心由一个使用 Spark 实现的批量化 LSH(locality-sensitive hashing,局部敏感哈希)搜索器和一个基于 TensorFlow 的分类器构成。这个数据流处理系统每天能够比较上亿个分析对象,并渐进式地完成各个图像类别的信息更新。在本文中,我们将讲解如何使用这项技术更好地理解海量图片内容,从而使得我们产品前端界面的推荐内容和搜索结果具有更高的信息准确性、更大的数据密度。

简介

我们将我们图片库中的所有图片划分为不同的图片类,每一类都由几近相同(以人类观察员的判断为标准)的图片组成。这种分类标准有一定的主观性,为了给你一个感性认识,下图展示了一些按照 NearDup 阈值进行图片分类的例子。注意,这些相似图片不一定来自同一图像源(参见右下图),也不一定有相同的背景(参见左下图)。同时,图像中可能包含一定的几何扭曲(参见左上图),或者旋转、剪切和翻转变化(见中心图和右上图)。

为图片库中的所有图片进行分类与划分的过程在数学上无法进行严格定义与求解,这是因为在 NearDup 系统中,图片之间的关系不具有传递性和相等性。为了说明这一点,我们可以想象将一张「猫」的图片通过 1000 步慢慢地形变为一张「狗」的图片的过程。容易推断,每一步微小形变前后的两张图片的相似度都将落入 NearDup 的阈值,从而将它们判断为「相似」图片。然而,究竟该将这一串前后相似的图片序列划分为哪几类?猫类,狗类,还是猫-狗类?为了解决这一问题,我们将问题模型转化为图:图的节点代表图片,边代表相应图片间的相似度。随后我们结合传递闭包法( transitive closure )和贪婪 k-cut 算法来最小化图的 k-cut 划分,从而近似求解整个图片库的最优划分。

使用批量化 LSH 进行数据预处理

嵌入和 LSH 对象

为了理解图片内容,我们将图片转换到一个嵌入向量空间(embedded vector space)中。这些图嵌入向量是图片的一种高维向量表示,能够抓取图片的视觉和语义相似性。它们一般通过神经网络架构如 VGG16 或 Inception 等处理生成。为了在 NearDup 系统中处理图片关系并对图片库进行分类,我们每天要比较几千万张新图片,并将它们分类到上亿个图片类别中。如果没有优化措施,如此大规模的近邻搜索(nearest neighbor search)问题的时间复杂度为平方(quadratic)复杂度,相应的计算时间将正比于甚至超过 10 个 quadrillion 秒(1 后面 16 个 0!)。为此,我们通过将图嵌入向量进一步缩减为 LSH 对象的方法,显著缩小了问题规模,降低了处理难度。

LSH 是一种先进的数据降维技术,降维前后数据点之间的距离关系保持不变。原向量空间首先通过随机投影法(random projection)和位抽样 LSH(bit sampling LSH)法进行一定的降维。随后,我们继续将所得到的向量位分组为多个 LSH 对象,分组过程有效地权衡了检测准确率和计算时间这一矛盾体。分组越精细,进行最近邻搜索的计算复杂度将越高,但检测准确率也将越高。这里,我们使用 LSH 对象之间的 Jaccard 重合度来近似表示原向量空间中相应向量间的余弦相似度。

批量 LSH 搜索

当所有图片都用一组 LSH 对象表示之后,我们继续为它们建立反向索引,并实现对所有图片的批量查询与搜索。从顶层看,我们通过函数式转换法(functional transformation)、压缩式反向索引与连接法(compressed inverted indexes and joins)等方法的结合,来实现对所有图片的一次性批量查询与比较。这个数据流处理过程是用 Spark 实现的,并需要借助一系列的优化措施来进一步保证这些海量数据能够转化到尽量简单有效地的LSH 对象空间中进行处理。我们所使用到的主要优化措施包括:

  • 字典编码( Dictionary encoding ) 使得所有数据都用具有最短宽度的数值进行表示
  • 可变字节编码( Variable byte encoding ) 被用于所有的反向索引
  • 索引切分( Index partitioning ) 提高了反向索引的平衡性
  • 基于代价的优化器( Cost-based optimizer ) 能够检测嵌入向量空间的密度,并计算最优的运行时参数
  • 原始数据堆排( Primitive data packing ) 进一步提高了内存使用率
  • Jaccard 重合度计数( Jaccard overlap counting ) 基于低层次、高性能的数据收集实现
  • 去堆化( Off heaping ) 减少了垃圾回收(GC)过载

使用迁移学习的候选选择

批量化LSH是产生高查全率(召回率)同时又能最小化计算成本的一个很效果的方法。但是,它通常不会对候选项产生最优的查准率(准确率)和排序。我们通过使用一个有监督的分类器去挑选那些NearDups 认为足够相似的候选项。这个分类器是一个迁移学习在视觉嵌入上的例子。它使用了Tensorflow 前馈网络和一个 Adam 优化器 。我们已经在超过包含10亿不同对图像的样本集中训练了分类器。训练集由决策树分类器在SURF 视觉特征上的输出得到,并进行了几何验证,然后用于NearDup 系统的先前迭代。为了提高学习和每一对图像的收敛性,将 hamming 码字节进行异或运算后输入到输入层。该分类器被调整到很高的准确率并且在人类标记的样本上达到了 99% 以上准确率。

SparkContext 也可以对训练过的网络进行推断。使用 mapPartitions 和分组范式,我们可以使用预定义好尺寸的大批数据去有效地向量化和减少开销。在一个拥有1000万个参数的网络中,我们在一个r3.8xlarge 的机器集群上实现了平均2ms进行一个预测的速率。

结论

NearDup 检测需要进行计算代价很高的两两比较。通过在Spark 中使用批处理LSH实现,我们通过跳过不太相似的图像对大大降低了计算的复杂度。Spark-based 的实现结合了高效的工作负载分配和低层次的优化,以最小化内存和CPU占用。随后的调优步骤使用了一个有监督的前馈网络来选择和排序高于NearDup 相似性阈值的图相对。Spark 和Tensorflow 的推断结合使用了分布式计算和每个内核矢量化的最佳特性,实现了高吞吐量和低延迟的预测。然后,将这两个步骤的结果用于集群图像,每天帮助提供数百亿的搜索结果和在Pinterest 上的推荐。

欲了解更多关于这个问题的信息,请看我在 Spark+AI Summit 2018 的演讲。https://vimeo.com/274629687

致谢:感谢以下团队成员对本项目的所有贡献:Jiajing Xu, Vitaliy Kulikov, Jooseong Kim, Peter John Daoud, Andrew Zhai, Matthew Fang, Kevin Lau, Jacob Hanger, Zhuoyuan Li and Chao Wang

原文链接:

https://medium.com/@Pinterest_Engineering/detecting-image-similarity-using-spark-lsh-and-tensorflow-618636afc939

原文发布于微信公众号 - AI研习社(okweiwu)

原文发表时间:2018-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏量子位

用Keras+TensorFlow,实现ImageNet数据集日常对象的识别

王新民 编译自 Deep Learning Sandbox博客 量子位 出品 | 公众号 QbitAI ? 在计算机视觉领域里,有3个最受欢迎且影响非常大的学术...

68180
来自专栏大数据文摘

机器学习算法一览(附python和R代码)

258140
来自专栏一棹烟波

利用光场进行深度图估计(Depth Estimation)算法之一——聚焦算法

前面几篇博客主要说了光场相机,光场相机由于能够记录相机内部整个光场,可以实现重聚焦(模糊线索)和不同视角的变换(视差线索),同时也可以利用这个特性进行深度估计(...

35360
来自专栏机器学习原理

我的机器学习概率论篇排列 组合古典概率联合概率条件概率全概率公式贝叶斯公式独立事件随机变量离散型随机变量连续型随机变量期望和方差三个基本定理参数估计

前言: 概率论的理解有些抽象,掌握概率论的方法,用实际样本去无限接近真实,熟练掌握并且使用一些最基本的概念是前提,比如,均值,方差 排列 组合 计算各种...

69860
来自专栏机器之心

深度 | 从数据结构到Python实现:如何使用深度学习分析医学影像

选自Medium 作者:Taposh Dutta-Roy 机器之心编译 运用深度学习技术进行图像和视频分析,并将它们用于自动驾驶汽车、无人机等多种应用场景中已成...

80390
来自专栏人工智能LeadAI

时间序列异常检测 EGADS Surus iForest

时间序列异常检测 (原文链接:http://wurui.cc/tech/time-series-anomaly-detection/) 本文总结了我在时间序列异...

1.6K40
来自专栏AI研习社

小白学CNN以及Keras的速成

为何要用Keras 如今在深度学习大火的时候,第三方工具也层出不穷,比较出名的有Tensorflow,Caffe,Theano,MXNet,在如此多的第三方...

31940
来自专栏机器之心

专访 | 基于LSTM与TensorFlow Lite,kika输入法是如何造就的

机器之心原创 作者:思源 近日,机器之心采访了 kika 的高级技术总监黄康,他向我们讲述了 kika 开发输入法 AI 引擎(项目代号:Alps)所采用的深度...

34850
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

《Single Image Haze Removal Using Dark Channel Prior》一文中图像去雾算法的原理、实现、效果(速度可实时)

      最新的效果见 :http://video.sina.com.cn/v/b/124538950-1254492273.html         可处理...

891100
来自专栏IT派

资源 | Chinese Word Vectors:目前最全的中文预训练词向量集合

项目链接:https://github.com/Embedding/Chinese-Word-Vectors

15460

扫码关注云+社区

领取腾讯云代金券