HCHUNGW的部落格

8.8 Image Retrieval 圖像檢索 （上）

前言

本節介紹圖像檢索的概念及相關優化演算法，為後續代碼實踐打下基礎。

本節主要內容包括：

1. 常用資料集
2. 評價指標：R@K、mAP的計算
3. 常用的loss
4. 向量檢索框架簡介：Faiss、Milvus、Jina、Proxima和vearch都是工業界常用的向量檢索框架
5. 向量檢索優化演算法：LSH（局部敏感雜湊）、HNSW（基於圖的近似最近鄰搜索）、PQ（乘積量化）、IVF（倒排檢索）
6. 檢索中的排序：粗排、精排、重排的概念

圖像檢索簡介

圖像檢索（Image Retrieval）指根據使用者輸入的資訊進行圖像查詢，在資料庫中查找出與之相似/相關的圖像。

圖像檢索在電商、安防、醫學領域有廣泛應用，例如微信掃一掃、淘寶的拍立淘、搜尋引擎的圖片搜索功能等。

圖像檢索可根據輸入的內容不同，可分為以文搜圖和以圖搜圖。

以文搜圖又稱TBIR (Text Based Image Retrieval)，是通過圖片名稱、關鍵字等資訊進行檢索，是早期圖像檢索的方法，依賴於圖像的描述資訊。

以圖搜圖又稱CBIR (Content Based Image Retrieval)，也叫基於內容的圖像檢索，也是目前主流的方法。CBIR的方式更符合人類視覺感覺，基於圖像內容、圖像相似度進行檢索相似的圖像。本節後續內容均以CBIR為例。

下圖是圖像檢索系統的基礎元件，通常分為offline和online兩部分，offline主要構建圖像資料庫及特徵資料庫，online則是完成query圖像特徵提取，並從特徵資料庫中找到相似的特徵，最終由推薦策略模組輸出相似圖像。

在構建圖像檢索系統時，需要關注：

1. 特徵提取器：傳統方法中會基於SIFT、HoG等特徵描述子，2012年後，主要是基於神經網路進行特徵提取，獲得特徵向量，如1x768維，本文後續也會基於CLIP來進行特徵提取。對特徵提取器一個簡單的要求是，相似圖像的特徵向量的歐氏距離要相近，差異大的圖像的歐氏距離要大。特徵提取模型可分為無監督與有監督的，無監督的主要採用視覺預訓練模型進行特徵提取，如CLIP， BLIP之類的，有監督的訓練則可以採用CNN-base或者ViT-base的模型進行訓練。
2. 向量檢索：如何快速的從億萬級的特徵資料庫中找到相似的那一批特徵向量，這是向量檢索及推薦策略需要考慮的，後續會介紹一系列快速的向量檢索策略。
3. 推薦策略：由於特徵檢索階段採用了快速檢索方法，勢必損失一定精度，因此在後續需要做一些排序策略，如粗排、精排、重排等，最終輸出相似的檢索結果。

圖像檢索資料集

圖像檢索常用資料集並不多，常用的有Oxford-5k, UKBench, Holidays, Paris-6k

• Oxford-5k 由牛津的11個建築物的5062張圖片構成，每個建築物提供了5張query image。標籤從官網下載，圖片從paddle下載
• UKBench 包含2550組，每組4張圖，總共10200張圖片，圖片由日常生活中常見的物體構成，如物體、場景和CD封面等。下載連結：https://pan.baidu.com/s/1LAURtLwq8UYPW3cnetDCyg 提取碼：yrsy
• Holidays 是個人假日相冊中收集的1491張圖像，有500張query images， 991張相關圖像。
• Paris-6k 包含來自Flickr上爬取的6412張圖片，由12組巴黎的建築構成，總共提供了500張 query images進行評估。

數據從kaggle下載

圖像檢索評價指標

以圖搜圖中，常用的評價指標有mAP和R@1, R@5, R@10。

R@K：top-k個檢索結果中的召回率(recall)，對於檢索結果中存在目標結果的即判為召回，記1分， 總得分÷樣本總數 = R@K。

