導讀：百度富媒體檢索比對系統是一套基于 Ann(approximate nearest neighbor)檢索和內容特征比對技術，旨在提供針對圖像、音頻、視頻等多媒體資源的相似檢索系統。包括離線訓練、建庫，在線特征提取、檢索。目前百度富媒體檢索比對系統除了承接了百度 FEED 所有視頻、圖像的反作弊、下發去重以及關聯推薦和黃反等業務，另外還支持了包括視頻搜索、貼吧、文庫在內的數十個業務方，支撐了千億級數據規模。在數據規模、系統性能、召回率和準確度上都處于領先地位。

01 背景

隨著互聯網和 AI 技術的發展，網絡信息的主要傳輸媒介，已經從傳統的網頁文字發展到圖片、視頻、音頻等資源，相對純文字的網頁，富媒體內容能傳遞更多的信息量，同時也帶來更新的用戶體驗。隨著富媒體內容急劇爆發, 理解這些實體內容，找到他們之間的相似關系，不僅能夠對這些富媒體內容進行篩選和處理，還可以更好的被推薦和搜索引擎理解，更好的服務用戶。

得益于神經網絡的飛速發展，多媒體數據的檢索問題通常可以轉化為高維向量的相似性檢索, 采用 CNN(Convolutional Neural Network）的各種特征來描述這些多媒體資源的語義信息，基于 CNN 特征向量，將 query 與庫中所有數據進行相關性計算，檢索出相關的結果集。以圖像為例，我們首先會對存量圖像，進行收錄、篩選，計算它們的 CNN 特征，然后把這些 CNN 進行建庫。當輸入 query 圖像，需要從歷史庫中檢索出與之相似或相同的圖像時，我們首先計算 query 圖像的 CNN 特征，然后與歷史庫中的全量 CNN 特征進行計算（通常計算歐式或 cosin 距離），選取距離最近的 topk 個圖像作為召回結果。通常情況下，我們還會提取圖像的視覺描述信息，來進行輔助后校驗，進一步提升召回的準確率。視頻檢索比對與圖像類似，是在圖像的基礎上增加了關鍵幀的抽取，以及召回圖像幀序列以后，會進行視頻和音頻級別的比對。

△圖 1. 視頻檢索比對方法

基于 CNN 特征向量的數據檢索，數據量大、特征維度高以及要求響應時間短。隨著多媒體數據的快速增長，圖像幀的數據量已經達到千億甚至萬億級別，在這種大規模數據集的檢索上，傳統的暴力計算雖然能滿足準確度的需求，但是在計算資源和檢索時間的消耗上是巨大和無法接受的。為了降低搜索的空間復雜度與時間復雜度，在過去的十幾年里研究者們找到了一種可供替代的方案：近似最近鄰(Approximate Nearest Neighbor)檢索方法。它們往往通過對向量集合進行預處理，生成一些可以用來指導查找過程的知識，在查找時以犧牲一定精度的方式加速查找過程。

02 整體架構

百度富媒體內容比對系統，是一套包括離線 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 索引建庫；

03 應用場景

B 端反作弊

• 作者上傳、抓取視頻全覆蓋
• 每天過濾 60%+的重復視頻，減輕審核壓力
• 高準確率，嚴格反作弊
• 百家號發文、UGC、小程序、貼吧等

C 端下發去重

• 用戶體驗
• 原創保護，生態建設

關聯推薦

• 短帶長，引入廠外長視頻資源，可為用戶關聯當前視頻的完整版

風控

• 涉政、黃反等敏感資源的識別和屏蔽

△圖 3. 業務應用

04 關鍵技術

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 倍。

05 比對技術

1.圖像比對

目前主要有兩種表征圖像的方法：局部特征點和圖像 CNN 向量。

• 局部特征點：對圖片的視覺描述，如 SIFT、ORB 等，對尺度、旋轉、亮度保持不變，視覺變化、防射變化、噪聲也有一定的穩定性。
• 圖像 CNN 特征：對圖像的語義特征，通常使用 CNN 分類模型等的最后幾層網絡輸出。

△圖 7

因此當前比對技術，采用 CNN 特征篩選+視覺局部特征后校驗

△圖 8

2.視頻比對

視頻比對復用了圖像比對的技術，在幀檢索的基礎上增加了視頻和音頻級別的比對技術，主要是基于動態規劃計算最佳匹配序列。

△圖 9

06 總結

近年來，隨著計算機技術的發展，圖片、視頻、音頻等富媒體信息的呈井噴式增長，內容檢索比對技術在推薦、搜索等各個領域也有了更廣泛的應用。本文對百度富媒體檢索比對系統的基本原理和核心技術進行了一次全面的總覽介紹，同時介紹了各模塊的工作機制，包括：特征提取、離線訓練建庫、在線預估、檢索比對等。它提供了一套通用的多媒體資源檢索比對方案，保證了高召回、高準確和高性能。基于百度 FEED 和搜索兩大核心業務，它擁有全網最大的數據規模和最豐富的資源類型，涵蓋了短視頻、小視頻、直播、圖片等絕大數富媒體資源，服務于 30+產品線，為百度產品的效果提升提供了有效的輔助。

文章看完，還不過癮？
更多精彩內容歡迎關注百度開發者中心公眾號

總結

以上是生活随笔為你收集整理的超详细！百度富媒体检索比对系统的关键技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。