端上的圖像相似度演算法選型

05-01

概述

電商場景中，賣家為獲取流量，常常出現重複鋪貨現象，當用戶發布上傳圖像或視頻時，在客戶端進行圖像特徵提取和指紋生成，再將其上傳至雲端指紋庫對比後，找出相似圖片，杜絕重複鋪貨造成的計算及存儲資源浪費。

該方法基於圖像相似度計算，可廣泛應用於安全、版權保護、電商等領域。

摘要

端上的圖像相似度計算與傳統圖像相似度計算相比，對計算複雜度及檢索效率有更高的要求。本文通過設計實驗，對比三類圖像相似度計算方法：感知哈希演算法、基於局部不變性的圖像相似度匹配演算法以及基於卷積神經網路的圖像相似度演算法，權衡其在計算複雜度及檢索效率方面的優劣，最終選取 Hessian Affine進行特徵提取，SIFT特徵描述生成指紋，作為端上的圖像相似度計算模型。

關鍵詞：圖像相似度計算、特徵提取、計算複雜度、檢索效率

引言

圖像相似度計算在當前的雲計算處理方式，會將客戶端數據上傳至雲端，進行圖像、視頻檢索相似度計算等一系列複雜邏輯處理後將結果反饋給終端，雖然在計算能力上雲端優勢明顯，但該方式同時存在嚴重的存儲、計算資源及流量的浪費且無法滿足實時性要求。

隨著手機計算能力的提升，一種顯而易見的方式是將部分數據在客戶端進行處理後，再將有價值的數據上傳雲端存儲及進一步處理。對於電商場景中的重複鋪貨現象，可在用戶發布上傳圖像、視頻時，在客戶端進行圖像相似度計算，做到實時反饋，對於重複圖像及視頻不進行雲端存儲，避免了存儲及計算資源的浪費。

圖像檢索演算法的基本步驟包括特徵提取、指紋生成和相似度匹配。業界常用的圖像相似度計算方法大致分為三類，傳統的感知哈希演算法、基於局部不變性的圖像相似度匹配演算法以及利用深度學習演算法進行的圖像相似度計算方法。

1．傳統的hash演算法

自2011年百度藉助TinEye發布百度識圖後不久，google發布了類似的以圖搜圖圖片搜索服務，「感知哈希演算法」在圖像搜索過程中發揮了重要作用。大致流程如下：

1.1感知哈希演算法理論簡介：

1.1.1均值hash:

通過對原始圖像進行壓縮（8*8）和灰度處理後計算壓縮後的圖像像素均值，用8*8圖像的64個像素與均值對比，大於均值為1，小於均值為0，得到得64位二進位編碼即為原圖像的ahash值。演算法速度快，但精確度較低。

1.1.2差異hash：

與均值hash相比，差異hash同樣要進行圖像壓縮和灰度處理，然後用每行的前一個像素與後一個像素對比，大於為1，小於為0，來生成指紋信息。演算法精確度較高，速度較快。

1.1.3感知hash：

通過對原始圖像進行壓縮（32*32）和灰度處理後計算壓縮，對其進行離散餘弦變換後，用32*32圖像的前8*8像素計算均值，8*8像素值大於均值為1，小於均值為0，得到64位指紋信息為原始圖像的phash值。演算法精準度較高，速度較差。

根據以上三種演算法可計算出兩張圖像響應的hash值，利用兩張圖像hash值得漢明距離，可判別出其相似程度，其中漢明距離越大，相似度越低，漢明距離越小，相似度越高。

1.2各個演算法之間的抗干擾能力對比

從視頻內容中選取兩組測試集，通過設計抗干擾能力實驗，對三種經典感知哈希演算法進行對比。

測試集1：

結果對比

測試集2

結果對比

通過實驗結果發現Hash在圖像相似度計算上，準確度較低，無法滿足實際業務需求。

2．利用卷積神經網路計算圖片相似度