假設我們有一個包含100張圖片的資料集，進行一次圖片檢索，對於查詢圖片Query-img來說，100張圖片裡只有1張是相似的，GT為圖片編號5，其它的都是負樣本，假設演算法返回的Top 10檢索結果如下：

R@1，Top 1的圖片編號為56，不是真實目標，因此R@1的值為0。

R@5，Top 5的圖片編號為56、12、5、88、1，其中圖片5是真實目標，因此R@5的值為1。

R@10，Top 10的圖片中，其中圖片5是真實目標，因此R@10的值為1。

假設有20張查詢圖片，統計20張查詢圖片的R@1，得到20個R@1，求平均，即可得到最終R@1。

由此可知，R@1≤ R@5≤ R@10。

mAP

mAP（mean average precision）是AP的平均值，對於每一張查詢圖片計算一個AP，求取平均。

AP值是PR（Precision-Recall）曲線下的面積，具體定義參考機器學習基礎知識。

這裡借助一個視頻的示意圖來講解具體的計算

上圖有兩個查詢，分別是query 1和query 2，其中黑色的樣本表示正樣本，是期望所檢索到的樣本，白色是負樣本。

對於查詢圖像1，有5個相關結果，檢索的排序結果如圖所示，分別排在了1,3,6,9,10。

AP是將5個結果的Precision求平均，每個結果的Precision為 “標籤次序÷結果次序”。

因此查詢圖像1的AP = （1/1 + 2/3 + 3/6 + 4/9 + 5/10）/ 5 = 0.62

mAP則是將所有查詢圖像的AP求取平均，如上例，為 (0.62+0.44) / 2 = 0.53

圖像檢索常用loss

圖像檢索選擇特徵提取器時，如果需要自行訓練一個特徵提取器，通常會選擇一個適合的loss來約束模型輸出的特徵向量。

這裡可能不好理解，先從圖像分類模型思考，分類模型輸出層前一層通常認為是對圖像的特徵描述，這個特徵向量被認為是具備圖像語義資訊的描述，它只需要經過一個分類層，就能實現圖像分類。

Triplet Loss

同理，也可把該特徵向量認為是圖像的描述，用於圖像檢索，但是圖像檢索裡，還希望相同類別的向量的歐氏距離要近，不同類別的向量要遠。

這時就可以在此處增加一個Triplet Loss（三元組損失函數）進行訓練，triplet loss訓練時有3個樣本，分別稱為anchor， negative， positive。

A表示靶心圖表片，N表示負樣本，要與靶心圖表片遠離的， P表示正樣本，與A是同類型圖片，要接近的。

更詳細的triplet loss請閱讀原論文，提出triplet loss是為了解決人臉比對問題的，後來拓展到各類對比任務中。在圖像檢索任務中，Triplet Loss同樣具有較好的表現。通過將同一類別的圖片的嵌入向量盡可能地接近，而將不同類別的嵌入向量盡可能地遠離，可以實現高效的圖像檢索。

(N+1)-tuplet loss

三元損失函數考慮的 negative 樣本太少，以至於收斂慢，為此，研究者提出了(N+1)-tuplet loss，一次考慮N-1個負樣本，N=2時，等價於 triplet loss。

(N+1)-tuplet loss 如下圖所示

N-pair Loss

(N+1)-tuplet loss 有個缺點是計算量大，需要計算N-1個負樣本的距離，推理成本過高。

為此，提出了N-pair Loss，巧妙的實現樣本的重複利用，減少了負樣本的多次運算。N-pair loss 思想是把其他樣本的正樣本作為當前樣本的負樣本，這樣就不用重複計算不同樣本的負樣本，只需要計算 N 次即可得出。

除了 triplet loss 思路外，還可以借鑒其它類似任務的loss，例如：

人臉：ArcFace，sub-ArcFace

類內損失：center loss， Island loss

類間損失：cosface

度量學習任務：Multi-Similarity Loss， Contrastive Loss / Pairwise Ranking Loss，SimCSE loss， Smooth AP

更多loss參考論文2021年的Deep_Image_Retrieval_A_Survey

檢索核心技術——向量檢索

向量檢索概念

圖像檢索的核心技術之一是向量檢索，也稱向量索引、相似度匹配，是將query向量與資料庫中萬億級的向量進行相似度匹配，要求又快又准的找出相似向量。

