基于內容的商品圖像檢索技術與系統研究

李燦

提出了一種新的基于商品圖像的檢索系統，充分利用當前學術界的一些高效算法，包括基于Hadoop平臺的大數據處理技術，基于E2LSH的高維數據近鄰查找技術，基于圖像全局特征提取的GIST技術以及基于深度學習的卷積神經網絡技術CNN。緊密結合這些新技術，在基于商品圖像的檢索方面取得了較好的檢索效果。

1 引言

基于內容的商品圖像檢索作為移動互聯網中一種新興的購物方式和商品推薦方式，目前仍然處于研發階段。相比于普通的基于內容的圖像檢索（如Google識圖、百度識圖等），它主要側重于電商平臺的商品圖像檢索和廣告推薦。為了使其能夠應用到商業平臺并且為人們提供更加便捷的購物方式，這就對基于內容的圖像檢索提出了更高的要求。因為檢索結果不僅要與被檢索商品圖像非常相似，而且要與被檢索商品圖像同屬于一個類別。如用戶希望查詢相似的衣服，那么反饋給用戶的檢索結果只能是與用戶查詢圖像相似的衣服類圖像?，F在是信息爆炸的時代，像阿里巴巴、京東以及亞馬遜等大的電商平臺同樣也面臨著日益增長的海量商品圖像數據以及高訪問量所帶來的壓力，顯然傳統的基于集中式的數據處理方式很難滿足這方面的需求。而在大數據處理方面，開源的Hadoop框架是目前非常流行的分布式并行計算框架。因此，將其應用在圖像數據處理方面是一個很好的選擇。

位置敏感的哈希算法（Locality Sensitive Hashing，LSH）[1]是解決高維數據近似最近鄰檢索算法。基于內容的圖像檢索方法往往是將提取圖像的內容特征，如紋理、顏色、形狀、輪廓等轉化成一個高維向量，通過檢索相似的高維向量來進行圖像匹配。因此，將LSH應用在基于內容的圖像檢索方面也是目前的一個研究熱點。

基于內容的圖像檢索同樣也存在自身的局限性，那就是太依賴圖像的特征提取，圖像特征提取的好壞會直接影響查詢的正確率。目前雖然已經有比較多的圖像特征提取算法被提出，但這方面的提取算法依然處于發展階段。而基于深度學習的圖像識別算法，如卷積神經網絡（CNN）[2]在圖像識別準確率上是非常高的。因此，如果將其和一般的基于內容的圖像檢索算法相結合，過濾掉一些非同一類別的候選結果，這樣可以大大提高用戶檢索的準確性。

基于以上原因，提出了一種新的基于內容的商品圖像檢索技術及系統，并實現了基于Hadoop[3]大數據處理框架的圖像檢索算法。在圖像特征提取方面選取經典的GIST[4]圖像特征提取算法，在圖像檢索上選取E2LSH[5]算法，而在候選結果集的過濾上選取開源的深度學習處理框架Caffe[6]提供的CNNs圖像識別算法。

2 總體框架

2.1 Hadoop框架

Hadoop是Apache共享出的一個開源的分布式計算基礎架構。在該平臺上提交上來的計算任務被稱之為“Job”。而這些“Job”又會被分割為一個個的“任務（Task）”。通過將這些分割出來的“Task”分發到不同的集群節點中實現分布式并行計算，可以大大地提高“Job”的處理速度。而HDFS則是Hadoop提供的一個分布式文件系統，用于數據的存儲。在數據處理方面提供了MapReduce的編程模型。

（1）分布式文件系統HDFS

HDFS是Hadoop的一個分布式文件系統，由于它具有存儲容量大、容錯能力強、吞吐量高等特點同樣也得到了一些其它的分布式計算平臺的支持。HDFS主要采用主/從（Master/Slave）的結構模型，在HDFS中有兩個非常重要的組成部分，一個是主要負責整個分布式文件系統的命名空間，存儲文件的元數據和集群中各個節點與數據塊之間的映射。通過“心跳機制”監控著集群中各個節點的存儲情況，將其稱之為“NameNode”節點；另一個是“DataNode”，它主要負責存儲用戶數據，數據在這些節點中均以塊的形式進行存儲。

