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

作者 | Thomas Berg

译者 | 王强

策划 | 蔡芳芳

当你寻找一张几年前某次野餐拍摄的照片时，你肯定不记得相机设置的文件名是“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」。在倒排索引中，对于每个类别，我们存储该类别的一个具有正分数的图像发布列表。

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

因此，当用户搜索“野餐”时：

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

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

对于每个搜索结果，从前向索引中提取类别空间向量 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