向量相似度可以通過歐氏距離、余弦距離、漢明距離等距離度量方法來計算，通常float類型採用歐氏距離，二值雜湊採用漢明距離。

對於歐氏距離、余弦距離來說，時間複雜度為O(nd)，其中n是資料集中向量的數量，d是向量的維度，這對於億萬級的檢索是不可接受的。

為了實現快速的向量檢索，針對暴力檢索（精確檢索）有一系列的優化演算法，例如基於樹的KD-Tree，基於圖的NSW、HNSW， 倒排索引、PQ（乘積量化，Product-Quantization）等。

由於採用了快速索引，必然導致精度損失，因此在向量檢索之後，通常有排序演算法的介入，一般有粗排、精排和重排，這個在下一小節講解。

向量檢索框架

向量檢索不僅可用於圖像檢索，在搜尋引擎、短視頻推薦、商品推薦等領域均是基礎模組，有較多開發者及對應的產品，因此，可以選擇開源的向量檢索引擎，而無需造輪子。

下面簡單總結幾款常用的框架

• Faiss：由 Facebook 開發的適用于稠密向量匹配的開源庫。
•  
  • 支持相似度檢索和聚類
•  
  • 支援多種索引方式
  • 支援CPU和GPU計算
  • 支援Python和C++調用
  • 常見的人臉比對，指紋比對，基因比對等
  • 缺點是單機部署，無法分散式
• Milvus：是一個開源的分散式向量搜尋引擎。集成了成熟的向量相似度搜索技術，包括Faiss、Annoy、NMSLIB等。
• Jina ：Jina AI公司開發，是一家專注基於深度學習模型搭建搜尋引擎技術的開源商業公司
• Proxima：阿裡巴巴達摩院自研的向量檢索內核，通用化的向量檢索工程引擎，實現了對大資料的高性能相似性搜索，支援 ARM64、x86、GPU 等多種硬體平臺
• vearch：是京東開源一個分散式向量搜索系統，可用來存儲、計算海量的特徵向量，在 faiss 的基礎上研發了 vearch，提供了類似 ElasticSearch 的靈活易用的 RESTFul API，可以方便地對表結構及資料進行管理查詢。

更多框架介紹推薦閱讀幾款多模態向量檢索引擎

Faiss簡介

對於80%的場景，基於faiss足以滿足需求，並且faiss開源早，性能強大，功能多，且易上手，這裡就介紹Faiss的使用及常用演算法的原理。

Faiss由 Facebook AI開發及開源，適用於億級的稠密向量檢索，並且部分演算法支援GPU加速。

faiss中常用的演算法有，精確檢索FlatL2、FlatIP，局部敏感雜湊LSH（Locality-Sensitive Hashing），基於圖的近似最近鄰搜索 HNSW，倒排檢索 IFS（Inverted File System，倒排）和 乘積量化PQ（Product Quantization）。

更詳細介紹，參見faiss wiki

最常用的演算法是倒排、乘積量化，接下來會對上述4個演算法進行介紹，並詳細介紹倒排與乘積量化。

LSH——局部敏感雜湊

LSH是雜湊演算法中的一種，是將向量映射為標量，並進行分桶，距離較近的向量在雜湊後映射到同一個桶的概率較高，反之概率較低，這個性質稱之為局部敏感。

下麵借助一位Up主的講解及代碼，解釋LSH實現過程：

1. 選擇一系列hash functions，對原始資料進行投影，一個樣本變為一個標量
2. 選擇分桶間隔w，標量除以間隔w，並向下取整，獲得樣本的hash編碼

如上圖，6個資料經過一次投影後得到的hash編碼分別是 0, 1, 2, 3, 5, 5，選擇多個hash functions即可得到一個樣本的多個編碼，即可構成一個編碼向量。

hash function到底要選擇怎樣的投影方式，才能使得距離較近的向量在雜湊後映射到同一個桶的概率較高，反之概率較低呢？

其實這裡可以直接採用高斯分佈採樣得到的向量，與樣本x進行點乘即可，這個可以通過P穩定分佈定義進行證明，詳情可參見第八講 圖像檢索

