圖像相似度算法 (Google以圖搜圖) 2

Hash Algorithm、Hamming distance

13 min readOct 18, 2020

■ 前提摘要

上一篇為各位介紹了圖像相似度算法 (電子圍籬、移動偵測、入侵偵測) 1的原理，主要介紹SITF圖像相似度算法，如果還沒有看過的朋友可以先參考一下。但由於SIFT的計算複雜度較高，因此計算速度就相對較慢，因此這次為各位介紹另一種速度較快的圖像相似度算法 — 雜湊演算法 /哈希演算法 (Hash Algorithm)。

■ 簡述 (Introduction)

大家是否有想過，我們常常如想要搜尋一張圖片，除了下關鍵字以外，另一種方法為：Google以圖搜圖。下面這張圖片是美國女演員Alyson Hannigan。

當我們透過Google以圖搜圖放入Alyson Hannigan的圖片後，Google即會返回相似圖片對應的搜索結果。

各位是否問過這到底是採用了什麼技術?根據Neal Krawetz博士的文章(Looks Like It)提到，其實透過一個簡單的演算方法，即可得到這樣的結果，這方法就是雜湊演算法 (Hash Algorithm)。

■雜湊演算法簡述(Hash Algorithm)

雜湊演算法是一種從資料中建立一個“數位指紋(Digital Fingerprint)”字符串，每個數位指紋都是一個是一個無法冒充的識別碼，因此擁有唯一性。雜湊演算法主要是將訊息或資料進行壓縮，只取出其主要的特徵，將資料量縮小，並將資料的格式固定下來，具有不可逆的特性。常見的應用包含：圖像相似度比對、檔案驗證、錯誤校正等。

雜湊演算法與加密算法類似，但又與其有不同之處，主要是加密算法再進行加密時，會產生密鑰，事後可將加密的檔案進行還原，但經由雜湊演算法處理過的資料是無法進行還原。

常見的用於圖像處理的雜湊演算法包含以下幾種算法，包含：AHash（Average Hash 均值哈希）、DHash（Difference Hash 差值哈希）、PHash（Perceptual Hash 感知哈希），這類的演算法總稱為：雜湊演算法或稱為哈希演算法 (Hash Algorithm)。

一張高解析度且清楚的圖片可以提供給我們很多訊息與細節，而一張低解析度的圖片只能看出一個輪廓。如果我們想要快速提取圖片的特徵最快速的方法就是壓縮，以下將依序介紹三種Hash Algorithm的步驟與流程。

●均值雜湊演算法（AHash、Average Hash）

Hash算法的主要觀念即為將圖片進行Hash轉化後，生成一組二進制(0、1)的數字串，接著透過比對不同圖片之間的Hash值，計算出圖片之間的相似度，即可得出圖片之間的相似性。aHash除了翻譯成均值雜湊演算法外，也稱作平均哈希演算法，顧名思義在轉換Hash值的途中，會採用到圖片的平均像素為計算標準。

首先我們先準備一張高解析度的照片作為原始照片。

1. 縮小尺寸：去除高頻和細節的最快方式即為縮小圖片，不要保持其長寬比例，我們將圖片縮小至8x8的大小，總共64個像素點。摒棄不同尺寸、比例帶來的圖片差異，只保留結構、明暗等基本資訊，這樣的作法較為彈性，可以任意比較大小尺寸不同的圖片。

img=cv2.resize(img,(8,8),interpolation=cv2.INTER_CUBIC)

2. 灰階化處理：縮放完後可以發現，圖片的細節部分均被移除，僅留下圖片的原來的輪廓。接著將圖片統一轉為灰階，進一步簡化計算量。

gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

3. 計算像素平均值：計算所有64個畫素的灰度平均值。

## =========== Total 為像素和初始值等於0 ===========
    Total = 0
    ahash_str = ''
    for i in range(8):                  #累加求像素之和
        for j in range(8):
            Total = Total + gray[i,j]
    avg = Total / 64                     #平均灰度

4. 比較每個化素的灰度：將64個畫素的灰度與平均值進行比較，如果該畫素點的值大於等於平均值，則將該點註記為1；小於平均值則註記為0。

## =========== 灰度大於平均值為1；反之為0 ===========
for i in range(8):                  
        for j in range(8):
            if  gray[i,j]>avg:
                ahash_str=ahash_str+'1'
            else:
                ahash_str=ahash_str+'0'

5. 計算Hash值：該圖片計算出來的Hash Value是由64位數的整數所組成，這即為這張圖片的指紋，其數字的組合順序並不重要，只要確保每張圖片的組成方式均為相同即可。

Hash Value：1111110001100010110011100001001110100101101000111111011111000111

6. 準備一張要與其比對之圖片，重複上述流程1~5步驟後，獲取其Hash Value。

Hash Value：1100110001010010111011100001001110100101101000111111011111100111

7. 圖片比對：兩張圖片都產生出Hash Value後，即可透過漢明距離（Hamming distance）來計算兩張圖片的差異性。漢明距離計算結果之數值越小，表示兩張圖片的相似度越高；反之計算結果之數值越大表示相似度越低(漢明距離計算方法會在下述介紹)。

兩張圖片均值哈希算法相似度值(漢明距離)為： 6 (最低為 0，最高為 64)

透過Hamming distance的計算結果可以看出，相似度值(漢明距離)為6，基本上可以歸類出兩張圖片的差異很小(畢竟只多了一個聖誕帽)。由於計算結果為數值化呈現，因此可以彈性調整對於兩張圖片相似度的定義。

●漢明距離（Hamming distance）

在資訊理論中，兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

