感知哈希算法

感知哈希算法(以下簡稱PHA)是哈希算法的一類,主要用來做相似圖片的搜尋工作。

簡介

PHA是一類比較哈希方法的統稱。圖片所包含的特徵被用來生成一組指紋(不過它不是唯一的),而這些指紋是可以進行比較的。

算法流程

下面是簡單的步驟,來說明對圖像進行PHA的運算過程 :

第一步,縮小尺寸。

最快速的去除高頻和細節,只保留結構明暗的方法就是縮小尺寸。

將圖片縮小到8x8的尺寸,總共64個像素。摒棄不同尺寸、比例帶來的圖片差異。

第二步,簡化色彩。

將縮小後的圖片,轉為64級灰度。也就是說,所有像素點總共只有64種顏色。

第三步,計算DCT(離散餘弦變換)。

DCT是把圖片分解頻率聚集和梯狀形,雖然JPEG使用8*8的DCT變換,在這裡使用32*32的DCT變換。

第四步,縮小DCT。

雖然DCT的結果是32*32大小的矩陣,但我們只要保留左上角的8*8的矩陣,這部分呈現了圖片中的最低頻率。

第五步,計算平均值。

計算所有64個值的平均值。

第六步,進一步減小DCT。

這是最主要的一步,根據8*8的DCT矩陣,設定0或1的64位的hash值,大於等於DCT均值的設為”1”,小於DCT均值的設為“0”。結果並不能告訴我們真實性的低頻率,只能粗略地告訴我們相對於平均值頻率的相對比例。只要圖片的整體結構保持不變,hash結果值就不變。能夠避免伽馬校正或顏色直方圖被調整帶來的影響。

第七步,計算哈希值。

將64bit設定成64位的長整型,組合的次序並不重要,只要保證所有圖片都採用同樣次序就行了。將32*32的DCT轉換成32*32的圖像。

將上一步的比較結果,組合在一起,就構成了一個64位的整數,這就是這張圖片的指紋。組合的次序並不重要,只要保證所有圖片都採用同樣次序就行了(例如,自左到右、自頂向下、big-endian)。

得到指紋以後,就可以對比不同的圖片,看看64位中有多少位是不一樣的。在理論上,這等同於計算“漢明距離”(Hammingdistance)。如果不相同的數據位不超過5,就說明兩張圖片很相似;如果大於10,就說明這是兩張不同的圖片。

算法評價

這個算法非常好,無論你改變圖片的高寬、亮度甚至顏色,都不會改變哈希值。最關鍵的是速度極快!cool!

相關詞條

熱門詞條

聯絡我們