姚永明， 楊 純， 吳凌燕， 沈 燁

(南京郵電大學 通達學院,江蘇 揚州 225200)

關(guān)于對圖像哈希算法的研究與應(yīng)用

姚永明， 楊 純， 吳凌燕， 沈 燁

(南京郵電大學 通達學院,江蘇 揚州 225200)

傳統(tǒng)的基于文本的檢索方式無法精確地搜索圖片，因此基于圖像內(nèi)容的檢索技術(shù)應(yīng)運而生.它利用圖像哈希算法提取圖像特征，通過量化壓縮等方法產(chǎn)生一個標明圖像指紋的哈希序列，對比哈希序列即可判定兩張圖像的相似度.主要從圖像哈希算法的定義、原理、特點、應(yīng)用等方面進行研究，并著重介紹和對比aHash算法及pHash算法.

均值哈希算法;感知哈希算法;哈希算法；圖片相似搜索

1 概述

在網(wǎng)絡(luò)技術(shù)飛速發(fā)展的當今社會，以圖片、音樂和視頻為主的非結(jié)構(gòu)化數(shù)據(jù)已經(jīng)占據(jù)主導地位，如何從如此龐大的數(shù)據(jù)庫中快速準確地找出我們需要的圖像成為研究重點，同時隨著人們對圖像檢索要求的提高，圖像哈希技術(shù)應(yīng)運而生.其工作原理是通過構(gòu)造哈希函數(shù)將高維的數(shù)據(jù)映射成低維的二值哈希碼，并使其在二值空間中保持高維數(shù)據(jù)的空間結(jié)構(gòu),具有檢索速度快、存儲空間小、表示方式簡潔等優(yōu)點.本文主要對圖像哈希算法的概念及相關(guān)應(yīng)用進行介紹,總結(jié)了aHash算法和pHash算法的基本思想、實現(xiàn)步驟，并通過旋轉(zhuǎn)、縮放圖像，改變圖像顏色、內(nèi)容等實驗對均值哈希算法和感知哈希算法實現(xiàn)相似圖像搜索的效果進行比較,總結(jié)其優(yōu)缺點.

2 圖像哈希算法的介紹及應(yīng)用

圖像哈希技術(shù)可以將任意分辨率的圖像數(shù)據(jù)通過哈希函數(shù)轉(zhuǎn)化為幾十或幾百個比特的二進制編碼序列，稱為哈希編碼.哈希編碼在目前二進制的計算機系統(tǒng)系下，不僅可以加快檢索速度，還節(jié)省了內(nèi)存空間.

2.1 哈希算法含義及特點

哈希的英文為HASH，也叫作散列函數(shù).它是一種單向密碼體制,同時可以把任意長度的輸入，通過散列算法，變換成固定長度的輸出.簡單地說，哈希算法就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù).

HASH主要用于信息安全領(lǐng)域中的加密算法，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做HASH值，即HASH就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系.

2.2 均值哈希算法原理及應(yīng)用

Average Hash,簡稱aHash，即均值哈希算法,主要用于由圖像的縮略圖搜原圖.aHash主要利用圖片的低頻信息，其工作過程如下：

①縮小尺寸：將圖片縮小到8×8的尺寸,共64個像素.

②簡化色彩：將8×8的小圖片轉(zhuǎn)換成灰度圖像.

③計算平均值：計算64個像素的灰度平均值.

④比較像素的灰度：將每個像素的灰度與平均值進行比較，大于或等于平均值記為1，小于平均值記為0.

⑤計算Hash值：將④的比較結(jié)果組合成一個64位的整數(shù)，即該圖片的指紋.

⑥對比圖片指紋：對比不同圖片的指紋,計算出64位不相同位的位數(shù).如果不相同的數(shù)據(jù)位數(shù)不超過5，說明兩張圖片很相似，如果大于10，說明兩張圖片不相同.

2.3 感知哈希算法原理及應(yīng)用

pHash，全稱為Perceptual Hash，即感知哈希算法.主要應(yīng)用于圖像檢索、圖像識別、圖像認證及數(shù)字水印技術(shù).其工作過程如下[1]：

①縮小尺寸：選取大于8×8，32×32的圖片，簡化DCT的計算，而非減小頻率.

②簡化色彩：將圖片轉(zhuǎn)化成灰度圖像，進一步簡化計算量.

③計算DCT：計算圖片的DCT變換，得到32×32的DCT系數(shù)矩陣.

④縮小DCT：保留32×32大小的矩陣中呈現(xiàn)圖片中最低頻率的8×8矩陣.

⑤計算平均值：計算DCT的均值.

