导读：百度富媒体检索比对系统是一套基于 Ann(approximate nearest neighbor)检索和内容特征比对技术，旨在提供针对图像、音频、视频等多媒体资源的相似检索系统。包括离线训练、建库，在线特征提取、检索。目前百度富媒体检索比对系统除了承接了百度 FEED 所有视频、图像的反作弊、下发去重以及关联推荐和黄反等业务，另外还支持了包括视频搜索、贴吧、文库在内的数十个业务方，支撑了千亿级数据规模。在数据规模、系统性能、召回率和准确度上都处于领先地位。
随着互联网和 AI 技术的发展，网络信息的主要传输媒介，已经从传统的网页文字发展到图片、视频、音频等资源，相对纯文字的网页，富媒体内容能传递更多的信息量，同时也带来更新的用户体验。随着富媒体内容急剧爆发, 理解这些实体内容，找到他们之间的相似关系，不仅能够对这些富媒体内容进行筛选和处理，还可以更好的被推荐和搜索引擎理解，更好的服务用户。
得益于神经网络的飞速发展，多媒体数据的检索问题通常可以转化为高维向量的相似性检索, 采用 CNN(Convolutional Neural Network）的各种特征来描述这些多媒体资源的语义信息，基于 CNN 特征向量，将 query 与库中所有数据进行相关性计算，检索出相关的结果集。以图像为例，我们首先会对存量图像，进行收录、筛选，计算它们的 CNN 特征，然后把这些 CNN 进行建库。当输入 query 图像，需要从历史库中检索出与之相似或相同的图像时，我们首先计算 query 图像的 CNN 特征，然后与历史库中的全量 CNN 特征进行计算（通常计算欧式或 cosin 距离），选取距离最近的 topk 个图像作为召回结果。通常情况下，我们还会提取图像的视觉描述信息，来进行辅助后校验，进一步提升召回的准确率。视频检索比对与图像类似，是在图像的基础上增加了关键帧的抽取，以及召回图像帧序列以后，会进行视频和音频级别的比对。
△图 1. 视频检索比对方法
基于 CNN 特征向量的数据检索，数据量大、特征维度高以及要求响应时间短。随着多媒体数据的快速增长，图像帧的数据量已经达到千亿甚至万亿级别，在这种大规模数据集的检索上，传统的暴力计算虽然能满足准确度的需求，但是在计算资源和检索时间的消耗上是巨大和无法接受的。为了降低搜索的空间复杂度与时间复杂度，在过去的十几年里研究者们找到了一种可供替代的方案：近似最近邻(Approximate Nearest Neighbor)检索方法。它们往往通过对向量集合进行预处理，生成一些可以用来指导查找过程的知识，在查找时以牺牲一定精度的方式加速查找过程。
百度富媒体内容比对系统，是一套包括离线 ANN 训练、建库和模型训练，在线特征预估、检索比对等功能在内的通用多媒体资源检索比对系统，处理的资源包括图像、视频和音频。
△图 2. 整体架构
- cnn-service: 用来提取资源特征的模块，包括图像、视频和音频三种类型资源的特征提取;
- feature-sevicez: 统一特征模块，提供统一特征提取和缓存功能，对上层隐藏异构 cnn 特征，可配置化访问指定cnn-service;
- vs-image: 召回前，访问 feature-service 计算 query 的特征，然后请求 as 获取 ann检索召回结果，进行视频和音频级别的比对；
- bs: Ann 索引服务，通过 cnn 特征，计算 topk召回，然后进行视觉特征后校验，最终得到召回结果。支持多分片和分片的自动更新、扩容;
- as: 支持 bs 多分片的并发访问和异构索引的检索 merge;
- finger-builder: 资源入库统一入口，获取资源 cnn 特征数据，并写入 afs；
- index-builder: 定时 ann 索引建库；
B 端反作弊
- 作者上传、抓取视频全覆盖
- 每天过滤 60%+的重复视频，减轻审核压力
- 高准确率，严格反作弊
- 百家号发文、UGC、小程序、贴吧等
C 端下发去重
- 用户体验
- 原创保护，生态建设
关联推荐
- 短带长，引入厂外长视频资源，可为用户关联当前视频的完整版
风控
- 涉政、黄反等敏感资源的识别和屏蔽
△图 3. 业务应用
1、ANN
ANN 搜索方法通过将全空间分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历，从而达到次线性的计算复杂度。正是因为缩减了遍历的空间大小范围，从而使得 ANN 能够处理大规模数据的索引。常见的 ANN 检索算法有：
- 基于树的方法：经典实现为 KD-Tree、Annoy 等。Annoy的核心是不断用选取的两个质心的法平面对空间进行分割，最终将每一个区分的子空间里面的样本数据限制在 K以内通过将空间按维度进行划分，缩小检索范围的方法来加速，适用于空间维度较小的情况。
- 基于 Hash 的方法：经典实现为 LSH、PCAH 等，LSH的核心思想是：在高纬度空间相邻的数据经过哈希函数的映射投影转化到低维空间后，他们落入同一个吊桶的概率很大而不相邻的数据映射到同一个吊桶的概率很小。在检索时将欧式空间的距离计算转化到汉明空间，并将全局检索转化为对映射到同一个吊桶的数据进行检索，从而提高了检索速度
- 矢量量化方法：PQ、OPQ 等，PQ的主要思想是将特征向量进行正交分解，在分解后的低维正交子空间进行量化，采用较小的码本进行编码，从而降低存储空间。
- 基于倒排索引的方法：IVF、IMI、GNO-IMI 等。
- 基于图的方法：NSW、HNSW、NSG 等。
2、GNOIMI
GNOIMI(The Generalized Non-Orthogonal Inverted Multi-Index)是百度内自研实现的 ANN 检索引擎，它通过聚类的方式将空间分割成许多子空间。在检索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历，从而达到次线性的计算复杂度。
CNN 特征通常特征维度高，保存全量数据特征所需内存与样本数据量成正比。对于千万级以上的数据集，通常面临内存受限的问题。GNOIMI 使用 PQ 乘积量化的方法，用一个有限子集对全量特征空间进行编码，达到大幅的降低内存消耗的目的。
1.训练 1)空间分割 GNOIMI 使用聚类的方法对训练集特征向量空间进行分割。
用户保证原始特征数据无重复，从原始数据中随机抽样。抽样数据集个数小于等于 500w， 
。
对抽样样本进行 KMEANS 聚类，得到初始的一级聚类中心 
。计算抽样本与其所属一级子空间聚类中心的残差向量，在残差向量上进行 K-means 聚类，将残差向量空间分为 L 个子空间，得到二级聚类中心码本
。一二级聚类中心将整个数据空间分割为个子空间（cell），每个 cell 的聚类中心点定义为
。任一训练集样本特征向量所属的 cell，满足
。
空间分割如图 4 所示，所有一级聚类中心共享二级聚类中心。
△图 4
因为二级聚类中心使用的是全量原始特征的残差向量，因而认为二级聚类中心在每个一级子空间内分布相似，全量原始特征数据共享二级聚类中心。这种方法被称为 NO-IMI(The Non-Orthogonal Inverted Multi-Index)。蓝色点为一级聚类中心点，红色点为个 cell 的聚类中心点。显然，cell 的形状和大小需根据数据分布可变，尤其是在全量特征数据空间同时存在稀疏和密集区域时。引入参数矩阵，cell 的聚类中心点定义为。引入参数矩阵后 cell 分布如图 5 所示，cell 的形状和大小根据实际数据分布可变，空间分割更符合一级子空间内数据分布情况。参数矩阵是有全量数据计算得到的，因而更准确的描述数据分布，称这种方法为 GNO-IMI。
△图 5
2)乘积量化
计算抽样数据集中样本所属于的一二级距离中心，得到样本与一二级聚类中心的残差数据集。将残差数据集分为 nsq 个空间，每个子空间特征维度为 feature_dim/nsq，每个子空间分别进行 KMEANS 聚类，得到 256 个聚类中心(一个 char 占 8bit，可用一个 char 字长标记所有的聚类中心 ID)，得到每个子空间的码本。将 nsq 个子空间的子码本做笛卡尔积，得到整个数据集的 PQ 码本。
2.建库
计算原始特征向量数据集中样本所属的一二级聚类中心。
计算原始特征向量数据集中样本与其所属的一二级聚类中心的残差。将残差向量分为 nsq 个子空间，在每个子空间内，计算该子特征向量距离最近的聚类中心并记录聚类中心 ID，将 feature_dim 维度的特征向量映射为 nsq 个聚类中心的 ID，可用 nsq 个聚类中心 ID 标识该特征向量。通常取 nsq = feature_dim 进行四分之一量化，feature_dim * sizeof(float) -> nsq *sizeof(char)。
在检索过程中，将 query 与该样本在每个子空间内的距离，转化为与该样本距离最近的聚类中心的距离。因而，在检索过程中，无需加载原始特征向量，可降低检索过程中所需要的内存。
3.检索
-
特征进行归一化;
-
计算 query 与一级聚类中心的距离并排序;
-
计算 query 与前 gnoimi_search_cells 个一级聚类中心下的二级聚类中心的距离并排序，共计 gnoimi_search_cells * gnoimi_fine_cells_count 个二级聚类中心;
-
以优先队列的方式，从最近的二级聚类中心开始，依次取出其下的样本，并计算 query 与这些样本的距离，取满 neighbors_count 个为止;
-
排序后返回 topK 个样本和对应的距离
4.实现
ANN 的算法本身并不算复杂，难点主要在实现上，GNOIMI 做了大量实现优化，简要介绍如下：
1）设计新的训练方案，重新组织一二级聚类中心的关系，在召回率略微提升的前提下，训练速度提升 1000%。
2）对于 L2/COS 距离空间下，任意三点满足三角不等式；在建库阶段，根据该特质，利用样本、一级聚类中心和二级聚类中心之间的两两距离进行剪枝，可降低 95%+的计算量，建库速度提升 550%+。
3）训练 &建库所需内存大大降低，仅为 Faiss-IVF*和 nmslib-HNSW 的 10%。
4）在检索阶段，空间分割规模超过千万，计算 query 与二级聚类中心过程中，设计新的计算 &排序逻辑，将百万级聚类中心的计算 &排序时延控制在 2ms 内，降低 20 倍。计算 query 与样本距离时，优化 PQ 量化计算过程，降低 800%+的计算量，整体吞吐提升 30%+。
5.应用
GNOIMI 与 IVF*比较时，使用相同聚类中心个数及检索 doc 个数下，比较检索时间、召准和内存；与 HNSW 比较时，在相同检索时间下，比较召准和内存。
经过测评，百万数据量级相同检索时间内 GNOIMI 效果略低于 HNSW，远超 ivf，内存占用极小，HNSW 效果最优，但内存消耗最多。随着数据增多，维度增大，相同检索时间内 GNOIMI 效果相比其他更优，内存保持低增长。
目前 GNOIMI 广泛应用于百度内各种场景，包括视频比对、图片/视频检索、FEED 等等场景，支撑规模上千亿特征，每天 PV 过 10 亿
3、HNSW
HNSW（Hierarchical Navigable Small World）是 ANN 搜索领域基于图的算法。它的前身是 NSW (Navigable-Small-World-Graph) 。NSW 通过设计出一个具有导航性的图来解决近邻图发散搜索的问题，但其搜索复杂度仍然过高，达到多重对数的级别，并且整体性能极易被图的大小所影响。HNSW 则是着力于解决这个问题。作者借鉴了 SkipList 的思想，提出了 Hierarchical-NSW 的设想。简单来说，按照一定的规则把一张的图分成多张，越接近上层的图，平均度数越低，节点之间的距离越远；越接近下层的图平均度数越高，节点之间的距离也就越近（见下图 6）。
搜索从最上层开始，找到本层距离最近的节点之后进入下一层。下一层搜索的起始节点即是上一层的最近节点，往复循环，直至找到结果。由于越是上层的图，节点越是稀少，平均度数也低，距离也远，所以可以通过非常小的代价提供了良好的搜索方向，通过这种方式减少大量没有价值的计算，减少了搜索算法复杂度。更进一步，如果把 HNSW 中节点的最大度数设为常数，这样可以获得一张搜索复杂度仅为 log(n) 的图。
△图 6. hnsw
HNSW 的一个显著优点是无需训练，在某些没有初始数据的场景非常好用。
目前百度内容侧使用的是 hnsw 的一种优化实现，在开源版本的基础上，做了很多优化，性能提升了将近 3.6 倍。
1.图像比对
目前主要有两种表征图像的方法：局部特征点和图像 CNN 向量。
- 局部特征点：对图片的视觉描述，如 SIFT、ORB 等，对尺度、旋转、亮度保持不变，视觉变化、防射变化、噪声也有一定的稳定性。
- 图像 CNN 特征：对图像的语义特征，通常使用 CNN 分类模型等的最后几层网络输出。
△图 7
因此当前比对技术，采用 CNN 特征筛选+视觉局部特征后校验
△图 8
2.视频比对
视频比对复用了图像比对的技术，在帧检索的基础上增加了视频和音频级别的比对技术，主要是基于动态规划计算最佳匹配序列。
△图 9
近年来，随着计算机技术的发展，图片、视频、音频等富媒体信息的呈井喷式增长，内容检索比对技术在推荐、搜索等各个领域也有了更广泛的应用。本文对百度富媒体检索比对系统的基本原理和核心技术进行了一次全面的总览介绍，同时介绍了各模块的工作机制，包括：特征提取、离线训练建库、在线预估、检索比对等。它提供了一套通用的多媒体资源检索比对方案，保证了高召回、高准确和高性能。基于百度 FEED 和搜索两大核心业务，它拥有全网最大的数据规模和最丰富的资源类型，涵盖了短视频、小视频、直播、图片等绝大数富媒体资源，服务于 30+产品线，为百度产品的效果提升提供了有效的辅助。
文章看完，还不过瘾？ 更多精彩内容欢迎关注百度开发者中心公众号