基于哈希的圖像相似度算法比較研究

黃嘉恒，李曉偉，陳本輝，楊鄧奇

（大理大學數學與計算機學院，云南大理 671003）

圖片相似度檢測是對兩張或多張圖片的內容相似程度進行分析對比，或檢測某張圖片的內容是否包含在另一圖片內。圖片相似度比較被廣泛應用于基于圖片的搜索引擎、目標檢測、照片過濾、文獻查重等多個領域。

輸入圖片到搜索引擎可以檢索出搜索引擎數據庫中包含目標圖片的所有鏈接。通過提取目標照片特征來檢測照片中是否存在目標物體，實現圖片內容過濾、圖片篩選和分類。在網絡安全領域，通過對不雅圖片、不良圖片（如包含色情、反動標語等的圖片）進行采樣，提取不雅、不良圖片的指紋特征，檢測圖片中是否存在不雅、不良內容；將圖片相似度檢測算法應用于網關設備，可以實現基于圖片的互聯網不良內容檢測，凈化網絡環境。在生態保護領域，利用紅外相機對野生動物進行非入侵、無干擾、全天候的實時監控變得越來越受歡迎〔1〕。根據紅外相機的觸發機制，當動物經過紅外相機的鏡頭視野時會觸發相機自動拍攝一組連續的照片，實現對生態保護區野生動物的觀測、統計與研究〔2-3〕。但實際應用中，除了動物經過鏡頭外，鏡頭內的任何風吹草動也會觸發紅外相機自動拍攝而產生空照片。實際上，紅外監測拍攝到的照片中大部分是沒有捕獲到動物影像的空照片。Diaz等〔4〕所拍攝到的20萬張照片中，成功捕獲到動物的照片僅占1%；位于坦桑尼亞西北部的塞倫蓋蒂平原的320萬張紅外監測照片數據集中75%都是空照片〔5〕。當前生態學領域的研究者對紅外空照片的分揀都靠人工完成，存在工作效率低、人力成本高、易出錯等問題。利用照片相似度比較實現紅外空照片自動過濾可以節省大量的人力成本、提高工作效率。

本文研究基于哈希的圖像相似度檢測算法，通過對均值哈希（Average Hash，aHash）算法、感知哈希（Perceptual Hash，pHash）算法和差異值哈希（Deference Hash，dHash）算法進行分析，研究各算法在圖片相似度檢測方面的優缺點，并基于相同照片組對不同精度下3個圖像哈希算法的檢測精度和性能進行細粒度測試，為其他研究者選擇基于哈希的圖像相似度檢測算法提供理論依據和數據參考。

1 相關工作

圖像相似度比較被廣泛應用于圖像搜索、目標識別、照片過濾等領域。鄒承明等〔6〕基于顏色直方圖提出一種改進的圖形特征計算和相似度比較算法。潘楠等〔7〕基于SIFT算法計算圖片指紋特征，并根據相似度比較實現犯罪工具圖片快速溯源。郭儀權等〔8〕將圖像哈希算法應用于多目標跟蹤，利用圖像哈希算法計算圖像指紋，然后通過對比跟蹤目標在相鄰時刻照片的相似度，實現目標跟蹤。李恩等〔9〕利用aHash算法實現人臉特征計算，并通過比較特征來判斷人臉相似度。干麗萍等〔10〕利用pHash算法提取學生圖片格式作業的特征，檢測學生作業的相似度以發現學生抄襲作業的行為。這些研究主要是對算法的直接利用或改進，沒有對3個圖像哈希算法進行細粒度的比較，無法為算法選擇提供參考。姚永明等〔11〕對aHash和pHash算法進行了簡單的介紹，并利用MATLAB對兩個算法進行了仿真測試，但并沒有對兩個算法在相似度檢測精度和性能方面做出比較，不能為其他研究者在選擇算法時提供決策依據。

2 圖像哈希算法

