原標(biāo)題 Detecting image similarity using Spark, LSH and TensorFlow，作者為 Andrey Gusev(Pinterest 工程師，內(nèi)容質(zhì)量分析師)。

作為一個(gè)視覺數(shù)據(jù)處理平臺(tái)，擁有從海量圖片中學(xué)習(xí)并理解其內(nèi)容的能力是非常重要的。為了檢測(cè)幾近重復(fù)的相似圖片，我們使用了一套基于 Spark 和 TensorFlow 的數(shù)據(jù)流處理系統(tǒng)——NearDup。這套系統(tǒng)的核心由一個(gè)使用 Spark 實(shí)現(xiàn)的批量化 LSH(locality-sensitive hashing，局部敏感哈希)搜索器和一個(gè)基于 TensorFlow 的分類器構(gòu)成。這個(gè)數(shù)據(jù)流處理系統(tǒng)每天能夠比較上億個(gè)分析對(duì)象，并漸進(jìn)式地完成各個(gè)圖像類別的信息更新。在本文中，我們將講解如何使用這項(xiàng)技術(shù)更好地理解海量圖片內(nèi)容，從而使得我們產(chǎn)品前端界面的推薦內(nèi)容和搜索結(jié)果具有更高的信息準(zhǔn)確性、更大的數(shù)據(jù)密度。

簡(jiǎn)介

我們將我們圖片庫(kù)中的所有圖片劃分為不同的圖片類，每一類都由幾近相同(以人類觀察員的判斷為標(biāo)準(zhǔn))的圖片組成。這種分類標(biāo)準(zhǔn)有一定的主觀性，為了給你一個(gè)感性認(rèn)識(shí)，下圖展示了一些按照 NearDup 閾值進(jìn)行圖片分類的例子。注意，這些相似圖片不一定來自同一圖像源(參見右下圖)，也不一定有相同的背景(參見左下圖)。同時(shí)，圖像中可能包含一定的幾何扭曲(參見左上圖)，或者旋轉(zhuǎn)、剪切和翻轉(zhuǎn)變化(見中心圖和右上圖)。

 

 

為圖片庫(kù)中的所有圖片進(jìn)行分類與劃分的過程在數(shù)學(xué)上無法進(jìn)行嚴(yán)格定義與求解，這是因?yàn)樵?NearDup 系統(tǒng)中，圖片之間的關(guān)系不具有傳遞性和相等性。為了說明這一點(diǎn)，我們可以想象將一張「貓」的圖片通過 1000 步慢慢地形變?yōu)橐粡垺腹贰沟膱D片的過程。容易推斷，每一步微小形變前后的兩張圖片的相似度都將落入 NearDup 的閾值，從而將它們判斷為「相似」圖片。然而，究竟該將這一串前后相似的圖片序列劃分為哪幾類?貓類，狗類，還是貓-狗類?為了解決這一問題，我們將問題模型轉(zhuǎn)化為圖：圖的節(jié)點(diǎn)代表圖片，邊代表相應(yīng)圖片間的相似度。隨后我們結(jié)合傳遞閉包法( transitive closure )和貪婪 k-cut 算法來最小化圖的 k-cut 劃分，從而近似求解整個(gè)圖片庫(kù)的最優(yōu)劃分。

使用批量化 LSH 進(jìn)行數(shù)據(jù)預(yù)處理

嵌入和 LSH 對(duì)象

為了理解圖片內(nèi)容，我們將圖片轉(zhuǎn)換到一個(gè)嵌入向量空間(embedded vector space)中。這些圖嵌入向量是圖片的一種高維向量表示，能夠抓取圖片的視覺和語(yǔ)義相似性。它們一般通過神經(jīng)網(wǎng)絡(luò)架構(gòu)如 VGG16 或 Inception 等處理生成。為了在 NearDup 系統(tǒng)中處理圖片關(guān)系并對(duì)圖片庫(kù)進(jìn)行分類，我們每天要比較幾千萬張新圖片，并將它們分類到上億個(gè)圖片類別中。如果沒有優(yōu)化措施，如此大規(guī)模的近鄰搜索(nearest neighbor search)問題的時(shí)間復(fù)雜度為平方(quadratic)復(fù)雜度，相應(yīng)的計(jì)算時(shí)間將正比于甚至超過 10 個(gè) quadrillion 秒(1 后面 16 個(gè) 0!)。為此，我們通過將圖嵌入向量進(jìn)一步縮減為 LSH 對(duì)象的方法，顯著縮小了問題規(guī)模，降低了處理難度。

LSH 是一種先進(jìn)的數(shù)據(jù)降維技術(shù)，降維前后數(shù)據(jù)點(diǎn)之間的距離關(guān)系保持不變。原向量空間首先通過隨機(jī)投影法(random projection)和位抽樣 LSH(bit sampling LSH)法進(jìn)行一定的降維。隨后，我們繼續(xù)將所得到的向量位分組為多個(gè) LSH 對(duì)象，分組過程有效地權(quán)衡了檢測(cè)準(zhǔn)確率和計(jì)算時(shí)間這一矛盾體。分組越精細(xì)，進(jìn)行最近鄰搜索的計(jì)算復(fù)雜度將越高，但檢測(cè)準(zhǔn)確率也將越高。這里，我們使用 LSH 對(duì)象之間的 Jaccard 重合度來近似表示原向量空間中相應(yīng)向量間的余弦相似度。

批量 LSH 搜索