2.1 端到端的方式

利用卷積神經網路計算相似度時，一種方法是直接採用端到端的方式，利用卷積層提取兩張圖片的特徵，再用全連接層輸出兩張圖片的「匹配度」。可參考[1] 2015年CVPR文章：《Learning

to Compare Image Patches via Convolutional Neural Networks》，相關中文解釋可參考[2] ：http://blog.csdn.net/hjimce/article/details/50098483

該方法對於少量圖像相似度計算優勢明顯，但不適用於從大量圖像中進行相似度匹配的場景，如視頻檢索。通常，視頻檢索大致步驟如下：

假設視頻庫中的存量視頻有1萬個，每個視頻抽取10張圖片，則幀庫有10萬張圖片，一次視頻查詢需要的比對次數為：10 x 100000 = 100萬次。

因此，儘管該方法對於圖像相似度計算有較高的準確性，但在進行視頻檢索時計算量過大。

2.2 提取中間產物方式

由於卷積操作的本質即為特徵提取，卷積層輸出的矩陣天然代表各種特徵，

通過對兩張圖片的特徵矩陣進行相減，計算差值平方和（或者其他方式）得到的數值作為兩張圖片的相似度判斷依據，即為利用卷積神經網路進行圖像相似度計算的第二種方式。

利用預訓練好的VGG16模型來做測試，網路結構如下（不帶全連接層）：

以block5_pool 輸出的結果做為目標產物（也可以用其它層），可以看到這一層輸出的是形狀為(7,7,512) 的矩陣,我們先用一組圖片（來源網路）做測試，來驗證輸出的結果是否大致符合預期：

以上六張測試圖片分別為：原圖、加少量文字、修改少量底部、底部裁剪、修改底部一半、完全不同的另一張圖片。對每張圖片用卷積模型計算得到

7x7x512 形狀的數組後，分別計算第一張圖片與後面五張圖片的特徵數組差值的平方和，並將結果歸一化處理以方便觀察，結果如下：

Diff 1 - 2: 2 Diff 1 - 3: 128 Diff 1 - 4: 182 Diff 1 - 5: 226 Diff 1 - 6: 377

從觀測結果中可以看出，第一張圖片與其後的圖片差異越來越大的。並且2和377 這兩個值代表非常相似和完全不同的圖片，具有一定辨識度。

進一步設計實驗，用視頻測試裁剪、加字幕、亮度調整、旋轉、以及完全不一樣的另一個視頻等抗干擾能力。

針對視頻的diff計算方式為：每個視頻每隔1秒抽一幀圖片，循環比對兩個視頻每個對應位置的圖片幀，計算差異值，最後除以幀數得到平均差異。對於兩個幀數不一致的情況，以較少幀為準，多出來的幀不處理。圖片間的差異值計算方式同上，結果如下：

Diff 0 - 1: 6

Diff 0 - 2: 4

Diff 0 - 3: 2

Diff 0 - 4: 22

Diff 0 - 5: 26

從實驗結果可以看出，對於裁剪、字幕、亮度調整的情況，差異值都在同一個數量級上，明顯小於不同視頻的情況，但是對於旋轉的情況，該方法無效。

3．基於局部不變特徵的相似度匹配演算法

除了基於哈希和基於卷積神經網路的相似度匹配演算法外，局部特徵檢測演算法在相似度計算、圖像檢索、物體識別等領域具有重要意義。相對於像素級的全局特徵，局部特徵在描述圖像特徵時更加靈活，其中SIFT（Scale-invariant feature transform）是比較常用的，具有較好的尺度不變性，即使改變旋轉角度或者拍攝角度，仍然能夠得到較好的檢測效果。

3.1抗干擾能力測試

用opencv+python，對測試圖片提取SIFT特徵：

進一步測試同樣的裁剪、旋轉等情況的特徵點匹配情況：

裁剪：

字幕+改變大小：

