以圖搜圖背后的技術(shù)，你了解嗎？

當(dāng)你看到一株未曾見(jiàn)過(guò)的植物，你可以打開(kāi)百度APP，拍照搜索，找到相關(guān)信息；當(dāng)你看到朋友穿了一件你特別喜歡的衣服，你也想買(mǎi)一件，你可以通過(guò)淘寶APP的拍立淘功能，找到商品；當(dāng)你到達(dá)一個(gè)陌生的地方，你可以通過(guò)微信APP對(duì)著當(dāng)?shù)氐慕謪^(qū)或者建筑物拍一張照片，來(lái)定位你的詳細(xì)位置。這背后都是強(qiáng)大的以圖搜圖技術(shù)。

以圖搜圖技術(shù)發(fā)展了許多年，從早期以圖搜圖的精度不盡如人意，到后來(lái)基于以圖搜圖技術(shù)開(kāi)發(fā)出非常多的改變用戶行為和提升效率的應(yīng)用，經(jīng)歷了不小于10年的發(fā)展，整體的技術(shù)方案、數(shù)據(jù)量級(jí)、工程架構(gòu)都進(jìn)行了多輪的迭代。當(dāng)前，各個(gè)大廠都在基于以圖搜圖技術(shù)來(lái)提供更好的產(chǎn)品和服務(wù)。我們希望在這篇文章中對(duì)以圖搜圖技術(shù)做一個(gè)全面的總結(jié)，主要包含以下幾個(gè)方面：

1. 以圖搜圖技術(shù)的通用框架；

2. 以圖搜圖技術(shù)迭代；

3. 以圖搜圖是工程+算法的結(jié)合，架構(gòu)演進(jìn)。

Part 1. 以圖搜圖技術(shù)的通用框架

在這一章，我們來(lái)介紹以圖搜圖技術(shù)的通用框架。在介紹以圖搜圖技術(shù)之前，我們來(lái)看任何一個(gè)搜索技術(shù)所擁有的基本組件。舉個(gè)例子，我們需要到圖書(shū)館查找一本書(shū)，需要幾個(gè)基本的要素：1. 圖書(shū)館（海量圖書(shū)）；2. 圖書(shū)的分類、書(shū)名或者作者（在圖書(shū)館的編碼體系下，這些信息的組合能夠唯一表示這一本書(shū)）；3. 圖書(shū)館的書(shū)需要按照一定的規(guī)律來(lái)布置（科目、難易程度、首字母、作者、年份等）；在有了這些基本的要素之外，只要圖書(shū)館有這本書(shū)，我們就能夠快速找到它；或者即便沒(méi)有某一本具體的書(shū)，我們也能夠查詢到與這本書(shū)有著相近內(nèi)容的書(shū)。

結(jié)合上面的例子，我們來(lái)看一個(gè)典型的以圖搜圖系統(tǒng)所擁有的基礎(chǔ)框架：

先來(lái)看offline部分，包括3個(gè)基本的要素：

01. 檢索圖片庫(kù)：這就相當(dāng)于上一個(gè)例子中的圖書(shū)，我們需要有一個(gè)足夠規(guī)模的圖片庫(kù)，比如淘寶的所有商品的圖片集合，比如百度圖片搜索中收集到的互聯(lián)網(wǎng)圖片數(shù)據(jù)集合。當(dāng)然，這里我們介紹的是一個(gè)靜態(tài)的圖片庫(kù)，在實(shí)際項(xiàng)目中，我們需要有能力來(lái)處理動(dòng)態(tài)變化的圖片數(shù)據(jù)庫(kù)。

02. 特征提?。哼@就相當(dāng)于上一個(gè)例子中圖書(shū)的作者、年份、科目等等，我們稱為圖片的特征。實(shí)際上，圖片的任何統(tǒng)計(jì)量都可以作為圖片的特征，甚至圖像的像素值本身通過(guò)歸一化之后也可以作為圖片的特征。在實(shí)際中，我們使用圖片的顏色分布、梯度變化統(tǒng)計(jì)量、紋理、BOW統(tǒng)計(jì)、底層/中層/高層語(yǔ)義特征等作為圖片的特征，非常豐富。

03. 檢索結(jié)構(gòu)：檢索結(jié)構(gòu)的唯一目的就是讓查找更快更準(zhǔn)。簡(jiǎn)單的，一一對(duì)比是最簡(jiǎn)單的查詢結(jié)構(gòu)，最準(zhǔn)，但是最慢；所以所有檢索結(jié)構(gòu)本質(zhì)上都是效率和精度的平衡。常見(jiàn)的，我們可以對(duì)數(shù)據(jù)集進(jìn)行聚類，把數(shù)據(jù)分成一堆一堆的，比對(duì)時(shí)先選擇相似的堆，然后在堆內(nèi)部再進(jìn)行細(xì)致的比對(duì)。而分堆的理念又可以通過(guò)樹(shù)結(jié)構(gòu)、Hash結(jié)構(gòu)、倒排索引、圖結(jié)構(gòu)等等來(lái)刻畫(huà)。