簡單舉個例子給大家說明，兩個等長度的二元碼，數組1為：0111010；數組2為：1111011，透過下圖可以看到，黑色數字為兩個數組間數字均相同之處，而標記紅色為數字不同之處。漢明距離即為計算兩個等長度的二元碼，其位元值不相同之位置的數目，即為此兩個二元碼之漢明距離。因此可以知道這兩個數組有兩處為差異之處(第一點與最後一點)，因此漢明距離即為2。

## =========== 漢明距離 (Hash值對比對) ===========
def cmpHash(hash1,hash2):              
    n=0                                #n表示漢明距離初始值為0
    if len(hash1)!=len(hash2):         #hash長度不同則返回-1代表傳參出錯
        return -1
    for i in range(len(hash1)):        #for迴圈逐一判斷
        if hash1[i]!=hash2[i]:         #不相等則n+1，最終為相似度
           n=n+1
    return n

●感知雜湊演算法（PHash、Perceptual Hash）

感知雜湊演算法(PHash)是三種演算法中最複雜的一種，與均值雜湊演算法(AHash)差別在於PHash是採用DCT（離散餘弦變換）來獲取圖片的低頻資訊。DCT（離散餘弦變換）是一種用於影像壓縮的演算法，可以將影像從畫素轉換到頻域，透過兩次的DCT後，把頻率按照頻率大小進行分離。低頻率的訊息會集中於左上角，右下角則集中高頻率訊息，主要基於計算低頻的均值哈希值，對每張影像產生一組指紋字符串，透過漢明距離來比對影像之間的相似度。

縮小尺寸：將圖片縮小成32*32，目的是為了簡化DCT的計算時間。

image = cv2.resize(image,(32,32), interpolation=cv2.INTER_CUBIC)

2. 灰階化處理：將圖片轉為灰階化，近一步減少計算量。

image = cv2.cvtColor(image,cv2.COLOR_BGR2GRAY)

3. DCT變換：計算圖片的DCT變換，得到32*32的DCT矩陣。

# ========== 將灰度圖轉為浮點型，再進行DCT變換 ==========
dct = cv2.dct(np.float32(image))

4. 縮小DCT：低頻率的訊息會集中於左上角，因此僅取左上角8*8的矩陣。

dct_roi = dct[0:8,0:8]

5. 計算像素平均值：計算所有64個畫素的灰度平均值avreage。

avreage = np.mean(dct_roi)

6. 計算Hash值：將8*8的DCT矩陣，設定成0或1的Hash值。每一個像素點均與像素平均值進行比對，大於等於avreage的像素點就設為1，小於的則設為0。結果並不能告訴我們真實性的低頻率，只能粗略地告訴我們相對於平均值頻率的相對比例。只要圖片的整體結構保持不變，hash結果值就不變。能夠避免伽馬校正或顏色直方圖被調整帶來的影響。對於變形程度在25%以內的圖片也能精準識別。

hash = [] 
for i in range(dct_roi.shape[0]): 
    for j in range(dct_roi.shape[1]): 
        if dct_roi[i,j] > avreage: 
            hash.append(1) 
        else: 
            hash.append(0) 
print('PHash => ',hash)

7. 計算漢明距離：與比對影像之hash值透過漢明距離計算後，即可得出兩張圖片之相似度。

以下為Phash在計算時的流程圖。

●差值雜湊演算法（DHash、Difference Hash）

接下來介紹最後一種算法DHash，與PHash比起來，DHash由於計算較為簡單，因此速度快非常多。與AHash相比，DHash在速度與準確度上的效果更好，下方將簡述其作法。

縮小尺寸：將圖片縮小為9*8，共72個像素點。

#  ========== 將圖片轉化為9*8 ==========image = cv2.resize(image,(9,8),interpolation=cv2.INTER_CUBIC )

2. 灰階化處理：將圖片轉為灰階化，近一步減少計算量。

gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)

3. 計算差異值：從左邊的像素點往右邊比較，如果左邊的像素點大於右邊，則標記為1，反之則為零，最後會產生一個8*8的共64個差異值。

dhash_str = ''for i in range(8):    for j in range(8):        if gray[i,j]>gray[i, j+1]:            dhash_str = dhash_str + '1'        else:            dhash_str = dhash_str + '0'

4. 產生Hash值：計算完成後，產生的數值即為該圖片的Hash值

● 三種算法總結(AHash、PHash、DHash) 與性能比較

在多數文章中，都會看到AHash、PHash、DHash三種結論如下：

AHash：平均雜湊演算法。速度比較快，但是常常不太精確。
PHash：感知雜湊演算法。精確度比較高，但是速度方面較差一些。
DHash：差異雜湊演算法。精確度較高，且速度也非常快。

但由於沒有實際數據進行比較，因此評價較為不太客觀。不過日前看到作者Notzuonotdied在博客上整理一片關於aHash、dHash、pHash比較。主要是將同一張圖片將原圖與以下處理後的原圖進行比較：增加亮度、縮放比例、對比度增強、銳化、模糊、色度增量、旋轉。比較後的結果如下圖。

由測試結果中可以發現到，在速度方面由DHash的計算速度最快；在準確率方面，由PHash的準確率稍微超過DHash一些。但在速度與準確率的雙重考量下，應該是DHash較為推薦，畢竟大量的圖片比較講求的是速度，但準確率不要差距太多的情況下為優先考量。如果真的要講求較為精準的圖片比對算法，建議可以採用SIFT的演算法來進行比對，關於SIFT的演算法可以參考我寫的：圖像相似度算法 (電子圍籬、移動偵測、入侵偵測) 1。

圖像相似度算法 (Google以圖搜圖) 2

Hash Algorithm、Hamming distance

■ 前提摘要

■ 簡述 (Introduction)

■雜湊演算法簡述(Hash Algorithm)

Reference :

Written by 郭耀文