Google 相似圖片搜索的原理：『感知哈希算法』解析 ！

今年六月的時候，Google 把『相似圖片搜索』正式放上了首頁。
使用者可以用一張圖片，搜索網際網路上所有與它相似的圖片。只要點擊搜索框中照相機的圖標，一個對話框會出現。

輸入圖片的網址或者直接上傳，Google 就會自動找出與其相似的圖片。下面這張圖片是台灣美女主持人艾莉絲。

上傳後，Google 返回如下結果：

其實類似功能的『相似圖片搜索引擎』還有不少，著名的 TinEye（http://www.tineye.com/）甚至可以找出照片的拍攝背景。

那這種技術的原理是什麼？電腦又怎麼知道兩張圖片相似呢？

根據 Neal Krawetz 博士的解釋，原理非常簡單易懂。我們可以用一個快速算法，就達到基本的效果。這裡的關鍵技術叫做『感知哈希算法』（Perceptual hash algorithm），它的作用是對每張圖片生成一個『指紋』（fingerprint）字符串，然後比較不同圖片的指紋。結果越接近，就說明圖片越相似。

下面是一個最簡單的實現：

第一步：
縮小尺寸。將圖片縮小到 8*8 的尺寸，共 64 個像素。這一步的作用是去除圖片的細節，只保留結構、明暗等基本信息，摒棄不同尺寸、比例帶來的圖片差異。

第二步：
簡化色彩。將縮小後的圖片，轉為 64 級灰度。也就是說，所有像素點總共只有 64 種顏色。

第三步：
計算平均值。計算所有 64 個像素的灰度平均值。

第四步：
比較像素的灰度。將每個像素的灰度，與平均值進行比較。大於或等於平均值，記為 1；小於平均值，記為 0。

第五步：
計算哈希值。將上一步的比較結果，組合在一起，就構成一個 64 位的整數，這就是這張圖片的指紋。組合的次序並不重要，只要保證所有圖片都採用同樣次序就行。

= = 8f373714acfcf4d0

經過以上流程得到指紋以後，就可以對比不同的圖片，看看 64 位中有多少位是不一樣的。在理論上，這等同於計算『漢明距離』（Hamming distance）。如果不相同的數據位不超過 5，就說明兩張圖片很相似；如果大於 10，就說明這是兩張不同的圖片。

具體的代碼實現，可以參見 Wote 用 python 語言寫的 imgHash.py。代碼很短，只有 53 行。使用的時候，第一個參數是基準圖片，第二個參數是用來比較的其他圖片所在的目錄，返回結果是兩張圖片之間不相同的數據位數量（漢明距離）。

這種算法的優點是簡單快速，不受圖片大小縮放的影響，缺點是圖片的內容不能變更。如果在圖片上加幾個文字，它就認不出來了。所以，它的最佳用途是根據縮略圖，找出原圖。 實際應用中，往往採用更強大的 pHash 算法和 SIFT 算法，它們能夠識別圖片的變形。只要變形程度不超過 25%，它們就能匹配原圖。這些算法雖然更複雜，但是原理與上面的簡便算法是一樣的，就是先將圖片轉化成 Hash 字符串，然後再進行比較。

===============================================

★數位夢想★ 由 Redwolf 製作以 創用CC 姓名標示-相同方式分享 3.0 台灣 授權條款 釋出