圖片本質上是一個二維信號，它由多個不同頻率成分構成。圖片中低頻成分對應亮度變化較小的區域，高頻成分對應亮度變化較大的區域。低頻成分對應圖像大塊區域，是對整幅圖像強度的綜合度量；高頻成分對應圖片的細節，是對圖像邊緣和輪廓的度量。通過縮小圖片可以快速去除圖像的高頻成分，通常將圖片縮小到8×8、16×16、32×32、64×64等尺寸，尺寸越小圖像細節保留越少，圖像越不清晰。圖1分別給出原圖及其被縮放到64×64、32×32、16×16、8×8大小后，按相同尺寸顯示的圖片效果。方便起見，本文用n×n來描述圖片縮小后的尺寸。

圖1 原圖與縮小到不同尺寸的圖片

2.1 aHash算法aHash算法設計比較簡單，主要利用圖片的低頻成分，通過縮小圖片去除圖片的高頻成分，保留低頻信息，并使用圖像灰度方法化去除圖像色彩來進一步去除高頻成分。在此基礎上，計算灰度圖的像素平均值。遍歷灰度圖每一像素，將其與像素均值做比較，若大于均值，則記下1；否則，記下0，得到二進制串即為圖像Hash值，也稱為圖像指紋。具體算法描述如下：

步驟1：將圖片縮小到n×n，共n2個像素；

步驟 2：將n×n圖片轉換為灰度圖，記為Ga；

步驟 3：計算灰度圖Ga的像素平均值，記為pavg；

步驟4：遍歷Ga中每一個像素pi，并將pi與pavg進行比較，若pi≥pavg，則記下1，否則記下0，得到n2個比特的二進制串即為圖片aHash值，記為Ha；

步驟 5：計算兩張圖片哈希值的海明距離，距離越小圖片越相似，距離越大圖片差異性越大。

2.2 pHash算法任何圖像都可以用頻率域表示，將圖像表示為由不同頻率分量疊加而成的形式。圖像轉換到頻率域后，大部分頻率分量對應的系數很小，只有少數頻率分量對應的系數較大，且系數較大的值一般集中在系數矩陣的左上角，沿對角線方向越往右下角則系數矩陣元素值越小。因此，左上角部分保留了圖片的絕大多數信息。

pHash算法首先利用離散余弦變化（Discrete Cosine Transform，DCT）將圖像從像素域變換為頻率域，再保留其頻率系數矩陣的左上角區域元素來計算圖像哈希，能增加更多的圖像細節。DCT變換如（1）所示：

其中x，y是像素域中元素的坐標，f(x,y)是對應元素的值，n是像素矩陣的階。u，v是頻率域中元素的坐標，F（u，v）是轉換后頻率域的系數矩陣的元素，將系數矩陣記為Mn×n，如（2）所示，其中mk×k，為左上角k×k矩陣。

pHash算法描述如下：

步驟1：將圖片縮小到n×n，共n2個像素；

步驟2：將n×n圖片轉換為灰度圖，記為Gp；

步驟3：進行DCT變化并取系數矩陣左上角的k×k矩陣，Mn×n=DCT（Gp），mk×k=Top_left（Mn×n）。

步驟 4：計算mk×k矩陣元素的平均值，記為eavg；

步驟 5：遍歷mk×k中每一個元素ei，并將ei與eavg進行比較，若ei≥eavg，則記下1，否則記下0，得到k2個比特的二進制串即為圖片aHash值，記為Hp；

步驟 6：計算兩張圖片哈希值的海明距離，距離越小圖片越相似，距離越大圖片差異性越大。

