[转载]感知哈希算法——找出相似的图片 – Create Chen – 博客园.
Google 图片搜索功能
在谷歌图片搜索中, 用户可以上传一张图片, 谷歌显示因特网中与此图片相同或者相似的图片.
比如我上传一张照片试试效果:
原理讲解
参考Neal Krawetz博士的这篇文章, 实现这种功能的关键技术叫做”感知哈希算法”(Perceptual Hash Algorithm), 意思是为图片生成一个指纹(字符串格式), 两张图片的指纹越相似, 说明两张图片就越相似. 但关键是如何根据图片计算出”指纹”呢? 下面用最简单的步骤来说明一下原理:
第一步 缩小图片尺寸
将图片缩小到8×8的尺寸, 总共64个像素. 这一步的作用是去除各种图片尺寸和图片比例的差异, 只保留结构、明暗等基本信息.
第二步 转为灰度图片
将缩小后的图片, 转为64级灰度图片.
第三步 计算灰度平均值
计算图片中所有像素的灰度平均值
第四步 比较像素的灰度
将每个像素的灰度与平均值进行比较, 如果大于或等于平均值记为1, 小于平均值记为0.
第五步 计算哈希值
将上一步的比较结果, 组合在一起, 就构成了一个64位的二进制整数, 这就是这张图片的指纹.
第六步 对比图片指纹
得到图片的指纹后, 就可以对比不同的图片的指纹, 计算出64位中有多少位是不一样的. 如果不相同的数据位数不超过5, 就说明两张图片很相似, 如果大于10, 说明它们是两张不同的图片.
代码实现 (C#版本)
下面我用C#代码根据上一节所阐述的步骤实现一下.
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; xfor (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; } } }
谷歌服务器里的图片数量是百亿级别的, 我电脑里的图片数量当然没法比, 但以前做过爬虫程序, 电脑里有40,000多人的头像照片, 就拿它们作为对比结果吧! 我计算出这些图片的”指纹”, 放在一个txt文本中, 格式如下.
用ASP.NET写一个简单的页面, 允许用户上传一张图片, 后台计算出该图片的指纹, 并与txt文本中各图片的指纹对比, 整理出结果显示在页面中, 效果如下:
本文地址: http://www.cnblogs.com/technology/archive/2012/07/12/Perceptual-Hash-Algorithm.html