姓名：尤學強? 學號：17101223374
轉(zhuǎn)載自：http://mp.weixin.qq.com/s/pD7G40yVGdo50cgvP0DfVw
【嵌牛導讀】：照片的詳細分類，和特征處理
【嵌牛鼻子】：圖片箩张，像素惨远，圖像
【嵌牛提問】：怎樣能讓圖片高清顯示谅摄？
【嵌牛正文】：
2011年冰寻，Google把“相似圖片搜索”正式放上了首頁。你可以用一張圖片，搜索互聯(lián)網(wǎng)上所有與它相似的圖片。點擊搜索框中照相機的圖標聂抢。
一個對話框會出現(xiàn)。
你輸入網(wǎng)片的網(wǎng)址辩尊，或者直接上傳圖片涛浙，Google就會找出與其相似的圖片。下面這張圖片是美國女演員Alyson Hannigan摄欲。
上傳后轿亮，Google返回如下結(jié)果
類似的”相似圖片搜索引擎”還有不少，TinEye甚至可以找出照片的拍攝背景胸墙。
這種技術(shù)的原理是什么我注？計算機怎么知道兩張圖片相似呢？
根據(jù)Neal Krawetz博士的解釋迟隅，原理非常簡單易懂但骨。我們可以用一個快速算法，就達到基本的效果智袭。
這里的關(guān)鍵技術(shù)叫做”感知哈希算法”（Perceptual hash algorithm）奔缠，它的作用是對每張圖片生成一個”指紋”（fingerprint）字符串，然后比較不同圖片的指紋吼野。結(jié)果越接近校哎，就說明圖片越相似。
下面是一個最簡單的實現(xiàn)：
第一步瞳步，縮小尺寸闷哆。
將圖片縮小到8×8的尺寸，總共64個像素单起。這一步的作用是去除圖片的細節(jié)抱怔，只保留結(jié)構(gòu)、明暗等基本信息嘀倒，摒棄不同尺寸屈留、比例帶來的圖片差異。
第二步测蘑，簡化色彩绕沈。
將縮小后的圖片，轉(zhuǎn)為64級灰度帮寻。也就是說乍狐，所有像素點總共只有64種顏色。
第三步固逗，計算平均值浅蚪。
計算所有64個像素的灰度平均值。
第四步烫罩，比較像素的灰度惜傲。
將每個像素的灰度，與平均值進行比較贝攒。大于或等于平均值盗誊，記為1；小于平均值，記為0哈踱。
第五步荒适，計算哈希值。
將上一步的比較結(jié)果开镣，組合在一起刀诬，就構(gòu)成了一個64位的整數(shù)，這就是這張圖片的指紋邪财。組合的次序并不重要陕壹，只要保證所有圖片都采用同樣次序就行了。
得到指紋以后树埠，就可以對比不同的圖片糠馆，看看64位中有多少位是不一樣的。在理論上怎憋，這等同于計算”漢明距離”（Hamming distance）又碌。如果不相同的數(shù)據(jù)位不超過5，就說明兩張圖片很相似盛霎；如果大于10赠橙，就說明這是兩張不同的圖片。
具體的代碼實現(xiàn)愤炸，可以參見Wote用python語言寫的imgHash.py期揪。代碼很短，只有53行规个。使用的時候凤薛，第一個參數(shù)是基準圖片，第二個參數(shù)是用來比較的其他圖片所在的目錄诞仓，返回結(jié)果是兩張圖片之間不相同的數(shù)據(jù)位數(shù)量（漢明距離）缤苫。
這種算法的優(yōu)點是簡單快速，不受圖片大小縮放的影響墅拭，缺點是圖片的內(nèi)容不能變更活玲。如果在圖片上加幾個文字，它就認不出來了谍婉。所以舒憾，它的最佳用途是根據(jù)縮略圖，找出原圖穗熬。
實際應(yīng)用中镀迂，往往采用更強大的pHash算法和SIFT算法，它們能夠識別圖片的變形唤蔗。只要變形程度不超過25%探遵，它們就能匹配原圖窟赏。這些算法雖然更復雜，但是原理與上面的簡便算法是一樣的箱季，就是先將圖片轉(zhuǎn)化成Hash字符串涯穷，然后再進行比較。
我在 isnowfy 的網(wǎng)站看到规哪，還有其他兩種方法也很簡單求豫，這里做一些筆記塌衰。
一诉稍、顏色分布法
每張圖片都可以生成顏色分布的直方圖（color histogram）。如果兩張圖片的直方圖很接近最疆，就可以認為它們很相似杯巨。
任何一種顏色都是由紅綠藍三原色（RGB）構(gòu)成的，所以上圖共有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ū)，總共可以構(gòu)成64種組合（4的3次方）挟冠。
任何一種顏色必然屬于這64種組合中的一種于购，這樣就可以統(tǒng)計每一種組合包含的像素數(shù)量。
上圖是某張圖片的顏色分布表知染，將表中最后一欄提取出來肋僧，組成一個64維向量(7414, 230, 0, 0, 8, …, 109, 0, 0, 3415, 53929)。這個向量就是這張圖片的特征值或者叫”指紋”控淡。
于是嫌吠，尋找相似圖片就變成了找出與其最相似的向量。這可以用皮爾遜相關(guān)系數(shù)或者余弦相似度算出逸寓。
二居兆、內(nèi)容特征法
除了顏色構(gòu)成，還可以從比較圖片內(nèi)容的相似性入手竹伸。
首先泥栖，將原圖轉(zhuǎn)成一張較小的灰度圖片簇宽，假定為50×50像素。然后吧享，確定一個閾值魏割，將灰度圖片轉(zhuǎn)成黑白圖片。
如果兩張圖片很相似钢颂，它們的黑白輪廓應(yīng)該是相近的钞它。于是，問題就變成了殊鞭，第一步如何確定一個合理的閾值遭垛，正確呈現(xiàn)照片中的輪廓？
顯然操灿，前景色與背景色反差越大锯仪，輪廓就越明顯。這意味著趾盐，如果我們找到一個值庶喜，可以使得前景色和背景色各自的”類內(nèi)差異最小”（minimizing the intra-class variance），或者”類間差異最大”（maximizing the inter-class variance）救鲤，那么這個值就是理想的閾值久窟。
1979年，日本學者大津展之證明了本缠，”類內(nèi)差異最小”與”類間差異最大”是同一件事斥扛，即對應(yīng)同一個閾值。他提出一種簡單的算法搓茬，可以求出這個閾值犹赖，這被稱為”大津法”（Otsu’s method）。下面就是他的計算方法卷仑。
假定一張圖片共有n個像素峻村，其中灰度值小于閾值的像素為 n1 個，大于等于閾值的像素為 n2 個（ 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
可以證明锚扎，這兩個式子是等價的：得到”類內(nèi)差異”的最小值吞瞪，等同于得到”類間差異”的最大值。不過驾孔，從計算難度看芍秆，后者的計算要容易一些惯疙。
下一步用”窮舉法”，將閾值從灰度的最低值到最高值妖啥，依次取一遍霉颠，分別代入上面的算式。使得”類內(nèi)差異最小”或”類間差異最大”的那個值荆虱，就是最終的閾值蒿偎。具體的實例和Java算法，請看這里怀读。
有了50×50像素的黑白縮略圖诉位，就等于有了一個50×50的0-1矩陣。矩陣的每個值對應(yīng)原圖的一個像素愿吹，0表示黑色不从，1表示白色惜姐。這個矩陣就是一張圖片的特征矩陣犁跪。
兩個特征矩陣的不同之處越少，就代表兩張圖片越相似歹袁。這可以用”異或運算”實現(xiàn)（即兩個值之中只有一個為1坷衍，則運算結(jié)果為1，否則運算結(jié)果為0）条舔。對不同圖片的特征矩陣進行”異或運算”枫耳，結(jié)果中的1越少，就是越相似的圖片孟抗。
經(jīng)過6年多的發(fā)展迁杨，LSGO軟件技術(shù)團隊在地理信息系統(tǒng)、數(shù)據(jù)統(tǒng)計分析凄硼、計算機視覺領(lǐng)域積累了豐富的研發(fā)經(jīng)驗铅协，也建立了人才培養(yǎng)的完備體系。
歡迎對算法設(shè)計與實現(xiàn)感興趣的同學加入摊沉，與我們共同成長進步狐史。
本微信公眾平臺長期系統(tǒng)化提供有關(guān)機器學習、軟件研發(fā)说墨、教育及學習方法骏全、數(shù)學建模的知識，并將以上知識轉(zhuǎn)化為實踐尼斧。拒絕知識碎片化姜贡、耐心打磨技能、解決實際問題是我們的宗旨和追求棺棵。