下面看一個具體案例，包含8個向量，採用4個hash functions進行編碼，得到的編碼如下。

可以看到，樣本7和樣本8的4個編碼都相同，表明它們很類似。

同理，樣本1和樣本2的hash編碼也很類似，因它們的樣本資料比較類似。

原始資料：

[[8, 7, 6, 4, 8, 9], [7, 8, 5, 8, 9, 7], [3, 2, 0, 1, 2, 3], [3, 3, 2, 3, 3, 3], [21, 21, 22, 99, 2, 12],

           [1, 1, 1, 0, 1, 0], [1, 1, 1, 1, 1, 0]]

編碼向量：

[3.0, 3.0, 0.0, 1.0, 8.0, 0.0, 0.0]

[5.0, 5.0, 1.0, 2.0, 32.0, 1.0, 1.0]

[4.0, 4.0, 1.0, 2.0, 22.0, 0.0, 0.0]

[7.0, 6.0, 2.0, 3.0, 21.0, 1.0, 1.0]

Copy

import numpy as np

import random

def getHash(v, x, b, w):

    return (v.dot(x) + b) // w

def dealOneBuket(dataSet):

    k = dataSet.shape[1]

    b = random.uniform(0, w)

    x = np.random.random(k)

    buket = []

    for data in dataSet:

        h = getHash(data, x, b, w)

        buket.append(h)

    return buket

if __name__ == "__main__":

    dataSet = [[8, 7, 6, 4, 8, 9], [7, 8, 5, 8, 9, 7], [3, 2, 0, 1, 2, 3], [3, 3, 2, 3, 3, 3], [21, 21, 22, 99, 2, 12],

               [1, 1, 1, 0, 1, 0], [1, 1, 1, 1, 1, 0]]

    dataSet = np.array(dataSet)

    w = 4

    hash_funcs_num = 4

    for _ in range(hash_funcs_num):

        print(dealOneBuket(dataSet))

Copy

HNSW——基於圖的近似最近鄰搜索

HNSW（Hierarchical Navigable Small World）是一種以空間換時間的基於圖的最近鄰搜索，屬於基於層級結構的ANN（Approximate Nearest Neighbor）演算法，通過建立多層圖結構實現高效的最近鄰搜索。其核心思想是在每一層圖中使用稠密連接的方式建立向量之間的聯繫，同時保持局部連通性，從而形成“小世界”網路。

分層機制類似高速公路，頂層是省份間的連接，往下則是城市之間，城市內部之間的連接，由大到小的縮小檢索範圍。

更詳細理解，推薦閱讀Faiss的手冊

倒排索引的優點是可以快速地定位包含某個特徵的向量，適用于高維稠密向量。但是在處理高維稀疏向量時，倒排索引的效果會受到影響。

總之，倒排索引是向量檢索演算法中重要的一種索引方式，可以大幅提高檢索效率和準確性。

PQ —— 乘積量化

PQ（product quantizaition）是2011年，Herve Jegou等學者在PAMI上發表的論文《Product quantization for nearest neighbor search》，提出的一個快速向量檢索演算法。

PQ方法可以減少幾十倍的RAM消耗，並且獲得數倍的速度提升，並且精度損失不是很大，非常適合高維向量檢索任務的優化。

PQ演算法的思想是將原始向量分解為多個子向量，並對每個子向量進行量化，從而將高維空間中的向量轉換為一個小的離散碼本，編碼代表子向量所處的聚類中心的編號。查詢向量需要與子向量的聚類中心進行距離計算，獲得距離表，隨後資料庫向量根據編碼進行查詢，即可獲得查詢向量與被索引向量的距離，最後對子段距離求和、排序。

PQ的思想可以總結為，將高維向量劃分子段，並且利用子段的聚類中心來代替原始資料，查詢向量只需要與聚類中心計算距離，即可實現所有向量距離的近似計算。

下面以一個1000個128維向量資料庫為例，講解PQ過程。

第一步，pre-train，獲得聚類中心。

第二步，對資料庫向量進行編碼。

第三步，查詢向量與聚類中心計算距離表。

第四步，查詢所有向量與查詢向量的距距離求和、排序，得到結果。

