【AICon】探索RAG 技术在实际应用中遇到的挑战及应对策略!AICon精华内容已上线73%>>> 了解详情
写点什么

如何高效实现图片搜索?Dropbox 的核心方法和架构优化实践

Thomas Berg

  • 2021-06-30
  • 本文字数:4579 字

    阅读完需:约 15 分钟

如何高效实现图片搜索?Dropbox的核心方法和架构优化实践

照片是 Dropbox 中最常见的文件类型之一,但是按文件名搜索它们的效率甚至低于基于文本的文件搜索效率。当你寻找一张几年前某次野餐拍摄的照片时,你肯定不记得相机设置的文件名是“2017-07-0412.37.54.jpg”。

 

相比之下,你会查看每张照片或它们的缩略图,并尝试找出与搜索内容相匹配的对象或内容——不管你是要从库中找出一张照片,还是要从公司存档里找出一张合适的照片为新的促销活动当素材,流程都是差不多的。如果 Dropbox 可以代替你来查阅所有这些图像,并找出与你指定的几个描述性词汇最匹配的图像,这岂不是非常方便?这基本就是我们的图像搜索所要做的事情。

 

图像内容“野餐”的搜索结果

 

在这篇文章中,我们将基于机器学习中的技术描述图像内容搜索方法背后的核心思想,然后讨论如何在 Dropbox 现有的搜索基础架构上构建高效的实现。

我们的方法


下面是解决图像搜索问题的一种简单方法:找到一个关联函数,该函数需要一个(文本)查询 q 和一个图像 j,然后返回一个关联分数 s,以表明该图像与查询的匹配程度。


s=f(q, j)


有了这个函数以后,当用户进行搜索时,我们将在所有图像上运行这个搜索,然后返回得分高于一个阈值的图像(按得分排序)。我们使用机器学习领域中的两个关键成果来构建这个函数:准确的图像分类和词向量。

图像分类


图像分类器读取图像并输出一个描述其内容的类别打分列表。较高的分数表示图像属于该类别的可能性较高。

 

类别可以是:

 

  • 图像中的特定对象,例如树或人

  • 整体场景描述,例如户外活动或婚礼

  • 图像本身的特征,例如黑白或特写

 

在过去的十年中,使用卷积神经网络分类图像的方法取得了巨大进展,这一趋势始于 Krizhevsky 等人在 2012 年 ImageNet 挑战赛中取得的突破性成果。此后,随着模型架构的改进,以及更好的训练方法、大型数据集(如 OpenImages 或 ImageNet)和像 TensorFlow/PyTorch 这样易用的库的出现,研究人员已经构建了可以识别数千个类别的图像分类器。

 

看看今天的图像分类效果如何:

图像分类器对一张典型的未分类照片的输出结果

 

图像分类使我们能够自动了解图像中的内容,但是仅凭这一点还不足以实现搜索。当然,如果用户搜索的是“海滩(beach)”,我们可以返回该类别得分最高的图像;但如果他们搜索的是“海岸(shore)”该怎么办?如果他们搜索的不是“苹果(apple)”,而是“水果(fruit)”或“澳洲青苹果(granny smith)”该怎么办?

 

我们可以整理出一个大型的同义词和近义词字典以及单词之间的层次关系,但这种方法很快就会变得笨重难用,尤其是在我们还要支持多种语言的情况下。

词向量


因此我们要重构问题。我们可以将图像分类器的输出解释为每个类别得分的一个向量 j「c」(本文中用「」表示下标,用【】表示上标)。此向量将图像的内容表示为 C 维类别空间中的一个点,其中 C 是类别的数量(数千个)。如果我们可以在该空间中提取查询的一个有意义的表示形式,就可以解析图像向量与查询向量的接近程度,进而衡量图像与查询的匹配程度。

 

幸运的是,提取文本的向量表示是自然语言处理中的研究重点。Mikolov 等人在 2013 年的 word2vec 论文中介绍了该领域的一种最知名的方法。Word2vec 为字典中的每个单词分配一个向量,这样含义相似的单词将具有彼此接近的向量。这些向量位于 d 维词向量空间中,其中 d 一般有几百之多。

 

