Google圖片搜索的原理

        google的搜索引擎算法是強大的，針對這個問題，一些人址請教了算法組的朋友，他們分享了基本的思路，在這里表示感謝：
 
　　對于這種圖像搜索的算法，一般是三個步驟：
 
　　1. 將目標圖片進行特征提取，描述圖像的算法很多，用的比較多的是：SIFT描述子，指紋算法函數，bundling features算法，hash function(散列函數)等。也可以根據不同的圖像，設計不同的算法，比如圖像局部N階矩的方法提取圖像特征。
 
　　2. 將圖像特征信息進行編碼，并將海量圖像編碼做查找表。對于目標圖像，可以對分辨率較大的圖像進行降采樣，減少運算量后在進行圖像特征提取和編碼處理。
 
　　3. 相似度匹配運算：利用目標圖像的編碼值，在圖像搜索引擎中的圖像數據庫進行全局或是局部的相似度計算;根據所需要的魯棒性，設定閾值，然后將相似度高的圖片預保留下來;最后應該還有一步篩選最佳匹配圖片，這個應該還是用到特征檢測算法。
 
　　其中每個步驟都有很多算法研究，圍繞數學，統計學，圖像編碼，信號處理等理論進行研究。
 
　　下面是阮一峰的一個最簡單的實現：
 
　　你輸入Google圖片的網址，或者直接上傳圖片，Google就會找出與其相似的圖片。下面這張圖片是美國女演員Alyson Hannigan。
 
　　

 

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

 

　　這種技術的原理是什么?計算機怎么知道兩張圖片相似呢?
 
　　根據Neal Krawetz博士的解釋，原理非常簡單易懂。我們可以用一個快速算法，就達到基本的效果。
 
　　這里的關鍵技術叫做"感知哈希算法"(Perceptual hash algorithm)，它的作用是對每張圖片生成一個"指紋"(fingerprint)字符串，然后比較不同圖片的指紋。結果越接近，就說明圖片越相似。
 
　　下面是一個最簡單的實現：
 
　　第一步，縮小尺寸。
 
　　將圖片縮小到8x8的尺寸，總共64個像素。這一步的作用是去除圖片的細節，只保留結構、明暗等基本信息，摒棄不同尺寸、比例帶來的圖片差異。
 
　　

　　第二步，簡化色彩。
 
　　將縮小后的圖片，轉為64級灰度。也就是說，所有像素點總共只有64種顏色。
 
　　第三步，計算平均值。
 
　　計算所有64個像素的灰度平均值。
 
　　第四步，比較像素的灰度。
 
　　將每個像素的灰度，與平均值進行比較。大于或等于平均值，記為1;小于平均值，記為0。
 
　　第五步，計算哈希值。
 
　　將上一步的比較結果，組合在一起，就構成了一個64位的整數，這就是這張圖片的指紋。組合的次序并不重要，只要保證所有圖片都采用同樣次序就行了。
 
　　

　　得到指紋以后，就可以對比不同的圖片，看看64位中有多少位是不一樣的。在理論上，這等同于計算"漢明距離"(Hamming distance)。如果不相同的數據位不超過5，就說明兩張圖片很相似;如果大于10，就說明這是兩張不同的圖片。
 
　　具體的代碼實現，可以參見Wote用python語言寫的imgHash.py。代碼很短，只有53行。使用的時候，第一個參數是基準圖片，第二個參數是用來比較的其他圖片所在的目錄，返回結果是兩張圖片之間不相同的數據位數量(漢明距離)。
 
　　這種算法的優點是簡單快速，不受圖片大小縮放的影響，缺點是圖片的內容不能變更。如果在圖片上加幾個文字，它就認不出來了。所以，它的最佳用途是根據縮略圖，找出原圖。
 
　　實際應用中，往往采用更強大的pHash算法和SIFT算法，它們能夠識別圖片的變形。只要變形程度不超過25%，它們就能匹配原圖。這些算法雖然更復雜，但是原理與上面的簡便算法是一樣的，就是先將圖片轉化成Hash字符串，然后再進行比較。