第一步：pre-train，對128維向量劃分為M份，這裡劃分8個子段，每個欄位長度為16，針對每個欄位進行K-means聚類，聚為256類（256是作者自訂的）。

打不嚴謹的比方，1000個向量分為256類，平均4個向量為一簇，由1個聚類中心向量代表，後續查詢向量只需要與聚類中心比較，就可知道查詢向量與4個向量的距離了。簡單理解就是聚類簇中的向量統一由聚類中心作為代表，查詢向量與中心近，那麼就與類成員近，以此減少計算量。

第二步，對資料庫向量進行編碼，得到資料庫的PQ code，這個code的作用是用於查表的，即每個向量它被誰代表了，後續只需要去找“代表”獲取距離，而不是與查詢向量計算距離。

1000個128維向量，最終的PQ code為 1000x8bit的碼表，碼表上的值表示它歸屬於哪個聚類中心，如第一個向量的第一個欄位為2，則說明它屬於第二類，它後續與查詢向量的距離只需要查看，查詢向量與第二個聚類中心的距離即可。

經過PQ編碼，記憶體的效果顯著下降，下降了64倍，64來自128維下降到了8維，這裡減少了16倍；資料精度由32b減少到了8b，這裡減少了4倍，總共64倍。

第三步，查詢向量與聚類中心計算距離，獲得查詢向量與聚類中心的距離表（256x8）。

例如查詢向量為[1, 2, ..., 128]，首先對第一子段進行256個聚類中心的距離計算，採用[1, 2, 3, 4, 5, 6, 7, 8]與256個聚類中心計算距離，填入Distance Table的第一列，

以此類推，獲得256x8的距離表。

距離表的作用是供PQ code查詢的，前面提到，資料庫向量已經被代表了，被聚類中心代表，查詢向量不與資料庫向量直接計算距離，而是與聚類中心計算距離。

資料庫向量只需要找到它的代表與查詢向量的距離即可，因此PQ code是 Distance Table的索引，只需要查表即可獲得資料庫向量與查詢向量的距離。

第四步，查詢所有向量與查詢向量的距距離求和、排序，得到結果。

PQ演算法巧妙的採用了代表（聚類中心），以此減少運算複雜度，同時得益于代表（聚類中心），資料庫無需存儲所有資料，只需要存儲所處聚類的編號，從存儲上優化了演算法。

IVF —— 倒排檢索

IVF（Inverted File Index），倒排檔索引，用於快速地定位包含某個特徵的向量。其中使用了聚類分組、倒排索引的方法來加速索引速度。

這裡的Inverted Index 是著名的倒排索引演算法，最早來自文本搜索領域，關於Inverted Index的命名及翻譯，讓人多少有些困惑，倒排？怎麼倒？怎麼排？

其實這裡和“倒”沒啥關係，更好的中文意譯是，分詞索引或反向索引。詳見知乎問題

Inveted Index是從文檔檢索中提出的，以往檢索文檔是通過一個一個文檔中從頭到尾比對，是否存在關鍵字，是文檔-->關鍵字的方式；倒排則是將文檔中文字進行分詞，並且構建詞到文檔編號的一個字典索引，查詢時只需要根據字典的key索引，可得到哪些文檔中存在這些關鍵字。

這裡借助 喔喔牛的回答 - 知乎

假設有一個文檔資料庫，共5分文檔，現在需要檢索“wave”關鍵字在哪份文檔中，正向索引則是挨個文檔一次檢索匹配“wave”，到了第4個文檔的中間才能找到，相當耗時。

倒排索引的思路是將文檔中的詞先拆分，需要用分詞工具把文檔打散稱為一系列word，然後構建關鍵字到文檔的關係字典。

如下圖，通過倒排索引字典，直接獲取文檔3是包含"wave"的，效率提升顯而易見。

回到Faiss中的IVF，IVF是將向量先分為nlist個組，每組有一個聚類中心及類別id，通過構建聚類中心+類別id 到 向量的索引字典，可以快速的找到查詢向量與哪一些資料庫向量是相近的，與上文的PQ量化中的聚類類似，一群被檢索向量採用聚類中心作為代表。

具體地，IVF演算法流程如下：