2.3 dHash算法dHash算法基于像素域，根據相鄰像素之間的差異（即像素值間的大小關系）來計算圖片哈希，若兩幅圖的像素間關系越接近，則說明兩幅圖越相似。相鄰像素的比較在像素矩陣的同一行進行，若左邊的像素值大于右邊的像素值，則記為1，否則為0。因此，對比完像素矩陣的所有行后即得到圖像的哈希值。為了得到k2個比特的哈希值，需要將圖片縮小為（k+1）×k大小，因為k+1個元素之間有k個不同的差異，一共k行，可以產生k2個差異值，對應k2個比特的二進制串。dHash算法描述如下：

步驟1：將圖片縮小到（k+1）×k；

步驟 2：將（k+1）×k圖片轉換為灰度圖，記為Gd；

步驟3：遍歷像素矩陣每一行，從左到右比較相鄰兩個像素值，若左邊大于右邊，則記下1，否則記下0，遍歷完所有行后，得到一個k2個比特的二進制串即為圖片dHash值，記為Hd；

步驟 4：計算兩張圖片哈希值的海明距離，距離越小圖片越相似，距離越大圖片差異性越大。

3 算法分析與測試

3.1 算法分析aHash、pHash和dHash 3個算法都可用于計算圖片的特征指紋、檢測圖片相似度。

aHash算法基于像素域設計，原理簡單，實現速度快，圖片尺寸縮放對圖片哈希值的影響較小；但圖像進行伽馬校正或直方圖均衡對圖像哈希值影響較大。更適用于根據縮略圖檢索原圖。

pHash算法基于頻域實現，通過離散余弦變換極大地保留了圖片中低頻成分，相比于aHash算法，pHash保留了更多的細節。pHash算法能夠容忍對圖片做出少量的修改，只要保持圖片的整體結構不變，則其哈希值基本保持不變，能夠避免伽瑪校正或顏色直方圖調整的影響。但相對來說，離散余弦變換比較耗時，因此，3個算法中，pHash速度最慢。

dHash算法設計是基于漸變實現的。在識別效果方面，dHash算法優于aHash算法，但不如pHash算法。在實現速度方面，dHash算法優于pHash算法，但不如aHash快。

3.2 算法測試算法測試包括相似度檢測效果測試和性能測試兩個方面。為了對3個算法的識別效果和實現速度進行細粒度的比較，本文從位于坦桑尼亞西北部的塞倫蓋蒂平原紅外監測照片數據集中挑選了6組照片進行測試，分別標記為a、b、c、d、e、f，如圖2所示。每組包含2張照片，a（1），a（2）為一組，記為a；b（1），b（2）為一組，記為b；以此類推。為了盡可能進行全面的比較，測試照片既有白天拍攝的，也有夜間拍攝的，還有意選擇了一組動物移動較快的照片。圖2中的照片均為紅外相機自動拍攝的照片，其中c、d兩組照片在夜間拍攝，其他均在白天拍攝。第c組照片動物正在移動且速度較快，照片部分區域比較模糊。

圖2 塞倫蓋蒂平原紅外監測照片

相似度檢測效果測試：

分別比較圖2中每一組中兩張照片的相似度（以百分比記）。表1中第一列a、b、c、d、e、f分別對應圖2中的6組照片。對每一組內的兩張照片，分別用aHash、pHash和dHash 3個算法進行測試。測試時，對于3個圖像哈希算法，本文均將圖片分別縮放到8×8、16×16、32×32和64×64 4種不同的尺寸進行測試比較。表1中具體行、列對應的元素值表示該行對應的組內兩張照片，在該列對應的圖像哈希算法和縮放尺寸下的相似度（單位為%）。從表1可以發現：①縮放8×8尺寸的照片后，3種算法比較出來的相似度均偏高，這是因為原圖被縮小太多后，多數細節信息已經丟失的原因；②隨著縮放尺寸的增大，圖片保留的信息增加，相似度呈減小趨勢，說明了兩個不完全相同的圖片保留的細節越多差異越大；③aHash算法對圖片的區分度較小，pHash和dHash兩個算法對圖片的區分度明顯優于aHash；④dHash算法相似度取值區間比較集中，pHash算法相似度取值區間比較分散；⑤pHash和dHash均能較好的反映圖片之間的相似程度，但隨著縮放尺寸的增大，pHash算法能更好地反映圖片之間的真實相似程度。

