http://www.ruanyifeng.com/blog/2011/07/principle_of_similar_image_search.html
二年前浸须，我寫了《相似圖片搜索的原理》，介紹了一種最簡單的實(shí)現(xiàn)方法努酸。
昨天，我在isnowfy的網(wǎng)站看到说铃，還有其他兩種方法也很簡單鲫售，這里做一些筆記。
一橱鹏、顏色分布法
每張圖片都可以生成顏色分布的直方圖（color histogram）。如果兩張圖片的直方圖很接近堪藐，就可以認(rèn)為它們很相似莉兰。
任何一種顏色都是由紅綠藍(lán)三原色（RGB）構(gòu)成的，所以上圖共有4張直方圖（三原色直方圖 + 最后合成的直方圖）礁竞。
如果每種原色都可以取256個(gè)值糖荒，那么整個(gè)顏色空間共有1600萬種顏色（256的三次方）。針對(duì)這1600萬種顏色比較直方圖模捂，計(jì)算量實(shí)在太大了捶朵，因此需要采用簡化方法》闵穑可以將0～255分成四個(gè)區(qū)：0～63為第0區(qū)泉孩，64～127為第1區(qū)硼端，128～191為第2區(qū)并淋，192～255為第3區(qū)。這意味著紅綠藍(lán)分別有4個(gè)區(qū)珍昨，總共可以構(gòu)成64種組合（4的3次方）县耽。
任何一種顏色必然屬于這64種組合中的一種句喷，這樣就可以統(tǒng)計(jì)每一種組合包含的像素?cái)?shù)量。
上圖是某張圖片的顏色分布表兔毙，將表中最后一欄提取出來唾琼，組成一個(gè)64維向量(7414, 230, 0, 0, 8, ..., 109, 0, 0, 3415, 53929)。這個(gè)向量就是這張圖片的特征值或者叫"指紋"澎剥。
于是锡溯，尋找相似圖片就變成了找出與其最相似的向量。這可以用皮爾遜相關(guān)系數(shù)或者余弦相似度算出哑姚。
二祭饭、內(nèi)容特征法
除了顏色構(gòu)成，還可以從比較圖片內(nèi)容的相似性入手叙量。
首先倡蝙，將原圖轉(zhuǎn)成一張較小的灰度圖片，假定為50x50像素绞佩。然后寺鸥，確定一個(gè)閾值，將灰度圖片轉(zhuǎn)成黑白圖片品山。
如果兩張圖片很相似胆建，它們的黑白輪廓應(yīng)該是相近的。于是肘交，問題就變成了眼坏，第一步如何確定一個(gè)合理的閾值，正確呈現(xiàn)照片中的輪廓酸些？
顯然宰译，前景色與背景色反差越大，輪廓就越明顯魄懂。這意味著沿侈，如果我們找到一個(gè)值，可以使得前景色和背景色各自的"類內(nèi)差異最小"（minimizing the intra-class variance）市栗，或者"類間差異最大"（maximizing the inter-class variance）缀拭，那么這個(gè)值就是理想的閾值。
1979年填帽，日本學(xué)者大津展之證明了蛛淋，"類內(nèi)差異最小"與"類間差異最大"是同一件事，即對(duì)應(yīng)同一個(gè)閾值篡腌。他提出一種簡單的算法褐荷，可以求出這個(gè)閾值，這被稱為"大津法"（Otsu's method）嘹悼。下面就是他的計(jì)算方法叛甫。
假定一張圖片共有n個(gè)像素层宫，其中灰度值小于閾值的像素為 n1 個(gè)，大于等于閾值的像素為 n2 個(gè)（ n1 + n2 = n ）其监。w1 和 w2 表示這兩種像素各自的比重萌腿。
w1 = n1 / n
w2 = n2 / n
再假定，所有灰度值小于閾值的像素的平均值和方差分別為 μ1 和 σ1抖苦，所有灰度值大于等于閾值的像素的平均值和方差分別為 μ2 和 σ2毁菱。于是，可以得到
類內(nèi)差異 = w1(σ1的平方) + w2(σ2的平方)
類間差異 = w1w2(μ1-μ2)^2
可以證明锌历，這兩個(gè)式子是等價(jià)的：得到"類內(nèi)差異"的最小值鼎俘，等同于得到"類間差異"的最大值。不過辩涝，從計(jì)算難度看贸伐，后者的計(jì)算要容易一些。
下一步用"窮舉法"怔揩，將閾值從灰度的最低值到最高值捉邢，依次取一遍，分別代入上面的算式商膊。使得"類內(nèi)差異最小"或"類間差異最大"的那個(gè)值伏伐，就是最終的閾值。具體的實(shí)例和Java算法晕拆，請(qǐng)看這里藐翎。
有了50x50像素的黑白縮略圖，就等于有了一個(gè)50x50的0-1矩陣实幕。矩陣的每個(gè)值對(duì)應(yīng)原圖的一個(gè)像素吝镣，0表示黑色，1表示白色昆庇。這個(gè)矩陣就是一張圖片的特征矩陣末贾。
兩個(gè)特征矩陣的不同之處越少，就代表兩張圖片越相似整吆。這可以用"異或運(yùn)算"實(shí)現(xiàn)（即兩個(gè)值之中只有一個(gè)為1拱撵，則運(yùn)算結(jié)果為1，否則運(yùn)算結(jié)果為0）表蝙。對(duì)不同圖片的特征矩陣進(jìn)行"異或運(yùn)算"拴测，結(jié)果中的1越少，就是越相似的圖片府蛇。
（完）
