2011年仅孩，Google把“相似圖片搜索”正式放上了首頁府瞄。你可以用一張圖片碧磅，搜索互聯網上所有與它相似的圖片。點擊搜索框中照相機的圖標遵馆。
一個對話框會出現鲸郊。
你輸入網片的網址，或者直接上傳圖片货邓，Google就會找出與其相似的圖片秆撮。下面這張圖片是美國女演員Alyson Hannigan。
上傳后换况，Google返回如下結果
類似的”相似圖片搜索引擎”還有不少职辨，TinEye甚至可以找出照片的拍攝背景盗蟆。
這種技術的原理是什么？計算機怎么知道兩張圖片相似呢舒裤？
根據Neal Krawetz博士的解釋喳资，原理非常簡單易懂。我們可以用一個快速算法腾供，就達到基本的效果仆邓。
這里的關鍵技術叫做”感知哈希算法”（Perceptual hash algorithm），它的作用是對每張圖片生成一個”指紋”（fingerprint）字符串伴鳖，然后比較不同圖片的指紋节值。結果越接近，就說明圖片越相似榜聂。
下面是一個最簡單的實現：
第一步搞疗，縮小尺寸。
將圖片縮小到8×8的尺寸须肆，總共64個像素匿乃。這一步的作用是去除圖片的細節(jié)，只保留結構休吠、明暗等基本信息扳埂，摒棄不同尺寸、比例帶來的圖片差異瘤礁。
第二步，簡化色彩梅尤。
將縮小后的圖片柜思，轉為64級灰度。也就是說巷燥，所有像素點總共只有64種顏色赡盘。
第三步，計算平均值缰揪。
計算所有64個像素的灰度平均值陨享。
第四步，比較像素的灰度钝腺。
將每個像素的灰度抛姑，與平均值進行比較。大于或等于平均值艳狐，記為1定硝；小于平均值，記為0毫目。
第五步蔬啡，計算哈希值诲侮。
將上一步的比較結果，組合在一起箱蟆，就構成了一個64位的整數沟绪，這就是這張圖片的指紋。組合的次序并不重要空猜，只要保證所有圖片都采用同樣次序就行了近零。
得到指紋以后，就可以對比不同的圖片抄肖，看看64位中有多少位是不一樣的久信。在理論上，這等同于計算”漢明距離”（Hamming distance）漓摩。如果不相同的數據位不超過5裙士，就說明兩張圖片很相似；如果大于10管毙，就說明這是兩張不同的圖片腿椎。
具體的代碼實現，可以參見Wote用python語言寫的imgHash.py夭咬。代碼很短啃炸，只有53行。使用的時候卓舵，第一個參數是基準圖片南用，第二個參數是用來比較的其他圖片所在的目錄，返回結果是兩張圖片之間不相同的數據位數量（漢明距離）掏湾。
這種算法的優(yōu)點是簡單快速裹虫，不受圖片大小縮放的影響，缺點是圖片的內容不能變更融击。如果在圖片上加幾個文字筑公，它就認不出來了。所以尊浪，它的最佳用途是根據縮略圖匣屡，找出原圖。
實際應用中拇涤，往往采用更強大的pHash算法和SIFT算法捣作，它們能夠識別圖片的變形。只要變形程度不超過25%工育，它們就能匹配原圖虾宇。這些算法雖然更復雜，但是原理與上面的簡便算法是一樣的如绸，就是先將圖片轉化成Hash字符串嘱朽，然后再進行比較旭贬。
轉注：阮一峰第一篇寫于 2011 年。下面是第二篇搪泳，寫于 2013 年稀轨。
相似圖片搜索的原理（2）
我在 isnowfy 的網站看到，還有其他兩種方法也很簡單岸军，這里做一些筆記奋刽。
一、顏色分布法
每張圖片都可以生成顏色分布的直方圖（color histogram）艰赞。如果兩張圖片的直方圖很接近佣谐，就可以認為它們很相似。
任何一種顏色都是由紅綠藍三原色（RGB）構成的方妖，所以上圖共有4張直方圖（三原色直方圖 + 最后合成的直方圖）狭魂。
如果每種原色都可以取256個值，那么整個顏色空間共有1600萬種顏色（256的三次方）党觅。針對這1600萬種顏色比較直方圖雌澄，計算量實在太大了，因此需要采用簡化方法杯瞻「湮可以將0～255分成四個區(qū)：0～63為第0區(qū)，64～127為第1區(qū)魁莉，128～191為第2區(qū)睬涧，192～255為第3區(qū)。這意味著紅綠藍分別有4個區(qū)沛厨，總共可以構成64種組合（4的3次方）宙地。
任何一種顏色必然屬于這64種組合中的一種，這樣就可以統(tǒng)計每一種組合包含的像素數量逆皮。
上圖是某張圖片的顏色分布表，將表中最后一欄提取出來参袱，組成一個64維向量(7414, 230, 0, 0, 8, …, 109, 0, 0, 3415, 53929)电谣。這個向量就是這張圖片的特征值或者叫”指紋”。
于是抹蚀，尋找相似圖片就變成了找出與其最相似的向量剿牺。這可以用皮爾遜相關系數或者余弦相似度算出。
二环壤、內容特征法
除了顏色構成晒来，還可以從比較圖片內容的相似性入手。
首先郑现，將原圖轉成一張較小的灰度圖片湃崩，假定為50×50像素荧降。然后，確定一個閾值攒读，將灰度圖片轉成黑白圖片朵诫。
如果兩張圖片很相似，它們的黑白輪廓應該是相近的薄扁。于是剪返，問題就變成了，第一步如何確定一個合理的閾值邓梅，正確呈現照片中的輪廓脱盲？
顯然，前景色與背景色反差越大日缨，輪廓就越明顯钱反。這意味著，如果我們找到一個值殿遂，可以使得前景色和背景色各自的”類內差異最小”（minimizing the intra-class variance）诈铛，或者”類間差異最大”（maximizing the inter-class variance），那么這個值就是理想的閾值墨礁。
1979年幢竹，日本學者大津展之證明了，”類內差異最小”與”類間差異最大”是同一件事恩静，即對應同一個閾值焕毫。他提出一種簡單的算法，可以求出這個閾值驶乾，這被稱為”大津法”（Otsu’s method）邑飒。下面就是他的計算方法。
假定一張圖片共有n個像素级乐，其中灰度值小于閾值的像素為 n1 個疙咸，大于等于閾值的像素為 n2 個（ n1 + n2 = n ）。w1 和 w2 表示這兩種像素各自的比重风科。
w1 = n1 / n
w2 = n2 / n
再假定撒轮，所有灰度值小于閾值的像素的平均值和方差分別為 μ1 和 σ1，所有灰度值大于等于閾值的像素的平均值和方差分別為 μ2 和 σ2贼穆。于是题山，可以得到
類內差異 = w1(σ1的平方) + w2(σ2的平方)
類間差異 = w1w2(μ1-μ2)^2
可以證明，這兩個式子是等價的：得到”類內差異”的最小值故痊，等同于得到”類間差異”的最大值顶瞳。不過，從計算難度看，后者的計算要容易一些慨菱。
下一步用”窮舉法”焰络，將閾值從灰度的最低值到最高值，依次取一遍抡柿，分別代入上面的算式舔琅。使得”類內差異最小”或”類間差異最大”的那個值，就是最終的閾值洲劣。具體的實例和Java算法备蚓，請看這里。
有了50×50像素的黑白縮略圖囱稽，就等于有了一個50×50的0-1矩陣郊尝。矩陣的每個值對應原圖的一個像素，0表示黑色战惊，1表示白色流昏。這個矩陣就是一張圖片的特征矩陣。
兩個特征矩陣的不同之處越少吞获，就代表兩張圖片越相似况凉。這可以用”異或運算”實現（即兩個值之中只有一個為1，則運算結果為1各拷，否則運算結果為0）刁绒。對不同圖片的特征矩陣進行”異或運算”，結果中的1越少烤黍，就是越相似的圖片知市。
