原標題 Detecting image similarity using Spark, LSH and TensorFlow，作者為 Andrey Gusev(Pinterest 工程師，內容質量分析師)。

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

簡介

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

 

 

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

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

嵌入和 LSH 對象

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

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

批量 LSH 搜索

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

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

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

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

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

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

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

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

使用遷移學習的候選選擇

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

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

結論

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

欲了解更多關于這個問題的信息，請看我在 Spark+AI Summit 2018 的演講。https://vimeo.com/274629687

致謝：感謝以下團隊成員對本項目的所有貢獻：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

標簽： seo 搜索 網絡

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