我们可以简单地查询 word2vec 向量来获得搜索查询的向量表示。该向量不在图像分类器向量的类别空间中,但是我们可以参考图像类别的名称将其转换为类别空间,如下所示:

 

  1. 对于查询词 q,获取归一化为一个单位向量的 d 维词向量 q「w」。我们将在词空间中对向量使用一个 w 下标,对类别空间中的向量使用 c 下标。

  2. 对于每个类别,获取类别名称 c【i】「w」的归一化词向量。然后定义 m̂【i】=q「w」·c【i】「w」,即查询向量和第 i 个类别向量之间的余弦相似度。介于-1 和 1 之间的分数表示查询词与类别名称的匹配程度。我们将负值裁剪为零,从而使 m【i】=max(0, m̂【i】),这样就可以获得与图像分类器输出相同范围的分数。

  3. 之后我们可以计算 q「c」=[m【1】 m【2】... m【C】],这是 C 维类别空间中的一个向量,表示查询与每个类别的匹配程度,就像每个图像的图像分类器矢量表示图像与每个类别的匹配程度一样。

 

步骤 3 只是一个向量矩阵乘法 q「c」=q「w」C,其中 C 是矩阵,其列为类别词向量 c【i】「w」。

 

一旦将查询映射到类别空间向量 q「c」,我们就可以获取每个图像与类别空间向量的余弦相似度,以获取图像的最终相关性分数 s=q「c」j「c」。

 

这是我们的相关性函数,我们根据这个分数对图像排名,以显示查询结果。此函数应用在一组图像上也可以表示为一个向量矩阵乘法 s=q「c」J,其中 J 的每一列是一张图像的分类器输出向量 j「c」,s 是所有图像的相关性得分向量。

举个例子


我们来看一个只有几个维度的示例,其中词向量只有三个维度,而分类器只有四个类别:苹果、沙滩、毯子和狗。

 

假设用户搜索的是“海岸”。我们查询词向量,获得[0.35 -0.62 0.70],然后乘以类别词向量矩阵,以将查询投影到类别空间中。

 

由于“海岸”的词向量接近“海滩”的词向量,因此这个投影在海滩类别中有很大的值。

将查询词向量投影到类别空间中

建模细节


我们的图像分类器是在 OpenImages 数据集上训练的一个 EfficientNet 网络。它生成约 8500 个类别的分数。我们发现,这种架构和数据集以合理的成本提供了良好的准确度,因为我们要为 Dropbox 如此大规模的客户群提供服务,所以这非常重要。

 

我们使用 TensorFlow 训练和运行模型。我们使用预训练的 ConceptNet Numberbatch 词向量。它们提供了良好的结果,并且对我们而言很重要的是它们支持多种语言,对于具有相似含义的不同语种的单词返回相似的向量。这样我们就可以很容易地支持多种语言的图像内容搜索:英语中的 dog 和法语中的 chien 的词向量相似,因此我们不用做显式翻译就可以支持两种语言的搜索。

 

对于多词搜索,我们将查询解析为各个词的一个 AND。我们还会维护一个多词术语列表,例如“沙滩球”就可以视为单个词。当查询包含这些术语之一时,我们将做一个备用解析并运行两个已解析查询的 OR,于是“沙滩球”这个查询将变为(沙滩 AND 球)OR(沙滩)。这将同时匹配沙滩上的“大球”“彩色球”“充气球”和“网球”等结果。

生产架构


每当用户进行搜索时,获取完整的最新 J 矩阵都是不切实际的。用户可能可以访问数十万甚至数百万个图像,并且我们的分类器输出具有数千个维度,因此该矩阵可能有数十亿个条目,且每当用户添加、删除或修改图像时都需要更新。对于数亿规模的用户群而言,我们(还)无法负担得起背后的成本。

 

因此,我们不是为每个查询实例化 J,而是使用上述方法的一种近似方法,可以在 Dropbox 的 Nautilus 搜索引擎上有效地实现。

 

从概念上讲,Nautilus 包括将每个文件映射到某些元数据(例如文件名)和文件全文的一个前向索引,以及将每个单词映射到包含该单词的所有文件的一个发布列表的反向索引。对于基于文本的搜索,一些配方文件的索引内容可能是这样的:


 

在基于文本的搜索中搜索索引内容

 

如果用户搜索“白葡萄酒(white wine)”,我们将在倒排索引中查找两个词,发现 doc_1 和 doc_2 都包含这两个词,因此我们应将它们包含在搜索结果中。Doc_3 只有一个词,因此我们应该将其省略或放在结果列表的最后。

 

