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

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

（大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

圖片相似度檢測(cè)是對(duì)兩張或多張圖片的內(nèi)容相似程度進(jìn)行分析對(duì)比，或檢測(cè)某張圖片的內(nèi)容是否包含在另一圖片內(nèi)。圖片相似度比較被廣泛應(yīng)用于基于圖片的搜索引擎、目標(biāo)檢測(cè)、照片過(guò)濾、文獻(xiàn)查重等多個(gè)領(lǐng)域。

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

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

1 相關(guān)工作

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

2 圖像哈希算法

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

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

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

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

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

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

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

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

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

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

其中x，y是像素域中元素的坐標(biāo)，f(x,y)是對(duì)應(yīng)元素的值，n是像素矩陣的階。u，v是頻率域中元素的坐標(biāo)，F(xiàn)（u，v）是轉(zhuǎn)換后頻率域的系數(shù)矩陣的元素，將系數(shù)矩陣記為Mn×n，如（2）所示，其中mk×k，為左上角k×k矩陣。

pHash算法描述如下：

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

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

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

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

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

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

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

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

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

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

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

3 算法分析與測(cè)試

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

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

pHash算法基于頻域?qū)崿F(xiàn)，通過(guò)離散余弦變換極大地保留了圖片中低頻成分，相比于aHash算法，pHash保留了更多的細(xì)節(jié)。pHash算法能夠容忍對(duì)圖片做出少量的修改，只要保持圖片的整體結(jié)構(gòu)不變，則其哈希值基本保持不變，能夠避免伽瑪校正或顏色直方圖調(diào)整的影響。但相對(duì)來(lái)說(shuō)，離散余弦變換比較耗時(shí)，因此，3個(gè)算法中，pHash速度最慢。

dHash算法設(shè)計(jì)是基于漸變實(shí)現(xiàn)的。在識(shí)別效果方面，dHash算法優(yōu)于aHash算法，但不如pHash算法。在實(shí)現(xiàn)速度方面，dHash算法優(yōu)于pHash算法，但不如aHash快。

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

圖2 塞倫蓋蒂平原紅外監(jiān)測(cè)照片

相似度檢測(cè)效果測(cè)試：

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

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

性能測(cè)試：

對(duì)aHash、pHash和dHash算法在8×8、16×16、32×32和64×64這4種不同尺寸下的實(shí)現(xiàn)速度進(jìn)行測(cè)試及比較。測(cè)試環(huán)境使用普通的臺(tái)式計(jì)算機(jī)，其主要硬件配置為：i5-4690K 3.50 GHz四核CPU，8 GB內(nèi)存；計(jì)算機(jī)操作系統(tǒng)為Windows 8.1 64位，編程語(yǔ)言使用Python 3.5。

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

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

圖3 3種算法在不同尺寸下時(shí)間花費(fèi)比較

4 結(jié)束語(yǔ)

理論分析和實(shí)驗(yàn)結(jié)果均表明，3個(gè)圖像哈希算法在圖像相似度檢測(cè)方面各有優(yōu)缺點(diǎn)。本文通過(guò)原理分析和實(shí)驗(yàn)測(cè)試的方式對(duì)3個(gè)算法在圖像相似度檢測(cè)方面的效果和性能進(jìn)行了全面的評(píng)估，給出了相關(guān)的實(shí)驗(yàn)數(shù)據(jù)，為其他學(xué)者提供數(shù)據(jù)參考。根據(jù)實(shí)驗(yàn)測(cè)試數(shù)據(jù)及具體應(yīng)用領(lǐng)域?qū)ψR(shí)別效果和檢測(cè)速度要求，可以為不同的應(yīng)用選擇合適的算法。也可以結(jié)合3個(gè)算法的設(shè)計(jì)原理和實(shí)驗(yàn)數(shù)據(jù)，對(duì)3個(gè)算法在精度和速度方面進(jìn)行改進(jìn)。

〔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，F(xiàn)LATHER 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ìn)的圖像相似度算法〔J〕. 計(jì)算機(jī)科學(xué)，2016，43（6）：72-76.

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

〔8〕郭儀權(quán).基于哈希的多目標(biāo)跟蹤算法的研究〔D〕.合肥：安徽大學(xué)，2017.