當(dāng)所有圖片都用一組 LSH 對(duì)象表示之后，我們繼續(xù)為它們建立反向索引，并實(shí)現(xiàn)對(duì)所有圖片的批量查詢與搜索。從頂層看，我們通過函數(shù)式轉(zhuǎn)換法(functional transformation)、壓縮式反向索引與連接法(compressed inverted indexes and joins)等方法的結(jié)合，來實(shí)現(xiàn)對(duì)所有圖片的一次性批量查詢與比較。這個(gè)數(shù)據(jù)流處理過程是用 Spark 實(shí)現(xiàn)的，并需要借助一系列的優(yōu)化措施來進(jìn)一步保證這些海量數(shù)據(jù)能夠轉(zhuǎn)化到盡量簡(jiǎn)單有效地的LSH 對(duì)象空間中進(jìn)行處理。我們所使用到的主要優(yōu)化措施包括：

•  字典編碼( Dictionary encoding ) 使得所有數(shù)據(jù)都用具有最短寬度的數(shù)值進(jìn)行表示

•  可變字節(jié)編碼( Variable byte encoding ) 被用于所有的反向索引

•  索引切分( Index partitioning ) 提高了反向索引的平衡性

•  基于代價(jià)的優(yōu)化器( Cost-based optimizer ) 能夠檢測(cè)嵌入向量空間的密度，并計(jì)算最優(yōu)的運(yùn)行時(shí)參數(shù)

•  原始數(shù)據(jù)堆排( Primitive data packing ) 進(jìn)一步提高了內(nèi)存使用率

•  Jaccard 重合度計(jì)數(shù)( Jaccard overlap counting ) 基于低層次、高性能的數(shù)據(jù)收集實(shí)現(xiàn)

•  去堆化( Off heaping ) 減少了垃圾回收(GC)過載

使用遷移學(xué)習(xí)的候選選擇

批量化LSH是產(chǎn)生高查全率(召回率)同時(shí)又能最小化計(jì)算成本的一個(gè)很效果的方法。但是，它通常不會(huì)對(duì)候選項(xiàng)產(chǎn)生最優(yōu)的查準(zhǔn)率(準(zhǔn)確率)和排序。我們通過使用一個(gè)有監(jiān)督的分類器去挑選那些NearDups 認(rèn)為足夠相似的候選項(xiàng)。這個(gè)分類器是一個(gè)遷移學(xué)習(xí)在視覺嵌入上的例子。它使用了Tensorflow 前饋網(wǎng)絡(luò)和一個(gè) Adam 優(yōu)化器 。我們已經(jīng)在超過包含10億不同對(duì)圖像的樣本集中訓(xùn)練了分類器。訓(xùn)練集由決策樹分類器在SURF 視覺特征上的輸出得到，并進(jìn)行了幾何驗(yàn)證，然后用于NearDup 系統(tǒng)的先前迭代。為了提高學(xué)習(xí)和每一對(duì)圖像的收斂性，將 hamming 碼字節(jié)進(jìn)行異或運(yùn)算后輸入到輸入層。該分類器被調(diào)整到很高的準(zhǔn)確率并且在人類標(biāo)記的樣本上達(dá)到了 99% 以上準(zhǔn)確率。

SparkContext 也可以對(duì)訓(xùn)練過的網(wǎng)絡(luò)進(jìn)行推斷。使用 mapPartitions 和分組范式，我們可以使用預(yù)定義好尺寸的大批數(shù)據(jù)去有效地向量化和減少開銷。在一個(gè)擁有1000萬個(gè)參數(shù)的網(wǎng)絡(luò)中，我們?cè)谝粋�(gè)r3.8xlarge 的機(jī)器集群上實(shí)現(xiàn)了平均2ms進(jìn)行一個(gè)預(yù)測(cè)的速率。

結(jié)論

NearDup 檢測(cè)需要進(jìn)行計(jì)算代價(jià)很高的兩兩比較。通過在Spark 中使用批處理LSH實(shí)現(xiàn)，我們通過跳過不太相似的圖像對(duì)大大降低了計(jì)算的復(fù)雜度。Spark-based 的實(shí)現(xiàn)結(jié)合了高效的工作負(fù)載分配和低層次的優(yōu)化，以最小化內(nèi)存和CPU占用。隨后的調(diào)優(yōu)步驟使用了一個(gè)有監(jiān)督的前饋網(wǎng)絡(luò)來選擇和排序高于NearDup 相似性閾值的圖相對(duì)。Spark 和Tensorflow 的推斷結(jié)合使用了分布式計(jì)算和每個(gè)內(nèi)核矢量化的最佳特性，實(shí)現(xiàn)了高吞吐量和低延遲的預(yù)測(cè)。然后，將這兩個(gè)步驟的結(jié)果用于集群圖像，每天幫助提供數(shù)百億的搜索結(jié)果和在Pinterest 上的推薦。

欲了解更多關(guān)于這個(gè)問題的信息，請(qǐng)看我在 Spark+AI Summit 2018 的演講。https://vimeo.com/274629687

致謝：感謝以下團(tuán)隊(duì)成員對(duì)本項(xiàng)目的所有貢獻(xiàn)：Jiajing Xu, Vitaliy Kulikov, Jooseong Kim, Peter John Daoud, Andrew Zhai, Matthew Fang, Kevin Lau, Jacob Hanger, Zhuoyuan Li and Chao Wang

原文鏈接：https://medium.com/@Pinterest_Engineering/detecting-image-similarity-using-spark-lsh-and-tensorflow-618636afc939

標(biāo)簽： seo 搜索 網(wǎng)絡(luò)

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。