Google 圖片搜索功能
在谷歌圖片搜索中, 用戶可以上傳一張圖片, 谷歌顯示因特網(wǎng)中與此圖片相同或者相似的圖片.
比如我上傳一張照片試試效果:
原理講解
參考Neal Krawetz博士的這篇文章, 實(shí)現(xiàn)這種功能的關(guān)鍵技術(shù)叫做"感知哈希算法"(Perceptual Hash Algorithm), 意思是為圖片生成一個(gè)指紋(字符串格式), 兩張圖片的指紋越相似, 說(shuō)明兩張圖片就越相似. 但關(guān)鍵是如何根據(jù)圖片計(jì)算出"指紋"呢? 下面用最簡(jiǎn)單的步驟來(lái)說(shuō)明一下原理:
第一步 縮小圖片尺寸
將圖片縮小到8x8的尺寸, 總共64個(gè)像素. 這一步的作用是去除各種圖片尺寸和圖片比例的差異, 只保留結(jié)構(gòu)、明暗等基本信息.
第二步 轉(zhuǎn)為灰度圖片
將縮小后的圖片, 轉(zhuǎn)為64級(jí)灰度圖片.
第三步 計(jì)算灰度平均值
計(jì)算圖片中所有像素的灰度平均值
第四步 比較像素的灰度
將每個(gè)像素的灰度與平均值進(jìn)行比較, 如果大于或等于平均值記為1, 小于平均值記為0.
第五步 計(jì)算哈希值
將上一步的比較結(jié)果, 組合在一起, 就構(gòu)成了一個(gè)64位的二進(jìn)制整數(shù), 這就是這張圖片的指紋.
第六步 對(duì)比圖片指紋
得到圖片的指紋后, 就可以對(duì)比不同的圖片的指紋, 計(jì)算出64位中有多少位是不一樣的. 如果不相同的數(shù)據(jù)位數(shù)不超過(guò)5, 就說(shuō)明兩張圖片很相似, 如果大于10, 說(shuō)明它們是兩張不同的圖片.
代碼實(shí)現(xiàn) (C#版本)
下面我用C#代碼根據(jù)上一節(jié)所闡述的步驟實(shí)現(xiàn)一下.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | using System; using System.IO; using System.Drawing; namespace SimilarPhoto { class SimilarPhoto { Image SourceImg; public SimilarPhoto( string filePath) { SourceImg = Image.FromFile(filePath); } public SimilarPhoto(Stream stream) { SourceImg = Image.FromStream(stream); } public String GetHash() { Image image = ReduceSize(); Byte[] grayValues = ReduceColor(image); Byte average = CalcAverage(grayValues); String reslut = ComputeBits(grayValues, average); return reslut; } // Step 1 : Reduce size to 8*8 private Image ReduceSize( int width = 8, int height = 8) { Image image = SourceImg.GetThumbnailImage(width, height, () => { return false ; }, IntPtr.Zero); return image; } // Step 2 : Reduce Color private Byte[] ReduceColor(Image image) { Bitmap bitMap = new Bitmap(image); Byte[] grayValues = new Byte[image.Width * image.Height]; for ( int x = 0; x<image.Width; x++) for ( int y = 0; y < image.Height; y++) { Color color = bitMap.GetPixel(x, y); byte grayValue = ( byte )((color.R * 30 + color.G * 59 + color.B * 11) / 100); grayValues[x * image.Width + y] = grayValue; } return grayValues; } // Step 3 : Average the colors private Byte CalcAverage( byte [] values) { int sum = 0; for ( int i = 0; i < values.Length; i++) sum += ( int )values[i]; return Convert.ToByte(sum / values.Length); } // Step 4 : Compute the bits private String ComputeBits( byte [] values, byte averageValue) { char [] result = new char [values.Length]; for ( int i = 0; i < values.Length; i++) { if (values[i] < averageValue) result[i] = '0' ; else result[i] = '1' ; } return new String(result); } // Compare hash public static Int32 CalcSimilarDegree( string a, string b) { if (a.Length != b.Length) throw new ArgumentException(); int count = 0; for ( int i = 0; i < a.Length; i++) { if (a[i] != b[i]) count++; } return count; } } } |
谷歌服務(wù)器里的圖片數(shù)量是百億級(jí)別的, 我電腦里的圖片數(shù)量當(dāng)然沒法比, 但以前做過(guò)爬蟲程序, 電腦里有40,000多人的頭像照片, 就拿它們作為對(duì)比結(jié)果吧! 我計(jì)算出這些圖片的"指紋", 放在一個(gè)txt文本中, 格式如下.
用ASP.NET寫一個(gè)簡(jiǎn)單的頁(yè)面, 允許用戶上傳一張圖片, 后臺(tái)計(jì)算出該圖片的指紋, 并與txt文本中各圖片的指紋對(duì)比, 整理出結(jié)果顯示在頁(yè)面中, 效果如下:
本文地址: http://www.cnblogs.com/technology/archive/2012/07/12/Perceptual-Hash-Algorithm.html
原文:http://www.cnblogs.com/technology/archive/2012/07/12/Perceptual-Hash-Algorithm.html