【图像相似计算】感知哈希算法-图相似计算

**乔克斯** · 发表于 2014-8-10 02:20:51

感知哈希算法-图相似计算

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;
        }
    }
}

案例效果截图：