再來(lái)看online部分，其中特征提取和offline的特征提取需要保持高度的一致性，所以實(shí)際中我們通常使用一個(gè)單獨(dú)的特征服務(wù)器來(lái)提供特征提取服務(wù)。這里之所以將檢索結(jié)構(gòu)和檢索引擎分開(kāi)，主要是基于如下的考慮：檢索引擎需要應(yīng)對(duì)高并發(fā)等一些的工程方面的問(wèn)題，所以本質(zhì)上檢索引擎更傾向于工程架構(gòu)的優(yōu)化，而檢索結(jié)構(gòu)更傾向于檢索結(jié)構(gòu)算法方面的優(yōu)化；但實(shí)際上，二者是沒(méi)辦法完全拆分開(kāi)的。

以圖搜圖技術(shù)本質(zhì)上是尋找相似圖片，但兩張圖片是否相似有非常多的維度：

因此在很多時(shí)候，以圖搜圖技術(shù)需要根據(jù)不同的使用場(chǎng)景來(lái)選擇合適的技術(shù)方案，尤其是特征的選擇。產(chǎn)品層面，也層出不窮，可以參考下面的幾個(gè)鏈接：

The Best Image Search Engines on the Web

https://www.lifewire.com/where-to-find-images-online-3482427

The 7 Best Search Engines for Finding Free Images

https://www.sitepoint.com/7-best-search-engines-free-images/

Part 2. 以圖搜圖的技術(shù)迭代

這個(gè)部分我先打算介紹一下特征、檢索引擎各自都經(jīng)歷了哪些迭代，然后在以不同時(shí)段典型的工業(yè)界的使用方案來(lái)介紹以圖搜圖技術(shù)代際的迭代。

特征層面：

簡(jiǎn)單的，圖像的單通道、多通道的顏色直方圖可以作為一個(gè)簡(jiǎn)單的特征；進(jìn)一步顏色矩特征，圖像中任何的顏色分布都可以通過(guò)它的矩來(lái)表示。另外需要強(qiáng)調(diào)的局部特征是SIFT特征（參考：https://blog.csdn.net/abcjennifer/article/details/7639681），SURF特征，HOG特征等；當(dāng)有了局部特征之后，我們需要對(duì)局部特征進(jìn)行聚合，作為圖像的全局表示；將多個(gè)局部特征矢量聚合成一個(gè)統(tǒng)一維度的矢量表示的方法有：BOW、VLAD、Fisher Vector等等。

深度學(xué)習(xí)技術(shù)興起之后，基于深度學(xué)習(xí)的圖像特征開(kāi)始成為圖像檢索的主流。我們知道CNN網(wǎng)絡(luò)具有很多不同程度對(duì)圖像進(jìn)行抽象的layer，較低的層得到的是圖像的簡(jiǎn)單特征，而較高層得到的是圖像的語(yǔ)義相關(guān)的特征，不同層的特征在檢索層面精度有很大的區(qū)別，在Oxford Building數(shù)據(jù)集上，使用VGGNet進(jìn)行簡(jiǎn)單的測(cè)試，得到了如下的統(tǒng)計(jì)結(jié)果。

（參考：http://yongyuan.name/blog/layer-selection-and-finetune-for-cbir.html）

實(shí)際上，深度網(wǎng)絡(luò)最后的FC層同樣可以作為圖像的特征表示，當(dāng)使用FC作為特征時(shí)，網(wǎng)絡(luò)訓(xùn)練時(shí)使用的label對(duì)檢索的效果有較大的影響。理論上，label如果能夠提供更多的細(xì)粒度的信息，則學(xué)習(xí)到的FC特征則更能夠表達(dá)圖像的細(xì)粒度特征。

特征類型對(duì)檢索效果影響很大；但特征的學(xué)習(xí)方式，尤其是引入度量學(xué)習(xí)的思路之后，即便是同一個(gè)網(wǎng)絡(luò)的同一層特征，不同的訓(xùn)練方式對(duì)最后的精度也會(huì)有很大的影響。

比如Class weighted conv features

（參考：https://github.com/bikong2/retrieval-2017-cam）

分類loss和triplet loss結(jié)合：

引入更多監(jiān)督信息的學(xué)習(xí)：

以及通過(guò)KL散度來(lái)優(yōu)化：

其實(shí)通過(guò)不同的方式進(jìn)行網(wǎng)絡(luò)學(xué)習(xí)的優(yōu)化方式還有很多，這里大致總結(jié)幾個(gè)優(yōu)化的大致方向：

1. 引入更多的監(jiān)督信息；

2. 不同程度、維度的attention（包括層、channel、類等等）；

3. Triplet loss及其各種變種；

4. 不同的特征聚合方式。

檢索引擎：