找到所有可能要返回的文档后,我们在前向索引中查找它们,并使用那里的信息对它们进行排名和过滤。在本例中,我们可能让 doc_1 的排名高于 doc_2,因为这两个词彼此相邻。

将文本搜索方法用于图像搜索


我们可以使用相同的系统来实现我们的图像搜索算法。在前向索引中,我们可以存储每张图像的类别空间向量 j「c」。在倒排索引中,对于每个类别,我们存储该类别的一个具有正分数的图像发布列表。


在图像内容搜索中搜索索引内容

 

因此,当用户搜索“野餐”时:

 

  1. 查找“野餐”的词向量 q「w」,然后乘以类别空间投影矩阵 C 以获得 q「c」,如上所述。C 是对所有用户都相同的固定矩阵,因此我们可以将其保存在内存中。

  2. 对于每个在 q「c」中具有非零条目的类别,从倒排索引中获取发布列表。这些列表的并集是匹配图像的搜索结果集,但仍需要对这些结果进行排名。

  3. 对于每个搜索结果,从前向索引中提取类别空间向量 j「c」并乘以 q「c」以获得相关性分数 s。返回分数高于某个阈值的结果,按分数排序。

优化可伸缩性


考虑到存储空间和查询处理时间,这种方法仍然是很昂贵的。如果我们有 10,000 个类别,那么对于每个图像,我们必须在正向索引中存储 10,000 个分类器分数;如果使用四字节浮点值,则需要 40KB 的成本。而且由于分类器分数很少为零,因此这 10,000 个发布列表中的大多数都需要添加一个典型图像。如果我们使用四字节整数作为图像 ID,这又需要 40KB,也就是说每张图像的索引成本为 80KB。对于许多图像来说,索引存储空间甚至会大于图像文件!

 

至于查询处理时间(对于执行搜索的用户来说,这就是等待时间),我们可以预期查询类别匹配分数 m̂【i】大约有一半为正数,因此我们将从倒排索引中读取大约 5,000 个发布列表。与文本查询相比这个结果非常差,毕竟文本查询通常只读取大约十个发布列表。

 

幸运的是,我们可以丢弃许多接近零的值以获得更有效的近似值。上面给出的每个图像的相关性分数为 s=q「c」j「c」,其中 q「c」包含查询与每大约 10,000 个类别之间的匹配分数,而 j「c」保含来自分类器的大约 10,000 个类别分数。这两个向量几乎都由零值组成,这些值对 s 的贡献很小。

 

近似地,我们将 q「c」和 j「c」的绝大多数项都设置为零。通过实验,我们发现保留 q「c」的前 10 个条目和 j「c」的前 50 个条目就足以防止质量下降了。这样就能在存储和处理方面节省可观成本:

 

  • 在前向索引中,相比 10,000 维的密集向量,我们只存储具有 50 个非零条目的稀疏向量——也就是每个图像的前 50 个类别得分。在稀疏表示中,我们存储每个非零条目的位置和值;50 个 2 字节整数位置和 50 个 4 字节浮点值需要大约 300 个字节。

  • 在倒排索引中,每张图像被添加到 50 个发布列表中,而不是 10,000 个中,这大约需要 200 个字节。因此,每个图像的总索引存储为 500 字节,而不是 80KB。

  • 在查询时,q「c」有 10 个非零条目,因此我们只需要扫描 10 个发布列表——与文本查询所做的工作量大致相同。这为我们提供了一个较小的结果集,我们也可以更快地对其评分。

 

通过这些优化,索引和存储成本降到了合理水平,并且查询延迟足以低到文本搜索延迟的水平。因此,当用户启动搜索时,我们可以并行运行文本搜索和图像搜索,并一起显示全部结果,而无需让用户等待比单独进行文本搜索更长的时间。

当前部署


现在,我们为所有的专业(Professional)和商业(Business)级别用户都启用了图像内容搜索。我们将图像内容搜索(用于一般图像)、基于 OCR 的对文档图像的搜索以及对文本文档的全文本搜索结合在一起,这样这些用户的大部分文件都可以通过基于内容的搜索获取。

视频搜索?