亮度調整：

旋轉90度：

不同視頻：

從測試結果上看，SIFT做特徵檢測具有良好的抗干擾能力。

3.2 檢索效率測試

初步確定採用局部不變特徵來做特徵提取後，需要做進一步的測試：搭建測試集，構建特徵提取、檢索系統，以測試準確率、召回率等指標。通過參考2017 年Araujo 和 Bernd

Girod的論文：《Large-Scale Video Retrieval Using Image

Queries》，基於其工程進行測試。

數據集準備：

1.圖片庫：取線上1000個視頻，對每個視頻每隔1秒抽一張視頻幀圖片，作為總圖片庫。

2.待查詢圖片：定義7種圖片變換方式：旋轉、拉伸、調整亮度、裁剪、加字幕、無處理，每種變換生成100個樣本。每個樣本的生成方式為：從1000個視頻里隨機選取一個視頻，並從所有圖片幀里隨機取一幀。這樣總共得到700個待查詢圖片。

局部特徵提取包含兩部分內容：特徵點檢測和特徵點描述。

3.2.1 SIFT特徵提取+SIFT描述子

對所有的庫存圖片以及待查詢圖片用SIFT提取特徵，並利用特徵從檢索庫里檢索700個測試樣本，計算召回率和準確率如下：

結果顯示準確率較低，通過觀察錯誤結果發現，部分圖片提取到的特徵數目較少，甚至只有個位數，而正常圖片能達到幾百到上千個特徵點，特徵點缺失會導致檢索時易匹配到錯誤的樣本。通過設置「最低樣本數」限制，當樣本數大於閾值時，認為其查詢結果「可信」。

經測試，將「最低樣本數」閾值定為30，並加入「排除率」指標，表示未達到最低樣本數，該查詢記錄不可信。將特徵數太少的樣本排除後，再次測試結果如下：

結果顯示在增加了「最低樣本數」和「排除率」指標後，準確率大幅度提升，但仍有20% 左右的排除率，即有五分之一的查詢是沒有返回可信結果的。

3.2.2 Hessian Affine特徵提取+SIFT描述子

為進一步提升準確率，參考[4]工程描述，將SIFT特徵點檢測換成Hessian-Affine特徵檢測會有更好的效果，即先用Hessian-Affine檢測特徵點，後用SIFT描述子描述特徵。換用Hessian-Affine後，測試結果如下；

結果顯示，召回率和準確率均有所提升，且排除率降至4%。

4. 結論

通過設計實驗測試結果發現，基於局部不變特徵做相似度計算具有良好的抗干擾能力，準確度優於傳統感知哈希演算法，對旋轉不變性的支持優於卷積神經網路。最終權衡計算複雜度和檢索效率，在端上選取Hessian-Affine做特徵點檢測，SIFT做描述子的方式進行圖像相似度計算。

5. 趨勢展望

儘管基於局部特徵不變性的圖像相似度計算在抗干擾能力及計算複雜度上佔優，但僅能表達圖像淺層特性，而卷積神經網路具有多層次語義表達能力，不同層所提取的圖像特徵具有不同含義，低層次表達角點特徵，中間層聚合角點特徵表達物體部件，高層進一步表達整個物體，選擇不同卷積層會提取出不同層次的特徵。在計算複雜度及檢索效率高要求的客戶端將局部特徵提取與卷積神經網路相結合互相彌補不足，突出優勢，可能會帶來更好的效果，未來將進一步探索。

參考：

[1] 2015 CVPR《Learning to Compare Image Patches via

Convolutional Neural Networks》

[2] http://blog.csdn.net/hjimce/article/details/50098483

[3] Araujo, A. and Girod, B 《Large-Scale Video Retrieval Using Image

Queries》2017

[4] https://github.com/andrefaraujo/videosearch.

http://weixin.qq.com/r/Pi4nIyXEpO3YKWFAb3u6 (二維碼自動識別)