表1 圖像哈希算法在不同縮放尺寸下的相似度比較（%）

性能測試：

對aHash、pHash和dHash算法在8×8、16×16、32×32和64×64這4種不同尺寸下的實現速度進行測試及比較。測試環境使用普通的臺式計算機，其主要硬件配置為：i5-4690K 3.50 GHz四核CPU，8 GB內存；計算機操作系統為Windows 8.1 64位，編程語言使用Python 3.5。

測試數據集仍然采用塞倫蓋蒂平原紅外監測照片數據集，隨機選擇了50組、100組、300組、600組和1 200組照片進行組內照片比較，每組有3張照片（該數據集拍攝時紅外相機參數設置為每次連續拍攝3張照片），每組均進行3次比較，則對應的相似度計算次數分別為150次、300次、900次、1 800次和3 600次。

性能測試如圖3所示，圖3（a）、圖3（b）分別表示原圖被縮小到8×8、16×16時3個算法的時間花費。可以發現，在圖片尺寸較小、計算次數較少時，3個算法時間花費差別并不明顯，隨著計算次數增加計算性能才逐漸有所區分。圖3（c）、圖3（d）分別表示原圖被縮小到32×32、64×64時3個算法的時間花費，可以看出，計算次數超過900次后，pHash算法時間花費明顯高于aHash和dHash，但aHash與dHash算法時間花費差別仍然不明顯。

圖3 3種算法在不同尺寸下時間花費比較

4 結束語

理論分析和實驗結果均表明，3個圖像哈希算法在圖像相似度檢測方面各有優缺點。本文通過原理分析和實驗測試的方式對3個算法在圖像相似度檢測方面的效果和性能進行了全面的評估，給出了相關的實驗數據，為其他學者提供數據參考。根據實驗測試數據及具體應用領域對識別效果和檢測速度要求，可以為不同的應用選擇合適的算法。也可以結合3個算法的設計原理和實驗數據，對3個算法在精度和速度方面進行改進。

〔1〕HARRIS G，THOMPSON R，CHILDS J L，et al.Auto?matic storage and analysis of camera trap data〔J〕.The Bulletin of the Ecological Society of America，2010，91（3）：352-360.

〔2〕PIDGEON A M，RADELOFF V C，FLATHER C H，et al.Associations of forest bird species richness with housing and landscape patterns across the usa〔J〕.Eco?logical Applications，2007 ，17：1989-2010.

〔3〕 BOWKETT A E，ROVERO F，MARSHALL A R.The use of camera-trap data to model habitat use by ante?lope species in the udzungwa mountain forests，tanza?nia〔J〕.African Journal of Ecology，2008，46（4）：479-487.

〔4〕 DIAZ-PULIDO，GARRIDO A P，ESTEBAN.Densidad de ocelots（leopardus pardalis） en los llanos colombia?nos〔J〕.Mastozoologia Neotropical，2011，18（1）：63-71.

〔5〕 NOROUZZADEH M S，NGUYEN A，KOSMALA M.Automatically identifying wild animals in camera trap imageswithdeeplearning 〔EB∕OL〕. 〔2017-01-05〕.https:∕∕arxir.org∕abs∕1703.05830V1.

〔6〕鄒承明，薛棟，郭雙雙，等.一種改進的圖像相似度算法〔J〕. 計算機科學，2016，43（6）：72-76.

〔7〕潘楠，闞立峰，劉益.犯罪工具圖片快速溯源技術研究〔J〕.昆明理工大學學報（自然科學版），2017，42（3）：52-59.

〔8〕郭儀權.基于哈希的多目標跟蹤算法的研究〔D〕.合肥：安徽大學，2017.