1. 將資料集進行聚類，得到若干個簇（nlist個），每個簇有一個代表它的中心點；
2. 為每個簇建立一個倒排檔，key是聚類中心，value是簇內所有向量；
3. 對於一個查詢向量，計算其與每個簇中心點的距離，確定其所屬的簇；
4. 在所屬簇的倒排文件中搜索與查詢向量最相似的資料點。

在實際實現時，還會針對邊緣問題，提出所個類簇的比對，如下圖所示，對聚類中心最新的8個類簇內所有向量均進行比對，以此提高召回。詳情可見Faiss中的IVF

IVF+PQ

Faiss中用得更多的是將IVFPQ，主要是用IVF中的方法來減少搜索向量範圍，然後利用PQ的索引。product-quantization中對FlatL2（精確檢索）、PQ和IVFPQ進行了對比，可見IVFPQ速度快，並且召回與PQ相當。

這裡需要注意的是IVF中的nlist和nprobe是超參，需要仔細選擇，尤其是nprobe，文中實驗採用了nprobe=48才達到52%的召回，nrpobe越高，召回越高，但是時間越慢。

檢索核心技術——粗排、精排、重排

上文提到的一系列向量檢索方法僅僅是檢索的第一步——召回，通常一個檢索系統是級聯式的，多層級一步一步的由粗到精，得到最終輸出結果。

如下圖所所示

• 召回，是處理億萬級別資料量，要求的是速度快，精度可以不高，但別漏，去粗取精還有粗排、精排和重排來完成，但是漏了的話，後續是沒辦法“生成”、找回的。
• 粗排，是召回和精排之間的過渡，速度比精排快，但精確度不需要那麼高。
• 精排，核心層，直接決定檢索推薦的效果；
• 重排，根據業務邏輯，決定哪些item的順序需要調整。

總結下來，推薦演算法的這一套級聯策略——召回、粗排、精排、重排，與其電商業務、互聯網搜索業務息息相關，每一個模組為了處理特定了業務邏輯而設計的一個操作。

例如第一步召回是從億萬級數據撈資料的過程；

粗排、精排是根據特定的業務背景設計演算法、模型，詳見知乎文章；

重排也是根據業務邏輯，例如為了提升使用者的多樣性體驗，扶持業務產品，這時在重排層則需要寫一些固定的邏輯判斷來重排。

在圖像檢索領域，較少涉及粗排、精排，通常只需要做一個重排，圖像檢索的重排技術非常細分，這裡不進行介紹了，感興趣自行閱讀一下論文：

擴展查詢（Query Expansion）

• Ondrej Chum, James Philbin, Josef Sivic, Michael Isard, and Andrew Zisserman. Total recall: Automatic query expansion with a generative feature model for object retrieval. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, pages 1–8, 2007. 1, 2, 3, 9
• Ondˇ rej Chum, Andrej Mikulik, Michal Perdoch, and Jiˇ rí Matas. Total recall ii: query expansion revisited. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, pages 889–896, 2011

幾何信息法（Geometric Context Verification (GCV)）

• Yannis Avrithis and Giorgos Tolias. Hough pyramid matching: Speeded-up geometry re-rankingfor large scale image retrieval. International Journal of Computer Vision, 107(1):1–19, 2014

行人重識別中假陽過濾：Box Re-Ranking_ Unsupervised False Positive Suppression for Domain Adaptive Pedestrian Detection

基於Transformer的重排：Contextual Similarity Aggregation with Self-attentionfor Visual Re-ranking

小結

本小節介紹了圖像檢索技術的概念、資料集、損失函數和常用的評價指標，然後介紹了檢索的兩大核心技術，向量檢索與排序。

向量檢索中最常用的是PQ+IVF，這也將在後續代碼實現中進行使用以及講解，LSH和HNSW也有自己的特點，可根據是否需要用空間換時間來決定選擇。

檢索任務的排序環節包括一系列的操作，有粗排、精排、重排等操作，就像一個漏斗，逐步去粗取精，每一步都是與業務場景息息相關，在圖像任務中往往只需要一個重排就ok了。

本節整體介紹圖像檢索概念及實現技術，下一節將介紹Faiss庫的使用、構建基於CLIP模型的圖像檢索演算法、基於Flask部署圖像檢索系統等。