感知雜湊算法1 Average Hashing

感知雜湊算法

什麼是感知雜湊算法

感知雜湊算法 (perceptual hash algorithm )，主要是用來產生圖像結構的雜湊值，讓有相似結構的圖片產生相同或相似的雜湊值。而且感知雜湊算法的雜湊值 hash 跟一般雜湊運算有些許不同，可以使用感知雜湊值來比對圖像是否相似。

一般的雜湊運算如 MD5 、SHA ，不同的數據會產生不同的雜湊值，哪怕數據只有一個位元不同，也會產生完全不同的雜湊值，一般稱這個特徵為「雪崩效應」(Avalanche effect )。而感知雜湊算法的雜湊值是可以透過比較雜湊值的漢明距離 (Hamming Distance )來算出圖像的相似度。

average hashing algorithm
均值雜湊算法

1、縮小
要保留圖片結構最快的方式就是把圖片縮小，縮小可以去掉圖片的細節及變化大的高頻部份。縮小的方式只要保持一致，就不會影響比對的正確性。

2、減少顏色
把縮小後的圖片轉為灰階。

3、計算平均值
算出64個像素的平均值

4、計算每個像素的高低值
每個像素跟平均值比較，高於平均值結果計為1，低於平均值結果計為0。此步驟會得出長度為64個位元的結果。

5、組合成雜湊值
將64個位元的結果轉換成十六進制。這也可以看成是把長度為64的二進制結果轉換為64位元的整數類型。

算出均值雜湊之後，就可以比對雜湊值，來判斷圖片是否相同。當圖片放大縮小，更改寬高比時，成生的雜湊不值將保持不變(放大縮小及更改寬高應有有條件限制)。增加減少亮度、對比度及改變顏色時，都不會顯著改變雜湊值。

實作後，以六張經過處理之後的圖片，第七張圖是第一張圖經過直方圖等化處理的結果，進行交叉比對後，將相同位元總數記錄如下表。

xx	h1	h2	h3	h4	h5	h6	h7
h1	xx	57	53	57	64	62	62
h2	57	xx	50	58	57	55	55
h3	53	50	xx	50	53	53	53
h4	57	58	50	xx	57	55	55
h5	64	57	53	57	xx	62	62
h6	62	55	53	55	62	xx	64
h7	62	55	53	55	62	64	xx

結果基本符合預期，對於有旋轉或變形的圖片，雜湊值的相似度較低。經過變色、縮放等操作的雜湊值相似度較高甚至相同(64為雜湊值相同)。程式及圖片附於下方。下一篇文章將會做程式整理及說明。

import numpy as np
from skimage import io, transform, color, util

img = io.imread('asset/g04.png')
hash_size = 8

io.imshow(img)
io.show()

# 縮小
img_r = transform.resize(img, (hash_size, hash_size))
io.imshow(img_r)
io.show()

# 灰階
img_f = color.rgb2gray(img_r)
io.imshow(img_f)
io.show()

# 轉成 0-255
# pixels = np.asarray(img_f)
pixels = util.img_as_ubyte(img_f)
# pixels = np.around(255*img_f)

# 計算平均值
avg = pixels.mean()

#   與平均值的差異
diff = pixels > avg

# 轉換為 bit array
# diff.astype(np.uint8)
# diff.flatten().astype(np.uint8)

# 轉換成每一個 byte 值
np.packbits(diff)

# 輸出 hex
np.packbits(diff).astype(np.uint8).tobytes().hex()


# bin(int("abc123efff", 16))[2:]


def compare_hash(s, diff):
    a1 = diff.flatten().astype(np.uint8)
    a2 = np.array(list(s), dtype=np.uint8)

圖片b1：原始圖

圖片b2：變形+旋轉

圖片b3：變形+黑邊

圖片b4：縮小

圖片b5：加字

圖片b6：放大少許

圖片b7：直方圖等化

下圖為 b1，原始圖，產生 h1 hash

下圖為 b2，變形+旋轉，產生 h2 hash

下圖為 b3，變形+黑邊，產生 h3 hash

下圖為 b4，縮小，產生 h4 hash

下圖為 b5，加字，產生 h5 hash

下圖為 b6，放大少許，產生 h6 hash
感知雜湊算法1 Average Hashing