檢索引擎方面，早期我們通過(guò)層次化的聚類來(lái)對(duì)數(shù)據(jù)分組，通過(guò)K-D Tree對(duì)數(shù)據(jù)進(jìn)行劃分，通過(guò)Hash對(duì)空間進(jìn)行劃分，通過(guò)倒排索引加速檢索的效率，通過(guò)PQ量化對(duì)更大規(guī)模的數(shù)據(jù)進(jìn)行二次方的劃分。參考：

?? 圖像檢索：再敘ANN Search

https://blog.csdn.net/qq_27245709/article/details/72393613

?? 圖像檢索：基于內(nèi)容的圖像檢索技術(shù)

https://yongyuan.name/blog/cbir-technique-summary.html

?? Product Quantization for Nearest Neighbor Search論文理解

https://blog.csdn.net/CHIERYU/article/details/50347735

層次化的聚類算法可以通過(guò)如下的圖片來(lái)表示：

通過(guò)聚類來(lái)減少檢索時(shí)比對(duì)的檢索時(shí)間。K-D Tree和Hash請(qǐng)參考下面的圖片。K-D Tree相對(duì)層次化聚類基本原理是一致的，不過(guò)聚類算法更多的是數(shù)據(jù)的劃分，但樹(shù)結(jié)構(gòu)的層次化劃分包含特征和數(shù)據(jù)的劃分兩方面。Hash方法，尤其是LSH（局部敏感哈希），則是同時(shí)在尋找特征的mapping和空間的劃分。

PQ量化本質(zhì)上是在特征和數(shù)據(jù)的兩個(gè)層面對(duì)數(shù)據(jù)集進(jìn)行量化，如下圖所示，特征向量本身是16*8=128維，通過(guò)特征層面的劃分，分成y1…y8總共8組特征；劃分之后，對(duì)每一組特征在全數(shù)據(jù)集上進(jìn)行聚類等量化手段，比如量化的長(zhǎng)度是8bits的01向量。最終得到的是8*8bits的01向量，壓縮比超高。

接下來(lái)，介紹兩代不同的以圖搜圖技術(shù)。

局部特征（如SIFT特征）+BOW+LSH的方案：

這種方案大致在2015年之前算是比較流行的框架，通常針對(duì)特殊的使用場(chǎng)景，在檢索基礎(chǔ)上可能還需要進(jìn)行細(xì)粒度的精排序。這個(gè)方案在10億以內(nèi)的數(shù)據(jù)量級(jí)上非常適用，當(dāng)然如果數(shù)量級(jí)更大，也是可以的，只是需要引入其他的檢索結(jié)構(gòu)。關(guān)于LSH，推薦使用一個(gè)開(kāi)源的工具包FALCONN：

https://github.com/FALCONN-LIB/FALCONN

CNN卷積特征+VLAD+PQ量化的方案：

這是目前比較主流的方案，卷積特征建議做多層特征的組合，PQ量化建議根據(jù)數(shù)據(jù)規(guī)模做密集的參數(shù)選擇，推薦使用Facebook開(kāi)源的工具包FAISS：

https://github.com/facebookresearch/faiss

當(dāng)然，卷積特征的學(xué)習(xí)方式的選擇層面，需要根據(jù)實(shí)際擁有的數(shù)據(jù)的標(biāo)簽信息來(lái)決策。有一些基于弱監(jiān)督學(xué)習(xí)的方案，也可以嘗試。

Part 3. 以圖搜圖是工程+算法的結(jié)合

架構(gòu)演進(jìn)

在這里，我們介紹一個(gè)理想狀態(tài)下的以圖搜圖架構(gòu)，需要嘗試去解決的幾個(gè)問(wèn)題：

1. 如何解決檢索庫(kù)動(dòng)態(tài)增加的問(wèn)題；

2. 如何解決全量的特征迭代的問(wèn)題，也就是說(shuō)query和database的特征需要同步；

3. 特征增強(qiáng)，在檢索結(jié)構(gòu)確定的情況下獲得更好的檢索效果；

4. 高并發(fā)低延遲。

以上只是一個(gè)簡(jiǎn)單的架構(gòu)示意圖，如果涉及到特征評(píng)價(jià)，檢索結(jié)構(gòu)評(píng)價(jià)，甚至其他的策略迭代等一系列的關(guān)于AB Test的需要，架構(gòu)層面需要進(jìn)行深度的優(yōu)化。

到這里基本上對(duì)以圖搜圖技術(shù)從特征、檢索結(jié)構(gòu)、架構(gòu)等層面進(jìn)行了一個(gè)基本的介紹。其實(shí)工業(yè)界的以圖搜圖產(chǎn)品或者說(shuō)引擎遠(yuǎn)比我寫(xiě)到的要復(fù)雜，如果有大家有興趣，建議研究以下幾個(gè)檢索系統(tǒng)的演進(jìn)：

阿里的拍立淘

百度的圖片搜索

谷歌的圖片搜索

Pinterest的商品搜索