⑥計算Hash值：根據(jù)8×8的DCT矩陣，設(shè)置0或1的64位的Hash值，大于等于DCT均值的設(shè)為“1”，小于DCT均值的設(shè)為“0”.組合在一起構(gòu)成一個64位的整數(shù)，即這張圖片的指紋.

3 實踐算法仿真

3.1 Matlab仿真實驗

3.1.1 圖像性質(zhì)及特征

圖像是一種二維的連續(xù)函數(shù)，像素是構(gòu)成數(shù)字圖像的最小單位.圖像特征一般包含顏色特征、紋理特征、形狀特征及空間關(guān)系特征.在計算機上對圖像進行數(shù)字處理的時候，需要對圖像進行采樣和量化，量化級別越高，圖像質(zhì)量越好[2].

3.1.2 圖形變換分析

(1)圖像灰度處理

在數(shù)字圖像處理中，灰度直方圖表達的信息是每種亮度的像素點的個數(shù).直方圖是圖像的一個重要特征，因為它用少量的數(shù)據(jù)就可以表達圖像的灰度統(tǒng)計特征.在Matlab仿真實驗中，建立一個數(shù)組存儲1～256灰度級出現(xiàn)的個數(shù)，然后根據(jù)定義，計算各像素灰度值出現(xiàn)的個數(shù)，如圖1、圖2所示.

圖1 原始圖像

圖2 各像素灰度值個數(shù)圖

(2)基于DCT的圖像去噪

對圖像進行模糊和去噪聲處理，目的是去除太小的細節(jié)或?qū)⒛繕藘?nèi)的小間斷連接起來，以減少對圖像特征識別的影響.一般圖像存在很多冗余和相關(guān)性，也就是說圖像的噪聲在離散余弦變換結(jié)果中處在其高頻部分，而高頻部分的幅值一般很小，利用這一性質(zhì)，很容易實現(xiàn)圖像的噪聲抑制.處理結(jié)果如圖3、圖4所示.

圖3 原始圖像

圖4 濾波處理后的圖像

(3)圖像的縮小與放大

圖像的縮小是通過減少像素個數(shù)來實現(xiàn)的，為減少縮小圖像時的像素丟失，可以采用等間隔采樣的圖像縮小或局部均值的圖像縮小[3].本實驗采用局部均值法縮小圖片，因為它不同于等間隔采樣，僅取在原圖像中的采樣點像素，而是以相鄰的兩個采樣點為分割，將原圖像分成一個個的子塊，縮小圖像的像素取相應(yīng)子塊像素的均值.

一張圖片的高頻成分描述具體的細節(jié)，低頻成分描述大范圍的信息，在對圖像數(shù)字處理時我們希望保留低頻成分去除高頻成分.所以圖像的放大采用雙線性插值法，因為雙線性灰度插值的平滑作用可使得圖像的細節(jié)產(chǎn)生退化，而這種現(xiàn)象在進行圖像放大時尤其明顯.

3.2 JAVA(eclipse)環(huán)境測試

為對比兩種算法相似搜圖的效果，實驗對圖片進行一系列的變化后提取出特征因子，計算出每張圖片的漢明距離，并與原圖的漢明距離進行比較，來判別此圖是否與原圖相似或者全部相同.同時，在多次變換圖形形狀、顏色、大小、內(nèi)容等情況下，分析出算法對何種變換不敏感，并總結(jié)了它們各自的優(yōu)缺點.

3.2.1 均值哈希(aHash)算法的測試

均值哈希算法通過對比圖像指紋的差異，也就是漢明距離來判定圖像是否相似.漢明距離表示兩個等長字對應(yīng)位不相同的數(shù)量，即兩個字之間的差異.若計算以d(x,y)表示的兩個字符串x,y之間的漢明距離，那么對x和y字符串進行異或運算，結(jié)果為1的個數(shù)之和便是它們的漢明距離.

(1)顏色變化的影響：通過5張背景顏色不同的圖片與原圖比較，得如下實驗結(jié)果：

Resources: [0008884b0b080808,ffff4fbcfcfffff7,0008080b0b080800,

0008080b0b080808,0008080b0b080808](指紋數(shù))

Source: ffff4fbcfcfffff7(指紋數(shù))

[16,0,16,16,16](漢明距離)

漢明距離越小說明兩張圖相似度越高，因此只有第2張圖與原圖完全相同，其他的漢明距離都大于10而與原圖不相似.因此顏色的改變對相似搜索有很大的影響.

(2)同樣地，用均值哈希算法對改變了內(nèi)容、大小和旋轉(zhuǎn)角度的圖片進行實驗，并得如下結(jié)論：

