感知雜湊算法2 Perceptual Hashing(DCT)

使用均值雜湊算法 (average hashing algorithm, aHash )已經可以初步達成感知算法所需要的效果，就是類似的圖片會有類似的雜湊值，再透過計算雜湊值的漢明距離 (hamming distance ) 來得到圖片的相似度。可是這個方式遇到改變對圖片均值的變化時，就會產生較大的誤差。例如，原本比均值大，變成比均值小。

而第二種感知雜湊算法則是使用離散餘弦轉換 (discrete cosine transform, DCT) 在頻率域做比較計算。我們先來看看做法的步驟。

一、減少顏色
將圖片轉換為灰階。在改變大小前減少顏色的主要目的是增加效能。

二、減少尺寸
跟 aHash 的減少尺寸目的不同，是為了減少 DCT 運算而不是為了減少細節(高頻)。

三、計算 DCT
DCT 將圖片轉換為一組頻率及標量。這裡使用 32×32 而不是 JPEG 的8×8。這個步驟有兩種做法，第一種是做二維的 DCT ，另一種是做一維的 DCT 。兩種方式結果的差異需要再進一步進行比對。

四、減少 DCT 能量值
只保留代表低頻的 8×8

五、計算平均值
這個步驟有兩種做法，一個是取中位數。另一個是計算代表低頻 8×8 的平均值，但排除第一項。因為通常第一項是低頻，代表的是圖片裡完全平坦的部份，數值通常顯著不同，並且偏離平均值或中位數。

六、計算與平均值的比較
比較64個DCT值與平均值的高低，如果第五步取的是中位數，則是與中位數進行比較。高計為1，低計為0。

七、組合成雜湊值
和 aHash 相同，將64個結果組合成十六進制的字串，成為雜湊值。

python 程式如下

def phash(img):
    img_size = 32
    hash_size = 8
    image = transform.resize(img, (img_size, img_size))

    dct = fp.dct(fp.dct(image, norm='ortho', axis=0), norm='ortho', axis=1)

    dct_lowfreq = dct[:hash_size, 1:hash_size+1]
    med = np.median(dct_lowfreq)
    diff = dct_lowfreq > med
    return diff.flatten().astype(np.uint8)

這裡的步驟第三、五，有另一種計算做法。第三步中的 DCT 使用的是二維轉換，在我們的程式碼第六行，分別對 image 的 x,y 軸做了各一次的一維變換，這個與 OpenCV的 DCT 函數執行結果是一致的 cv2.dct(image.astype('float')) 。另一種做法是只做一維的DCT 變換。而程式碼第八行則對應第五步中的取中位數。
我們將另一種做法同樣寫成一個函數，來進行比對。

def phash_1(img):
    img_size = 32
    hash_size = 8
    image = transform.resize(img, (img_size, img_size))

    dct = fp.dct(image)

    dctlowfreq = dct[:hash_size, 1:hash_size + 1]
    avg = dctlowfreq.mean()
    diff = dctlowfreq > avg
    return diff.flatten().astype(np.uint8)

phash
median	h1	h2	h3	h4	h5	h6	h7
h1	64	48	50	56	64	62	60	2672
h2	48	64	44	50	48	48	46
h3	50	44	64	44	50	50	50
h4	56	50	44	64	56	54	52
h5	64	48	50	56	64	62	60
h6	62	48	50	54	62	64	58
h7	60	46	50	52	60	58	64

mean	h1	h2	h3	h4	h5	h6	h7
h1	64	52	47	51	64	62	61	2644	28
h2	52	64	45	47	52	50	51
h3	47	45	64	40	47	49	48
h4	51	47	40	64	51	51	48
h5	64	52	47	51	64	62	61
h6	62	50	49	51	62	64	59
h7	61	51	48	48	61	59	64

pHash_1
median	h1	h2	h3	h4	h5	h6	h7
h1	64	50	22	48	60	62	58	2326
h2	50	64	24	48	46	48	50
h3	22	24	64	30	22	20	26
h4	48	48	30	64	50	46	50
h5	60	46	22	50	64	60	58
h6	62	48	20	60	60	64	56
h7	58	50	26	46	58	56	64

mean	h1	h2	h3	h4	h5	h6	h7
h1	64	50	22	43	61	62	55	2280	46
h2	50	64	24	43	47	48	47
h3	22	24	64	33	23	22	29
h4	43	43	33	64	46	43	48
h5	61	47	23	46	64	61	54
h6	62	48	22	43	61	64	55
h7	55	47	29	48	54	55	64

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

no reduce	h1	h2	h3	h4	h5	h6	h7
h1	64	48	50	56	64	62	60	2672
h2	48	64	44	50	48	48	46
h3	50	44	64	44	50	50	50
h4	56	50	44	64	56	54	52
h5	64	48	50	56	64	62	60
h6	62	48	50	54	62	64	58
h7	60	46	50	52	60	58	64

結論
數據似乎沒有預期中的應該比 aHash 高。因為我們的圖片相似度很高，而我們預期 DCT 結果應該比均值結果來得好，但結果卻是相反。造成這個結果的原因，除了樣本圖片可能不準確之外，這裡有一個可調整的步驟，就是圖片縮小成 32×32 再進行 DCT ，如果完整尺寸進行 DCT 的效果是否能夠更好呢？經過測試，縮小與否並不影響結果。

在本方法中比較時，使用中位數比較的效果比使用平均值比較的結果來得好。下一個實作 wavelet hashing 來進行比對，看結果是否有改善。