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

全文5612字，預計閱讀時間11分鐘。小程序

1、背景

隨着互聯網和AI技術的發展，網絡信息的主要傳輸媒介，已經從傳統的網頁文字發展到圖片、視頻、音頻等資源，相對純文字的網頁，富媒體內容能傳遞更多的信息量，同時也帶來更新的用戶體驗。隨着富媒體內容急劇爆發, 理解這些實體內容，找到他們之間的類似關係，不只可以對這些富媒體內容進行篩選和處理，還能夠更好的被推薦和搜索引擎理解，更好的服務用戶。
得益於神經網絡的飛速發展，多媒體數據的檢索問題一般能夠轉化爲高維向量的類似性檢索, 採用CNN(Convolutional Neural Network）的各類特徵來描述這些多媒體資源的語義信息，基於CNN特徵向量，將query與庫中全部數據進行相關性計算，檢索出相關的結果集。以圖像爲例，咱們首先會對存量圖像，進行收錄、篩選，計算它們的CNN特徵，而後把這些CNN進行建庫。當輸入query圖像，須要從歷史庫中檢索出與之類似或相同的圖像時，咱們首先計算query圖像的CNN特徵，而後與歷史庫中的全量CNN特徵進行計算（一般計算歐式或cosin距離），選取距離最近的topk個圖像做爲召回結果。一般狀況下，咱們還會提取圖像的視覺描述信息，來進行輔助後校驗，進一步提高召回的準確率。視頻檢索比對與圖像相似，是在圖像的基礎上增長了關鍵幀的抽取，以及召回圖像幀序列之後，會進行視頻和音頻級別的比對。
△圖1. 視頻檢索比對方法

緩存

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

網絡

2、總體架構

百度富媒體內容比對系統，是一套包括離線ANN訓練、建庫和模型訓練，在線特徵預估、檢索比對等功能在內的通用多媒體資源檢索比對系統，處理的資源包括圖像、視頻和音頻。△圖2. 總體架構
架構

• cnn-service: 用來提取資源特徵的模塊，包括圖像、視頻和音頻三種類型資源的特徵提取;併發

• feature-sevicez: 統一特徵模塊，提供統一特徵提取和緩存功能，對上層隱藏異構cnn特徵，可配置化訪問指定cnn-service;app

• vs-image: 召回前，訪問feature-service計算query的特徵，而後請求as獲取ann檢索召回結果，進行視頻和音頻級別的比對;ide

• bs: Ann索引服務，經過cnn特徵，計算topk召回，而後進行視覺特徵後校驗，最終獲得召回結果。支持多分片和分片的自動更新、擴容;函數

• as: 支持bs多分片的併發訪問和異構索引的檢索merge;性能

• finger-builder: 資源入庫統一入口，獲取資源cnn特徵數據，並寫入afs；

• index-builder: 定時ann索引建庫；

3、應用場景

• B端反做弊

  • 做者上傳、抓取視頻全覆蓋

  • 天天過濾60%+的重複視頻，減輕審覈壓力

  • 高準確率，嚴格反做弊

  • 百家號發文、UGC、小程序、貼吧等

• C端下發去重

  • 用戶體驗

  • 原創保護，生態建設

• 關聯推薦

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

• 風控

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

△圖3. 業務應用

4、關鍵技術

一、ANN

ANN搜索方法經過將全空間分割成不少小的子空間，在搜索的時候，經過某種方式，快速鎖定在某一（幾）子空間，而後在該（幾個）子空間裏作遍歷，從而達到次線性的計算複雜度。正是由於縮減了遍歷的空間大小範圍，從而使得ANN可以處理大規模數據的索引。常見的ANN檢索算法有：

• 基於樹的方法：經典實現爲KD-Tree、Annoy等。Annoy的核心是不斷用選取的兩個質心的法平面對空間進行分割，最終將每個區分的子空間裏面的樣本數據限制在K之內經過將空間按維度進行劃分，縮小檢索範圍的方法來加速，適用於空間維度較小的狀況。

• 基於Hash的方法：經典實現爲LSH、PCAH等，LSH的核心思想是：在高緯度空間相鄰的數據通過哈希函數的映射投影轉化到低維空間後，他們落入同一個吊桶的機率很大而不相鄰的數據映射到同一個吊桶的機率很小。在檢索時將歐式空間的距離計算轉化到漢明空間，並將全局檢索轉化爲對映射到同一個吊桶的數據進行檢索，從而提升了檢索速度。

• 矢量量化方法：PQ、OPQ等，PQ的主要思想是將特徵向量進行正交分解，在分解後的低維正交子空間進行量化，採用較小的碼本進行編碼，從而下降存儲空間。

• 基於倒排索引的方法：IVF、IMI、GNO-IMI等。

• 基於圖的方法：NSW、HNSW、NSG等。

二、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.檢索

1) 特徵進行歸一化;2) 計算query與一級聚類中心的距離並排序;3) 計算query與前gnoimi_search_cells個一級聚類中心下的二級聚類中心的距離並排序，共計gnoimi_search_cells * gnoimi_fine_cells_count個二級聚類中心;4) 以優先隊列的方式，從最近的二級聚類中心開始，依次取出其下的樣本，並計算query與這些樣本的距離，取滿neighbors_count個爲止;5) 排序後返回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億

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

5、比對技術

1.圖像比對

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

• 局部特徵點：對圖片的視覺描述，如SIFT、ORB等，對尺度、旋轉、亮度保持不變，視覺變化、防射變化、噪聲也有必定的穩定性。

• 圖像CNN特徵：對圖像的語義特徵，一般使用CNN分類模型等的最後幾層網絡輸出。

△圖7

所以當前比對技術，採用CNN特徵篩選+視覺局部特徵後校驗△圖8

2.視頻比對

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

6、總結

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

閱讀原文：詳解百度富媒體檢索比對系統的關鍵技術

更多幹貨、內推福利，歡迎關注同名公衆號「百度Geek說」～