a.圖片放大或縮小，或改變縱橫比，結(jié)果值不會改變，對搜索影響不大.

b.均值哈希算法更簡單也更快速，不受圖片大小縮放的影響，但是如果在圖片上加幾個文字，它就無法識別.所以，它的最佳用途是根據(jù)縮略圖找出原圖.

3.2.2 感知哈希(pHash)算法的測試

pHash算法使用離散余弦變換(DCT)來獲取圖片的低頻成分，離散余弦變換公式如下：

其中F(u,v)是變換系數(shù)陣列的元素，式中表示的陣列為N*N.DCT是種圖像壓縮算法，它將圖像從像素域變換到頻率域.

二維圖像進行離散余弦(DCT)變換的步驟：

①獲得圖像的二維數(shù)據(jù)矩陣f(x,y)；

②求離散余弦變換的系數(shù)矩陣A；

③求系數(shù)矩陣對應(yīng)的轉(zhuǎn)置矩陣AT；

④根據(jù)公式[F(u,v)]=Af(x,y)AT計算離散余弦變換.

實驗把對圖形的變換集中在一起，用pHash算法對其進行相似比較，實驗結(jié)果如下：

source:a000000000000000

1-1 2-0 3-2 4-2 5-0 6-0 7-0 8-1 9-16 10-0 11-1

(注：a000000000000000是原圖片的指紋數(shù)；“a-b”型數(shù)據(jù)的a代表圖片序號，b代表漢明距離，b越小就越相似)

本次實驗達到了圖片相似搜索的目的，而且改善了均值哈希算法對顏色的敏感性，從而使得搜索相似圖的效果大大改善.

3.3 實驗總結(jié)

通過Matlab對圖像的分析，我們得知在pHash算法處理圖像中加入DCT變換會使相似搜索的可比性提高，并且采用局部均值法縮小圖像和雙線性插值法放大圖片，減少了圖像像素的丟失，圖片的特征識別效果有所提高.另外eclipse環(huán)境測試的實驗結(jié)果，也說明了均值哈希算法(aHash)更簡單，但是在比較上略顯死板，一旦圖像中涉及顏色變化或者內(nèi)容修改，它將無法識別.感知哈希算法(pHash)雖然比較復(fù)雜，但它能很好地容忍一些小的變形，改善了相似圖片比較的性能.

4 總結(jié)與展望

本文對圖像哈希算法的應(yīng)用背景及相關(guān)理論知識進行了介紹，主要對均值哈希算法和感知哈希算法進行了研究和比較，總結(jié)了它們各自算法的思想、實現(xiàn)過程及優(yōu)缺點.面對大數(shù)據(jù)下的檢索，圖像搜索似乎成為一種趨勢，圖像哈希技術(shù)在圖像檢索、模式識別以及多媒體認證等應(yīng)用領(lǐng)域有著重要的研究意義.今后我們會更加關(guān)注圖像檢索技術(shù)的發(fā)展，努力研究算法的核心思想，并盡其所能地從多方面來提高算法的精確性、抗干擾性.

[1] 牛夏牧,焦玉華.感知哈希綜述[J].電子學報,2008,36(7)：1406-1411.

[2] 趙小川.學以致用：現(xiàn)代數(shù)字圖像處理技術(shù)提高及應(yīng)用案例詳解(MATLAB版)[M].北京：北京航空航天大學出版社,2012.

[3] 史世澤.局部敏感哈希算法的研究[D].西安：西安電子科技大學,2013.

[責任編輯 馬云彤]

Research and Application of the Image Hash Algorithm

YAO Yong-ming, YANG Chun, WU Ling-yan, SHEN Ye

(Tongda College, Nanjing University of Posts and Telecommunications, Yangzhou 225200, China)

The traditional text based retrieval method can not accurately search the image, so the image content based retrieval technology came into being. It uses the image Hashing algorithm to extract image features, and a marked image fingerprint of the Hash sequence is produced by using of the method of quantization and compression, and the similarity of two images can be determined by compared to the Hash sequence. In this paper, the definition, principles, characteristics, applications and other aspects of the image Hashing algorithms are studied, and the aHash algorithm and the pHash algorithm are mainly introduced and compared.

mean Hash algorithm; perceptual Hash algorithm; Hash algorithm; image similarity search

1008-5564(2016)05-0030-04

2016-05-24

2015年江蘇省大學生科技創(chuàng)新訓練計劃項目(CX66615011)

姚永明(1987—)，男，江蘇揚州人，南京郵電大學通達學院講師，主要從事數(shù)字圖像處理研究.

TN919.81

A