在HDFS中，當用戶提交存儲數據之后，這些數據均會被劃分成塊的形式，然后分發保存在集群中不同的“DataNode”中。

（2）MapReduce編程模型

MapReduce是Hadoop提供的處理海量數據的分布式編程模型和并行計算框架。在MapReduce編程模型中，用戶只需要將主要精力放在Map（）方法和Reduce（）方法的設計上，同時Map階段將以塊形式輸入的數據按照的方式進行處理，然后轉化成新的鍵值對的形式并進行輸出。如果有Shuffle階段，那么Map階段輸出的數據在輸出之前會先合并再按照鍵值對的形式輸出，然后將Map階段的結果作為Reduce（）函數的輸入，通過Reduce（）函數的計算，最終生成鍵值對并保存到結果文件中。

在MapReduce模型中同樣運用到了“分而治之”的思想。其中，通過JobTracker將用戶提交的作業分割成多個任務并分配給TaskTracker執行。MapReduce框架采用“移動計算優于移動數據”的理念，計算的執行應該盡量存儲在有相關數據的DateNode中，這樣做可以節省寬帶資源。

2.2 圖像的全局特征GIST

本系統所處理的數據都是一些背景比較簡單的商品圖像，因此本系統選用提取圖像全局特征的方式來表征圖像，即圖像的GIST特征。這種方式所描述的是圖像的一些比較宏觀的信息，提取出來的GIST特征向量主要由圖像的開放度、粗糙度、自然度、膨脹度和險峻度5個維度信息組成，并不考慮圖像的一些局部特征信息，如SIFT算法需要提取非常多的圖像局部特征信息。

2.3 LSH

令q∈B（o，s）={q∈Rd|‖o，q‖≤s}記作以數據對象o∈D為中心，半徑為s的超球體。因此，LSH函數定義如下：

其中，P[h（o）=h（q）]表示對象o和q落入相同桶中的概率，c>1和p1>p2。此外，組合的哈希函數表示成g=（h1， … ， hk），其中h1， …， hk是從LSH哈希函數族中隨機抽取的k個距離敏感函數。根據文獻[18]，一個用以構造適用于l2距離度量的LSH函數家族的形式如下：

