CSkin博客

标题: 【图像相似计算】感知哈希算法-图相似计算 [打印本页]

作者: 乔克斯    时间: 2014-8-10 02:20
标题: 【图像相似计算】感知哈希算法-图相似计算
感知哈希算法-图相似计算
Google 图片搜索功能

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

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

原理讲解

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

第一步 缩小图片尺寸

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

        

第二步 转为灰度图片

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

        

第三步 计算灰度平均值

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

第四步 比较像素的灰度

        将每个像素的灰度与平均值进行比较, 如果大于或等于平均值记为1, 小于平均值记为0.

第五步 计算哈希值

         将上一步的比较结果, 组合在一起, 就构成了一个64位的二进制整数, 这就是这张图片的指纹.

第六步 对比图片指纹

        得到图片的指纹后, 就可以对比不同的图片的指纹, 计算出64位中有多少位是不一样的. 如果不相同的数据位数不超过5, 就说明两张图片很相似, 如果大于10, 说明它们是两张不同的图片.

代码实现 (C#版本)

        下面我用C#代码根据上一节所阐述的步骤实现一下.

[C#] 纯文本查看 复制代码
using System;
using System.IO;
using System.Drawing;
using System.Text;

namespace 图像比较
{
    //感知哈希算法——找出相似的图片
    public class SimilarPhoto
    {
        /// <summary>
        /// 获取图片的Hashcode
        /// </summary>
        /// <param name="imageName"></param>
        /// <returns></returns>
        public static string GetImageHashCode(string filePath)
        {
            return GetImageHashCode((Bitmap)Image.FromFile(filePath));
        }

        /// <summary>
        /// 获取图片的Hashcode
        /// </summary>
        /// <param name="imageName"></param>
        /// <returns></returns>
        public static string GetImageHashCode(Stream stream)
        {
            return GetImageHashCode((Bitmap)Image.FromStream(stream));
        }

        /// <summary>
        /// 获取图片的Hashcode
        /// </summary>
        /// <param name="imageName"></param>
        /// <returns></returns>
        public static string GetImageHashCode(Bitmap image)
        {
            int width = 8;
            int height = 8;

            //  第一步
            //  将图片缩小到8x8的尺寸,总共64个像素。这一步的作用是去除图片的细节,
            //  只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。
            Bitmap bmp = new Bitmap(Thumb(image));
            int[] pixels = new int[width * height];

            //  第二步
            //  将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。
            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    Color color = bmp.GetPixel(i, j);
                    pixels[i * height + j] = RGBToGray(color.ToArgb());
                }
            }

            //  第三步
            //  计算所有64个像素的灰度平均值。
            int avgPixel = Average(pixels);

            //  第四步
            //  将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。
            int[] comps = new int[width * height];
            for (int i = 0; i < comps.Length; i++)
            {
                if (pixels >= avgPixel)
                {
                    comps = 1;
                }
                else
                {
                    comps = 0;
                }
            }

            //  第五步
            //  将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。
            StringBuilder hashCode = new StringBuilder();
            for (int i = 0; i < comps.Length; i += 4)
            {
                int result = comps * (int)Math.Pow(2, 3) + comps[i + 1] * (int)Math.Pow(2, 2) + comps[i + 2] * (int)Math.Pow(2, 1) + comps[i + 2];
                hashCode.Append(BinaryToHex(result));
            }
            bmp.Dispose();
            return hashCode.ToString();
        }

        /// <summary>
        /// 计算"汉明距离"(Hamming distance)。
        /// 如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。
        /// </summary>
        /// <param name="sourceHashCode"></param>
        /// <param name="hashCode"></param>
        /// <returns></returns>
        public static int HammingDistance(String sourceHashCode, String hashCode)
        {
            int difference = 0;
            int len = sourceHashCode.Length;

            for (int i = 0; i < len; i++)
            {
                if (sourceHashCode != hashCode)
                {
                    difference++;
                }
            }
            return difference;
        }

        /// <summary>
        /// 缩放图片
        /// </summary>
        /// <param name="imageName"></param>
        /// <returns></returns>
        private static Image Thumb(Bitmap image)
        {
            return image.GetThumbnailImage(8, 8, () => { return false; }, IntPtr.Zero);
        }

        /// <summary>
        /// 转为64级灰度
        /// </summary>
        /// <param name="pixels"></param>
        /// <returns></returns>
        private static int RGBToGray(int pixels)
        {
            int _red = (pixels >> 16) & 0xFF;
            int _green = (pixels >> 8) & 0xFF;
            int _blue = (pixels) & 0xFF;
            return (int)(0.3 * _red + 0.59 * _green + 0.11 * _blue);
        }

        /// <summary>
        /// 计算平均值
        /// </summary>
        /// <param name="pixels"></param>
        /// <returns></returns>
        private static int Average(int[] pixels)
        {
            float m = 0;
            for (int i = 0; i < pixels.Length; ++i)
            {
                m += pixels;
            }
            m = m / pixels.Length;
            return (int)m;
        }

        /// <summary>
        /// 生成16位指纹
        /// </summary>
        /// <param name="binary"></param>
        /// <returns></returns>
        private static char BinaryToHex(int binary)
        {
            char ch = ' ';
            char[] c = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
            ch = c[binary];
            return ch;
        }
    }
}