当然,我们正在努力让你可以搜索所有 Dropbox 内容。图像搜索是朝着这一目标迈出的一大步。最终,我们希望视频内容也可以纳入搜索范围。在视频中寻找某帧或为整个剪辑编制索引以进行搜索的技术(可能是采用静止图像技术来实现)仍处于研究阶段,但回过头来想想,仅仅几年前,“从我的所有野餐照片中找到有我的狗的那些”这样的需求是只在好莱坞电影中才能实现的梦想。

 

我们的目标是:如果什么内容在你的 Dropbox 中,我们都将为你找到它!

 

原文链接:https://dropbox.tech/machine-learning/how-image-search-works-at-dropbox

公众号推荐:

2024 年 1 月,InfoQ 研究中心重磅发布《大语言模型综合能力测评报告 2024》,揭示了 10 个大模型在语义理解、文学创作、知识问答等领域的卓越表现。ChatGPT-4、文心一言等领先模型在编程、逻辑推理等方面展现出惊人的进步,预示着大模型将在 2024 年迎来更广泛的应用和创新。关注公众号「AI 前线」,回复「大模型报告」免费获取电子版研究报告。

AI 前线公众号
2021-06-30 18:382481

评论

发布
暂无评论
发现更多内容

openGauss社区成立ReleaseManagement SIG

openGauss

安全app之PHP代码审计

网络安全学海

网络安全 信息安全 渗透测试 WEB安全 代码审计

移动域全链路可观测架构和关键技术

阿里巴巴终端技术

架构 App 移动端 体验优化

向工程腐化开炮 | Java代码治理

阿里巴巴终端技术

Java android JVM 代码治理

企业内PAAS建设的经验与教训

Crazy

中间件 PaaS 经验 云原生应用

基于WEB快速开发平台的轻量ERP

雯雯写代码

ERP 快速开发平台

云计算及国内主流云厂商概述

穿过生命散发芬芳

3月月更

什么是以特性为核心的持续交付|阿里巴巴DevOps实践指南

阿里云云效

云计算 阿里云 研发效能 研发 DevOps实践指南

如何从头到脚彻底解决一个MySQL Bug?华为云数据库高级专家带你看

华为云数据库小助手

bug GaussDB 华为云数据库 GaussDB(for MySQL)

APICloud平台使用融云模块实现音视频通话实践经验总结分享

YonBuilder低代码开发平台

前端开发 APP开发 APICloud 融云 跨端开发

租房小程序

源字节1号

前端开发 后端开发 租房小程序

hexo+github搭建个人博客前期部署工作

静Yu

Hexo

被冰封的 Bug:Fishhook Crash 修复纪实

声网

Dev for Dev fishhook

聊聊 kerberos 的 kinit 命令和 ccache 机制

明哥的IT随笔

数据安全 kerberos

基于微信小程序的大学社团平台的可研方案

CC同学

企业知识管理的目标是什么?

小炮

实用机器学习笔记二十五:超参数优化

打工人!

学习笔记 超参数调优 机器学习算法 3月月更

租房小程序

源字节1号

前端开发 后端开发 租房小程序

关于知识库:你需要知道的一切

小炮

手把手教程|构建无服务器通用文本识别功能

亚马逊云科技 (Amazon Web Services)

架构

打造优质的车联网体验,仍需注意数据安全保护

FinClip

Gitlab-ci 替代 webhook 触发Jenkins job

网易云信

gitlab

喜讯!openGauss社区入选2021年 “科创中国”榜单

openGauss

OceanBase 社区版 运维管控平台 OCP 功能解读

OceanBase 数据库

OCP oceanbase OceanBase 开源 OceanBase 社区版

VuePress 博客之 SEO 优化(一) sitemap 与搜索引擎收录

冴羽

Vue vuepress SEO 博客搭建 sitemap

杜绝不良信息侵害未成年,皮皮APP发起语音社交行业自律书

联营汇聚

如何从头到脚彻底解决一个MySQL Bug

华为云开发者联盟

MySQL 数据库 华为云 bug GaussDB(for MySQL)

WebRTC 简单入门

ZEGO即构

WebRTC 动手实践 音视频开发 即构科技

如何使用OKR管理团队?

优秀

盲盒风潮过后,中国收藏玩具市场该何去何从?

易观分析

盲盒 潮玩

基于深度学习的时间序列预测

云智慧AIOps社区

如何高效实现图片搜索?Dropbox的核心方法和架构优化实践_语言 & 开发_InfoQ精选文章