其中，o為數據對象o∈Rd的向量表示；a為每個維度均符合隨機分布，從標準正態分布中抽取的d維向量；w是一個常數代表，劃分出桶的寬度；b是隨機地從均勻分布[0， w）中抽取的實數。

一個LSH函數ha，b（o）哈希過程如下：首先，把數據對象o投影到以向量a表示的一維空間上；再把o的投影移動b的長度；最后把a以寬度w劃分成多個區間；返回o經過投影后所得的桶號。令s=‖o1，o2‖，表示對于任意兩個數據對象o1和o2的距離，則o1和o2在LSH函數ha，b（o）作用下產生碰撞的概率p（s）為：

對于給定的桶寬w，碰撞概率p（s）隨著s的增大而減小。因此，哈希函數ha，b是（s， cs， p1， p2）敏感的，其中p1=p（s），p2=p（cs）。當s=1時，該函數為（1， c， p1， p2）敏感，且p1=p（1），p2=p（c）[7]。

2.4 卷積神經網絡

卷積神經網絡是人工神經網絡的一種。與其它神經網絡不同的是，這種網絡采用的是權值共享的方式，與生物神經網絡更相似。通過這種設計不僅可以使模型的復雜度降低，而且使網絡權值的數量也大大地減少。在卷積神經網絡中，可以直接對圖像數據進行處理，而無需像傳統神經網絡算法那樣對數據進行特征提取和重新構建，往往這些過程需要耗費非常大的開銷。因此，在卷積神經網絡中，相比于傳統的神經網絡，模型的訓練速度是很快的。通過卷積神經網絡中多層感知器的構造方式可以對一些結構平移的圖像、比例不同的圖像或者圖像內容有傾斜的圖像都有較高的容忍能力。

CNNs利用權值共享的方式減少需要學習的參數數目，和一般前向BP[8]算法相比，使得訓練速度和準確度得到了極大的提高。CNNs作為一個深度學習算法，可以使數據的預處理開銷達到最小化。在該算法中，作為層級結構的最低層的輸入只是圖像的一小部分（即局部感受區域或者視野感受子），經過處理后的信息再傳輸到更深的層次，每層會通有濾波器來取得上層輸入的觀測數據特征。

圖1展示了在卷積神經網絡中，網絡組成以及圖像數據在各個層次網絡中的轉化，其中C1層稱之為特征映射層。在特征映射層中，圖像數據會以每5個像素為一組進行求和以及加上權值和偏置，然后通過符號函數得到S1層，即濾波層。通過對S1層進行濾波得到C2層。然后通過重復之間的處理方式一直到得到S4層。最終，這些像素值被光柵化并通過BP全連接網絡得到最終的輸出。

卷積過程如圖2所示，包括用可訓練的濾波器fx對輸入的圖像進行卷積，并且通過與偏置bx求和，得到卷積層Cx。在子采樣過程中，通過對每4個像素的鄰域求和轉化成一個像素，然后通過與標量Wx+1進行運算，再加上bx+1偏置，最后通過一個符號函數，產生一個大概縮小四倍的特征映射圖Sx+1。

3 系統流程圖及各個部分的實現

圖3展示了本系統中索引文件的建立過程和用戶在線查詢過程的流程圖。整個系統劃分為兩個部分。首先是離線建立索引階段；其次便是在線查詢階段。這也與一般的基于Web的服務相同。從流程圖也可知，整個系統的核心分為以下幾個部分：一是基于GIST圖像特征的E2LSH算法和Hadoop平臺索引文件的建立；二是CNN算法的實現。下面將從這兩個方面對該系統進行介紹。

3.2 基于圖像GIST特征的E2LSH算法

圖像的GIST特征是圖像的全局特征信息，并不像SIFT特征那樣具有多樣性。一幅圖像只能提取出一個GIST特征向量，并且以高維特征向量（維數都超過10維）來表示。由于“維度災難”的原因，并不適合選用KD-tree、R-tree等樹形索引結構來對這些高維數據進行檢索。

E2LSH算法是近似最近鄰檢索算法，并且在維度很高的情況下比一般的樹形結構的檢索算法效果更加明顯。本算法將其應用到了基于圖像GIST特征的檢索上。基于圖像的GIST特征的E2LSH算法主要包括兩個階段，分別是創建索引文件階段和離線圖像檢索階段。

（1）創建索引文件階段

由于本算法是基于Hadoop分布式并行處理框架，所以在創建索引文件階段需要首先將圖庫圖像數據集存儲到Hadoop分布式文件系統HDFS中，然后對這些圖像進行GIST特征提取，提取出來的GIST特征向量保存到HDFS文件上。由于數據量較大，這些數據會以塊的形式被單獨保存到各個節點中。

特征向量的數據格式為<圖像名， 高維特征向量>的鍵值對形式。每一行保存一幅圖像的圖像名和特征向量對。圖像名不僅包含圖像的文件名同時也包含圖像在HDFS文件系統中的邏輯路徑，方便后續階段取出圖像源文件。高維特征向量則使各個維度之間以空格的形式保存。同時圖像與特征向量之間以“，”進行標識。

將這些數據保存在HDFS上后，便可以用E2LSH位置敏感的哈希函數對這些特征向量建立索引。通過將圖像GIST高維特征哈希到相同的哈希桶中，并保存到以桶號所代表的文件中，使得圖像集中原本比較相似的圖像保存到一起。

經過LSH函數后高維GIST特征向量變成一維哈希桶號，但是準確率和查全率并不高。因此，為了提高算法的準確率和查全率，E2LSH算法對位置敏感的哈希函數的使用進行了改變。將每一幅圖像改為使用由k個h（o）組成的g（o）函數，其中g（o）=。由于單個h（o）在映射的時候會有較高的概率使得原本不相近的GIST向量映射成相同值，即會降低算法的準確率。而使用多個h（o）函數組成的g（o）函數可以使算法的準確率得到提高，即常說的“AND”過程。

在單個g（o）中，每幅圖像被映射成一個k維的組合哈希桶號，這可能會使很多原本相似的圖像得到不相近的k維索引值，從而使得算法的查全率降低。為了解決這個問題，可以通過使用L個g（o），即G=（g1， g2， …， gL）來創建L個索引表。這樣在查詢的時候通過多個索引表之間的“OR”操作可以避免“AND”操作所導致的假陰性增大的問題。

其中每一行保存著一個k維索引值代表“AND”之后的組合哈希桶號以及其中所保存的圖像名列表（其中圖像名代表的是圖像的絕對路徑）。

（2）基于開源Caffe框架CNNs的實現

本系統在圖像識別上采用的是目前非常流行的伯克利實驗室的Caffe開源深度學習框架，即6層的深度學習算法CNN。其中訓練圖片在各個層次中的轉化如圖4所示。

圖4展示了在CNN算法中經過各個層次的特征提取C層或者濾波S層后輸出的圖像數據。其中每幅圖片只是對結果中的一部分進行展示。如第一層特征提取層的輸出C1有256個，只顯示了前36個特征提取進行顯示。一層過濾器S1有256個，其中每個尺寸為5×5×48像素，只顯示前48個過濾器，每個通道分別顯示，使每個過濾器是一排。其中第五層為采用BP算法的全連接層。最終輸出結果用直方圖進行展示，如圖5所示。

最終的預測結果如圖6所示，其中橫軸坐標為類別（有1000個類別），按照相似圖表示成柱狀圖。

得到預測的類別圖后，取其中最相似的類別進行輸出，結果如表2所示：

4 實驗數據及結果

4.1 Hadoop分布式環境的部署

Hadoop部署在4臺Ubuntu12.04的Linux操作系統PC機上。其中，Hadoop的主服務器（即Master節點）運行NameNode、JobTracker進程；其余作為Hadoop的工作節點（即Slave節點），運行著DataNode和TaskTracker等進程。

4.2 實驗的圖像數據集以及開發工具

在圖像檢索中有很多評價方式，常見的評價測度包括查全率（Recall）和準確率（Precision），本文采用比較常用的評價測度方式。如對于一幅查詢圖像，根據檢索返回的結果的正確性將其標記為4種類型：假陽性FP（False Positive）、真陰性TN（True Negative）、真陽性TP（（True Positive）、假陰性FN（False Negative）。根據以上概念，可以得到Precision和Recall的計算公式定義為：

其中符號代表該項結果的數據個數，TP和FN的和是數據庫所有相關圖片的總數。其中，FP的含義是檢索判定為相似圖像，但實際上這些結果與查詢圖像卻并不相似；TP的含義是檢索為相似的圖像，實際上與查詢圖像也不相似；FN的含義是檢索為不相似圖像，但實際上這些結果與查詢圖像是相似的；TN的含義是檢索為不相似的圖像，實際上這些結果與查詢圖像的確不相似。

本文采用的三個實驗數據集分別來自：（1）ImageNet[9]：這是一個計算機視覺系統識別項目，是目前世界上圖像識別最大的數據庫，是美國哈佛的計算機科學家模擬人類的識別系統建立的。從中挑選出了具有商品圖片性質的1000幅圖片作為實驗數據集。（2）Flickr[10]：Flickr是目前世界上最好的線上相片管理和分享應用程式之一，從中挑選出了1000幅圖像作為實驗數據集。（3）來自于亞馬遜商城[11]收集的商品圖片2000幅。實驗圖片在選取過程中主要集中于鞋子、衣服、皮包、首飾等類別。

從實驗（1）和實驗（2）可以看出：k值越大，查準率普遍升高，其中Shoes的查準率由62%升到了86%，Leather Bag由85%升到100%；但是查準率提高的同時，查全率下降的也比較明顯，Clothes的查全率由66%下降到43%，Bag的查全率由55%降到29%；如果k值較小，查找到的圖片總數量會很多，但準確率會下降，因為其中不相似的圖片數量也會增多，而查全率會升高。

從實驗（1）和實驗（3）可以得出，隨著L值的減小，準確率和查全率都呈下降趨勢。因此，從上述實驗結果得出，L值和k值也不能很大，隨著L值的增大，雖然會使算法的查全率和準確率相應地提高但會使索引文件的數量增多，增加查詢時間的開銷；對于k值，隨著k增大，算法的準確率會提高，但又會降低算法的查全率。參數L值和k值的選取需要通過實驗進行優化。

5 結束語

本文主要研究了基于內容的商品圖像檢索系統并將其應用到了Hadoop分布式計算平臺上，詳細地描述了系統的實現以及所用到的核心技術。其中，基于Hadoop圖像GIST特征的E2LSH算法是檢索相似商品圖像的算法；基于Caffe的CNNs深度學習算法是開源高效的圖像識別算法。通過Hadoop的MapReduce編程模型實現了E2LSH算法，生成圖像的索引文件并保存在Hadoop的HDFS文件系統中。算法的實現主要分為兩個階段，一是創建索引文件階段，另一階段即為離線查詢階段。通過實驗對算法中所涉及的各個參數進行優化，本文進行了大量的實驗來測試本系統的效果，并對實驗結果進行了分析對比。

通過實驗可以發現，在圖像的檢索階段通過采用E2LSH的近似最近鄰檢索算法可以加快候選集的檢索速度，然后通過CNN的深度學習算法可以過濾掉候選集中和被檢索圖像不屬于同一個類別的圖像，從而大大提高了檢索的正確率。這也說明了該系統在基于內容的商品圖像檢索上的有效性。

參考文獻：

[1] Gionis A， Indyk P， Motwani R. Similarity Search in High Dimensions via Hashing[A]. Proc of the 25th International Conference on Very Large Data Bases， 1999： 518-529.

[2] Roska T， Chua L O. The CNN universal machine： an analogic array computer[J]. IEEE Transactions on Circuits & Systems II Analog & Digital Signal Processing， 1993，40（3）： 163-173.

[3] Chansler R， Sunnyvale Y. The Hadoop Distributed File System[J]. IEEE Symposium on Mass Storage Systems & Technologies， 2010（11）： 1-10.

[4] Oliva A， Torralba A. Modeling the shape of the scene： A holistic representation of the spatial envelope[J]. International journal of computer vision， 2001，42（3）： 145-175.

[5] Datar M， Indyk P， Immorlica N， et al. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions[J]. SoCG， 2004（2）： 253-262.

[6] Sun Y， Wang X， Tang X. Deep learning face representation from predicting 10，000 classes[A]. Computer Vision and Pattern Recognition （CVPR）， 2014 IEEE Conference on IEEE， 2014： 1891-1898.

[7] Tao Yu fei， Yi Ke， Sheng Cheng， et al. Quality And Efficiency In High Dimensional Nearest Neighbor Search[A]. Proc of the 35th SIGMOD international conference on Management of data， 2009： 563-575.

[8] STUIVER M， REIMER P J， BARD E， et al. INTCAL98 radiocarbon age calibration， 24 000-0 cal BP[J]. Radiocarbon， 1998，40（3）： 1041-1083.

[9] Krizhevsky A， Sutskever I， Hinton G E. ImageNet classification with deep convolutional neural networks[J]. Advances in neural information processing systems， 2012（2）： 1097-1105.

[10] Sawant N， Li J， Wang J Z. Automatic image semantic interpretation using social action and tagging data[J]. Multimedia Tools & Applications， 2011，51（1）： 213-246.