C#实现谷歌相似图片查询算法

   在谷歌图片搜索中, 用户可以上传一张图片, 谷歌显示因特网中与此图片相同或者相似的图片.

C#实现谷歌相似图片查询算法

        比如我上传一张照片试试效果:

C#实现谷歌相似图片查询算法

原理讲解

  参考Neal Krawetz博士的这篇文章, 实 现这种功能的关键技术叫做"感知哈希算法"(Perceptual Hash Algorithm), 意思是为图片生成一个指纹(字符串格式), 两张 图片的指纹越相似, 说明两张图片就越相似. 但关键是如何根据图片计算出"指纹"呢? 下面用最简单的步骤来说明一下原理:

第一步 缩小图片尺寸

  将图片缩小到8x8的尺寸, 总共64个像素. 这一步的作用是去除各种图片尺寸和图片比例的差异, 只保留结构、明暗等基本信息.

        C#实现谷歌相似图片查询算法

第二步 转为灰度图片

         将缩小后的图片, 转为64级灰度图片.

        C#实现谷歌相似图片查询算法

第三步 计算灰度平均值

         计算图片中所有像素的灰度平均值

第四步 比较像素的灰度

        将每个像素的灰度与平均值进行比较, 如果大于或等于平均值记为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; 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; 
        } 
    } 
}

  谷歌服务器里的图片数量是百亿级别的, 我电脑里的图片数量当然没法比, 但以前做过爬虫程序, 电脑里有40,000多人的头像照片, 就拿它们作为对比结果吧! 我计算出这些图片的"指纹", 放在一个txt文本中, 格式如下. 

C#实现谷歌相似图片查询算法

  用ASP.NET写一个简单的页面, 允许用户上传一张图片, 后台计算出该图片的指纹, 并与txt文本中各图片的指纹对比, 整理出结果显示在页面中, 效果如下:

C#实现谷歌相似图片查询算法

来源:http://www.cnblogs.com/technology/archive/2012/07/12/Perceptual-Hash-Algorithm.html

加支付宝好友偷能量挖...


评论(0)网络
阅读(458)喜欢(1)Asp.Net/C#/WCF