案例效果截图:


案例源码下载: 感知哈希算法-图相似计算.rar (56 KB, 下载次数: 133, 售价: 1 金钱)


作者: 佐佑    时间: 2014-8-10 10:00
沙发沙发啊思密达,难道百度图片搜索的原理就是这个?
作者: 乔克斯    时间: 2014-8-10 12:24
佐佑 发表于 2014-8-10 10:00
沙发沙发啊思密达,难道百度图片搜索的原理就是这个?

差不多,他们的应该是类似的更高级算法。
作者: 羽叶    时间: 2014-8-10 17:27
棒棒哒~
作者: xiaobo    时间: 2014-8-11 08:42
为什么我每次看这张图片,都感觉她是躺在床上的……
作者: iHomeSoft    时间: 2014-8-11 08:51
做验证码识别的是不是也是这个原理!
作者: 乔克斯    时间: 2014-8-11 09:49
iHomeSoft 发表于 2014-8-11 08:51
做验证码识别的是不是也是这个原理!

不是,这个是针对图相似计算的,和验证码没有关系。
作者: 佐佑    时间: 2014-8-11 22:16
乔克斯 发表于 2014-8-11 09:49
不是,这个是针对图相似计算的,和验证码没有关系。

求个九宫格滑动解锁
作者: 原始    时间: 2014-8-13 18:19
有没有验证码自动识别的算法啊?

作者: 乔克斯    时间: 2014-8-13 18:23
原始 发表于 2014-8-13 18:19
有没有验证码自动识别的算法啊?

验证码多钟多样,没有全能的验证码识别代码的。除非是一些网站的打码功能,都是机器+人工处理验证码,然后给你返回的。貌似要收费。
作者: shaohuatsou    时间: 2014-8-13 21:25
先收藏了。
作者: pain    时间: 2014-11-4 16:47
只是8x8感觉不够细,对比识别不够。应该有更好的方法
作者: 乔克斯    时间: 2014-11-4 16:55
pain 发表于 2014-11-4 16:47
只是8x8感觉不够细,对比识别不够。应该有更好的方法

= =像素比较。。。耗时多了要试试么。
【大图找小图】C#图片对比高速找图源码
http://bbs.cskin.net/forum.php?m ... d=146&fromuid=2
(出处: CSkin论坛)

作者: zhengxl    时间: 2014-11-4 22:27
超级感谢啦
作者: zhengxl    时间: 2014-11-4 22:27
超级感谢啦
作者: zasray    时间: 2014-11-5 11:06
第一次看到这样理论,又长见识了
作者: kenhy    时间: 2014-11-20 00:28
图片指纹...不知道楼主有提取音乐指纹这类代码吗~
作者: 乔克斯    时间: 2014-11-20 11:11
kenhy 发表于 2014-11-20 00:28
图片指纹...不知道楼主有提取音乐指纹这类代码吗~

你可以提取他们的进制码,MD5加密下- -不就是音乐签名了。
作者: dm9901    时间: 2014-11-25 11:04
希望这个可以用,谢谢分享
作者: 王者VIP    时间: 2015-9-25 14:22
这个高端了
作者: agrapier    时间: 2015-10-10 09:21
感谢楼主 学到了新知识
不过用thumb获得缩略图效果不好,图片有点差别识别率就很低了
缩小图片的方法换一下就管用多了
作者: somk    时间: 2015-10-10 13:03
学到新东西
作者: sunkes    时间: 2015-10-22 18:48
学习啦 原来如此
作者: lwlivy    时间: 2017-3-8 17:07
沙发沙发啊思密达
作者: wesson2016    时间: 2017-3-9 10:43
学习一下




欢迎光临 CSkin博客 (http://bbs.cskin.net/) Powered by Discuz! X3.2